数据结构之线性表的应用
1．实验题目
约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1 开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
2．需求分析
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
① 程序所能达到的功能：完成单向循环链表的建立，以及相应操作解决约瑟夫问题。
② 测试数据：
m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5）
3．概要设计
1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
ADT LinkList{
数据对象：D={n|n∈EvaluList，0＜n≤30}
数据关系：R={<n-1,n>|n,n-1∈D}
基本操作：
EvaluList（int n）
操作结果：对单向循环链表进行尾插入赋值
size(LinkList L)
初始条件：单链表L已存在
操作结果：求出其节点个数
ScanList(LinkList L)
初始条件：单链表L已存在
操作结果：若单链表为空，则输出“人数为空”，否则依次遍历单链表中元素。
Joseph(LinkList &L,int m)
初始条件：单链表L已存在
操作结果：若单链表为空，输出“人数为空，出列结束”，否则根据每一轮的上限初值m输出对应的编号n。}
2）本程序包含5个函数：
①主函数main（）
②定义单链表进行尾插赋值EvaluList（）
③求链表节点个数size（）
④遍历单向循环链表ScanList（）
⑤约瑟夫环的实现Joseph（）
4．详细设计
实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模
块也都需要写出伪码算法。
1）结点类型和指针类型
1 typedef struct LNode{
2
3 int number;
4
5 int data;
6
7 struct LNode *next;
8
9 }LNode, *LinkList;
2）单链表的基本操作
1 LinkList EvaluList(int n){
2
3 LinkList p=new LNode;
4
5 输入第i个人的密码key；
6
7 p->data=key;
8
9 p->number=I;
10
11 p->next=L->next;
12
13 L->next=p;
14
15 L=L->next;
16
17 return L;}
18
19 int size(LinkList L){
20
21 LinkList p=L->next;
22
23 while(p!=L)
24
25 {
26
27 i++;
28
29 p=p->next;
30
31 }
32
33 return i;}
34
35 Status ScanList(LinkList L)
36
37 { p->data;
38
39 p=p->next;
40
41 while(p!=L)
42
43 {p->data;
44
45 p=p->nex
46
47 return TRUE;}
48
49 Status Joseph(LinkList &L,int m)
50
51 { while(p->next!=L)
52
53 p=p->next;
54
55 for(int n=size(L); n>0 ; n--)
56
57 {
58
59 cout<<"上限初值为"<<m<<",出列编号为";
60
61 for(int i=1; i<=m%n-1; i++)
62
63 p=p->next;
64
65 cout<<p->next->number<<endl;
66
67 m=p->next->data;
68
69 LinkList q=p->next;
70
71 p->next=q->next;
72
73 free(q);
74
75 }
76
77 }
5．调试分析
链表以结点连接，结点Node存储的信息包括每个人手中的密码、每个人的位置以及下一个结点在计算机中的存储位置，及指向下一个结点的指针。一个玩家被移除之后，链表后的元素位置会“前进”，而我们需要的玩家的位置始终是不变的。
6．使用说明
根据提示分别输入报数上限m，键入回车，人数n键入回车，后按照提示分别输入n个人的密码依次键入回车；最后系统给出每一次的上限初值和对应的出列编号。
7．测试结果
8．附代码
1 // 实验一.cpp : 定义控制台应用程序的入口点。
2 //
3
4 #include "stdafx.h"
5
6
7 #include<iostream>
8 using namespace std;
9 #define TRUE 1
10 #define FALSE 0
11 #define OK 1
12 typedef int Status;
13 typedef double ElemType;
14 //定义单向循环链表
15 typedef struct LNode
16 {
17 int number;
18 int data;
19 struct LNode *next;
20 }LNode, *LinkList;
21
22 LinkList EvaluList(int n);//对单向循环链表进行尾插入赋值
23 int size(LinkList L);//求链表的节点个数
24 Status ScanList(LinkList L);//遍历单向循环链表
25 Status Joseph(LinkList &L,int m);//约瑟夫环的实现
26
27 void main()
28 {
29 int m,n;
30 cout<<"请输入正整数报数上限m和人数n（n≤30）"<<endl;
31 cin>>m>>n;
32 cout<<"请输入"<<n<<"个人的密码:"<<endl;
33 LinkList L=EvaluList(n);
34 ScanList(L);
35 cout<<n<<"个人的出列顺序为"<<endl;
36 Joseph(L,m);
37 }
38 //对单向循环链表进行尾插入赋值
39 LinkList EvaluList(int n)
40 {
41 if(n==0)
42 return NULL;
43 int key;
44 cout<<"输入第1个人的密码 ";
45 cin>>key;
46 LinkList L=new LNode;
47 L->data=key;
48 L->number=1;
49 L->next=L;
50 for(int i=2;i<=n;i++)
51 {
52 LinkList p=new LNode;
53 int key;
54 cout<<"输入第"<<i<<"个人的密码 ";
55 cin>>key;
56 p->data=key;
57 p->number=i;
58 p->next=L->next;
59 L->next=p;
60 L=L->next;
61 }
62 cout<<endl;
63 L=L->next;
64 return L;
65 }
66 //求链表的节点个数
67 int size(LinkList L)
68 {
69 if(L==NULL)
70 return 0;
71 int i=1;
72 LinkList p=L->next;
73 while(p!=L)
74 {
75 i++;
76 p=p->next;
77 }
78 return i;
79 }
80 //遍历单向循环链表
81 Status ScanList(LinkList L)
82 {
83 LinkList p=L;
84 if(p==NULL)
85 {
86 cout<<"人数为空"<<endl;
87 return FALSE;
88 }
89 p->data;
90 p=p->next;
91 while(p!=L)
92 {
93 p->data;
94 p=p->next;
95 return TRUE;
96 }
97 }
98 //约瑟夫环的实现
99 Status Joseph(LinkList &L,int m)
100 {
101 if(L==NULL)
102 {
103 cout<<"人数为空，出列结束"<<endl;
104 return FALSE;
105 }
106 LinkList p=L;
107 while(p->next!=L)
108 p=p->next;
109 for(int n=size(L); n>0 ; n--)
110 {
111 cout<<"上限初值为"<<m<<",出列编号为";
112 for(int i=1; i<=m%n-1; i++)
113 p=p->next;
114 cout<<p->next->number<<endl;
115 m=p->next->data;
116 LinkList q=p->next;
117 p->next=q->next;
118 free(q);
119 }
120 system("pause");
121 return OK;
122 }
View Code