【数据结构实验】约瑟夫环

news/2024/11/22 14:15:40/

数据结构实验—约瑟夫环

简介

分别利用线性表的顺序存储形式和链式存储形式，按照出列的顺序印出各人的编号。文末贴出了源代码

需求分析

  1. 每个人的数据m需要随机产生，可正可负且不是实现存储的，这意味着需要使用随机函数来生成每个人的数据。同时，由于数据可正可负，所以应将所有人的排列方式视作一个闭环。在用线性存储形式实现时，在扫描到表尾且仍未结束时，需返回表头继续扫描；在使用链式存储形式时，应使用双向循环链表。
  2. 程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。
  3. 程序的执行的命令包括：
    1）构造约瑟夫环
    2）按顺序印出各人的编号
    构造约瑟夫环时需要用户指定人数，按顺序印出各人的编号前需要用户指定初始数据m。
  4. 测试数据
    1）m的初值为20；n=7,7个人的密码依次为：3,1,7,2,4,8,4，出队顺序为6,1,4,7,2,3,5.
    2）m的初值为8，n=7,7个人的密码依次为：-1,2，-1，-5,3，-5，-3，出队顺序为1,5,2,4,7,6,3.

概要设计

为实现上述功能，可选用顺序存储结构和链式存储结构，为此需要两个抽象数据类型。线性表抽象数据类型的定义为：

ADT List {
数据对象：D={ ai | ai ∈ ElemSet, i=1,2,3,……,n,n≥0}
数据关系：R1={<ai-1，ai>,ai-1,ai∈ D, i=2,3……n,n≥0}
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L。
DestoryList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ClearList(&L)
初始条件：线性表L已存在。
操作结果：将L重置为空表。
ListInsert ( &L, i, e )
初始条件：线性表L已存在，1≤i≤ListLength(L)+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
ListDelete( &L, i, &e )
初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
PriorElem ( L, cur _ e, &pre_e )
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素且不是第1个，则用pre _e返回它的前驱，否则操作失败。
NextElem ( L, cur_ e, &next_e )
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素且不是最后一个，则用next _ e返回它的后继，否则操作失败。
GrtElem(L , i , &e)
初始条件：线性表L已存在,1≤i≤ListLength(L)+1。
操作结果：用e返回L中第i个数据元素的值。
ListEmpty (L)
初始条件：线性表L已存在。
操作结果：若L 为空表，则返回TRUE，否则返回 FALSE。
ListLength (L)
初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。
LocateElem ( L,e, compare() )
初始条件：线性表L已存在，compare()是判定函数。
操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值0。
ListTraverse ( L,visit())
初始条件：线性表L已存在。
操作结果：依次对L的每个数据元素调用函数 visit()。一旦visit()失败，则操作失败。
}
ADT List
  1. 本程序包含3个模块：
    1）主程序模块
int main()
{初始化；接受命令；处理命令；
}

2）线性表单元模块—实现线性表的抽象数据类型；
3）约瑟夫环单元模块—实现将成员存储在线性表中，并将线性表中的成员按指定顺序出队；
各模块之间的调用关系如下：

Created with Raphaël 2.3.0 开始 主程序模块 约瑟夫单元模块 线性表单元模块 结束

详细设计

  1. 顺序存储结构实现

1） 元素类型

#define ElemType people  //元素类型
typedef struct
{int peopleID;int data;
}people;

2） 所用到的线性表基本操作

typedef struct
{ElemType *elem; int length;int listsize;
} SqList;
Status InitList_Sq(SqList &L,int LIST_INIT_SIZE);
// 构造一个空的线性表L。
void print_Sq(SqList &L);
//打印线性表中所有元素
Status DeleteK(SqList &a,int i,int k);
//从线性表a中删除第i个元素起的k个元素
Status ListInsert_Sq(SqList &L, int i, ElemType e);
//若线性表L存在，将元素e插入到L第i个位置 
Status ListDelete_Sq(SqList &L,int i,ElemType &e);
//若线性表L以及第i个元素存在，将其从表中删除并保存到e中

3） 程序源代码

