目录
目录 1
任务书…………………………………………………………………………………….2
正 文 4
一、 数据结构定义 4
1. 抽象数据类型 4
2. 存储结构定义 4
3. 基本操作 5
二、 解题过程 7
1. 问题分解 7
2. 模块结构 7
3. 解题思路 8
三、 实现 9
四、 实验结果 13
1. 实验数据 13
2. 实验结果 13
五、 实验小结 16
1. 数据结构使用小结 16
2. 需完善之处 17
课程设计体会 19
参考文献 20
课程设计(论文)任务书
软件 学院 软件工程 专业 2012 - 3 班
一、课程设计(论文)题目 数据结构课程设计
二、课程设计(论文)工作自2013 年12月24日起至2013 年12月26 日止。
三、课程设计(论文) 地点:软件工程实训中心308
四、课程设计(论文)内容要求：
1．本课程设计的目的
（1）使学生熟练掌握抽象数据类型的组织和定义；
（2）使学生熟练掌握数据类型的定义和实现；
（3）培养学生组织和分析数据的能力；
（4）培养学生分析和应用基于不同数据结构的算法的能力；
（5）提高学生的科技论文写作能力。
2．基本要求：
每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计：
R 约瑟夫环：参见《数据结构题集》P179。
□ 赫夫曼编/译码器：参见《数据结构题集》P149。
□ 教学计划编制问题：参见《数据结构题集》P150。
3．课程设计论文编写要求
（1）要按照书稿的规格打印誊写课设报告；
（2）报告分为封面、任务书（本文档）、正文、
课程设计体会和参考文献四部分；
学生签名：
年 月 日
课程设计(论文)评审意见
（1）题目分析 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（2）流程分析 （30分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（3）数据定义 （30分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（4）代码编写 （10分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（5）创新能力 （10分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（6）格式规范性、设计态度及考勤是否降等级：是（ ）、否（ ）
评阅人： 职称：讲师
20##年1月6日
正 文
一、 数据结构定义
1. 抽象数据类型
本设计中用到的数据结构ADT定义如下：
ADT Node{
数据对象：D={id,key|id∈Node,key∈Node,id>=0;key>=0}
数据关系：R={<id,key>|id,key∈D, id>=0;key>=0}
基本操作：
CreatList(&pHead,k)
操作结果：构造单循环链表
PrintList(pHead)
初始条件：链表已存在
操作结果：打印输出链表数据元素
Joesph(&pHead,m)
初始条件：链表已存在，m为出列者所在编号
操作结果：删除出队编号所在结点，并将该结点的key作为新的key，从该结点的下一结点移动
} ADT Node
2. 存储结构定义
数据存储结构的C语言定义如下：
typedef struct Node{ //带头结点的单循环链表
int id; //编号
int key; //密码
struct Node *next;
}Node,*CircularList;
3. 基本操作
数据结构的基本操作实现如下：
1、 构造单循环链表函数：
void CreatList(CircularList *ppHead,const int k){
int i,ikey;
Node *pNew,*pCur;
for(i=1;i<=k;i++){
printf("请输入第%d个人所持有的密码：",i);
scanf("%d",&ikey);
pNew=(Node *)malloc(sizeof(Node));
pNew->id=i;
pNew->key=ikey;
pNew->next=NULL;
if(*ppHead==NULL){
*ppHead=pCur=pNew;
pCur->next=*ppHead;
}
else{
pNew->next=pCur->next;
pCur->next=pNew;
pCur=pNew;
}
}
printf("约瑟夫环已建成，可以开始进入报数游戏！\n");
}
2、 输出单循环链表函数：
void PrintList(const Node *pHead){
const Node *pCur=pHead;
if(!pHead) printf("单循环链表是空的！\n");
do{
printf("第%d个人所持有的密码是：%d\n",pCur->id,pCur->key);
pCur=pCur->next;
}while(pCur!=pHead);
}
3、约瑟夫环规则删除结点并输出结点信息函数：
void Joesph(CircularList *ppHead,int ikey){
int iCount,iFlag=1;
Node *pPrv,*pCur,*pDel;
pPrv=pCur=*ppHead;//将pPrv初始为指向尾结点，为删除做好准备
while(iFlag){
for(iCount=1;iCount<=ikey;iCount++){//移动iCount-1趟指针
pPrv=pCur;
pCur=pCur->next;
}
if(pPrv==pCur) iFlag=0;//最后一结点
pDel=pCur; //删除pCur指向的结点
pPrv->next=pCur->next;
pCur=pCur->next;
printf("第%d个人出列，所持密码为:%d\n",pDel->id,pDel->key);
ikey=pDel->key-1;
free(pDel);
}
ppHead=NULL;
}
二、 解题过程
1. 问题分解
该问题主要应实现以下功能：建立约瑟夫环并解约瑟夫环，直到所有玩家出列，并顺序输出出列编号。它主要解决约瑟夫环问题。
2. 模块结构
系统主要由 5个模块组成，分别是：
（1）、构造链表模块
void CreatList(CircularList *ppHead,const int k)
（2）、输出链表模块
void PrintList(const Node *pHead)
（3）、约瑟夫环函数模块
void Joesph(CircularList *ppHead,int ikey)
（4）、菜单模块
void menu()
（5）、主函数模块
int main(int argc,char *argv[])
![圆角矩形: 主函数模块
int main(int argc,char *argv[])](https://upload2.fanwen118.com/wk001/4085670/4085670_img_003.png)
模块之间的结构如下：
3. 解题思路
各模块的实现步骤为
（1）、创建单循环链表函数模块：用一个for循环来给链表的每一个结点分配空间，输入每个人所持有的密码key，并创建结点。然后用头插法建立一个带结点的单循环链表。
（2）、输出单循环链表模块：先判断表是否为空，若不空则输出结点信息，同时指针向后移，指向下一结点，继续输出直到指针再次指向头结点为止，输出完毕。
（3）、约瑟夫环函数模块：建立一个iFlag标签，值为1执行循环语句，值为0跳出循环。While循环语句里的for循环实现报数功能，设指针pPrv和指针pCur，移动结点到ikey,再删除第ikey个结点并把该结点的key值赋给ikey，再从该结点的下一个结点开始移动，重复上述过程，直到结点全部出列。结束while循环。
（4）、菜单模块：用简单的printf设计出具有一定美观的菜单界面，使得程序所要实现的功能一目了然，又可以供操作者自主选择。
（5）主函数模块：设置标签iflag，供用户选择输入数字操作。若为1则开始或继续约瑟夫环游戏；若为0，退出游戏。游戏开始后，首先得设置参与者人数n以及初始报数上限m，调用CreatList()创建约瑟夫环，然后调用PrintList()输出当前已输入的信息以确认信息无误，再调用Joesph()函数解决约瑟夫环问题。结束后再用iflag标志位判断是否继续。
三、 实现
代码及注释：
//#include"consts.h"
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{ //带头结点的单循环链表
int id; //编号
int key; //密码
struct Node *next;
}Node,*CircularList;
void CreatList(CircularList *ppHead,const int k){ //构建单循环链表
int i,ikey;
Node *pNew,*pCur;
for(i=1;i<=k;i++){
printf("请输入第%d个人所持有的密码：",i);
scanf("%d",&ikey);
pNew=(Node *)malloc(sizeof(Node));
pNew->id=i;
pNew->key=ikey;
pNew->next=NULL;
if(*ppHead==NULL){
*ppHead=pCur=pNew;
pCur->next=*ppHead;
}
else{
pNew->next=pCur->next;
pCur->next=pNew;
pCur=pNew;
}
}
printf("约瑟夫环已建成，可以开始进入报数游戏！\n");
}
void PrintList(const Node *pHead){ //输出单循环链表
const Node *pCur=pHead;
if(!pHead) printf("单循环链表是空的！\n");
do{
printf("第%d个人所持有的密码是：%d\n",pCur->id,pCur->key);
pCur=pCur->next;
}while(pCur!=pHead);
}
void Joesph(CircularList *ppHead,int ikey){ //约瑟夫环规则删除结点并输出结点信息
int iCount,iFlag=1;
Node *pPrv,*pCur,*pDel;
pPrv=pCur=*ppHead;//将pPrv初始为指向尾结点，为删除做好准备
while(iFlag){
for(iCount=1;iCount<=ikey;iCount++){//移动iCount-1趟指针
pPrv=pCur;
pCur=pCur->next;
}
if(pPrv==pCur) iFlag=0;//最后一结点
pDel=pCur; //删除pCur指向的结点
pPrv->next=pCur->next;
pCur=pCur->next;
printf("第%d个人出列，所持密码为:%d\n",pDel->id,pDel->key);
ikey=pDel->key-1;
free(pDel);
}
ppHead=NULL;
}
void menu(){
printf("******************************约瑟夫环问题*************************************\n\n");
printf(" 1、约瑟夫环报数游戏(继续游戏)\n");
printf(" 0、退出游戏\n");
printf("\n*****************************请输入数字选择************************************\n");
}
int main(int argc,char *argv[]){
int n,m;
int iflag=1;
menu();
scanf("%d",&iflag);
while(iflag){
CircularList pHead=NULL;
printf("请输入总人数n:");
scanf("%d",&n);
printf("请输入初始报数上限m:");
scanf("%d",&m);
CreatList(&pHead,n);
printf("\n----------------参与游戏者的个人信息如下:\n");
PrintList(pHead);
printf("\n----------------按照出列顺序输出游戏者的编号:\n");
Joesph(&pHead,m-1);
printf("\n本回游戏结束！\n");
printf("\n\n是否继续游戏?(请输入数字选择)\n");
scanf("%d",&iflag);
}
}
四、 实验结果
1. 实验数据
① 输入数字1，输入下列数据测试：
请输入总人数n:7
请输入初始报数上限m:20
然后依次输入每个人的密码：3 1 7 2 4 8 4
② 继续输入数字1继续游戏，输入下列数据测试：
请输入总人数n:5
请输入初始报数上限m:30
然后依次输入每个人的密码：3 4 5 6 7
③ 输入数字0，结束程序。
2. 实验结果
图1为主界面
图2
输入数字1，输入下列数据测试：
请输入总人数n:7
请输入初始报数上限m:20
然后依次输入每个人的密码：3 1 7 2 4 8 4
出列顺序为：6 1 4 7 2 3 5
图3
继续输入数字1继续游戏，输入下列数据测试：
请输入总人数n:5
请输入初始报数上限m:30
然后依次输入每个人的密码：3 4 5 6 7
出列顺序为：5 3 1 2 4
图4
输入0，选择退出。
五、 实验小结
1. 数据结构使用小结
本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
2. 需完善之处
由于本程序主要解决的事约瑟夫环问题，并且程序的功能设计的比较单一，代码本身也并不复杂。
课程设计体会
通过此次课程设计，让我对单循环链表的使用加深了印象，了解到单循环链表的构造，删除操作，以及指针的移动等。此次约瑟夫环问题用的是单循环链表存储结构解决的。虽然约瑟夫环问题的原理不难理解，甚至刚看到这个问题时，让我想起了以前学习C语言时的队列问题，不过那个只是按某一个数字为周期,然后在一个循环队列中进行游戏，按一定的次序报数，谁报到该数则出列，最后输出所有出列编号的次序。而约瑟夫环又感觉到在这种简单问题上深化了点，毕竟它选的key会变化，出列后，从下一元素开始报数。所以解决这个问题时使用单循环链表存储结构具有一定的简化性，利用此存储结构的优点，使用指针进行结点移动，在实现删除这一功能时单链表具有很大的化简性。也让我觉得要对数据进行操作，必须选择好一种比较合适的存储结构，了解该存储结构才能对具体的操作有更好的了解，也可以快速又准确写出它的代码。很多东西都是很重要的，而今后也要对软件方面的代码算法有所领悟才行。
参考文献
1．严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社
2．严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社
3．滕国文《数据结构课程设计》.清华大学出版社