《数据结构实验报告》由会员分享，可在线阅读，更多相关《数据结构实验报告（36页珍藏版）》请在金锄头文库上搜索。
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 dat
4、a,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 c
5、ount;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+
9、1;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);六、 运行结果（1） 顺序表实现A、m相同B、m不同（2）单链表实现A、m相
10、同B、m不同2、一元代数多项式求和一、 结点类型PNode.htemplatestruct PNodeT coef;T exp;PNode *next;二、 链表定义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-next=s;r=s;r-next=NULL;三、 主函数实现#include#includeLinkList.hLinkList *Add(LinkList *A,LinkListin
