实验报告1约瑟夫环.doc

郭艳慧 实验一 线性表 08-10-20 PAGE PAGE 4 《数据结构》实验报告 班级： 姓名： 学号： 日期： 08-10-20 题目： 约瑟夫环 上机实验的问题和要求： 问题描述： 编号为1到n的n个人围成一圈，每人带一个密码c，以m为报数上限。然后从第一个人开始顺时针自1开始报数，报到m的人出列，将其密码作为新的m值，从他的下一个人开始，同样顺时针自1开始报数，依次循环下去，直到所有的人都出列！要求得到依次出列的那些人的编号序列！ 基本要求： 用C代码实现此活动，要求使用一定的算法进行操作，并最终通过程序运算出最后的结果！ 二、程序设计的基本思想，原理和算法描述： （包括程序的模块结构，数据结构，输入/输出设计，符号名说明等） 基本思想： 利用不带头结点单向循环链表模拟该活动，在实现了一切动作之后，运用一定的算法得到最终的结果。 程序的模块结构： 定义了相关的结构体之后，主要有以下几大模块： 建立由头指针指示的有n个结点的不带头结点的单向循环链表crt_CLinkList(H,n); 寻找、输出、删除H单循环链表的第m个结点locfor(H,m); 最后通过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;im;i++) /*形成m个结点的不带头结点的单