《数据结构》

课程设计报告

20##年12月18日

目        录

1  课程设计的目的………………………………………………………………2

2 需求分析………………………………………………………………………2

3  课程设计报告内容……………………………………………………………3

1、概要设计……………………………………………………………………3

2、详细设计……………………………………………………………………3

3、调试分析……………………………………………………………………x

4、用户手册……………………………………………………………………x

5、测试结果……………………………………………………………………6

6、程序清单……………………………………………………………………7

4  小结 …………………………………………………………………………10

1、   课程设计的目的

（1）  熟练使用C++编写程序，解决实际问题；

（2）  了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

（3）  初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

（4）  提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

2、   需求分析

1、问题描述：

编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

2、要求：

利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

3、测试数据：

m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

输出形式：建立一个输出函数，将正确的输出序列

3、课程设计报告内容

概要设计：

   在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。

详细设计：

    我先建立一个结构体，与单链表一样，只是多了一个存密码的code域

    struct LinkNode

{

      int data;   //顺序

      int code;   //密码

      LinkNode *next; 

};

建立一个类LinkList ,包含的函数：

LinkList();       //构造函数

   void Creat(const int );    //创建循环链表

   int Delete(LinkNode* );   //删除报到数的结点

   int Joseph(int );        // 约瑟夫环

私有成员是

LinkNode* head;   //指向第一个结点的指针

LinkNode* elem;   // 同上

    int len;      //长度

我定义了一个elem指针是为了约瑟夫环里运行方便，elem只在约瑟夫环这个函数里用到，其他函数没有特别大的用处。

构造函数与书上的没什么大差别，创建循环链表时，要考虑几个问题，一个是题目要求是不带头结点，所以head指针直接指向了第一个结点，我在创建链表时把第一个结点初始化data为1，表明这个结点是第一个结点。具体如下：

void LinkList::Creat(const int number)      //number为结点个数，也就是参与的人数

{    

     if(number==1)       //只有一个人的情况

{

      head=elem=new LinkNode;

      head->data=1;    

      cout<<"请输入密码:"<<endl;

      cin>>head->code;

      head->next=head;

}

    else

{

      head=elem=new LinkNode;

      head->data=1;    

      cout<<"请依次输入各个密码:"<<endl;

      cin>>head->code;

LinkNode*q=head;

      q=head;

      for(int i=1;i<number;i++)   //将每个结点链接上，在链接时填入密码

{

        LinkNode*p=new LinkNode;

        p->data=i+1;    

        cin>>p->code;

        q->next=p;

        q=p;

}

    q->next=head;     //构成循环链表

}

    len=number;

}

   在构建约瑟夫环的执行函数时，我首先考虑了递归调用的函数，原本的这个程序的所有的都定为elemtype类型的，虽然编译没出错，但是在连接时发生了错误，在老师的指导下改成了具体的int型。

int LinkList::Joseph(int m)

{

     if(len>1)

{                                                                             

LinkNode *q;

if(m==1)   //在初始报数为1的情况下

        {

q=elem;

int a=q->code;   //将选中的结点的密码记录在a中

elem=elem->next;

cout<<Delete(q)<<endl;  //Delete函数是为了将已经报过数的人删除Joseph(a);       //用已经删除的结点的存的密码作为下一次循环的报数值

}

else    //一般情况下

{

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

             elem=elem->next; //找到需要出列的结点

q=elem;

elem=elem->next;   //此处的elem指针指向要删除的结点的下一个结点，下次递归调用时从这里开始向下循环报数

         int a=q->code;

         cout<<Delete(q)<<endl;

Joseph(a);

}

}

else   //在只有一个结点的情况下

cout<<head->data;

}

  最后还有一个Delete函数，在删除结点的时候要考虑几个特殊情况，头尾结点。删除第一个结点时，需要将head指针下移，尾结点的next也要指向第二个结点；删除尾结点时，要将尾结点前的结点与第一个结点相连。在设计这个函数时，我只考虑了当len大于1的情况，在只剩下一个结点时，不必要删除，直接输出data的值即可（在约瑟夫函数中有写）。具体函数如下：

int LinkList::Delete(LinkNode *a)  

{

   if(len>1)  //只考虑长度大于1的情况

   {

       if(head==a)

{

         int out=head->data;

LinkNode* q=head;

         while(q->next!=head)

{

             q=q->next;

}

q->next=head->next;

head=head->next;

delete a;

len--;    //用len记录删除后的循环链表的长度

return out;

}

       else

       {

LinkNode* q=head;

int out=a->data;

           while(q->next!=a)

{

             q=q->next;

 }

if(a->next=head)  .//删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）

           {

              q->next=head;   //重新链接

   delete a;

              len--;

              return out;

}

else

           {

              q->next=a->next;

              delete a;

           len--;

           return out;

           }

}

   }

}

