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

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

2、ata; /結(jié)點(diǎn)的數(shù)據(jù)域?yàn)檎蛃truct node *next; /結(jié)點(diǎn)的指針域 ListNode;typedef ListNode * LinkList; / 自定義LinkList單鏈表類型LinkList CreatListR1(); /函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表ListNode *LocateNode(LinkList head, int key); /函數(shù)，按值查找結(jié)點(diǎn)void DeleteList(LinkList head,int key); /函數(shù)，刪除指定值的結(jié)點(diǎn)void printlist(LinkList head); /函數(shù)，打印鏈表中的所有值void De

3、leteAll(LinkList head); /函數(shù)，刪除所有結(jié)點(diǎn)，釋放內(nèi)存/=主函數(shù)=void main() int num; char ch; LinkList head; head=CreatListR1(); /用尾插入法建立單鏈表，返回頭指針 printlist(head); /遍歷鏈表輸出其值 printf(" Delete node (y/n):"); /輸入"y"或"n"去選擇是否刪除結(jié)點(diǎn) scanf("%c",&ch); if(ch=y) | ch=Y) printf("Ple

4、ase 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)的位置，否則返回NULL=ListNode *LocateNode(LinkList head, int key) return p; /若p=NULL則查找失敗

5、，否則p指向找到的值為key的結(jié)點(diǎn)/=刪除帶頭結(jié)點(diǎn)的單鏈表中的指定結(jié)點(diǎn)=void DeleteList(LinkList head,int key) /按key值查找結(jié)點(diǎn)的 /若沒有找到結(jié)點(diǎn)，退出/若找到，則從單鏈表中刪除該結(jié)點(diǎn)，并釋放結(jié)點(diǎn)/=打印鏈表,輸出所有結(jié)點(diǎn)的值=void printlist(LinkList head) /=刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head) 1、 實(shí)現(xiàn)并調(diào)試單鏈表的的相關(guān)算法；2、改寫以上程序，實(shí)現(xiàn)功能如下：(1）編寫一個(gè)刪除鏈表中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的算法，若有多個(gè)值為x的結(jié)點(diǎn)，則刪除第一個(gè)x的直接前趨結(jié)點(diǎn)。(

6、2）改寫CreatListR1函數(shù)，使得鏈表創(chuàng)建時(shí)為非遞減有序的單鏈表。(3）在算法(2）生成的非遞減有序的單鏈表中，編寫一個(gè)算法，刪除單鏈表中值相同的多余結(jié)點(diǎn)。(4）寫一個(gè)對單循環(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所示：圖2（2）實(shí)驗(yàn)結(jié)果如圖3所示：圖3（3）實(shí)驗(yàn)結(jié)果如圖4所示：圖4(4) 實(shí)驗(yàn)結(jié)果如圖5所示：圖5五、分析與討論感覺實(shí)驗(yàn)3比之前的實(shí)驗(yàn)一、二難度更大，只能瀏覽同學(xué)的，有疑問便問同學(xué)，這樣勉強(qiáng)理解。六、教師評語簽名：日期：成績附源程序清單：一. #include"stdio.h"

7、;#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; / 自定義LinkList單鏈表類型LinkList CreatListR1(); /函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表void printlist(LinkList head);/函數(shù)，打印鏈表中的所有值ListNode *LocateNode(LinkList head, int key); /函數(shù)，按值查找結(jié)點(diǎn)

8、void DeleteList(LinkList head,int key); /函數(shù)，刪除指定值的結(jié)點(diǎn) void DeleteAll(LinkList head); void main() int num; char ch; LinkList head; head=CreatListR1(); printf("List:n"); printlist(head); printf(" Delete node (y/n):"); /輸入"y"或"n"去選擇是否刪除結(jié)點(diǎn) getchar(); scanf("%c

9、",&ch); if(ch='y'|ch='Y') printf("Please input Delete_data:"); scanf("%d",&num); /輸入要?jiǎng)h除的數(shù) DeleteList(head,num); /刪除 printlist(head);/打印 DeleteAll(head); /刪除所有結(jié)點(diǎn)，釋放內(nèi)存/=用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=LinkList CreatListR1(void) int n,i,count; LinkList head=(LinkList)ma

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

11、 count; /用新節(jié)點(diǎn)的數(shù)據(jù)域來接受i r->next = s; /用r來接納新節(jié)點(diǎn) r = s; /r指向終端節(jié)點(diǎn) r->next = NULL; return head; /返回頭指針 return head; /返回頭指針void printlist(LinkList head) ListNode *p=head->next; /從開始結(jié)點(diǎn)打印 while(p)printf("%d, ",p->data);p=p->next; printf("n");/=按值查找結(jié)點(diǎn)，找到則返回該結(jié)點(diǎn)的位置，否則返回NULL=Li

12、stNode *LocateNode(LinkList head, int key) ListNode *p=head->next; /從開始結(jié)點(diǎn)比較 while(p && p->data!=key) /直到p為NULL或p->data為key止p=p->next; /掃描下一個(gè)結(jié)點(diǎn) return p; /若p=NULL則查找失敗，否則p指向找到的值為key的結(jié)點(diǎn)/=刪除帶頭結(jié)點(diǎn)的單 鏈表中的指定結(jié)點(diǎn)=void DeleteList(LinkList head,int key) ListNode *p,*r,*q=head; p=LocateNode(h

13、ead,key); /按key值查找結(jié)點(diǎn)的 if(p=NULL ) /若沒有找到結(jié)點(diǎn)，退出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;

14、free(p);二（1）#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; / 自定義LinkList單鏈表類型LinkList CreatListR1(); /函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表void printlist(LinkList head);ListNode *LocateNode(LinkList h

15、ead, 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=CreatListR1(); printf("List:n"); printlist(head); printf(" 是否刪除鏈表中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)(y/n):"); /輸入"y"或"n"去

16、選擇是否刪除結(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(void) int n,i,cou

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

18、quot;,&count);s->data = count; /用新節(jié)點(diǎn)的數(shù)據(jù)域來接受i r->next = s; /用r來接納新節(jié)點(diǎn) r = s; /r指向終端節(jié)點(diǎn) r->next = NULL; return head; /返回頭指針 return head; /返回頭指針void printlist(LinkList head) ListNode *p=head->next; /從開始結(jié)點(diǎn)打印 while(p)printf("%d, ",p->data);p=p->next; printf("n");/=

19、/按值查找結(jié)點(diǎn)，找到返回該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)位置，否則返回NULL=ListNode *LocateNode(LinkList head, int key) ListNode *p=head->next; ListNode *x=head->next;/從開始結(jié)點(diǎn)比較 while(p && p->data!=key)/直到p為NULL或p->data為key止x=p; / x為P的前一個(gè)節(jié)點(diǎn)；p=p->next; /掃描下一個(gè)結(jié)點(diǎn)if( p->data!=key)x=NULL; return x; /若p=NULL則查找失敗，否則p指向找到的

20、值為key的結(jié)點(diǎn)/=刪除帶頭結(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 ) /若沒有找到結(jié)點(diǎn)，退出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)/=刪除

21、所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p->next)r=p->next;free(p);p=r; free(p);（2）#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; / 自定義LinkList單鏈表類型L

22、inkList CreatListR1(); /函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表void printlist(LinkList head);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

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

24、點(diǎn) scanf("%d",&count);s->data = count; /用新節(jié)點(diǎn)的數(shù)據(jù)域來接受i r->next = s; /用r來接納新節(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=ch

25、ange;q=q->next;elseq=q->next; return head; /返回頭指針 return head; /返回頭指針void printlist(LinkList head) ListNode *p=head->next; /從開始結(jié)點(diǎn)打印 while(p)printf("%d, ",p->data);p=p->next; printf("n");/=刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p->ne

26、xt)r=p->next;free(p);p=r; free(p);（3）#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; / 自定義LinkList單鏈表類型LinkList CreatListR1(); /函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表void printlist(LinkList head); vo

27、id 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)存/=用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表=LinkList CreatListR1(void) int n,i,count

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

29、 scanf("%d",&count);s->data = count; /用新節(jié)點(diǎn)的數(shù)據(jù)域來接受i r->next = s; /用r來接納新節(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=ch

30、ange;q=q->next;elseq=q->next; return head; /返回頭指針 return head; /返回頭指針void printlist(LinkList head) ListNode *p=head->next; /從開始結(jié)點(diǎn)打印 while(p)printf("%d, ",p->data);p=p->next; printf("n");/=刪除多余節(jié)點(diǎn)= void DeleteSameNode(LinkList head) int n=2; ListNode *p,*q,*t,*s; p =

31、 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; elsep=p->next; /=刪除所有結(jié)點(diǎn)，釋放空間=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p->next)r=p->next;free(p);p=

32、r; free(p);(4)#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; / 自定義LinkList單鏈表類型LinkList CreatListR1(); /函數(shù)，用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表void printlist(LinkList head);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(head); De