合工大 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

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

2、e<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 dataMA

3、XLEN;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(

4、)return underflow;elsecount-;return success;bool stack:full()constreturn count=MAXLEN;void main()stack S;int N,d;cout<<"請輸入一個(gè)十進(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é)

5、果:"<<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. 給出順序隊(duì)列的類定義和函數(shù)實(shí)現(xiàn)，并利用隊(duì)列計(jì)算并打印楊輝三角的前n行的內(nèi)容。(n=8)實(shí)驗(yàn)原理：楊輝三角的規(guī)律是每行的第一和最后一個(gè)數(shù)是1，從第三行開始的其余的數(shù)是上一行對應(yīng)位置的左右兩個(gè)數(shù)之和。因此，可用上一行的數(shù)來求出對應(yīng)位置的下一行內(nèi)容。為此，需要用隊(duì)列來保存上一行的

6、內(nèi)容。每當(dāng)由上一行的兩個(gè)數(shù)求出下一行的一個(gè)數(shù)時(shí)，其中的前一個(gè)便需要?jiǎng)h除，而新求出的數(shù)就要入隊(duì)。程序清單：#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_co

7、de append(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

8、success;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.

9、append(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ù)實(shí)現(xiàn)，并設(shè)計(jì)程序完成如下功能：讀入一個(gè)有限大小的整數(shù)n，并讀入n個(gè)數(shù)，然后按照與輸入次序相反的次序輸出各元素的值。實(shí)

10、驗(yàn)原理：依次將棧中的元素出棧，因?yàn)闂５囊粋€(gè)特點(diǎn)就是先進(jìn)后出，。這樣，當(dāng)將原棧為空時(shí)，輸出與輸入次序相反，從而實(shí)現(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(

11、);bool 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 LN

12、ode;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 succes

13、s;linkstack:linkstack()while(!empty()pop();void main()linkstack L;int n;cout<<"請任意輸入一個(gè)整數(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é)果：實(shí)驗(yàn)二:單鏈表實(shí)驗(yàn)?zāi)康模豪斫饩€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。熟練掌握動(dòng)態(tài)鏈表結(jié)構(gòu)及有關(guān)算法的設(shè)計(jì)。根據(jù)

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

15、 *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);node *locate(const int x) const;node *get_head()return head;void

16、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<<"輸入一個(gè)值："cin>>x;while(x!=-1)s=new node; s->data=x;s->next=NULL; p->next=s;p=s;cout<<"輸入一個(gè)值："cin>>x;int l

17、ist: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-&g

18、t;data=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->nex

19、t;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->next=u->next;delete u;count-;return success;void list:print()node *p=head->nex

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

21、t<<"輸入一個(gè)數(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ù)項(xiàng)和偶數(shù)項(xiàng)結(jié)點(diǎn)分解開，并分別連成一個(gè)帶頭結(jié)點(diǎn)的單鏈表，然后再將這兩個(gè)新鏈表同時(shí)輸出在屏幕上，并保留原鏈表的顯示結(jié)果，以便對照求解結(jié)果。實(shí)驗(yàn)原理：依據(jù)題目的要求，需要再創(chuàng)建兩個(gè)新鏈表來存儲分離后的奇偶項(xiàng)，而奇偶項(xiàng)可以根據(jù)數(shù)字來控制，把他們?nèi)〕鰜聿⒅匦逻B起來。程序清單：#include<iostream>#include<cstdli

22、b>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)

23、;node *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<<"輸入一個(gè)值："cin>>x;while(x!=-1)s=new nod

24、e; s->data=x;s->next=NULL; p->next=s;p=s;cout<<"輸入一個(gè)值："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->d

25、ata;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=ne

26、w 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: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->

27、;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_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->nex

28、t;p->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ù)表

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

30、(1).pa->data=pb->data:搜索到公共元素，應(yīng)在C表表尾插入一個(gè)結(jié)點(diǎn)，其值為pa->data，然后繼續(xù)A表中下一個(gè)元素的搜索，即pa=pa->next,同時(shí)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表中下一個(gè)元素的判斷。反復(fù)執(zhí)行上述比較，直到pa,pb至少有一個(gè)為

31、空為止。此時(shí)，剩余的非空部分沒有所需要的公共元素，因而搜索結(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) c

32、onst;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()i

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

34、gt;next;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;

35、u->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:d

36、ivide(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:i

37、nsert(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_

38、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;while(p!=NULL)cout<<p->data<<" "p

39、=p->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ù)： 第一個(gè)鏈表元素為 （1，3，6，10，15，16，17，18，19，20） 第二個(gè)鏈表元素為 （1，2，3，4，5，6，7，8，9，10，18，20，30） 第二組數(shù)據(jù)： 第一個(gè)鏈表元素為 （1，3，6，10，15，16，17，18，19，20） 第二個(gè)鏈表元素為 （2，4，5，7，8

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

41、，可借助對整個(gè)二叉樹的遍歷算法來實(shí)現(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 fu

42、ll()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;b

43、ool 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

44、(full()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 *cre

45、ate();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

46、*root;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

48、*T)if(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!=NUL

49、L)s.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

50、*T)stack 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<&l

51、t;endl;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->da

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

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