数据结构实验二 求解约瑟夫问题_数据结构实验二学习
数据结构实验二 求解约瑟夫问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验二学习”。
数据结构实验二
求解约瑟夫问题
问题描述：使用代表头节点的循环单链表解决此问题。设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人离开。接着从出列的下一个人开始重新从1开始报数，数到m的人又出列，如此下去直到所有的人都出列为止。求出他们的出列序列。
问题分析：例如，当n=8,m=4时，若从第一个人开始报数（设从1开始编号），则得到的序列是：4，8，5，2，1，3，7，6。算法：
void Josephus(int n, int m,int s)
{ //生成表头节点，空单循环链表
LNode * HL = new LNode;
HL-> next = HL;
int i;//生成含有 n 个节点的、节点值依次为1，2……，n的带表头节点的循环单链表
For(i = n;i>=1;i--)
{ LNode * newptr = new LNode;
Newptr-> data = i;
newptr-> next = HL-> next;
HL-> next = newptr;}
//从表头开始顺序查找出第s个节点，对应第一个开始报数的人 LNode * ap = HL, *cp = HL->next;for(i= 1;i
ap = cp;
cp = cp->next;if(cp = = HL){ ap = HL;cp = HL->next;} } //依次使n-1个人出列 for(i=1;i
//顺序查找出待出列的人，即为循环结束后cp所指向的节点
for(int j=1;jnext;if(cp ==HL){ ap = HL;cp = HL->next;} } //输出cp节点的值，即出列的人
cout data
“;//从单链表中删除cp节点
ap-> next = cp-> next;delete cp;//使cp指向被删除节点的后续节点
cp = ap-> next;//若cp指向了表头节点，则后移ap和cp指针 if(cp = = HL){ ap = HL;cp = HL-> next;} }
//使最后一人出列
count next-> data
//删除表头节点和表头附加节点
delete HL->next;
delete HL;}
补充操作系统练习：
1、有一个虚拟存储系统, 每个进程在内存占有3页数据区、1页程序区.刚开始时数据区为空.有以下访页序列:1、5、4、1、2、3、2、1、5、4、2、4、6、5、1
试给出下列情形下的缺页次数:
(1)系统采用先进先出(FIFO)淘汰算法.(2)系统采用最近最少使用(LRU)淘汰算法.(3)若采用优化(OPT)淘汰算法呢?
2、设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：
最大需求量
已分配资源量
剩余资源量
A
B
C
A
B
C
A
B
C
P1 8
P2 4
P3 10 1
P4 3
P5 5(1)系统是否处于安全状态？如是，则给出进程安全序列.(2)如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？
3、在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示.作业号
进入时刻
估计运行时间
优先级
JOB1
8：00
90分钟
JOB2
8：10
30分钟
JOB3
8：30
20分钟
JOB4
8：50
15分钟
JOB5
9：20
10分钟
JOB6
9：40
5分钟系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以按照优先级进行进程调度.（1）试给出各个作业的运行时间序列.（例如：JOB1：8：00-8：30，9：10-9：20，…）
（2）试计算出作业的平均周转时间.
