数据结构课程设计之约瑟夫问题

设计题目：3.3“银行排队系统”的设计与实现P44 ........................................................... 错误！未定义书签。

一、设计要求 . ................................................................................................................................. 错误！未定义书签。

1．问题描述 . ........................................................................................................................... 错误！未定义书签。 2．需求分析 . ........................................................................................................................... 错误！未定义书签。二、概要设计 . ................................................................................................................................. 错误！未定义书签。

3．系统功能设计 .................................................................................................................... 错误！未定义书签。三、模块设计 . ................................................................................................................................. 错误！未定义书签。

1．模块设计 . ........................................................................................................................... 错误！未定义书签。 2．系统子程序及功能设计 .................................................................................................... 错误！未定义书签。 3．函数主要调用关系图 ...................................................................................................... 错误！未定义书签。 1．数据类型定义 .................................................................................................................... 错误！未定义书签。 2．系统主要子程序详细设计 ................................................................................................ 错误！未定义书签。五、测试分析 . ................................................................................................................................. 错误！未定义书签。六、用户手册 . ................................................................................................................................. 错误！未定义书签。七、调试报告 . ................................................................................................................................. 错误！未定义书签。八、程序清单 . ................................................................................................................................. 错误！未定义书签。设计题目：6.4.1二叉排序树基本操作的实现盘P134 ............................................................... 错误！未定义书签。

一、设计要求 . ................................................................................................................................. 错误！未定义书签。

1．问题描述 . ........................................................................................................................... 错误！未定义书签。 2．需求分析 . ......................................................................................................................... 错误！未定义书签。二、概要设计 . ................................................................................................................................. 错误！未定义书签。

1．主界面设计 . ....................................................................................................................... 错误！未定义书签。 2．存储结构设计 .................................................................................................................. 错误！未定义书签。 3．系统功能设计 .................................................................................................................. 错误！未定义书签。三、模块设计 . ............................................................................................................................... 错误！未定义书签。

1．数据类型定义 .................................................................................................................... 错误！未定义书签。 2．系统主要子程序详细设计 .............................................................................................. 错误！未定义书签。

五、测试分析 . ......................................................................................................................................... 错误！未定义书签。六、用户手册 . ....................................................................................................................................... 错误！未定义书签。七、调试报告 . ....................................................................................................................................... 错误！未定义书签。八、程序清单 . ......................................................................................................................................... 错误！未定义书签。设计题目：2.4.2约瑟夫问题P34 ................................................................................................. 错误！未定义书签。一、设计要求 . ........................................................................................................................................................................... 2

1．问题描述 . ..................................................................................................................................................................... 2 2．需求分析 . ................................................................................................................................................................... 2 二、概要设计 . ........................................................................................................................................................................... 2

1．主界面设计 . ................................................................................................................................................................. 2

2．存储结构设计 .................................................................................................................................................... 2 3．系统功能设计 .................................................................................................................................................... 3 三、模块设计 . ................................................................................................................................................................... 3

1．模块设计 . ............................................................................................................................................................. 3

第 1 页共 12 页

2．系统子程序及功能设计 .................................................................................................................................... 3 3．函数主要调用关系图 ........................................................................................................................................ 3 四、详细设计 . ................................................................................................................................................................... 3

1．数据类型定义 ...................................................................................................................................................... 3 2．系统主要子程序详细设计 ................................................................................................................................ 4 （1）主函数模块设计 ...................................................................................................................................................... 4 五、测试分析 . ................................................................................................................................................................. 7 六、用户手册 . ................................................................................................................................................................... 8 七、调试报告 . ................................................................................................................................................................... 8 八、程序清单 . ................................................................................................................................................................... 8

设计题目：2.4.2约瑟夫问题P34 一、设计要求 1．问题描述

约瑟夫问题时：编号为1，2，，，，n 的n 个人按顺时针方向围坐一圈，每人持有一个密码。一开始人性一个正整数作为报数上限值m, 从第一个人开始顺时针方向自1开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

2．需求分析

