數(shù)據(jù)結(jié)構(gòu)實驗報告(合工大)

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗一:棧和隊列實驗?zāi)康模赫莆諚：完犃刑攸c、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)熟悉對棧和隊列的一些基本操作和具體的函數(shù)定義。利用棧和隊列的基本操作完成一定功能的程序。實驗任務(wù)1. 給出順序棧的類定義和函數(shù)實現(xiàn)，利用棧的基本操作完成十進(jìn)制數(shù)N與其它d進(jìn)制數(shù)的轉(zhuǎn)換。（如N=1357,d=8）實驗原理:將十進(jìn)制數(shù)N轉(zhuǎn)換為八進(jìn)制時，采用的是“除取余數(shù)法”，即每次用8除N所得的余數(shù)作為八進(jìn)制數(shù)的當(dāng)前個位，將相除所得的商的整數(shù)部分作為新的N值重復(fù)上述計算，直到N為0為止。此時，將前面所得到的各余數(shù)反過來連接便得到最后的轉(zhuǎn)換結(jié)果。程序清單#include<iostream>#include<

2、;cstdlib>using namespace std;typedef int DATA_TYPE;const int MAXLEN=100;enum error_codesuccess,overflow,underflow;class stackpublic:stack();bool empty()const;error_code get_top(DATA_TYPE &x)const;error_code push(const DATA_TYPE x);error_code pop();bool full()const;private:DATA_TYPE dataMAXLEN

