數(shù)據(jù)結構課程設計單鏈表操作

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

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

3、ct Node/定義結點的結構體DataType data;/數(shù)據(jù)域struct Node *next;/指針域LNode;/ 結點的類型3.所設計的函數(shù)( 1) Create(void)LNode *Create(void) / 建立單循環(huá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(" 請輸入數(shù)組元素的個數(shù)： &

4、quot;); scanf("%d",&n);printf(" 請輸入數(shù)組： ");for(i=0;i<n;i+)scanf("%d",&Ai);/ 勾鏈建表，使鏈表中元素的次序與數(shù)組 A 各元素次序相同 for(j=0;j<n;j+)/ 根據(jù)一維數(shù)組 AM 建立一個單循環(huán)鏈表p=(LNode*)malloc(sizeof(LNode); p->data=Aj;p->next=move->next; move->next=p;move=move->next;/ 返回頭指針 re

5、turn head;(2) Locate(LNode *head,DataType key)LNode *Locate(LNode *head,DataType key) / 建立定位查找函數(shù) LocateLNode *q=head->n ext;/查找并返回值為key的第1個元素的結點指針；若找不到，則返回NULLwhile(q!=head && q->data!=key)q=q->n ext;if(q->data=key)return q;elseprintf("查找的結點不存在！ n");return NULL;Y(3) Sea

6、rch(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指第一個結點，*p 指向第二個結點,Max=head->next;Secmax=head->next->next;while(p!=head)if(Max->data > p->data)/*Max 指向最大值if(p-

7、>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(" 請輸入 key：");scanf("%d",&key);L=Locate(head,key);k=L;rear=k; while(p!=head

8、)if(front->next!=k)if(p->data > k->data)/4) Sort(LNode *head)/ 查找 key, 把鏈表中比 key 小的作為前驅結點，比 key 大的作為后繼結點LNode *Sort(LNode *head) /*front 指向 key 前部分鏈表， *rear 指向 key 后部分鏈表DataType key;/ 調用 Locate() 查找 key/ 判斷 key 前面鏈表是否已經比較完畢 將 key 結點前驅比 key 大的插到 key 后面front->next=front->next->nex

9、t; p->next=rear->next; rear->next=p; rear=rear->next; p=front->next;elsep=p->next;front=front->next;/ 斷開結點/ 插入結點/*p 指回 key 的前驅結點/ 移動指針/ 斷開結點/ 插入結點/*p 指回 key 的后繼結點/ 移動指針/ 返回頭指針elsep=rear->next;if(p->data < k->data)/將 key 結點后繼比 key 小的插到 key 前面rear->next=rear->nex

10、t->next; p->next=front->next; front->next=p; front=front->next; 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(” 請輸入 key:"); sca nf("%d",&key); L=Locate(head,key);k

11、=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 ext=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

12、->nextp=p->n ext; rear=rear- >n ext;retur n head;結束L( 5)主函數(shù)：/ 主函數(shù)void main()LNode *L,*W,*H;DataType a,b;int key,choice;/choice 記載操作 ,key 為輸入值printf("*n");printf("n");H=Create(); / 調用 Create() 建立單循環(huán)鏈表 / 界面美化 printf("n");f*printf("*n");printf("*定位查

13、找1*n");printf("*輸出最大和次大值2 *n");printf("*輸出比較值key后的結果3 *n");printf("*重新輸入一個數(shù)組4 *n");printf("*退出系統(tǒng)0*n");printf("*n");printf("f*n");printf("n");/ 功能選擇printf(" 請選擇系統(tǒng)功能 :");scanf(" %d", &choice);printf(&quo

14、t;n");while(choice != 0)switch (choice)case 1:printf(" 請輸入要查找的值： "); scanf("%d",&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 并返

15、回指針/ 求鏈表的最大和次大值/ 將 key 插入鏈表中H=Sort(H);printf("*n");W=H->next;printf(" 結果是： "); while(W!=H)printf(" %d",W->data);/ 輸出結果/ 依次輸出W=W->next; printf("n");break;case 4:main();default:printf(" 請輸入正確的選項！ ！n");/ 錯誤處理/ 功能重復f*4 *n");退printf("*p

16、rintf("*printf("*定位查找1 *n");printf("*輸出最大和次大值2 *n");printf("*輸出比較值key后的結果3 *n");printf("*重新輸入一個數(shù)組*n");出系統(tǒng)0 *n");printf("*n");printf("*n")；printf("請選擇系統(tǒng)功能:");sea nf(” d", & choice);4運行結果:且目/，£ 券養(yǎng)i5103 (>5

17、66 321 211 2133 65654 415大號五直二找大英先皇1H.旳結爭-rJMMMMMMNMXMXMKMM MM MM KMKMXMrfMMMM1«KKMNMN<MP<>>M>r KM KM NM MF<KH MMMM M MXM X霍二找大燹猊付岀幕出rl®* H-stle退右累蜒一 '-_0 *MM鯉璨聲虧茶二二二二二二二二二二二二二二二虧:請選擇系統(tǒng)功能詡nna finy )(«u fcn cnnlzini'im找大費繞 咅出新曲 定Bs迫杲415 f.bf-h W1335.問題與總結(1)在編寫Create()函數(shù)時，要根據(jù)一維數(shù)組 A【M建立單循環(huán)鏈表，一開始 只是用 for 語句結合頭結點創(chuàng)建單鏈表方法。 后來測試時發(fā)現(xiàn)這樣無法建立有序 的單循環(huán)鏈表，要定義一個移動指針 *move 總是指向鏈表最后一個結點。( 2)在編寫 Search() 函數(shù)時， 一開始是找出鏈表中最大值， 然后刪去這個結點， 在剩下的結點中找出最大值，最后輸出。 但后來測試整個程序運行時， 出現(xiàn)每次 執(zhí)行 Search()