数据结构实验二求解约瑟夫问题.doc

数据结构实验二 求解约瑟夫问题问题描述：使用代表头节点的循环单链表解决此问题。设有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; inext;if ( cp = = HL ) ap = HL; cp = HL-next ; /依次使n-1个人出列for ( i=1; in; i+ ) /顺序查找出待出列的人，即为循环结束后cp所指向的节点 for ( int j=1; jnext ;if ( cp =HL) ap = HL; cp = HL-next ; /输出cp节点的值，即出列的人 cout data next = cp - next ; delete cp;/使cp指向被删除节点的后续节点 cp = ap - next ;/若cp指向了表头节点，则后移ap和cp指针 if ( cp = = HL ) ap = HL ; cp = HL- next ; /使最后一人出列 count next - data 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 CA B CA B C P1 8 6 41 2 12 1 1 P2 4 3 33 1 1 P3 10 1 34 1 3 P4 3 3 33 2 2 P5 5 4 61 1 3(1) 系统是否处于安全状态？如是，则给出进程安全序列.(2) 如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？3、 在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示. 作业号 进入时刻 估计运行时间 优先级 JOB1 8：00 90分钟 5 JOB2 8：10 30分钟 6 JOB3 8：30 20分钟 3 JOB4 8：50 15分钟 8 JOB5 9：20 10分钟 2 JOB6 9：40 5分钟 4系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以