用单链表解决约瑟夫问题.doc
数据结构上机实验报告 题目：用单链表解决约瑟夫问题 学生姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 目 录 第一章 需求分析 11.1 原题表述 11.2 问题解决方案 1 第二章 概要设计 22.1 抽象数据类型 22.2 主要算法描述 22.3 主要算法分析 2 第三章 详细设计 33.1 程序代码 3 第四章 调试分析 54.1 出现的问题及解决方法 5 第五章 测试分析 65.1 测试样例 6 第六章 未来展望与思考 7计算机学院2013级数据结构上机实验报告第1章 需求分析1.1 原题表述一个旅行社要从n个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈，从帽子中取出一张纸条，用上面写的正整数m(<n)作为报数值。游戏进行时，从第s个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人被淘汰出列，然后从他顺时针方向上的下一个人开始重新报数，如此下去，直到圆圈中只剩下一个人，这个最后的幸存者就是游戏的胜利者，将得到免费旅行的奖励。1.2 问题解决方案 由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍要是围成一个圆圈，可以使用循环表；由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，应该选用效率较高的链表结构；为了程序指针每一次都指向一个具体的代表一个人的结点而不需要进行判断，链表不带表头结点。所以，对于所有人围成的圆圈所对对应的数据结构采用一个不带头结点的循环链表来描述。第二章 概要设计2.1 抽象数据类型ADT Josephus 数据对象：D = ai = ai | ai ElemSet,i = 1,2,3,n, n >= 0数据关系：S = < ai - 1 ,ai > | ai -1 ,ai D, i = 2,3,4,，n基本操作：CreatList（n）操作结果：构建一个含n个结点的单循环链表StartNum（s）初始条件：单循环链表已存在操作结果：将头指针指向第s个结点DeleteList（m）初始条件：单循环链表已存在操作结果：依次输出被删除的数到m的元素及最后剩余的元素开始2.2 主要算法描述被删除的数到m的元素及最后剩余的元素结束将头指针指向第s个结点构建含n个结点的单循环链表n, s, m 图 2-12.3 主要算法分析CreatList（n）一重循环 时间复杂度 = O(n)StartNum(s) 一重循环 时间复杂度 = O(n)DeleteList(m) 二重循环 时间复杂度 = O(m*n） 第三章 详细设计3.1 程序代码 #include<stdio.h> #include<malloc.h> typedef struct Josephus int data; struct Josephus *next; Josephus, *LinkList; LinkList p, r, last = NULL; /构造一个不带头结点的循环链表，并赋值1n void CreatList(int n) for(int i = 1; i <= n; i+) p = (LinkList)malloc(sizeof(Josephus); /申请一个新的链结点 p -> data = i;/存放第i个结点的元素 if(last = NULL) last = p; else r -> next = p; r = p; p -> next = last; p = last; /循环链表建立完成 /将头指针p指向第s个人 void StartNum(int s) for(int i = 1; i < s; i+) r = p; p = p -> next; /此时p指向第1个出发结点 /依次输出被删除的元素及最后剩余的元素。 void DeleteList(int m) while(p -> next != p) for(int i = 1; i < m; i+) r = p; p = p->next; /p指向第m个结点,r指向第m-1个结点 r -> next = p -> next;/删除第m个结点 printf("Number %d is outn", p->data);/依次输出删除结点的元素 free(p);/释放被删除结点的空间 p = r -> next;/p指向新的出发结点 printf("Number %d is outn", p->data);/输出最后一个结点的元素 int main() int n, m, s; printf("Enter n:n"); scanf("%d", &n); printf("Enter m:n"); scanf("%d", &m); printf("Enter s:n"); scanf("%d", &s); CreatList(n); StartNum(s); printf("* Solve Josephus Problem *n"); DeleteList(m); printf("* END *n"); return 0; 第四章 调试分析4.1 出现的问题及解决方法1. 由于对循环链表算法的理解不够透彻，在构建循环链表的前期，指针指向混乱，导致程序无法通过编译。2、由于建立的是带头结点的单循环链表，导致输出的结果许多是错的，删除头结点，即建立的是不带头结点的单循环链表解决。3、运行出现输出元素顺序与样例不同，调试时发现数数出错了，改为每次数 m-1 次。 4、程序运行停止前出现错误对话框，百度发现可能是内存泄露的原因。5、在循环链表的使用中，由于指针使用占主导地位，理解节点的前后关系有点复杂，偶尔会出现小错误。以后吸取教训，在复杂循环时，最好通过图形的辅助，以使编程过程思路清晰。第五章 测试分析5.1 测试样例 测试样例 1：输入m = 10，n = 4，s = 3图 5-1 测试样例 2：输入m = 13， n = 3， s = 4图 5-2第六章 未来展望与思考通过这次数据结构编程实验，我初步了解了约瑟夫问题的求解方法，并熟悉了带尾指针的单循环链表，练习了利用尾插法构建链表的方法。在约瑟夫问题解决的过程中，复习了链表的出列操作，并通过编译时暴露出的问题，对指针使用方面存在的盲点进行了及时的查漏补缺，有了许多收获。总而言之，通过这次试验，不仅让我对这段时间内所学的知识有了更好的理解，而且对自己的编程能力也有所提高。发现在解决问题的过程中还有很多不会的地方，在编程和写报告的过程中曾多次遇到各种各样的问题，发现自己的编程能力亟待提高。通过与同学们的交流以及自己思考，最终得到解决并顺利完成了此次作业。6
