数据结构上机实验报告

1、需求分析

　1：用一个循环链表实现n个人按顺时针排成一圈,每个人看作一个节点,每个节点都是一个结构体类型,包含三个域: 序号域(data), 密码域(key),指向下一个人的指针域(next).

　　2：程序开始时由用户任意输入人数n及一个正整数作为报数上限值m,一个正整数作为密码最大值，判断所输密码是否在范围内。然后为依次每一个人指定一个密码

　　3：初始密码为用户外部输入的密码m, 从第一个人开始按顺市针方向自1开始报数.,报道m的时停止,报m的人出列,将他的密码作为新的密码值(m), 从他在顺针方向的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.

　　4：本程序最终结果为n 的人的出列顺序

　　5：测试数据: m的初值为1; n =5(即有5个人)57个人的密码依次为:1，2，3,4，5.首先没的值为1,正确的出列顺序应为1，2，4，3，5。

2概要分析

（1）抽象数据类型的定义：

为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。

算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。

核心算法主要分为两步：

1、确定需要删除的位置，2、设置并删除该位置。

已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

反复进行上述确定位置和删除位置的操作，直到顺序表为空。

（2）主程序的流程：

程序由三个模块组成：

（1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。

（2）构造链表并输入每个人信息模块：

（3）主要处理出列的函数：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。

3、详细设计

 1.本程序包含三个模块

     1) 主程序模块

 int main()

 {

     int m,n,i=0;

  LinkList s;

  printf("请输入报数上限m和人数n:\n"); 

  do{

   if(i>0)

    printf("输入有误，请重新输入:\n");

  scanf("%d",&m);

  getchar();

  scanf("%d",&n);

  getchar();

  i++;

  }while(m <= 0 || n <= 0);

  s=CreatList_L(n);

  ListDelete_L(s,m,n);

  return 0;

 }

      2) 构造链表并输入每个人信息模块；

LinkList L,r,q;

 int i,key;

 printf("请输入%d个数字作为每个人的密码:\n",n);

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

 {

  scanf("%d",&key);  //输入每个人的密码

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

  if(i==1)

  {

   L=q=r;

  }

  else{

     q->next=r;

     q=r;

  }    

        r->num=i; 

        r->pwd=key;

 }

 r->next=L; //使最后节点指向首节点，形成循环链表

 return L; //向主函数返回创建完成的循环链表首节点的地址

}

3）主要处理出列的函数：

void ListDelete_L(LinkList &L, int m, int n){

 LinkList p,s;

 int j;

 while(n>0){//只要人数大于0就继续，直到全部出列

  p=L;

  for(j=1; j<m; j++){  //顺序找到第m个节点（人）并使指针指向该节点

   s=p;

   p=p->next;

  }

  printf("出列人原来的序号是:%d\n",p->num); //输出出列人序号

  m=p->pwd; //将出列人的密码作为新的报数值m

  s->next=p->next;//将出列的节点（人）从循环链表中删除

  L=p->next;

  free(p);

  n--;

 }

}

4、调试分析

（1）编写程序时，指针运用不熟练，导致调试时错误过多，花费了太多时间，后通过对指针相关知识的进一步了解，改正了程序中的错误，正确运行了程序。

（2）数据结构是一门比较抽象的课程，但是也是一门最基础的课程学的过程。在现实生活的也非常广泛通过设计该实验让我更加深刻的掌握了有关链表的知识，同时也认识到了自己在平时学习当中的盲点。通过这次实验发现了自己在数据结构这门功课上存在严重的不足。链表中的指针理解不够，运用不够熟练，常常出现一些莫名其妙的问题，调试费时太多。今后一定会多编程，多思索。在以后的学习过程中还需要不断的完善学习，希望能把数据结构这门课学习的更加深入，更加透彻。

5、测试结果

6、附录

#include<stdio.h>

#include<malloc.h>

typedef struct LNode{

 int pwd,num;

 struct LNode *next;

}LNode, *LinkList;