/*库函数*/ 
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<time.h>
using namespace std;/*宏定义*/
#define LISTINCREMENT 10 
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define ElemType people/*线性表定义*/
typedef int Status; 
typedef struct
{int peopleID;int data;
}people;typedef struct
{ElemType *elem; int length;int listsize;
} SqList;/*函数声明*/
Status InitList_Sq(SqList &L,int LIST_INIT_SIZE);// 构造一个空的线性表L。
void print_Sq(SqList &L);
Status DeleteK(SqList &a,int i,int k);//2-10 从线性表a中删除第i个元素起的k个元素
Status ListInsert_Sq(SqList &L, int i, ElemType e); 
Status ListDelete_Sq(SqList &L,int i,ElemType &e);
Status Josephus(int peopleNum,int firstdata);int main()
{cout<<"线性表（数组）解决约瑟夫问题\n";cout<<"请确定人数\n";int peopleNum;int firstdata;peopleNum=60000;//firstdata=peopleNum/2;cin>>peopleNum;cout<<"请确定初始密码\n";cin>>firstdata;clock_t start, stop;double duration;start=clock();int result=Josephus(peopleNum,firstdata);stop=clock();duration=((double)(stop-start))/CLK_TCK;if(result==OK)cout<<"执行成功"<<endl;elsecout<<"执行失败"<<endl;printf("线性表（数组）算法(peopleNum=%d,firstdata=%d)花费时间为%fs\n",peopleNum,firstdata,duration);return 0;
}Status InitList_Sq(SqList &L,int LIST_INIT_SIZE) 
{  L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if (!L.elem) return OK;        // 存储分配失败L.length = 0;                  // 空表长度为0L.listsize = LIST_INIT_SIZE;   // 初始存储容量return OK;
} // InitList_Sqvoid print_Sq(SqList &L)
{cout<<"编号\t密码"<<endl;for(int i=0;i<L.length;i++) cout<<L.elem[i].peopleID<<"\t"<<L.elem[i].data<<endl;
}Status DeleteK(SqList &a,int i,int k)//2-10 从线性表a中删除第i个元素起的k个元素  
{if(i<1||k<0||i+k>a.length) return INFEASIBLE ;else{for(int j=i-1;j<i-1+k;j++) {a.elem[j]=a.elem[j+k];a.length--;}return OK;}
}Status ListInsert_Sq(SqList &L, int i, ElemType e) 
{  // 算法2.4// 在顺序线性表L的第i个元素之前插入新的元素e，// i的合法值为1≤i≤ListLength_Sq(L)+1ElemType *p;if (i < 1 || i > L.length+1) return ERROR;  // i值不合法if (L.length >= L.listsize) {   // 当前存储空间已满，增加容量ElemType *newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType));if (!newbase) return ERROR;   // 存储分配失败L.elem = newbase;             // 新基址L.listsize += LISTINCREMENT;  // 增加存储容量}ElemType *q = &(L.elem[i-1]);   // q为插入位置for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;// 插入位置及之后的元素右移*q = e;    // 插入eL.length=L.length+1;;   // 表长增1return OK;
} // ListInsert_SqStatus ListDelete_Sq(SqList &L,int i,ElemType &e) 
{if((i<1)||(i>L.length))return ERROR;ElemType *p=&(L.elem[i-1]);e=*p;ElemType *q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;return OK;
}Status Josephus(int peopleNum,int firstdata)
{if(peopleNum<=0) return ERROR;SqList L;InitList_Sq(L,peopleNum); if(firstdata==0) return ERROR; int a,b;people x;srand((int)time(NULL));for(int i=0;i<peopleNum;i++){	a = rand()%peopleNum+1;b=rand()%peopleNum;x.data=a*pow(-1,b);x.peopleID=i+1;ListInsert_Sq(L,i+1,x);}print_Sq(L);cout<<"现在开始\n";cout<<"编号\t密码"<<endl;people e;int outpeople,lastposition=0; if(firstdata>0)outpeople=firstdata%peopleNum;elseoutpeople=(peopleNum+2-((-1)*firstdata)%peopleNum)%peopleNum;while(L.length>0){if(outpeople==0) outpeople=L.length;ListDelete_Sq(L, outpeople,e);if(L.length){if(e.data>0){lastposition=outpeople%L.length;outpeople=(e.data+lastposition-1)%L.length;}else{if(outpeople==1) lastposition=L.length;else lastposition=outpeople-1;outpeople=e.data+lastposition-1;if(outpeople>0) outpeople=outpeople%L.length;else outpeople=(L.length+2-((-1)*outpeople)%L.length)%L.length;}	}cout<<e.peopleID<<"\t"<<e.data<<"\n";}return OK;
}
  1. 链式存储结果实现
    1） 元素类型
#define ElemType int

2） 所用到的线性表的基本操作