5、测试结果：

6 程序清单：

#include <iostream.h>

struct LinkNode

{

      int data;

      int code;

      LinkNode *next;

};

class LinkList

{

public:

   LinkList();      

   void Creat(const int );

   //~LinkList();     

  

   int Delete(LinkNode* );

   int Joseph(int );   

 

private:

    LinkNode* head;

       LinkNode* elem;

    int len;    

};

LinkList::LinkList()    

{

    head=elem=NULL;

    len=0;

}

void LinkList::Creat(const int number)     

{    

     if(number==1)

       {

      head=elem=new LinkNode;

      head->data=1;    

      cout<<"请输入密码:"<<endl;

      cin>>head->code;

      head->next=head;

       }

    else

       {

      head=elem=new LinkNode;

      head->data=1;    

      cout<<"请依次输入各个密码:"<<endl;

      cin>>head->code;

         LinkNode*q=head;

      q=head;

      for(int i=1;i<number;i++)  

         {

        LinkNode*p=new LinkNode;

        p->data=i+1;    

        cin>>p->code;

        q->next=p;

        q=p;

         }

    q->next=head;

       }

    len=number;

}

int LinkList::Delete(LinkNode *a)  

{

   if(len>1)

   {

       if(head==a)

          {

         int out=head->data;

               LinkNode* q=head;

           while(q->next!=head)

                 {

             q=q->next;

                 }

                 q->next=head->next;

                  head=head->next;

                delete a;

                len--;

                return out;

          }

       else

       {

                 LinkNode* q=head;

                 int out=a->data;

           while(q->next!=a)

                 {

             q=q->next;

                 }

                  q->next=a->next;

              delete a;

              len--;

              return out;  

        }

   }

}

int LinkList::Joseph(int m)

{

     if(len>1)

       {    

          LinkNode *q;

            if(m==1)

         {

            q=elem;

               int a=q->code;

               elem=elem->next;

               cout<<Delete(q)<<endl;

            Joseph(a);

           }

            else

               {

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

             elem=elem->next;

                q=elem;

                elem=elem->next;

         int a=q->code;

         cout<<Delete(q)<<endl;

            Joseph(a);

            }

       }

       else

              cout<<head->data;   

}

int main()

{

   int num,code;

   cout<<"请输入人数: ";

   cin>>num;

   LinkList L;

   L.Creat(num);

   cout<<"请输入第一个上限数:   ";

   cin>>code;

   cout<<"出列顺序:"<<endl;

   L.Joseph(code);

   return 0;

}

4、小结

一、这次课程设计的心得体会通过实践我的收获如下：

一开始接触数据结构课程设计真的挺难的，好多都不会，不是逻辑方面的问题，而是不具备动手能力，脑子里总有一团火，比如对于这个题目，一开始有很多的想法，想到了从逻辑上怎么实现他，要编写哪些程序，但是一到需要编写了就开始为难了，可以说是几乎不知道从哪里入手，参考了书本里的程序，仿照他的结构一步一步做下来，现在对于单链表的各种操作已经算是比较熟练了，让我知道光有理论知识还远远不够，需要多动手，写的多了自然就能手到擒来。

二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：

1、认真上好专业实验课，多在实践中锻炼自己。

2、写程序的过程中要考虑周到，严密。

3、在做设计的时候要有信心，有耐心，切勿浮躁。

4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。

5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。

 

第二篇：数据结构 约瑟夫环 课程设计

摘要：

约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码Ki（整数），留作其出圈后应报到Ki后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。

关键词：约瑟夫环；双向循环链表；数据结构；删除结点

目   录

1需求分析. 2

1.1功能分析. 2

1.2设计平台. 2

2概要设计. 2

2.1类LinkList 3

2.2类Joseph 3

2.3类异常处理. 3

3详细设计和实现. 3

3.1创建结点Node 3

3.2创建双向循环链表. 4

3.3从链表中删除结点. 5

4调试与操作说明. 5

4.1调试情况. 5

4.2操作说明. 6

总  结. 8

致   谢. 9

参 考 文 献. 10

                     

1需求分析

1.1功能分析

本次选做的课程设计是改进约瑟夫(Joseph)环问题。我选择了和薛晶两个人来完成本次课程设计的作业。约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。

在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针current指向当前的结点，指针front始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过rand()函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。

1.2设计平台

Windows2000以上操作系统；Microsoft Visual C++ 6.0

2概要设计

