![数据结构课程设计报告约瑟夫环完整版[1]](https://img.doczj.com/imgf1/0795x60j4m77jxuk1k2j-11.webp)
![数据结构课程设计报告约瑟夫环完整版[1]](https://img.doczj.com/imgf1/0795x60j4m77jxuk1k2j-c2.webp)
*******************
实践教学
*******************
兰州理工大学
软件职业技术学院
2011年春季学期
算法与数据结构课程设计
题目：约瑟夫环
专业班级：
姓名：
学号：
指导教师：
成绩：
摘要
约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。
经过分析，我们使用MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。
关键词：单循环链表；c语言；约瑟夫环；
序言
数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。
本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。
通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
目录
摘要 (1)
序言 (2)
目录 (3)
正文 (4)
一、问题描述 (4)
二、逻辑设计 (5)
三、详细设计 (7)
四、程序代码 (13)
五、程序调试与测试 (13)
设计总结 (18)
参考文献 (19)
致谢 (20)
附录 (21)
正文
一、问题描述
约瑟夫环问题描述的是：设编号为1，2，…，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。如下图分析：
二、逻辑设计
1、循环链表抽象数据类型定义
typedef struct LNode//定义单循环链表中节点的结构 { int num;//编号 int pwd;//password
struct LNode *next;//指向下一结点的指针
}LNode;
2、本程序包含一下几个模块 （1）构造结点模块
LNode *createNode(int m_num,int m_pwd)
图2 约瑟夫环原理演示图
{
LNode *p;
p=(LNode *)malloc(sizeof(LNode));//生成一个结点
p->num=m_num;//把实参赋给相应的数据域
p->pwd=m_pwd;
p->next=NULL;//指针域为空
return p;
}
（2）创建链表模块
void createList(LNode *ppHead,int n)
（3）出队处理模块
void jose(LNode *ppHead,int m_pwd)
（4）约瑟夫环说明输出模块
void instruction()
（5）菜单模块
void menu()
（6）主函数模块
int main（）
函数的调用关系图如下：
三、详细设计
1.主函数
图4 主函数数据流程图
根据流程图，主函数程序如下：
int main()
{
int n,m,x;
LNode *ppHead=NULL;
menu();
for(;;){
printf("\n请选择要执行的操作：");
scanf("%d",&x);
system("cls");
switch(x){
case 1:
printf("*************************************************************** *\n");
printf("约瑟夫环:\n");
printf(" 编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n");
printf("码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n");
printf("按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码\n");
printf("m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n");
printf("直到所有人全部出列为止.编程打印出列顺序.\n");
printf("*************************************************************** *\n");
main();
break;
case 2:
printf("\n请输入总人数n：");
scanf("%d",&n);
printf("请输入开始上限数m：");
scanf("%d",&m);
createList(&ppHead,n);
printf("\n");
printf("出队顺序：\n");
jose(ppHead,m);
printf("\n约瑟夫环游戏结束!\n");
main();
break;
case 0:
exit(0);
default:
system("cls");
printf("\n您选择的操作有误，请重新选择...\n\n\n");
main();
}
}
return 0;
}
2.链表的创建
图5 创建链表函数的数据流程图
/*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为"空"的节点，再把P插入循环链表ppHead中*/
根据流程图，创建链表函数程序如下：
void createList(LNode **ppHead,int n)
{
int i,m_pwd;
LNode *p,*cur;//cur:浮标指针
for(i=1;i<=n;i++)
{
printf("输入第%d个人的密码：",i);
scanf("%d",&m_pwd);//输入持有密码
p=createNode(i,m_pwd);//调用构造结点函数
if(*ppHead==NULL)//如果头结点为空
{
*ppHead=cur=p;//生成头结点，让cur指向他
cur->next=*ppHead;//cur的指针域指向自身
}
else//如果不为空，则插入结点
{
p->next = cur->next;
cur->next = p;
cur= p;//cur指向新插入结点
}
}
printf("完成创建！\n"); //提示链表创建完成
}
3.出队处理
图6 出队函数的数据流程图
/*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，
ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/
根据流程图，出队函数程序如下：
void jose(LNode *ppHead,int m_pwd)
{
int i,j;
LNode *p,*p_del;//定义指针变量
for(i=1;p!=ppHead;i++){
for(j=1;j p=ppHead;//p赋值为ppHead，p指向要删除结点的前一个结点 ppHead=ppHead->next;//ppHead指向下一个元素 } p->next = ppHead->next;//p结点与头结点链接 i=ppHead->pwd;//i赋值为ppHead->pwd j=ppHead->num;//j赋值为ppHead->num，j为要删除的密码值 printf("第%d个人出列，密码：%d\n",j,i); m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd free(ppHead);//释放头结点 ppHead=p->next;//ppHead重新赋值给p->next,即释放前的ppHead->pwd 指针//删除报数结点 } i=ppHead->pwd;//i赋值为ppHead->pwd j=ppHead->num;//j赋值为ppHead->num printf("最后一个出列是%d号，密码是:%d\n",j,i); free(ppHead);//释放头结点 } 4. 约瑟夫环说明模块 void instruction() { printf("*************************************************************** *\n"); printf("约瑟夫环:\n"); printf(" 编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n"); printf("码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n"); printf("按顺时针方向自1开始顺序报数,报到时停止.报m的人出列，将他的密码\n"); printf("m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n"); printf("直到所有人全部出列为止.编程打印出列顺序.\n"); printf("******************************************************\n"); return 0; } 5. 菜单模块 void menu(){ printf("**************************约瑟夫环*****************************\n"); printf(" \n"); printf(" [1]约瑟夫环问题的阐述\n"); printf(" [2]按要求求解约瑟夫环\n"); printf(" [0]退出\n"); printf("************************** 欢迎使用！****************************\n"); } 四、程序代码 见附录源程序。 五、程序调试与测试 1. 调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现两次错误，加入子函数的声明后错误消失。 2 . 刚开始时曾忽略了一些变量参数的标识"&"和“*”，使调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。 3. 本次课程设计采用数据抽象的程序设计方法，将程序划分为三个层次结构：元素节点、单向循环链表，主控制模块。思路较为清晰，实现调用顺利。经过本次实验，使我对数据结构这门课程有了进一步的了解，每一个程序经过需求分析、概要设计、详细设计之后，思路即清晰呈现，程序也很快就出来了，最后经过调试、运行又有新的体验。 <测试用例> 这是一个使用循环链表的经典问题。本程序开始运行界面如下： 选择1进入约瑟夫环问题阐述。 图7 约瑟夫环开始运行界面 图8 约瑟夫环问题阐述 ①选择2，输入下列数据测试： 请输入总人数n：7 请输入开始上限数m：20； 请依次输入每个人的密码：3 1 7 2 4 8 4 6 1 4 7 2 3 5 出队顺序： 图9 约瑟夫环测试1 ②继续选择2，输入下列数据测试： 请输入总人数n：5 请输入开始上限数m：30 请依次输入每个人的密码：3 4 5 6 7 出队顺序：5 3 1 2 4 ③继续选择2，输入下列数据测试： 请输入总人数n ：8 请输入开始上限数m ：14 请依次输入每个人的密码：3 4 5 6 7 8 9 10 出队顺序：6 7 2 8 3 5 1 4 图10 约瑟夫环测试2 图11 约瑟夫环测试3 测试完成，选择0退出。 设计总结 我的这次数据结构课程设计的题目是:《约瑟夫环》,通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构，尤其是对单循环链表上基本运算的实现,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。 通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。 在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。 两周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织起来进行学习，总而言之这两周中我学到很多，受益匪浅。 参考文献 1．严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社. 2．严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社. 3．《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）. 4．谭浩强.《c语言程序设计》. 清华大学出版社. 沈阳大学 2.3 MASM的介绍 MASM是微软公司开发的汇编开发环境，拥有可视化的开发界面，使开发人员不必再使用DOS环境进行汇编的开发，编译速度快，支持80x86汇编以及Win32Asm是Windows下开发汇编的利器。它与windows平台的磨合程度非常好，但是在其他平台上就有所限制，使用MASM的开发人员必须在windows下进行开发，历经二三十年的发展，目前MASM的版本已升至6.15，支持MMX Pentium、Pentium II、Pentium III及Pentium 4等指令系统。 2.4总体设计功能 本次课程设计的内容是采用汇编语言设计一个运行于计算机的“霓虹灯”的模拟显示 程序，由$及*字符相间，从两侧向中间螺旋汇聚直至形成一个矩形，这就要求该霓虹灯能够动态地进行变化；霓虹灯模拟显示程序主要是进行程序循环调用，可以通过CMP、JMP、JZ、RET等命令进行跳转。由于是霓虹灯的模拟显示，因此在进行程序循环调用前需要进行数据段定义，以使子程序在进行调用时能够根据数据段的定义来执行，最后显示结果。 定时器中断处理程序：计数器中断的次数记录在计数单元count中，由于定时中断的引发速率是每秒18.2次，即计数一次为55ms，当count计数值为18时，sec计数单元加一（为1秒）。 视频显示程序设计：一般由DOS 或BIOS调用来完成。有关显示输出的DOS功能调用不多，而BIOS调用的功能很强，主要包括设置显示方式、光标大小和位置、设置调色板号、显示字符、显示图形等。用INT 10H中断即可建立某种显示方式。用DOS功能调用显示技术，把系统功能调用号送至AH，把程序段规定的入口参数，送至指定的寄存器，然后由中断指令INT 21H来实现调用。 键盘扫描程序设计：利用DOS系统功能调用的01号功能，接受从键盘输入的字符到AL寄存器，以及检测键盘状态，有无输入，并检测输入各值。 2.5详细功能设计 2.5.1主程序功能 主程序通过调用各个子程序来实现清屏，改变图形等功能，具体调用过程如图1所示。 沈阳大学 《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日 目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列 3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果： 《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月 三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均 以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。 三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后 各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。 目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6) 一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能： （结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 （基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现） 模块一： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX ) 汇编语言课程实验报告 实验名称 课程设计1 实验环境 硬件平台：Intel Core i5-3210M 操作系统：DOSBox in Windows 软件工具：Turbo C , Debug, MASM 实验内容 《 将实验7中的Power idea公司的数据按照下图所示的格式在屏幕上显示出来。 实验步骤 1.要完成这个实验，首先我们需要编写三个子程序。第一个子程序是可以显示字符串到屏 幕的程序，其汇编代码如下： ;名称：show_str ;功能：在屏幕的指定位置，用指定颜色，显示一个用0结尾的字符串 ;参数：（dh）=行号，（dl）=列号（取值范围0～80），（cl）=颜色，ds：si：该字符串的首地址 ;返回：显示在屏幕上 ￥ show_str: push ax push cx push dx push es push si push di mov ax,0b800h - mov es,ax mov al,160 mul dh add dl,dl mov dh,0 add ax,dx mov di,ax mov ah,cl . show_str_x: mov cl,ds:[si] mov ch,0 jcxz show_str_f mov al,cl mov es:[di],ax inc si inc di 【 inc di jmp show_str_x show_str_f: pop di pop si pop es pop dx pop cx } pop ax ret 2.第二个程序是将word型数据转换为字符串，这样我们才能调用第一个程序将其打印出 《数据结构与算法》课程设计报告 学号： 班级序号： 姓名： 指导教师： 成绩： 中国地质大学信息工程学院地理信息系统系 2011年12 月 1．需求规格说明 【问题描述】 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。 【基本要求】 一个完整的系统应具有以下功能： （1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。 （2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。 （3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。 （4）程序使用命令行方式运行 压缩命令：SZip A Test.Haf 1.doc 解压缩命令：SZip X Test.Haf 2.doc或SZip X Test.Haf 用户输入的命令不正确时，给出提示。 （5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。 2．总体分析与设计 （1）设计思想： 1、压缩准备：1> 读文件，逐个读取字符，统计频率 2> 建立哈夫曼树 3> 获得哈弗曼编码 2、压缩过程： 1> 建立一个新文件，将储存权值和字符的对象数组取存储在文件头 一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={ 燕山大学 汇编语言课程设计说明书 题目：计算机钢琴程序 交通灯控制系统 学院（系）：信息科学与工程学院 年级专业： 10级计算机科学2班 学号： 100104010113 学生姓名：马强 学号： 100104010116 学生姓名：夏洋 指导教师：何海涛、邹晓红 完成日期： 2013年7月3日 目录 1.课程设计的目的和意义........................................................................................................... - 2 - 1.1课程设计目的................................................................................................................ - 2 - 1.2课程设计的意义............................................................................................................ - 2 - 2.题目一：计算机钢琴程序....................................................................................................... - 2 - 2.1系统的主要功能............................................................................................................ - 2 - 2.2总体设计方案................................................................................................................ - 2 - 2.2.1扬声器驱动方式................................................................................................. - 2 - 2.2.2延时原理............................................................................................................. - 3 - 2.2.3键盘控制发声程序............................................................................................. - 4 - 2.2.4设计总结............................................................................................................. - 5 - 2.3作品使用说明................................................................................................................ - 6 - 3.题目二：交通灯控制系统....................................................................................................... - 6 - 3.1系统的主要功能............................................................................................................ - 6 - 3.2 系统工作原理............................................................................................................... - 6 - 3.2.1 8259的工作原理................................................................................................ - 6 - 3.2.2 8255A的工作原理：...................................................................................... - 7 - 3.2.3 8253的工作原理：............................................................................................ - 7 - 3.3总体设计方案................................................................................................................ - 7 - 3.3.1程序流程图......................................................................................................... - 8 - 3.3.2接口电路图....................................................................................................... - 11 - 3.4交通灯的设计总结...................................................................................................... - 11 - 4.课程设计心得体会................................................................................................................. - 12 - 5.参考文献................................................................................................................................. - 12 - 6.附录：程序代码..................................................................................................................... - 12 - 6.1计算机钢琴程序代码.................................................................................................. - 12 - 6.2交通灯控制系统代码.................................................................................................. - 14 - 线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 课程设计报告 课程名称：数据结构课程设计课程设计题目：约瑟夫环问题 姓名：余明旭 系：计算机科学与技术专业：计算机科学与技术年级：2010级 学号：100310236 指导教师：陈老师 职称：学生 一、需求分析 1、输入的形式和输入值的范围： 本程序中，输入报数上限值n，初始报数者s，初始报数者携带的密码m1，n-2个人携带的密码m（最后一人携带的密码没用），均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。 2、输出的形式： 从屏幕显示出列顺序。 3、程序所能够达到的功能： 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4、测试数据： 输入 8 1 4 4 4 4 4 4 4 输出 4 8 5 2 1 3 7 6 一、详细设计 以单向循环链表实现该结构： 1、抽象数据类型的定义为： struct LNode { ElemType data; LNode* next; }; 2、本程序包含以下模块： 主程序模块： Void main() { 初始化； 输入数据； 执行功能； 显示结果； } 各功能模块：实现单链表的各项功能。 Void fun() { } 3、各模块的调用关系： 三、调试分析 程序的编写和调试基本正常，遇到的问题主要是：指针的指向的边界问题，如何每次正确找到出列的人的位置。 解决方法： for(int j=1;j 编号 课程设计 题目 1、一元稀疏多项式计算器 2、模拟浏览器操作程序 3、背包问题的求解 4、八皇后问题 二级学院计算机科学与工程学院 专业计算机科学与技术 班级 2011级 37-3班 学生姓名 XX 学号 XXXXXXXXXX 指导教师 XXXXX 评阅教师 时间 1、一元稀疏多项式计算器 【实验内容】 一元稀疏多项式计算器。 【问题描述】 设计一个一元稀疏多项式简单计算器。 【需求分析】 其基本功能包括： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列为：n,c1,e1,c2,e2,……,cn,en,其中n 是多项式的项数，ci，ei分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相减，建立多项a+b； （4）多项式a和b相减，建立多项式a-b； （5）计算多项式在x处的值； （6）计算器的仿真界面（选做）； 【概要设计】 -=ADT=- { void input(Jd *ha,Jd *hb)； void sort(dnode *h) dnode *operate(dnode *a,dnode *b) float qiuzhi(int x,dnode *h) f",sum); printf("\n"); } 【运行结果及分析】 （1）输入多项式： （2）输出多项式（多项式格式为：c1x^e1+c2x^e2+…+cnx^en）： （3）实现多项式a和b相加： （4）实现多项式a和b相减： （5）计算多项式在x处的值： 2、模拟浏览器操作程序 【实验内容】 模拟浏览器操作程序 【问题描述】 标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是：使用两个栈，追踪可以后退和前进而能够到达的网页。在本题中，要求模拟实现这一功能。 【需求分析】 需要支持以下指令： BACK：将当前页推到“前进栈”的顶部。取出“后退栈”中顶端的页面，使它成为当前页。若“后退栈”是空的，忽略该命令。 FORWARD：将当前页推到“后退栈”的顶部。取出“前进栈”中顶部的页面，使它成为当前页。如果“前进栈”是空的，忽略该命令。 VISIT 《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期： 一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n-- 四、源程序代码 //Joseph问题求解算法的设计与实现 #include 计算机与信息工程学院《汇编语言》课程设计四则运算器的设计 专业：计算机科学与技术 班级：控制11-2班 姓名: 倪天天 学号：2011025745 指导教师：郝维来 2013年6月28日 摘要 计算器是最简单的计算工具，简单计算器具有加、减、乘、除四项运算功能。想要用汇编语言实现简单的计算器，就必须通过对数据存储，寄存器的使用，加减乘除相关指令以及模块的调用等汇编语言知识进行运用，以实现一个基本功能完善，界面友好，操作简便易行的计算器。用汇编语言实现简单计算器还涉及到输入输出模块的设计，加减乘除运算的判断以及退出程序的判断的设计。通过对各种指令的合理使用，设计各个功能模块。当实现各个程序模块后，通过程序的调用最终实现一个简单的计算器。 关键词：计算器，汇编语言，四则运算，功能模块 Abstract Calculator is the easiest calculation tools, a simple calculator with addition, subtraction, multiplication, division four arithmetic functions. Want to use assembly language to achieve a simple calculator, you must pass on the data storage, register usage, addition, subtraction, and related instructions such as assembly language module calls the use of knowledge in order to achieve a basic functional, user-friendly, easy to operate easy calculator. Using assembly language to achieve a simple calculator also involves the design of input and output modules, the judgment of arithmetic operations and exit the program to judge design. Through the rational use of various commands, design various functional modules. When implementing various program modules, through a call to the ultimate realization of the program a simple calculator. Keyword:Calculator, assembly language, four arithmetic, functional modules #include L->next = p; L = p; } L->next = q->next; free(q); } void PrintList(int x,int n,LinkList L) //输出出列顺序 { LinkList p,q; p = L; for(int i = 1;i <= n;i++) { for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf("%d ",q->number); p->next = q->next; free(q); } } int main() { printf("=============约瑟夫环==============\n\n\n"); int n,x; LinkList L; L = NULL; InitList(L); //构造空链表 printf("输入初始密码："); scanf("%d",&x); //初始密码为x printf("\n"); printf("输入参与总人数："); scanf("%d",&n); //总共的人数n printf("\n"); CreateList(n,L); //建立好一个约瑟夫环printf("\n\n\n===================================\n\n"); printf("出列编号为："); PrintList(x,n,L); //输出出列顺序 printf("\n\n"); return 0; } 数据结构课程设计 设计说明书 TSP 问题 起止日期：2016 年 6 月27 日至2016 年7 月 1 日 学生姓名 班级 学号 成绩 指导教师( 签字) 2016 年7 月 1 日 目录 第1 章需求分析.................................................................................1... 1.1 简介 (1) 1.2 系统的开发背景 (1) 1.3 研究现状 (1) 第2 章概要设计.................................................................................2... 2.1 系统开发环境和技术介绍 (2) 2.2 系统需求分析 (2) 2.2.1 总体功能分析 (2) 2.2.2 核心功能分析 (3) 第3 章详细设计...................................................................................4... 3.1 系统开发流程 (4) 3.2 系统模块设计 (4) 3.3 系统结构 (6) 3.2 系统流程图 (6) 第4 章调试分析...................................................................................7... 4.1 程序逻辑调试 (7) 4.2 系统界面调试 (8) 第5 章测试结果...................................................................................9... 5.1 测试环境 (9) 5.2 输入输出测试项目 (9) 5.3 测试结果 (10) 结论.....................................................................................................1..1.. 参考文献................................................................................................1..1. 附录.......................................................................................................1..2.. 农林大学金山学院 课程设计报告 课程名称：汇编语言课程设计 课程设计题目：动画设计“我爱大自然”姓名： 系：信息与机电工程系 专业：电子信息工程 年级：2008级 学号：082230066 指导教师：\ 职称：助教 2009～2010学年第二学期 目录 1 课程设计的目的 (2) 2 课程设计的要求 (2) 3课程设计报告容 (2) 3.1设计思路 (2) 3.2程序流程图 (2) 3.3设计源程序 (5) 3.4动画示意图 (19) 4 总结 (20) 5参考文献 (20) 6评分标准 (21) 动画设计“我爱大自然” 一、课程设计的目的 《汇编语言课程设计》是电子信息工程专业集中实践性环节之一，是学习完《汇编语言》课程后进行的一次全面的综合练习。其目的是： 培养学生熟练掌握汇编语言指令系统，深化和巩固指令系统和编程方法，提高学生的编程应用能力。为将来从事专业工作打下基础，培养良好的职业道德和严谨的工作作风。 二、课程设计的要求 1)具备初步的独立分析和解决问题的能力； 2)初步掌握问题分析、系统设计、程序编码、测试等基本方法和技能； 3)提高综合运用所学的理论知识和方法的能力； 4)训练用系统的观点和软件开发一般规进行软件开发，培养科学的工作方法和作风； 5)设计的题目要求达到一定工作量，并具有一定的深度和难度； 6)编写出课程设计说明书。 三、课程设计报告容 （一）设计思路 “我爱大自然”这个程序中包含了比较多的景物，既有静态的也有动态的，其中还有一段音乐。为了节省存储空间，提高程序设计的效率和质量，使程序简洁、清晰，便于阅读，同时也为了便于修改和扩充，采用子程序设计技术和宏定义，根据程序要实现的若干主要功能及个功能块要调用的公共部分，将程序划分为若干个相对独立的模块，为每个模块编制独立的程序段，最后将这些子程序根据调用关系连成一个整体。 这样，整个程序就被分为几个子程序的有机统一。根据BIOS中断调用原理，设置80×25彩色文本显示方式，分别编写一个子程序显示“I LOVE NATURE,LET US GO AIRING”和一个子程序在屏幕上“画”树。这两个子程序所体现出来的事物都是的。为了实现小鸟汇编语言课程设计
约瑟夫环课程设计实验报告
数据结构课程设计报告模板
汇编语言-课程设计1
数据结构课程设计报告
约瑟夫环实验报告
汇编课程设计
约瑟夫问题算法及数据结构课程设计报告
数据结构课程设计报告模板
课程设计(约瑟夫环)[1]
数据结构课程设计报告
数据结构实验报告(约瑟夫环)
(新)汇编语言课程设计四则运算
数据结构课程设计——约瑟夫环报告(含代码)
数据结构课程设计报告
汇编语言课程设计报告
相关主题
文本预览