分别用数组和链表解决约瑟夫环问题。

《数据结构》实验报告

班级:JS001001 姓名:葛赛磊学号:2010300006 E-mail:1015562653@https://www.wendangku.net/doc/5511120584.html, 日期:2012.10.19

◎实验题目:约瑟夫环问题

◎实验目的：分别用数组和链表解决约瑟夫环问题。

◎实验内容：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

一、需求分析

1、输入的形式和输入值的范围：

总人数ｎ，整型（ｉｎｔ）

开始报数的号数：ｍ，整型（ｉｎｔ）（ｍ＜＝ｎ）

数到Ｍ时出列的Ｍ值：d，整型（ｉｎｔ）

2、输出的形式:

依次出列的号数：整型

3、程序所能达到的功能：

程序实现的功能是把n个人按照规定输出报号的次序

4、测试数据：

人数 8 开始报数的号 3 报到 5出列

输出的结果是：

7 2 5 1 6 4 8 3

人数 16 开始报数的号 8 报到 9出列

输出的结果是：

16 8 1 10 4 14 11 7 6 9 13 3 2 12 5 15

二概要设计

1、抽象数据类型的定义

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

①对链表存储形式下的

循环链表的结构体定义

typedef struct A

{

int data;

struct A *next;

}list,*node;

链表的创建函数：

x createlist(x *L,int n)

双重循环的设置：

Do

{

用for循环查找并删除节点；

}while（链表非空）；

②对数组存储形式下的数据类型定义

输入数据，控制数据及计数器变量的设置：int count=0,s,d,n,m,i,l; 数组的定义：int a[100];

（2）主程序的流程：

①链表实现：

1.根据输入环的长度创建链表并给其中元素赋初值；

2.根据报数的起点对链表指针进行移动；

3.利用双重循环进行元素的删除和输出；

②数组实现：

1.根据输入环的长度对数组进行初始化；

2.设置一个元素出列的函数；

3.执行循环，直到所有的元素都出列；

（3）其函数之间调用关系如下：

①链表实现:

②数组实现：

实现较为简单，没有定义和调用相关函数；

注：大箭头表示函数调用，小箭头表示程序执行过程；

三详细设计

①链表实现:

1.元素类型

typedef int ElemType;

typedef struct LNode

{

ElemType data;

struct LNode *next;

} LinkList,*x;

2．每个模块的分析：

（1）主程序模块：

//主函数

int main()

