约瑟夫环实验报告

约瑟夫环实验报告

实 验 报 告

一、实验目的

（1） 掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。

（2） 掌握线性表的链式存储结构的应用。

二、实验内容与实验步骤

（1）实验内容：

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

（2）抽象数据类型和设计的函数描述，说明解决设想。

首先定义一个链表，用其中的data项存储每个人的编号，用password项存储每个人所持有的密码，并且声明一个指针。之后使用CreatList_CL函数来创建一个循环链表，在其中的data和password中存入编号和密码，最后使最后一个节点的next指向L，使其能够形成循环队列。定义了函数Display来显示链表当中的内容，以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能，依次比较，如果某个人所持的密码和m值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。

（3） 简短明确地写出实验所采用的存储结构，并加以说明。

该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。

三、实验环境

操作系统：Windows 7

调试软件名称：VC++

版本号：6.0

上机地点：综合楼311

四、实验过程与分析

（1）主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧妙之处。

本实验中主要的函数包括创建链表、显示链表内容和出列过程四个部分。主要函数的代码如下：

创建链表：

typedef int Datatype;

typedef struct node//链表的定义

{

Datatype data;

int password;

struct node *next;

}ListNode,*CLinkList;

void CreatList_CL(CLinkList *L,int n)//创建一个链表