3、;int count;stack:stack()count=0;bool stack:empty()constreturn count=0;error_code stack:get_top(DATA_TYPE &x)constif(empty()return underflow;elsex=datacount-1;return success;error_code stack:push(const DATA_TYPE x)if(full()return overflow;elsedatacount=x;count+;error_code stack:pop()if(empty()ret

4、urn underflow;elsecount-;return success;bool stack:full()constreturn count=MAXLEN;void main()stack S;int N,d;cout<<"請輸入一個十進(jìn)制數(shù)N和所需轉(zhuǎn)換的進(jìn)制d"<<endl;cin>>N>>d;if(N=0)cout<<"輸出轉(zhuǎn)換結(jié)果:"<<N<<endl;while(N)S.push(N%d);N=N/d;cout<<"輸出轉(zhuǎn)換結(jié)果:&q

5、uot;<<endl;while(!S.empty()S.get_top(N);cout<<N;S.pop();cout<<endl;while(!S.empty()S.get_top(x);cout<<x;S.pop();測試數(shù)據(jù)：N=1348 d=8運(yùn)行結(jié)果：2. 給出順序隊列的類定義和函數(shù)實現(xiàn)，并利用隊列計算并打印楊輝三角的前n行的內(nèi)容。(n=8)實驗原理：楊輝三角的規(guī)律是每行的第一和最后一個數(shù)是1，從第三行開始的其余的數(shù)是上一行對應(yīng)位置的左右兩個數(shù)之和。因此，可用上一行的數(shù)來求出對應(yīng)位置的下一行內(nèi)容。為此，需要用隊列來保存上一行的內(nèi)容。每

6、當(dāng)由上一行的兩個數(shù)求出下一行的一個數(shù)時，其中的前一個便需要刪除，而新求出的數(shù)就要入隊。程序清單：#include<iostream>#include<cstdlib>using namespace std;typedef int DATA_TYPE;const int MAXLEN=100;enum error_codesuccess,underflow,overflow;class queuepublic:queue();bool empty()const;error_code get_front(DATA_TYPE &x)const;error_code a

7、ppend(const DATA_TYPE x);error_code serve();bool full()const;private:int front,rear;DATA_TYPE dataMAXLEN;queue:queue()rear=0;front=0;bool queue:empty()constreturn (front%MAXLEN=rear%MAXLEN);error_code queue:get_front(DATA_TYPE &x)constif(empty()return underflow;elsex=datafront%MAXLEN;return succ

8、ess;error_code queue:append(const DATA_TYPE x)if(full()return overflow;elsedatarear%MAXLEN=x;rear+;error_code queue:serve()if(empty()return underflow;elsefront+;return success;bool queue:full()constreturn(rear+1)%MAXLEN=front);void main()queue Q;int num1,num2;int i=0;cout<<1<<endl;Q.appe

9、nd(1);num1=0;num2=1;for(i=0;i<=7;i+)int j=0;int k=0;num1=0;for(j=0;j<=i;j+)Q.get_front(num2);Q.serve();cout<<num1+num2<<" "Q.append(num1+num2);num1=num2;cout<<1<<endl;Q.append(1);運(yùn)行結(jié)果：3. 給出鏈棧的類定義和函數(shù)實現(xiàn)，并設(shè)計程序完成如下功能：讀入一個有限大小的整數(shù)n，并讀入n個數(shù)，然后按照與輸入次序相反的次序輸出各元素的值。實驗原理：

10、依次將棧中的元素出棧，因為棧的一個特點就是先進(jìn)后出，。這樣，當(dāng)將原棧為空時，輸出與輸入次序相反，從而實現(xiàn)了本題的要求。程序清單：#include<iostream>#include<cstdlib>using namespace std;typedef int DATA_TYPE;typedef struct LNodeDATA_TYPE data;LNode *next;LNode; enum error_coderange_error,success,underflow;class linkstackpublic:linkstack();linkstack();bo

11、ol empty()const;error_code push(const DATA_TYPE x);error_code get_top(DATA_TYPE &x)const;error_code pop();private:LNode *top;int count; DATA_TYPE data;linkstack:linkstack()top=NULL;count=0;bool linkstack:empty()constreturn (count=0);error_code linkstack:push(const DATA_TYPE x)LNode *s=new LNode;

12、s->data=x;s->next=top;top=s;count+;return success;error_code linkstack:get_top(DATA_TYPE &x)constif(empty()return underflow;elsex=top->data;return success;error_code linkstack:pop()if(empty()return underflow;elseLNode *u=new LNode;u=top;top=top->next;delete u;count-;return success;li

13、nkstack:linkstack()while(!empty()pop();void main()linkstack L;int n;cout<<"請任意輸入一個整數(shù)n:"<<endl;cin>>n;for(int i=1;i<=n;i+)L.push(i);while(!L.empty()L.get_top(i);cout<<i<<" "L.pop();測試數(shù)據(jù)：n=9 i=1運(yùn)行結(jié)果：實驗二:單鏈表實驗?zāi)康模豪斫饩€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。熟練掌握動態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計。根據(jù)具體問題

14、的需要，設(shè)計出合理的表示數(shù)據(jù)的鏈表結(jié)構(gòu)，并設(shè)計相關(guān)算法。實驗任務(wù)：在一個遞增有序的鏈表L中插入一個值為x的元素，并保持其遞增有序特性。1. 實驗數(shù)據(jù)：鏈表元素為（10,20,30,40,50,60,70,80,90,100）,x分別為25，85，110和8。實驗原理:給出了要插入的條件，但沒有給定插入位置。因此，需要搜索滿足這一條件的插入位置的前驅(qū)結(jié)點而不是序號。程序清單:#include<iostream>#include<cstdlib>using namespace std;typedef struct snodeint data;struct snode *ne

15、xt;node;enum error_codearrange_error,success;class listpublic:list();void create2();int length() const;error_code get_element(const int i,int &x) const;error_code insert(const int &x);error_code delete_element(const int i);node *locate(const int x) const;node *get_head()return head;void prin

16、t();private:int count;node *head;list:list()head=new node; head->next=NULL;count=0;void list:create2()int x; node *p=head;node *s; cout<<"輸入一個值："cin>>x;while(x!=-1)s=new node; s->data=x;s->next=NULL; p->next=s;p=s;cout<<"輸入一個值："cin>>x;int list:

17、length() constreturn count;error_code list:get_element(const int i,int &x) constint j=1;node *p=head->next;while(p!=NULL&&j!=i)p=p->next;j+;if(p=NULL)return arrange_error;x=p->data;return success;node *list:locate(const int x) constnode *p=head->next;while(p!=NULL)if(p->da

18、ta=x)return p;p=p->next;return NULL;error_code list:insert(const int &x)node *s;node *q=head;node *p=head->next;while(p!=NULL&&p->data<x)q=p;p=p->next;if(p=NULL)s=new node;s->data=x;s->next=NULL;q->next=s;count+;elses=new node;s->data=x;s->next=q->next;q-

19、>next=s;count+;return success;error_code list:delete_element(const int i)node *u;node *p=head;int j=0;while(j!=i-1&&p!=NULL)p=p->next;j+;if(i<1|i>count)return arrange_error;u=p->next;p->next=u->next;delete u;count-;return success;void list:print()node *p=head->next;wh

20、ile(p!=NULL)cout<<p->data<<" "p=p->next;cout<<endl;void main()list l;int x;cout<<"創(chuàng)建一個鏈表(輸入-1結(jié)束)："<<endl;l.create2();cout<<"輸入要插入的數(shù)（輸入-1結(jié)束）:"<<endl;cout<<"輸入一個數(shù):"cin>>x;while(x!=-1)l.insert(x);cout<

21、;<"輸入一個數(shù):"cin>>x;l.print();測試數(shù)據(jù):鏈表元素為（10,20,30,40,50,60,70,80,90,100）,x分別為25，85，110和8。運(yùn)行結(jié)果：2. 將單鏈表中的奇數(shù)項和偶數(shù)項結(jié)點分解開，并分別連成一個帶頭結(jié)點的單鏈表，然后再將這兩個新鏈表同時輸出在屏幕上，并保留原鏈表的顯示結(jié)果，以便對照求解結(jié)果。實驗原理：依據(jù)題目的要求，需要再創(chuàng)建兩個新鏈表來存儲分離后的奇偶項，而奇偶項可以根據(jù)數(shù)字來控制，把他們?nèi)〕鰜聿⒅匦逻B起來。程序清單：#include<iostream>#include<cstdlib>

22、;using namespace std;typedef struct snodeint data;struct snode *next;node;enum error_codearrange_error,success;class listpublic:list();void create2();int length() const;error_code get_element(const int i,int &x) const;error_code insert(const int &x);error_code delete_element(const int i);nod

23、e *locate(const int x) const;node *get_head()return head;divide(list &B,list &C);void print();private:int count;node *head;list:list()head=new node; head->next=NULL;count=0;void list:create2()int x; node *p=head;node *s; cout<<"輸入一個值："cin>>x;while(x!=-1)s=new node; s

24、->data=x;s->next=NULL; p->next=s;p=s;cout<<"輸入一個值："cin>>x;int list:length() constreturn count;error_code list:get_element(const int i,int &x) constint j=1;node *p=head->next;while(p!=NULL&&j!=i)p=p->next;j+;if(p=NULL)return arrange_error;x=p->data;

25、return success;node *list:locate(const int x) constnode *p=head->next;while(p!=NULL)if(p->data=x)return p;p=p->next;return NULL;void list:divide(list &B,list &C)node *u;node *pa=head->next;node *pb=B.get_head();node *pc=C.get_head();for(int i=0;pa!=NULL;i+,pa=pa->next)u=new no

26、de;u->data=pa->data;if(i%2=0)pb->next=u;pb=pb->next;elsepc->next=u;pc=pc->next;pb->next=NULL;pc->next=NULL;error_code list:insert(const int &x)node *s;node *q=head;node *p=head->next;while(p!=NULL&&p->data<x)q=p;p=p->next;if(p=NULL)s=new node;s->dat

27、a=x;s->next=NULL;q->next=s;count+;elses=new node;s->data=x;s->next=q->next;q->next=s;count+;return success;error_code list:delete_element(const int i)node *u;node *p=head;int j=0;while(j!=i-1&&p!=NULL)p=p->next;j+;if(i<1|i>count)return arrange_error;u=p->next;p-

28、>next=u->next;delete u;count-;return success;void list:print()node *p=head->next;while(p!=NULL)cout<<p->data<<" "p=p->next;cout<<endl;void main()list A,B,C; int x,y,z;A.create_R();A.divide(B,C);cout<<"原表："A.output();cout<<"奇數(shù)表：&qu

29、ot;B.output();cout<<"偶數(shù)表："C.output();測試數(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）運(yùn)行結(jié)果：3.求兩個遞增有序鏈表L1和L2中的公共元素，并以同樣方式連接成鏈表L3。實驗原理：設(shè)置兩個指針怕，pa,pb分別依次指示A,B表中的元素，其初始值分別為A.head->next和B.head->next。在pa,pb均非空時，根據(jù)其值的大小關(guān)系可能有如下三種情況。(1).

30、pa->data=pb->data:搜索到公共元素，應(yīng)在C表表尾插入一個結(jié)點，其值為pa->data，然后繼續(xù)A表中下一個元素的搜索，即pa=pa->next,同時pb也往后移。(2). pa->data>pb->data:表明A表中這一元素可能在B表當(dāng)前元素的后面,因此要往B表的后面搜索,故而執(zhí)行pb=pb->next,然后繼續(xù)搜索。(3). pa->data<pb->data:表明A中這一元素在B中不存在，因而執(zhí)行pa=pa->next以繼續(xù)對A表中下一個元素的判斷。反復(fù)執(zhí)行上述比較，直到pa,pb至少有一個為空為止。

31、此時，剩余的非空部分沒有所需要的公共元素，因而搜索結(jié)束。程序清單：#include<iostream>#include<cstdlib>using namespace std;typedef struct snodeint data;struct snode *next;node;enum error_codearrange_error,success;class listpublic:list();void create2();int length() const;error_code get_element(const int i,int &x) const

32、;error_code insert(const int &x);error_code delete_element(const int i);node *locate(const int x) const;node *get_head()return head; void list:gongyou(list &L1,list &L2)void print();private:int count;node *head;list:list()head=new node; head->next=NULL;count=0;void list:create2()int x

33、; node *p=head;node *s; cout<<"輸入一個值："cin>>x;while(x!=-1)s=new node; s->data=x;s->next=NULL; p->next=s;p=s;cout<<"輸入一個值："cin>>x;int list:length() constreturn count;error_code list:get_element(const int i,int &x) constint j=1;node *p=head->n

34、ext;while(p!=NULL&&j!=i)p=p->next;j+;if(p=NULL)return arrange_error;x=p->data;return success;void list:gongyou(list &L1,list &L2)node *p1=L1.head->next;node *p2=L2.head->next;node *p3=head;node *u;while(p1!=NULL&&p2!=NULL)if(p1->data=p2->data)u=new node;u-&g

35、t;data=p1->data;p3->next=u;p1=p1->next;p2=p2->next;p3=p3->next;elseif(p1->data<p2->data)p1=p1->next;elsep2=p2->next;p3->next=NULL;node *list:locate(const int x) constnode *p=head->next;while(p!=NULL)if(p->data=x)return p;p=p->next;return NULL;void list:divid

36、e(list &B,list &C)node *u;node *pa=head->next;node *pb=B.get_head();node *pc=C.get_head();for(int i=0;pa!=NULL;i+,pa=pa->next)u=new node;u->data=pa->data;if(i%2=0)pb->next=u;pb=pb->next;elsepc->next=u;pc=pc->next;pb->next=NULL;pc->next=NULL;error_code list:inser

37、t(const int &x)node *s;node *q=head;node *p=head->next;while(p!=NULL&&p->data<x)q=p;p=p->next;if(p=NULL)s=new node;s->data=x;s->next=NULL;q->next=s;count+;elses=new node;s->data=x;s->next=q->next;q->next=s;count+;return success;error_code list:delete_elem

38、ent(const int i)node *u;node *p=head;int j=0;while(j!=i-1&&p!=NULL)p=p->next;j+;if(i<1|i>count)return arrange_error;u=p->next;p->next=u->next;delete u;count-;return success;void list:print()node *p=head->next;while(p!=NULL)cout<<p->data<<" "p=p-&

39、gt;next;cout<<endl;void main()list L1,L2,L3;L1.create_R(); L2.create_R(); L3.gongyou(L1,L2);cout<<"共有的元素為："L3.output();測試數(shù)據(jù)：第一組數(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） 第二組數(shù)據(jù)： 第一個鏈表元素為 （1，3，6，10，15，16，17，18，19，20） 第二個鏈表元素為 （2，4，5，7，8，9，1

40、2，22）運(yùn)行結(jié)果：實驗三：二叉樹一、 實驗?zāi)康? 掌握二叉樹的動態(tài)鏈表存儲結(jié)構(gòu)及表示。2 掌握二叉樹的三種遍歷算法（遞歸和非遞歸兩類）。3 運(yùn)用二叉樹三種遍歷的方法求解有關(guān)問題。二、實驗任務(wù)1. 建立一棵采用二叉鏈表結(jié)構(gòu)存儲的二叉樹。2. 分別采用遞歸和非遞歸兩種方式對該二叉樹進(jìn)行先序、中序和后序遍歷。3. 求二叉樹的高度以及二叉樹中葉子結(jié)點的數(shù)目。實驗原理：在二叉鏈表存儲結(jié)構(gòu)中，每個結(jié)點應(yīng)包括存儲結(jié)點值的數(shù)據(jù)部分及指向兩個孩子結(jié)點的指針，不妨設(shè)為data,lchild和rchild。對二叉樹的遍歷是在對各子樹分別遍歷的基礎(chǔ)之上進(jìn)行的。由于各子樹的遍歷和整個二叉樹的遍歷方式相同，因此，可借助

41、對整個二叉樹的遍歷算法來實現(xiàn)對左、右子樹的遍歷。程序清單：#include<iostream.h>#define maxlen 200enum tagtypeL1,L2;typedef struct nodechar data;struct node *lchild,*rchild;bnode;typedef struct bnode *ptr; tagtype tag;stacknode;enum error_codesuccess,underflow,overflow;class stackpublic:stack();bool empty()const;bool full()

42、const;error_code get_top(stacknode &x);error_code get_top(bnode* &x);error_code push(stacknode x);error_code push(bnode* x);error_code pop();private:int count;bnode* data_xianmaxlen;stacknode data_houmaxlen;stack:stack()count=0;bool stack:empty()constif(count=0)return true;return false;bool

43、stack:full()constif(count=maxlen)return true;return false;error_code stack:get_top(stacknode &x)if(empty()return underflow;x=data_houcount-1;return success;error_code stack:get_top(bnode* &x)if(empty()return underflow;x=data_xiancount-1;return success;error_code stack:push(stacknode x)if(ful

44、l()return overflow;data_houcount=x;count+;return success;error_code stack:push(bnode* x)if(full()return overflow;data_xiancount=x;count+;return success;error_code stack:pop()if(empty()return underflow;count-;return success;bitree.h#include"stack.h"class bitreepublic:bitree();bnode *create(

45、);bnode *get_root()return root;int max(int a,int b);void preorder1()preorder1(root);void inorder1()inorder1(root);void postorder1()postorder1(root);void preorder2()preorder2(root);void inorder2()inorder2(root);void postorder2()postorder2(root);int high(bnode *T);int leaf(bnode *T);private:bnode *roo

46、t;void visite(bnode *T);void preorder1(bnode *T);void inorder1(bnode *T);void postorder1(bnode *T);void preorder2(bnode *T);void inorder2(bnode *T);void postorder2(bnode *T);bitree:bitree()root=NULL;bnode* bitree:create()char ch;bnode *p;cout<<"輸入二叉樹的值："cin>>ch;if(ch='#'

47、;)return NULL;p=new bnode;p->data=ch;if(root=NULL)root=p;p->lchild=create();p->rchild=create();return p;int bitree:max(int a,int b)if(a>=b)return a;return b;void bitree:preorder1(bnode *T)if(T!=NULL)visite(T);preorder1(T->lchild);preorder1(T->rchild);void bitree:inorder1(bnode *T)i

48、f(T!=NULL)preorder1(T->lchild);visite(T);preorder1(T->rchild);void bitree:postorder1(bnode *T)if(T!=NULL)preorder1(T->lchild);preorder1(T->rchild);visite(T);void bitree:preorder2(bnode *T)stack s;if(T!=NULL)s.push(T);while(!s.empty()s.get_top(T);s.pop();visite(T);if(T->rchild!=NULL)s.

49、push(T->rchild);if(T->lchild!=NULL)s.push(T->lchild);cout<<endl;void bitree:inorder2(bnode *T)stack s;if(T!=NULL)while(T!=NULL|!s.empty()while(T!=NULL)s.push(T);T=T->lchild;if(!s.empty()s.get_top(T);s.pop();visite(T);T=T->rchild;cout<<endl;void bitree:postorder2(bnode *T)s

50、tack s; stacknode x; do while(T!=NULL) x.ptr=T;x.tag=L1;s.push(x);T=T->lchild; int continue1=1;while(!s.empty()&&continue1)s.get_top(x); s.pop();T=x.ptr; switch(x.tag)case L1: x.tag=L2; s.push(x); T=T->rchild; continue1=0; break;case L2:visite(T); break; while(!s.empty();cout<<en

51、dl;int bitree:high(bnode *T)if(T=NULL)return 0;elsereturn max(high(T->lchild),high(T->rchild)+1;int bitree:leaf(bnode *T)if(T=NULL)return 0;if(T->lchild=NULL&&T->rchild=NULL)return 1;return leaf(T->lchild)+leaf(T->rchild);void bitree:visite(bnode *T)cout<<T->data&l

52、t;<" "void main()bitree b;int x;cout<<"創(chuàng)建一個先序二叉樹(輸入#為空)："<<endl;b.create();cout<<"1.遞歸遍歷"<<" "<<"2.非遞歸遍歷"<<endl;cout<<"輸入你的選擇（輸入-1退出）:"cin>>x;while(x!=-1)switch(x)case 1:cout<<"先

53、序遍歷為："b.preorder1();cout<<endl;cout<<"中序遍歷為："b.inorder1();cout<<endl;cout<<"后序遍歷為："b.postorder1();cout<<endl;cout<<"樹的高度為："cout<<b.high(b.get_root()<<endl;cout<<"葉子結(jié)點數(shù)為："cout<<b.leaf(b.get_root()<<endl;break;case 2:cout<<"先序遍歷為："b.preorder2();cout<<"中序遍歷為："b.inorder2();cout<<"后序遍歷為："b.postorder2();cout<<"樹的高度為："cout<<b.high(b.