已知n个人（以编号1，2，3...n分别表示）围成一圈。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到一圈的人全部出列。这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head。解决问题的核心步骤：首先建立一个具有n个链结点，无头结点的循环链表。然后确定第1个报数人的位置。最后不断地从链表中删除链结点，直到链表为空。

改进的约瑟夫环问题与原问题思路一致，只是不再采用单循环链表存储结构，而采用双向循环链表，而且用一个判断语句来决定报数的方向的顺时针还是逆时针。本课程设计主要采用了类的数据结构，程序中包含了两个类：Linklist , Joseph。

2.1类LinkList

主要功能是创建结点，每个结点数值域包括data,password,还有指示前驱结点的指针llink,和指示后继结点的指针rlink。

2.2类Joseph

主要功能是实现创建双向循环链表及一些相应的操作。

2.3类异常处理

在C++程序中，可以使用try-throw-catch结构处理程序异常。采用这一程序结构能够将使用和实现分离：类和函数的实现者使用throw语句易地错误类别通知使用者。使用者根据获悉的错误类别采取相应的措施，这就是异常处理。

3详细设计和实现

改进约瑟夫环问题的基本思路和原问题基本一致，只是一个采用单循环链表，另一个采用双向循环链表来解决问题。第一步是定义结构变量结点linklist，并在该结点下定义结点的元素域:data,password，指针域:lLink和rLink。然后建立一个由n个链结点，无表头结点的双向循环链表。并由构造函数对结点赋值，由随机函数rand()产生每个结点的password。由于每个结点的password是由随机函数产生的，也就是每个结点的password是后知的，所以在一开始人为地指定一个结点的顺序，由此结点开始报数。报password个数后，报到的那个结点被删除，它的password被记录下，由它的下一个结点开始逆方向报数………如此循环，直到循环链表里只剩下一个结点，那就是问题所求的结果。具体到问题上，还需要创建一个Joseph类，由构造函数来初始化，输入所有的人数，也就是表长，然后指定由第几个人开始报数。在Joseph类中定义一个GetWinner()函数，由它来实现获得最后的胜利者。并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了一个人之后，再按逆时针顺序报数，如此交替进行。

3.1创建结点Node

链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。因此需要创建双向链表结点。由于每一个结点有一个密码和一个序号，所以可以将结点结构体定义为：

struct Node{

int data;

int password;

DNode* llink;

DNode* rlink;}                     图3.1 结点Dnode

3.2创建双向循环链表

创建一个空双向循环链表，双向循环链表和每个结点包括三个域:Element，

lLink,rLink.其中element为元素域，rLink域为指向后继结点的指针，新增的lLink域用以指向前驱结点。双向链表也可以带表头结点，并且也可以构成双向循环链表。此时，表头结点的rLink，lLink分别指向双向循环链表的头结点(或表头结点)和尾结点。

一个结点的lLink域的指针指向它左边结点的后部，这并不意味着该结点的lLink域保存的仍是该左边结点存储块的起始地址。在此处，指针指向某个结点任何部分都是等价的，都是指该存储块的起始位置。

图3.2 单表头的双向循环链表

每当结点计数到某一结点时，将他的前驱结点接到他的后继结点，然后将他的密码值password赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。

由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为front，front始终指向头结点，并定义指针current记录当前的结点。并根据具体情况移动（顺逆时针）。

为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的data值就可以。最后通过函数调用来输出顺序。要解决约瑟夫环问题，首先一点就是必须有一个环，所以第一步我们必须建立一个双向循环链表。而建立一个双向循环链表必须有一个空的双向循环链表，然后运用尾插法建立一个双向循环链表，这样约瑟夫环就创建出来了，接下来就是处理约瑟夫环问题。

3.3从链表中删除结点

在双向循环链表中，一个结点的前驱结点地址保存在该结点的lLink域中，这样可以方便地实现在一个指定结点之前插入一个新结点的操作，也可以方便地删除某个指定结点。

函数通过代码：q->llink->rlink=q->rlink;q->rlink->llink=q->llink;delete q;

来删除当前的那个结点q，通过循环来一次次删除当前的结点，直到链表中剩下最后一个结点。

具体程序如下：

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

typedef struct node //定义单循环链表中节点的结构

{

    int num;//序列号即个人的编号

    int cipher;//个人所持有的密码

    struct node *next;

}linklist;

class YSFH

{

public:

    linklist *Creat(int n);

    linklist *Select1(int m);

    linklist *head;//头指针指示有n个结点的单循环链表creat

protected:

    linklist *Select(linklist *head,int m);

private:

    linklist *p;//存放人员信息

    linklist *r;//临时存放

    linklist *q;

    int k;

};

/*建立单循环链表函数*/