{

int i,pin;

CLinkList p,q;

(*L)=(CLinkList)malloc(sizeof(ListNode));

if((*L)==NULL)

printf("error\n");

else

(*L)->next=NULL;

q=*L;

for(i=0;i

{

p=(CLinkList)malloc(sizeof(ListNode));

if(p==NULL)

printf("error\n");

printf("请输入第%d个人的密码：",i+1);

scanf("%d",&pin);

p->data=i+1;

p->password=pin;

q->next=NULL;

q->next=p;

q=p;

}

q->next=(*L)->next;//指向L结点，形成

}

创建这个链表的时间复杂度为O(n)，空间复杂度为O（n2）。

显示链表中的信息内容：

void Display(CLinkList *L,int n)

{

int i;

CLinkList p;

p=(*L)->next;

printf("\n显示链表内容\n");

for(i=0;i

{

printf("编号：%2d 密码：%d\n",p->data,p->password);

p=p->next;

}

}

该算法的时间复杂度为O（n）,空间复杂度为O(n2)。

删除结点，完成出列功能：

void Delete_L(CLinkList *L,int n,int m)

{

int i=0,j;

CLinkList p,q;

q=(*L);

p=(*L)->next;

printf("\n删除的顺序：\n");

while(i

{

for(j=0;j

{

q=p;

p=p->next;

}

printf("编号：%d 密码：%d\n",p->data,p->password);

m=p->password;

q->next=p->next;

free(p);

p=q->next;

n--;

}

}

该算法的时间复杂度为O(n2)，空间复杂度为O(n2)。

该设计的巧妙之处在于并不需要额外的空间来存储数据，因而空间复杂度较低，而且线性表的链式存储结构可以用物理位置上的邻接关系来表示结点间的逻辑关系，这样使读者在阅读代码的过程中可以更加方便和便于理解。它可以随机存取表中的任一结点，还可以免插入和删除操作带来的大量的结点的移动，能给结点动态分配内存，这样就不存在存储空间不足的情况，而且循环链表还可以方便的从链表的最后一个结点遍历到链表的第一个结点。使操作更加方便。

（2）你在调试过程中发现了怎样的问题？又做了怎样的改进

1）在最开始的调试阶段，我发现链表插入结束之后，不能按照正常情况下输出链表的内容，只能正常显示第一个人的数据,在显示第二个人的信息是数据为乱码。之后我发现，在插入链表的过程中，我是在执行循环插入数据的循环中将结点的指针指向了第一个结点，因而，在进行链表显示的过程中，第二个结点的内容不是正常的数据。之后我将q->next=(*L)->next;这条指令放到了整个插入循环的外部，这样表示在插入所有数据之后，最后一个结点的指针指向了第一个结点，形成了一个循环队列，此时链表的数据显示正确。

2）再次调试时，我发现人员出列时，只有第一个人出列正常，在第二个人出列时程序自动终止，不能正常显示之后出列的人的信息，并且程序自动终止运行，经过检查我发现在经过一次删除后，没有将指针指向下一个结点，因而出现问题。经过更改，程序运行正常。

3）在实验的开始阶段，数据遍历总是出现问题，经过查找资料我发现了约瑟夫环头结点的特殊性，因此我不再使用头结点，程序便恢复正常了。

（2）测试结果

五、实验结果总结

回答以下问题：

（1） 你的测试充分吗？为什么？你是怎样考虑的？

答：我认为我的测试充分，因为我随机选用了很多组不同的数据进行测试，并且每次测试的结果都是正确的答案，这样选取的数据具有很强的随机性，具有代表性，因而我认为我的测试比较充分。

（2） 你的存储结构的选取是不是很适合这个应用？为什么？

答：我认为我选取的线性链式存储结构适合这个应用，因为首先此题中描述的情景中表示人们按照顺时针的方向进行排队，此时头尾相连，这与循环链表的结构十分相似，使用循环链表的结构，这样可以很方便的从链表的最后一个结点访问到链表的第一个结点，并且这样的存储方式是用物理位置上的邻接关系来表示结点间的逻辑关系，根据这个特点，该种结构可以随机存取表中的任一结点，而且它也可以避免插入和删除操作带来的大量结点的移动，并且可以随时分配空间和释放空间，这样可以减少空间的使用量，并且可以做到灵活的扩充空间，这样的结构很适合这个应用。

（3） 用一段简短的代码及说明论述你的应用中有关插入和删除元素是如何做的？

答：插入元素：首先定义了两个临时指针p和q来分别表示新插入结点的指针和第一个结点的指针，在每次插入之前应该动态的分配内存，输入要输入的信息，并且将各种数据存储到链表中相应的项里，将前一个结点的next赋值为空，再将前一个结点的指针指向下一个结点，此时完成一个元素的插入。依次类推，运用循环来实现所有人的数据的插入，关键代码如下：

p=(CLinkList)malloc(sizeof(ListNode));

if(p==NULL)

printf("error\n");

printf("请输入第%d个人的密码：",i+1);

scanf("%d",&pin);

p->data=i+1;

p->password=pin;

q->next=NULL;

q->next=p;

q=p;

删除元素：进行循环来实现每个元素出列的功能，首先每个人进行循环，一次进行报数，在报到m-1之前都不进行删除元素这个动作，在m时，把此时结点中的password中的数值赋给m然后运用q->next=p->next;将结点删除，同时释放结点p,将人数减1，以此类推完成所有的删除操作，直到所有的元素出列，关键代码如下：

while(i

{

for(j=0;j

{

q=p;

p=p->next;

}

printf("编号：%d 密码：%d\n",p->data,p->password);

m=p->password;

q->next=p->next;

free(p);

p=q->next;

n--;

}

（4）在你的应用中是否用到了头结点？你觉得使用头结点为你带来方便了吗？

答：在我的应用中我没有用到头结点。在实验的一开始，我使用了头结点，但是使用头结点给数据的遍历带来了困难，因此我便放弃使用头结点。

（5）源程序的大致的执行过程是怎样的？

答：首先用编译器编写一个.c的文件，然后编译生成.obj的文件，通过连接将目 标文件连接生成一个.exe文件，之后运行文件就可以执行了。

六、附录

（1）实验设想和建议

这次实验提高了我对数据结构中关于循环链表和顺序表的理解，提高了我的编程能力，学校以后最好可以增加实验课的课时，这样我们可以更大程度的提高自己的编程能力。另外我认为该实验不仅可以使用使用链表指针来实现，还可以使用数组来模拟链表来实现约瑟夫环，用数组的下标来指向前一个和后一个元素，之后进行删除来实现约瑟夫环。

（2）参考资料：《数据结构（第二版）》 闫玉宝编著 清华大学出版社

本文来源：https://www.2haoxitong.net/k/doc/eee532ea4a73f242336c1eb91a37f111f0850d0b.html