搜索
《数据结构》实验报告实验课程：线性表的应用专业：**********年级（班级）：******姓名：***学号：******实验报告实验名称约瑟夫环问题实验时间实验地点指导教师一、实验目的：1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4.通过本章实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。二、实验内容：【问题描述】设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人又出列，如此下去，直到所有的人都出列为止。试设计确定他们的出列次序序列的程序【基本要求】选择单向循环链表或循环数组作为存储结构模拟整个过程，并依次输出出列的各人的编号。【实现提示】由于问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。程序运行之后，首先要求用户指定初始报数的上限值，可以N〈=30，此题中循环链表可以不设头结点，而且必须注意空表和“非空表”的界限。如N=8，M=4时，若从第一人开始，设每个人的编号依次是1，2，3，……..开始报数，则得到的出列次序为4，8，5，2，1，3，7，6。三、实验程序：#includestdio.h#includemalloc.h#includestdlib.h/*宏定义和单链表类型定义*/#defineListSize100typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}ListNode,*LinkList;/*函数声明*/LinkListCreateCycList(intn);/*创建一个长度为n的循环单链表的函数声明*/voidJosephus(LinkListhead,intn,intm,intk);/*在长度为n的循环单链表中，报数为编号为m的出列*/voidDisplayCycList(LinkListhead);/*输出循环单链表*/voidmain(){LinkListh;intn,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);}voidJosephus(LinkListhead,intn,intm,intk)/*在长度为n的循环单链表中，从第k个人开始报数，数到m的人出列*/{ListNode*p,*q;inti;p=head;for(i=1;ik;i++)/*从第k个人开始报数*/{q=p;p=p-next;}while(p-next!=p){for(i=1;im;i++)/*数到m的人出列*/{q=p;p=p-next;}q-next=p-next;/*将p指向的结点删除，即报数为m的人出列*/printf(%4d,p-data);free(p);p=q-next;/*p指向下一个结点，重新开始报数*/}printf(%4d\n,p-data);}LinkListCreateCycList(intn)/*宏定义和单链表类型定义*/{LinkListhead=NULL;ListNode*s,*r;inti;for(i=1;i=n;i++){s=(ListNode*)malloc(sizeof(ListNode));s-data=i;s-next=NULL;if(head==NULL)head=s;elser-next=s;r=s;}r-next=head;returnhead;}voidDisplayCycList(LinkListhead)/*输出循环链表的每一个元素*/{ListNode*p;p=head;if(p==NULL){printf(该链表是空表);return;}while(p-next!=head)/*如果不是最后一个结点，输出该结点*/{printf(%4d,p-data);p=p-next;}printf(%4d\n,p-data);/*输出最后一个结点*/}四、实验结果及分析：五、感想与体会：做这次数据结构实验，不仅让我对这段时间内所学的知识有了更好的理解，而且对自己的编程能力也有所提高。发现在解决问题的过程中还有很多不会的地方，在编程和写报告的过程中曾多次遇到各种各样的问题，发现自己的编程能力亟待提高。通过与同学们的交流以及自己思考，最终得到解决并顺利完成了此次作业。六、得分：指导教师评语：□实验目的明确；□操作步骤正确；□设计文稿符合要求；□实验结果正确；□实验分析总结全面；□实验报告规范；评阅教师签名：