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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：?jiǎn)捂湵聿僮鲗I(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)功能。1. 本人完成的工作：一、定義結(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)菜單2. 所采用的數(shù)據(jù)結(jié)構(gòu)：?jiǎn)捂湵頂?shù)據(jù)結(jié)構(gòu)的定義：typedef stru

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

4、,&n);printf( 請(qǐng)輸入數(shù)組： );for(i=0;in;i+)scanf(%d,&Ai);/ 勾鏈建表，使鏈表中元素的次序與數(shù)組 A 各元素次序相同 for(j=0;jdata=Aj;p-next=move-next; move-next=p;move=move-next;/ 返回頭指針 return head;(2) Locate(LNode *head,DataType key)LNode *Locate(LNode *head,DataType key) / 建立定位查找函數(shù) LocateLNode *q=head-n ext;/查找并返回值為key的第1個(gè)元素的結(jié)點(diǎn)指針；若找

5、不到，則返回NULLwhile(q!=head & q-data!=key)q=q-n ext;if(q-data=key)return q;elseprintf(查找的結(jié)點(diǎn)不存在！ n);return NULL;Y(3) Search(LNode *head,DataType *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

6、=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;p=p-next;*a=Max-data;/把最大和次大值分別賦值給*a和*b*b=Secmax-data;LNode *k,*p,*front,*rear,*L;front=head;p=head-next;printf( 請(qǐng)輸入 key：);scanf(%d,&key);L=Locate(head,key);

7、k=L;rear=k; while(p!=head)if(front-next!=k)if(p-data k-data)/4) Sort(LNode *head)/ 查找 key, 把鏈表中比 key 小的作為前驅(qū)結(jié)點(diǎn)，比 key 大的作為后繼結(jié)點(diǎn)LNode *Sort(LNode *head) /*front 指向 key 前部分鏈表， *rear 指向 key 后部分鏈表DataType key;/ 調(diào)用 Locate() 查找 key/ 判斷 key 前面鏈表是否已經(jīng)比較完畢 將 key 結(jié)點(diǎn)前驅(qū)比 key 大的插到 key 后面front-next=front-next-next; p

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

9、p=rear-next;elsep=p-next; rear=rear-next; return head;開始LNode *k,*p,*fro nt,*rear,*L;DataType key; fron t=head; p=head-n ext; printf(” 請(qǐng)輸入 key:); sca nf(%d,&key); L=Locate(head,key);k=L;rear=k;NNfront-n ext=fr ont-n ext- n ext;p-n ext=rear- n ext;rear-n ext=p;rear=rear- n ext;p=front-n ext;rear-n ex

10、t=rear- n ext-n ext; p-n ext=fr ont-n ext;fron t- n ext=p; front=front-n ext;p=rear- n ext;p=p-n ext; fron t=fr ont-nextp=p-n ext; rear=rear- n ext;retur n head;結(jié)束L( 5)主函數(shù)：/ 主函數(shù)void main()LNode *L,*W,*H;DataType a,b;int key,choice;/choice 記載操作 ,key 為輸入值printf(*n);printf(n);H=Create(); / 調(diào)用 Create()

11、建立單循環(huán)鏈表 / 界面美化 printf(n);f*printf(*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(f*n);printf(n);/ 功能選擇printf( 請(qǐng)選擇系統(tǒng)功能 :);scanf( %d, &choice);printf(n);while(choice != 0)switch (choice)case 1:printf( 請(qǐng)輸入要查找的值： ); scanf(%d,

12、&key); L=Locate(H,key);if(L!=NULL)printf( 查找成功 !n);break;case 2:Search(H,&a,&b);printf( 最大值： %dn,a); printf( 次大值： %dn,b);break;case 3:/ 查找數(shù)值 key 并返回指針/ 求鏈表的最大和次大值/ 將 key 插入鏈表中H=Sort(H);printf(*n);W=H-next;printf( 結(jié)果是： ); while(W!=H)printf( %d,W-data);/ 輸出結(jié)果/ 依次輸出W=W-next; printf(n);break;case 4:main

13、();default:printf( 請(qǐng)輸入正確的選項(xiàng)！ ！n);/ 錯(cuò)誤處理/ 功能重復(fù)f*4 *n);退printf(*printf(*printf(*定位查找1 *n);printf(*輸出最大和次大值2 *n);printf(*輸出比較值key后的結(jié)果3 *n);printf(*重新輸入一個(gè)數(shù)組*n);出系統(tǒng)0 *n);printf(*n);printf(*n)；printf(請(qǐng)選擇系統(tǒng)功能:);sea nf(” d, & choice);4運(yùn)行結(jié)果:且目/， 券養(yǎng)i5103 (566 321 211 2133 65654 415大號(hào)五直二找大英先皇1H.旳結(jié)爭(zhēng)-rJMMMMMMNMX

14、MXMKMM MM MM KMKMXMrfMMMM1KKMNMNMPMr KM KM NM MFKH MMMM M MXM X霍二找大燹猊付岀幕出rl* H-stle退右累蜒一 -_0 *MM鯉璨聲虧茶二二二二二二二二二二二二二二二虧:請(qǐng)選擇系統(tǒng)功能詡nna finy )(u fcn cnnlziniim找大費(fèi)繞 咅出新曲 定Bs迫杲415 f.bf-h W1335.問(wèn)題與總結(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)試之后才知道是找最大和次 大值破壞了鏈表的完整性， 導(dǎo)致其他函數(shù)執(zhí)行