合肥工業(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è)班級(jí)學(xué)生及學(xué)號(hào)課程教學(xué)班號(hào)任課教師實(shí)驗(yàn)指導(dǎo)教師實(shí)驗(yàn)地點(diǎn)20152016學(xué)年第2學(xué)期說(shuō)明實(shí)驗(yàn)報(bào)告是關(guān)于實(shí)驗(yàn)教學(xué)容、過(guò)程及效果的記錄和總結(jié)，因此，應(yīng)注意以下事項(xiàng)和要求：1. 每個(gè)實(shí)驗(yàn)單元在4頁(yè)的篇幅完成一份報(bào)告。“實(shí)驗(yàn)單元”指按照實(shí)驗(yàn)指導(dǎo)書規(guī)定的實(shí)驗(yàn)容。若篇幅不夠，可另附紙。2. 各實(shí)驗(yàn)的預(yù)習(xí)部分的容是進(jìn)入實(shí)驗(yàn)室做實(shí)驗(yàn)的必要條件，請(qǐng)按要求做好預(yù)習(xí)。3. 實(shí)驗(yàn)報(bào)告要求：書寫工整規(guī)，語(yǔ)言表達(dá)清楚，數(shù)據(jù)和程序真實(shí)。理論聯(lián)系實(shí)際，認(rèn)真分析實(shí)驗(yàn)中出現(xiàn)的問(wèn)題與現(xiàn)象，總結(jié)經(jīng)驗(yàn)。4. 參加實(shí)驗(yàn)的每位同學(xué)應(yīng)獨(dú)立完成實(shí)驗(yàn)報(bào)告的撰寫，其中程序或相關(guān)的設(shè)計(jì)圖紙也可以采用打印等方式粘貼到

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

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

4、(函數(shù))，若不存在，則返回NULL實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長(zhǎng)度nA10i分別為5,n,0,n+1,n+2第二組數(shù)據(jù)：鏈表長(zhǎng)度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個(gè)結(jié)點(diǎn)前插入值為x的結(jié)點(diǎn)。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長(zhǎng)度nA10x=100,i分別為5,n,n+1,0,1,n+2第二組數(shù)據(jù)：鏈表長(zhǎng)度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個(gè)元素結(jié)點(diǎn)。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長(zhǎng)度nA10i分別為5,n,1,n+1,0第二組數(shù)據(jù)：鏈表長(zhǎng)度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>在一個(gè)遞增有序的鏈表L中插入一個(gè)值為x的元素，并保持其遞增有序特性。實(shí)驗(yàn)測(cè)試數(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ù)項(xiàng)和偶數(shù)項(xiàng)結(jié)點(diǎn)分解開(kāi)，并分別連成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，然后再將這兩個(gè)新鏈表同時(shí)輸出在屏幕上，并保留原鏈表的顯示結(jié)果，以便對(duì)照求解結(jié)果。實(shí)驗(yàn)測(cè)試數(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>求兩個(gè)遞增有序鏈表L1和L2中的公共元素，并以同樣方式連接成

12、鏈表L3。實(shí)驗(yàn)測(cè)試數(shù)據(jù)基本要求:第一組第一個(gè)鏈表元素為(1,3,6,10151617181920)第二個(gè)鏈表元素為(1,2,3,4,5,6,7,8,9,101820,30)第二組第一個(gè)鏈表元素為(1,3,6,10151617181920)第二個(gè)鏈表元素為(2,45,7,8,9,1222)第三組第一個(gè)鏈表元素為（）第二個(gè)鏈表元素為(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<<"請(qǐng)輸入鏈表中的數(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個(gè)節(jié)點(diǎn)指針n"cout<<"n"cout<<"3-在第i個(gè)節(jié)點(diǎn)前插入一個(gè)數(shù)4-刪除鏈表中的第i個(gè)節(jié)點(diǎn)n”cout<<"n"cout<<"5-分離鏈表6-求公共兀素n”;cout<<"n"cout<<"7-插入一個(gè)數(shù)8-退出n"cout<<"n"cout<<"*"<<endl;c