北理工数据结构上机实验报告1

数据结构上级实验报告1——采用单向环表实现约瑟夫环一实验目的采用单向环表实现约瑟夫环二实验内容请按以下要求编程实现：①从键盘输入整数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)概要设计抽象数据类型：structnode{intnumber;structnode*next;};宏：无主函数流程与各函数模块调用关系：创建头结点=〉输入链表的长度m=〉调用create函数建立链表=〉输入首次定位的节点s以及间隔数n=〉调用deal函数处理链表=〉结束函数模块间无彼此调用关系(2)详细设计建立链表算法实现：voidcreate(node*head,intm){node*p,*q;inti=1;for(;m0;m--){p=(node*)malloc(sizeof(node));if(p==NULL)exit(0);p-number=m;p-next=head-next;head-next=p;if(i){q=p;i--;}}q-next=head-next;}处理链表算法实现：voiddeal(node*head,intm,ints,intn){node*p,*q;intcount=1,tag=0;p=head;while(s--){p=p-next;}while(tag!=m){if(count==n){printf(%d-,p-number);for(q=p-next;q-next!=p;q=q-next);q-next=p-next;p=p-next;q=q-next;count=1;tag++;}else{p=p-next;count++;}}printf(-end\n);}主函数代码实现：intmain(){intm,s,n;node*head,*p;p=(node*)malloc(sizeof(node));p-next==NULL;head=p;printf(pleaseinputnumberm:\n);scanf(%d,&m);create(head,m);printf(pleaseinputnumbers(1=s=m):\n);scanf(%d,&s);printf(pleaseinputnumbern:\n);scanf(%d,&n);deal(head,m,s,n);system(pause);}四程序调试分析1在deal函数中进行对p节点的删除操作时出现问题，定位p的前一个节点q时，依旧采用了head指针从头遍历的方法，但是忽略了在函数操作中会删除掉头结点，这样head指针指向位置改变不能得到正确结果。所以改用q=p-next从p后节点遍历的方法能够一直正确的获得p的前一节点的位置。五用户使用说明双击exe程序后，软件提示依次输入m，s，n的值；m为链表总长度，为任意正整数；s为第一次定位的节点位置，其值应满足1=s=m的正整数；n为间隔的数目，为任意正整数；输入后即可获得结果。六程序运行结果七程序清单#includestdio.h#includestdlib.hstructnode//定义链表{intnumber;structnode*next;};voidcreate(node*head,intm)//创建包含m个数字的环形表{node*p,*q;inti=1;for(;m0;m--){p=(node*)malloc(sizeof(node));if(p==NULL)exit(0);p-number=m;p-next=head-next;head-next=p;if(i){q=p;i--;}}q-next=head-next;//将最后一个节点指向头结点，实现环形表}voiddeal(node*head,intm,ints,intn)//处理链表，完成删除及输出{node*p,*q;intcount=1,tag=0;p=head;while(s--){p=p-next;}//将p指向首次定位的第s个节点while(tag!=m){if(count==n){//如果正好数到n值，则进行输出、删除操作并重置计数器printf(%d-,p-number);for(q=p-next;q-next!=p;q=q-next);q-next=p-next;p=p-next;q=q-next;count=1;tag++;}else{p=p-next;count++;}//如果没有到n值，则继续循环链表}printf(-end\n);}intmain(){intm,s,n;node*head,*p;p=(node*)malloc(sizeof(node));p-next==NULL;head=p;//定义头结点printf(pleaseinputnumberm:\n);scanf(%d,&m);//输入m值——链表长度create(head,m);//创建该链表printf(pleaseinputnumbers(1=s=m):\n);scanf(%d,&s);//输入s值——首次定位节点printf(pleaseinputnumbern:\n);scanf(%d,&n);//输入n值——间隔数deal(head,m,s,n);//处理链表，完成输出，删除操作system(pause);}