说明书 Microsoft Word 文档

摘要

约瑟夫环问题是典型的线性表的应用实例，猴子吃桃问题是递归的应用实例，稀疏矩阵是对三元组的主要运用，它们的开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。 经过分析，我们使用 MICROSOFT公司的Microsoft Visual C++6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。

关键词：c语言；约瑟夫环；递归；三元组；

序言

数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。

本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。

猴子吃桃问题是采用数组数据结构、链式数据结构。分别利用递归算法、链式存储、数组来实现函数功能。将所有模块放在一起，利用主函数中的菜单来调用不同子函数以实现题目要求。

稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出;完成稀疏矩阵的转置操作；完成对两个具有相同行列数的稀疏矩阵进行求和操作；对前一矩

阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。

通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

目录

摘要 ............................................................................................................. 1 序言 ............................................................................................................. 2 目录 ............................................................................................................. 3 正文 ............................................................................................................. 5 一、约瑟夫问题描述 .......................................................................... 5 1.逻辑设计 ....................................................................................... 5 2.详细设计 ....................................................................................... 6 3.程序代码 ..................................................................................... 12 4.程序调试与测试 .................................................................................................. 12 二、猴子吃桃问题描述 ...................................................................... 5 1.逻辑设计 ....................................................................................... 5 2.详细设计 ....................................................................................... 6 3.程序代码 .................................................................................................................. 12 4.程序调试与测试 .................................................................................................. 12 三、稀疏矩阵问题描述 ...................................................................... 5 1.逻辑设计 ....................................................................................... 5 2.详细设计 ....................................................................................... 6 3.程序代码 ..................................................................................... 12 4.程序调试与测试 .................................................................................................. 12 设计总结 .................................................................. 错误！未定义书签。

参考文献 .................................................................. 错误！未定义书签。 致谢 .......................................................................... 错误！未定义书签。 附录 .......................................................................... 错误！未定义书签。

正文

一．约瑟夫问题描述

约瑟夫环问题描述的是：设编号为1，2，…，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。

1．逻辑设计

1、循环链表抽象数据类型定义

typedef struct LNode//定义单循环链表中节点的结构 {

int num;//编号 int pwd;//password

struct LNode *next;//指向下一结点的指针

}LNode;

2、本程序包含一下几个模块 （1）构造结点模块

LNode *createNode(int m_num,int m_pwd) {

LNode *p;

p=(LNode *)malloc(sizeof(LNode));//生成一个结点 p->num=m_num;//把实参赋给相应的数据域 p->pwd=m_pwd;

p->next=NULL;//指针域为空 return p;

}

（2）创建链表模块

void createList(LNode *ppHead,int n) （3）出队处理模块

void jose(LNode *ppHead,int m_pwd) （4）约瑟夫环说明输出模块

void instruction() （5）菜单模块

void menu() （6）主函数模块

int main（）

函数的调用关系图如下：

Case 1：一个简单的输出函数，用于说明约瑟夫环； void instruction() 主函数调用函数； main() 菜单函数； void menu() Case 2:建立的约瑟夫环,并输出已建立的约瑟夫环： createList(LNode **ppHead,int n) 输出该约瑟夫环的每个人的出列顺序: jose(LNode *ppHead,int m_pwd) Case 0:default : 输入0，退出 exit(0)； 图1 约瑟夫环函数调用关系图

2．详细设计

1. 主函数

Main()开始 选择要执行的操作 Menu()功能菜单 功能1：约瑟夫环说明 功能2：按要求求解约瑟夫环 功能3：退出系统 输入总人数n 输入开始上线数：m 输入每个玩家的密码 调用：createList(&ppHead,n); jose(ppHead,m);函数求解所需的密码序列 程序运行完，自动返回到功能菜单 图2主函数数据流程图

根据流程图，主函数程序如下：

