<<数据结构>>课程设计班级:111004姓名:董丽美学号:111004122指导教师:史延新完成日期:2013 _07 _10题目一:约瑟夫环问题【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为1,2，…,n 的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m 的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
试设计一个程序求出列顺序。
【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。
【测试数据】m的初值为20；n=7,7个人的密码依次为：3,1,7,2，4,8,4，首先m值为6（正确的出列顺序应为：6,1,4,7,2,3,5）一 .需求分析1．用单循环链表存储并遍历及删除节点的方法，计算并输出约瑟夫环的问题。
2．环中总人数和节点信息由用户输入，且均为正整数。
3．在窗口界面输出出列顺序的编号。
二．概要设计1.设定链表的抽象数据类型定义：ADT List{数据对象：D={a(i)|a(i)∝Elemset,i=1,2,…,n,n>=0}数据关系：R1={<a(i-1),a(i)>|a(i-1),a(i)∝D,i=2,…,n}基本操作：InitList(&L)操作结果：构造一个空的线性表ListInsert(&L,i,e)初始条件：线性表L已经存在。
操作结果：在L中第i个位置之前插入新的数据元素 e,L的长度增加1。
ListDelete(&L,i,&e)初始条件：线性表L已经存在且非空，1<=i<=ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L 的长度减1 。
}2.算法的基本思想：根据题目要求，采用单循环线性表的基本操作来实现约瑟夫环问题。
首先根据所给信息生成链表节点并插入，根据节点记录密码及其所在链表中的顺序，由给出的初始访问值进行遍历，当变量i增量等于所给的值（即关键字）时，指针所指的节点处的顺序值即为所需输出的顺序号。
每输出一次顺序号，将顺序号所在的节点删除，当最后单循环链表的头指针为空时，跳出循环。
完成出列顺序的打印。
3.程序的流程:程序由三个模块组成：1）输入模块：完成两个正整数的输入，存入变量n和m 中。
初始值:n=7;m=62）计算模块：用循环的方式设计算法计算出依次输出的序列数。
3）输出模块：屏幕上显示依次被淘汰的人的编号。
三．详细设计1.不带头结点单循环链表节点结构体定义：typedef struct NODE{int code;//密码int num; //在链表中顺序号NODE *pnext;//节点指针}NODE;typedef struct CIRCLE_LINK//循环链表{NODE *front;NODE *rear;}CIRCLE_LINK;2.源程序代码：(运行环境：VC++ 6.0)#include "stdafx.h"#include<stdlib.h>#include<string.h>typedef struct NODE{int code;int num;NODE *pnext;}NODE;typedef struct CIRCLE_LINK{NODE *front;NODE *rear;}CIRCLE_LINK;bool init_circle_link(CIRCLE_LINK **link) {*link=(CIRCLE_LINK *)malloc(sizeof(CIRCLE_LINK));if(NULL==*link){return false;}(*link)->front=NULL;(*link)->rear=NULL;return true;}bool insert_circle_link_end(CIRCLE_LINK *link,int code,int num){NODE *curt=NULL;curt=(NODE*)malloc(sizeof(NODE));if(NULL==curt){return false;}curt->num=num;curt->code=code;if(NULL==link->front){link->front=curt;link->rear=link->front;link->rear->pnext=link->front;}else{curt->pnext=link->rear->pnext;link->rear->pnext=curt;link->rear=curt;}return true;}void delete_node(CIRCLE_LINK *link,NODE *pcurt) {NODE *ptem=link->front;NODE *prear=link->rear;while(true){if(link->front==link->rear&&link->front==pcurt)//删除链表中唯一的一个节点{link->front=NULL;link->rear=NULL;break;}if(link->front==pcurt)//删除头结点{link->front=link->front->pnext;link->rear->pnext=link->front;free(pcurt);pcurt=NULL;break;}ptem=ptem->pnext;if(ptem->pnext==pcurt&&pcurt->pnext==link->front) //删除尾节点{ptem->pnext=link->front;link->rear=ptem;free(pcurt);pcurt=NULL;break;}if(ptem->pnext==pcurt)//删除中间节点{ptem->pnext=pcurt->pnext;free(pcurt);pcurt=NULL;break;}}}void find_key(CIRCLE_LINK *link,int key) {NODE *pcurt=link->front;NODE *ptem=NULL;int i=1;printf("输出序列为:\n");while(link->front!=NULL){for(;i<key;){i++;pcurt=pcurt->pnext;}i=1;printf("%d\n",pcurt->num);key=pcurt->code;ptem=pcurt;pcurt=pcurt->pnext;delete_node( link,ptem);}}int main(int argc, char* argv[]) {int i=0;int n=0;int num=1;int code=0;int key=0;CIRCLE_LINK *link=NULL;init_circle_link(&link);printf("请输入总人数:");scanf("%d",&n);getchar();for(i=0;i<n;i++){printf("请输入第%d个人的密码:",num);scanf("%d",&code);getchar();insert_circle_link_end(link,code,num);num++;}printf("请输入初值（关键字）:");scanf("%d",&key);printf(".................\n");getchar();find_key(link,key);return 0;}3. 输出结果及输出界面：四.调试分析1.调试过程中出现scanf语句后，不加getchar();使缓冲区出空格未被读取，不能继续调试及运行。
经分析并修改后正确。
2.对循环的退出条件。
五.用户使用说明1.用户可根据需求进行客户端窗口的数据信息的输入，从而的到所需求的输出结果。
六.测试结果1.根据所给测试数据可知，测试结果正确，及所编写程序代码正确。
七.参考文献1.《数据结构》C语言版严蔚敏吴伟民清华大学出版社2.《数据结构题集》C语言版严蔚敏吴伟民清华大学出版社3.《C语言程序设计》谭浩强清华大学出版社题目二:图遍历的演示【问题描述】很多涉及图上操作的算法都是以图的遍历操作为基础的。
试写一个程序，演示在连通的无向图上访问全部结点的操作。
【基本要求】以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。
【测试数据】交通网例图所示：一 .需求分析根据节点数组进行边信息存储，进行两种方式的遍历。
二．概要设计1.图的存储本课题要求采取邻接表的存储结构。
邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。
每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条2.边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。
所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。
此时要分两种情况：有向图与无向图。
对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。
同时将终点的单链表表头插入一边结点，即起点。
对于有向图，只能向起点的单链表的表头插入一个边结点，即终点。
但不能反过来。
至于邻接表的输出，由于不了解C++中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出。