数据结构课程设计报告-模版.docVIP

数据结构课程设计报告实验名称： 班 级： 学 号： 姓 名： 实验日期： 年 月 日目 录一：实验目的二：需求分析三：概要设计四：详细设计五：调试分析六：实验总结样例：一、实验目的1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。二、需求分析约瑟夫问题（Josephus Problem）：据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。1. 约瑟夫问题的描述：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为初始报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数。【方法一】报m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。【方法二】报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即任意的人数n、初始报数上限值m以及每个人所持的密码），最终输出相应的出列序列。 3. 测试数据：1) 首先假设m=6，n=7。设定7个人的密码依次为：3，1，7，2，4，8，4，则正确的出列顺序为：6，1，4，7，2，3，5。2) m=6,n=13) m=6,n=0前面一组为常规数据，后面两组为边缘数据。三、概要设计为了实现上述操作，应以单向循环链表为存储结构。程序执行的命令包括：【方法一】1）构造链表2）输入人数n和初始报数上限值m3）执行报数，储存出列人的编号，删除出列人的信息4）输出出列序列，即每个人的编号5）结束【方法二】1）构造链表2）输入人数n和初始报数上限值m3）输入每个人的密码4）执行报数，储存出列人的编号，删除出列人的信息以及把出列人的密码重新赋给m5）输出出列序列，即每个人的编号和密码6）结束四、详细设计#include#includetypedef struct data /定义一个结构体data int num; /用于存放人的序号 int val; /用于存放密码 typedata; typedef struct node /定义一个结构体（结点），其中包含一个数据域和一个指针域 typedata data; /结构体的嵌套 struct node *next; listnode; typedef listnode *linklist; linklist head; void main()/ 进入主函数 int n,i,b,m,j; linklist head=(listnode *)malloc(sizeof(listnode); /申请一个空间（头结点 head） listnode *p,*q; /定义两个可以指向结点的指针 printf(输入总人数n：); scanf(%d,&n); q=head; /用指针q指向头结点 for(j=1;jnext=(listnode *)malloc(sizeof(listnode); /将头结点的next域指向刚生成的一个结点 q=q-next; q-data.val=b; /输入密码 q-data.num=j; /输入序号 q-next=head-next; /将尾结点的next域指向第一个结点，构成循环链表 printf(请任意输入一个数m：); scanf(%d,&m); if(mnext; /将q指针一直后移直到指向所要输出的结点的前一结点 i+; p=q-next; /p指向输出结点 q-next=p-next; /将输出结点的前结点的next域指向输出结点的后结点 printf(num:%dtval:%dn,p-data.num,p-data.val); /输出该结点 m=p-data.val; /取得输出结点的密码 free(p); while(q-next!=q); /只剩最后一个结点时结束 printf(num:%dtval:%dn,q-