typedef struct DuLNode
{ElemType data;int number; //记录顺时针的编号 struct DuLNode *prior;struct DuLNode *next;
}DuLNode, *DuLinkList;
void print(DuLinkList L);
//打印双向循环链表的每个元素
Status  InitDuLinkList(DuLinkList &head); 
//构建双向循环链表  
Status  InsertDuLinkList(DuLinkList &head,ElemType e); 
//若双向循环链表head存在，向表头插入数据e 
Status DelDuLinkList(DuLinkList &head,int m,ElemType &e); 
//若存在，则删除并返回第m个结点的数据,并把头结点赋给删掉结点的下一个

3） 源代码

/*头文件*/ 
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<time.h>
using namespace std;/*宏定义*/
#define ElemType int
#define OK 1
#define INFEASIBLE -1
#define ERROR -1/*双向循环链表定义*/
typedef struct DuLNode
{ElemType data;int number; //记录顺时针的编号 struct DuLNode *prior;struct DuLNode *next;
}DuLNode, *DuLinkList; 
typedef int Status;/*函数声明*/
void print(DuLinkList L);
Status  InitDuLinkList(DuLinkList &head); //构建双向循环链表  
Status  InsertDuLinkList(DuLinkList &head,ElemType e); //向循环链表插入数据e 
Status DelDuLinkList(DuLinkList &head,int m,ElemType &e); //删除并返回第m个结点的数据,并把头结点赋给删掉结点的下一个
Status Josephus(int n,int m); //报数大于0，则顺时针数，确定出栈人后，出栈人顺时针下一位继续数//报数小于0，则逆时针数，确定出栈人后，出栈人逆时针下一位继续数int main()
{clock_t start, stop;int m,n;//n=10000;
//	m=n/2;cout<<"解决约瑟夫环问题\n";cout<<"请输入人数n：\n";cin>>n;if(n<=0) return ERROR;cout<<"请指定初值m：\n";cin>>m;double duration;start=clock();int result=Josephus(n,m);stop=clock();duration=((double)(stop-start))/CLK_TCK;if(result==OK)cout<<"执行成功"<<endl;elsecout<<"执行失败"<<endl;printf("双向循环链表算法花费时间为%fs\n",duration);return 0;
}Status  InitDuLinkList(DuLinkList &head) //构建双向循环链表 
{//创建一个首元节点，链表的头指针为headhead=(DuLinkList)malloc(sizeof(DuLNode));//对节点进行初始化head->prior=NULL;head->next=NULL;return OK;
}Status  InsertDuLinkList(DuLinkList &head,ElemType e) //向循环链表插入数据e 
{if(head->next==NULL||head->prior==NULL) //如果链表为空,则直接给head节点赋值 {head->data=e;head->number=1;head->next=head;head->prior=head; return OK;} //创建新的节点并初始化DuLinkList body=(DuLinkList)malloc(sizeof(DuLNode));if(!body) return ERROR;body->data=e;head->prior->next=body;body->prior=head->prior;body->number=((body->prior)->number)+1;body->next=head;head->prior=body;return OK;
}Status DelDuLinkList(DuLinkList &head,int m,ElemType &e) //删除并返回第m个结点的数据,并把头结点赋给删掉结点的下一个 
{int number;if(head->next==NULL&&head->prior==NULL) return ERROR;if(head->next==head&&head->prior==head){e=head->data;number=head->number;head->next=head->prior=NULL;printf("%d\t%d\n",number,e);return OK;}int count;DuLinkList body=head,temp;if(m>0){count=1;while(count<m){head=head->next;count++;}e=head->data;number=head->number;printf("%d\t%d\n",number,e);head->prior->next=head->next;head->next->prior=head->prior;temp=head;head=head->next;free(temp);return OK;}else if(m<0){count=-1;while(count>m){head=head->prior;count--;}e=head->data;number=head->number;printf("%d\t%d\n",number,e);head->prior->next=head->next;head->next->prior=head->prior;temp=head;head=head->prior;free(temp);return OK;}else //m==0head=head->prior;e=head->data;number=head->number;printf("%d\t%d\n",number,e);head->prior->next=head->next;head->next->prior=head->prior;temp=head;head=head->next;free(temp);return OK;
}  
void print(DuLinkList L)
{DuLinkList head=L;while(L->next!=head) {cout<<L->number<<"\t";cout<<L->data;cout<<endl;L=L->next;}cout<<L->number<<"\t";cout<<L->data;cout<<endl;
}Status Josephus(int n,int m) //报数大于0，则顺时针数，确定出队人后，出对人顺时针下一位继续数//报数小于0，则逆时针数，确定出栈人后，出栈人逆时针下一位继续数
{if(n<=0) return ERROR;int e;DuLinkList L;InitDuLinkList(L);int a,b,x;srand((int)time(NULL));/**/for(int i=0;i<n;i++){a = rand()%n+1;b=rand()%n;x=a*pow(-1,b);InsertDuLinkList(L,x);}printf("已随机生成%d个人的数据，顺时针依次为：\n",n);print(L);cout<<"出栈顺序依次为："<<endl;cout<<"编号\t数值\n"; while(L->next){if(m>0) m=m%n;else if(m<0){m=((-m)%n)*(-1);} else return ERROR;DelDuLinkList(L,m,m);n--;}return OK;
}

