合肥工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)試驗(yàn)一實(shí)驗(yàn)報(bào)告

1、.計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告專 業(yè) 班 級 學(xué)生姓名及學(xué)號 課程教學(xué)班號 任 課 教 師 實(shí)驗(yàn)指導(dǎo)教師 實(shí)驗(yàn)地點(diǎn) 2015 2016 學(xué)年第 2 學(xué)期說 明實(shí)驗(yàn)報(bào)告是關(guān)于實(shí)驗(yàn)教學(xué)內(nèi)容、過程及效果的記錄和總結(jié)，因此，應(yīng)注意以下事項(xiàng)和要求：1每個實(shí)驗(yàn)單元在4頁的篇幅內(nèi)完成一份報(bào)告。“實(shí)驗(yàn)單元”指按照實(shí)驗(yàn)指導(dǎo)書規(guī)定的實(shí)驗(yàn)內(nèi)容。若篇幅不夠，可另附紙。2、各實(shí)驗(yàn)的預(yù)習(xí)部分的內(nèi)容是進(jìn)入實(shí)驗(yàn)室做實(shí)驗(yàn)的必要條件，請按要求做好預(yù)習(xí)。3實(shí)驗(yàn)報(bào)告要求：書寫工整規(guī)范，語言表達(dá)清楚，數(shù)據(jù)和程序真實(shí)。理論聯(lián)系實(shí)際，認(rèn)真分析實(shí)驗(yàn)中出現(xiàn)的問題與現(xiàn)象，總結(jié)經(jīng)驗(yàn)。4參加實(shí)驗(yàn)的每位同學(xué)應(yīng)獨(dú)立完成實(shí)驗(yàn)報(bào)告的撰寫，其中程序或相關(guān)

2、的設(shè)計(jì)圖紙也可以采用打印等方式粘貼到報(bào)告中。嚴(yán)禁抄襲或拷貝，否則，一經(jīng)查實(shí)，按作弊論取，并取消理論課考試資格。5實(shí)驗(yàn)報(bào)告作為評定實(shí)驗(yàn)成績的依據(jù)。 實(shí)驗(yàn)序號及名稱：實(shí)驗(yàn)一 單鏈表實(shí)驗(yàn) 實(shí)驗(yàn)時(shí)間 2016年 5 月 預(yù)習(xí)內(nèi)容一、實(shí)驗(yàn)?zāi)康暮鸵螅?）理解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。（2）熟練掌握動態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計(jì)。（3）根據(jù)具體問題的需要，設(shè)計(jì)出合理的表示數(shù)據(jù)的鏈表結(jié)構(gòu)，設(shè)計(jì)相關(guān)算法。二、實(shí)驗(yàn)任務(wù)說明1：本次實(shí)驗(yàn)中的鏈表結(jié)構(gòu)均為帶頭結(jié)點(diǎn)的單鏈表。說明2：為使實(shí)驗(yàn)程序簡潔直觀，下面的部分實(shí)驗(yàn)程序中將所需要的函數(shù)以調(diào)用庫函數(shù)的形式給出，并假設(shè)將庫函數(shù)放在程序文件“l(fā)inklist.h”中，同時(shí)假設(shè)該

3、庫函數(shù)文件中定義了鏈表結(jié)構(gòu)中的指針類型為link，結(jié)點(diǎn)類型為node，并定義了部分常用運(yùn)算。 例如構(gòu)建鏈表、以某種方式顯示鏈表、從文件中讀入一個鏈表、跟蹤訪問鏈表結(jié)點(diǎn)等。 各運(yùn)算的名稱較為直觀，并有相應(yīng)的注釋，因而易于理解和實(shí)現(xiàn)。三、實(shí)驗(yàn)準(zhǔn)備方案，包括以下內(nèi)容：（硬件類實(shí)驗(yàn)：實(shí)驗(yàn)原理、實(shí)驗(yàn)線路、設(shè)計(jì)方案等）（軟件類實(shí)驗(yàn)：所采用的核心方法、框架或流程圖及程序清單）實(shí)驗(yàn)準(zhǔn)備方案： 構(gòu)建庫函數(shù)：定義了鏈表結(jié)構(gòu)中的指針類型為link，結(jié)點(diǎn)類型為node，并定義了部分常用運(yùn)算，如構(gòu)建鏈表，顯示鏈表，讀取鏈表，訪問鏈表等；流程： 略 實(shí)驗(yàn)內(nèi)容一、實(shí)驗(yàn)用儀器、設(shè)備：個人計(jì)算機(jī)C-free5.0二、實(shí)驗(yàn)內(nèi)容與

