数据结构实验报告1.doc

计算机科学与工程系实验（一）实验名称线性表基本操作软件环境Windows98/2000, VC+6.0或turbo C硬件环境P以上微型计算机实验目的理解线性表的逻辑特点，掌握顺序表、链表存储结构和基本操作的实现。实验内容（应包括实验题目、实验要求、实验任务等）约瑟夫(Josephus)环问题设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，如此反复直到所有的人全部出局为止。 下面要解决的约瑟夫(Josephus)环问题是：对于任意给定的n，s和m，求出这n个人的出局序列。要求以单循环链表作为存储结构，实现约瑟夫环问题。然后使用n=9，s=1，m=5，以及n=9，s=1，m=10作为输入数据，检查你的程序的正确性和健壮性。实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程：1. 创建单循环链表L：为了便于实现约瑟夫环问题，链表没有头指针，用尾插入法创建链表，从空链表L开始，设计工作指针p作为每次读入一个元素申请的一个新结点，将读入的数据存到新的结点p的数据域中，然后设计辅助工作指针r作为链表L的尾指针，把新的结点插入到当前链表的尾结点，重复上述过程，直到输入n个元素为止，最后将尾结点的指针指向L。其算法的伪代码如下：1.1空链表L，工作指针r初始化，输入数据元素的个数n：r=L；L-data=11.2用i来记录循环的次数，i的初始值为2，循环直到i=n工作指针p初始化：p-data=i ；将p插入到链表L的尾端：r-next=p；指针r指向链表尾结点：r=p；1.3构成循环链表，将尾结点r指向第一个结点L：r-next=L；2. 运用单循环链表结构实现约瑟夫环问题：设计工作指针p指向当前计数结点，为实现删除结点p的操作，再设计辅助工作结点q指向结点p的后继结点，计数器从1开始计数。其算法的伪代码如下：2.1工作指针p初始化，计数器count初始化：p=L；count=1；2.2输出单循环链表中的每一个元素；2.3循环直到单循环链表中只有一个结点p2.3.1当count=m时，即p指向的结点为要删除的结点时初始化q：q=p-next；输出结点p的值；删除p所指向的下一个结点，即q所指向的结点： p-next= p-next-next；交换p与q所指结点的值并删除结点q，即删除了结点p所指元素；计数器变为1；2.3.2 工作指针p后移，计数器count+1；2.4输出链表中剩余的最后一个结点，并删除。3. 在主函数中调用各个函数，完成程序。结论：实验中，输入9,1,5，输出5 1 7 4 3 6 9 2 8，输入9,1,10，输出1 3 6 2 9 5 7 4 8。实验中曾出现的问题：构造单循环链表时，运用了头插法，最后无法使尾结点指向第一个结点，改用尾插法；在使用count计数时，没有清零使count变为1，结果程序运行后，无法输出约瑟夫环的出圈顺序，在if执行语句中增加语句count=1；使用while循环时，忘记L为循环链表了，终止条件为p为空，结果程序运行出错，将循环执行的条件改为p-next不为p。附录（可包括源程序清单或其它说明）#include#include#includestdio.htypedef struct LNode /链表类型int data;struct LNode *next;LNode,*LinkList;void createLink(LinkList &L,int n); /创建链表void printList(LinkList L,int n); /输出链表void Josephus(LinkList &L,int s,int m); /约瑟夫环void createLink(LinkList &L,int n)LinkList p,r;L=(LinkList)malloc(sizeof(LNode);r=(LinkList)malloc(sizeof(LNode);r=L;L-data=1;L-next=NULL;for(int i=2;idata=i;p-next=NULL;r-next=p;r=p;r-next=L;void Josephus(LinkList &L,int s,int m)LinkList p,q;int count=1,t;p=L;for(int i=1;inext;while(p-next!=p)if(count=m)q=p-next;p-next=p-next-next;coutdatadata;p-data=q-data;delete q;count=1;count+;p=p-next;coutdataendl;delete p;void printList(LinkList L,int n)LinkList p;p=L;for(int i=0;in;i+)coutdatanext;coutendl;void main()LinkList L;int n,s,m;cout请输入Josephus环所需要的总人数n，起始点s，数过的人数mn;cins;cinm;