http://www.ppmy.cn/news/49335.html

相关文章

redis设计与实现读书笔记（2）

redis设计与实现读书笔记（2）

今天看的是关于单机数据库&#xff0c;RDB持久化以及AOF持久化的内容。 关于单机数据库 1.默认数据库数量 redis的服务器默认是会创建16个数据库&#xff0c;每个客户端访问的时候都要指定自己的目标数据库。 select可以切换目标数据库。 注意事项 到目前为止&#xff0c…
阅读更多...
瓷器：伟大发明的特点和能量的作用

瓷器：伟大发明的特点和能量的作用

文章目录 引言I 瓷器的独特性1.1 用途特别大。1.2 影响力广泛，经济意义大1.3 难以替代性。1.4 瓷器的发明特别难II 上釉2.1 上釉方法2.2 发明和发现的区别III 发明的必然性和偶然性3.1 偶然性3.2 偶然性的背后常常有着必然性。3.3 一种技术会抑制另一种技术引言 从预先要求和…
阅读更多...
数据库方言：了解不同数据库系统的特性和差异

数据库方言：了解不同数据库系统的特性和差异

摘要&#xff1a; 数据库方言指的是不同数据库系统在 SQL 语法和实现上的差异。本文将探讨数据库方言的概念、为什么会存在方言、常见数据库方言的特点以及如何处理方言差异。 1. 什么是数据库方言&#xff1f; 数据库方言是指不同数据库系统在 SQL 语法、数据类型、函数和存…
阅读更多...
软考 - IP地址与网络划分

软考 - IP地址与网络划分

一.IP组成 1.1 首个八位字节规则 1.2 地址掩码 IP地址掩码 标准地址掩码 A类&#xff1a;255.0.0.0 前1个字节是网络号 后3个字节是主机号 B类&#xff1a;255.255.0.0 前2个字节是网络号 后2个字节是主机号 C类&#xff1b;255.255.255.0 前3个字节是网络号 后1个字节是主机号…
阅读更多...
赛效：怎么用改图鸭进行一键Logo设计?

赛效：怎么用改图鸭进行一键Logo设计?

改图鸭工具是一款在线图像处理工具&#xff0c;可以对图片进行大小调整、添加色彩、滤镜等&#xff0c;用户使用改图鸭可快速轻松地对多种图像进行处理操作&#xff0c;另外&#xff0c;改图鸭工具还支持一键进行Logo设计&#xff0c;很多人对改图鸭工具比较陌生&#xff0c;不…
阅读更多...
【头歌C语言程序设计】结构体解答

【头歌C语言程序设计】结构体解答

写在前面 这道题总体来说还是偏难的&#xff0c;如果只看代码比较难以理解&#xff0c;当结构体的文章发出后&#xff0c;就有许多小伙伴问我这个问题&#xff0c;我开始意识到&#xff0c;可能我对这道题所作的解答还不够&#xff08;不装了&#x1f601;&#xff0c;根本没有…
阅读更多...
揭秘移动云大会展区前沿科技

揭秘移动云大会展区前沿科技

2023年4月25日-26日 我们苏州金鸡湖国际会议中心见&#xff01; 1场重磅主论坛、10场分论坛、2600㎡展区 数字中国新未来 尽在2023移动云大会 2023移动云大会设有中国移动和合作伙伴两大展区&#xff0c;联合40余家优质合作伙伴&#xff0c;全方位展示移动云在自主能力、行…
阅读更多...
【程序员面试金典】面试题 02.07. 链表相交

【程序员面试金典】面试题 02.07. 链表相交

【程序员面试金典】面试题 02.07. 链表相交 题目描述解题思路 题目描述 描述&#xff1a;给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#…
阅读更多...
最新文章

Copyright @ 2022~2023