课程设计(论文)任务书
信息 学 院 计算机 专 业 20##-- 2 班
一、课程设计(论文)题目 约瑟夫环程序设计
二、课程设计(论文)工作自2014 年12月29 日起至20##年1月10 日止。
三、课程设计(论文) 地点: 5-204
四、课程设计(论文)内容要求：
1．本课程设计的目的
1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结
构、存储结构和操作实现算法，以及它们在程序中的使用方法。
2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计
能力；使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设
计的基本能力。初步掌握软件开发过程的问题分析、系统设计、程序编码、测
试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
2．课程设计的任务及要求
1）基本要求：
1. 分析题目，查阅相关资料；
2. 算法设计、数据结构设计；
3. 编写代码并调试；
4. 完成课程设计报告。
2）创新要求：
在基本要求达到后，可进行创新设计。
3）课程设计论文编写要求
（1）要按照书稿的规格打印誊写论文
（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等
（3）课程设计论文装订按学校的统一要求完成
4）答辩与评分标准：
（1）完成问题的解决方法分析：20分；
（2）算法思想（流程）：20分；
（3）数据结构：20分；
（4）测试数据：20分
（5）回答问题：20分。
5）参考文献：
《C程序设计》（第二版） 谭浩强 著 清华大学出版社出版
《C++程序设计》 谭浩强 著 清华大学出版社出版
《数据结构》（C语言版） 严蔚敏、吴伟民 著 清华大学出版社出版
6）课程设计进度安排
内容 天数 地点
构思及收集资料 图书馆
编程与调试 实验室
答疑 老师办公室
学生签名：
20##年 12 月 29 日
课程设计(论文)评审意见
（1）完成问题分析（20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（2）算法思想 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（3）数据结构 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（4）测试数据 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（5）回答问题 （20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（6）格式规范性及考勤是否降等级：是（√）、否（ ）
评阅人： 赵海霞 职称：讲师
20##年1 月11 日
目录
一、综合软件设计目的................................... 4
二、综合软件设计内容................................... 4
1、课程设计的题目及简介....................................................... 4
2、设计说明............................................................................... 4
3、程序截图............................................................................... 5
4、程序清单............................................................................... 5
三、测试数据：............................................ 20
四、总结（写出心得和总结）...................... 21
五、参考文献............................................... 21
一、综合软件设计目的
熟练掌握循环链表的建立删除，对一些实际问题的解决。
解决一些特殊情况的漏洞。
二、综合软件设计内容
1、课程设计的题目及简介
约瑟夫环
问题描述：编号为1，2? n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。
基本要求：
1、利用单循环链表作为存储结构模拟此过程； 2、键盘输入总人数、初始报数上限值m及各人密码； 3、按照出列顺序输出各人的编号。
2、设计说明
通过对一些初始数据总人数N和初始报数上限m的输入并且对每个人的密码值输入，通过这些数据创建一个单循环链表。每个节点储存了每个人的密码值并且序号，已经下一个节点也的指针也就是下一个人的位置。通过遍历的次数达到报数的目的。出列后的人，就删除他所对应的节点，这样就又能进行下一次报数了。
3、程序截图
4、程序清单
#include"LinkList.h"
#define ERROR 0
#define OK 1
#define TRUE 1
#define FLASE 0
typedef int ElemType;
typedef int Status;
Status chulie(LinkList &L,int m);
Status menu(LinkList &L);
void main()
{
LinkList L;
while (1){ if (menu(L)) exit(1); };
}
/* 对界面的打印并且输入 */
Status menu(LinkList &L)
{
int n=0;
int m;
printf("\n************** 约瑟环 *********************");
printf("\n请输入总人数:");
scanf_s("%d", &n);
if (n <= 0) { printf("\n输入错误"); return ERROR; }
printf("\n请输入初始报数上限值m:");
scanf_s("%d",&m);
if (m<1) { printf("\n输入错误"); return ERROR; }
CreateXHList_shun(L,n);
if (n == 1) printf("\n出列顺序为：\t1");
else chulie(L,m);
char choose=NULL; //存放是否需要再来一次的y/n
printf("\n是否再来一次(y/n)");
scanf_s("%c", &choose);
while (1){
scanf_s("%c", &choose);
fflush(stdin);
if ((choose == 'y' || choose == 'Y' || choose == 'n' || choose == 'N'))
break;
else printf("\n输入错误请重新输入(y/n)");
}
// } while (!(choose == 'y' || choose == 'Y'||choose == 'n'||choose == 'N'));
if (choose == 'y' || choose == 'Y') return ERROR;
else return OK;
}
Status chulie(LinkList &L,int m) //对队伍出列的处理，
{
if (!ListPankong(L)) return ERROR; //若队伍为空或者未对线性链表初始化则退出
printf("\n出列顺序为：");
LinkList p = L; //先将头指针赋值给p
while (p != p->next) //当p的指针指向自己的时候退出循环
{
for (int ls = 0; ls < m-1; ls++)
{
p = p->next;
}
LinkList q = p->next;
printf("\t%d", q->x);
m = q->data;
if (q == L->next&&p == L)
{
LinkList ls = q;
while (ls->next != q)
{
ls = ls->next;
}
ls->next = q->next;
}
p->next = q->next;
free(q);
}
printf("\t%d", p->x); //由于p指向自己的时候就退出循环所以p节点的编号还未打印
return OK;
}
/*
此头文件写的是对线性链表的一些操作
*/
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
int x;
ElemType data; //存放数据
struct LNode *next; //用来指向下一节点，最后一个节点指向NULL
}LNode,*LinkList;
Status CreateList_ni(LinkList &L, int n);
Status CreateXHList_shun(LinkList &L, int n);
Status CreateList_shun(LinkList &L, int n);
Status ListInit(LinkList &L);
Status ListInsert(LinkList &L, int i, ElemType e);
Status ListDelete(LinkList &L, int i, ElemType &e);
Status ListPrintf(LinkList &L);
Status ListFind(LinkList &L, int &i, ElemType e);
Status ListLength(LinkList &L);
Status ListPankong(LinkList &L);
Status ListPaixv(LinkList &L);
Status ListNizhi(LinkList &L);
Status ListChuchong(LinkList &L);
void ListJiaoji(LinkList &LA, LinkList &LB);
void ListBingji(LinkList &LA, LinkList &LB);
void ListChaji(LinkList &LA, LinkList &LB);
/* 初始化线性链表给头结点开辟内存并给空值 */
Status ListInit(LinkList &L)
{
L = (LinkList)malloc(sizeof(LNode));
if (L == NULL)
{
printf("\n开辟头结点失败");
return ERROR;
}
L->next = NULL;
return OK;
}
/* 在线性链表中第i个元素前插入元素e 成功返回ok */
Status ListInsert(LinkList &L, int i,ElemType e) //
{
LinkList p;
int j = 0;
p = L;
while (p&&j < i - 1) { p = p->next; j++; }
if (!p || j>i - 1) return ERROR;
LinkList s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
/* 逆序创建输入长度为n的线性链表 */
Status CreateList_ni(LinkList &L, int n)
{
ListInit(L);
for (int ls = 1; ls <= n; ls++)
{
ElemType e;
printf("\n请输入第%d个元素:",ls);
scanf_s("%d",&e);
ListInsert(L,1,e);
}
return OK;
}
/* 顺序创建输入长度为n的线性链表 */
Status CreateList_shun(LinkList &L, int n)
{
ListInit(L);
LinkList q;
q = L;
for (int ls = 0; ls < n; ls++)
{
q->next = (LinkList)malloc(sizeof(LNode));
q = q->next;
// q->x = ls + 1;
// printf("\t*****%d",q->x);
printf("\n请输入第%d个元素:",ls+1);
scanf_s("%d",&q->data);
}
q->next = NULL;
return OK;
}
/* 顺序创建输入长度为n的循环线性链表 */
Status CreateXHList_shun(LinkList &L, int n)
{
ListInit(L);
LinkList q;
q = L;
for (int ls = 0; ls < n; ls++)
{
q->next = (LinkList)malloc(sizeof(LNode));
q = q->next;
q->x = ls+1;
printf("\n请输入第%d个人的密码:", ls + 1);
scanf_s("%d", &q->data);
}
q->next = L->next;
return OK;
}
/* 删除指定第i个节点并用e返回其值 */
Status ListDelete(LinkList &L, int i, ElemType &e)
{
if (!L){ printf("\n线性表未初始化"); return ERROR; }
LinkList p = L;
int j = 0;
while (p&&j < i - 1) { p = p->next; j++; };
if (!(p->next || j>i - 1)) return ERROR;
LinkList q = p->next;
e = q->data;
p->next = q->next;
free(q);
return OK;
}
/* 打印线性链表 */
Status ListPrintf(LinkList &L)
{
if (L) { printf("\n未初始化"); return ERROR; }
if (L->next == NULL) { printf("\n线性链表中无元素"); return ERROR; }
printf("\n线性链表全部元素为：");
LinkList p = L->next;
while (p)
{
if (p->data)
printf("\t%d",p->data);
p = p->next;
}
return OK;
}
/* 若线性链表为空则返回ERROR，否则通过对线性链表中遍历比对线性链表中是否有该元素，找到返回OK,没找到返回ERROR */
Status ListFind(LinkList &L, int &i, ElemType e) //查找元素e在线性链表中有没有
{
if (L->next == NULL){ printf("\n线性表为空"); return ERROR; }
LinkList p = L->next;
int num=1;
while (p)
{
if (p->data == e)
{
i = num;
return OK;
}
else
{
p = p->next;
num++;
}
}
return ERROR;
}
/* 返回当前线性链表的长度 */
Status ListLength(LinkList &L)
{
int num = 0;
LinkList p = L;
while (p->next!=NULL)
{
p = p->next;
num++;
}
return num;
}
/* 先对头结点进行判断是否初始化，再判断线性链表是否为空若为空返回FALSE不是空返回TRUE */
Status ListPankong(LinkList &L)
{
if (!L) { printf("\n线性表为初始化"); return ERROR; }
if (L->next == NULL){ printf("\n线性表为空"); return FALSE; }
else return TRUE;
}
/* 把线性链表中的元素都存到a这个数组里再对a数组进行排序后对线性链表重新存入值 */
Status ListPaixv(LinkList &L)
{
if (!L ) { printf("\n未初始化"); return ERROR; }
if (L->next==NULL){ printf("\n线性链表为空"); return ERROR; }
ElemType a[100];
int num = 0;
LinkList p = L->next;
while (p != NULL)
{
a[num++] = p->data;
p = p->next;
}
for (int i=0; i < num; i++)
for (int j = i; j < num; )
{
if (a[i] > a[j])
{
int ls = a[i];
a[i] = a[j];
a[j] = ls;
}
else
j++;
}
p = L->next;
for (int ls = 0; ls < num; ls++)
{
p->data = a[ls];
p = p->next;
}
return OK;
}
/* 把线性链表中的元素取出来存至数组中再逆序取出数组中的元素存入线性链表达到逆置的目的 */
Status ListNizhi(LinkList &L)
{
if (L->next == NULL){ printf("\n线性链表为空"); return ERROR; }
ElemType a[100];
int num = 0;
LinkList p = L->next;
while (p != NULL)
{
a[num++] = p->data;
p = p->next;
}
p = L->next;
while (num>0)
{
p->data = a[--num];
p = p->next;
}
return OK;
}
/* 对线性表进行除去重复元素的操作 */
Status ListChuchong(LinkList &L)
{
ElemType a[100];
int num = 0;
LinkList p = L->next;
if (p == NULL) return ERROR;
while (p != NULL)
{
a[num++] = p->data;
p = p->next;
}
for (int i = 0; i < num; i++)
for (int j = i + 1; j < num;)
{
if (a[i] == a[j])
{
for (int ls = i; ls < num-1; ls++)
{
a[ls] = a[ls + 1];
}
num--;
ElemType e;
ListDelete(L,i+1,e);
}
else j++;
}
p = L->next;
for (int ls = 0; ls < num;ls++)
{
p->data = a[ls];
p = p->next;
}
return OK;
}
/* 销毁线性链表 */
Status ListDestroy(LinkList &L)
{
if (L==NULL) return ERROR;
LinkList p = L->next;
LinkList q;
while (p)
{
q = p;
p = p->next;
free(q);
}
return OK;
}
/* 对LA和LB进行进行比对有相同的元素就存放在a这个数组里，并且最后将a中的元素都打印出来 */
void ListJiaoji(LinkList &LA, LinkList &LB)
{
ListChuchong(LA);
ListChuchong(LB);
int a[100];
int num = 0;
LinkList p = LA->next;
for (int ls = 0; ls < ListLength(LA); ls++)
{
int i;
if (ListFind(LB, i, p->data))
{
a[num++] = p->data;
}
p = p->next;
}
for (int ls = 0; ls < num; ls++)
{
printf("\t%d",a[ls]);
}
}
/* 对LA和LB求并集的操作 */
void ListBingji(LinkList &LA, LinkList &LB)
{
int a[100];
ListChuchong(LA);
LinkList p = LA;
int num = 0;
for (int ls = 0; ls < ListLength(LA); ls++)
{
p = p->next;
a[num++] = p->data;
}
p = LB;
for (int ls = 0; ls < ListLength(LB); ls++)
{
p = p->next;
int i;
if (!ListFind(LA, i, p->data))
{
a[num++] = p->data;
}
}
for (int ls = 0; ls < num; ls++)
{
printf("\t%d",a[ls]);
}
}
/* 对LA和LB球差集的操作 */
void ListChaji(LinkList &LA, LinkList &LB)
{
int a[100];
int num=0;
LinkList p=LA->next;
while (p!=NULL)
{
int i;
if (!ListFind(LB, i, p->data))
a[num++] = p->data;
p = p->next;
}
printf("\nLA减LB的差集为:");
for (int ls = 0; ls < num; ls++)
printf("\t%d",a[ls]);
num = 0;
p = LB->next;
while (p != NULL)
{
int i;
if (!ListFind(LA, i, p->data))
a[num++] = p->data;
p = p->next;
}
printf("\nLB减LA的差集为:");
for (int ls = 0; ls < num; ls++)
printf("\t%d", a[ls]);
}
三、测试数据：
输入总人数：3
输入初始报数上限m：2
输入第一个人密码为：1
输入第二个人密码为：2
输入第三个人密码为：3
则输出出列顺序为： 2 1 3
并且可以选择是否再来一次计算<y/n>
四、总结（写出心得和总结）
这次课设的制作过程中遇见了一些问题，主要就是以前只写过线性链表，没写过循环线性链表，所以在创建方面参考了一下网上的方法。最主要的问题困恼了我一个星期，就是之前创建好了线性链表后，要是开头就删除第一个节点也就是开始就第一个人出列的话，我不能把第一个节点的前驱的指针改掉。也是后面通过答疑给老师看，老师一分钟就把问题查找出来了，才让我完成了这次课设编写过程。让我知道有时候应该拿出草稿纸来把每一步的结果写出来就能发现出看不出的问题。让我知道得细心写程序才能把每个容易忽略的错误纠正过来。
五、参考文献
《C程序设计》（第二版） 谭浩强 著 清华大学出版社出版
《C++程序设计》 谭浩强 著 清华大学出版社出版
《数据结构》（C语言版） 严蔚敏、吴伟民 著 清华大学出版社出版