[计算机类论文精品]c语言数据结构双链表源代码.doc

《[计算机类论文精品]c语言数据结构双链表源代码.doc》由会员分享，可在线阅读，更多相关《[计算机类论文精品]c语言数据结构双链表源代码.doc（7页珍藏版）》请在三一办公上搜索。

1、c语言数据结构双链表源代码/*双链表的创建。此双链表要求为带头节点的，为了算法方便特采用了循环双链表。通过编程发现带头节点的也有其不便之处。为了保持表的一直有序性思考如下：1：表的一开始的创建就要有序。2：插入元素后要做到仍然有序。3：删除元素不会改变表的有序性4：所谓有序，即为非降序或者非升序排列。5：为了做到以上几点，考虑到链表的不易排序性质，特设置一个线性表作为输入缓存空间进行事先排序。关于排序的方法有多种，为了快速完成采用了较为简单的插入排序。copyright :yywill 帖请注明，做人要厚道*/#include typedef struct LNode int data; st

2、ruct LNode *next; struct LNode *prior;*Link,Position;typedef struct List_Struct /* 头节点 */ Link head,tail; int len; int value; /* 0表示升序/非降序排列，1表示降序/非升序排列 */LinkList,*List;/*/MakeNode(Link p,List l,int e) /* 创建节点 */ List InitList(); p-data=e; l-tail=p;/* 此函数只设置尾节点，因为头节点只要设置一次 */*/List InitList() /* 初始

3、化建立双链表 */ LinkList *l; l=(LinkList *)malloc(sizeof(LinkList); l-len=0; l-head=l-tail;/* 当头节点和尾节点指向同一地址时候表示为空表 */ return l;/*/CreateList(int n,List l,int *e) /* 1.建立一个有序的带表头结点的双链表 */ /* n为元素个数 */int i,elem;Position *p1,*p2;Sort(n,e) ;p1=(Position *)malloc(sizeof(Position);elem=e1 ;MakeNode(p1,l,elem)

4、;/* 第一个节点 */p1-next=p1;p1-prior=p1;l-head=p1;l-len=1; if(n=0)return;/* 如果链表只有一个项则不用执行下面的函数，直接退出 */ for(i=2;ilen)+;/* 表长度计数，每循环一次加一 */ p1-next=p2;p2-next=l-head; l-head-prior=p2;p2-prior=p1;p1=p2; l-value=1;/* 默认为非升序创建 */*/ListTraverse(List l) /* 遍历链表 */int i=0;Link p;p=l-head;printf(); for(;ilen;i+)

5、 printf(%d,p-data); p=p-next ; printf();/*/ConListTraverse(List l) /* 反向遍历链表 */int i=0;Link p;p=l-tail;printf(); for(;ilen;i+) printf(%d,p-data); p=p-prior ; printf();/*/Reverse(List l) /* 5.逆置该双链表 */int i=0;Link p1,p2;List l1,l2;p1=l-head;l1=l;p2=l1-head;l1-head=l1-tail;l1-tail=p2; for(;ilen;i+) p2

6、=p1-next; p1-next=p1-prior; p1-prior=p2; p1=p1-prior; if(l-value=1)l-value=0; else l-value=1;/*/LocateElem(int i,List l) /* 3.按位置号查找该双链表 */int j,n;Link p;n=l-len;if(in&n1) printf(nerror!it is not exist!);return ;if(ihead ; for(j=0;jnext; printf(nthe elem_value is:%d,p-data); else p=l-tail ; for(;ipr

7、ior; printf(nthe elem_value is:%d,p-data); /*/int GetCurElem(int n,List l) /* 4.按结点值查找该双链表 */ /* 如查找成功则返回所在位置，如找不到则返回0 */Link p;int i;p=l-head; for(i=0;ilen;i+) if(p-data=n)return i+1; p=p-next; return 0;/*/int InsBefore(Position *p,int e,List l) /* 6.向前插入一个元素 */ /* 1=ndata=e ;s-prior=p-prior;p-prio

8、r-next=s;s-next=p;p-prior=s;l-len=(l-len+1);return 1;/*/int Ins(int e,List l) /* 6.插入一个元素 ,使表仍然保持有序 */Link p,p1,p2;int i;if(l-value=1)/* 降序 */ p=l-head; /* 从头部开始搜寻 */ for(i=1;ilen;i+) p=p-next; if(p-data=e&ehead-data)InsBefore(p,e,l);return 1; /* e比当前元素大且比头元素（即最大的元素）小 */ else if(l-value=0)/* 升序 */ p

9、=l-tail; /* 从尾处开始搜寻 */ for(i=1;ilen;i+) p=p-prior; if(p-data=e&etail-data)InsBefore(p-next,e,l);return 1; /* e比当前元素大且比尾元素（即最大的元素）小 */ InsTail(e,l);return 1; /* 当上述条件都不满足的时候可以认为，该元素该插入到头节点 */ /* 或者尾节点，这是两种特殊的情况。 */*/InsTail(int e,List l) /* 为了简单算法，全部插入到尾节点，头节电的通过导致连标， */ /* 换算成尾节点的情况计算 */ /* 全部插尾巴 */

10、Link p1,p2;p1=l-tail;if(l-tail-data)head-data)value=1) Reverse(l) ; /* 降 */ p2=(Position *)malloc(sizeof(Position); p1=l-tail; MakeNode(p2,l,e); (l-len)+;/* 表长度计数，每循环一次加一 */ p1-next=p2;p2-next=l-head; l-head-prior=p2;p2-prior=p1; else if(l-tail-data=e&l-head-data=e) if(l-value=0)Reverse(l); p2=(Posi

11、tion *)malloc(sizeof(Position); p1=l-tail; MakeNode(p2,l,e); p1-next=p2;p2-next=l-head; l-head-prior=p2;p2-prior=p1; /*/int Remove(int i,List l) /* 7.删除指定位置号结点 */ /* i的合法长度为 1=nhead;n=l-len;if(in)printf(now!);return 0; for(;jnext; p-prior-next=p-next;p-next-prior=p-prior;l-len=(l-len-1);if(i=l-len)l

12、-tail=p-prior;if(i=1)l-head=p-next;free(p);return 1;/*/Sort(int n,int *elem) /* 为了保持表的有序，将输入保存在线性表中 */ /* 先用插入排序法排序好后再创建双链表 */ int i,j; for(i=2;ielemi-1) elem0=elemi ; elemi=elemi-1 ; for(j=i-2;elem0elemj;-j) elemj+1=elemj ; /* 记录后移 */ elemj+1=elem0 ; /*/int RemoveCur(int e,List l) /* 删除某个值的元素，如果该元素

13、不存在则返回0 */ /* 否则返回1，成功 */int i;i=GetCurElem(e,l);if(i=0) return 0;i=Remove(i,l);if(i=0) return 0;else return 1;/*/main()Link p;List l;int e999,i=1,n,elem,j;char c,NO;l=InitList();printf(nplease input the elems of the List:); for(;) printf(n please input the elems:); while(scanf(%d,&ei+)!=1) fflush(s

14、tdin); i-; printf(nplease input integer:); /* 防止用户误操作，清除键盘缓冲区，重置输入条件。 */ printf(n any more?:y/n); for(;) scanf(%c,&c); if(c=y)break; else if(c=n)break; else c=y;continue; if(c=n)break; ; /* 此处输入创建列表 */i=i-1;CreateList(i,l,e);printf(nplease select by NO:);for(j=0;j+)if(j%2=1)printf(n2.ListTraverse);p

15、rintf(n3.ConListTraverse);printf(n4.insert);printf(n5.LocateElem);printf(n6.GetCurElem);printf(n7.RemoveNO);printf(n8.RemoveCurElem);printf(n9.Reverse);printf(n0.Exit);scanf(%c,&NO); switch(NO) break; case 2:ListTraverse(l);break; case 3:ConListTraverse(l);break; case 4:printf(ninput:);scanf(%d,&ele

16、m);Ins(elem,l);break; case 5:printf(ninput:);scanf(%d,&elem);LocateElem(elem,l);break; case 6:printf(ninput:);scanf(%d,&elem);n=GetCurElem(elem,l); if(n=0)printf(nit is not exist!);break; else printf(n the NO is:%d,n);break; case 7:printf(ninput:);scanf(%d,&elem);n=Remove(elem,l); if(n=0)printf(nit is not exist!);break; else break; case 8:printf(ninput:);scanf(%d,&elem);n=RemoveCur(elem,l); if(n=0)printf(nit is not exist!);break; else break; case 9:Reverse(l);break; case 0:exit(); default :;