《數(shù)據(jù)結(jié)構(gòu)》實驗報告二及其答案

1、PAGE PAGE 8數(shù)據(jù)結(jié)構(gòu)實驗報告二一、上機實驗的問題和要求：單鏈表的查找、插入與刪除。設(shè)計算法，實現(xiàn)線性結(jié)構(gòu)上的單鏈表的產(chǎn)生以及元素的查找、插入與刪除。具體實現(xiàn)要求：從鍵盤輸入20個整數(shù)，產(chǎn)生帶表頭的單鏈表，并輸入結(jié)點值。從鍵盤輸入1個整數(shù)，在單鏈表中查找該結(jié)點。若找到，則顯示“找到了”；否則，則顯示“找不到”。從鍵盤輸入2個整數(shù)，一個表示欲插入的位置i，另一個表示欲插入的數(shù)值x，將x插入在對應位置上，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。從鍵盤輸入1個整數(shù)，表示欲刪除結(jié)點的位置，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。將單鏈表中值重復的結(jié)點刪除，使所得的結(jié)果表中個結(jié)點值均不相同，輸出單鏈表所

2、有結(jié)點值，觀察輸出結(jié)果。刪除其中所有數(shù)據(jù)值為偶數(shù)的結(jié)點，輸出單鏈表所有結(jié)點值，觀察輸出結(jié)果。把單鏈表變成帶表頭結(jié)點的循環(huán)鏈表，輸出循環(huán)單鏈表所有結(jié)點值，觀察輸出結(jié)果。（）將單鏈表分解成兩個單鏈表A和B，使A鏈表中含有原鏈表中序號為奇數(shù)的元素，而B鏈表中含有原鏈表中序號為偶數(shù)的元素，且保持原來的相對順序，分別輸出單鏈表A和單鏈表B的所有結(jié)點值，觀察輸出結(jié)果。二、程序設(shè)計的基本思想，原理和算法描述：（包括程序的結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，輸入/輸出設(shè)計，符號名說明等）三、源程序及注釋：#include /單鏈表的定義：typedef int DataType; /DataType可以是任何相應的數(shù)據(jù)類型如in

3、t, float或chartypedef struct node /結(jié)點類型定義DataType data; /結(jié)點的數(shù)據(jù)域struct node *next; /結(jié)點的指針域ListNode,*LinkList;/typedef ListNode *LinkList;void main()int i;DataType key,x;LinkList head;/ListNode *p;LinkList p;LinkList CreateList(void);void PrintList(LinkList head);LinkList LocateNode(LinkList head,DataT

4、ype key);LinkList GetNode(LinkList head,int i);void InsertList(LinkList head,DataType x,int i);void DeleteList(LinkList head,int i);void DeleteManyList(LinkList head);void DeleteEvenList(LinkList head);void ChangeCircList(LinkList head);void PrintCircList(LinkList head);head=CreateList(); /建立單鏈表Prin

5、tList(head); /打印單鏈表coutkey;p=LocateNode(head,key);/單鏈表查找couti;p=GetNode(head, i);couti;coutx;InsertList(head,x,i);/單鏈表插入PrintList(head); /打印單鏈表couti;DeleteList(head,i); /單鏈表刪除PrintList(head); /打印單鏈表DeleteManyList(head); /刪除重復值PrintList(head); /打印單鏈表DeleteEvenList(head); /刪除偶數(shù)值PrintList(head); /打印單鏈表

6、ChangeCircList(head); /修改為循環(huán)單鏈表PrintCircList(head); /打印循環(huán)單鏈表/*void DivideList(LinkList head,LinkList *A,LinkList *B); /分割成兩個單鏈表DivideList(head, &A, &B);PrintList(A);PrintList(B);*/單鏈表的建立：LinkList CreateList(void)LinkList head,p,q;head=new ListNode;head-next=NULL;q=head;cout輸入20個整數(shù)(以空格分隔):;for(int i=

7、0;ip-data;q-next=p;q=q-next;q-next=NULL;return head;/在此插入必要的語句/單鏈表的打印：void PrintList(LinkList head)LinkList L=head;coutnext!=NULL)coutnext-datanext;coutnext!=NULL)if(L-next-data=key)coutnext;cout沒找到!n;return L;/在此插入必要的語句 /*單鏈表的查找2：LinkList GetNode(LinkList head,int i) LinkList L=head;for(int j=1;jne

8、xt;if(L-next=NULL)coutn查找失敗!n;return L; if(i=0)coutn查找失敗!n;return L;coutdata;cout找到了!n;return L;/單鏈表的插入：void InsertList(LinkList head,DataType x,int i)LinkList L=head,p;for(int j=1;jnext-next=NULL)if(L-next=NULL)coutn;break;L=L-next; if(i=0)coutn;/L=L-next;p=new ListNode;p-data=x;p-next=L-next;L-nex

9、t=p;/在此插入必要的語句/單鏈表的刪除：void DeleteList(LinkList head,int i)LinkList L=head;for(int j=1;jnext;if(L-next=NULL)coutn刪除失敗!n;return;if(i=0)coutn刪除失敗!n;return;L-next=L-next-next;cout刪除成功!n;/在此插入必要的語句/刪除單鏈表中重復值：void DeleteManyList(LinkList head)LinkList L=head,p;coutnext!=NULL)p=L-next;while(p-next!=NULL)if

10、(L-next-data=p-next-data)L-next=L-next-next;p=p-next;L=L-next;/在此插入必要的語句/刪除單鏈表中偶數(shù)值：void DeleteEvenList(LinkList head)LinkList L=head;coutnext-data%2=0)if(L-next-next!=NULL)L-next=L-next-next;else L-next=NULL;break;L=L-next;while(L-next!=NULL);/在此插入必要的語句/修改為循環(huán)單鏈表：void ChangeCircList(LinkList head)LinkList L=head;coutnext!=NULL)L=L-next;L-next=head;/在此插入必要的語句/循環(huán)單鏈表的打?。簐oid PrintCir