数据结构实验报告Ⅰ.docVIP

《数据结构与算法统计》 实验报告一 学院： 自动化学院 班级： 061111xx 学号： 112011xxxx 姓名： 张xxx 实验目的 采用单向环表实现约瑟夫环，熟练掌握线对性表的各种基本操作：线性表的建立、数据元素的查找、结点的删除等。 实验内容 按以下要求编程实现： 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。 从键盘输入整数s（1=s=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。 例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。 程序设计 1、概要设计 以单向循环链表为存储结构： 基本操作： CreateList_L ( ) 操作结果：构造一个有m个结点的单向环表L ListDelete_L ( ) 初始条件：单向环表L已存在 操作结果：删除指向出列的数的结点 本程序包含三个模块： (1)构造链表并初始化环表结点编号； (2)删除结点模块 (3)主程序模块 主程序流程： 主程序首先调用CreateList_L ( )函数创建含有m个结点的单向环表L，然后调用ListDelete_L ( )函数计算结果并在屏幕上打印。 流程图： 2、详细设计 数据类型设计： typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; LinkList L,p,h; 操作算法设计： void CreateList_L ( LinkList L, int m ) { //创建一个有m个结点的单向环表 int j; L = ( LinkList ) malloc ( sizeof (L) );//申请空间 h=L; for(j=1;j=m;j++) { p = ( LinkList ) malloc ( sizeof(L) ); p-data = j; h-next = p; // 插到表尾 h=p; } h-next = L-next ; } //CreateList_L void ListDelete_L(LinkList L,int s,int n) { p=L; LNode *head=p; //声明结点 while(p-data!=s) { p=p-next; head=p; } //寻找起始结点 while(p-next!=p) { for(int i=0;in-1;i++) { head=p; //保存前置节点 p=p-next; } printf(%d ,p-data); head-next=p-next; //删除已输出结点 p=head-next; } if(n!=1) printf(%d\n,p-data); else printf(\n); }//ListDelete_L 程序调试分析 开始时忽略了文件包含#includestdlib.h，而且思路不是很清晰，调试时浪费了不少时 间。今后应多注意细节并认真理清思路。 在删除函数中，未定义当前结点的前置结点，导致输出结果有误，后经仔细分析及调试，定义指针指向当前结点的前置结点，简化了程序，提高了效率。 五、程序运行结果 打开程序，在“请输入m：”后输入所需单向环表结点数；随后在“请输入s：”后输入起始结点数；最后在“请输入n：”后输入计数规则。 运行后即在屏幕上输出计算结果。 六、程序清单 #includestdio.h #includestdlib.h typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList; LinkList L,p,h; void CreateList_L ( LinkList L, int m ) {//创建一个有m个结点的单向环表 int j; L = ( LinkList ) malloc ( sizeof (L) );//申请空间 h=L; for(j=1;j=m;j++) { p = ( LinkList ) malloc ( sizeof(L) ); p-data = j; h-next = p; // 插到表尾 h=p; } h-next = L-next ; }