天大数据结构实验报告一-约瑟夫环

数据结构上机实验报告题目：用单循环链表解决约瑟夫问题学生姓名学生学号学院名称计算机学院专业计算机科学与技术时间2013.10.7PAGE1PAGE1目录第一章、需求分析…………11.1原题表述……………11.2所选的要求及整体规划……………1第二章、概要设计…………22.1抽象数据类型…………22.2算法……………………2第三章、详细设计…………33.1程序代码………………3第四章、调试分析…………74.1调试工作………………74.2时间复杂度…………7第五章、测试结果…………85.1输入数据和输出数据样例…………8计算机学院2012级数据结构上机实验报告PAGE8第一章需求分析1.1原题表述设n个人围坐在一圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局者的下一人重新开始报数，数到第m个人，再让他出局······如此反复，直到所有的人全部出局为止。1.2所选的要求及整体规划 对于任意给定的n、s和m，求出这个n个人的出局序列，数据结构采用单循环链表。构造不带头结点的单循环链表。

第二章概要设计2.1抽象数据类型不带头结点的单循环链表2.2算法建立一个不带头结点的空循环链表，依次在链表中添加数据域为1~n的n个数据元素，此时指针head指向第一个元素，再用一个for循环让头指针head指向第s个元素，之后用while循环让head指向第m-1个元素，删除第m个元素，head指向第m+1个元素，直至链表中只剩一个元素。依次输出被删除的元素及最后剩余的元素。

第三章详细设计3.1程序代码#include<stdio.h>#include<malloc.h>typedefstructnode{ intdata; structnode*next;}node;//函数功能：构造不带头结点的循环链表并赋值1~n，头指针head指向第s个人node*create(intn,ints){ node*head; node*p,*q,*r;inti,j; if(n<=0)returnNULL;//若分配内存失败返回 //把长度为n的链表赋值1~n head=(node*)malloc(sizeof(node)); head->data=1; head->next=NULL; p=head; for(i=1;i<n-1;i++) { q=(node*)malloc(sizeof(node)); q->data=i+1; p->next=q; p=q; } //构造循环链表 q=(node*)malloc(sizeof(node)); q->data=n; p->next=q; q->next=head;//不带头结点 for(j=1;j<s;j++)//从第s个人开始数 { r=head->next; head=r; } returnhead;}intdel(node*head)//删除{ node*p,*q; if(head==NULL)return-1; p=head; q=p->next; p->next=q->next; p=q->next; free(q); head=p;return1;}intmain(){ intn,m,s,person; node*head,*r,*p; //输入n、m、s printf("Entern:\n"); scanf("%d",&n); printf("Enterm:\n"); scanf("%d",&m); printf("Enters:\n"); scanf("%d",&s); head=create(n,s);//head指向第s个人 while(head->next!=head)//循环结束后链表只剩一个元素 { //数到第m个删除，head指向m的前一个 for(inti=1;i<m-1;i++) { r=head->next; head=r; } person=head->next->data; printf("Number%disout\n",person); p=head->next->next; del(head); head=p; } person=head->data; printf("Number%disout\n",person); system("pause"