《用单链表解决约瑟夫问题.doc》由会员分享，可在线阅读，更多相关《用单链表解决约瑟夫问题.doc（9页珍藏版）》请在三一文库上搜索。
1、数据结构上机实验报告 题目：用单链表解决约瑟夫问题 学生姓名 学生学号 学院名称 计算机学院 专 业 计算机科学与技术 时 间 目 录 第一章 需求分析 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个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅
2、行社安排这些旅客围成一个圆圈，从帽子中取出一张纸条，用上面写的正整数m(= 0数据关系：S = | 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）一重循环
3、 时间复杂度 = O(n)StartNum(s) 一重循环 时间复杂度 = O(n)DeleteList(m) 二重循环 时间复杂度 = O(m*n） 第三章 详细设计3.1 程序代码 #include #include 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 data = i;/存放第i个结点的元素 i
4、f(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 next; /此时p指向第1个出发结点 /依次输出被删除的元素及最后剩余的元素。 void DeleteList(int m) while(p - next != p) for(int i = 1; i next; /p指向第m个结点,r指向第m-1个结点 r - next = p - next;/删除第m个结点 pri
5、ntf(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(* Sol
6、ve Josephus Problem *n); DeleteList(m); printf(* END *n); return 0; 第四章 调试分析4.1 出现的问题及解决方法1. 由于对循环链表算法的理解不够透彻，在构建循环链表的前期，指针指向混乱，导致程序无法通过编译。2、由于建立的是带头结点的单循环链表，导致输出的结果许多是错的，删除头结点，即建立的是不带头结点的单循环链表解决。3、运行出现输出元素顺序与样例不同，调试时发现数数出错了，改为每次数 m-1 次。 4、程序运行停止前出现错误对话框，百度发现可能是内存泄露的原因。5、在循环链表的使用中，由于指针使用占主导地位，理解节点的前
7、后关系有点复杂，偶尔会出现小错误。以后吸取教训，在复杂循环时，最好通过图形的辅助，以使编程过程思路清晰。第五章 测试分析5.1 测试样例 测试样例 1：输入m = 10，n = 4，s = 3图 5-1 测试样例 2：输入m = 13， n = 3， s = 4图 5-2第六章 未来展望与思考通过这次数据结构编程实验，我初步了解了约瑟夫问题的求解方法，并熟悉了带尾指针的单循环链表，练习了利用尾插法构建链表的方法。在约瑟夫问题解决的过程中，复习了链表的出列操作，并通过编译时暴露出的问题，对指针使用方面存在的盲点进行了及时的查漏补缺，有了许多收获。总而言之，通过这次试验，不仅让我对这段时间内所学的知识有了更好的理解，而且对自己的编程能力也有所提高。发现在解决问题的过程中还有很多不会的地方，在编程和写报告的过程中曾多次遇到各种各样的问题，发现自己的编程能力亟待提高。通过与同学们的交流以及自己思考，最终得到解决并顺利完成了此次作业。6