《华中科技大学数据结构试验报告》由会员分享，可在线阅读，更多相关《华中科技大学数据结构试验报告（17页珍藏版）》请在金锄头文库上搜索。
1、实验报告课程名称：数据结构班 级：姓 名：指导老师：实验日期： 实验成绩: 实验名称 约瑟夫环1 需求分析（1）输入的形式和输入值的范围：每一次输入的值为两个正整数，中间用ENTER隔开。若分别设为 n,m，则输入格式为：a .”“n/nm ”。不对非法输入做处理，即假设输入都是合法的。（2）输出的形式：输出格式 1：在字符界面上输出这 n 个数的输出序列 输出格式 2：将这 n 个数的输出序列写 入到文件中（3）程序所能达到的功能：对于输入的约瑟夫环长度n和间隔m，输出约瑟夫环的出列顺序。（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。正确：输入： 10,3输出： 3
2、 6 9 2 7 1 8 5 10 4输入： 41,3输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 252 22 4 35 16 31错误：输入： 10 3输出： 6 8 7 1 3 4 2 9 5 102 概要设计（1）抽象数据类型的定义： 为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表 LinkList 定义如下：LinkList数据对象： LinkList *L 数据结构；循环列表p-next = h
3、ead;/* 使链表尾指向链表头 形成循环链表 */（2）算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的” ，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可 以采用循环列表来实现线性表，完成出列顺序的输出。核心算法主要分为两步：1、确定需要删除的位置，2、设置并删除该位置。已知报数间隔 m,我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置,继而删掉该位置。 反复进行上述确定位置和删除
4、位置的操作,直到顺序表为空。（3）主程序的流程： 程序由三个模块组成：（1 ）输入模块：有提示语句，直接输入总人数n和报数次数m，中间用ENTER隔开。（2）处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元素的位置， 在顺序表中设置该位置并删除该位置， 同时输出该位置的值。 反复设置并删除直到表空。(3)输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。( 4)各程序模块之间的层次(调用)关系：主函数会按设计的方法调用顺序表中 “获取实际长度” 、“设置需要删除元素的位置” 、“移除 该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束
5、程序。程序如下：#include#includetypedef struct Nodeint num;struct Node *next; LinkList;LinkList *creat(int n)LinkList *p, *q, *head;int i = 1;p = (LinkList *)malloc(sizeof(LinkList);p-num = i;head = p;for (i = 2; i num = i;p-next = q;p = q;p-next = head; /* 使链表尾指向链表头 形成循环链表 */return head;void fun(LinkList *
6、L, int m)int i;LinkList *p, *s, *q;p = L;printf( 出列顺序为 :);while (p-next != p)for (i = 1; i next;printf(%5d, p-num);s = p；q_next = p_n ext;p = p-next; /*使p指向新的起点*/free(s);/*free()与malloc()函数配对使用，释放malloc函数申请的动态内存*/prin tf(%5dn, p- nu m);int mai n()Lin kList *L;int n, m;prin tf(i nput n, m:n); scan f(
7、%d%d, &n, &m);L = creat( n);fun (L, m);return 0;实验结果: E:A bodeM i c rosoft Vi su 日I Stu d i oMyProj ectsm yDe b u gm y.exeinput n, m；103出列顺序为：36927185 1G 4Press any key to continue实验体会：由于并不熟练，只能看着书，对着书上的写，很多地方没完善，因为 不会，马马虎虎。实验名称 车厢调度 一、需求分析1. 本演示程序中，使用顺序堆栈作为车厢调度车站，车子按1,2n的顺序依次排列在车站入口处，其中n50则会提示出错。2.
8、 演示程序以用户和计算机对话方式执行。即在计算机终端上显示提示信息之后，由用户在键盘上输入车厢数目 n 后，相应的结果会显示在屏幕上。3. 程序执行的命令包括：1 )构造顺序堆栈2)输初始化堆栈出结果3)调用递归函数为：4.1测试数据n=1,n=2,输 出 结果为:2112n=3,输出结果为 :321231213132123n=4，输出结果为：432134213241321424312341 23142143213414321342132412431234二、概要设计1 、设定栈的抽象数据类型定义：ADT Stack数据对象：D=ai | ai CharSet, i=1, 2, , , n,
9、n0数据关系：R仁 |ai-1,ai D,i=2, , ， n 基本操作： InitStack(&S)操作结果：构造一个空栈S。 Push(&S,e);初始条件：栈S已存在。操作结果：在栈 S的栈顶插入新的栈顶元素e。Pop(&S,e);初始条件：栈S已存在。操作结果：删除 S的栈顶元素，并以 e返回其值。StackEmpty(S) 初始条件：栈S已存在。操作结果：若 S为空栈，则返回 TRUE否则返回FALSE ADT Stack2、本程序包括两个模块：(1 ) 初始化数据输入总数初始化栈和序列(2) 显示所有的序列递归调用输出所有结果 程序如下：#include#include#defin
10、e STACK_INI_SIZE 1000#define STACKINEMENT 10#define NULL 0typedef structint *base;int *top;int stacksize;int length;stack;main()void initlist(stack *s);void operation(stack *s);stack s;initlist(&s); operation(&s);void initlist(stack *s)s-base=s-top=(int *)malloc(STACK_INI_SIZE*sizeof(int); if(!s-bas
11、e)printf( 开辟失败 );exit(1);s-length=0; s-stacksize=STACK_INI_SIZE;void push(stack *s,int i)if(s-length=s-stacksize)s-base=(int *)realloc(s-base,(STACK_INI_SIZE+STACKINEMENT)*sizeof(int); s-length=STACK_INI_SIZE;s-stacksize+=STACKINEMENT;*(s-top)=i; s-length+;s-top+;void pop(stack *s)if(s-top=s-base)pr
12、intf( 栈空无法删除错误 );exit(1);s-top-;printf(%d ,*(s-top);*(s-top)=NULL;s-length-;void operation(stack *s)int a1000,i,j,k,m,n,l,z,y,flag1=1,flag2=1;char ch;printf( 请输入车厢数 n); scanf(%d,&i);flag1=1;for(j=0;ji*2;j+)/* 对数组初始化为 10101010 ，即首组输出的数据为 1234*/ aj+=1;aj=0;while(flag1)/* 总循环，输出所有满足条件的车厢调度 */l=1,k=0;for(j=0;ji*2;j+)/* 输出车厢调度 */if(aj=1) push(s,l+);else if(aj=0)pop(s);printf(n);for(j=0;j=0&z;j-)/* 假如自加之后是 2 的话，前一位自加0*1if(aj!=2)z=0;elseaj=0;aj-1+;for(j=0;ji*2 &y;j+)/*检验新的组合是否满足需求*/