4、步驟（過程及數(shù)據(jù)記錄）：求鏈表中第i個結(jié)點(diǎn)的指針（函數(shù)），若不存在，則返回NULL。實(shí)驗(yàn)測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度n10，i分別為5，n，0，n+1，n+2第二組數(shù)據(jù)：鏈表長度n=0，i分別為0，2node* list:address(int i)node *p = head-next;int n = 1;while (n != i&p != NULL)p = p-next;n+;if (p!=NULL) return p;else return NULL;第一組數(shù)據(jù)第二組數(shù)據(jù)在第i個結(jié)點(diǎn)前插入值為x的結(jié)點(diǎn)。實(shí)驗(yàn)測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度n10，x=100, i分別為5

5、,n,n+1,0,1,n+2第二組數(shù)據(jù)：鏈表長度n=0，x=100，i=5errorcode list:insert(const int i, const int x)node *p;p = head;int n = 1;while (n != i&p != NULL)p = p-next;n+;if (ilength() + 1) return rangeerror;node *s = new node;s-data = x;s-next = p-next;p-next = s;count+;return success;刪除鏈表中第i個元素結(jié)點(diǎn)。實(shí)驗(yàn)測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度n

6、10，i分別為5,n,1,n+1,0 第二組數(shù)據(jù)：鏈表長度n=0， i=5errorcode list:delete_ele(const int i)node *p;p = head;int n = 1;while (n != i&p != NULL)p = p-next;n+;if (i count) return rangeerror;node *u;u = p-next;p-next = u-next;count-;delete u;return success;在一個遞增有序的鏈表L中插入一個值為x的元素，并保持其遞增有序特性。實(shí)驗(yàn)測試數(shù)據(jù)基本要求：鏈表元素為 （10,20,30,40

