数据结构实验报告_第1页
数据结构实验报告_第2页
数据结构实验报告_第3页
数据结构实验报告_第4页
数据结构实验报告_第5页
已阅读5页,还剩31页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、数据结构实验报告实验一 线性表实验1、 约瑟夫问题求解一问题描述设有编号为1,2,n(n0)的个人围成一个圈,每个人持有一个密码m。从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。二基本要求(1)建立模型,确定存储结构(2)对任意n个人,密码为m,实现约瑟夫问题(3)出圈次序依次输出三本实验用到的理论知识该实验主要要求用线性表完成一些具体问题的应用,在实验中需用到顺序表的定义,循环单链表的建立以及节点类型的选择等问题,将用到模板函数linklist,其中

2、各头文件的定义如下:顺序表结点类型:templatestruct nodet data;/存放个人的编号node *next;/存放个人的密码;单链表结点类型 单链表node.h:templatestruct nodet data;/存放个人的编号t code;/存放个人密码node *next;单链表模板:#include单链表node.htemplateclass linklistpublic:node *first;linklist(t a,t b,int n)first=new node;first-data=a0;first-code=b0;node *r=first,*s;for(

3、int i=1;in;i+)s=new node;s-data=ai;s-code=bi;r-next=s;r=s;r-next=first;/建立有n个元素的单链表;四主要算法(1)顺序表存储时a、m相同void josephus(int a,int n,int m)int s=0;/length表示表长 cout=2;length-)/表示每次减一s=(s+m-1)%length;coutassetw(7);/s为第s个人for(int i=s+1;ilength;i+) ai-1=ai;/删除couta0endl;/最后只剩下一个人b、m不同void josephus(node data

4、,int n,int m)int s=0,k;/k用于保存出圈人的密码cout个人的编号和密码分别为:=2;length-)if(length=n)s=(s+m-1)%length;elses=(s+k-1)%length;k=datas.next-data;coutdatas.data,kt;for(int i=s+1;ilength;i+)datai-1=datai;coutdata0.data,dataendl;(2)循环单链表存储时a、m相同void josephus(linklist *d,int m)node *p=d-first,*pre,*last=d-first;int co

5、unt;cout出队序号为:next!=d-first) last=last-next;while(p-next!=p)count=m;if(count=1)coutdatanext;delete pre;last-next=p;else while(-count)pre=p;p=p-next;coutdatanext=p-next;delete p;p=pre-next;coutdataendl;delete p;b、m不同void josephus(linklist *d,int m)node *p,*pre,*last=d-first;int code=m;p=d-first;cout圈

6、中出队人的编号和密码分别为:next!=d-first) last=last-next;while(p-next!=p)if(code=1)coutdata,codenext=p-next;code=p-code;delete p;p=last-next;elsewhile(-code)pre=p;p=p-next;coutdata,codecode;pre-next=p-next;delete p;p=pre-next;coutdata,codeendl;delete p;五主函数实现(1)顺序表时a、m相同void main()int n,m,a100;cout请输入圈中人的个数n(n0)

7、和出圈人的序号m(m=0):nm;while(n100|n=0|m0)cout输入有误,请重新输入!n;cout请输入圈中人的个数n(n=0):nm; cout出圈人的顺序为:n;for(int i=0;in;i+)ai=i+1;cout第i+1人 ;coutendl;josephus(a,n,m);b、m不同void main()int n,m;node data100,code100;cout请输入圈中的总人数n(n0)和初始的报数上限m(m=0):nm;while(n100|n=0|m0)cout输入有误,请重新输入数据!n;cout请输入圈中的总人数n(n=100)和初始的报数上限m(

8、m=n):nm;for(int i=0;in;i+)codei.data=2*(i+1);codei.next=null;for(i=0;in;i+)datai.data=i+1;datai.next=&codei;josephus(data,n,m);(2)单链表时a、m相同void main()int m,n,a100,b100;cout请输入圈中的总人数n(n0)和出圈人的编号m(m=0):nm;while(n100|n=0|m0)cout您输入有误,请重新输入数据!n;cout请输入圈中的总人数n(n0)和出圈人的编号m(m=0):nm;for(int i=0;in;i+)ai=i+1

9、;bi=m;linklist data(a,b,n);josephus(&data,m);b、m不同void main()int a100,b100,m,n;cout请输入圈中的总人数n(n0)和初始出队数m(m0):nm;while(n100|n=0|m=0)cout您的输入有误,请按要求输入数据!n;cout请输入圈中的总人数n(n0)和初始出队数m(m0):nm;for(int i=0;in;i+)ai=i+1;bi=2*(i+1);linklist data(a,b,n);josephus(&data,m);6、 运行结果(1) 顺序表实现a、m相同b、m不同(2)单链表实现a、m相同

