数据结构课程设计 约瑟夫环问题（报告+代码）

学院

计算机与信息工程系

数据结构课程设计

设计题目：约瑟夫环问题

专 业

班 级

学 号

姓 名

指导教师

2010年12月20日

约瑟夫环

一. 实验目的：本实验是设计一个可以解决约瑟夫环问题的程序。此程序要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。

二. 实验环境：VC2008.

三. 试验步骤：

1. 问题分析和任务定义

本实验要求设计一个程序解决约瑟夫环问题，且要利用单向循环链表存储结构模拟此过程。这就要求我们必须用链表结构而不能用像数组等其它结构。首先输入的数据必须是整型且是整数，同样输出的也必须是整型且整数；其次也要备好测试数据（包括合法的输入数据和非法形式输入的数据）以此来检查程序是否符合要求；最后

2. 数据类型和系统设计

链表存储结构的定义：

typedef struct Node

{

}SeqList

链表的建立：

SeqList * Creat(int num)

{

}

链表的输出：

void OutQueue(SeqList * tail, int num, int code)

{

}

3. 详细设计：

#include

#include

typedef struct Node

{

int num;

int code;

struct Node * next;

}SeqList;

SeqList * Creat(int);

void OutQueue(SeqList *, int , int );

int main()

{

int n,m,i;

printf( " 姓名：徐正杰 学号：090502201：\n");

printf("Input The Number of People, Frist Code:");

{

int num = 0,code = 0;

scanf("%d%d",&num, &code);

{

SeqList * tail = NULL;

tail=Creat(num);

OutQueue(tail, num, code);

}

}

return 0;

}

SeqList * Creat(int num)

{

getchar();

SeqList * tail = NULL;

tail=(SeqList *)malloc(sizeof(SeqList));

{

int i = 1, code = 0;

printf("Input Num.%d Code:", i);

scanf("%d", &code);

tail->num = i;

tail->code = code;

tail->next = tail;

{

SeqList * p = NULL;

for(i = 2; i <= num; ++i)

{

p = (SeqList *)malloc(sizeof(SeqList));

if(p)

{

printf("Input Num.%d Code:", i);

scanf("%d", &code);

p->num = i;

p->code = code;

p->next = tail->next;

tail->next = p;

tail = p;

}

else

{

perror("Out of menroy!");

getchar();

exit(1);

}

}

}

}

return(tail);

}

void OutQueue(SeqList * tail, int num, int code)

{

printf("Out of Queue:");

{

SeqList * p;

while(tail - tail->next)

{

code=(code-1)%num+1;

{

int i;

for(i = 1; i < code; ++i)

{tail = tail->next;}

}

p = tail->next;

printf("%d,", p->num);

tail->next = p->next;

code = p->code;

free(p);

p = NULL;

--num;

}

}

printf("%d.",tail->num);

free(tail);

tail = NULL;

}

4. 调试分析

在本次试验调试中很不顺利。一开始运行出现了很多错误与警告，通过一个个的检查和问同学纠正了部分语法错误像丢了分号和对出列位置判断不准确以及对于最后一个出列的人判断不准确等然而最后还是有很多问题不能解决。这时有个同学说可能是路径问题你试下重新打开结果还真可以。

5. 用户使用说明：

首先用户可以点击图标检查一下是否有错误，确认没错误后再单击图标运行程序。出现界面：

在frist code 后输入人的个数n和报数上限m在按enter键输入每个人的密码最后enter键即可。

6. 测试结果：

输入：7 6

3 1 7 2 4 8 4

输出：6 1 4 7 2 3 5

四．实验总结：

通过本次实验，我学会了对单向循环链表的应用，同时，我学会了对链表的定义、建立以及输出和对链表循环的认识。实验之中，我遇到了很多问题，通过不断地问自己、同学和老师最后都一一得到了解决，这让我深深认识到，没有程序一开始就是百分百正确，我们必须细心检查耐心解决。最后我感到我们平常课堂上所学的知识仅仅是一些皮毛，而我们所要掌握的更深更难。这要求我以后必须认真学习并且需要通过课外扩展来提高自己，只有这样才能顺应时代的发展和对人才的需求。

.

本文来源：https://www.2haoxitong.net/k/doc/037ac1c34028915f804dc247.html