注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

独立观察员·网易

分享万岁

 
 
 

日志

 
 

[实验报告]约瑟夫环问题  

2013-01-23 15:35:00|  分类: 原新浪博客的 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

杭州电子科技大学

计算机学院

 

数据结构课程设计

 

 

设计题目:约瑟夫环问题

 

 

 

 

 

 

 

                                    网络工程      

       11052411       

       11054126       

       魏刘宏         

指导教师   王立波        

 

 

                                        20121228

 

一、    需求分析

    1、问题描述:

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


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

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

4
、测试数据:
   N=7
,七个人的密码依次为3172484 初始报数上限值m=20

           正确出列顺序为6147235

 

 

二、    概要设计

 

链表存储结构的定义:

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

 

五、    用户手册

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

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

 

六、    测试结果[实验报告]约瑟夫环问题 - 独立观察员 - 独立观察员的博客

 

七、    验收过程心得体会

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

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

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

 

  评论这张
 
阅读(53)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018