约瑟夫环课程设计

学号 **********

2011-2012学年 第二学期

《数据结构课程设计》

课程设计报告

题 目： 专 业： 班 级： * 名： * * * 师： 成 绩：

计算机与信息工程系

年 月 日

约瑟夫环设计与实现 计算机科学与技术 08(2)班 *** *** 数据结构课程设计报告

目 录

1.课程设计介绍…………………………………………………....3

1.1 课程设计容………………………………………………...............................3 1.2 课程设计要求…………………………………………………………….......3

2.课程设计原理与分析…………………………………………...4

2.1 课程题目粗略分析…………………………………………….......................4 2.2 原理图介绍…………………………………………………….......................4

3.数据结构分析...............................................................................8

3.1 单链表存储结构 3.2单链表算法描述

4. 调试与分析.................................................................................9

4.1.单链表调试过程

4.2单链表程序执行过程 4.3 运行时的界面显示

5.数组实现简单的约瑟夫环.........................................................11 6.参考文献....................................................................................13 7.课程设计体会与总结.................................................................13

附录：1单链表实现约瑟夫环源代码.........................................14 2 数组实现简单约瑟夫环源代码.....................................16

数据结构课程设计报告

1. 课程设计介绍

1.1 课程设计内容

编号为1，2···n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值1开始顺序报数，报到m时 m，从第一个人开始按顺时针方向自 停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向的下一个开始重新从1报数，如此下去，直至所有的人 全部出列为止，设计一个程序求出出列顺序。

1.2 课程设计要求

1.

2. 3. 4.

使用单循环链表作为储存结构，并模拟该过程; 使用数组作为存储结构，并模拟该过程

从键盘输入开始开始时的总人数、初始报数上限值m及每个人的密码； 按照出列顺序输出各人的编号。

数据结构课程设计报告

2. 课程设计原理与分析

2.1 课程题目粗略分析

2.1.1 单链表的实现分析

演示程序以用户和计算机的对话的方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应的数据（即每个人都所持的密码），每个人的序号由程序自动分配。

程序执行的命令包括： （1）构造链表； （2）输入数据；

（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；

（4）结束。

本程序包括三个模块：

（1）信息录入（构造链表）模块。此模块将对数据进行初始化，构造链表，并录入数据以便后续程序的使用。

（2）结果输出模块。此模块将根据前面所输入的数据对数据进行处理，输出报数号码，删除报数节点，并继续进行处理。

（3）主程序模块。此模块实现整个程序的进入和退出，及各种初始化处理。

2.2 原理图介绍

功能模块图为：

约瑟夫环主函数模块信息录入模块结果输出模块

数据流程图为：

数据结构课程设计报告

1．此部分为createlist函数。首先初始化变量，再输出提示性语句，等待用户输入数据，将总人数和初始上限值分别存入num和m。以num为上限值建立单循环链表，最后返回L。

begin声明变量t和指针p,q输出提示语句并录入总人数和初始上限值num和mt=1Nt<=numYp=(node*)malloc(sizeof(node));L==NULLYL=q=pq->next=p;t++Np->next=L;Return

2．此部分为printlist函数部分。定义变量temp=m，从第一个人开始进行报数，指针q和p指向第一个人L，当q->next=p时，q=q->next;否则当q->next!=q时—temp，直到—temp！=0时输出p所指向的节点的num；重复以上处理直到q->next!=q为假时结束该函数。

数据结构课程设计报告

