下载文档原格式
《数据结构》实验报告班级：姓名：学号：日期：08-10-20题目：约瑟夫环一、上机实验的问题和要求：问题描述：编号为1到n的n个人围成一圈，每人带一个密码c，以m为报数上限。
然后从第一个人开始顺时针自1开始报数，报到m的人出列，将其密码作为新的m值，从他的下一个人开始，同样顺时针自1开始报数，依次循环下去，直到所有的人都出列！要求得到依次出列的那些人的编号序列！基本要求：用C代码实现此活动，要求使用一定的算法进行操作，并最终通过程序运算出最后的结果！二、程序设计的基本思想，原理和算法描述：（包括程序的模块结构，数据结构，输入/输出设计，符号名说明等）基本思想：利用不带头结点单向循环链表模拟该活动，在实现了一切动作之后，运用一定的算法得到最终的结果。
程序的模块结构：定义了相关的结构体之后，主要有以下几大模块：1.建立由头指针指示的有n个结点的不带头结点的单向循环链表crt_CLinkList(H,n);2.寻找、输出、删除H单循环链表的第m个结点locfor(H,m);3.最后通过main函数体处理参数的输入与显示，并调用以上两函数，最终解决问题。
主要数据结构：单链的循环链表，即线性表的链式存储结构。
算法的伪码描述：结构体定义如下：typedef struct Lnode /*定义单链表*/{int number; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/算法的实现详见源程序。
输入/输出设计本程序并未采用任何二进制文件出入的方式，这点说明将在最后总结提到。
至于函数的出入口问题，在源程序及注释中将得到详细说明，这里不再赘述。
三、源程序及注释：(说明函数功能、入口及出口参数,其他)#include <stdio.h> /* 头文件*/#include <stdlib.h>#include <alloc.h>typedef struct Lnode /*定义单链表*/{int number; /*编号*/int cipher; /*密码*/struct Lnode *next; /*指针*/}Lnode,*CLinklist; /*重定向命名*/CLinklist H; /*Ｈ为全局单链表*/struct Lnode *crt_CLinkList(CLinklist H,int m) /*创建一个不带头结点的单向循环链表*/{ /*其中，Ｈ为全局单链表，m为链表结点总数*/ int i; /*循环记数用*/struct Lnode *ptr1; /*用于索引*/if((ptr1=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL) /*一旦动态内存分配失败，报错退出！*/ {perror("malloc");return ptr1;}H=ptr1; /*形成单个结点的单循环链表*/ptr1->next=H;for(i=1;i<m;i++) /*形成m个结点的不带头结点的单循环链表*/ {if((ptr1->next=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL){perror("malloc");ptr1->next=H;return H;}ptr1=ptr1->next; /*其中Ｈ指头，ptr指尾*/ptr1->next=H;}return H; /*返回成功新建的单链表Ｈ*/}void locfor(CLinklist H,int m) /*寻找输出删除链表Ｈ中的第m个结点*/{ /*H为全局链表，m为要查找删除的结点位置*/ int i; /*循环计数*/struct Lnode *ptr;for(i=1;i<=5;i++) /*考虑图形界面的美观问题*/printf("number\tcipher\t");i=1; /*初始化*/while(H->next!=H) /*只剩单个结点时停止循环，进行最后输出！*/ {if(m==1) /*考虑进行自身删除的情况，即m=1*/{for(ptr=H->next;ptr->next!=H;ptr=ptr->next);/*正因为是自身删除才要费大劲寻找其父结点*/printf("%-6d\t",H->number); /*找到后，先输出*/printf("%-6d\t",H->cipher);m=H->cipher; /*确定下一次寻找的m值*/ptr->next=H->next; *删除结点，即自身结点*/ptr=ptr->next;free(H); /*因为对于链表中的结点，每个之前都分配了内存，所以free是必要的*/H=ptr; /*不同于以下普通结点的删除，自身删除还要还原H*/i=1; /*i重置，以方便下一次的循环操作*/}else if(i==m-1) /*因为从自身开始即为1号，因为m-1,而不是m*/{ptr=H->next; /*结点的删除操作同于上面的情况!*/printf("%-6d\t",ptr->number);printf("%-6d\t",ptr->cipher);m=ptr->cipher;H->next=ptr->next;H=H->next;free(ptr);i=1;}else{H=H->next; /*若未找到，则继续遍历！*/i++;}}printf("%-6d\t",H->number); /*对于单个结点的单循环链表，进行最终的输出操作！*/ printf("%-6d",H->cipher);free(H); /*完成所有任务并释放所有内存占用！*/}void main() /*主函数接口*/{ /*调用所有函数，进行实验模拟，并得出实验结果！*/ int i,j,n=30,m,k;struct Lnode *ptr;randomize(); /*因为下面调用了random函数，故此处的初始化很有必要！*/ printf("Now the experiment will begin.You have two choices!\n");/*数据输入可以电脑随机，也可以自行输入*/printf("If you want to enter the datas all by yourself,please enter 1.\n");/*自行输入（方便检测程序问题）*/ printf("If you want to get the datas by the computer,please enter 0.\n"); /*电脑随机产生数据*/printf("Now your choice:"); /*用户选择*/scanf("%d",&j);while(j!=0&&j!=1) /*考虑程序的完善性，对于误输入的提示并报警！*/ {printf("\nYou enter is unillage!Please try again!\n");printf("Now your choice:"); /*重新输入*/scanf("%d",&j);}H=crt_CLinkList(H,n); /*初始化链表*/if(j==0) /*电脑随机充入数据*/for(i=1;i<=30;i++){H->number=i;H->cipher=rand(); /*随机函数*/H=H->next;}else /*此时选择实验者输入数据！*/{for(i=1;i<=30;i++){H->number=i;printf("Now number %d,please enter the cipher:",i);scanf("%d",&k);H->cipher=k;H=H->next;}}m=rand(); /*默认情况下，m随机产生*/printf("Do you want to enter the number m?Enter 1 to set or others cancel!\n");/*当然，如果想自已输，可以进行覆盖*/scanf("%d",&k);if(k==1) /*自行输入m值*/{printf("Please enter the number m:");scanf("%d",&m);}system("cls"); /*考虑屏幕大小，进行分屏显示*/printf("All followed are your datas!\n"); /*界面友善*/for(i=1;i<=5;i++)printf("number\tcipher\t");for(i=0;i<30;i++) /*显示所有处理前数据*/{printf("%-6d\t",H->number);printf("%-6d\t",H->cipher);H=H->next;}printf("And the number m is :%d\n",m);printf("\nAfter the program,the result is:\n");locfor(H,m); /*对所有数据进行实验处理，直至所有结点处理完！*/ getchar();printf("\nPress any key return!"); /*TC环境下，方便查看结果！*/getchar();}四、用户使用说明与测试运行结果：1．运行程序后，首先弹出界面，截图如右：理性化的选择：如果打1，则所有的cipher均由用户输入，这样方便对特殊数据进行程序测试！如果打0，那么所有的数据均由电脑产生！那如果打其他的呢？考虑到误输入，加了一个循环，以提高程序的健壮性！2．首先自行输入数据进行测试。
2010级数据结构实验报告实验名称：实验一——线性表（约瑟夫问题）学生姓名：在这我就不写了班级：**班内序号：**学号：**日期：2010年11月4日1．实验要求一、实验目的通过实现约瑟夫问题，掌握如下内容：1、熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法；2、学习指针、模板类、异常处理的使用；3、掌握线性表的操作实现方法；4、培养使用线性表解决实际问题的能力。
二、实验内容利用循环链表实现约瑟夫问题的求解。
约瑟夫问题如下：有n个人(n>=1)围坐在一个圆桌周围，把这n个人依次编号为1，…，n。
从编号是1的人开始报数，顺时针数到m的那个人出列，他的下一个然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列。
请问最后一个出列的人的编号。
2. 程序分析对于这个程序来说，首先要确定构造链表时所用的插入方法。
当数到m时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。
由于是循环计数，所以才采用循环列表这个线性表方式。
在这个程序中解决了存储问题后，之后最大的难点就是关于出列节点的逻辑判断。
由于我插入元素时是将rear指针中也存入了元素值，又增加了一个front指针，实际上是front 指针始终存在而rear指针有可能消除。
这样遇到的问题就是，假设p本身就是rear指针，那当移到下一位时就应该移动两位来跳过front这一个空节点。
这个是程序实现中容易发生逻辑错误的地方。
2.1 存储结构本实验中所用的存储结构为单链表。
以下即为单链表的存储结构示意图：front（2）非空单循环链表2.2 关键算法分析1、关键算法：（1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。
在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。
伪代码阐释如下：1)、在堆中建立新节点：Node<T> *s=new Node<T>;2)、将a[i]写入到新节点的数据域：s->data=a[i];3)、修改新节点的指针域：s->next=front->next;4)、修改头结点的指针域，将新节点加入到链表中：front->next=s;时间复杂度为：1；(2)、删除：首先通过p指针查找到所要删除的节点的前一个节点，继而通过q=p->next简单地删除掉。
数据结构实验⼀线性表数据结构与算法实验报告实验⼀：线性表操作实验—⽤循环链表实现约瑟夫环问题姓名：沈靖雯学号：2014326601094班级：14信科⼆班⼆〇⼀六年⼗⽉实验⼀线性表操作实验【实验内容】实现线性表的初始化和插⼊删除操作提⾼部分实验：⽤循环链表实现约瑟夫环问题【实验⽬的】掌握线性表的顺序映象和链式映象⽅式，能熟练掌握链表结构的使⽤。
【问题描述】⼀个旅⾏社要从n 个旅客中选出⼀名旅客，为他提供免费的环球旅⾏服务。
旅⾏社安排这些旅客围成⼀个圆圈，从帽⼦中取出⼀张纸条，⽤上⾯写的正整数m(要求：⽤C 或C++语⾔实现，对某个给定的n 和m （例如n=7和m=3），给出被淘汰出列的旅客编号序列，以及最终的幸存者。
要求实验结果上机演⽰，最终以实验报告（附原程序）的⽅式递交。
【问题的实现】⼀、线性表初始化和插⼊删除操作（1）抽象数据类型ADT SqList {数据对象: 0}n n,,1,2,3,i ElemSet,a |{a i i≥?=∈=D数据关系： n},2,3,i D,a ,a |a ,a {1i 1-i i 1-i ?=∈=R 基本操作： InitList_Sq(&L)操作结果：构造⼀个空的线性表L 。
GetElem(L,i,&e)初始条件：线性表L 已存在，）（L L istLength i 1≤≤。
操作结果：⽤e 返回L 中第i 个元素的值。
ListInsert_Sq(&L,i,e)初始条件：线性表L 已存在,1istLengthi 1+≤≤）（L L 。
操作结果：在L 中第i 个位置之前插⼊新数据元素e ，L 长度加1。
ListDelete_Sq(&L,i,e)初始条件：循环链表L 已存在且⾮空，）（L L istLength i 1≤≤。
操作结果：删除L 第i 个数据元素，⽤e 返回其值，L 长度减1。
ListPrint_Sq (&L )初始条件：线性表L 已存在。
实验一：约瑟夫问题求解一、问题描述1、实验题目：约瑟夫（Josephus）问题的一种描述是：编号为1，2，……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上线值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。
2、基本要求：试设计一个程序，按出列顺序印出个人编号。
3、测试数据：m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4。
ｍ的初值为6，正确的出列顺序应为：6，1，4，7，2，3，5。
二、需求分析１、本程序用来求出含有密码的约瑟夫问题，可以输出所有人的出列顺序。
2 、程序运行后显示提示信息，提示用户输入一圈的人数n，接着输入每个人的密码，最后提示输入初始密码。
3、用户输入完毕后，程序自动输出运算结果。
三、概要设计1、设计思路n个人围成一圈，每个人的手中都有一个密码，这个密码决定了下一次报数的上限。
游戏规则：①给定一个初始密码②循环报数，报到密码值的人要出列，依次类推，直到所有的人都出列本程序要求输入的内容：n个人的密码及初始密码；本程序要求输出的内容：n个人出列的顺序。
2、数据结构为了实现上述功能，可以采用链式存储结构。
采用链式存储结构，定义了一个存储个人信息的结构体，及两个自定义函数，分别用于创建链表和约瑟夫出列操作。
①链表抽象数据类型的定义： #define SLNODE struct slnodeADT SLNODE{数据对象：D={ i a |i a ∈SLNODE, i=1,2,3.... }数据关系：R=φ}ADT SLNODE;②自定义函数:void create_SLnode(SLNODE *p,int n)//创建队列{ 创建链表，为N 个人分配密码 }void Josef(SLNODE *p,int n)//进行约瑟夫操作{输入初始密码m;for(){ 将出列的结点删除，并输出出列序号；}}③本程序的保护模块：结构体模块主程序模块自定义函数模块调用关系：3、程序设计主要算法的流程图：create_SLnode( )算法流程图Josef( )算法流程图四、详细设计1、元素类型、结点的类型及指针#define SLNODE struct slnodeSLNODE//每个结点的结构体{int num;//num代表序号int code;//code代表密码SLNODE *next;};2、自定义函数：void create_SLnode(SLNODE *p,int n)//创建队列，并将其尾指针指向第一个序号{SLNODE *r,*s;s=p;int i,m;cout<<"请给这"<<n<<"个人分配密码："<<endl;for(i=0;i<n;i++){cout<<"请给第"<<i+1<<"个人输入密码："<<endl;cin>>m;r=(SLNODE *)malloc(sizeof(SLNODE));r->code=m;r->num=i+1;r->next=s->next;s->next=r;s=s->next;}p=p->next;s->next=p;}void Josef(SLNODE *p,int n)//进行约瑟夫操作{p=p->next;int m;int i,j;SLNODE *r;cout<<"请输入初始密码："<<endl;cin>>m;cout<<"依次出列的序号为:"<<endl;for(i=0;i<n-1;i++)p=p->next;for(i=0;i<n-2;i++){for(j=0;j<m-1;j++)p=p->next;cout<<(p->next)->num<<endl;m=(p->next)->code;r=p->next;p->next=r->next;}if(m%2==0)cout<<p->num<<endl<<(p->next)->num<<endl;elsecout<<(p->next)->num<<endl<<p->num<<endl;}3、主函数：int main(){SLNODE *p;int n;cout<<"请输入一圈的人数："<<endl;cin>>n;p=(SLNODE *)malloc(sizeof(SLNODE));p->next=NULL;create_SLnode(p,n);Josef(p,n);return 0;}4、函数的调用关系：主函数main()调用自定义函数void create_SLnode(SLNODE *p,int n);/*创建队列*/与void Josef(SLNODE *p,int n);/*进行约瑟夫操作*/。
华北#########学院数据结构实验报告2011～2012学年第二学期级计算机专业班级：学号：姓名：实验一线性表及其应用一、实验题目：线性表及其应用——约瑟夫环二、实验内容：1．设带头结点的单链表ha和hb中结点数据域值按从小到大顺序排列，且各自链表内无重复的结点，要求：（1）建立两个按升序排列的单链表ha和hb。
（2）将单链表ha合并到单链表hb中，且归并后的hb链表内无重复的结点，结点值仍保持从小到大顺序排列。
（3）输出合并后单链表hb中每个结点的数据域值。
代码：实验结果：struct Node{ int data;Node* next; };typedef Node Slink;void create(Slink* h);void show(Slink* h);void merge(Slink* ha,Slink* hb);#include<iostream.h>void main(){cout<<"创建链表ha"<<endl;Slink ha; ha.next =NULL;create(&ha);cout<<"链表ha的节点排列"<<endl;show(&ha);cout<<endl;cout<<"创建链表hb"<<endl;Slink hb; hb.next =NULL;create(&hb);cout<<"链表hb的节点排列"<<endl;show(&hb);cout<<endl;cout<<"合并后链表hb的节点排列"<<endl;merge(&ha,&hb);show(&hb);}void create(Slink* h){if(!h) return;int n=0;//节点总数int j=0;//累计创建结点个数cout<<"请输入创建节点的个数"<<endl;cin>>n;Node* F=h;//F始终指向tou节点Node* pre=h;//pre始终指向要插入位置的前一个节点while(j<n){Node* p=new Node;cout<<"请输入节点的数据"<<endl;cin>>p->data;//链表为空时if(!F->next ){ F->next =p;p->next =NULL;j++;continue;}//链表不空时while(pre->next ){ if(p->data <pre->next ->data ){ p->next =pre->next ;pre->next =p;pre=h;j++;break;}else if (p->data ==pre->next ->data){ cout<<"该值已存在，请重新输入"<<endl;break;}pre=pre->next ;}if(!pre->next ){ pre->next =p;p->next =NULL;j++;}}}void merge(Slink* ha,Slink* hb){ //p遍历ha,q遍历hbNode * p=ha->next ;Node * q=hb->next ;//pw始终指向新生成链表的最后一个结点Node * pw=hb;while(p&&q){ if((p->data)<(q->data)){ pw->next=p;p=p->next;pw=pw->next;continue;}if((p->data)>(q->data)){ pw->next=q;q=q->next;pw=pw->next;continue;}if((p->data)==(q->data)){ pw->next=q;p=p->next;q=q->next;pw=pw->next;continue;}}while(p){ pw->next=p;p=p->next;pw=pw->next;}while(q){ pw->next=q;q=q->next;pw=pw->next;}pw->next=NULL;}void show(Slink* h){Node* p=h->next ;while(p ){ cout<<p->data <<" ";p=p->next ;}cout<<endl;}2．约瑟夫（Joseph）问题。
数据构造实验实验一、约瑟夫环问题实验目的 1〕掌握线性表的存储构造； 2〕学会利用线性表解决实际问题。
实验内容编号为 1，2，┅，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码〔正整数〕。
一开场任选一个密码 m，从第一个人开场按顺时针方向自 1 开场顺序报数，报到 m 时停顿报数。
报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开场重新从 1 顺序报数，如此下去，直到所有人全部出列为止。
实验要求 1〕建立模型模拟约瑟夫环问题，确定存储构造，用单链表实现； 2〕输入 m 的初值，人数 n，输入每个人的密码；出圈的顺序请依次输出。
数据构造分析^p 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表。
链表的每个结点有两个域，分别是序号和其所持有的密码。
建立单链表后，根据算法找到相应的结点，对找到的结点进展输出，并把该结点从链表中删除，再释放该结点空间。
实验程序 #include // 实验数据: 总人数：6 初始密码：18 个人密码：2,1,4,2,4,8 #include // 出圈顺序：6,3,2,4,1,5 typedef struct LNode {intid,password;struct LNode *next;} LNode, *LinkList;void main{ int n,m,e,i,Flag=1;LinkList L,p,q,s;printf(“请输入总人数 n：n”);scanf(“%d”,&n);printf(“请输入初始密码 m：n”);scanf(“%d”,&m);for(i=1;i1 链接结点printf(“请输入第%d 个人的密码：n”,i);scanf(“%d”,&e);s->id=i;s->passwoed=e;p->next=s;p=s;} s->next=L;// 构成循环链表 p=q=L;//约瑟夫环问题----报数，依次出列while(Flag){ printf(“出圈顺序依次为：n”);for(i=1;inext;} //搜索第 m 个人if(p==q)Flag=0;//表示全部查找完毕 s=p;// 找到第 m 个人出列 q->next=p->next;p=p->next;// 指出下一次第一个要报数的人 m=s->password;// 更新 m 值 pri ntf(“第%d 个人出列，密码：%dn”,s->id,s->password);free(s);}} 实验二、数制转换和汉诺塔实验目的 1〕掌握栈的逻辑构造和物理存储构造； 2〕学会利用栈的特点解决实际问题。
2009级数据结构实验报告实验名称： 实验一 线性表学生姓名：班 级：班内序号：学 号：日 期： 2010年11月5日1．实验要求一、实验目的通过选择下面4个题目之一进行实现，掌握如下内容：● 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法；● 学习指针、模板类、异常处理的使用；● 掌握线性表的操作实现方法；● 培养使用线性表解决实际问题的能力。
二、实验内容4.题目4利用循环链表实现约瑟夫问题的求解。
约瑟夫问题如下：已知n 个人（n ≥1）围坐一圆桌周围，从1开始顺序编号。
从序号为1的人开始报数，顺时针数到m 的那个人出列。
他的下一个人又从1开始报数，数到m 的那个人又出列。
依次规则重复下去，直到所有人全部出列。
请问最后一个出列的人的编号。
2. 程序分析2.1 存储结构循环链表。
线性表简称表，是由零个或多个具有相同类型的数据元素构成的有限序列。
链表为了正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这两部分信息构成了实际的存储结构，称为结点。
如果将单链表的终端节点的指针域指向头结点，则整个链表构成一个环，成为单循环链表。
如图所示：2.2 关键算法分析1．关键算法约瑟夫问题的实质就是在含n 个元素的循环链表中依次删除第m 个元素，返回链表中rear最后一个元素值。
即用含n个元素的数组初始化循环链表，从第一个元素开始查找第m-1个元素，删除第m个元素，然后从第m+1个元素开始继续查找第m-1个元素，删除第m个元素，循环此过程直到链表中只剩下最后一个元素。
关键算法伪代码如下：[1] 用含n个元素的数组初始化循环链表，初始化指针p指向第一个结点；[2] 判断人数n或报数m是否为1；[2.1] 人数n或报数m为1，将人数n赋给x；[2.2] 当人数不为1时，进入循环；[2.2.1] 初始化计数器i=1；[2.2.2] 查找第m-1个元素，p指向第m-1个元素；[2.2.3] 初始化指针q指向p->next，p的指针域指向q的指针域，第m个元素摘链，删除q，指针p后移；[2.2.4] 人数n减1；[2.3] 尾指针rear指向最后的结点p，将此结点值赋给x；[3] 返回x的值。
数据结构实验报告—约瑟夫问题求解《计算机软件技术基础》实验报告 I —数据结构实验一、约瑟夫斯问题求解一、问题描述1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。
开始选择一个正整数作为报数上限m，从第一个人开始顺时针自1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。
2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。
3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8,4.m初值为6（正确的出列顺序应为 6,1,4,77,2,3）。
二、需求分析1. 本程序所能达到的基本可能：该程序基于循环链表来解决约瑟夫问题。
用循环链表来模拟n 个人围坐一圈，用链表中的每一个结点代表一个人和他所代表的密码。
在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。
重复上述过程，直至所有的结点被释放空间出列。
2. 输入输出形式及输入值范围：程序运行后提示用户输入总人数。
输入人数n 后，程序显示提示信息，提示用户输入第i个人的密码，在输入达到预定次数后自动跳出该循环。
程序显示提示信息，提示用户输入初始密码，密码须为正整数且不大于总人数。
3．输出形式提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。
用户输入完毕后，程序自动运行输出运行结果。
4.测试数据要求：测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8，4。
m初值为 6（正确的出列顺序应为6， 1， 4，7， 2， 3， 5）。
三、概要设计为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码信息，因此需要循环链表结构体这个抽象数据类型。
1．循环链表结构体抽象数据类型定义：ADT Node{数据对象：D={ai,bi,ci|ai∈ int,bi ∈ int,ci∈(Node*),i=1,2...,n,n ≥0}:数据关系： R=?基本操作：CreatList(int n)// Order(int m,node *l)}ADT node；构建循环单链表；// 输出函数，输出出列顺序并删除链表中的结点；2.ADT 的 C 语言形式说明：typedef struct Node{int num;//结点的数据域，存放编号；int word; //结点的数据域，存放密码；struct Node *next; //结点的指针域，存放指向下一结点的指针；}Node；Node *CreatList( )// 建立循环单项链表；void Order(Node *h) //输出出列顺序并删除结点；3.主程序流程及其模块调用关系:1） . 主程序流程：先提示用户输入相关数据：总人数，运行循环链表结构体模块，输入每个人持有的密码值，创建出新链表，运行输出函数模块，再输入初始密码m值，输出出列序列。
实验报告实验一线性表的基本操作及其应用一、实验目的1、复习C语言程序设计中的知识。
2、熟悉线性表的逻辑结构。
3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。
二、实验内容本次实验提供2个题目，如果实现第一个题目有困难，可做第二个题目题目一：约瑟夫环[问题描述]约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人可有代表本人的序号。
一开始任选一个正整数m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
试设计一个程序求出出列顺序。
[基本要求]利用单向链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
[测试数据]由学生任意指定。
如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；(报告上要求写出多批数据测试结果)[实现提示]程序运行后首先要求用户输入初始报数m，人数n,(设n≤30)。
然后输入各人的序号。
[选作内容]向上述程序中添加在顺序结构上实现的部分实验题目一：约瑟夫环一．需求分析1．利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
2．演示程序以用户和计算机的对话方式执行，即在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结构显示在其后。
3.程序执行的命令包括：1）输入报数上限值；2）输入人数以及所持密码；3）输出出列顺序；4）结束2）测试数据4.由学生任意指定。
如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；二．概要设计为实现上述程序功能，需建立单向循环链表以存储此结构。
为此，需要一个抽象数据结构类型。
1.链表结点的抽象数据类型定义为：ADT2.本程序包含三个模块：3）主程序模块；4）循环链表的创建模块——实现创建循环链表；5）出列操作的模块——实现最终的出列操作；各模块之间的调用关系如下：出列操作的模块<——主程序模块——>循环链表的创建模块三.详细设计1.元素类型，结点类型和指针类型struct Lnode{int password;struct Lnode *next;};typedef struct Lnode *LinkList;2. 子函数1，创建循环链表int Creatlist_L(LinkList &head,int n)程序的实现：int Creatlist_L(LinkList &head,int n){//利用引用调用得到头指针head;int i;LinkList p,q;printf("请依次输入各位密码：");for(i=1;i<=n;i++){if(i==1){//申请一个空间，将头指针head和指针p均指向第一个结点；head=p=(LinkList)malloc(sizeof(struct Lnode));if(p==0) return 0; //分配存储空间失败}else{q=(LinkList)malloc(sizeof(struct Lnode));if(q==0) return 0;p->next=q;//通过next将下一个结点和前一个结点连起来;p=q;}scanf("%d",&(p->password));//一次输入对应的密码；}p->next=head;//构成循环链表，并返回链表的头指针return 0;}void DeleteNode(LinkList head,int m,int n){LinkList p,q;int j,i;p=head;for(j=1;j<n;j++){//先出列前n-1个人，并依次释放其结点的空间；for(i=1;i<m;i++,p=p->next);//寻找第m个人；printf("%d ",p->password);p->password=p->next->password;//将后一个结点的数据全部赋值于当前p所指的结点q=p->next;p->next=p->next->next;//p指向其下一个的下个一结点，重新开始寻找；free(q);}printf("%d",p->password);//最后一个人出列，并释放其结点所占空间；free(p);} }scanf("%d",&(p->password));//一次输入对应的密码；}p->next=head;//构成循环链表，并返回链表的头指针return 0;}3.主函数的实现，对两个子函数的调用void main(){int n,m;LinkList List;printf("输入人数:");scanf("%d",&n);printf("输入值m:");scanf("%d",&m);Creatlist_L(List,n);DeleteNode(List,m,n);printf("\n");}4.函数的调用关系图反映了演示程序的层次结构：main——>Creatlist;main——>DeleteNode;四调试分析1.由于对引用调用理解的不透侧，导致刚开始修改了很长时间。
