没有合适的资源?快使用搜索试试~ 我知道了~
数据结构实验报告C++版
5星 · 超过95%的资源 需积分: 10 44 下载量 72 浏览量
2009-05-15
19:54:54
上传
评论 4
收藏 125KB DOC 举报
温馨提示
试读
14页
数据结构实验报告,有源程序,C++版,包你满意数据结构实验报告,有源程序,C++版,包你满意
资源推荐
资源详情
资源评论
数据结构实验报告
实验一:线性表的应用
实验二:二叉树的先序遍历、中序遍历
实验三:图的拓扑排序
实验四:内部排序
姓名:张自耕
学号:0605064131
日期:2009 年 5 月 10 日
实验一:线性表的应用
一、 实验目的与要求
(一) 目的
了解线性表及在计算机中的两类不同的存储结构;熟练掌握线性表的查找、插入和删
除等算法并灵活运用这些算法。
(二) 要求
用 C++语言编写程序,实现求解约瑟夫问题。
二、实验内容
题目 约瑟夫问题
编号为 1,2,···,n 的 n 个人围坐在一圆桌旁,从第 s 个人开始报数,报到第 m 的人
退席,下一个人又重新从 1 开始报数,依此重复,直至所有的人都退席。
例 如 , 设 s=1 , m=4 , n=8 , 则 退 席 的 人 的 编 号 依 次 为
4,8,5,2,1,3,7,6。
三、实验原理
(1)以顺序表为存储结构
int p[n];
(2)以循环链表为存储结构
typedef struct lnode{
int data;
struct lnode *next;
} lnode;
四、实验程序
#include <iostream.h>
#include<stdlib.h>
typedef double ElemType;
struct ListSq{
ElemType *list;
int len;
int MaxSize;
};
struct sNode{
ElemType data;
sNode*next;
};
void InitList(ListSq&L,int ms)
{
if(ms<=0){cout<<"ms 值非法!"<<endl;exit(1);}
L.MaxSize=ms;
L.list=new ElemType[ms];
if(!L.list){
cerr<<"存储空间用完"<<endl;
exit(1);
}
L.len=0;
}
void Josephus(int n, int m, int s) //使用带表头附加结点的循环单链表解决约瑟夫问题。
{
//生成表头附加结点,此时循环单链表为空。
sNode* HL=new sNode;
HL->next=HL;
int i; //生成含有 n 个结点的、结点值依次为 1,2,...,n 的带表头附加结点的循环单链
表。
for(i=n; i>=1; i--) {
//生成新结点。
sNode* newptr=new sNode;
newptr->data=i;
//把新结点插入到表头。
newptr->next=HL->next;
HL->next=newptr;
}
//从表头开始顺序查找出第 s 个结点,对应第一个开始报数的人
sNode *ap=HL, *cp=HL->next;
for(i=1; i<s; i++) {
//ap 和 cp 指针后移一个位置。
ap=cp;
cp=cp->next;
//若 cp 指向了表头附加结点,则仍需后移 ap 和 cp 指针,/使之指向表头结点。
if(cp==HL) {ap=HL; cp=HL->next; }
}
//依次使 n-1 个人出列。
for(i=1; i<n; i++) {
//顺序查找出待出列的人,即为循环结束后 cp 所指向的结点
for(int j=1; j<m; j++) {
ap=cp;
cp=cp->next;
if(cp==HL) {ap=HL; cp=HL->next; }
}
//输出 cp 结点的值,即出列的人
剩余13页未读,继续阅读
资源评论
- mzwscdnid2012-12-25改改可以用
- LWZ2332012-05-18条例也比较清晰.报告内容不错
- lichanxiyu2011-10-22报告还蛮详细的,而且条例也比较清晰.
- CHARLIE5112011-10-19报告内容不错,比较有用处
- alec10192017-10-15报告内容可以值得参考,谢谢
zhangzigeng
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功