int main() {

int n,m,x;

LNode *ppHead=NULL; menu(); for(;;){

printf(\"\\n请选择要执行的操作：\"); scanf(\"%d\ system(\"cls\"); switch(x){ case 1:

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

printf(\"约瑟夫环:\\n\");

printf(\" 编号为1,2,3,4„,n的n个人按顺时针方向围坐一圈,每人持有一个密\\n\");

printf(\"码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\\n\");

printf(\"按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码\\n\");

printf(\"m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\\n\");

printf(\"直到所有人全部出列为止.编程打印出列顺序.\\n\"); printf(\"****************************************************************\\n\");

main(); break; case 2:

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

printf(\"请输入开始上限数m：\"); scanf(\"%d\ createList(&ppHead,n); printf(\"\\n\"); printf(\"出队顺序：\\n\"); jose(ppHead,m);

printf(\"\\n约瑟夫环游戏结束!\\n\"); main(); break; case 0: exit(0); default: system(\"cls\"); printf(\"\\n您选择的操作有误，请重新选择...\\n\\n\\n\"); main(); } }

return 0; }

2. 链表的创建

Main()函数 createList（）; 创建储存玩家密码的循环单链表的方法 从主函数中获取玩家信息n 如果n>0 是 否 退出 创建循环单链表，储存各个玩家密码 创建链表完成返回主函数main() 图3 创建链表函数的数据流程图

/*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为\"空\"的节点，再把P插入循环链表ppHead中*/ 根据流程图，创建链表函数程序如下：

void createList(LNode **ppHead,int n) {

int i,m_pwd;

LNode *p,*cur;//cur:浮标指针 for(i=1;i<=n;i++) { printf(\"输入第%d个人的密码：\ scanf(\"%d\输入持有密码 p=createNode(i,m_pwd);//调用构造结点函数 if(*ppHead==NULL)//如果头结点为空 { *ppHead=cur=p;//生成头结点，让cur指向他

}

cur->next=*ppHead;//cur的指针域指向自身 } else//如果不为空，则插入结点 { p->next = cur->next; cur->next = p; cur= p;//cur指向新插入结点 } }

printf(\"完成创建！\\n\"); //提示链表创建完成

3. 出队处理

Main()函数 jose()；出队函数 出队处理的方法 从循环链表中按初始密码依次扫描，找出对应的玩家序列 输出其持有的密码i=ppHead->pwd; j=ppHead->num; 移动浮标指针 m_pwd=ppHead->pwd; 输出密码后，删除相应的结点，并释放所占的储存空间free(ppHead); ppHead=p->next; 执行完后返回主函数 图4 出队函数的数据流程图

/*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，

ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/

根据流程图，出队函数程序如下：

void jose(LNode *ppHead,int m_pwd) {

int i,j;

LNode *p,*p_del;//定义指针变量 for(i=1;p!=ppHead;i++){ for(j=1;jnext;//ppHead指向下一个元素 } p->next = ppHead->next;//p结点与头结点链接 i=ppHead->pwd;//i赋值为ppHead->pwd

j=ppHead->num;//j赋值为ppHead->num，j为要删除的密码值 printf(\"第%d个人出列，密码：%d\\n\ m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd free(ppHead);//释放头结点 ppHead=p->next;//ppHead重新赋值给p->next,即释放前的ppHead->pwd指针//删除报数结点 }

i=ppHead->pwd;//i赋值为ppHead->pwd j=ppHead->num;//j赋值为ppHead->num

printf(\"最后一个出列是%d号，密码是:%d\\n\ free(ppHead);//释放头结点 }

4. 约瑟夫环说明模块

void instruction() {

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

printf(\"约瑟夫环:\\n\");

printf(\" 编号为1,2,3,4„,n的n个人按顺时针方向围坐一圈,每人持有一个密\\n\");

printf(\"码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\\n\");

printf(\"按顺时针方向自1开始顺序报数,报到时停止.报m的人出列，将他的密码\\n\");

printf(\"m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\\n\");

printf(\"直到所有人全部出列为止.编程打印出列顺序.\\n\");

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

return 0; }

5. 菜单模块

void menu(){

printf(\"**************************约瑟夫环 *****************************\\n\");

printf(\" \\n\");

printf(\" [1]约瑟夫环问题的阐述 \\n\");

printf(\" [2]按要求求解约瑟夫环 \\n\");

printf(\" [0]退出 \\n\");

printf(\"************************** 欢迎使用！ ****************************\\n\");

}

3．程序代码

见附录源程序。

4．程序调试与测试

1. 调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现两次错误，加入子函数的声明后错误消失。

2 . 刚开始时曾忽略了一些变量参数的标识\"&\"和“*”，使调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。

3. 本次课程设计采用数据抽象的程序设计方法，将程序划分为三个层次结构：元素节点、单向循环链表，主控制模块。思路较为清晰，实现调用顺利。 经过本次实验，使我对数据结构这门课程有了进一步的了解，每一个程序经过需求分析、概要设计、详细设计之后，思路即清晰呈现，程序也很快就出来了，最后经过调试、运行又有新的体验。

<测试用例>

这是一个使用循环链表的经典问题。本程序开始运行界面如下：

图5 约瑟夫环开始运行界面

选择1进入约瑟夫环问题阐述。

图6 约瑟夫环问题阐述

①选择2，输入下列数据测试： 请输入总人数n：7 请输入开始上限数m：20；

请依次输入每个人的密码：3 1 7 2 4 8 4 出队顺序：6 1 4 7 2 3 5

图7 约瑟夫环测试1

②继续选择2，输入下列数据测试： 请输入总人数n：5 请输入开始上限数m：30

请依次输入每个人的密码：3 4 5 6 7 出队顺序：5 3 1 2 4

图8 约瑟夫环测试2

③继续选择2，输入下列数据测试： 请输入总人数n：8 请输入开始上限数m：14

请依次输入每个人的密码：3 4 5 6 7 8 9 10 出队顺序：6 7 2 8 3 5 1 4

图9 约瑟夫环测试3

测试完成，选择0退出。

一．猴子吃桃问题描述

有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。

1．逻辑设计

本程序包含一下几个模块 （1） 递归模块

int recursion(int N){ if(N==10)

return 1; //跳出循环

}

else

return N=2*recursion(N+1)+2; //递归调用计算

（2） 数组模块

void Array(int a[]){

int i=10; //初始化，从10开始计算 while(i>0){

a[i-1]=2*a[i]+2; i--; } }

（3）单链表模块

typedef struct Lnode{

int data; // struct Lnode *next; //}LinkList;

LinkList *CreatList() （3） 主函数模块 void main()

数据域 链表指针