数据结构实验一joseph
- 格式：doc
- 大小：137.12 KB
- 文档页数：13
课 程 设 计 报 告 课程设计名称 数据结构课程设计 专 业 计算机科学与技术 班 级 计科三班 学 号 XXXXXX 姓 名 XXXXXX 指导教师 XXXXXX 成 绩 数据结构课程设计 ——《Joseph环》
目 录 一、设计任务与要求 ...................................................... 1 1.1 总体目标与任务要求 .............................................. 1 1.2 题目选择与目的意义 .............................................. 1 1.3 所选题目的主要工作 .............................................. 1 二、需求分析 ............................................................ 1 2.1 用户需求分析 ..................................................... 1 2.2 功能需求分析 ..................................................... 1 2.3 系统需求分析 ..................................................... 2 三、概要设计 ............................................................ 2 3.1 各模块的算法设计说明 ............................................ 2 函数流程图： ......................................................... 2 模块关系图： ......................................................... 3 3.2 存储结构设计说明 ................................................ 4 四、详细设计 ............................................................ 4 五、源代码 .............................................................. 6 六、运行结果分析 ........................................................ 7 算法的时空分析 ....................................................... 8 七、收获与体会 .......................................................... 9 八、主要参考资料 ........................................................ 9 1
一、设计任务与要求 1.1 总体目标与任务要求 总体目标：用C++软件设计一个程序用来求出一个序列的出列顺序。 要求：利用单向循环链表存储结构实现这个过程，按照出列的顺序输出每一个人的编号。 1.2 题目选择与目的意义 据说joseph在战争时期，与39个犹太人和他一个朋友躲到一个洞里，39个犹太人决定宁死也不被敌人抓到，于是他们决定了一个自杀方式，41个人排成圈，由第一个人开始报数，每报到三的人就必须自杀，依次循环直到每个人都自杀身亡。但josrph和他的朋友并不想村从，于是他把自己和朋友安排到第16个位置和第31个位置，于是他们俩逃过了这个死亡游戏。 Joseph问题是个很由意思的问题，其意义在于它启发我们用一个循环的链来表示这个圈子，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人的标记。所以我们选择了这个题目。 1.3 所选题目的主要工作 以单向循环链表的方式建立约瑟夫环。 建立输入处理输入数据，输入m的初值，n ，建立单向链表，输入每个人的密码建立一个输出函数，将正确的出列顺序输出序列。
二、需求分析 2.1 用户需求分析 编号是1，2，„„,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
2.2 功能需求分析 各个模块间的调用关系如下： 2
2.3 系统需求分析 系统软件：Windows操作系统 开发软件：Microsoft Visual C++ 6.0 其他软件：Microsoft Office Word 2003，Adobe Photoshop CS3
三、概要设计 3.1 各模块的算法设计说明 函数流程图： 3
模块关系图： joseph *creat(void)，void game(joseph *head,int m)，void main()部分函数流程图： 4 3.2 存储结构设计说明 typedef struct Node { ElemType date; //编号 int mima; //密码 struct Node *next; }Node,*LinkList; 单向循环链表： LinkList H; //表头指针 Node *Q,*Pre;//*Q指新建结点，*pre指向当前工作结点 Q=(Node*)malloc(sizeof(Node));
构造函数： void InitList(LinkList *H); //初始化循环链表 void InPut(LinkList H,int *A);//插入结点 void DelList(LinkList H,int *x, int*a); //删除结点
四、详细设计 typedef struct Lnode{//节点类型 ElemType data; Struct Lnode *next; }*Link,*Position; typedef struct{ //链表类型 Link head,tail; //分别指向线性链表中的头结点和最后一个结点 Int len; //只是线性链表中的数据元素 }LinkList; Status MakeNode(Link&p,ElemType e); //分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR void FreeNode(Link&p); //释放p所指接点 Status InitList(LinkList&L); //构造一个空的线性表L Status DestroyList(LinkList&L); //销毁线性表L,L不再存在 Status ClearList(LinkList&L); //将线性表L从之唯恐表，并释放原链表的结点空间 Status InsFirst(Link h,Link s); //已知h指向线性链表的头结点，将s所直接点插入在第一个结点之前 Status DelFirst(Link h,Link&q); //已知h指向线性表的头结点，删除链表中的第一个结点并以q返回 Status Append（LinkList&L,Link s）; //将指针s所指（彼此以指针项链）的一串结点链接在线性链表L的最后一个结点 5
//之后，并改变链表L的尾指针指向新的尾节点 Status Remove(LinkList&L,Link&q); //删除线性链表L中的尾结点并以q返回，改变链表L的尾指针只想新的尾结点 Status InsBefore(LinkLIst&L,Link&p,Link s); //已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前， //并修改指针p指向新插入的结点 Status InsAfter (LinkLIst&L,Link&p,Link s); //已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后， //并修改指针p指向新插入的结点 Status SetCurElem(Link&p,ElemType e); //已知p指向线性链表中的一个结点，用e更新p所指结点中的数据元素的值 ElemType GetCurElem(Link p); //已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 Status listEmpty（LinkList L）； //若线性链表L为空表，则返回TRUE，否则返回FALSE int ListLength(LinkList L); //返回线性链表L中元素个数 Position GetHead(LinkList L); //返回线性链表L中头结点的位置 Position GetLast(LinkList L); //返回线性链表L中最后一个结点的位置 Position PriorPos (LinkList L,Link p); //已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置‘ //若无前驱，则返回NULL Position NextPos(LinkList L,Link p); //已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置‘ //若无后继，则返回NULL Status LocatePos(LinkList L,int I,Link&p); //返回p指示线性链表L中的第I个节点的位置并返回OK，i值不合法时返回ERROR Position LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)); //返回线性链表L中的第1个与e满足函数compare()判定关系的元素的位置， //若不存在这样的元素，则返回NULL Status ListTraverse(LinkList L,status(*visit)());
//依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败
