数据结构约瑟夫环实验报告(共7页).doc

《数据结构约瑟夫环实验报告(共7页).doc》由会员分享，可在线阅读，更多相关《数据结构约瑟夫环实验报告(共7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构实 验 报 告实 验 课 程： 线性表的应用 专 业： * 年级（班级）： * 姓 名： * 学 号： * 实 验 报 告实验名称约瑟夫环问题实验时间实验地点指导教师一、实验目的：1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4. 通过本章实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。二、实验内容：【问题描述】设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的

2、下一个人开始重新报数，数到M的人又出列，如此下去，直到所有的人都出列为止。试设计确定他们的出列次序序列的程序【基本要求】选择单向循环链表或循环数组作为存储结构模拟整个过程，并依次输出出列的各人的编号。【实现提示】 由于问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。程序运行之后，首先要求用户指定初始报数的上限值，可以N=30，此题中循环链表可以不设头结点，而且必须注意空表和“非空表”的界限。如 N=8，M=4时，若从第一人开始，设每个人的编号依次是1，2，3，.开始报数，则得到的出列次序为4，8，5，2，1，3，7，6。 专心-专注-专业三、实验

3、程序：#include #include#include/*宏定义和单链表类型定义*/#define ListSize 100typedef int DataType;typedef struct NodeDataType data;struct Node *next;ListNode,*LinkList;/*函数声明*/LinkList CreateCycList(int n);/*创建一个长度为n的循环单链表的函数声明*/void Josephus(LinkList head,int n,int m,int k); /*在长度为n的循环单链表中，报数为编号为m的出列*/void Displ

4、ayCycList(LinkList head);/*输出循环单链表*/void main() LinkList h; int n,k,m; printf(输入环中人的个数n=); scanf(%d,&n); printf(输入开始报数的序号k=); scanf(%d,&k); printf(报数为m的人出列m=); scanf(%d,&m); h=CreateCycList(n); Josephus(h,n,m,k); void Josephus(LinkList head,int n,int m,int k)/*在长度为n的循环单链表中，从第k个人开始报数，数到m的人出列*/ ListNo

5、de *p,*q; int i; p=head; for(i=1;inext; while(p-next!=p) for(i=1;inext; q-next=p-next; /*将p指向的结点删除，即报数为m的人出列*/ printf(%4d,p-data); free(p); p=q-next; /*p指向下一个结点，重新开始报数*/ printf(%4dn,p-data);LinkList CreateCycList(int n)/*宏定义和单链表类型定义*/ LinkList head=NULL; ListNode *s,*r; int i; for(i=1;idata=i; s-nex

6、t=NULL; if(head=NULL) head=s; else r-next=s; r=s; r-next=head; return head;void DisplayCycList(LinkList head)/*输出循环链表的每一个元素*/ ListNode *p; p=head; if(p=NULL) printf(该链表是空表); return; while(p-next!=head)/*如果不是最后一个结点，输出该结点*/ printf(%4d,p-data); p=p-next; printf(%4dn,p-data);/*输出最后一个结点*/四、实验结果及分析：五、感想与体会： 做这次数据结构实验，不仅让我对这段时间内所学的知识有了更好的理解，而且对自己的编程能力也有所提高。发现在解决问题的过程中还有很多不会的地方，在编程和写报告的过程中曾多次遇到各种各样的问题，发现自己的编程能力亟待提高。通过与同学们的交流以及自己思考，最终得到解决并顺利完成了此次作业。六、得分：指导教师评语： 实验目的明确； 操作步骤正确； 设计文稿符合要求； 实验结果正确； 实验分析总结全面； 实验报告规范； 评阅教师签名：