输入形式：两个整数n 和m ；输出形式：在一行中输出n 个整数；程序功能：能够输出n 个人的出列编号；例如：输入20 7；输出6,1,4,7,2,3,5

二、概要设计 1．主界面设计

约瑟夫问题界面设计并复杂，根据提示输入数，运行结果如下：

图3-1 主界面

2．存储结构设计

本系统采用循环链表的存储结构， struct Node//循环节点的定义

第 2 页共 12 页

{

int number; Node *next; };

//编号

//尾指针

3．系统功能设计

本系统分为两部分；1用户指定上限值；2读取每人的密码。

三、模块设计 1．模块设计

图3-2 模块调用示意图

2．系统子程序及功能设计

本系统中5个函数，包括主函数。各函数功能如下：

（1）

Node *CreateList(Node *L,int &n,int &m);//建立约瑟夫环函数（2）void Joseph(Node *L,int n,int m);//输出每次出列号数函数（3）Node *DeleteList(Node **L,int i,Node *q);//寻找每次出列人的号数（4）int LengthList(Node *L);//计算环上所有人数函数

3．函数主要调用关系图

图3-3 系统函数调用关系图

四、详细设计 1．数据类型定义

(1)循环节点的定义

第 3 页共 12 页

struct Node {

int number; Node *next;

};

(2)全局变量定义 int n, m;

2．系统主要子程序详细设计

（1）主函数模块设计 void main()

