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

c语言数据结构双链表源代码/*双链表的创建。此双链表要求为带头节点的，为了算法方便特采用了循环双链表。通过编程发现带头节点的也有其不便之处。为了保持表的一直有序性思考如下：1：表的一开始的创建就要有序。2：插入元素后要做到仍然有序。3：删除元素不会改变表的有序性4：所谓有序，即为非降序或者非升序排列。5：为了做到以上几点，考虑到链表的不易排序性质，特设置一个线性表作为输入缓存空间进行事先排序。关于排序的方法有多种，为了快速完成采用了较为简单的插入排序。copyright :yywill 帖请注明，做人要厚道*/#include typedef struct lnode int data; struct 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() /* 初始化建立双链表 */ 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);/* 第一个节点 */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+) 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=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(;iprior; 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-prior-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=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) /* 为了简单算法，全部插入到尾节点，头节电的通过导致连标， */ /* 换算成尾节点的情况计算 */ /* 全部插尾巴 */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=(position *)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-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) /* 删除某个值的元素，如果该元素不存在则返回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(stdin); 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);printf(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,&elem);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:);