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

《数据结构与算法设计》实验报告——实验一学院：自动化学院班级：06111001学号：1120100001姓名：宝竞宇一、实验目的实现链表的基本操作，如：建立，插入，删除等。应用链表解决实际问题。二、实验内容采用单向环表实现约瑟夫环。①从键盘输入整数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、概要设计本程序要用到一个抽象的数据类型：链表节点。其中包括一个数值项，和指针项。宏定义“错误”，与程序成功后返回的“成功。”建立一个“生成函数”来生成，环表。在建立一个“查找输出函数”，来实现约瑟夫的输出。在主程序中先定义一个链表节点定义，然后在调用“生成函数”来生成约瑟夫表。接下来调用“查找输出函数”，输出题目要求的数字编号序列。2、详细设计抽象数据类型定义：typedefstructNODE{intnum;structNODE*next;}linklist;宏定义：#defineERROR0#defineOK1生成函数：该函数的输入值为n值，返回为linklist型的指针变量指向生成的环表的头结点。其中先定义一个头结点，给其分配储存空间head=p=(linklist*)malloc(sizeof(linklist));然后再用一个for循环连续的生成，插入节点到该函数中for(i=2;i=n;i++){q=(linklist*)malloc(sizeof(linklist));if(q==0)return(ERROR);q-num=i;p-next=q;p=q;}程序错误返回ERROR。最后函数返回其头结点“head”。.查找输出函数:该函数的操作值为生成链表的头结点。在其函数内部输入题目中要求的“起始点”s,和“每次查找的数目”n。先用一个while循环找到s点，把其地址给指针变量p，再用一个循环，查找n个数目的节点，然后输出节点，再删除节点，释放节点。while(p-next!=p){for(i=1;in;i++){q=p;p=p-next;}printf(%5d,p-num);w=p;q-next=p-next;p=p-next;free(w);}主函数：在主函数内部先输入所要生成的m的节点数，定义一个linklist指针变量。先调用生成函数，再调用查找函数。完成程序实现intmain(intargc,char*argv[]){linklist*l;intm;printf(m=);scanf(%d/n,&m);l=creat(m);fun(l);system(PAUSE);return0;}主要流程图：调用creat（）函数模块创建链表调用主函数，输入m调用fun函数模块查找开始结束四、程序调试分析在程序调试过程中，creat（）函数的编写，关于next指针的指向，和删除节点的过程并没掌握清晰，导致生成的链表并不成功，后来参照课本上的生成程序找到了p-next的具体使用。q-next=p-next;句。在fun函数的编写过程中并没有考虑到i和n的关系“”和“=”没有弄清，导致少输出最后一个节点。同时在链表全部输出完后的条件也没有弄清，后来在程序分析过程中找到了结束条件p-next!=p，这是环表的结束条件。在这次的实验中，我掌握了链表的生成，删除，查找等功能，同时自己找到了环表的结束条件，掌握了链表的指针型的指向，和各节点之间的关系。五、用户使用说明打开函数，然后根据提示依次输入链表的节点数；m，开始序号：s；每次查找的个数：n；然后按“回车键”输入结果，再按任意键退出程序。六、程序运行结果七、程序清单#includestdio.h#includestdlib.h#defineERROR0#defineOK1typedefstructNODE{intnum;structNODE*next;}linklist;linklist*creat(intn)/*生成函数，返回为指针*/{linklist*p,*q,*head;inti=1;head=p=(linklist*)malloc(sizeof(linklist));/*创造头结点*/p-num=i;for(i=2;i=n;i++)/*循环建立环表，其中num为序号*/{q=(linklist*)malloc(sizeof(linklist));if(q==0)return(ERROR);q-num=i;p-next=q;p=q;}p-next=head;returnhead;/*返回头结点指针*/}fun(linklist*l)/*查找输出函数，输入值为环表头结点指针*/{intn,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;in;i++){q=p;p=p-next;}printf(%5d,p-num);w=p;q-next=p-next;/*从下一个节点开始再次循环*/p=p-next;free(w);}printf(%5d,p-num);printf(\n);returnOK;}intmain(intargc,char*argv[]){linklist*l;intm;printf(m=);scanf(%d/n,&m);l=creat(m);fun(l);system(PAUSE);return0;}