10、b、m不同2、一元代数多项式求和1、 结点类型pnode.htemplatestruct pnodet coef;t exp;pnode *next;2、 链表定义linklist.h#includepnode.htemplateclass linklistpublic:pnode *first;linklist(t a,t b,int n);templatelinklist:linklist(t a,t b,int n)first=new pnode;pnode *r=first,*s;for(int i=0;in;i+)s=new pnode;s-coef=ai;s-exp=bi;r-ne

11、xt=s;r=s;r-next=null;3、 主函数实现#include#includelinklist.hlinklist *add(linklist *a,linklist *b)pnode *pre,*qre,*p,*q,*v;pre=a-first;p=pre-next;qre=b-first;q=qre-next;while(p&q)if(p-expexp)pre=p;p=p-next;else if(p-expq-exp)v=q-next;pre-next=q;q-next=p;q=v;elsep-coef=p-coef+q-coef;if(p-coef=0)pre-next=p

12、-next;delete p;p=pre-next;elsepre=p;p=p-next;qre-next=q-next;delete q;q=qre-next;if(q) pre-next=q;delete b-first;return a;void sort(linklist *a)/将链表按升序排序pnode *p,*q,*r,*s;if(a-first-next&a-first-next-next)s=a-first-next;q=s-next;while(q)r=a-first;p=r-next;while(pexpexp)r=p;p=p-next;elseq=q-next;s-ne

13、xt-next=p;r-next=s-next;s-next=q;break;if(p=q)s=q;q=q-next;void main()int a1100,b1100,a2100,b2100,c1200,c2200;int n1,n2;cout请输入第一个多项式的项数n1(n1=100):n1;while(n1100)cout您输入的项数超出范围,请重新输入!n;cout请输入第一个多项式的项数n1(n1=100):n1;cout请输入第二个多项式的项数n2(n2=100):n2;while(n2100)cout您输入的项数超出范围,请重新输入!n;cout请输入第二个多项式的项数n1(n

14、1=100):n2;cout请分别输入第一个多项式各项的系数和各项对应的指数:n;for(int i=0;in1;i+)cout第i+1a1ib1i;cout请分别输入第二个多项式各项的系数和各项对应的指数:n;for(i=0;in2;i+)cout第i+1a2ib2i;linklist a(a1,b1,n1),b(a2,b2,n2);linklist *add;sort(&a);sort(&b);add=add(&a,&b);pnode *x=add-first;i=0;while(x-next)x=x-next;c1i=x-coef;c2i=x-exp;i+;cout第一项和第二项多项式相

15、加后结果多项式的各项的系数和指数分别为:n;for(int j=0;ji;j+)cout第j+1项系数和指数分别为: c1j,c2jn;4、 运行结果a(x)=4+3-7x+5,b(x)=4+9-8x+6xa(x)+b(x)=12-15x+4x+9x+6x五、实验心得体会本次试验使我初步掌握用上机调试线性表的基本方法。掌握线性表的基本操作,插入,删除,查找,以及线性表经过本次上机实验,我获得的最大的感受是实验前做好准备工作,准备好实验代码,节约录入的时间,并且在程序录入时要认真,往往一时的马虎得通过较长时间的检查方能找到,要是录入时够认真就可以节约很多,通过数次调试,在运行过程中思考发现具体实

16、现细节,进而能够显示期望的实验结果。实验二 栈和队列:迷宫问题求解1、 实验目的2、 掌握栈和队列的顺序存储结构;3、 掌握栈和队列的操作特性;4、 掌握基于顺序栈和链队列的基本操作的实现方法。2、 实验内容1、 设计数据结构存储迷宫;2、 设计存储结构保存从入口到出口的通路;3、 设计算法完成迷宫问题的求解;4、 分析算法的时间复杂度。3、 实验实现1、用栈实现求迷宫从出口到入口的一条路径(不一定是最短路径)(1)顺序栈结构seqstack.hconst int stacksize=64; /10只是示例性的数据,可以根据实际问题具体定义template /定义模板类seqstackclas

17、s seqstackpublic: seqstack(); /构造函数,栈的初始化seqstack() /析构函数 void push(t x); /将元素x入栈t gettop(); t pop(); /将栈顶元素弹出int empty(); /判断栈是否为空void print(); /输出栈中元素private: t datastacksize; /存放栈元素的数组 int top; /栈顶指针,指示栈顶元素在数组中的下标;template seqstack:seqstack()top=-1;template void seqstack:push(t x) if (top=stacksi

18、ze-1) throw 上溢; top+; datatop=x;template t seqstack:pop( ) t x; if (top=-1) throw 下溢; x=datatop-; return x;template t seqstack:gettop()if(top!=-1) return datatop;template int seqstack:empty( )if(top=-1) return 1;else return 0; template void seqstack:print()while(top!=-1)t temp;temp=pop();couttemp.xt

