Joseph环数据结构设计报告毕业设计（论文）.doc

西安工業大學 数据结构课程设计报告 班级：081001 姓名：巩雪 学号指导教师：史延新 完成日期：2010-12-24 题目1.Joseph环 1.问题描述： 编号是1，2，……，n的n个人按照顺时针方向围坐一圈，一开始任选一个正整数作为报数上限（开始）值m(m＜n)，从第个人开始沿顺时针方向顺序报数，报到m时停止报数，报m的人出列，然后在从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 要求： 利用此过程，按照出列的顺序输出各个人的编号。 输入数据：建立输入处理输入数据，输入m、n、的初值和每个人的编号，建立单循环链表。 输出形式：建立一个输出函数，将正确的序列输出。 测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 需求分析 1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。 2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示提示信息之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。 3． 程序执行的命令包括： 1)构造单向循环链表；2）提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4． 测试数据 m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，3，5）。 概要设计 1．单向循环链表的抽象数据类型定义为： ADT List｛ 数据对象：D=｛ai | ai正整数，I=1，2，......，n,n≥0｝ 数据关系：R1=｛lt; ai-1，ai gt; |，ai-1，aiD,I=1，2，......，n｝ 基本操作： InitList(L)操作结果：构造一个最大长度ms内容为空的有序表L。ClearList(L)初始条件：线性表L已经存在。操作结果：将L重置为空表。EmptyList(L)初始条件：线性表L已经存在。操作结果：若L为空表返回TRUE，否则返回FALSE。ListLength(L)初始条件：线性表L已经存在。操作结果：返回L中数据元素个数。GetElem(L, pos, e)初始条件：线性表L已经存在，1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L, e)初始条件：线性表L已经存在。操作结果：返回L中第1个与e相同的元素的位序。若不存在返回0。ListInsert (L, i, e)初始条件：线性表L已经存在。操作结果：在L中的第i个元素的位置之前插入新元素 e,L的长度加1。ListDelete(L, pos, e)初始条件：线性表L已经存在，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L)初始条件：线性表L已经存在。操作结果：依次对L的每个数据元素进行访问。}ADT SqList本程序包含以下模块：（1）主程序模块：void main(){??? 初始化；??? 输入数据；??? 执行功能；显示结果；} （3）元素结构单元模块：定义线性表每个元素的结构 （2）各功能模块——实现顺序表的各项功能。各模块的调用关系：主程序?? ↓各功能模块typedef struct Node { int num; //?? 表示该元素的编号 int cipher;----- //?? 表示该元素的顺序位置 struct Node *next; }node,*hu;--------// 结点类型，指针类型 （2）设定了init(int n)函数来模拟所输入的N个数以线性循环单链表的形式进入和输出：init(int n) { int i;-----------\设定第i个数 int cipher；--------//定义元素的顺序位置 hu L;------------//定义指向下一个元素的指针节点L if(n=1)----------//定义 循环的输入的条件 { scanf(%d,cipher); H=(hu)malloc(sizeof(node));---------//生成头结点; H-number=1; H-cipher=cipher; H-next=H; for(i=1;in;i++) { scanf(%d,cipher); L=(hu)malloc(sizeo