开发学院软件开发C++ 数据结构C语言实现系列——线性表 阅读

数据结构C语言实现系列——线性表

 2008-03-08 21:38:19 来源:WEB开发网   
核心提示:Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid">#include <stdio.h>#include <stdlib.h>typedef int elemType;//
Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid"> #include <stdio.h>
#include <stdlib.h>
typedef int elemType;
/************************************************************************/
/*        以下是关于线性表顺序存储操作的16种算法             */
/************************************************************************/
strUCt List{
  elemType *list;
  int size;
  int maxSize;
};

void againMalloc(struct List *L)
{  
  /* 空间扩展为原来的2倍,并由p指针所指向,原内容被自动拷贝到p所指向的存储空间 */
  elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType));
  if(!p){  /* 分配失败则退出运行 */
    PRintf("存储空间分配失败! ");
    exit(1);
  }
  L->list = p;  /* 使list指向新线性表空间 */
  L->maxSize = 2 * L->maxSize;  /* 把线性表空间大小修改为新的长度 */
}

/* 1.初始化线性表L,即进行动态存储空间分配并置L为一个空表 */
void initList(struct List *L, int ms)
{
  /* 检查ms是否有效,若无效的则退出运行 */
  if(ms <= 0){
    printf("MaxSize非法! ");
    exit(1);  /* 执行此函数中止程序运行,此函数在stdlib.h中有定义 */
  }
  L->maxSize = ms;  /* 设置线性表空间大小为ms */
  L->size = 0;
  L->list = malloc(ms * sizeof(elemType));
  if(!L->list){
    printf("空间分配失败! ");
    exit(1);
  }
  return;
}

/* 2.清除线性表L中的所有元素,释放存储空间,使之成为一个空表 */
void clearList(struct List *L)
{
  if(L->list != NULL){
    free(L->list);
    L->list = 0;
    L->size = L->maxSize = 0;
  }
  return;
}

/* 3.返回线性表L当前的长度,若L为空则返回0 */
int sizeList(struct List *L)
{
  return L->size;
}

/* 4.判定线性表L是否为空,若为空则返回1, 否则返回0 */
int emptyList(struct List *L)
{
  if(L->size ==0){
    return 1;
  }
  else{
    return 0;
  }
}

/* 5.返回线性表L中第pos个元素的值,若pos超出范围,则停止程序运行 */
elemType getElem(struct List *L, int pos)
{
  if(pos < 1 pos > L->size){  /* 若pos越界则退出运行 */
    printf("元素序号越界! ");
    exit(1);
  }
  return L->list[pos - 1];  /* 返回线性表中序号为pos值的元素值 */
}

/* 6.顺序扫描(即遍历)输出线性表L中的每个元素 */
void traverseList(struct List *L)
{
  int i;
  for(i = 0; i < L->size; i++){
    printf("%d ", L ->list[i]);
  }
  printf(" "); 
  return;
}

/* 7.从线性表L中查找值与x相等的元素,若查找成功则返回其位置,否则返回-1 */
int findList(struct List *L, elemType x)
{
  int i;
  for(i = 0; i < L->size; i++){
    if(L->list[i] == x){
      return i;
    }
  }
  return -1;
}

/* 8.把线性表L中第pos个元素的值修改为x的值,若修改成功返回1,否则返回0 */
int updatePosList(struct List *L, int pos, elemType x)
{
  if(pos < 1 pos > L->size){  /* 若pos越界则修改失败 */
    return 0;
  }
  L->list[pos - 1] = x;
  return 1;
}

/* 9.向线性表L的表头插入元素x */
void inserFirstList(struct List *L, elemType x)
{
  int i;
  if(L->size == L->maxSize){
    againMalloc(L);
  }
  for(i = L->size - 1; i >= 0; i--){
    L->list[i + 1] = L ->list[i];
  }
  L->list[0] = x;
  L->size ++;
  return;
}

/* 10.向线性表L的表尾插入元素x */
void insertLastList(struct List *L, elemType x)
{
  if(L->size == L ->maxSize){  /* 重新分配更大的存储空间 */
    againMalloc(L);
  }
  L->list[L->size] = x;  /* 把x插入到表尾 */
  L->size++;  /* 线性表的长度增加1 */
  return;
}

