数据结构实验报告(合工大)

1、数据结构实验报告实验一:栈和队列实验目的：掌握栈和队列特点、逻辑结构和存储结构熟悉对栈和队列的一些基本操作和具体的函数定义。利用栈和队列的基本操作完成一定功能的程序。实验任务1. 给出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数N与其它d进制数的转换。（如N=1357,d=8）实验原理:将十进制数N转换为八进制时，采用的是“除取余数法”，即每次用8除N所得的余数作为八进制数的当前个位，将相除所得的商的整数部分作为新的N值重复上述计算，直到N为0为止。此时，将前面所得到的各余数反过来连接便得到最后的转换结果。程序清单#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<<"请输入一个十进制数N和所需转换的进制d"<<endl;cin>>N>>d;if(N=0)cout<<"输出转换结果:"<<N<<endl;while(N)S.push(N%d);N=N/d;cout<<"输出转换结果:&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();测试数据：N=1348 d=8运行结果：2. 给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前n行的内容。(n=8)实验原理：杨辉三角的规律是每行的第一和最后一个数是1，从第三行开始的其余的数是上一行对应位置的左右两个数之和。因此，可用上一行的数来求出对应位置的下一行内容。为此，需要用队列来保存上一行的内容。每

6、当由上一行的两个数求出下一行的一个数时，其中的前一个便需要删除，而新求出的数就要入队。程序清单：#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);运行结果：3. 给出链栈的类定义和函数实现，并设计程序完成如下功能：读入一个有限大小的整数n，并读入n个数，然后按照与输入次序相反的次序输出各元素的值。实验原理：

10、依次将栈中的元素出栈，因为栈的一个特点就是先进后出，。这样，当将原栈为空时，输出与输入次序相反，从而实现了本题的要求。程序清单：#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<<"请任意输入一个整数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();测试数据：n=9 i=1运行结果：实验二:单链表实验目的：理解线性表的链式存储结构。熟练掌握动态链表结构及有关算法的设计。根据具体问题

14、的需要，设计出合理的表示数据的链表结构，并设计相关算法。实验任务：在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。1. 实验数据：链表元素为（10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8。实验原理:给出了要插入的条件，但没有给定插入位置。因此，需要搜索满足这一条件的插入位置的前驱结点而不是序号。程序清单:#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<<"创建一个链表(输入-1结束)："<<endl;l.create2();cout<<"输入要插入的数（输入-1结束）:"<<endl;cout<<"输入一个数:"cin>>x;while(x!=-1)l.insert(x);cout<

21、;<"输入一个数:"cin>>x;l.print();测试数据:链表元素为（10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8。运行结果：2. 将单链表中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验原理：依据题目的要求，需要再创建两个新链表来存储分离后的奇偶项，而奇偶项可以根据数字来控制，把他们取出来并重新连起来。程序清单：#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<<"奇数表：&qu

29、ot;B.output();cout<<"偶数表："C.output();测试数据：第一组数据：链表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60） 第二组数据：链表元素为 （10,20,30,40,50,60,70,80,90,100）运行结果：3.求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。实验原理：设置两个指针怕，pa,pb分别依次指示A,B表中的元素，其初始值分别为A.head->next和B.head->next。在pa,pb均非空时，根据其值的大小关系可能有如下三种情况。(1).

30、pa->data=pb->data:搜索到公共元素，应在C表表尾插入一个结点，其值为pa->data，然后继续A表中下一个元素的搜索，即pa=pa->next,同时pb也往后移。(2). pa->data>pb->data:表明A表中这一元素可能在B表当前元素的后面,因此要往B表的后面搜索,故而执行pb=pb->next,然后继续搜索。(3). pa->data<pb->data:表明A中这一元素在B中不存在，因而执行pa=pa->next以继续对A表中下一个元素的判断。反复执行上述比较，直到pa,pb至少有一个为空为止。

31、此时，剩余的非空部分没有所需要的公共元素，因而搜索结束。程序清单：#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();测试数据：第一组数据： 第一个链表元素为 （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，1

40、2，22）运行结果：实验三：二叉树一、 实验目的1 掌握二叉树的动态链表存储结构及表示。2 掌握二叉树的三种遍历算法（递归和非递归两类）。3 运用二叉树三种遍历的方法求解有关问题。二、实验任务1. 建立一棵采用二叉链表结构存储的二叉树。2. 分别采用递归和非递归两种方式对该二叉树进行先序、中序和后序遍历。3. 求二叉树的高度以及二叉树中叶子结点的数目。实验原理：在二叉链表存储结构中，每个结点应包括存储结点值的数据部分及指向两个孩子结点的指针，不妨设为data,lchild和rchild。对二叉树的遍历是在对各子树分别遍历的基础之上进行的。由于各子树的遍历和整个二叉树的遍历方式相同，因此，可借助

41、对整个二叉树的遍历算法来实现对左、右子树的遍历。程序清单：#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<<"创建一个先序二叉树(输入#为空)："<<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<<"叶子结点数为："cout<<b.leaf(b.get_root()<<endl;break;case 2:cout<<"先序遍历为："b.preorder2();cout<<"中序遍历为："b.inorder2();cout<<"后序遍历为："b.postorder2();cout<<"树的高度为："cout<<b.high(b.