杭州电子科技大学

计算机学院

 

数据结构课程设计

 

 

设计题目：约瑟夫环问题

 

 

 

 

 

 

 

                             专    业   网络工程      

班    级   11052411       

学    号   11054126       

姓    名   魏刘宏         

指导教师   王立波        

 

 

                                        2012年12月28日

 

一、    需求分析

    1、问题描述：

   设编号为1，2，…，n(n>0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止。

2、基本要求
   设计一个程序模拟此过程，给出出列人的编号序列。

3、实现提示：
   可考虑不带头结点的单链表结构，注意空表和非空表的界限。

4、测试数据：
   N=7，七个人的密码依次为3，1，7，2，4，8，4； 初始报数上限值m=20。

           （ 正确出列顺序为6，1，4，7，2，3，5 ）

 

 

二、    概要设计

 

链表存储结构的定义：

typedef struct Lnode

{        } LNode, * LinkList;

 

LinkList CreatCycleList(int n)

         创建无头节点的单向循环链表；

 

void print(LinkList L)

         输出链表；

 

三、    详细设计

 

#include<stdio.h>

#include<stdlib.h>

typedef int ElemType;

 

typedef struct LNode{

         ElemType data;

         ElemType seq;

         struct LNode *next;

} LNode, * LinkList;

 

LinkList CreatCycleList(int n){

         //单向循环链表 ,无头节点；

         LinkList La = (LinkList)malloc(sizeof(LNode));

         ElemType a;

         scanf("%d",&a);

         La->data = a;

         La->seq = 1;

         LinkList q = La ;

         for(int i=1; i < n; i++){

                   LinkList p = (LinkList)malloc(sizeof(LNode));

                   q->next = p;

                   scanf("%d",&a);

                   p->data = a;

                   p->seq = i+1;

                   p->next = La;

                   q=p;

         }

         return q;  //指向尾节点，避免对第一个结点的操作失败；

}

 

void print(LinkList L) 

{ 

    LinkList p = L->next; 

    printf("%d ", p->data); 

    p = p->next; 

    while (p != L->next)  //适应链表指针指向尾节点的情况

    { 

        printf("%d ", p->data); 

        p = p->next; 

    }

         printf("\n");

} 

 

int main(){

         printf("约瑟夫环 单向循环链表 \n\n");

         int m,n,i,j;

         printf("请输入人数:  ");

         scanf("%d",&n);      

         printf("请输入每个人的密码（%d个正整数）:\n",n);

         LinkList L = CreatCycleList(n);

         LinkList pre = L;

                  

         //printf("初始站队为:\n");

         //print(L);

         printf("请输入初始报数上限值：\n");

         scanf("%d",&m);

        

         printf("\n出列顺序为：\n");

        

         j = n;

          

         while(j > 0){

         for(i = 1; i < m; i++){

                   pre = pre->next;

         }

         m = pre->next->data;

         printf("%d ",pre->next->seq);

         pre->next = pre->next->next;

         j--;

         }

         printf("\n\n");

        

         return 0;

}

 

 

四、    调试分析

这是我上数据结构课程设计这门课后做的第一个实验，所以开始时毫无头绪。

 

1、  开始时，我将代表链表的指针指向链表的第一个节点，这样操作第一个节点时会出错；后来，在老师的指点下，将代表指针指向链表的尾节点就成功了。

2、  本来我将序号和密码存在两个链表中，后来听老师说这样完全没有必要，纯粹浪费空间，于是就加以改进了。

 

五、    用户手册

用户点击运行后，依次输入人数n，n个人的密码，初始报数上限m

本程序将会计算并输出出队序列。

 

六、    测试结果http://i1292.photobucket.com/albums/b567/dlgcy/DLGCY/Pictures/QQImage_19392312.jpg

 

七、    验收过程心得体会

1、  有老师来验收对我们来说是很好的，老师既能督促我们，又能指出我们程序中的错误和不足；

2、  通过这次实验，我了解到写程序不是一蹴而就的，需要全面思考，反复调试；

3、  程序并不是功能实现就可以高枕无忧了，还要考虑效率和空间占用。