數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)單鏈表操作

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告內(nèi)容及其格式數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目： 單鏈表操作專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí)： 單鏈表操作針對(duì)帶頭結(jié)點(diǎn)的單循環(huán)鏈表，編寫實(shí)現(xiàn)以下操作的算法函數(shù)。實(shí)現(xiàn)要求： 單鏈表建立函數(shù)create：先輸入數(shù)據(jù)到一維數(shù)組AM中，然后根據(jù)一維數(shù)組AM建立一個(gè)單循環(huán)鏈表，使鏈表中個(gè)元素的次序與AM中各元素的次序相同，要求該函數(shù)的時(shí)間復(fù)雜度為O(m)； 定位查找函數(shù)Locate：在所建立的單循環(huán)鏈表中查找并返回值為key的第1個(gè)元素的結(jié)點(diǎn)指針；若找不到，則返回NULL； 求出該鏈表中值最大和次大的元素值，要求該算法的時(shí)間復(fù)雜度為O(m)，最大和次大的元素值通過(guò)指針變量帶回，函數(shù)不需要返回值；

2、 將鏈表中所有值比key(值key通過(guò)形參傳入)小的結(jié)點(diǎn)作為值為key的結(jié)點(diǎn)前驅(qū)，所有值比key大的結(jié)點(diǎn)作為值為key的結(jié)點(diǎn)后繼，并盡量保持原有結(jié)點(diǎn)之間的順序，要求該算法的時(shí)間復(fù)雜度為O(m); 設(shè)計(jì)一個(gè)菜單，具有上述處理要求和退出系統(tǒng)功能。 本人完成的工作：一、定義結(jié)構(gòu)體：LNode二、編寫以下函數(shù)：（1）建立單循環(huán)鏈表（2）建立定位查找函數(shù)（3）求出鏈表中最大和次大值（4）將鏈表中的值和輸入的Key比較，小的作為key前驅(qū)結(jié)點(diǎn)，大的作為key的后繼結(jié)點(diǎn)三、設(shè)計(jì)具有上述處理要求和退出系統(tǒng)菜單 所采用的數(shù)據(jù)結(jié)構(gòu)：?jiǎn)捂湵頂?shù)據(jù)結(jié)構(gòu)的定義：typedef struct Node/定義結(jié)點(diǎn)的結(jié)構(gòu)體 D