beginint temp=m;Linklist *q,*p;q=p=Lq->next=pNq=q->nextNq->next!=qY--temp!=0Yq=p;p=p->nextprintf(\"%d \",p->num);Temp=p->mmq->next=p->nextNYFree(p);p=q->nextprintf(\"%d\\n\num)Return

3．此部分为主程序部分。分别调用函数createlist和printlist，所有人输出，程序结束。并通过while循环对程序进行重复使用。

数据结构课程设计报告

开始ints=1;s!=0Linklist *L=NULL;list(L);printf(\"继续？（1.yes or 0.no）\");输入s的值printf(\"谢谢使用!\\n\");结束

数据结构课程设计报告

3.数据结构分析

本课程设计分别利用单循环链表和数组作为模拟约瑟夫的存储结构 3.1 单链表的存储结构

根据要求首先应该建立一个单循环链表，实现链式存储。设置结构体存储节点：

用结构体存储全体人数整型变量num和每个人的密码整型变量mm，用以指示下一结点的指针next。结构体指针Linklist;。

struct node {

int mark;

int num;

struct node *next;

}；

typedef struct node Linklist；

设置结构体指针p和q及表头指针L。 3.2 算法描述

3.2 算法描述

1．将人数的编号和相应的密码输入到单循环链表中，应用creatlist函数，输入总人数和初始上限值。然后依次输入每个人的密码，循环n-1次。设置指针p=(Linklist*)malloc(sizeof(node))；如果头结点为空，将指针p=L=q；每人的号码编号赋值给指针p所指的人数p->num=i；q->next=p;然后将p所指的节点赋给q,q=p;依次循环，直到所有的节点都赋值完成。赋值完成后，p->next=L；构成单循环链表的要求。

数据结构课程设计报告

2．进行出圈的过程，所用的函数为Print函数。因为上限值为全局变量值，所以在Print函数中用一个变量temp代替。令temp=m; q->next=L;进行循环，条件为q->next!=q；因为为循环链表，所以判断最后指针是否指向自己，while(q->next!=q)。在这循环体中，令变量temp逐步减1，判断是否为一，while(temp--!=1)。循环体为q=p；p=p->next；当为1时，选中第一个出圈的人，并输出他的编号，printf(\"%d \；此时将他的编号赋值为新的上限值，temp=p->mark；q指向的下一结点为p所指向的下一节点，并进行删除节点操作free(p)；将q的下一节点再次赋值给p, p=q->next ；重复以上的操作，知道所有的人都输出。

3．主程序模块部分，全局变量总人数n和初始上限值m，设置单循环链表的表头L，分别引用函数createlist 和printlist，本程序结束。并通过while循环对程序进行重复使用。

4 调试与分析

4.1 调试过程

在调试程序是主要遇到一下几类问题：

1. 当输入此函数时出现了与&相关的错误，例如后面缺少括号以及分号等等以下的错误；

2. 输入每个人的密码值出现连贯相同数字时，程序有可能出现停止； 3. 在主程序中main() 前不加返回值变量类型，调试时出现逻辑错误； 4. 在定义结构体时，定义结构体指针变量为指针，程序运行时出现了定义的结构体指针不起作用。

4.2程序执行过程

输入总人数：7 输入上限值：3

输入第一个人的密码：1

数据结构课程设计报告

输入第二个人的密码：2 输入第三个人的密码：3 输入第四个人的密码：4 输入第五个人的密码：5 输入第六个人的密码：6 输入第七个人的密码：7 出列顺序是： 2 6 7 4 5 1 2

继续（1.yes or 0.no）？1 ********************* 输入总人数：5 输入上限值：4

输入第一个人的密码：1 输入第二个人的密码：2 输入第三个人的密码：3 输入第四个人的密码：4 输入第五个人的密码：5

出列顺序是： 4 3 2 1 5

继续（1.yes or 0.no）？0 ********************* 谢谢本次使用！

数据结构课程设计报告

4.3运行时的界面显示

5.数组实现简单约瑟夫环

1.使用数组实现约瑟夫环主要有四个函数协和完成，即：

class JosephusCircle

void JosephusCircle::input() void JosephusCircle::Josephus() void main()

2.其功能模块图为：

数据结构课程设计报告

约瑟夫环主函数模块信息录入模块结果输出模块

3.算法描述为：

1首先需要定义一个类函数，用于存放一些公共函数和所需的控制变量，○

控制变量包括约瑟夫圈人数，报数起始位置，首位置到末位置的循环控制，以及一个指针变量用于指向当前的人. 2构造一个函数 JosephusCircle○

用于输入 约瑟夫圈人数，报数起始位

置，所报个数，通过一个条件语句控制报数的个数不许为0！创建一个动态数组，舍弃数组的第一个，将有人的位置设置为1.

3构造一个函数JosephusCircle::Josephus()用于报数起点，剩余人数的○

判断，然后控制其出圈顺序，用一个while循环进行对错误位置的处理，其中包括对当前人是否为出圈的判断，若访问了出圈的人，则数组的下标加１，看下一个人，用一个循环判断是否出圈或者数组是不是应经到了尾部。然后输出出圈顺序，出圈则标为０，剩余人数减１. ４在主函数中调用功能函数. ○

4.数组实现约瑟夫环的调试

**程序在调试过程中可能出现一些常见的逻辑错误，例如符号问题,主函数前不加返回值类型。以及大括号的匹配问题。 **对程序的调试过程为： 依次输入：： 5 1 2

出圈顺序为： 2 4 1 5 3 依次输入：：6 3 3

出圈顺序为： 5 2 6 4 1 3

5.程序运行界面为：

数据结构课程设计报告

6.参考文献

[1] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007. [2] 张长海，陈娟.C程序设计[M].北京：高等教育出版社，2004. [3] 谭浩强,C程序设计[M].北京：清华大学出版社，2005.

[4] 王杰，数据结构经典算法实现与习题解答[M].北京：人民邮电大学出版社，2004年

[5] 张长海，陈 娟.C程序设计[M].北京:高等教育出版社，2004年

7.课程设计体会与总结

通过本次课程设计使我深刻的意识到了自身的不足，以及在设计过程中应该持有怎样的心态，也促进了我对C语言和数据结构进一步学习，获得了很多以前没有遇到的处理问题的经验。 本次课程设计我通过两个方面来实现有趣的约瑟夫环的问题，其中把用单循环链表作为重点设计，根据题目的要求，首先得到的是用单链表作为全体人数与每个人的密码的存储结构。设置结构体指针，并定义了两个指针类型的指针

数据结构课程设计报告

p与q；并编写了两个函数，链表构造函数和输出函数。 在约瑟夫环的设计中我也领悟到实现一种功能可以有各种不同的方法和数据结构，通过程序所依循的数据结构选择最优的设计方法。同时也深感到作为一个合格的程序员的话不仅要由严谨的逻辑能力和动手能力还有持久的耐心和毅力，以及在面对困难时应该具备的不畏困难的精神，这将激励我以后的学习和生活，此外也教会了我遇到自己解决不了的问题时要谦虚的向同学和老师请教，真正的做到“敏而好学，不耻下问”，此外，也感谢指导老师时老师的悉心教导！

附录：

1单链表实现约瑟夫环源代码

#include #include int m=0,num=0; struct node {

int mm; int num;

struct node *next; };

typedef struct node Linklist;

Linklist *createlist(Linklist *L) //根据人数创建链表 { int t;

Linklist *p,*q;

printf(\"请输入总人数 : \"); scanf(\"%d\

printf(\"请输入初始上限值 : \"); scanf(\"%d\ for(t=1;t<=num;t++) {

p=(node*)malloc(sizeof(node)); printf(\"请输入第%d个人的密码 : \ scanf(\"%d\ p->num=t; if(L==NULL) L=q=p; else { q->next=p; q=p;

数据结构课程设计报告

} }

p->next=L;

return L; }

void printlist(Linklist *L) {

int temp=m; Linklist *p,*q;

printf(\"出列顺序是: \\n\"); p=q=L;

while(q->next!=p) q=q->next; while(q->next!=q) { while(--temp) { q=p; p=p->next; } printf(\"%d \ temp=p->mm; q->next=p->next; free(p); p=q->next ; }

printf(\"%d\\n\ return; }

void main() {int s=1; while(s!=0){

Linklist *L=NULL; L=createlist(L); printlist(L);

printf(\"继续？（1.yes or 0.no）\"); scanf(\"%d\

printf(\"************************\\n\");}

数据结构课程设计报告

printf(\"谢谢本次使用!\\n\");

2 数组实现简单约瑟夫环源代码

#include using namespace std; class JosephusCircle {

public:

void input(); void Josephus(); private:

int n; int s; int m;

int *p; };

void JosephusCircle::input() {

cout<<\"请依次输入，约瑟夫圈人数、报数起始位置、报几个数：\"<>n>>s>>m;

if(m==0) { cout<<\"报数的个数不许为0！\"; cout<void JosephusCircle::Josephus() {

int i;

int j=s; int leave=n; int order; cout<<\"出圈顺序为：\";

while(leave!=0) { if(j>n) j=j%n; for(i=0;i数据结构课程设计报告

// cout<n) j=1; } if(j>n) { j=1; while(p[j]==0){ j++; if(j>n) j=1; } } } else { while(p[j]==0){ j++; if(j>n) j=1; } } } cout<<' '<void main() {

JosephusCircle Jose; Jose.input(); Jose.Josephus(); cout<