数据结构约瑟夫环上机报告.doc

题目：约瑟夫环 班级：030914班 姓名：吴多坚 学号 完成日期：2010-5-12 一、需求分析 （1）创建链表的类型； 根据题意，操作对象是围成一圈的同学，数数时以一圈为循环，因此创建的链表为循环链表最为合适。 （2）每个结点所应包含的元素； 因为每位同学的座位都有对应固定的易个座位号和一个密码，所以结点中赋予两个个整型类型的变量作为座位号和密码。 （3）开始计数的起点； 最为重要的是第一次计数时位置的确定，虽然第一次的第一位同学是1号同学，但在链表中为了方便，要做删除操作时指针应指向被删除结点的前一位，所以程序开始的头指针应该是尾结点。而且每一次删除结点后指针所停留的位置都在下一次开始计数的前一位，所以后面的指针位置不需要更动。 （4）程序功能 按照给定密码将围成圈的同学分别找出。 （5）测试数据 见测试结果 二、概要设计 抽象数据类型的定义 typedef struct LNODE{ int data,wz; struct LNODE *next; }LNODE,*linklist; 三、详细设计 根据人数创建一个循环链表 for(i=1;in;i++)//n是人数 { p=(linklist)malloc(sizeof(LNODE));//申请结点 q-next=p; q=p;//尾结点 } 分别给每个结点赋值（座位号、密码） for(i=1;i=n;i++) { printf(第%d位同学的密码：,i); scanf(%d,head-data); //输入密码 head-wz=i; //利用循环赋值座位号 head=head-next; //后移一位指针 } 得到尾结点 L=q; 输出 for( i=1;i=n;i++) { for(j=1;jm;j++) { L=L-next; } p=L-next; m=p-data; printf(%d ,p-wz); L-next=p-next; free(p); } 四、调试分析 (1)调试过程中遇到的问题及其解决方法 A.问题:在申请头结点成功只赋值给head指针，所以当指针到达尾结点后指不回头结点。 解决方法：申请头结点成功后把head再赋值给q保存，为“头尾相接”作铺垫。 B.问题：最后输出的结点有错。 解决方法：如下： (2)经验与体会 我发现我这次所编程的错误点都出现在细小的地方，一个字母，一个赋值变量。而且这样的程序错误特别难排除。我用了不到半个小时编出来的程序却花了我几个小时来bugging，当我最后才发现我出错的地方后很抓狂，难以接受这样的错误。但后来我想了一下，这种错误的原因归于平常的不仔细，归于急于求成的结果。所以我想我会在在后面的编程中刻意注意这点，也希望这种错误能减少发生的可能。 五、用户使用说明 A、输入初始密码m； B、输入人数n; C、分别输入各同学所持有的密码； D、程序结果输出。 六、测试结果 七、附录 带有注释的源程序(见源程序文件)