数据结构C语言版线性表的单链表存储结构表示和实现

1、精品#include<stdio.h>#include<malloc.h>#include<stdlib.h>/*数据结构C语言版线性表的单链表存储结构表示和实现P28-31编译环境：Dev-C+4.9.9.2日期：2011年2月10日*/typedefintElemType;/线性表的单链表存储结构typedefstructLNodeElemTypedata;/数据域structLNode*next;/指针域LNode,*LinkList;/typedefstructLNode*LinkList;/另一种定义LinkList的方法/构造一个空的线性表Lin

2、tInitList(LinkList*L)/*产生头结点L,并使L指向此头结点，头节点的数据域为空，不放数据的。void*malloc(size_t)这里对返回值进行强制类型转换了，返回值是指向空类型的指针类型。*/(*L)=(LinkList)malloc(sizeof(structLNode);if(!(*L)exit(0);/存储分配失败(*L)->next=NULL;/指针域为空return1;/销毁线性表L,将包括头结点在内的所有元素释放其存储空间。intDestroyList(LinkList*L)LinkListq;/由于单链表的每一个元素是单独分配的，所以要一个一个的进行

3、释放感谢下载载精品while(*L)q=(*L)->next;free(*L);/释放*L=q;return1;/*将L重置为空表，即将链表中除头结点外的所有元素释放其存储空间，但是将头结点指针域置空，这和销毁有区别哦。不改变L，所以不需要用指针。*/intClearList(LinkListL)LinkListp,q;p=L->next;/p指向第一个结点while(p)/没到表尾则继续循环q=p->next;free(p);/释放空间p=q;L->next=NULL;/头结点指针域为空，链表成了一个空表return1;/若L为空表(根据头结点L->next来判

4、断，为空则是空表)，则返回1，/否则返回0。intListEmpty(LinkListL)if(L->next)/非空return0;elsereturn1;/返回L中数据元素个数。intListLength(LinkListL)inti=0;LinkListp=L->next;/p指向第一个结点while(p)/没到表尾，则继续循环i+;p=p->next;returni;/算法2.8P29/L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并/返回1,否则返回0。intGetElem(LinkListL,inti,ElemType*e)intj=1;/j为计数器

5、LinkListp=L->next;/p指向第一个结点while(p&&j<i)/顺指针向后查找,直到p指向第i个元素或p为空p=p->next;j+;感谢下载载精品if(!p|j>i)/第i个元素不存在return0;*e=p->data;/取第i个元素return1;/返回L中第1个与e满足关系compare()的数据元素的位序。/若这样的数据元素不存在,则返回值为0intLocateElem(LinkListL,ElemTypee,int(*compare)(ElemType,ElemType)inti=0;LinkListp=L->n

6、ext;while(p)/将链表的每一个元素进行对比i+;if(compare(p->data,e)/找到这样的数据元素returni;p=p->next;return0;/若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱/返回1;否则操作失败,pre_e无定义,返回-1intPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e)LinkListq,p=L->next;/p指向第一个结点感谢下载载while(p->next)/p所指结点有后继q=p->next;/q为p的后继if(q->data

7、=cur_e)*pre_e=p->data;return1;p=q;/p向后移return-1;/若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，/返回1;否则操作失败，next_e无定义，返回-1intNextElem(LinkListL,ElemTypecur_e,ElemType*next_e)LinkListp=L->next;/p指向第一个结点while(p->next)/p所指结点有后继if(p->data=cur_e)*next_e=p->next->data;return1;p=p->next;return-1

8、;/算法2.9P30/在带头结点的单链线性表L中第i个位置之前插入元素eintListInsert(LinkList*L,inti,ElemTypee)intj=0;LinkListp=*L,s;while(p&&j<i-1)/寻找第i-1个结点p=p->next;j+;if(!p|j>i-1)/i小于1或者大于表长return0;s=(LinkList)malloc(sizeof(structLNode);/生成新结点s->data=e;/插入L中s->next=p->next;p->next=s;return1;/算法2.10P30

9、/在带头结点的单链线性表L中，删除第i个元素，并由e返回其值intListDelete(LinkList*L,inti,ElemType*e)intj=0;LinkListp=*L,q;while(p->next&&j<i-1)/寻找第i个结点,并令p指向其前趋p=p->next;j+;if(!p->next|j>i-1)/删除位置不合理return0;q=p->next;/删除并释放结点p->next=q->next;*e=q->data;free(q);return1;/依次对L的每个数据元素调用函数vi()intLis

10、tTraverse(LinkListL,void(*vi)(ElemType)LinkListp=L->next;/对所有元素调用函数viwhile(p)vi(p->data);精品p=p->next;printf("n");return1;/在按非降序排列的线性表L中按非降序插入新的数据元素evoidInsertAscend(LinkListL,ElemTypee)LinkListq=L,p=L->next;while(p&&e>p->data)q=p;p=p->next;q->next=(LinkList)

11、malloc(sizeof(structLNode);/e插在q后q->next->data=e;q->next->next=p;/按非升序排列的线性表L中按非升序插入新的数据元素evoidInsertDescend(LinkListL,ElemTypee)LinkListq=L,p=L->next;while(p&&e<p->data)q=p;p=p->next;q->next=(LinkList)malloc(sizeof(structLNode);/e插在q后q->next->data=e;q->ne

12、xt->next=p;/L的头部插入新的数据元素e,作为链表的第一个元素intHeadInsert(LinkListL,ElemTypee)LinkLists;s=(LinkList)malloc(sizeof(structLNode);/生成新结点s->data=e;/给结点赋值s->next=L->next;/插在表头L->next=s;return1;/在L的尾部插入新的数据元素e,作为链表的最后一个元素intEndInsert(LinkListL,ElemTypee)LinkListp=L;while(p->next)/使p指向表尾元素在表尾生成新结

13、点p=p->next;p->next=(LinkList)malloc(sizeof(structLNode);/p->next->data=e;/给新结点赋值p->next->next=NULL;/表尾return1;/删除L的第一个数据元素，并由e返回其值intDeleteFirst(LinkListL,ElemType*e)LinkListp=L->next;if(p)*e=p->data;L->next=p->next;free(p);return1;elsereturn0;/删除L的最后一个数据元素，并用e返回其值intDe

14、leteTail(LinkListL,ElemType*e)LinkListp=L,q;if(!p->next)/链表为空return0;while(p->next)q=p;p=p->next;q->next=NULL;/新尾结点的next域设为NULL*e=p->data;感谢下载载精品free(p);return1;/删除表中值为e的元素，并返回1；如无此元素，则返回0intDeleteElem(LinkListL,ElemTypee)LinkListp=L,q;while(p)q=p->next;if(q&&q->data=e)p

15、->next=q->next;free(q);return1;p=q;return0;/用e取代表L中第i个元素的值intReplaceElem(LinkListL,inti,ElemTypee)LinkListp=L;intj=0;/找到第i个元素的位置给pwhile(p->next&&j<i)j+;p=p->next;if(j=i)p->data=e;return1;else/表中不存在第i个元素return0;/按非降序建立n个元素的线性表intCreatAscend(LinkList*L,intn)intj;LinkListp,q,s

16、;if(n<=0)return0;InitList(L);printf("请输入%d个元素:(空格)n",n);s=(LinkList)malloc(sizeof(structLNode);/第一个结点scanf("%d",&s->data);s->next=NULL;(*L)->next=s;for(j=1;j<n;j+)s=(LinkList)malloc(sizeof(structLNode);/其余结点scanf("%d",&s->data);q=*L;p=(*L)->

17、next;while(p&&p->data<s->data)/p没到表尾，且所指元素值小于新值q=p;p=p->next;/指针后移s->next=q->next;/元素插在q的后面q->next=s;return1;/按非升序建立n个元素的线性表intCreatDescend(LinkList*L,intn)intj;LinkListp,q,s;if(n<=0)return0;InitList(L);printf("请输入%d个元素:(空格)n",n);s=(LinkList)malloc(sizeof(st

18、ructLNode);/第一个结点scanf("%d",&s->data);s->next=NULL;(*L)->next=s;for(j=1;j<n;j+)s=(LinkList)malloc(sizeof(structLNode);/其余结点scanf("%d",&s->data);q=*L;p=(*L)->next;while(p&&p->data>s->data)/p没到表尾，且所指元素值大于新值q=p;p=p->next;/指针后移s->next=

19、q->next;/元素插在q的后面q->next=s;return1;/返回表头元素的值intGetFirstElem(LinkListL,ElemType*e)LinkListp=L->next;/第一个结点给pif(!p)/空表return0;else/非空表*e=p->data;return1;/算法2.11P30/逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表voidCreateList(LinkList*L,intn)inti;LinkListp;/先建立一个带头结点的空单链表，相当于初始化单链表*L=(LinkList)malloc(size

20、of(structLNode);(*L)->next=NULL;printf("请输入%d个数据n",n);for(i=n;i>0;-i)p=(LinkList)malloc(sizeof(structLNode);/生成新结点scanf("%d",&p->data);/输入元素值p->next=(*L)->next;/插入到表头(*L)->next=p;感谢下载载精品/正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表voidCreateList2(LinkList*L,intn)inti;Lin

21、kListp,q;/先建立一个带头结点的空单链表，相当于初始化单链表*L=(LinkList)malloc(sizeof(structLNode);/生成头结点(*L)->next=NULL;q=*L;printf("请输入%d个数据n",n);for(i=1;i<=n;i+)p=(LinkList)malloc(sizeof(structLNode);scanf("%d",&p->data);q->next=p;q=q->next;p->next=NULL;/*用单链表重写算法2.2供参考已知线性表La和Lb

22、中的数据元素按值非递减排列。归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列voidMergeList(LinkListLa,LinkListLb,LinkList*Lc)inti=1,j=1,k=0;intLa_len,Lb_len;ElemTypeai,bj;InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);while(i<=La_len&&j<=Lb_len)/表La和表Lb均非空GetElem(La,i,&ai);GetElem(Lb,j,&bj);if(ai&l

23、t;=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;while(i<=La_len)/表La非空且表Lb空GetElem(La,i+,&ai);ListInsert(Lc,+k,ai);while(j<=Lb_len)/表Lb非空且表La空GetElem(Lb,j+,&bj);ListInsert(Lc,+k,bj);*/算法2.12P31/已知单链线性表La和Lb的元素按值非递减排列。/归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列voidMergeList(LinkListLa,L

24、inkList*Lb,LinkList*Lc)LinkListpa=La->next,pb=(*Lb)->next,pc;*Lc=pc=La;/用La的头结点作为Lc的头结点while(pa&&pb)if(pa->data<=pb->data)pc->next=pa;*Lc=pa;pa=pa->next;elsepc->next=pb;pc=pb;pb=pb->next;感谢下载载精品pc->next=pa?pa:pb;/插入剩余段free(*Lb);/释放Lb的头结点Lb=NULL;/判断是否相等的函数，Union(

25、)用到intequal(ElemTypec1,ElemTypec2)if(c1=c2)return1;elsereturn0;/算法2.1La 中/将所有在线性表Lb中但不在La中的数据元素插入到voidUnion(LinkListLa,LinkListLb)ElemTypee;intLa_len,Lb_len;inti;La_len=ListLength(La);/求线性表的长度Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i+)GetElem(Lb,i,&e);/取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal)

26、/La中不存在和e相同的元素,则插入之ListInsert(&La,+La_len,e);/数据元素判定函数(相等为1,否则为0)intcomp(ElemTypec1,ElemTypec2)if(c1=c2)return1;elsereturn0;voidvisit(ElemTypec)printf("%d",c);intmain()LinkListL,La,Lb,Lc;ElemTypee,e0,d;inti,j,n,k;/初始化一个单链表i=InitList(&L);/通过插入操作创建一个单链表for(j=1;j<=5;j+)i=ListInsert

27、(&L,1,j);/调用visit函数，对单链表进行遍历printf("在L的表头依次插入15后：L=");ListTraverse(L,visit);/依次对元素调用visit()，输出元素的值感谢下载载精品/判断单链表是否为空i=ListEmpty(L);printf("L是否空：i=%d(1:是0:否)n”,i);/清空单链表i=ClearList(L);printf("清空L后：L=");ListTraverse(L,visit);/判断单链表是否为空i=ListEmpty(L);printf("L是否空：i=%d(1

28、:是0:否)n”,i);/再次通过插入操作创建一个单链表for(j=1;j<=10;j+)ListInsert(&L,j,j);printf("在L的表尾依次插入110后：L=");ListTraverse(L,visit);/取得单链表的第5个元素GetElem(L,5,&e);printf("第5个元素的值为：%dn",e);/在单链表中找到和j满足comp函数关系的元素for(j=0;j<=1;j+)k=LocateElem(L,j,comp);if(k)printf("第%d个元素的值为%dn",k

29、,j);elseprintf("没有值为%d的元素n",j);/找到某个元素的前驱for(j=1;j<=2;j+)/测试头两个数据GetElem(L,j,&e0);/把第j个数据赋给e0i=PriorElem(L,e0,&e);/求e0的前驱if(i=-1)printf("元素%d无前驱n",e0);elseprintf("元素%d的前驱为：%dn",e0,e);测试最后两个数据/找到某个元素的后继for(j=ListLength(L)-1;j<=ListLength(L);j+)/GetElem(L,j,

30、&e0);/把第j个数据赋给e0i=NextElem(L,e0,&e);/求e0的后继if(i=-1)printf("元素%d无后继n",e0);elseprintf("元素%d的后继为：%dn",e0,e);/求单链表的表长k=ListLength(L);/k为表长/删除操作for(j=k+1;j>=k;j-)i=ListDelete(&L,j,&e);/删除第j个数据if(i=0)printf("删除第%d个数据失败n",j);else感谢下载载精品printf("删除的元素为：%d

31、n",e);printf("依次输出L的元素：");ListTraverse(L,visit);/销毁单链表DestroyList(&L);printf("销毁L后：L=%unn",L);printf("按非降序建立n个元素的线性表L,请输入元素个数n:");scanf("%d",&n);CreatAscend(&L,n);printf("依次输出L的元素：");ListTraverse(L,visit);/按非降序插入元素10InsertAscend(L,10

32、);printf("按非降序插入元素10后，线性表L为：")；ListTraverse(L,visit);/在L的头部插入12HeadInsert(L,12);/在L的尾部插入9EndInsert(L,9);printf("在L的头部插入12，尾部插入9后，线性表L为：");ListTraverse(L,visit);i=GetFirstElem(L,&e);printf("第1个元素是:%dn",e);printf("请输入要删除的元素的值:");scanf("%d",&e);

33、i=DeleteElem(L,e);if(i)printf("成功删除%d!n",e);elseprintf("不存在元素%d!n",e);printf("线性表L为：");ListTraverse(L,visit);printf("请输入要取代的元素的序号元素的新值:");scanf("%d%d",&n,&e);ReplaceElem(L,n,e);printf("线性表L为：");ListTraverse(L,visit);DestroyList(&

34、;L);printf("销毁L后，按非升序重新建立n个元素的线性表L,请输入""元素个数n(>2):");scanf("%d",&n);CreatDescend(&L,n);printf("依次输出L的元素：");ListTraverse(L,visit);/按非升序插入元素10InsertDescend(L,10);printf("按非升序插入元素10后，线性表L为：")；ListTraverse(L,visit);printf("请输入要删除的元素的值:&qu

35、ot;);scanf("%d",&e);i=DeleteElem(L,e);if(i)printf("成功删除%d!n",e);elseprintf("不存在元素%d!n",e);printf("线性表L为：");ListTraverse(L,visit);DeleteFirst(L,&e);DeleteTail(L,&d);printf("删除表头元素%d和表尾元素%d后,线性表L为：",e,d);ListTraverse(L,visit);printf("n

36、");/测试算法2.11n=3;CreateList2(&La,n);/正位序输入n个元素的值printf("正位创建后La=");/输出链表La的内容ListTraverse(La,visit);CreateList(&Lb,n);/逆位序输入n个元素的值printf("逆位创建后Lb=");/输出链表Lb的内容ListTraverse(Lb,visit);DestroyList(&La);DestroyList(&Lb);/测试算法2.12/初始化一个单链表Lai=InitList(&La);/通过插入操作创建一个单链表for(j=2;j<=10;j+=2)i=ListInsert(&La,1,j);printf("La=");/输出链表La的内容ListTraverse(La,visit);/初始化一个单链表i=InitList(&Lb);/通过插入操作创建一个单链表for(j=1;j<=10;j+=2)i=ListInsert(&Lb,1,j);printf("Lb=");/输出链表Lb的内容Lis