郭艳慧 实验一 线性表 08-10-20
《数据结构》实验报告
班级： 学号：
姓名： 日期： 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; /*Ｈ为全局单链表*/ 算法的实现详见源程序。
输入/输出设计
本程序并未采用任何二进制文件出入的方式，这点说明将在最后总结提到。至于函数的出入口问题，在源程序及注释中将得到详细说明，这里不再赘述。
1
郭艳慧 实验一 线性表 08-10-20
三、源程序及注释：
(说明函数功能、入口及出口参数,其他)
#include
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(\ return ptr1; }
H=ptr1; /*形成单个结点的单循环链表*/ ptr1->next=H;
for(i=1;i if((ptr1->next=(struct Lnode *)malloc(sizeof(struct Lnode)))==NULL) { perror(\ 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++) /*考虑图形界面的美观问题*/ 2 郭艳慧 实验一 线性表 08-10-20 printf(\ i=1; /*初始化*/ while(H->next!=H) /*只剩单个结点时停止循环，进行最后输出！*/ { if(m==1) /*考虑进行自身删除的情况，即m=1*/ { for(ptr=H->next;ptr->next!=H;ptr=ptr->next);/*正因为是自身删除才要费大劲寻找其父结点*/ printf(\ /*找到后，先输出*/ printf(\ 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(\ printf(\ m=ptr->cipher; H->next=ptr->next; H=H->next; free(ptr); i=1; } else { H=H->next; /*若未找到，则继续遍历！*/ i++; } } printf(\ /*对于单个结点的单循环链表，进行最终的输出操作！*/ printf(\ free(H); /*完成所有任务并释放所有内存占用！*/ } void main() /*主函数接口*/ { /*调用所有函数，进行实验模拟，并得出实验结果！*/ int i,j,n=30,m,k; struct Lnode *ptr; randomize(); /*因为下面调用了random函数，故此处的初始化很有必要！*/ printf(\ /*数据输入可以电脑随机，也可以自行输入*/ 3 郭艳慧 实验一 线性表 08-10-20 printf(\自行输入（方便检测程序问题）*/ printf(\ /*电脑随机产生数据*/ printf(\ /*用户选择*/ scanf(\ while(j!=0&&j!=1) /*考虑程序的完善性，对于误输入的提示并报警！*/ { printf(\ printf(\ /*重新输入*/ scanf(\ } 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(\ scanf(\ H->cipher=k; H=H->next; } } m=rand(); /*默认情况下，m随机产生*/ printf(\ /*当然，如果想自已输，可以进行覆盖*/ scanf(\ if(k==1) /*自行输入m值*/ { printf(\ scanf(\ } system(\ /*考虑屏幕大小，进行分屏显示*/ printf(\ /*界面友善*/ for(i=1;i<=5;i++) printf(\ for(i=0;i<30;i++) /*显示所有处理前数据*/ { printf(\ printf(\ 4 郭艳慧 实验一 线性表 08-10-20 H=H->next; } printf(\ printf(\ locfor(H,m); /*对所有数据进行实验处理，直至所有结点处理完！*/ getchar(); printf(\ /*TC环境下，方便查看结果！*/ getchar(); } 四、用户使用说明与测试运行结果： 1．运行程序后，首先弹出界面，截图如右： 理性化的选择：如果打1，则所有的cipher均由用户输入，这样方便对特殊数据进行程序测试！如果打0，那么所有的数据均由电脑产生！那如果打其他的呢？ 考虑到误输入，加了一个循环，以提高程序的健壮性！ 2．首先自行输入数据进行测试。 输完后的对话框： 5