7、,50,60,70,80,90,100）,x分別為25，85，110和8errorcode list:orderinsert(int x)node *p = head;int n = 1;while (p-next != NULL)if (p-next-data next;else break;node *u = new node;u-data = x;u-next = p-next;p-next = u;count+;return success;將單鏈表中的奇數(shù)項(xiàng)和偶數(shù)項(xiàng)結(jié)點(diǎn)分解開，并分別連成一個帶頭結(jié)點(diǎn)的單鏈表，然后再將這兩個新鏈表同時(shí)輸出在屏幕上，并保留原鏈表的顯示結(jié)果，以便對照求解結(jié)

8、果。實(shí)驗(yàn)測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表元素為 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）第二組數(shù)據(jù)：鏈表元素為 （10,20,30,40,50,60,70,80,90,100）void separate(list&A,list&B,list&C) node*LA;node*LB;node*p;node*q;node*u;node*s; LA=A.get_head(); LB=B.get_head(); q=LA;p=LA-next;s=LB; if(p-data%2=0) u=p;p=p-next;q-next=p; s-next=u; s=s-next;

9、else p=p-next;q=q-next; 求兩個遞增有序鏈表L1和L2中的公共元素，并以同樣方式連接成鏈表L3。實(shí)驗(yàn)測試數(shù)據(jù)基本要求： 第一組第一個鏈表元素為 （1，3，6，10，15，16，17，18，19，20）第二個鏈表元素為 （1，2，3，4，5，6，7，8，9，10，18，20，30）第二組第一個鏈表元素為 （1，3，6，10，15，16，17，18，19，20）第二個鏈表元素為 （2，4，5，7，8，9，12，22）第三組第一個鏈表元素為 （）第二個鏈表元素為 （1，2，3，4，5，6，7，8，9，10）bingji(list A,list B,list&C) node*LA

10、; node*LB; node*LC; node*a;node*b; LC=C.get_head(); LA=A.get_head(); LB=B.get_head(); a=LA-next;b=LB-next; while(a!=NULL&b!=NULL) if(a-datadata) a=a-next; else if(a-datab-data) b=b-next; else node*c=new node; c-data=a-data;LC-next=c;LC=c;C.count+; a=a-next;b=b-next; LC-next=NULL; CPP文件附加：#include #i

11、nclude enum error_codesuccess,arrange_error; typedef struct nodeint data;node*next;node;class listpublic: list(); int length()const; list(); node* get_element(int locate)const; node*locate(const int x)const; error_code charu(const int i); error_code insert(const int locate,const int i); error_code d

12、elete_element(const int i); node* get_head()return head; void separate(list&A,list&B); int bingji(list A,list B,list&C); void create_R();void list:show(); private: int count; node*head ;node*rear ;list:list() head=new node; head-next=NULL; count=0; int list:length() const node*p=head-next; int count

13、=0; while(p!=NULL) count+; p=p-next; return count;void list:create_R()int x;cout請輸入鏈表中的數(shù)值，按-1后結(jié)束創(chuàng)建x;node*rear=head;while(x!=-1)count+;node*s=new node;s-data=x;rear-next=s;rear=s;rear-next=NULL;cinx; node * list :get_element(int locate)constif(count=0) return 0; elseif(locate=count)return 0;elsenode*

14、p=head; int k=0;while(p!=NULL&knext;k+;return p; void list:show() node*p=head; while(p!=NULL) coutdatanext; error_code list:insert(const int locate,const int i) if(count=0) node*s=new node; s-data=i; s-next=NULL; head-next=s; rear=s; count=1; return success; elseif (locatecount+1) return arrange_err

15、or; else node*p=head;int j=0; while(j!=locate-1&p!=NULL) p=p-next;j+; node*s=new node; s-data=i; s-next=p-next; p-next=s; count+;return success; error_code list:charu(const int i) node*p=head;while(p!=NULL&p-next!=NULL) if(p-data=i&inext-data) node*s=new node; s-data=i; s-next=p-next; p-next=s; coun

16、t+; else p=p-next;if(p-next=NULL) node*s=new node; s-data=i; s-next=NULL; p-next=s; count+; return success; error_code list:delete_element(const int i) node *p=head; int j=0; while(j!=i-1&p!=NULL) p=p-next;j+; if(icount) return arrange_error; node*u=new node; u=p-next; p-next=u-next; delete u; count

17、-; return success; void separate(list&A,list&B) node*LA;node*LB;node*p;node*q;node*u;node*s; LA=A.get_head(); LB=B.get_head(); q=LA;p=LA-next;s=LB; while(p!=NULL) if(p-data%2=0) u=p;p=p-next;q-next=p; s-next=u; s=s-next; else p=p-next;q=q-next; void separate(list&A,list&B,list&C) node*LA;node*LB;nod

18、e*p;node*q;node*u;node*s; LA=A.get_head(); LB=B.get_head(); q=LA;p=LA-next;s=LB; if(p-data%2=0) u=p;p=p-next;q-next=p; s-next=u; s=s-next; else p=p-next;q=q-next; int list: bingji(list A,list B,list&C) node*LA; node*LB; node*LC; node*a;node*b; LC=C.get_head(); LA=A.get_head(); LB=B.get_head(); a=LA-

19、next;b=LB-next; while(a!=NULL&b!=NULL) if(a-datadata) a=a-next; else if(a-datab-data) b=b-next; else node*c=new node; c-data=a-data;LC-next=c;LC=c;C.count+; a=a-next;b=b-next; LC-next=NULL; return success;int main()int choice;int i;list A; list B;list C;do/顯示主菜單 cout n; cout n; cout 主菜單 n; cout n; cout *endl; cout n;cout 1-創(chuàng)建鏈表 2-求第i個節(jié)點(diǎn)指針 n; cout n;cout 3-在第i個節(jié)點(diǎn)前插入一個數(shù) 4-刪除鏈表中的第i個節(jié)點(diǎn)n;cout