约瑟夫环实验报告

约瑟夫环实验报告 一． 实验目的 1.熟悉C语言对链表的操作，并编译出约瑟夫环； 2.熟悉链表结构，并解决问题； 3.熟悉C语言操作环境，及相关语法。 二．实验内容 编号为1,2,3，…，n的n个人 按顺时针方向围坐一圈，每人持有一个密码（正整数）一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报道m时停止报数。报m的人出列，将他的密码作为新的m至，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出列顺序。 三． 实验设计 建立一个循环链表，从而实现相关功能。先构建一个结点的结构体： typedef struct LNode                                                  { int number; //代表编号结点的数据 int code; //代表密码结点的数据 struct LNode *next; //代表后一个结点的地址 }Linklist; 然后不断生成新结点并连接成链表，最后的结点的next指向第一个结点，从而形成循环链表。 进行操作时，读取出相应结点数据后，将后一个的数据前移，然后释放该结点。接着继续操作，直到结束。 四． 程序设计 #include #include Typedef struct LNode                                              //建立结构体 { int number; int code; struct LNode *next; }Linklist; void main() { int m, n, i, num, cod; Linklist *p1, *p2, *head;                                          //调用结构体 printf("m,n:"); scanf("%d%d", &m, &n); if(m<1||n<1) { printf("Input error"); exit(1); } head = (Linklist *)malloc(sizeof(Linklist));                        //开辟出第一个单元 if (head == NULL) { printf("error\n"); exit(1); } p1 = head; printf("输入人数与密码:"); scanf("%d%d", &num, &cod);                                  //向链表里输入数据 p1->number = num; p1->code = cod; for (i = 1; i < n; i++) { p2 = (Linklist *)malloc(sizeof(Linklist));                    //每次开辟出一个新单元 if (p2 == NULL) { printf("error\n"); exit(1); } printf("输入人数与密码："); scanf("%d%d", &num, &cod); p2->code = cod; p2->number = num; p1->next = p2; p1 = p2; } p1->next = head; p1 = head; printf("\n输出顺序：\n"); while (n > 0) { for (i = 1; i < m ; i++) p1 = p1->next; m = p1->code; printf("%d ", p1->number); p1->code = p1->next->code;                            //将下个表里的数据复制进现表，然后删除下一个表，这是因为链表是 p1->number = p1->next->number;                        //单向循环的，因而如果要删除的是第一个表，原方法不能找到最后一个表 p1->next = p1->next->next; n--; } printf("\n"); } 五．实验结果 对比书中的参考数据，可知该程序满足该实验要求。 六．调试分析 1.该程序对数据输入类型要求是整型，对其他类型的输入会出现处理上的错误。接下来可以在这方面进行改进，从而使程序能对不合法的输入进行反应，而不出现错误的输出或反应。 2.由于刚开始时对循环链表的实现过程不清楚，导致出现无从下手的情况。在查阅相关资料后，终于可以将想法实现为程序。 3.通过malloc实现动态分配内存，这是数组结构无法实现的，而链表结构中的不同结点的储存地址并不一定相邻，但通过next指向下一个结点，从而实现串联。 七．程序清单 #include #include Typedef struct LNode                                              //建立结构体 { int number; int code; struct LNode *next; }Linklist; void main() { int m, n, i, num, cod; Linklist *p1, *p2, *head;                                          //调用结构体 printf("m,n:"); scanf("%d%d", &m, &n); if(m<1||n<1) { printf("Input error"); exit(1); } head = (Linklist *)malloc(sizeof(Linklist));                        //开辟出第一个单元 if (head == NULL) { printf("error\n"); exit(1); } p1 = head; printf("输入人数与密码:"); scanf("%d%d", &num, &cod);                                  //向链表里输入数据 p1->number = num; p1->code = cod; for (i = 1; i < n; i++) { p2 = (Linklist *)malloc(sizeof(Linklist));                    //每次开辟出一个新单元 if (p2 == NULL) { printf("error\n"); exit(1); } printf("输入人数与密码："); scanf("%d%d", &num, &cod); p2->code = cod; p2->number = num; p1->next = p2; p1 = p2; } p1->next = head; p1 = head; printf("\n输出顺序：\n"); while (n > 0) { for (i = 1; i < m ; i++) p1 = p1->next; m = p1->code; printf("%d ", p1->number); p1->code = p1->next->code;                            //将下个表里的数据复制进现表，然后删除下一个表，这是因为链表是 p1->number = p1->next->number;                        //单向循环的，因而如果要删除的是第一个表，原方法不能找到最后一个表 p1->next = p1->next->next; n--; } printf("\n"); }