linklist *YSFH::Creat(int n)

{

    linklist *head;

    linklist *p;

   

    p=(linklist *)malloc(sizeof(linklist));

    head=p;

    p->num=1;

    printf("随机产生第1个人的密码:  ");

    p->cipher=rand()%10;

    {   if(p->cipher==0)

       p->cipher=rand()%10;

    }

    printf("%d\n",p->cipher);

    r=p;

    p->next=p;

    for(int k=2;k<=n;k++)

    {

       p=(linklist *)malloc(sizeof(linklist));

       p->num=k;//给每人一个编号

       printf("随机产生第%d个人的密码:  ",k);

        p->cipher=rand()%10;

       {   if(p->cipher==0)

       p->cipher=rand()%10;

    }

       printf("%d\n",p->cipher);

       r->next=p;

       r=p;

    }

    p->next=head;

    return(head);

}

/*决定出列编号*/

linklist *YSFH::Select1(int m)

{

    return Select(head,m);

}

linklist *YSFH::Select(linklist *head,int m)

{

    q=head;

    k=1;

    p=q->next;//q为p的前驱指针,p指向当前报数的人

    printf("出列的序号依次为:");

    //在head中的第一个结点起循环记数找第m个结点

    while(q!=p)

    {

       k=k+1;//报一次数

        if(k%m==0)//所报数等于报数上限值时

       {

           printf("%d  ",p->num);//输出该结点的num值

           m=p->cipher;//把该结点的cipher(密码)值赋给m

           q->next=p->next;//对应的节点从链表中删除

           free(p);

           k=0;

           p=q->next;

       }

       else{

           q=p;

           p=p->next;//p指向当前报数的人

       }

    }

    head=p;

    return(head);

}

void main()

{

    int n,m;

    m!=0;

    YSFH Y;

    printf("输入总人数n:  ");

    scanf("%d",&n);

    Y.head=Y.Creat(n);

    printf("随机产生第一次的报数上限值m:  ");

    m=rand()%10;

    {

       if(m==0)

       m=rand()%10;

    }

    printf("%d\n",m);

    Y.head=Y.Select1(m);

    printf("%d\n",Y.head->num);

}

4调试与操作说明

4.1调试情况

这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写好后运行，出现了很多错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许不一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得不到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。

在随机设置每个结点的password时也曾是个问题，因为我做的随机函数一直都用不好，要不是每次随到的都是一样的，要么就是每次随到的数都很大，后来通过老师的耐心讲解才得以解决。

在调试的过程中，类的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。

4.2操作说明

生成界面如图4.1，4.2所示：

图4.1 生成界面

：

图4.2生成界面

当程序运行的时候会出现如上图所示的提示，要求使用者输入程序中所需的输入总人数，使用者只需输入自己所想的总人数，系统便会随机产生每个人对应的密码，同时随机产生第一次的报数上限值。最后系统会给出出列的次序，最后产生的编号便是此次游戏的获胜者。使用者还可按下任意键，进行下一次的游戏。

总结

为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。

在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。

在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。

致     谢

这次的课程设计，我们两人一个小组去完成我们自己的课程，但是还是得到了来自很多方面的帮助。在此首先要感谢淮阴工学院计算机工程系提供给我这次实践的机会，让我们有机会贴近现实，感受成功的喜悦；其次要感谢实验机房的老师提供优良的实验设备供我们做实验，正是这种良好的实验环境让我们整个实验过程心情都非常愉快。再次要感谢指导老师们的辛勤指导，每当我们遇到疑难问题时，是他们一次次不厌其烦的解释和悉心的指导，我们才能闯过一个个难关，到达胜利的彼岸，是他们给我们提供了一次宝贵的检验自己机会。只有在真正实战的时候才会发现书到用时方恨少的真谛。有时感觉自己那么一次次举手请教，可问题又那么幼稚简单。老师是那么的耐心与不厌其烦，直到我们点头说懂得的时候老师才离开。。最后也要感谢同学们的帮助，有了他们的支持使我遇到任何困难都不是一个人在战斗。感谢所有在我课程设计过程中帮助过我的人！

参考文献

1张乃孝,裘宗燕.数据结构C++与面向对象的途径.北京：高等教育出版社，1998

2 周云静．数据结构习题解析与上机指导．北京：冶金工业出版社，2004

3 陈慧南．数据结构—C++语言描述．北京：人民邮电出版社，2005

4 严蔚敏，吴伟民．数据结构．北京：清华大学出版社，1997

5 Adam Drozdek．数据结构与算法．北京：清华大学出版社，2006

6 徐孝凯．数据结构实验．北京：中央广播电视大学出版社，2001