{ Node *L; L=NULL;

int n, m;

cout>n;

if(n

else {

cout>m;

if(m

L=CreateList(L,n,m); Joseph(L,n,m); } }

system("pause");

//循环节点的定义

//编号

//尾结点

//主函数

//初始化尾指针

//环的长度

//人数异常处理

//号数异常处理

//重新给尾指针赋值第 4 页共 12 页

(2)建立一个约瑟夫环（尾插法） Node *CreateList(Node *L,int &n,int &m) { Node *q;

for(int i=1;inumber=i; p->next=NULL; if(i==1) L=q=p;

//工作指针的初始化

//建立一个约瑟夫环（尾插法）

else {

q->next=p; q=q->next; } }

q->next=L;

if(L!=NULL){return(L);}

//返回尾指针 //尾指针异常处理

else cout

(3)输出每次出列的人

void Joseph(Node *L,int n,int m) { int k;

cout>k;

//输出每次出列的人

if(kn){cout

第 5 页共 12 页

cout

for(int i=1;i

Node *q = new Node;

if(i==1) q=DeleteList(&L,k+m-1,q); else q=DeleteList(&L,m,q);

coutnumber

(4)寻找每次出列的人

Node *DeleteList(Node **L,int i,Node *q) {

if(i==1) i+=LengthList(*L); Node *p; p=*L; int j=0;

while(jnext;j++;} q = p->next;

p->next=p->next->next; *L = p->next; return(q); }

(5)计算环上的人数 int LengthList(Node *L) {

if(L){cout

//第一个出列人的号数

//释放出列人的存储空间

//寻找每次出列的人

//顺序依次出列情况的处理方式

//计算环上的人数

//异常处理

第 6 页共 12 页

{ int i=1;

Node *p=L->next; while(p!=L) { i++; p=p->next; } return(i); } }

五、测试分析

1, 在主菜单下按照提示输入数字，如下，输入的数字如下所示

图3-4 输入界面

2，按下enter 键可得到以下结果

第 7 页共 12 页

图3-4 输出界面

六、用户手册

用户只需在主界面上输入初始值为20，m=7,7个人的密码输入3，1，7，2，4，8，4.

七、调试报告

在调试过程中遇到了很多问题，在这些问题中有逻辑错误也有语法错误，我是先通过调试检查代码找出其中的语法错误然后通过设置断点找到逻辑错误。实在找不到就请教大神帮忙！嘿嘿！！！用到的循环链表有关的知识，虽然中间有很多的失败，但通过思考和讨论，最终测试成功。

八、程序清单

#include using namespace std; struct Node {

int number; Node *next; };

Node *CreateList(Node *L,int &n,int &m); void Joseph(Node *L,int n,int m);

//建立约瑟夫环函数 //输出每次出列号数函数 //寻找每次出列人的号数 //计算环上所有人数函数

//编号

//循环节点的定义

Node *DeleteList(Node **L,int i,Node *q); int LengthList(Node *L);

第 8 页共 12 页

void main() { Node *L; L=NULL; int n, m;

cout>n;

if(n

else {

cout>m;

if(m

L=CreateList(L,n,m);

Joseph(L,n,m); } }

system("pause"); }

Node *CreateList(Node *L,int &n,int &m) { Node *q;

for(int i=1;inumber=i; p->next=NULL;

//主函数

//初始化尾指针

//环的长度

//人数异常处理

//号数异常处理

//重新给尾指针赋值

//建立一个约瑟夫环（尾插法）第 9 页共 12 页

if(i==1) L=q=p; else {

q->next=p; q=q->next; } }

q->next=L;

if(L!=NULL){return(L);}

else cout

}

void Joseph(Node *L,int n,int m) { int k;

cout>k;

if(kn){cout

cout

Node *q = new Node;

if(i==1) q=DeleteList(&L,k+m-1,q); else q=DeleteList(&L,m,q);

coutnumber

第 10 页共 12 页//工作指针的初始化

//返回尾指针 //尾指针异常处理

//输出每次出列的人

//第一个出列人的号数

//释放出列人的存储空间 //输出最后出列人的号数

}

Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人 {

if(i==1) i+=LengthList(*L);

Node *p;

p=*L;

int j=0;

while(jnext;j++;}

q = p->next;

p->next=p->next->next;

*L = p->next;

return(q);

}

int LengthList(Node *L)

{

if(L){cout

else

{

int i=1;

Node *p=L->next;

while(p!=L)

{

i++;

p=p->next;

}

return(i);

}

第 11 页共 12 页 //顺序依次出列情况的处理方式 //计算环上的人数 //异常处理

第 12 页共 12 页

设计题目：3.3“银行排队系统”的设计与实现P44 ........................................................... 错误！未定义书签。

一、设计要求 . ................................................................................................................................. 错误！未定义书签。

1．问题描述 . ........................................................................................................................... 错误！未定义书签。 2．需求分析 . ......................................................................................................................... 错误！未定义书签。二、概要设计 . ................................................................................................................................. 错误！未定义书签。

1．主界面设计 . ................................................................................................................................................................. 2

1．模块设计 . ............................................................................................................................................................. 3

第 1 页共 12 页

设计题目：2.4.2约瑟夫问题P34 一、设计要求 1．问题描述

2．需求分析

输入形式：两个整数n 和m ；输出形式：在一行中输出n 个整数；程序功能：能够输出n 个人的出列编号；例如：输入20 7；输出6,1,4,7,2,3,5

二、概要设计 1．主界面设计

约瑟夫问题界面设计并复杂，根据提示输入数，运行结果如下：

图3-1 主界面

2．存储结构设计

本系统采用循环链表的存储结构， struct Node//循环节点的定义

第 2 页共 12 页

{

int number; Node *next; };

//编号

//尾指针

3．系统功能设计

本系统分为两部分；1用户指定上限值；2读取每人的密码。

三、模块设计 1．模块设计

图3-2 模块调用示意图

2．系统子程序及功能设计

本系统中5个函数，包括主函数。各函数功能如下：

（1）

3．函数主要调用关系图

图3-3 系统函数调用关系图

四、详细设计 1．数据类型定义

(1)循环节点的定义

第 3 页共 12 页

struct Node {

int number; Node *next;

};

(2)全局变量定义 int n, m;

2．系统主要子程序详细设计

（1）主函数模块设计 void main()

{ Node *L; L=NULL;

int n, m;

cout>n;

if(n

else {

cout>m;

if(m

L=CreateList(L,n,m); Joseph(L,n,m); } }

system("pause");

//循环节点的定义

//编号

//尾结点

//主函数

//初始化尾指针

//环的长度

//人数异常处理

//号数异常处理

//重新给尾指针赋值第 4 页共 12 页

(2)建立一个约瑟夫环（尾插法） Node *CreateList(Node *L,int &n,int &m) { Node *q;

for(int i=1;inumber=i; p->next=NULL; if(i==1) L=q=p;

//工作指针的初始化

//建立一个约瑟夫环（尾插法）

else {

q->next=p; q=q->next; } }

q->next=L;

if(L!=NULL){return(L);}

//返回尾指针 //尾指针异常处理

else cout

(3)输出每次出列的人

void Joseph(Node *L,int n,int m) { int k;

cout>k;

//输出每次出列的人

if(kn){cout

第 5 页共 12 页

cout

for(int i=1;i

Node *q = new Node;

if(i==1) q=DeleteList(&L,k+m-1,q); else q=DeleteList(&L,m,q);

coutnumber

(4)寻找每次出列的人

Node *DeleteList(Node **L,int i,Node *q) {

if(i==1) i+=LengthList(*L); Node *p; p=*L; int j=0;

while(jnext;j++;} q = p->next;

p->next=p->next->next; *L = p->next; return(q); }

(5)计算环上的人数 int LengthList(Node *L) {

if(L){cout

//第一个出列人的号数

//释放出列人的存储空间

//寻找每次出列的人

//顺序依次出列情况的处理方式

//计算环上的人数

//异常处理

第 6 页共 12 页

{ int i=1;

Node *p=L->next; while(p!=L) { i++; p=p->next; } return(i); } }

五、测试分析

1, 在主菜单下按照提示输入数字，如下，输入的数字如下所示

图3-4 输入界面

2，按下enter 键可得到以下结果

第 7 页共 12 页

图3-4 输出界面

六、用户手册

用户只需在主界面上输入初始值为20，m=7,7个人的密码输入3，1，7，2，4，8，4.

七、调试报告

八、程序清单

#include using namespace std; struct Node {

int number; Node *next; };

Node *CreateList(Node *L,int &n,int &m); void Joseph(Node *L,int n,int m);

//建立约瑟夫环函数 //输出每次出列号数函数 //寻找每次出列人的号数 //计算环上所有人数函数

//编号

//循环节点的定义

Node *DeleteList(Node **L,int i,Node *q); int LengthList(Node *L);

第 8 页共 12 页

void main() { Node *L; L=NULL; int n, m;

cout>n;

if(n

else {

cout>m;

if(m

L=CreateList(L,n,m);

Joseph(L,n,m); } }

system("pause"); }

Node *CreateList(Node *L,int &n,int &m) { Node *q;

for(int i=1;inumber=i; p->next=NULL;

//主函数

//初始化尾指针

//环的长度

//人数异常处理

//号数异常处理

//重新给尾指针赋值

//建立一个约瑟夫环（尾插法）第 9 页共 12 页

if(i==1) L=q=p; else {

q->next=p; q=q->next; } }

q->next=L;

if(L!=NULL){return(L);}

else cout

}

void Joseph(Node *L,int n,int m) { int k;

cout>k;

if(kn){cout

cout

Node *q = new Node;

if(i==1) q=DeleteList(&L,k+m-1,q); else q=DeleteList(&L,m,q);

coutnumber

第 10 页共 12 页//工作指针的初始化

//返回尾指针 //尾指针异常处理

//输出每次出列的人

//第一个出列人的号数

//释放出列人的存储空间 //输出最后出列人的号数

}

Node *DeleteList(Node **L,int i,Node *q) //寻找每次出列的人 {

if(i==1) i+=LengthList(*L);

Node *p;

p=*L;

int j=0;

while(jnext;j++;}

q = p->next;

p->next=p->next->next;

*L = p->next;

return(q);

}

int LengthList(Node *L)

{

if(L){cout

else

{

int i=1;

Node *p=L->next;

while(p!=L)

{

i++;

p=p->next;

}

return(i);

}

第 11 页共 12 页 //顺序依次出列情况的处理方式 //计算环上的人数 //异常处理

第 12 页共 12 页

数据结构课程设计之约瑟夫问题

相关文章