3、ataType data;/數(shù)據(jù)域struct Node *next;/指針域LNode;/結(jié)點(diǎn)的類型 所設(shè)計(jì)的函數(shù)（1） Create(void)LNode *Create(void)/建立單循環(huán)鏈表，鏈表頭結(jié)點(diǎn)head作為返回值int i,j,n,AM;/建立數(shù)組A【M】 LNode *head,*p,*move;head=(LNode*)malloc(sizeof(LNode);/創(chuàng)建空單循環(huán)鏈表head-next=head;move=head;printf(請(qǐng)輸入數(shù)組元素的個(gè)數(shù)：);/輸入數(shù)組scanf(%d,&n);printf(請(qǐng)輸入數(shù)組：);for(i=0;in;i+)/保存數(shù)組

4、元素scanf(%d,&Ai);/勾鏈建表，使鏈表中元素的次序與數(shù)組A各元素次序相同for(j=0;jdata=Aj;p-next=move-next;move-next=p;move=move-next;return head;/返回頭指針開始定義變量：int i ,j,n,AM;LNode *head,*p,*move;建立空單循環(huán)鏈表head建立一維數(shù)組A【M】j=0Jdata=Aj;p-next=move-next;/move-next=p;move=move-next;結(jié)束J+YN（2） Locate(LNode *head,DataType key)LNode *Locate(LN

5、ode *head,DataType key)/建立定位查找函數(shù)LocateLNode *q=head-next;/查找并返回值為key的第1個(gè)元素的結(jié)點(diǎn)指針；若找不到，則返回NULLwhile(q!=head & q-data!=key)q=q-next;if(q-data=key)return q;elseprintf(查找的結(jié)點(diǎn)不存在！n);return NULL;Y開始定義變量：*q=head-next；;結(jié)束q!=head&q-data!=keyq=q-nextq-data=keyreturn qReturn NULlLYNN（3）Search(LNode *head,DataTyp

6、e *a,DataType *b)/求鏈表的最大值和次大值，分別由*a和*b帶回void Search(LNode *head,DataType *a,DataType *b)LNode *p,*Max,*Secmax;p=head-next-next;/*Max和*Secmax指第一個(gè)結(jié)點(diǎn)，*p指向第二個(gè)結(jié)點(diǎn)，Max=head-next;Secmax=head-next-next;while(p!=head)if(Max-data p-data)/*Max指向最大值if(p-data Secmax-data)Secmax=p;else/*Sexmax指向次大值Secmax=Max;Max=p

7、;p=p-next;*a=Max-data;/把最大和次大值分別賦值給*a和*b*b=Secmax-data;開始LNode *p,*Max,*Secmax;p=head-next-next;Max=head-next;Secmax=p;P!=headMax-data p-datap-data Secmax-dataSecmax=p;Secmax=Max;Max=p;*a=Max-data;*b=Secmax-data;結(jié)束NYYNNYp=p-next;（4）Sort(LNode *head)/查找key,把鏈表中比key小的作為前驅(qū)結(jié)點(diǎn)，比key大的作為后繼結(jié)點(diǎn)LNode *Sort(LNo

8、de *head)/*front指向key前部分鏈表，*rear指向key后部分鏈表LNode *k,*p,*front,*rear,*L;DataType key;front=head;p=head-next;printf(請(qǐng)輸入key：);scanf(%d,&key);L=Locate(head,key);/調(diào)用Locate()查找keyk=L;rear=k;while(p!=head)if(front-next!=k)/判斷key前面鏈表是否已經(jīng)比較完畢if(p-data k-data)/將key結(jié)點(diǎn)前驅(qū)比key大的插到key后面front-next=front-next-next;/斷

9、開結(jié)點(diǎn)p-next=rear-next;/插入結(jié)點(diǎn)rear-next=p;rear=rear-next;p=front-next;/*p指回key的前驅(qū)結(jié)點(diǎn)elsep=p-next;/移動(dòng)指針front=front-next;elsep=rear-next;if(p-data data)/將key結(jié)點(diǎn)后繼比key小的插到key前面rear-next=rear-next-next;/斷開結(jié)點(diǎn)p-next=front-next;/插入結(jié)點(diǎn)front-next=p;front=front-next;p=rear-next;/*p指回key的后繼結(jié)點(diǎn)elsep=p-next;/移動(dòng)指針rear=rea

10、r-next;return head;/返回頭指針開始LNode *k,*p,*front,*rear,*L;DataType key;front=head;p=head-next;printf(請(qǐng)輸入key：);scanf(%d,&key);L=Locate(head,key);k=L;rear=k;p!=headfront-next!=kp-data k-datafront-next=front-next-next;p-next=rear-next;rear-next=p;rear=rear-next;p=front-next;p=p-next;front=front-next;p=rea

11、r-next;p-datadatarear-next=rear-next-next;p-next=front-next;front-next=p;front=front-next;p=rear-next;p=p-next;rear=rear-next;return head;結(jié)束YNYNNYNY（5）主函數(shù)：void main()/主函數(shù)LNode *L,*W,*H;DataType a,b;int key,choice;/choice記載操作,key為輸入值printf(n);H=Create();/調(diào)用Create()建立單循環(huán)鏈表/界面美化printf(n);printf(*n);pri

12、ntf(* *n);printf(* 定位查找-1 *n);printf(* 輸出最大和次大值-2 *n);printf(* 輸出比較值key后的結(jié)果-3 *n);printf(* 重新輸入一個(gè)數(shù)組-4 *n);printf(* 退出系統(tǒng)-0 *n);printf(* *n);printf(*n);printf(n);/功能選擇printf(請(qǐng)選擇系統(tǒng)功能:);scanf( %d, &choice);printf(n);while(choice != 0)switch (choice)case 1:/查找數(shù)值key并返回指針printf(請(qǐng)輸入要查找的值：);scanf(%d,&key);L=

13、Locate(H,key);if(L!=NULL)printf(查找成功!n);break;case 2:/求鏈表的最大和次大值Search(H,&a,&b);printf(最大值：%dn,a);printf(次大值：%dn,b);break;case 3:/將key插入鏈表中H=Sort(H);W=H-next;printf(結(jié)果是：);/輸出結(jié)果while(W!=H)printf( %d,W-data);/依次輸出W=W-next;printf(n);break;case 4:main();default:printf(請(qǐng)輸入正確的選項(xiàng)！n);/錯(cuò)誤處理/功能重復(fù)printf(*n);pr

14、intf(* *n);printf(* 定位查找-1 *n);printf(* 輸出最大和次大值-2 *n);printf(* 輸出比較值key后的結(jié)果-3 *n);printf(* 重新輸入一個(gè)數(shù)組-4 *n);printf(* 退出系統(tǒng)-0 *n);printf(* *n);printf(*n);printf(請(qǐng)選擇系統(tǒng)功能:);scanf( %d, &choice);運(yùn)行結(jié)果： 問題與總結(jié)（1）在編寫Create()函數(shù)時(shí)，要根據(jù)一維數(shù)組A【M】建立單循環(huán)鏈表，一開始只是用for語(yǔ)句結(jié)合頭結(jié)點(diǎn)創(chuàng)建單鏈表方法。后來(lái)測(cè)試時(shí)發(fā)現(xiàn)這樣無(wú)法建立有序的單循環(huán)鏈表，要定義一個(gè)移動(dòng)指針*move總是指向鏈表最后一個(gè)結(jié)點(diǎn)。（2）在編寫Search()函數(shù)時(shí)，一開始是找出鏈表中最大值，然后刪去這個(gè)結(jié)點(diǎn)，在剩下的結(jié)點(diǎn)中找出最大值，最后輸出。但后來(lái)測(cè)試整個(gè)程序運(yùn)行時(shí)，出現(xiàn)每次執(zhí)行Search()的功能后，別的函數(shù)就執(zhí)行不了，調(diào)試之后才知道是找最大和次大值破壞了鏈表