[計(jì)算機(jī)類論文精品]c語言數(shù)據(jù)結(jié)構(gòu)雙鏈表源代碼.doc

c語言數(shù)據(jù)結(jié)構(gòu)雙鏈表源代碼/*雙鏈表的創(chuàng)建。此雙鏈表要求為帶頭節(jié)點(diǎn)的，為了算法方便特采用了循環(huán)雙鏈表。通過編程發(fā)現(xiàn)帶頭節(jié)點(diǎn)的也有其不便之處。為了保持表的一直有序性思考如下：1：表的一開始的創(chuàng)建就要有序。2：插入元素后要做到仍然有序。3：刪除元素不會(huì)改變表的有序性4：所謂有序，即為非降序或者非升序排列。5：為了做到以上幾點(diǎn)，考慮到鏈表的不易排序性質(zhì)，特設(shè)置一個(gè)線性表作為輸入緩存空間進(jìn)行事先排序。關(guān)于排序的方法有多種，為了快速完成采用了較為簡(jiǎn)單的插入排序。copyright :yywill 帖請(qǐng)注明，做人要厚道*/#include typedef struct lnode int data; struct lnode *next; struct lnode *prior;*link,position;typedef struct list_struct /* 頭節(jié)點(diǎn) */ link head,tail; int len; int value; /* 0表示升序/非降序排列，1表示降序/非升序排列 */linklist,*list;/*/makenode(link p,list l,int e) /* 創(chuàng)建節(jié)點(diǎn) */ list initlist(); p-data=e; l-tail=p;/* 此函數(shù)只設(shè)置尾節(jié)點(diǎn)，因?yàn)轭^節(jié)點(diǎn)只要設(shè)置一次 */*/list initlist() /* 初始化建立雙鏈表 */ linklist *l; l=(linklist *)malloc(sizeof(linklist); l-len=0; l-head=l-tail;/* 當(dāng)頭節(jié)點(diǎn)和尾節(jié)點(diǎn)指向同一地址時(shí)候表示為空表 */ return l;/*/createlist(int n,list l,int *e) /* 1.建立一個(gè)有序的帶表頭結(jié)點(diǎn)的雙鏈表 */ /* n為元素個(gè)數(shù) */int i,elem;position *p1,*p2;sort(n,e) ;p1=(position *)malloc(sizeof(position);elem=e1 ;makenode(p1,l,elem);/* 第一個(gè)節(jié)點(diǎn) */p1-next=p1;p1-prior=p1;l-head=p1;l-len=1; if(n=0)return;/* 如果鏈表只有一個(gè)項(xiàng)則不用執(zhí)行下面的函數(shù)，直接退出 */ for(i=2;ilen)+;/* 表長(zhǎng)度計(jì)數(shù)，每循環(huán)一次加一 */ p1-next=p2;p2-next=l-head; l-head-prior=p2;p2-prior=p1;p1=p2; l-value=1;/* 默認(rèn)為非升序創(chuàng)建 */*/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.按位置號(hào)查找該雙鏈表 */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.按結(jié)點(diǎn)值查找該雙鏈表 */ /* 如查找成功則返回所在位置，如找不到則返回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.向前插入一個(gè)元素 */ /* 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.插入一個(gè)元素 ,使表仍然保持有序 */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比當(dāng)前元素大且比頭元素（即最大的元素）小 */ 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比當(dāng)前元素大且比尾元素（即最大的元素）小 */ instail(e,l);return 1; /* 當(dāng)上述條件都不滿足的時(shí)候可以認(rèn)為，該元素該插入到頭節(jié)點(diǎn) */ /* 或者尾節(jié)點(diǎn)，這是兩種特殊的情況。 */*/instail(int e,list l) /* 為了簡(jiǎn)單算法，全部插入到尾節(jié)點(diǎn)，頭節(jié)電的通過導(dǎo)致連標(biāo)， */ /* 換算成尾節(jié)點(diǎn)的情況計(jì)算 */ /* 全部插尾巴 */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)+;/* 表長(zhǎng)度計(jì)數(shù)，每循環(huán)一次加一 */ 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.刪除指定位置號(hào)結(jié)點(diǎn) */ /* i的合法長(zhǎng)度為 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) /* 為了保持表的有序，將輸入保存在線性表中 */ /* 先用插入排序法排序好后再創(chuàng)建雙鏈表 */ 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) /* 刪除某個(gè)值的元素，如果該元素不存在則返回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:); /* 防止用戶誤操作，清除鍵盤緩沖區(qū)，重置輸入條件。 */ 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; ; /* 此處輸入創(chuàng)建列表 */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:);