/* 11.向线性表L中第pos个元素位置插入元素x,若插入成功返回1,否则返回0 */
int insertPosList(struct List *L, int pos, elemType x)
{
  int i;
  if(pos < 1 pos > L->size + 1){  /* 若pos越界则插入失败 */
    return 0;
  }
  if(L->size == L->maxSize){  /* 重新分配更大的存储空间 */
    againMalloc(L);
  }
  for(i = L->size - 1; i >= pos - 1; i--){
    L->list[i + 1] = L->list[i];
  }
  L->list[pos - 1] = x;
  L->size++;
  return 1;
}
/* 12.向有序线性表L中插入元素x, 使得插入后仍然有序*/
void insertOrderList(struct List *L, elemType x)
{
  int i, j;
  /* 若数组空间用完则重新分配更大的存储空间 */
  if(L->size == L->maxSize){
    againMalloc(L);
  }
  /* 顺序查找出x的插入位置 */
  for(i = 0; i < L->size; i++){
    if(x < L->list[i]){ 
      break;
    }
  }
  /* 从表尾到下标i元素依次后移一个位置, 把i的位置空出来 */
  for(j = L->size - 1; j >= i; j--)
    L->list[j+1] = L->list[j];
  /* 把x值赋给下标为i的元素 */  
  L->list[i] = x;
  /* 线性表长度增加1 */
  L->size++;
  return;
}

/* 13.从线性表L中删除表头元素并返回它,若删除失败则停止程序运行 */
elemType deleteFirstList(struct List *L)
{
  elemType temp;
  int i;
  if(L ->size == 0){
    printf("线性表为空,不能进行删除操作! ");
    exit(1);
  }
  temp = L->list[0];
  for(i = 1; i < L->size; i++)
    L->list[i-1] = L->list[i];
  L->size--;
  return temp;
}

/* 14.从线性表L中删除表尾元素并返回它,若删除失败则停止程序运行 */
elemType deleteLastList(struct List *L)
{
  if(L ->size == 0){
    printf("线性表为空,不能进行删除操作! ");
    exit(1);
  }
  L->size--;
  return L ->list[L->size];    /* 返回原来表尾元素的值 */
}
/* 15.从线性表L中删除第pos个元素并返回它,若删除失败则停止程序运行 */
elemType deletePosList(struct List *L, int pos)
{
  elemType temp;
  int i;
  if(pos < 1 pos > L->size){    /* pos越界则删除失败 */
    printf("pos值越界,不能进行删除操作! ");
    exit(1);
  }
  temp = L->list[pos-1];
  for(i = pos; i < L->size; i++)
    L->list[i-1] = L->list[i];
  L->size--;
  return temp;
}
/* 16.从线性表L中删除值为x的第一个元素,若成功返回1,失败返回0 */
int deleteValueList(struct List *L, elemType x)
{
  int i, j;
  /* 从线性表中顺序查找出值为x的第一个元素 */
  for(i = 0; i < L->size; i++){
    if(L->list[i] == x){  
      break;
    }
  }
  /* 若查找失败,表明不存在值为x的元素,返回0 */
  if(i == L->size){
    return 0;
  }
  /* 删除值为x的元素L->list[i] */
  for(j = i + 1; j < L->size; j++){
    L->list[j-1] = L->list[j];
  }
  L->size--;
  return 1;
}

/************************************************************************/

void main()
{
  int a[10] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
  int i;
  struct List L;
  initList(&L, 5);
  for(i = 0; i < 10; i++){
    insertLastList(&L, a[i]);
  }
  insertPosList(&L, 11, 48);    insertPosList(&L, 1, 64);
  printf("%d ", getElem(&L, 1));
  traverseList(&L);
  printf("%d ", findList(&L, 10));
  updatePosList(&L, 3, 20);
  printf("%d ", getElem(&L, 3));
  traverseList(&L);
  deleteFirstList(&L);      deleteFirstList(&L);
  deleteLastList(&L);        deleteLastList(&L);
  deletePosList(&L, 5);      ;deletePosList(&L, 7);
  printf("%d ", sizeList(&L));
  printf("%d ", emptyList(&L));
  traverseList(&L);
  clearList(&L);
  return 0;
} 更多文章 更多内容请看C/C++进阶技术文档 数据结构 数据结构相关文章专题,或
#include <stdio.h>
#include <stdlib.h>
#define NN 12
#define MM 20
typedef int elemType ;
/************************************************************************/
/*       以下是关于线性表链接存储(单链表)操作的16种算法    */
/************************************************************************/
struct sNode{  /* 定义单链表结点类型 */
  elemType data;
  struct sNode *next;
};

