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

《数据结构课程设计报告-模版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构课程设计报告实验名称：班级：学号：姓名：实验日期：年月日目录一：实验目的………………………………………………二：需求分析………………………………………………三：概要设计………………………………………………四：详细设计………………………………………………五：调试分析………………………………………………六：实验总结………………………………………………样例：一、实验目的1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2.重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。二、需求分

2、析约瑟夫问题（JosephusProblem）：据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。1.约瑟夫问题的描述：编号为1，2，……，n的n个人

3、按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为初始报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数。【方法一】报m的人出列（将其删除），从他在顺时针方向上的下一个人开始重新从1报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。【方法二】报m的人出列（将其删除），将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从一报数，……，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表

4、存储结构模拟此过程，按照出列的顺序打印出各人的编号和此人密码。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）构

5、造链表2）输入人数n和初始报数上限值m3）执行报数，储存出列人的编号，删除出列人的信息4）输出出列序列，即每个人的编号5）结束【方法二】1）构造链表2）输入人数n和初始报数上限值m3）输入每个人的密码4）执行报数，储存出列人的编号，删除出列人的信息以及把出列人的密码重新赋给m5）输出出列序列，即每个人的编号和密码6）结束四、详细设计#include#includetypedefstructdata{//定义一个结构体"data"intnum;//用于存放人的序号intval;//用于存放密码}typedata;type

6、defstructnode{//定义一个结构体（结点），其中包含一个数据域和一个指针域typedatadata;//结构体的嵌套structnode*next;}listnode;typedeflistnode*linklist;linklisthead;voidmain()//进入主函数{intn,i,b,m,j;linklisthead=(listnode*)malloc(sizeof(listnode));//申请一个空间（头结点head）listnode*p,*q;//定义两个可以指向结点的指针printf("输入总人数n：");scanf("%d

7、",&n);q=head;//用指针q指向头结点for(j=1;j<=n;j++)//本次循环主要是将每一个人的数据（包括序号、密码）存入循环链表中{printf("请输入第%d号同学的密码:",j);scanf("%d",&b);printf("");q->next=(listnode*)malloc(sizeof(listnode));//将头结点的next域指向刚生成的一个结点q=q->next;q->data.val=b;//输入密码q->data.num=j;//输入序号q->next=head->next;}//将尾结点的next域指向

8、第一个结点，构成循环链表printf("请任意输入一个数m：");