《《数据结构与算法设计》实验报告》由会员分享，可在线阅读，更多相关《《数据结构与算法设计》实验报告（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法设计实验报告实验一学院： 班级：学号：姓名： 1、实验目的 1. 熟悉 VC+6.0 环境，学习使用 C+实现链表的存储结构；2. 通过编程，上机调试，进一步理解线性表、链表、环表的基本概念，并利用单向环实现约瑟夫环。二、实验内容 1、 采用单向环表实现约瑟夫环。请按以下要求编程实现： 从键盘输入整数 m，通过 create 函数生成一个具有 m 个结点的单向环表。环表中的结点编号依次为 1，2，m。 从键盘输入整数 s（1ai-1,aiD,i=2,n基本操作：Creat(LinkList&L,int m)操作结果：构造一个有 m 个节点的单向环表 L。YSF(int m,int
2、 s,int n,LNode *L)初始条件：单向环表 L 已经存在。操作结果： 找到单向环表 L 的第 s 个结点，并进行约瑟夫环的计算，并输出相应值。ADT List（2） 主程序流程主程序首先调用 Creat(LinkList&L,int m)函数，创建含有 m 个结点的单向环表 L；再调用 YSF(int m,int s,int n,LNode *L)函数，找到第 s 个结点，并进行约瑟夫环的计算，在屏幕上显示计算结果。（3） 模板调用关系由主函数模板调用创建模块和运算模块。由运算模块将结果输出。 （4） 流程图2、详细设计(1)数据类型设计typedef struct LNode /
3、定义结构体int data;struct LNode *next;LNODE; (2)操作算法设计void Create(LNode *L,int m) /创建单向环表int i; LNode *p;if(m1)p=(LNode*)malloc(sizeof(LNode);p-data=m;p-next=L;L-next=p; m=m-1; 开始输入数据（m，s，n）创建环表输出环表计算处理结束for(i=m;i1;i-) /插入到表头p=(LNode*)malloc(sizeof(LNode);p-data=i;p-next=L-next;L-next=p; m=m-1 void YSF(i
4、nt m,int s,int n,LNode *L) /找到第 s 个结点并进行约瑟夫计算int a=1,b=0;LNode *p,*head;p=L;head=p-next;while(head-next!=p)head=head-next;while(p-data!=s) /寻找起始结点p=p-next;head=head-next;for(b=m;b0;b-) for(a=1;anext;head=head-next;printf(%dn,p-data);head-next=p-next;free(p);p=head-next;(3) 主函数设计void main() /主函数int m
5、,s,n;LNode *L=NULL;scanf(%d %d %d,L=(LNode*)malloc(sizeof(LNode); /建立第一个结点L-data=1;L-next=NULL;Create(L,m);YSF(m,s,n,L); /计算并输出结果四、程序调试分析 （1）在第二步即环表建立的步骤时候，YSF 函数的编写总是出 error，在反复研究和调试之后依旧没有解决问题，最后在同学帮助下终于找到了的原因编写时未将结点退回原来结点处。所以说，调试一定要一步一步来，不能心急，仔细才能正确。（2）构造数据类型时，未写 typedef，导致编译无法通过。这是概念上的疏忽，要重视。五、用户
6、使用说明 1、本程序的运行环境为 Windows 操作系统下的 Microsoft Visual C+ 6.0。2、在 VC 环境下打开程序后，按要求键入 m,s,n 的值，敲击“回车符” ，即可以显示要求的结果。六、程序运行结果测试用例 1：输入：m=10，s=3，n=4 输出：6，10，4，9，5，2，1，3，8，7测试用例 2：输入：m=8，s=2，n=5 输出：6，3，1，8 ，2，5 ，7， 4 七、程序清单#include #include typedef struct LNode /定义结构体int data;struct LNode *next;LNODE;void Creat
7、e(LNode *L,int m) /创建单向环表int i;LNode *p;if(m1)p=(LNode*)malloc(sizeof(LNode);p-data=m;p-next=L;L-next=p;m=m-1;for(i=m;i1;i-) /插入到表头p=(LNode*)malloc(sizeof(LNode);p-data=m;p-next=L-next;L-next=p;m-;void YSF(int m,int s,int n,LNode *L) /主要的操作函数int a=1,b=0;LNode *p,*head;p=L;head=p-next;while(head-next
8、!=p)head=head-next;while(p-data!=s) /寻找起始结点p=p-next;head=head-next;for(b=m;b0;b-)for(a=1;anext;head=head-next;printf(%dn,p-data);head-next=p-next;free(p);p=head-next;void main() /主函数int m,s,n;LNode *L=NULL;scanf(%d%d%d,L=(LNode*)malloc(sizeof(LNode); /建立第一个结点L-data=1;L-next=NULL;Create(L,m);YSF(m,s,n,L); /计算并输出结果