/* 1.初始化线性表,即置单链表的表头指针为空 */
void initList(struct sNode* *hl)
{
  *hl = NULL;
  return;
}

/* 2.清除线性表L中的所有元素,即释放单链表L中所有的结点,使之成为一个空表 */
void clearList(struct sNode* *hl)
{
  /* cp和np分别作为指向两个相邻结点的指针 */
  struct sNode *cp, *np;
  cp = *hl;
  /* 遍历单链表,依次释放每个结点 */
  while(cp != NULL){
    np = cp->next;  /* 保存下一个结点的指针 */
    free(cp);
    cp = np;
  }
  *hl = NULL;    /* 置单链表的表头指针为空 */
  return;
}

/* 3.返回单链表的长度 */
int sizeList(struct sNode *hl)
{
  int count = 0;    /* 用于统计结点的个数 */
  while(hl != NULL){
    count++;
    hl = hl->next;
  }
  return count;
}

/* 4.检查单链表是否为空,若为空则返回1,否则返回0 */
int emptyList(struct sNode *hl)
{
  if(hl == NULL){
    return 1;
  }else{
    return 0;
  }
}

/* 5.返回单链表中第pos个结点中的元素,若pos超出范围,则停止程序运行 */
elemType getElem(struct sNode *hl, int pos)
{
  int i = 0;    /* 统计已遍历的结点个数 */
  if(pos < 1){
    printf("pos值非法,退出运行!
");
    exit(1);
  }
  while(hl != NULL){
    i++;
    if(i == pos){
      break;
    }
    hl = hl->next;
  }
  if(hl != NULL){
    return hl->data;
  }else{
    printf("pos值非法,退出运行! ");
    exit(1);
  }
}

/* 6.遍历一个单链表 */
void traverseList(struct sNode *hl)
{
  while(hl != NULL){
    printf("%5d", hl->data);
    hl = hl->next;
  }
  printf(" ");
  return;
}

/* 7.从单链表中查找具有给定值x的第一个元素,若查找成功则返回该结点data域的存储地址,否则返回NULL */
elemType* findList(struct sNode *hl, elemType x)
{
  while(hl != NULL){
    if(hl->data == x){
      return &hl->data;
    }else{
      hl = hl->next;  
    }
  }
  return NULL;
}

/* 8.把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0 */
int updatePosList(struct sNode *hl, int pos, elemType x)
{
  int i = 0;
  struct sNode *p = hl;
  while(p != NULL){    /* 查找第pos个结点 */
    i++;
    if(pos == i){
      break;
    }else{
      p = p->next;
    }
  }
  if(pos == i){
    p->data = x;
    return 1;
  }else{
    return 0;
  }
}

/* 9.向单链表的表头插入一个元素 */
void insertFirstList(struct sNode* *hl, elemType x)
{
  struct sNode *newP;
  newP = malloc(sizeof(struct sNode));
  if(newP == NULL){
    printf("内存分配失败,退出运行!
");
    exit(1);
  }
  newP->data = x;    /* 把x的值赋给新结点的data域 */
  /* 把新结点作为新的表头结点插入 */
  newP->next = *hl;    
  *hl = newP;
  return;
}

/* 10.向单链表的末尾添加一个元素 */
void insertLastList(struct sNode* *hl, elemType x)
{
  struct sNode *newP;
  newP = malloc(sizeof(struct sNode));
  if(newP == NULL){
    printf("内在分配失败,退出运行! ");
    exit(1);
  }
  /* 把x的值赋给新结点的data域,把空值赋给新结点的next域 */
  newP->data = x;
  newP->next = NULL;
  /* 若原表为空,则作为表头结点插入 */
  if(*hl == NULL){
    *hl = newP;    
  }
  /* 查找到表尾结点并完成插入 */
  else{
    struct sNode *p = NULL;
    while(p->next != NULL){
      p = p->next;
    }
    p->next = newP;
  }
  return;
}

/* 11.向单链表中第pos个结点位置插入元素为x的结点,若插入成功返回1,否则返回0 */
int insetPosList(struct sNode* *hl, int pos, elemType x){
  int i = 0;
  struct sNode *newP;
  struct sNode *cp = *hl, *ap = NULL;
  /* 对pos值小于等于0的情况进行处理 */
  if(pos <= 0){
    printf("pos值非法,返回0表示插入失败! ");
    return 0;
  }
  /* 查找第pos个结点 */
  while(cp != NULL){
    i++;
    if(pos == i){
      break;
    }else{
      ap = cp;
      cp = cp->next;
    }
  }
  /* 产生新结点,若分配失败,则停止插入 */
  newP = malloc(sizeof(struct sNode));
  if(newP == NULL){
    printf("内存分配失败,无法进行插入操作!
");
    return 0;
  }
  /* 把x的值赋给新结点的data域 */
  newP->data = x;
  /* 把新结点插入到表头 */
  if(ap == NULL){
    newP->next = cp;    /* 或改为newP->next = *hl; */
    *hl = newP;
  }
  /* 把新结点插入到ap和cp之间 */
  else{
    newP->next = cp;
    ap->next = newP;
  }
  return 1;    /* 插入成功返回1 */
}

/* 12.向有序单链表中插入元素x结点,使得插入后仍然有序 */
void insertOrderList(struct sNode* *hl, elemType x)
{
  /* 把单链表的表头指针赋给cp,把ap置空 */
  struct sNode *cp = *hl, *ap = NULL;
  /* 建立新结点 */
  struct sNode *newP;
  newP = malloc(sizeof(struct sNode));
  if(newP == NULL){
    printf("内在分配失败,退出运行! ");
    exit(1);
  }
  newP->data = x;    /* 把x的值赋给新结点的data域 */
  /* 把新结点插入到表头 */
  if((cp == NULL) (x < cp->data)){
    newP->next = cp;
    *hl = newP;
    return;
  }
  /* 顺序查找出x结点的插入位置 */
  while(cp != NULL){
    if(x < cp->data){
      break;
    }else{
      ap = cp;
      cp = cp->next;
    }
  }
  /* 把x结点插入到ap和cp之间 */
  newP->next = cp;
  ap->next = newP;
  return;
}

/* 13.从单链表中删除表头结点,并把该结点的值返回,若删除失败则停止程序运行 */
elemType deleteFirstList(struct sNode* *hl)
{
  elemType temp;
  struct sNode *p = *hl;    /* 暂存表头结点指针,以便回收 */
  if(*hl == NULL){
    printf("单链表为空,无表头可进行删除,退出运行!
");
    exit(1);
  }
  *hl = (*hl)->next;    /* 使表头指针指向第二个结点 */
  temp = p->data;      /* 暂存原表头元素,以便返回 */
  free(p);        /* 回收被删除的表头结点 */
  return temp;      /* 返回第一个结点的值 */
}

/* 14.从单链表中删除表尾结点并返回它的值,若删除失败则停止程序运行 */
elemType deleteLastList(struct sNode* *hl)
{
  elemType temp;
  /* 初始化cp和ap指针,使cp指向表头结点,使ap为空 */
  struct sNode *cp = *hl;
  struct sNode *ap = NULL;
  /* 单链表为空则停止运行 */
  if(cp == NULL){
    printf("单链表为空,无表头进行删除,退出运行! ");
    exit(1);
  }
  /* 从单链表中查找表尾结点,循环结束时cp指向表尾结点,ap指向其前驱结点 */
  while(cp->next != NULL){
    ap = cp;
    cp = cp->next;
  }
  /* 若单链表中只有一个结点,则需要修改表头指针 */
  if(ap == NULL){
    *hl = (*hl)->next;    /* 或改为*hl = NULL; */
  }
  /* 删除表尾结点 */
  else{
    ap->next = NULL;
  }
  /* 暂存表尾元素,以便返回 */
  temp = cp->data;
  free(cp);    /* 回收被删除的表尾结点 */
  return temp;    /* 返回表尾结点的值 */
}

/* 15.从单链表中删除第pos个结点并返回它的值,若删除失败则停止程序运行 */
elemType deletePosList(struct sNode* *hl, int pos)
{
  int i = 0;
  elemType temp;
  /* 初始化cp和ap指针,使cp指向表头结点,使ap为空 */
  struct sNode *cp = *hl;
  struct sNode *ap = NULL;
  /* 单链表为空或pos值非法则停止运行 */
  if((cp == NULL) (pos <= 0)){
    printf("单链表为空或pos值不正确,退出运行!
");
    exit(1);
  }
  /* 从单链表中查找第pos个结点,找到后由cp指向该结点,由ap指向其前驱结点 */
  while(cp != NULL){
    i++;
    if(i == pos){
      break;
    }
    ap = cp;
    cp = cp->next;
  }
  /* 单链表中没有第pos个结点 */
  if(cp == NULL){
    printf("pos值不正确,退出运行! ");
    exit(1);
  }
  /* 若pos等于1,则需要删除表头结点 */
  if(pos == 1){
    *hl = (*hl)->next;    /* 或改为*hl = cp->next; */
  }
  /* 否则删除非表头结点,此时cp指向该结点,ap指向前驱结点 */
  else{
    ap->next = cp->next;
  }
  /* 暂存第pos个结点的值,以便返回 */
  temp = cp->data;
  free(cp);    /* 回收被删除的第pos个结点 */
  return temp;  /* 返回在temp中暂存的第pos个结点的值 */
}

/* 16.从单链表中删除值为x的第一个结点,若删除成功则返回1,否则返回0 */
int deleteValueList(struct sNode* *hl, elemType x)
{
  /* 初始化cp和ap指针,使cp指向表头结点,使ap为空 */
  struct sNode *cp = *hl;
  struct sNode *ap = NULL;
  /* 从单链表中查找值为x的结点,找到后由cp指向该结点,由ap指向其前驱结点 */
  while(cp != NULL){
    if(cp->data == x){
      break;
    }
    ap = cp;
    cp = cp->next;
  }
  /* 若查找失败,即该单链表中不存在值为x的结点,则返回0 */
  if(cp == NULL){
    return 0;
  }
  /* 假如删除的是表头或非表头结点则分别进行处理 */
  if(ap == NULL){
    *hl = (*hl)->next;    /* 或改为*hl= cp->next */
  }else{
    ap->next = cp->next;
  }
  free(cp);    /* 回收被删除的结点 */
  return 1;    /* 返回1表示删除成功 */
}

/************************************************************************/

int main(int argc, char* argv[])
{
  int a[NN];
  int i;
  struct sNode *p, *h, *s;
  srand(time(NULL));
  initList(&p);
  for(i = 0; i < NN; i++){
    a[i] = rand() & MM;
  }
  printf("随机数序列:");
  for(i = 0; i < NN; i++){
    printf("%5d", a[i]);
  }
  printf(" ");
  printf("随机数逆序:");
  for(i = 0; i < NN; i++){
    insertFirstList(&p, a[i]);
  }
  traverseList(p);
  printf("单链表长度:%5d ", sizeList(p));
  for(h = p; h !
= NULL; h = h->next){
    while(deleteValueList(&(h->next), h->data)){
      ;
    }
  }
  printf("去除重复数:");
  traverseList(p);
  printf("单链表长度:%5d ", sizeList(p));
  h = NULL;
  for(s = p; s != NULL; s = s->next){
    insertOrderList(&h, s->data);
  }
  printf("有序表序列:");
  traverseList(h);
  clearList(&p);
  system("pause");
  return 0;
}
更多文章 更多内容请看C/C++进阶技术文档 数据结构 数据结构相关文章专题,或

Tags:数据结构 实现

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
更多精彩
    赞助商链接

    热点阅读
      焦点图片
        最新推荐
          精彩阅读