合肥工業(yè)大學數(shù)據(jù)結構試驗一實驗報告(共18頁)

1、精選優(yōu)質文檔-傾情為你奉上計算機與信息學院數(shù)據(jù)結構實驗報告專 業(yè) 班 級 學生姓名及學號 課程教學班號 任 課 教 師 實驗指導教師 實驗地點 2015 2016 學年第 2 學期說 明實驗報告是關于實驗教學內容、過程及效果的記錄和總結，因此，應注意以下事項和要求：1每個實驗單元在4頁的篇幅內完成一份報告?！皩嶒瀱卧敝赴凑諏嶒炛笇?guī)定的實驗內容。若篇幅不夠，可另附紙。2、各實驗的預習部分的內容是進入實驗室做實驗的必要條件，請按要求做好預習。3實驗報告要求：書寫工整規(guī)范，語言表達清楚，數(shù)據(jù)和程序真實。理論聯(lián)系實際，認真分析實驗中出現(xiàn)的問題與現(xiàn)象，總結經(jīng)驗。4參加實驗的每位同學應獨立完成實驗報

2、告的撰寫，其中程序或相關的設計圖紙也可以采用打印等方式粘貼到報告中。嚴禁抄襲或拷貝，否則，一經(jīng)查實，按作弊論取，并取消理論課考試資格。5實驗報告作為評定實驗成績的依據(jù)。 實驗序號及名稱：實驗一 單鏈表實驗 實驗時間 2016年 5 月 預習內容一、實驗目的和要求（1）理解線性表的鏈式存儲結構。（2）熟練掌握動態(tài)鏈表結構及有關算法的設計。（3）根據(jù)具體問題的需要，設計出合理的表示數(shù)據(jù)的鏈表結構，設計相關算法。二、實驗任務說明1：本次實驗中的鏈表結構均為帶頭結點的單鏈表。說明2：為使實驗程序簡潔直觀，下面的部分實驗程序中將所需要的函數(shù)以調用庫函數(shù)的形式給出，并假設將庫函數(shù)放在程序文件“l(fā)inkli

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

4、ee5.0二、實驗內容與步驟（過程及數(shù)據(jù)記錄）：<1>求鏈表中第i個結點的指針（函數(shù)），若不存在，則返回NULL。實驗測試數(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ù)<2>在第i個結點

5、前插入值為x的結點。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度n10，x=100, i分別為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 (i<1 | i>length() + 1) return rangeerror;node *s = new node;s->data = x;s->n

6、ext = p->next;p->next = s;count+;return success;<3>刪除鏈表中第i個元素結點。實驗測試數(shù)據(jù)基本要求：第一組數(shù)據(jù)：鏈表長度n10，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 < 1 | i > count) return rangeerror;no

7、de *u;u = p->next;p->next = u->next;count-;delete u;return success;<4>在一個遞增有序的鏈表L中插入一個值為x的元素，并保持其遞增有序特性。實驗測試數(shù)據(jù)基本要求：鏈表元素為 （10,20,30,40,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 < x)

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

9、0,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; else p=p->next;q=q->next; <6>求兩個遞增有序鏈表L1和L2中的公共元素

10、，并以同樣方式連接成鏈表L3。實驗測試數(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; node*LB; node*LC; node*a;node*b; LC=C.

11、get_head(); LA=A.get_head(); LB=B.get_head(); a=LA->next;b=LB->next; while(a!=NULL&&b!=NULL) if(a->data<b->data) a=a->next; else if(a->data>b->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

12、->next=NULL; CPP文件附加：#include <iostream.h>#include<math.h> 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 in

13、t i); error_code insert(const int locate,const int i); error_code delete_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 nod

14、e; head->next=NULL; count=0; int list:length() const node*p=head->next; int count=0; while(p!=NULL) count+; p=p->next; return count;void list:create_R()int x;cout<<"請輸入鏈表中的數(shù)值，按-1后結束創(chuàng)建"<<endl; cin>>x;node*rear=head;while(x!=-1)count+;node*s=new node;s->data=x;r

15、ear->next=s;rear=s;rear->next=NULL;cin>>x; node * list :get_element(int locate)constif(count=0) return 0; elseif(locate<=0|locate>=count)return 0;elsenode*p=head; int k=0;while(p!=NULL&&k<locate)p=p->next;k+;return p; void list:show() node*p=head; while(p!=NULL) cout&

16、lt;<p->data<<"t" p=p->next; 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 (locate<1|locate>count+1) return arrange_error; else node*p=head;int j=

17、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&&i<=p->next->data) node*s=ne

18、w node; s->data=i; s->next=p->next; p->next=s; count+; 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->nex

19、t;j+; if(i<1|i>count) return arrange_error; node*u=new node; u=p->next; p->next=u->next; delete u; count-; 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-&

20、gt;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;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->ne

21、xt=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->next;b=LB->next; while(a!=NULL&&b!=NULL) if(a->data<b->data) a=a->

22、next; else if(a->data>b->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" c

23、out<<" 主菜單 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;cout<<"Enter choice:"cin>>choice;switch(choice)case 1:A.create_R();B.create_R();A.le