北京理工大学数据结构与算法设计实验一

1、数据结构与算法设计实验报告实验一学院： 自动化学院班级： 学号： 姓名： 宝竞宇 一、 实验目的 实现链表的基本操作，如：建立，插入，删除等。应用链表解决实际问题。二、实验内容 采用单向环表实现约瑟夫环。 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，m。 从键盘输入整数s（1=s=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。例如，m=10，s=3，n=4。则输出序列

2、为：6，10，4，9，5，2，1，3，8，7。三、程序设计 1、概要设计 本程序要用到一个抽象的数据类型：链表节点。其中包括一个数值项，和指针项。宏定义“错误”，与程序成功后返回的“成功。” 建立一个“生成函数”来生成，环表。在建立一个“查找输出函数”，来实现约瑟夫的输出。在主程序中先定义一个链表节点定义，然后在调用“生成函数”来生成约瑟夫表。接下来调用“查找输出函数”，输出题目要求的数字编号序列。 2、详细设计抽象数据类型定义：typedef struct NODEint num; struct NODE *next; linklist;宏定义： #define ERROR 0 #defin

3、e OK 1生成函数：该函数的输入值为 n值，返回为linklist型的指针变量指向生成的环表的头结点。其中先定义一个头结点，给其分配储存空间head=p=(linklist *)malloc(sizeof(linklist);然后再用一个for循环连续的生成，插入节点到该函数中for(i=2;inum=i; p-next=q; p=q; 程序错误返回ERROR。最后函数返回其头结点“head”。.查找输出函数:该函数的操作值为生成链表的头结点。在其函数内部输入题目中要求的“起始点”s,和“每次查找的数目”n。先用一个while循环找到s点，把其地址给指针变量p，再用一个循环，查找n个数目的节

4、点，然后输出节点，再删除节点，释放节点。 while(p-next!=p)for(i=1;inext;printf(%5d,p-num);w=p;q-next=p-next;p=p-next;free(w);主函数：在主函数内部先输入所要生成的m的节点数，定义一个linklist指针变量。先调用生成函数，再调用查找函数。完成程序实现 int main(int argc, char *argv)linklist *l; int m; printf(m=); scanf(%d/n,&m); l=creat(m); fun(l);system(PAUSE); return 0;主要流程图：结 束开

5、始调用fun函数模块查找调用主函数，输入m调用creat（）函数模块创建链表四、程序调试分析 在程序调试过程中，creat（）函数的编写，关于next指针的指向，和删除节点的过程并没掌握清晰，导致生成的链表并不成功，后来参照课本上的生成程序找到了p-next的具体使用。q-next=p-next;句。在fun函数的编写过程中并没有考虑到i和n的关系“”和“=”没有弄清，导致少输出最后一个节点。同时在链表全部输出完后的条件也没有弄清，后来在程序分析过程中找到了结束条件p-next!=p，这是环表的结束条件。在这次的实验中，我掌握了链表的生成，删除，查找等功能，同时自己找到了环表的结束条件，掌握了

6、链表的指针型的指向，和各节点之间的关系。五、用户使用说明 打开函数，然后根据提示依次输入链表的节点数；m，开始序号：s；每次查找的个数：n；然后按“回车键”输入结果，再按任意键退出程序。六、程序运行结果 七、程序清单#include #include #define ERROR 0#define OK 1 typedef struct NODEint num; struct NODE *next; linklist;linklist *creat(int n) /* 生成函数，返回为指针*/ linklist *p,*q,*head; int i=1; head=p=(linklist *)m

7、alloc(sizeof(linklist); /*创造头结点*/ p-num=i; for(i=2;inum=i; p-next=q; p=q; p-next=head; return head; /*返回头结点指针*/ fun(linklist *l) /*查找输出函数，输入值为环表头结点指针*/int n,i,s; linklist *p=l,*q,*w; printf(s=);scanf(%d/n,&s);i=s; /*输入起点s*/ printf(n=);scanf(%d/n,&n); /*每次查找个数n*/while(i1)p=p-next; /*找到起点*/ i-; while(p-next!=p) /*依次查找输入*/for(i=1;inext;printf(%5d,p-num);w=p; q-next=p-next; /*从下一个节点开始再次循环*/p=p-next;free(w);printf(%5d,p-num);printf(n); return OK;