數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)3

1、WORD格式"數(shù)據(jù)構(gòu)造與算法"實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)序號(hào)： 3實(shí)驗(yàn)工程名稱：鏈?zhǔn)奖淼牟僮鲗W(xué)號(hào) 1507112104姓名陳忠表專(zhuān)業(yè)、班15 商智實(shí)驗(yàn)地點(diǎn)指導(dǎo)教師林開(kāi)標(biāo)實(shí)驗(yàn)時(shí)間16.11.09一、實(shí)驗(yàn)?zāi)康募耙?. 通過(guò)實(shí)驗(yàn)理解單鏈表的邏輯構(gòu)造；2. 通過(guò)實(shí)驗(yàn)掌握單鏈表的根本操作和具體的函數(shù)實(shí)現(xiàn)。二、實(shí)驗(yàn)設(shè)備環(huán)境及要求微型計(jì)算機(jī)；windows 操作系統(tǒng)；Microsoft Visual Studio 6.0 集成開(kāi)發(fā)環(huán)境。三、實(shí)驗(yàn)內(nèi)容與步驟鏈?zhǔn)奖肀硎竞蛯?shí)現(xiàn)線性表的如下：#include"stdio.h"#include"stdlib.h"專(zhuān)業(yè)資料

2、整理WORD格式typedef struct node/定義結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式int data;/結(jié)點(diǎn)的數(shù)據(jù)域?yàn)檎蛃truct node *next;/結(jié)點(diǎn)的指針域ListNode;typedef ListNode * LinkList;/自定義 LinkList單鏈表類(lèi)型LinkList CreatListR1();/函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表ListNode *LocateNode(LinkList head, int key);/函數(shù)，按值查找結(jié)點(diǎn)voidDeleteList(LinkListhead,intkey);/函數(shù)，刪除指定值的結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式

3、void printlist(LinkList head);voidDeleteAll(LinkListhead);/函數(shù)，打印鏈表中的所有值函數(shù)，刪除所有結(jié)點(diǎn)，釋放內(nèi)存專(zhuān)業(yè)資料整理WORD格式/= 主函數(shù) =void main()int num;char ch;LinkList head;專(zhuān)業(yè)資料整理WORD格式head=CreatListR1(); printlist(head);/用尾插入法建立單鏈表，返回頭指針遍歷鏈表輸出其值專(zhuān)業(yè)資料整理WORD格式printf(" Delete node (y/n):"); /輸入 "y" 或 "n&

4、quot; 去選擇是否刪除結(jié)點(diǎn)scanf("%c",&ch);if(ch=y ) | ch=Y )printf("Please input Delete_data:");scanf("%d",num);/輸入要?jiǎng)h除的字符串DeleteList(head,num);printlist(head);DeleteAll(head);/刪除所有結(jié)點(diǎn)，釋放內(nèi)存/= 用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=LinkList CreatListR1(void)return head;/返回頭指針/= 按值查找結(jié)點(diǎn)，找到那么返回該結(jié)點(diǎn)的位置，否那么返

5、回 NULL= ListNode *LocateNode(LinkList head, int key)return p;/假設(shè)p=NULL那么查找失敗，否那么p 指向找到的值為key 的結(jié)點(diǎn)/= 刪除帶頭結(jié)點(diǎn)的單鏈表中的指定結(jié)點(diǎn)=void DeleteList(LinkList head,int key)/ 按 key 值查找結(jié)點(diǎn)的/ 假設(shè)沒(méi)有找到結(jié)點(diǎn)，退出/ 假設(shè)找到，那么從單鏈表中刪除該結(jié)點(diǎn)，并釋放結(jié)點(diǎn)/= 打印鏈表 , 輸出所有結(jié)點(diǎn)的值=void printlist(LinkList head)/= 刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head)專(zhuān)業(yè)

