数据结构实验—约瑟夫环

简介

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

需求分析

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

2. 本程序包含3个模块：
   1）主程序模块

int main()
{初始化；接受命令；处理命令；
}

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

详细设计

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;
}

2. 链式存储结果实现
   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;
}

化学之窗