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

1、計算機與信息學院數(shù)據(jù)結(jié)構(gòu)實驗報告專業(yè)班級學生及學號課程教學班號任課教師實驗指導教師實驗地點20152016學年第2學期說明實驗報告是關(guān)于實驗教學容、過程及效果的記錄和總結(jié)，因此，應注意以下事項和要求：1. 每個實驗單元在4頁的篇幅完成一份報告?！皩嶒瀱卧敝赴凑諏嶒炛笇?guī)定的實驗容。若篇幅不夠，可另附紙。2. 各實驗的預習部分的容是進入實驗室做實驗的必要條件，請按要求做好預習。3. 實驗報告要求：書寫工整規(guī)，語言表達清楚，數(shù)據(jù)和程序真實。理論聯(lián)系實際，認真分析實驗中出現(xiàn)的問題與現(xiàn)象，總結(jié)經(jīng)驗。4. 參加實驗的每位同學應獨立完成實驗報告的撰寫，其中程序或相關(guān)的設計圖紙也可以采用打印等方式粘貼到

2、報告中。嚴禁抄襲或拷貝，否則，一經(jīng)查實，按作弊論取，并取消理論課考試資格。5. 實驗報告作為評定實驗成績的依據(jù)實驗序號及名稱：實驗_單鏈表實驗實驗時間：201胡5月預習容一、實驗目的和要求：(D理解線性表的鏈式存儲結(jié)構(gòu)。(2) 熟練掌握動態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設計。(3) 根據(jù)具體問題的需要，設計出合理的表示數(shù)據(jù)的鏈表結(jié)構(gòu)，設計相關(guān)算法。二、實驗任務：說明1:本次實驗中的鏈表結(jié)構(gòu)均為帶頭結(jié)點的單鏈表。說明2:為使實驗程序簡潔直觀，下面的部分實驗程序中將所需要的函數(shù)以調(diào)用庫函數(shù)的形式給出，并假設將庫函數(shù)放在程序文件“l(fā)inklist.fi中，同時假設該庫函數(shù)文件中定義了鏈表結(jié)構(gòu)中的指針類型為li

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

4、(函數(shù))，若不存在，則返回NULL實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度nA10i分別為5,n,0,n+1,n+2第二組數(shù)據(jù)：鏈表長度n=0,i分別為0,2node*list:address(inti)(node*p=head->next;intn=1;while(n!=i&&p!=NULL)(p=p->next;n+;if(p!=NULL)returnp;elsereturnNULL;第一組數(shù)據(jù)caut<<endl:SJBF:windowsAsyrtfrm32errid.execout<<"地址為："<<

5、endl:cout<<listl.address(S)<<endl;cout-list-1.address(11)endl;GQVftlist-Laddress(0)<目也dl；gqwV<<listlh4cout<<listLaddress«$ndl,/*cout<<list1raddress(0)<<endl:coat<<listl.addr*££(2)«end.1:leturnU:輸入鏈表的數(shù)據(jù)1234567890糖表丸123456709Q甌止為:09DF726

6、0曲麗麗跚0000000000010900青按任意鍵繼續(xù)-第二組數(shù)據(jù)cout<<”地址為："«endl：/*coudtlist1.address(EJCencLl:33F:windom32cmd.ex®輸入鏈表的數(shù)據(jù)rzr"H"list-1.address(11)«endl;<<list-1,address(0)<<endl;址為；<<listl.address(12)«endl:U.F：.<<listl.address11.5)«en.dl:*/勇按任意

7、鍵續(xù).cout<<list!,address(0)cout<<listl.address(2)return0,«endl;«endl：<2>在第i個結(jié)點前插入值為x的結(jié)點。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度nA10x=100,i分別為5,n,n+1,0,1,n+2第二組數(shù)據(jù)：鏈表長度n=0,x=100i=5errorcodelist:insert(constinti,constintx)(node*p;p=head;intn=1;while(n!=i&&p!=NULL)(p=p->next;n+;if(i&l

8、t;1|i>length()+1)returnrangeerror;node*s=newnode;s->data=x;s->next=p->next;p->next=s;count+;returnsuccess;<3>刪除鏈表中第i個元素結(jié)點。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度nA10i分別為5,n,1,n+1,0第二組數(shù)據(jù)：鏈表長度n=0,i=5errorcodelist:delete_ele(constinti)(node*p;p=head;intn=1;while(n!=i&&p!=NULL)(p=p->next;n

9、+;if(i<1|i>count)returnrangeerror;node*u;u=p->next;p->next=u->next;count-;deleteu;returnsuccess;<4>在一個遞增有序的鏈表L中插入一個值為x的元素，并保持其遞增有序特性。實驗測試數(shù)據(jù)基本要求：鏈表元素為(10,20,30,40,50,60,70,80,90,100x分別為25,85,11伽8errorcodelist:orderinsert(intx)(node*p=head;intn=1;while(p->next!=NULL)(if(p->n

10、ext->data<x)p=p->next;elsebreak;node*u=newnode;u->data=x;u->next=p->next;p->next=u;count+;returnsuccess;<5>將單鏈表L中的奇數(shù)項和偶數(shù)項結(jié)點分解開，并分別連成一個帶頭結(jié)點的單鏈表，然后再將這兩個新鏈表同時輸出在屏幕上，并保留原鏈表的顯示結(jié)果，以便對照求解結(jié)果。實驗測試數(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

11、,80,90,1)00voidseparate(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;elsep=p->next;q=q->next;<6>求兩個遞增有序鏈表L1和L2中的公共元素，并以同樣方式連接成

12、鏈表L3。實驗測試數(shù)據(jù)基本要求:第一組第一個鏈表元素為(1,3,6,10151617181920)第二個鏈表元素為(1,2,3,4,5,6,7,8,9,101820,30)第二組第一個鏈表元素為(1,3,6,10151617181920)第二個鏈表元素為(2,45,7,8,9,1222)第三組第一個鏈表元素為（）第二個鏈表元素為(1,2,3,4,5,6,7,8,9,1。bingji(listA,listB,list&C)(node*LA;node*LB;node*LC;node*a;node*b;LC=C.get_head();LA=A.get_head();LB=B.get_head

13、();a=LA->next;b=LB->next;while(a!=NULL&&b!=NULL)if(a->data<b->data)a=a->next;elseif(a->data>b->data)b=b->next;elsenode*c=newnode;c->data=a->data;LC->next=c;LC=c;C.count+;a=a->next;b=b->next;LC->next=NULL;CP以件附加:#include<iostream.h>#includ

14、e<math.h>enumerrorcodesuccess,arrangeerror;typedefstructnode(intdata;node*next;node;classlist(public:list();intlength()const;list()(;node*get_element(intlocate)const;node*locate(constintx)const;error_codecharu(constinti);error_codeinsert(constintlocate,constinti);error_codedelete_element(const

15、inti);node*get_head()(returnhead;voidseparate(list&A,list&B);intbingji(listA,listB,list&C);voidcreate_R();voidlist:show();private:intcount;node*head;node*rear;list:list()(head=newnode;head->next=NULL;count=0;intlist:length()const(node*p=head->next;intcount=0;while(p!=NULL)count+;p=

16、p->next;returncount;voidlist:create_R()intx;cout<<"請輸入鏈表中的數(shù)值，按-1后結(jié)束創(chuàng)建"<<endl;cin>>x;node*rear=head;while(x!=-1)count+;node*s=newnode;s->data=x;rear->next=s;rear=s;rear->next=NULL;cin>>x;node*list:get_element(intlocate)const(if(count=0)return0;else(if(loc

17、ate<=0|locate>=count)return0;else(node*p=head;intk=0;while(p!=NULL&&k<locate)p=p->next;k+;returnp;voidlist:show()node*p=head;while(p!=NULL)cout<<p->data<<"t”;p=p->next;error_codelist:insert(constintlocate,constinti)if(count=0)node*s=newnode;s->data=i;s-&

18、gt;next=NULL;head->next=s;rear=s;count=1;returnsuccess;else(if(locate<1|locate>count+1)returnarrange_error;else(node*p=head;intj=0;while(j!=locate-1&&p!=NULL)p=p->next;j+;node*s=newnode;s->data=i;s->next=p->next;p->next=s;count+;returnsuccess;error_codelist:charu(cons

19、tinti)node*p=head;while(p!=NULL&&p->next!=NULL)if(p->data<=i&&i<=p->next->data)node*s=newnode;s->data=i;s->next=p->next;p->next=s;count+;elsep=p->next;if(p->next=NULL)node*s=newnode;s->data=i;s->next=NULL;p->next=s;count+;returnsuccess;err

20、or_codelist:delete_element(constinti)node*p=head;intj=0;while(j!=i-1&&p!=NULL)p=p->next;j+;if(i<1|i>count)returnarrangeerror;node*u=newnode;u=p->next;p->next=u->next;deleteu;count-;returnsuccess;voidseparate(list&A,list&B)node*LA;node*LB;node*p;node*q;node*u;node*s;

21、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;elsep=p->next;q=q->next;voidseparate(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

22、;p=LA->next;s=LB;if(p->data%2=0)u=p;p=p->next;q->next=p;s->next=u;s=s->next;elsep=p->next;q=q->next;intlist:bingji(listA,listB,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->next;b=LB->next;while(a!=NULL&&b

23、!=NULL)if(a->data<b->data)a=a->next;elseif(a->data>b->data)b=b->next;else(node*c=newnode;c->data=a->data;LC->next=c;LC=c;C.count+;a=a->next;b=b->next;LC->next=NULL;returnsuccess;intmain()(intchoice;inti;listA;listB;listC;do(/顯示主菜單cout<<"n"cou

24、t<<"n"cout<<"主菜單n"cout<<"n"cout<<"*"<<endl;cout<<"n"cout<<"1-創(chuàng)建鏈表2-求第i個節(jié)點指針n"cout<<"n"cout<<"3-在第i個節(jié)點前插入一個數(shù)4-刪除鏈表中的第i個節(jié)點n”cout<<"n"cout<<"5-分離鏈表6-求公共兀素n”;cout<<"n"cout<<"7-插入一個數(shù)8-退出n"cout<<"n"cout<<"*"<<endl;c