《计算机软件技术基础》  实验报告I—数据结构
实验一、约瑟夫斯问题求解
一、问题描述
1.实验题目：编号1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自1报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，直至所有人全部出列。
2.基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。
3.测试数据：n=7,7个人的密码依次为：3,1,7,2,4,8,4.m初值为6（正确的出列顺序应为6,1,4,77,2,3）。
二、需求分析
1.本程序所能达到的基本可能：
该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n个人围坐一圈，用链表中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。
个人网站的制作实验报告2.输入输出形式及输入值范围：
程序运行后提示用户输入总人数。输入人数n后，程序显示提示信息，提示用户输入第i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入初始密码，密码须为正整数且不大于总人数。
3．输出形式
提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。用户输入完毕后，程序自动运行输出运行结果。
4.测试数据要求：
测试数据n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。
三、概要设计
  为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码信息，因此需要循环链表结构体这个抽象数据类型。
1．循环链表结构体抽象数据类型定义：
ADT  Node{
            数据对象：D={ai,bi,ci|ai∈int, bi∈int,ci∈(Node*),i =,n,n≥0}:
数据关系：R=∅
基本操作：
CreatList(int n)                //构建循环单链表；
Order(int m,node *l)            //输出函数，输出出列顺序并删除链表中的结点；
}ADT    node；
2. ADT的C语言形式说明：
typedef struct Node     
{
    int num;          //结点的数据域，存放编号；
    int word;    //结点的数据域，存放密码；
    struct Node *next;  //结点的指针域，存放指向下一结点的指针；
}Node；
Node *CreatList( )            //建立循环单项链表；
void Order(Node *h)  //输出出列顺序并删除结点；
3.  主程序流程及其模块调用关系:
1）.主程序流程：
先提示用户输入相关数据：总人数，运行循环链表结构体模块，输入每个人持有的密码值，创建出新链表，运行输出函数模块，再输入初始密码m值，输出出列序列。
（创建循环单链表模块：实现链表的抽象数据类型
删除链表结点输出序列模块：实现输出出列顺序）
2）.模块调用关系：
四、详细设计
1.元素类型、结点类型和结点指针类型：
typedef struct Node            //定义一个结构体，包含了每个人的序号和密码
{
    int word;
    int num;
    struct Node *next;
}Node;
2、创建单向循环链表类型：
Node *CreatList()      //尾插法创建一个单向循环链表
  {
      Node *p,*s;
      Node *h;      //定义头指针
      h=(Node*)malloc(sizeof(Node));  //申请动态存储空间
      p=h;
      h->next=NULL;      //初始化链表
      printf("第1个人的密码是："); 
      scanf("%d",&h->word);
      h->num=1;          //给头指针赋值
      for(i=0;i<n-1;i++)
      {
      s=(Node*)malloc(sizeof(Node));     
      if(h->next==NULL)  h->next=s;
      else            p->next=s;
      p=s;
        printf("第%d个人的密码是：",i+2);
      scanf("%d",&s->word);
      s->num=i+2;
      }
      p->next=h;
      return h;
  }
3.删除链表结点输出函数模块：
void Order(Node *h)      //输出结果
{
      Node *p;
      p=h;
      Node *d;
      while(p->next!=p)   
      {
        if(m<2)
        {
            p=p->next;
        }
        else
        {
          for(i=1;i<m-1;i++)  //查第m个结点
          {
            p=p->next;
          }
        }
       
      d=p->next;
      m=d->word;
      printf("%d--",d->num);
      p->next=d->next;    //删除结点
      p=p->next;
      free(d);
      }
      printf("%d\n",p->num);
  }
4.主函数：
void main()
  {
    printf("试验名称：约瑟夫斯问题求解\n");
    printf("学号：\n");
    printf("姓名：xx\n");
   
    printf("=========================================================\n");

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。