19、temp.yttemp.dn;(2) 主函数实现a、 四方向查找#include#includeseqstack.hconst int n=10;typedef structint x,y,d; datatype;struct directincint dx,dy;const directinc move4=0,1,1,0,0,-1,-1,0;void mazepath(int mazenn)datatype temp;int g,h,v,i,j;seqstack s;/栈(*s)已建立temp.x=1;temp.y=1;temp.d=-1;/入口位置及方向maze11=-1;s.push(t

20、emp);while(!s.empty()temp=s.gettop();i=temp.x;j=temp.y;v=temp.d+1;if(v=4) s.pop();while(v4)g=i+movev.dx; h=j+movev.dy;if(mazegh=0)temp.x=g; temp.y=h; temp.d=v;s.push(temp);mazeij=-1; i=g; j=h;if(i=n-2&j=n-2)s.print();return;else v=0;else v+;if(v=4) s.pop();/end while(v4)/end while(!s.empty()void mai

21、n()int mazenn=1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;cout从出口到入口的路径为n(x y代表坐标d代表方向(东0,南1,西2,北3)nxtytdendl;mazepath(maze);运行结果:b、八方向查找#includ

22、e#includeseqstack.hconst int n=10;typedef structint x,y,d; datatype;struct directincint dx,dy;const directinc move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;void mazepath(int mazenn)datatype temp;int g,h,v,i,j;seqstack s;/栈(*s)已建立temp.x=1;temp.y=1;temp.d=-1;/入口位置及方向maze11=-1;s.push(temp);while(!s.empty

23、()temp=s.gettop();i=temp.x;j=temp.y;v=temp.d+1;if(v=8) s.pop();while(v8)g=i+movev.dx; h=j+movev.dy;if(mazegh=0)temp.x=g; temp.y=h; temp.d=v;s.push(temp);mazeij=-1; i=g; j=h;if(i=n-2&j=n-2)s.print();return;else v=0;else v+;if(v=8) s.pop();/end while(v8)/end while(!s.empty()void main()int mazenn=1,1,1

24、,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;cout从出口到入口的路径为n(x y代表坐标d代表方向(东0,东南1,南2,西南3,西4,西北5,北6,东北7)nxtytdendl;mazepath(maze);运行结果:2、用队列实现求迷宫问题从入口到出

25、口的最短路径(1) 链队列结构cirqueue.hconst int queuesize=100; /定义存储队列元素的数组的最大长度template /定义模板类cirqueueclass cirqueuepublic: cirqueue( ); /构造函数,置空队 cirqueue( ); /析构函数 void enqueue(t x); /将元素x入队 t dequeue( ); /将队头元素出队 t getqueue( ); /取队头元素(并不删除) int empty( ); /判断队列是否为空t get(int i);int getfront()return front;int g

26、etrear()return rear;private: t dataqueuesize; /存放队列元素的数组 int front, rear; /队头和队尾指针,分别指向队头元素的前一个位置和队尾元素的位置;template cirqueue:cirqueue( ) front=rear=0; template cirqueue:cirqueue( )template void cirqueue:enqueue(t x) if (rear+1) % queuesize =front) throw 上溢; rear=(rear+1) % queuesize; /队尾指针在循环意义下加1 da

27、tarear=x; /在队尾处插入元素template t cirqueue:dequeue( ) if (rear=front) throw 下溢; front=(front+1) % queuesize; /队头指针在循环意义下加1 return datafront; /读取并返回出队前的队头元素,注意队头指针template /指向队头元素的前一个位置t cirqueue:getqueue( ) int i; if (rear=front) throw 下溢; i=(front+1) % queuesize; /注意不要给队头指针赋值 return datai;template int

28、cirqueue:empty( ) if (front=rear) return 1; else return 0;template t cirqueue:get(int i)if(i=0&i=rear) return datai;(2) 主函数实现(八方向查找)#include#include cirqueue.hconst int m=6,n=8;typedef structint x,y,pre; datatype;struct directincint dx,dy;directinc move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;void pr

29、intshortpath(cirqueue q)int i=q.getrear();dodatatype e=q.get(i);cout(e.x,e.y)pre:e.preendl;i=e.pre;while(i!=-1);coutendlwhole queue:endl;for(int u=1;u=q.getrear();u+)datatype e=q.get(u);cout(e.x,e.y)pre:e.preendl;void restore(int mazem+2n+2)int i,j;for(i=1;i=m;i+)for(j=1;j=n;j+)if(mazeij=-1) mazeij=

30、0;for(i=1;i=m;i+) for(j=1;j=n;j+)coutmazeij ;coutendl;void shortpathque(cirqueue *q,int mazem+2n+2)int i,j,g,h,v,find=0;datatype e=1,1,-1;q-enqueue(e);maze11=-1;while(!q-empty()&!find)e=q-dequeue();i=e.x;j=e.y;for(v=0;vgetfront();q-enqueue(e);mazegh=-1;if(g=m&h=n)printshortpath(*q);restore(maze);fin

31、d=1;/if(g)/if(maze)/for/whileif(!find) coutno path!endl;/endvoid main()cirqueue q;int mazem+2n+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,0,1,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1;cout走出迷宫的正确路径为:n;shortpathque(&q,maze);运行结果

32、:四、实验心得体会通过本实验,我初步了解了栈和队列的顺序存储结构;掌握栈和队列的操作特性;掌握基于顺序栈和链队列的基本操作的实现方法。我感觉最大的不足就是对c+编程不够熟悉,经常犯一些比较低级的错误,程序录入时,不时会有一些“马虎“,应多加注意。实验三 二叉树的操作1、 实验目的1、 掌握二叉树的逻辑结构;2、 掌握二叉树的二叉链表存储结构;3、 掌握基于二叉链表存储的二叉树的遍历操作的实现。2、 实验内容1、 采用二叉链表存储建立一棵含有n个结点的二叉树;2、 前序打印该二叉树的所有叶子结点;3、 统计该二叉树的结点个数;4、 计算该二叉树的深度;5、 交换该二叉树的所有左右子树。3、 程序

33、实现1、 二叉链表结点类型binode.htemplatestruct binode t data;binode *lchild,*rchild;2、 二叉树的建立及操作bitree.htemplatestruct binode t data;binode *lchild,*rchild;template class bitreepublic:bitree( ); /构造函数,初始化一棵二叉树,其前序序列由键盘输入bitree(); /析构函数,释放二叉链表中各结点的存储空间 binode* getroot(); /获得指向根结点的指针 void preorder(binode *root);

34、 /前序遍历二叉树 void inorder(binode *root); /中序遍历二叉树 void postorder(binode *root); /后序遍历二叉树 void levelorder(binode *root); /层序遍历二叉树 private: binode *root; /指向根结点的头指针 binode* creat(); /有参构造函数调用 void release(binode *root); /析构函数调用 ;templatebitree:bitree() coutroot=creat();template binode* bitree:creat()bino

35、de *root;t ch;cinch; if (ch=#) root = null; else root = new binode; /生成一个结点 root-data=ch; root-lchild=creat(); /递归建立左子树 root-rchild=creat(); /递归建立右子树 return root;templatebitree:bitree()release(root);templatebinode* bitree:getroot( )return root;templatevoid bitree:preorder(binode *root)if(root=null)

36、return;elsecoutdatalchild);preorder(root-rchild);template void bitree:inorder (binode *root) if (root=null) return; /递归调用的结束条件 else inorder(root-lchild); /中序递归遍历root的左子树 coutdatarchild); /中序递归遍历root的右子树template void bitree:postorder(binode *root) if (root=null) return; /递归调用的结束条件 else postorder(root

37、-lchild); /后序递归遍历root的左子树 postorder(root-rchild); /后序递归遍历root的右子树 coutdata ; /访问根结点的数据域template void bitree:levelorder(binode *root)const int maxsize = 100;int front = 0;int rear = 0; /采用顺序队列,并假定不会发生上溢binode* qmaxsize; binode* q;if (root=null) return;elseqrear+ = root;while (front != rear)q = qfront

38、+; coutdatalchild != null) qrear+ = q-lchild;if (q-rchild != null) qrear+ = q-rchild;templatevoid bitree:release(binode* root) if (root != null) release(root-lchild); /释放左子树 release(root-rchild); /释放右子树 delete root; 3、 主程序实现#include#include bitree.hint sumnode(binode *root)/统计二叉树结点个数int sum;if(root=

39、null)return 0;elsesum=sumnode(root-lchild)+1;sum+=sumnode(root-rchild);return sum;void preprint(binode *root)/前序打印二叉树叶子结点if(root=null) return;elseif(root-lchild=null&root-rchild=null)coutdatalchild);preprint(root-rchild);int treedeepth(binode *root)/计算二叉树的深度int deepth;if(root=null) return 0;elsedeepth=(treedeepth(root-lchild)+1)(treedeepth(root-rchild)+1)?(treedeepth(root-lchild)+1):(treedeepth(root-rchild)+1);return deepth;void chang

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论