6、資料整理WORD格式1、 實(shí)現(xiàn)并調(diào)試單鏈表的的相關(guān)算法；專(zhuān)業(yè)資料整理WORD格式2、改寫(xiě)以上程序，實(shí)現(xiàn)功能如下：(1 編寫(xiě)一個(gè)刪除鏈表中值為 x 的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的算法，假設(shè)有多個(gè)值為 x 的結(jié)點(diǎn)，那么刪除第一個(gè) x 的直接前趨結(jié)點(diǎn)。(2 改寫(xiě) CreatListR1函數(shù)，使得鏈表創(chuàng)立時(shí)為非遞減有序的單鏈表。(3 在算法 (2 生成的非遞減有序的單鏈表中，編寫(xiě)一個(gè)算法，刪除單鏈表中值一樣的多余結(jié)點(diǎn)。(4 寫(xiě)一個(gè)對(duì)單循環(huán)鏈表進(jìn)展逆序輸出打印每個(gè)結(jié)點(diǎn)的值的算法。四、實(shí)驗(yàn)結(jié)果與數(shù)據(jù)處理一 .實(shí)驗(yàn)結(jié)果如圖1 所示：圖 1二 . 1實(shí)驗(yàn)結(jié)果如圖2 所示：專(zhuān)業(yè)資料整理WORD格式圖 22實(shí)驗(yàn)結(jié)果如圖3

7、 所示：圖 33實(shí)驗(yàn)結(jié)果如圖4 所示：專(zhuān)業(yè)資料整理WORD格式圖 4(4) 實(shí)驗(yàn)結(jié)果如圖5 所示：圖 5五、分析與討論感覺(jué)實(shí)驗(yàn)3 比之前的實(shí)驗(yàn)一、二難度更大，只能瀏覽同學(xué)的，有疑問(wèn)便問(wèn)同學(xué)，這樣勉強(qiáng)理解。專(zhuān)業(yè)資料整理WORD格式六、教師評(píng)語(yǔ)成績(jī)簽名：日期：附源程序清單：一 .#include"stdio.h"#include"stdlib.h"typedef struct node/ 定義結(jié)點(diǎn)int data;/ 結(jié)點(diǎn)的數(shù)據(jù)域?yàn)檎蛃truct node *next;/ 結(jié)點(diǎn)的指針域ListNode;typedef ListNode * LinkList

8、;/ 自定義 LinkList 單鏈表類(lèi)型LinkList CreatListR1();/ 函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表void printlist(LinkList head);/函數(shù)，打印鏈表中的所有值ListNode *LocateNode(LinkList head, int key);/ 函數(shù)，按值查找結(jié)點(diǎn)void DeleteList(LinkList head,int key);/ 函數(shù)，刪除指定值的結(jié)點(diǎn)void DeleteAll(LinkList head);void main()int num;char ch;LinkList head;head=CreatList

9、R1();printf("List:n");printlist(head);printf(" Delete node (y/n):");/輸入 "y" 或 "n" 去選擇是否刪除結(jié)點(diǎn)getchar();scanf("%c",&ch);if(ch='y'|ch='Y')printf("Please input Delete_data:");scanf("%d",&num);/輸入要?jiǎng)h除的數(shù)DeleteList(

10、head,num);/刪除printlist(head);/打印DeleteAll(head);/ 刪除所有結(jié)點(diǎn)，釋放內(nèi)存專(zhuān)業(yè)資料整理WORD格式專(zhuān)業(yè)資料整理WORD格式/= 用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=LinkList CreatListR1(void)int n,i,count;LinkList head=(LinkList)malloc(sizeof(ListNode);ListNode *s, *r;/s 用來(lái)指向新生成的節(jié)點(diǎn)。r 始終指向 L 的終端節(jié)點(diǎn)。r=head;r->next=NULL;printf(" 請(qǐng)輸入鏈表節(jié)點(diǎn)數(shù)：");scanf(&qu

11、ot;%d",&n);printf(" 輸入節(jié)點(diǎn)值：");for ( i = 0; i < n; i+) s = (LinkList)malloc(sizeof(ListNode);/s 指向新申請(qǐng)的節(jié)點(diǎn) scanf("%d",&count);s->data = count; / 用新節(jié)點(diǎn)的數(shù)據(jù)域來(lái)承受ir->next = s; / 用 r 來(lái)接納新節(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式r = s; /r指向終端節(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式r->next = NULL;專(zhuān)業(yè)資料整理WORD格式return head

12、;/返回頭指針return head;/返回頭指針專(zhuān)業(yè)資料整理WORD格式void printlist(LinkList head)專(zhuān)業(yè)資料整理WORD格式ListNode *p=head->next;while(p)printf("%d, ",p->data);/ 從開(kāi)場(chǎng)結(jié)點(diǎn)打印專(zhuān)業(yè)資料整理WORD格式p=p->next;printf("n");/= 按值查找結(jié)點(diǎn)，找到那么返回該結(jié)點(diǎn)的位置，否那么返回NULL=ListNode *LocateNode(LinkList head, int key)專(zhuān)業(yè)資料整理WORD格式ListNod

13、e *p=head->next; / 從開(kāi)場(chǎng)結(jié)點(diǎn)比較while(p && p->data!=key)/直到 p 為 NULLp=p->next;/掃描下一個(gè)結(jié)點(diǎn)return p;/ 假設(shè) p=NULL那么查找失敗，否那么或 p->data 為 key 止p 指向找到的值為key 的結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式/= 刪除帶頭結(jié)點(diǎn)的單鏈表中的指定結(jié)點(diǎn)=void DeleteList(LinkList head,int key)ListNode *p,*r,*q=head;p=LocateNode(head,key);/按 key 值查找結(jié)點(diǎn)的if(p=NUL

14、L ) / 假設(shè)沒(méi)有找到結(jié)點(diǎn)，退出專(zhuān)業(yè)資料整理WORD格式printf("position error");exit(0);while(q->next!=p)/p 為要?jiǎng)h除的結(jié)點(diǎn)，q 為 p 的前結(jié)點(diǎn)q=q->next;r=q->next;q->next=r->next;free(r);/ 釋放結(jié)點(diǎn)/= 刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head)ListNode *p=head,*r;while(p->next)r=p->next;free(p);p=r;free(p);二 1專(zhuān)業(yè)資料整理WO

15、RD格式#include"stdio.h"#include"stdlib.h"typedef struct node/ 定義結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式int data;/ 結(jié)點(diǎn)的數(shù)據(jù)域?yàn)檎蛃truct node *next;/ 結(jié)點(diǎn)的指針域ListNode;typedef ListNode * LinkList;/ 自定義 LinkList 單鏈表類(lèi)型LinkList CreatListR1();/ 函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表void printlist(LinkList head);ListNode *LocateNode(LinkLis

16、t head, int key);/ 函數(shù)，按值查找前結(jié)點(diǎn)void DeleteList(LinkList head,int key);/函數(shù)，刪除指定值的結(jié)點(diǎn)void DeleteAll(LinkList head);void main()int num;專(zhuān)業(yè)資料整理WORD格式char ch;LinkList head;head=CreatListR1();printf("List:n");printlist(head);專(zhuān)業(yè)資料整理WORD格式printf(" 是否刪除鏈表中值為 x 的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn) (y/n):"); / 輸入 "

17、y" 或 "n" 去選擇是否刪除結(jié)點(diǎn)getchar();scanf("%c",&ch);if(ch='y'|ch='Y')printf("Please input Delete_data:");scanf("%d",&num);/輸入要?jiǎng)h除的字符串DeleteList(head,num);printlist(head);DeleteAll(head);/ 刪除所有結(jié)點(diǎn)，釋放內(nèi)存/= 用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=LinkList CreatListR1(v

18、oid)int n,i,count;LinkList head=(LinkList)malloc(sizeof(ListNode);ListNode *s, *r;/s 用來(lái)指向新生成的節(jié)點(diǎn)。r 始終指向 L 的終端節(jié)點(diǎn)。r=head;r->next=NULL;printf(" 請(qǐng)輸入鏈表節(jié)點(diǎn)數(shù)：");scanf("%d",&n);printf(" 輸入節(jié)點(diǎn)值：");for ( i = 0; i < n; i+) s = (LinkList)malloc(sizeof(ListNode);/s 指向新申請(qǐng)的節(jié)點(diǎn)sc

19、anf("%d",&count);s->data = count; / 用新節(jié)點(diǎn)的數(shù)據(jù)域來(lái)承受ir->next = s; / 用 r 來(lái)接納新節(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式r = s; /r指向終端節(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式r->next = NULL;專(zhuān)業(yè)資料整理WORD格式return head;/返回頭指針return head;/返回頭指針專(zhuān)業(yè)資料整理WORD格式void printlist(LinkList head)專(zhuān)業(yè)資料整理WORD格式ListNode *p=head->next;while(p)printf("%d

20、, ",p->data);p=p->next;/ 從開(kāi)場(chǎng)結(jié)點(diǎn)打印專(zhuān)業(yè)資料整理WORD格式printf("n");/=/按值查找結(jié)點(diǎn)，找到返回該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)位置，否那么返回NULL=ListNode *LocateNode(LinkList head, int key)ListNode *p=head->next;專(zhuān)業(yè)資料整理WORD格式ListNode *x=head->next;/ while(p && p->data!=key)/從開(kāi)場(chǎng)結(jié)點(diǎn)比較直到 p 為 NULL或p->data為 key 止專(zhuān)業(yè)資料

21、整理WORD格式專(zhuān)業(yè)資料整理WORD格式x=p; / x 為 P 的前一個(gè)節(jié)點(diǎn)；p=p->next;/ 掃描下一個(gè)結(jié)點(diǎn)if( p->data!=key)x=NULL;專(zhuān)業(yè)資料整理WORD格式return x;/ 假設(shè)p=NULL那么查找失敗，否那么p 指向找到的值為key 的結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式/= 刪除帶頭結(jié)點(diǎn)的單鏈表中的指定結(jié)點(diǎn)=void DeleteList(LinkList head,int key)ListNode *p,*r,*q=head;p=LocateNode(head,key);/按 key 值查找結(jié)點(diǎn)的if(p=NULL ) / 假設(shè)沒(méi)有找到結(jié)點(diǎn)，退出

22、printf("position error");exit(0);while(q->next!=p)/p 為要?jiǎng)h除的結(jié)點(diǎn)，q 為 p 的前結(jié)點(diǎn)q=q->next;r=q->next;q->next=r->next;free(r);/ 釋放結(jié)點(diǎn)/= 刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head)ListNode *p=head,*r;while(p->next)r=p->next;free(p);p=r;專(zhuān)業(yè)資料整理WORD格式free(p); 2專(zhuān)業(yè)資料整理WORD格式#include"

23、stdio.h"#include"stdlib.h"typedef struct node/ 定義結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式int data;struct node *next;/ 結(jié)點(diǎn)的數(shù)據(jù)域?yàn)檎? 結(jié)點(diǎn)的指針域?qū)I(yè)資料整理WORD格式ListNode;專(zhuān)業(yè)資料整理WORD格式typedef ListNode * LinkList; LinkList CreatListR1();/ 自定義 LinkList 單鏈表類(lèi)型/ 函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表專(zhuān)業(yè)資料整理WORD格式void printlist(LinkList head);專(zhuān)業(yè)資料整理WOR

24、D格式void DeleteAll(LinkList head);void main()int num;char ch;LinkList head;head=CreatListR1();printf("List:n");printlist(head);DeleteAll(head);/ 刪除所有結(jié)點(diǎn)，釋放內(nèi)存/= 用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=LinkList CreatListR1(void)int n,i,count,change,j;LinkList head=(LinkList)malloc(sizeof(ListNode);ListNode *s, *r,*q;

25、/s用來(lái)指向新生成的節(jié)點(diǎn)。r 始終指向L 的終端節(jié)點(diǎn)。r=head;q=head;r->next=NULL;printf(" 請(qǐng)輸入鏈表節(jié)點(diǎn)數(shù)：");scanf("%d",&n);printf(" 輸入節(jié)點(diǎn)值：");for ( i = 0; i < n; i+) s = (LinkList)malloc(sizeof(ListNode);/s 指向新申請(qǐng)的節(jié)點(diǎn)scanf("%d",&count);s->data = count; / 用新節(jié)點(diǎn)的數(shù)據(jù)域來(lái)承受i專(zhuān)業(yè)資料整理WORD格式

26、r->next = s; / 用 r 來(lái)接納新節(jié)點(diǎn)r = s; /r 指向終端節(jié)點(diǎn)r->next = NULL;/ 排序；for(i=n;i>0;i-)q=head->next;for(j=0;j<n-1;j+)if(q->data)>(q->next->data)change=q->data;q->data=q->next->data;q->next->data=change;q=q->next;elseq=q->next;專(zhuān)業(yè)資料整理WORD格式return head;/返回頭指針retu

27、rn head;/返回頭指針專(zhuān)業(yè)資料整理WORD格式void printlist(LinkList head)專(zhuān)業(yè)資料整理WORD格式ListNode *p=head->next;while(p)printf("%d, ",p->data);p=p->next;/ 從開(kāi)場(chǎng)結(jié)點(diǎn)打印專(zhuān)業(yè)資料整理WORD格式printf("n");專(zhuān)業(yè)資料整理WORD格式/= 刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head)ListNode *p=head,*r;while(p->next)r=p->next;f

28、ree(p);p=r;專(zhuān)業(yè)資料整理WORD格式free(p); 3專(zhuān)業(yè)資料整理WORD格式#include"stdio.h"#include"stdlib.h"typedef struct node/ 定義結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式int data;struct node *next;/ 結(jié)點(diǎn)的數(shù)據(jù)域?yàn)檎? 結(jié)點(diǎn)的指針域?qū)I(yè)資料整理WORD格式ListNode;專(zhuān)業(yè)資料整理WORD格式typedef ListNode * LinkList; LinkList CreatListR1();/ 自定義 LinkList 單鏈表類(lèi)型/ 函數(shù)，用尾插入法建立

29、帶頭結(jié)點(diǎn)的單鏈表專(zhuān)業(yè)資料整理WORD格式void printlist(LinkList head);專(zhuān)業(yè)資料整理WORD格式void DeleteSameNode(LinkList head);void DeleteAll(LinkList head);void main()int num;char ch;LinkList head;head=CreatListR1();printf("List:n");printlist(head);DeleteSameNode(head);printlist(head);DeleteAll(head);/ 刪除所有結(jié)點(diǎn)，釋放內(nèi)存/= 用

30、尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=LinkList CreatListR1(void)int n,i,count,change,j;LinkList head=(LinkList)malloc(sizeof(ListNode);ListNode *s,*r,*q;/s用來(lái)指向新生成的節(jié)點(diǎn)。r 始終指向L 的終端節(jié)點(diǎn)。r=head;q=head;r->next=NULL;printf(" 請(qǐng)輸入鏈表節(jié)點(diǎn)數(shù)：");scanf("%d",&n);printf(" 輸入節(jié)點(diǎn)值：");for ( i = 0; i < n; i+

31、) s = (LinkList)malloc(sizeof(ListNode);/s 指向新申請(qǐng)的節(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式scanf("%d",&count);s->data = count; / 用新節(jié)點(diǎn)的數(shù)據(jù)域來(lái)承受ir->next = s; / 用 r 來(lái)接納新節(jié)點(diǎn)r = s; /r 指向終端節(jié)點(diǎn)r->next = NULL;/ 排序；for(i=n;i>0;i-)q=head->next;for(j=0;j<n-1;j+)if(q->data)>(q->next->data)change=q-&

32、gt;data;q->data=q->next->data;q->next->data=change;q=q->next;elseq=q->next;專(zhuān)業(yè)資料整理WORD格式return head;/返回頭指針return head;/返回頭指針專(zhuān)業(yè)資料整理WORD格式void printlist(LinkList head)專(zhuān)業(yè)資料整理WORD格式ListNode *p=head->next;while(p)printf("%d, ",p->data);p=p->next;/ 從開(kāi)場(chǎng)結(jié)點(diǎn)打印專(zhuān)業(yè)資料整理WORD格

33、式printf("n");專(zhuān)業(yè)資料整理WORD格式/= 刪除多余節(jié)點(diǎn)=void DeleteSameNode(LinkList head)int n=2;ListNode *p,*q,*t,*s;專(zhuān)業(yè)資料整理WORD格式p = head;p = p->next;/ p 第一個(gè)while(p->next)if(p->data = p->next->data)if(p->next->next=NULL)p->next=NULL;elsep->next=p->next->next;p=p->next;else

34、p=p->next;/= 刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head)ListNode *p=head,*r;while(p->next)r=p->next;free(p);p=r;free(p);專(zhuān)業(yè)資料整理WORD格式(4)#include"stdio.h"#include"stdlib.h"typedef struct node/ 定義結(jié)點(diǎn)專(zhuān)業(yè)資料整理WORD格式int data;struct node *next;ListNode;/ 結(jié)點(diǎn)的數(shù)據(jù)域?yàn)檎? 結(jié)點(diǎn)的指針域?qū)I(yè)資料整理WORD格

35、式typedef ListNode * LinkList; LinkList CreatListR1();/ 自定義 LinkList 單鏈表類(lèi)型/ 函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表專(zhuān)業(yè)資料整理WORD格式void printlist(LinkList head);專(zhuān)業(yè)資料整理WORD格式void printlist_inverseorder(LinkList head);/逆序void DeleteAll(LinkList head);void main()int num;char ch;LinkList head;head=CreatListR1();printf("List:n");printlist(head);printlist_inverseorder(