南京工业大学 数据结构 实验报告2

《南京工业大学 数据结构 实验报告2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验报告二题目：约瑟夫环班级：电子1102学号：28姓名：杨筠日期：6月1日程序名：一、上机实验的问题和要求：约瑟夫环（《数据结构题集》P791.2）：约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新报数，如此下去，直至所有人全部出列为止。设计一个

2、程序求出出列顺序。利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）此程序实现的方法是建立一个没有表头结点循环链表，然后对循环链表进行相关操作，模拟整个报数及出列过程。将每个人的信息用一个结点存储，包括三个信息，一是他的编号number,二是他持有的密码code,三是指向下一结点的指针。其中编号是一开始按照相邻顺序编号的，密码可以设置，需要输入数值。typedefstructLNode{in

3、tnumber;//编号intcode;//持有密码structLNode*next;//指向下一结点的指针}LNode,*LinkList;主要过程由以下两个函数实现voidCreateList(LinkList&L,int&n);//创建循环链表voidJoseph(LinkList&L,int&n);//约瑟夫环解决方案主函数为voidmain(void){LinkListL;intn;printf("请输入人数：");scanf("%d",&n);//设置人数CreateList(L,n);//

4、创建循环链表Joseph(L,n);//约瑟夫环解决方案}6首先要创建循环链表，在确定人数基础上编号，并输入每个人的密码，连接成一个循环链表，头指针L指向编号为1号的结点。/**********************************************************************创建循环链表**********************************************************************/voidCreateList(LinkL

5、ist&L,int&n){printf("将这%d个人编号为1-%d号。请依次输入这%d个人的密码:",n,n,n);LinkListq;for(inti=1;i<=n;i++){LinkListp=(LinkList)malloc(sizeof(LNode));//创建新结点用p指向它p->number=i;//编号scanf("%d",&p->code);//输入持有密码p->next=NULL;if(i==1)L=q=p;//若是第一个结点，直接用头指针指向它else{q->next=p;//

6、将p指向的结点加入链表q=q->next;//q始终保持指向最后的结点}}q->next=L;//q指向的最后的结点指针域指向头结点，则成为循环链表}约瑟夫环解决方案具体实现方案：第一次报数默认为从1号开始报数，需设置报数上限值m,报m的人出列，然后从出列的人后面一个人开始下一轮报数，且报数上限值m变为出列的人持有密码。即第一次由头指针L开始向后数到第m-1个结点，删掉第m-1个结点的后继结点，即第m个结点，（可由一个指针q反馈回第m个结点，以便读取被删除结点的信息），这时第m-1个结点直接指向第m+1

7、个结点，同时让头指针L也指向第m+1个结点。因为下一轮报数时将从第m+1个结点开始，即还是L指向的结点开始。第二轮报数首先将m值修改为刚刚被删除结点的持有密码，即m=q->code再进行和第一轮报数相同的操作。以后每轮报数如次反复执行，直到所有结点被删除结束。这个过程需要一个删除函数来实现，函数功能是删除以头指针L开始第i个结点，q返回结点指针，并改变头指针位置为下一轮报数的第一个结点。/**********************************************************

8、************删除以L为头第i个结点，q返回结点指针,改变头指针位置**********************************************************************/voidDeleteList(LinkList&L,inti,LinkList&q){if(i==1)DeleteList(L,i+LengthList(L),q);//i=1时需要特殊处理else{LinkListp=L;