数据结构约瑟夫环实验报告_免费下载.docVIP

工商学院 数据结构 实验报告 年级 2012 学号 2012007554 姓名 刘怡然 成绩 专业 电气 实验地点 B3-401 指导教师 许文强 实验项目 约瑟夫环问题 实验日期 2013.10.21 一、实验目的 本实验的目的是进一步理解线性表的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 设编号为1、2、……n的n个人围坐一圈，约定编号为k（1=k=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 三、实验步骤 1、实验问题分析 由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为L，浮标指针p，并根据具体情况移动。 功能（函数）设计 由于函数功能比较简单，对子模块可以不再细分，而使用主函数main()做数组的初始化和输出工作，使用函数Josephus()做删除结点和输出顺序的工作，使用函数Move()做移动链表指针的工作，使用Creat_Linklist()做初始化链表的工作。 实验结果（程序）及分析 实验主要代码 Node.h typedef struct Node{ int number; struct Node *next; }LNode,*Linklist; Main.cpp #include Node.h #include iostream.h #include stdio.h Linklist Creat_Linklist(int x); void Josephus(Linklist L,int y,int z,int []); Linklist Move(Linklist L,int x); int main() { Linklist L;int n,k,m; int ASA[100]; cout人数上限为100，请输入人数n：; cinn; L=Creat_Linklist(n); printf(请输入起点k，循环基数m,逗号隔开：); scanf(%d,%d,k,m); if(k=0||kn) {cout你输入的K值不符合题目要求！;return 0;} Josephus(L,k,m,ASA); cout出列顺序为：endl; for(int i=0;in;i++) coutASA[i]endl; return 1; } Linklist Creat_Linklist(int x) { Linklist L; LNode *s,*r; L=r=NULL; int i; for(i=1;i=x;i++) { s=new LNode; s-number=i; if(L==NULL) L=s; else r-next=s; r=s; } r-next=L; return L; } void Josephus(Linklist L,int y,int z,int a[]) //头指针，起点，循环基数，输出数组 { LNode *p,*q;Linklist s;int i=0; p=L; p=Move(p,y); while(p-next!=p) { p=Move(p,z); q=p; while(q-next!=p) //使用q记录p的前驱节点，为接下来p所指向的节点做准备 q=q-next; a[i]=p-number; s=q-next; q-next=p-next; //删除节点，将断链接上 delete s; p=q-next; i++; } a[i]=p-number; } Linklist Move(Linklist L,int x) //移动指针x次 { LNode *p; p=L; for(int i=1;ix;i++) p=p-next; return p; } 实验数据与输出 调试过程中出现的问题以及解决策略。 在删除出栈节点前，要先记录它的前驱节点，保证删除后循环链表是完整的。