{

int n,s,d,i,j;

x h,l,p,r;

printf("请输入队列长度: ");

scanf("%d",&n);

//创建长度为n的循环链表；

h=createlist(h,n);

printf("请输入开始报数人的号数: "); scanf("%d",&s);

//将指针指向报数起始位置；

l=h;

for(i=1;i

{

l=l->next;

}

r=l;

printf("请输入开始出列的号数: "); scanf("%d",&d);

//进行元素删除及输出直至链表为空；

do

{

//查找需要进行删除的元素；

for(j=1;j

{

p=r;

r=r->next;

}

//对元素进行删除并释放节点；

p->next=r->next;

printf("%d ,",r->data);

if(r==h) h=h->next;

free(r);

r=p->next;

}while(h->next!=h);

printf("%d",h->data);

return 0;

}

（2）创建链表并初始化链表；

x createlist(x *L,int n)

{

x a,b;

int i;

L=(x *)malloc(sizeof(x));

a=L;

a->data=1;

for(i=1;i

b=(x*)malloc(sizeof(x));

a->next=b;

b->data=i+1;

a=b;

}

a->next=L;

return L;

②数组实现：

主函数模块：

#include

#include

int main()

{

int count=0,s,d,n,m,i,l;

int a[100];

printf("请输入环的长度： ");

scanf("%d",&n);

m=n;

//建立数组并对其进行初始化；

for(i=0;i

a[i]=i+1;

printf("请输入报数的起点: ");

scanf("%d",&s);

l=s-1;

printf("请输入出列的间隔： ");

//对数组中元素进行输出和覆零处理，直至数组中所有元素均为零； scanf("%d",&d);

do{

//查找并输出数组中满足条件的元素，并将其赋值为零；

/*while(count!=d)

{

if(l>n-1) l=l-n;

if(a[l]!=0) count++;

l++;

}

l--;

printf("%d ",a[l]);

m--;

a[l]=0;*/

l++;

if(l>n-1) l=l-n;

count=0;

}while(m!=0);

return 0;

}

四使用说明、测试分析及结果

1.程序使用说明；

（1）本程序的运行环境为Codeblocks10.5；

（2）进入演示程序后即显示提示信息：

请输入队列长度:

请输入报数的起点:

请输入开始出列的号数:

输出结果：

2、测试结果与分析；

请输入队列长度:10

请输入报数的起点:2

请输入开始出列的号数:4

输出结果：5 9 3 8 4 1 10 2 7 6

3、调试过程中遇到的问题是如何解决以及对设计与实现的回顾讨论和分析；

在利用链表实现时，输出结果中始终存在一个很大的常数，由于链表的建立中用到了指针，很可能是链表中指针指向错误所致，经修改解决；在用数组实现时，输出数据错误，并出现零和负数，请教同学分析认为很可能是数组元素越界所致，对循环内部结构进行调整，解决了问题。

4、运行界面。

五、实验总结

(1)你在编程过程中花时多少？

一个晚上。

(2)多少时间在纸上设计？

半小时。

（3）多少时间上机输入和调试？

四个小时。

（4）多少时间在思考问题？

一个小时

（5）遇到了哪些难题？

循环链表的输出时出现问题，调用函数时出现错误。

（6）你是怎么克服的？

根据提示检查错误，上互联网进行搜索，求助于同学。

（7）你的收获有哪些？

使用指针时要慎重，学会独立解决自己遇见的问题。

教师评语：

实验成绩：

指导教师签名：

批阅日期：

《数据结构》实验报告 设计循环单链表

《数据结构》实验报告 1、实验名称:设计循环单链表 2、实验日期: 2013-3-26 3、基本要求： 1）循环单链表的操作，包括初始化、求数据元素个数、插入、删除、取数据元素； 2）设计一个测试主函数实际运行验证所设计循环单链表的正确性。 4、测试数据： 依次输入1，2，3，4，5，6，7，8，9，10，删除5，再依次输出数据元素。 5、算法思想或算法步骤: 主函数主要是在带头结点的循环单链表中删除第i个结点，其主要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。 6、模块划分： 1）头文件LinList.h。头文件LinList.h中包括：结点结构体定义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作； 2）实现文件dlb.cpp。包含主函数void main(void)，其功能是测试所设计的循环单链表的正确性。

7、数据结构： 链表中的结点的结构体定义如下： typedef struct Node { DataType data; struct Node *next; }SLNode; 8、源程序： 源程序存放在两个文件中，即头文件LinList.h和实现文件dlb.cpp。//头文件LinList.h typedef struct Node { DataType data; struct Node *next; }SLNode; void ListInitiate(SLNode **head) //初始化 { *head=(SLNode *)malloc(sizeof(SLNode)); //申请头结点，由head指示其地址 (*head)->next=*head; }

单循环链表基本操作

/*1、CreateList( )：创建一个带头结点的空的单循环链表； 2、InsertList( )：输入一组数据，以0表示输入结束, 并依次建立各个元素结点，逐个插入到单循环链表尾 3、DeleteList( )：删除单循环链表的从第i个数据元素开始的m个数据元素,同时释放被删结点空间 4. ListPrint( ):将单向循环链表的数据元素从表头到表尾依次显示 5. DevList( )：将此单循环链表拆分成两个单循环链表，其中一个包含所有的数据元素为偶数的结点， 另一个包含所有的数据元素为奇数的结点.*/ #include #include typedef struct node{ int data; struct node *next; }LNode,*linklist; void createlist(linklist &L) {linklist p=L; p->next=p; } void insertlist(linklist &L) {int x; linklist p=L,q; scanf("%d",&x); while(x!=0) {q=(linklist)malloc(sizeof(LNode)); q->data=x;q->next=NULL; p->next=q; p=q; scanf("%d",&x); } q->next=L; } void printlist(linklist L) {linklist p=L->next ; if(p==L)printf("这是一个空表！\n"); while(p!=L){printf("%2d",p->data);p=p->next;} printf("\n"); } void deletelist(linklist &L,int i,int m) {linklist p=L,q; for(int n=1;nnext; if(p==L)p=p->next; }

约瑟夫环问题单循环链表解法讲解

约瑟夫环问题单循环链表解法 Description 约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。 Input 第一行有2个数，M和N。(0 第二行有 N 个数，表示每个人的 M 值。 Output 按照样例的格式，输出所有人退出环的顺序。 Sample Input 4 6 5 4 2 3 4 2 Sample Output 4,1,2,3,6,5 Source #include"iostream" #include"cstdio" #include"cstdlib" using namespace std; typedef struct cnode{ int label; int data; struct cnode *next; }cnode; int m,n,i,value,j; cnode *p,*q;

int main( { cin>>m>>n; cnode *clist; q=(cnode *malloc(sizeof(cnode; clist=q; for(i=1;i<=n;i++ { //cin>>value; cin>>value; p=(cnode *malloc(sizeof(cnode; //p=new cnode; p->label=i; p->data=value; p->next=NULL; q->next=p; q=p; if(i==nq->next=clist->next; } p=clist; //cout< label< for(i=1;i<=n;i++ { for(j=1;j { p=p->next; } q=p->next; m=q->data;

List-DuLinkedList-将单向循环链表改为双向的

List-DuLinkedList-将单向循环链表改为双向的 2.32 已知有一个单向循环链表，其每个结点中含有三个域：prior,data和next， 其中data为数据域，next为指向后继结点的指针域，prior也为指针域，但它的值为NULL。试编写算法将此单向循环链表改写为双向循环链表，即使prior成为指向前驱结点的指针域#include #include #define N 6 typedef struct DuLNode { //双向循环链表结点 char data; struct DuLNode *prior; struct DuLNode *next; } DuLNode, *DuLinkedList; void createLinkedList(DuLinkedList &L) { //创建双向循环链表（暂时只设NEXT指针）DuLinkedList p; int i; L = (DuLinkedList)malloc(sizeof(DuLNode)); L->data = NULL; L->next = L; L->prior = NULL; for(i=N; i>0; i--) { p = (DuLinkedList)malloc(sizeof(DuLNode)); p->data = getchar(); p->next = L->next; L->next = p; } } void singleToDu(DuLinkedList &L) { //将Prior指针添加上 DuLinkedList p, q; p = L; q = p->next; while(q != L) { q->prior = p; p = q; q = q->next; } q->prior = p; } void printList(DuLinkedList L) { //打印双向循环链表 DuLinkedList p; if(L->prior) { printf("链表的前驱指针存在，现采用反向遍历\n"); p = L->prior; while(p != L) {printf("%c ", p->data); p = p->prior;} } else { printf("链表的前驱指针不存在，将采用正向遍历\n"); p = L->next; while(p != L) {printf("%c ", p->data); p = p->next;} } }

一步一步写算法(之循环单向链表)

软件英才网软件行业驰名招聘网站 一步一步写算法（之循环单向链表） 前面的博客中，我们曾经有一篇专门讲到单向链表的内容。那么今天讨论的链表和上次讨论的链表有什么不同呢？重点就在这个"循环"上面。有了循环，意味着我们可以从任何一个链表节点开始工作，可以把root定在任何链表节点上面，可以从任意一个链表节点访问数据，这就是循环的优势。 那么在实现过程中，循环单向链表有什么不同？ 1）打印链表数据 1void print_data(const LINK_NODE* pLinkNode) 2{ 3 LINK_NODE* pIndex = NULL; 4if(NULL == pLinkNode) 5return; 6 7 printf("%d\n", pLinkNode->data); 8 pIndex = pLinkNode->next; 9while(pLinkNode != pIndex){ 10 printf("%d\n", pIndex->data); 11 pIndex = pIndex ->next; 12 } 13} 以往，我们发现打印数据的结束都是判断指针是否为NULL，这里因为是循环链表所以发生了变化。原来的条件（NULL != pLinkNode）也修改成了这里的（pLinkNode != pIndex）。同样需要修改的函数还有find函数、count统计函数。 2）插入数据 14STATUS insert_data(LINK_NODE** ppLinkNode, int data) 15{ 16 LINK_NODE* pNode; 17if(NULL == ppLinkNode) 18return FALSE; 19 20if(NULL == *ppLinkNode){ 21 pNode = create_link_node(data); 22 assert(NULL != pNode);

数据结构C语言版 循环链表表示和实现

数据结构C语言版循环链表表示和实现.txt37真诚是美酒，年份越久越醇香浓烈；真诚是焰火，在高处绽放才愈显美丽；真诚是鲜花，送之于人，手有余香。/* 数据结构C语言版循环链表表示和实现 P35 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月10日 */ #include #include #include typedef int ElemType; // 线性表的单链表存储结构 typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; // 要好好区分什么是头结点((*L)->next)，尾结点(*L)，以及第一个结 // 点(*L)->next->next,设立尾指针的单循环链表(头尾相接，即头结点 // 与尾结点是一样的，它们都没数据域. // 构造一个空的循环链表L int InitList_CL(LinkList *L) { // 产生头结点,并使L指向此头结点 *L = (LinkList)malloc(sizeof(struct LNode)); if(!*L) exit(0); // 指针域指向头结点，这样就构成了一个循环，空表循环，*L为表尾 (*L)->next = *L; return 1; } // 销毁循环链表L int DestroyList_CL(LinkList *L) { LinkList q, p = (*L)->next; // p指向头结点 while(p != *L) // 没到表尾，*L为表尾 { q = p->next; free(p);

单循环链表解决Josephus问题

//假设n个人围坐在圆桌周围，现在从第s个开始报数，数到m的那个人出局，下一个开始重新报数，如此反复，知道所有的人都出局为止。 #define _CRT_SECURE_NO_WARNINGS #include #include typedef struct cirlist{ int data; struct cirlist *next; }CirNode, *Cirlist; Cirlist CreateList_L(Cirlist L, int n)//正序输出链表； { Cirlist p = NULL, s; L = (Cirlist)malloc(sizeof(CirNode)); L->next = L;//建立头结点； s = L;//用一个中间变量承接L，保持L的地址不变； printf("输入链表的值：\n"); for (int i = 0; i < n; i++)//尾插法 { p = (Cirlist)malloc(sizeof(CirNode)); scanf("%d", &p->data); s->next = p; s = p; } p->next = L; return L;//如果不用s中间变量，利用尾插法L的地址是变化的； } void jopus(Cirlist L, int n, int s, int m) { Cirlist p = L->next, q = L; int i, j; for (i = 1; i < s; i++) { p = p->next; } for (i = 0; i < n; i++) { for (j = 1; j < m; j++) { q = p; p = p->next; if (p == L) { q = p; p = p->next;

单循环链表解决约瑟夫问题

//用单循环链表解决约瑟夫问题 #include using namespace std; typedef struct Lnode { int data; Lnode *next; }Lnode; class JosephusCircle { public: void creat_list(); void Josephus(); private: int n; int s; int m; Lnode *head; }; void JosephusCircle::creat_list() //初始化 { cout<<"请依次输入，约瑟夫圈人数、报数起始位置、报几个数："<>n>>s>>m; if(m==0) { cout<<"报数的个数不许为0！"; cout<next=head; tail=head; for(int i=0;idata=(i+1); tail->next=p; tail=p; p->next=head->next; } }

void JosephusCircle::Josephus() { Lnode *p=head->next; Lnode *q=head; //q指针紧随其后 int j=1; while (j!=s) //找到报数起点 { p=p->next; q=q->next; ++j; } while (p!=q) { for(int i=0;inext; q=q->next; } cout<data<<' '; //输出前n-1个出圈人编号 p=p->next; //删除节点 q->next=p; } cout<data; //输出最后一个出圈人编号} void main() { JosephusCircle Jose; Jose.creat_list(); cout<<"出圈顺序为："<

C语言单向循环链表实现实现约瑟夫环

C语言实现约瑟夫环问题------单向循环链表实现 问题描述： 有n个人围成一圈进行报数游戏，从第一个人开始报到m的人出圈，接下来有从下一个人开始，。。。。。。。一次这样往复，直到最后一个人也出圈，求他们的出圈顺序？（例如8个人，凡报3的人出圈，则他们出圈顺序是3 ，6, 1，，5 ，2 ，8，4 ，7） #include #include typedef struct node{ int value; struct node *next; }NODE; //*********************建立循环链表(尾插法建立)***********// NODE *createlink(int number)

{ NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); //***建立第一个节点***// head->value=i; p=head; for(i=2;i<=number;i++) //***建立剩下的number-1节点****// { q=(struct node*)malloc(sizeof(struct node)); if(q==0) return 0; p->next=q; p=q; p->value=i; } p->next=head; return head; } //*****************建立约瑟夫环********************// void jose(NODE *p,int number,int n) {

用单循环链表解决约瑟夫问题

问题背景 据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 问题描述 设n个人围坐在一圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局者的下一人重新开始报数，数到第m个人，再让他出局······如此反复，直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n、s和m，求出这个n个人的出局序列，数据结构采用单循环链表。 程序代码：(已通过) #include #include #include #include using namespace std; typedef struct clnode{ int data; struct clnode *next; }clnode,*linklist; //定义链表结构体，结构体包含两个元素：数据元素data和后继指针next void Create_L(linklist &L,int n) //构造一个以L为头结点，长度为n的单循环链表，节点元素依次为1.2.3...n { L=(linklist)malloc(sizeof(clnode)); linklist p; p=L;

带头结点的并具有头尾指针的单循环链表

长治学院 课程设计任务书 课程名称：数据结构课程设计 设计题目：带头结点的并具有头尾指针的单循环链表 系别：计算机系 专业：网络工程 学生姓名: 王鲁俊学号: 07407320 起止日期: 2008年 11月08 日~ 2008年12月18 日指导教师:孙俊杰

长治学院 目 录 第一 章 需求 分析 ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ -3 第二章开发过程-------------------------------------------------------------------------3 2.1系统目标----------------------------------------------------------------------3

2.2设计出友好的界面---------------------------------------------------- ---3 2.3实现 基本功能----------------------------------------------------------------3 2.5功能划分----------------------------------------------------------------------3 第三章系统设计--------------------------------------------------4 3.1系统设计方法-------------------------------------------4 3.2数据结构设计-------------------------------------------4 3.3数据结构设计概述---------------------------------------4 3.4数据实体类型-------------------------------------------4 3.5流程图-------------------------------------------------5 3.6程序中的源代码-----------------------------------------5 第四章附录-----------------------------------------------------13 第一章需求分析 1.编写带头结点头尾指针的单循环链表，并实现功能如下： 1.编写该单循环链表的环境 2.保存数据 3.建立密码，密码修改 4.单循环链表的位置查找.插入.删除.排序等操作 第二章开发过程 2.1系统目标

西安石油大学数据结构实验1-单循环链表

实验报告 课程名称：数据结构 上机实验名称：单循环链表 专业班级：计1201 指导教师：朱战立 学生姓名：张文江 学号：201107010122

一、题目：单循环链表 二、问题描述： (1)设计单循环链表的操作，包括初始化、求元素个数、插入、删除等。 (2)设计输出单循环链表中所有数据元素的输出函数。 (3)设计一个测试主函数。其中数据元素的类型任意。 三、基本要求： （1）把头节点的单循环链表设计为头文件。 （2）用带头节点的单循环链表作为存储结构。 四、测试数据： 输入10个字符，删除特定位置字符后统计字符个数，最后输出剩余字符。五、算法思想：单循环链表是利用单链表进行部分修改而来；其原理是单链表最后一个节点的指针重新指回第一个节点依次进行循环。 六、模块划分： （1）头文件lianbiao.h。其中包括了结点结构体定义、初始化操作、插入一个结点、删除一个结点、取一个数据元素操作及判断单循环链表是否为空等操作。 （2）源文件测试.cpp。其包括了： void main(void)函数：主函数，其功能是给出测试数据，建立测试数据 值得带头结点单循环链表。 ListInitiate(&head)函数：初始化单循环链表。 ListInsert(head,i,x[i])函数：往单循环链表中插入结点。 ListDelete(head,4,&x[i])函数：删除指定结点。 ListLength(head)函数：统计单循环链表中元素个数。 Output(head)函数：输出单循环链表中元素。 Destroy(&head)函数：程序执行完之后撤销单循环链表。 七、数据结构： 带头结点单循环链表结点的结构体定义如下： typedef struct Node{ DataType data; struct Node *next; }SLNode;