LinkList CreatList_L(int n){

 //建立循环链表

 LinkList L,r,q;

 int i,key;

 printf("请输入%d个数字作为每个人的密码:\n",n);

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

 {

  scanf("%d",&key);  //输入每个人的密码

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

  if(i==1)

  {

   L=q=r;

  }

  else{

     q->next=r;

     q=r;

  }    

        r->num=i; 

        r->pwd=key;

 }

 r->next=L; //使最后节点指向首节点，形成循环链表

 return L; //向主函数返回创建完成的循环链表首节点的地址

}

void ListDelete_L(LinkList &L, int m, int n){

 LinkList p,s;

 int j;

 while(n>0){//只要人数大于0就继续，直到全部出列

  p=L;

  for(j=1; j<m; j++){  //顺序找到第m个节点（人）并使指针指向该节点

   s=p;

   p=p->next;

  }

  printf("出列人原来的序号是:%d\n",p->num); //输出出列人序号

  m=p->pwd; //将出列人的密码作为新的报数值m

  s->next=p->next;//将出列的节点（人）从循环链表中删除

  L=p->next;

  free(p);

  n--;

 }

}

   int main()

 {

     int m,n,i=0;

  LinkList s;

  printf("请输入报数上限m和人数n:\n"); 

  do{

   if(i>0)

    printf("输入有误，请重新输入:\n");

  scanf("%d",&m);

  getchar();

  scanf("%d",&n);

  getchar();

  i++;

  }while(m <= 0 || n <= 0);

  s=CreatList_L(n);

  ListDelete_L(s,m,n);

  return 0;

 }

第二篇：数据结构实验报告(约瑟夫环)

《数据结构》课程实验

实验报告

题目：      Joseph问题求解算法的设计与实现                                             

专业：             计算机科学与技术                                                   

班级：                                                       

姓名：                                                                   

学号：                                                                   

完成日期：                                          

一、试验内容

约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

二、试验目的

掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。

三、流程图

四、源程序代码

//Joseph问题求解算法的设计与实现

#include

#include

struct list

{

    int num,code;

    struct list *next;

};

void main()

{

    printf("Joseph问题求解算法的设计与实现\n \n");

    int i,j,m=1;

    int key; // 密码.

    int n; //人数 .

list *p,*s,*head;

    head=(list *)malloc(sizeof(list)); //为头结点分配空间.

    p=head;

    printf("输入人的总个数:");

    scanf("%d",&n);

    for(i=1;i＜=n;i++)

        { key=rand() % 100;

            printf("第%d个人的密码:%d\n",i,key); 

       

            s=p;

            p=(list *)malloc(sizeof(list)); //创建新的结点.

            s-＞next=p;

            p-＞num=i;

            p-＞code=key;

        }

    p-＞next=head-＞next;

    p=head;

    head=head-＞next;

    free(p); //释放头结点.

    p=head;    

    do{

        printf("\n第%d号成员的密码为:%d",p-＞num,p-＞code); //输出链表.

        p=p-＞next;

    }while(p!=head);

    printf("\n\n输入第一个报的数:\n");

    scanf("%d",&key);

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

    do

        { j=1; p=head;

            while(j

                s=p;

                p=p-＞next;

                j++;

            } //报数过程.

        i=p-＞num;

        key=p-＞code; 

        printf("%d:第%d号成员出列\n",m,i);

        m++;

        s-＞next=p-＞next;

        head=p-＞next; //重新定义head,下次循环的开始结点.

        free(p);// 释放已出列的结点.

        n--; //人数减一.

        }while(n＞0);

}

五、调试过程

调试过程中,曾出现过缺少分号、括号之类的错误,还出现过运算顺序颠倒，致使运算出现了错误，在经过仔细的检查并且向人请教,终于得出了正确结果.

六、结果分析

Joseph问题求解算法的设计与实现

输入人的总个数:5

第1个人的密码:41

第2个人的密码:67

第3个人的密码:34

第4个人的密码:0

第5个人的密码:69

第1号成员的密码为:41

第2号成员的密码为:67

第3号成员的密码为:34

第4号成员的密码为:0

第5号成员的密码为:69

输入第一个报的数:

6

出列顺序为:

1:第1号成员出列

2:第2号成员出列

3:第3号成员出列

4:第5号成员出列

5:第4号成员出列

Press any key to continue