数据结构与算法实验报告-约瑟夫环
更新时间:2024-05-14 09:49:01 阅读量: 综合文库 文档下载
题目:约瑟夫环问题
班级:姓名:学号:完成日期:2011.12.28
一、需求分析 1.问题描述:设有n个人围坐在一个圆桌周围,现从第s个人开始报数,数到第m的人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,?,如此反复直到所有的人全部出列为止。 2.测试时n=8,s=1,m=4,若初始的顺序为1,2,3,4,5,6,7,8,则问题的解为4,8,5,2,1,3,7,6。 二、概要设计
为实现上述程序功能,应以循环队列表示。循环队列可用数组实现,但由于n是变量,我选择以单向链表实现循环队列。通过移动头结点的指针来实现“重新开始报数”,以循环实现计数。
1. 循环队列的抽象数据类型定义为: ADT LinkQueue{
数据对象:D={ai|ai∈ElemSet,i=1,2,?,n,n≥0}
数据关系:R1={|ai-1,ai∈D,i=2,?,n}约定其中a1端为队列头,an端为队列尾。 基本操作: InitQueue(&Q)
操作结果:构造一个空队列Q。 GetHead(Q,&e)
初始条件:Q为非空队列。
操作结果:用e返回Q的队头元素。 EnQueue(&Q,e)
初始条件:队列Q已存在。
操作结果:插入元素e为Q的新的队尾元素。 DeQueue(&Q,&e)
初始条件:Q为非空队列。
操作结果:删除Q的队头元素,并用e返回其值。 }ADT LinkQueue
2.本程序包含3个模块:
1)结点定义模块——对表结点进行定义
2)子函数定义模块——对链表的各操作的定义 3)主程序模块
模块之间的关系为主函数调用子函数模块,子函数调用结点结构。
三、详细设计
1. 头函数、元素类型、结点类型和指针类型 typedef int LElemType; typedef int Status;
typedef struct LNode {
LElemType data;
struct LNode *next; }LNode,*LinkList;
2. 根据循环队列的特点,链表的头指针和尾结点的指针都指向第一个结点。 对链表的基本操作如下: LNode *CreateLinkList(int n)
//构造一个空的循环队列,长为输入值n Status ListDelete_L(LNode *L,LElemType *e)
//若队列不为空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
其中部分操作的伪代码如下:
LNode *CreateLinkList(int n)//顺序建立链表,L为头结点 {
L=(LNode*)malloc(sizeof(LNode)); p=(LNode*)malloc(sizeof(LNode)); L->next=p;
p->next=L->next; p->data=1; x=1;
for(i=0;i<=n-2;i++) { x++;
s=(LNode*)malloc(sizeof(LNode)); s->data=x;//插入表尾 p->next=s; p=s; }
p->next=L->next; return L; }
Status ListDelete_L(LNode *L,LElemType *e) {//删除队列当前位置的元素q,并用e返回其值 LNode *p; LNode *q;
p=L;
if(!(p->next)) return ERROR; if (p->next==p) {
L->next=NULL; } else
{q=p->next;
p->next=q->next; *e=q->data; free(q); }
return OK; }//ListDelete_L
3.主函数的伪码算法 int main(void) {
LNode *L;
cc=1; //CC用于判断是否刚开始报数,1:刚开始 2:已经有人离开队列 scanf(\scanf(\scanf(\
L=CreateLinkList(n);
if(L->next->next= =L->next) return OK;//空表 else {
for(j=1;j
{L=L->next; //从第s个人开始报数 }
while(L->next!=NULL) {
if (cc= =1) {
for(j=1;j
L=L->next; }
ListDelete_L(L,&e);//删除第m个 printf(e); //出队列的数打印
++cc; } else {
for(j=2;j<=m;j++)
/*有人离开队列后,报数为1的数向前移动了一位,因此,循环从2开始*/ { L=L->next;}
ListDelete_L(L,&e);//删数第m个 printf(e); //出队列的数打印 } }
return OK; } }
四、调试分析
1.由于对算法在C语言的实现不是很熟练,在编写程序的过程中犯了些语法错误,改正错误浪费了时间。
2.由于开始时对循环链表为空时的状态不大清楚,修改程序花费了较长时间。链表为空时应该为L->next=NULL。
3.本程序的模块划分比较合理,基本按照初步设计的算法进行实现。 4.在调试中遇到了一些新问题,改进了算法。 5.调试中遇到的问题
问题一:每次第m个出队之后从后一个开始重新计数。 解决:及时加入L=L->next; 调整指针。 问题二:有些操作的算法实现不能使用。 解决:把Status换为int或者*。 问题三: 第一次报数会多数一人。
解决:引入了cc,cc=1则为第一次报数。 6.算法的时间复杂度分析
函数ListDelete_L的时间复杂度均为O(1),函数CreateLinkList的时间复杂度为O(n),主函数的时间复杂度为O(n2),综合来看此算法的时间复杂度为O(n+ n2)=O(n2)。
五、用户使用说明
1.本系统的运行环境为Windows系统Visual C++ 6.0,执行文件为j.c。 2.运行程序后即显示
输入总人数n的值,按Enter确认。即显示下图:
输入开始计数的人的序号s的值,Enter确认后显示如下:
输入每次数多少个人,即m的值。按Enter后显示所求顺序。
六、测试结果
n、s、m的值分别为8、1、4时所得结果如下:
n、s、m的值分别为10、3、5时所得结果如下:
n、s、m的值分别为100、3、5时所得结果如下:
经过手算比较,程序运行正确。
六、附录
带注释的源程序为: #include
typedef int LElemType; typedef int Status; typedef struct LNode {
LElemType data; struct LNode *next; }LNode,*LinkList;
LNode *CreateLinkList(int n)//顺序建立链表,L为头结点 {
int i,x;
LNode *p; LNode *s; LNode *L;
L=(LNode*)malloc(sizeof(LNode)); p=(LNode*)malloc(sizeof(LNode)); L->next=p;//循环链表空表 p->next=L->next;//p为尾结点 p->data=1; x=1;
for(i=0;i<=n-2;i++) { x++;
s=(LNode*)malloc(sizeof(LNode)); s->data=x;//插入表尾 p->next=s; p=s;
// printf(\ }
p->next=L->next; return L; }
Status ListDelete_L(LNode *L,LElemType *e)
{//删除队列当前位置的元素q,并用e返回其值, LNode *p; LNode *q;
p=L;
if(!(p->next)) return ERROR; if (p->next==p) {
// printf(\ //printf(\ L->next=NULL; } else
{q=p->next;
p->next=q->next; *e=q->data; free(q); }
return OK;
}//ListDelete_L int main(void) {
int s,m,n; int j,e,cc; LNode *L; cc=1;
printf(\ scanf(\
printf(\ scanf(\ printf(\ scanf(\
L=CreateLinkList(n);
if(L->next->next= =L->next) return OK;//空表 else {
for(j=1;j
//从第s个人开始报数 }
while(L->next!=NULL) {
if (cc==1) //CC用于判断是否刚开始报数,1为刚开始 2为已经有人离开队列, {
for(j=1;j
L=L->next;
//printf(\ //用于调试,观察开始报数的顺序,正式运行时可以注释掉 }
ListDelete_L(L,&e);//删数第m个 printf(\ //出队列的数打印 ++cc; } else {
for(j=2;j<=m;j++) //有人离开队列后,报数为1的数向前移动了一位,因此,循环从2开始 {
L=L->next;
//printf(\ //用于调试,看开始报数的顺序,正式运行时可以注释掉 }
ListDelete_L(L,&e);//删数第m个
printf(\ //出队列的数打印 } }
return OK; }
getchar();//循环不自动结束 }
正在阅读:
数据结构与算法实验报告-约瑟夫环05-14
家风作文300字07-06
2019年山东省征地补偿标准新规定是什么11-24
上海市嘉定、宝山区2015年中考九年级语文二模试卷10-12
(全国各地80套)2013年最新中考语文试题分类汇编_语言基础知识7_句子排列与衔接 205-25
邵寨学区学业水平测试32号04-26
关于医院企划工作的方案07-12
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 约瑟夫
- 数据结构
- 算法
- 实验
- 报告
- 2017北师大新闻与传播考研参考书推荐指南
- 表面活性剂原理及应用 - 图文
- 高中化学专题2第一单元第2课时同分异构体学案苏教版选修5[精品教
- 基础天天练
- 钢质修补剂 MSDS
- 江苏省化学工业发展规划(2016-2020年)
- XX县公安局处置各类突发事件应急预案
- 马克思主义基本原理复习题
- 电脑提速最快
- 郭锡良古代汉语
- 围护结构方案 - 图文
- 申论社会热点原因与对策整理
- 基于单片机的温度控制风扇的设计
- 数学建模 - 人口模型与预测
- 采购管理方法73:对所采购的物料进行检验及接收 - 图文
- 汕尾电大2016年秋季16秋专科辅导课程表 - 图文
- Allegro16.5新增功能
- 法律是一种理性对话 - 兼论司法判例制度的合理性
- 书写环保倡议书教案
- 电气面试基础知识