实验2 堆与队列.doc

《实验2 堆与队列.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验2堆栈与队列实验目的1． 会定义顺序栈和链栈的结点类型。2． 掌握栈的插入和删除结点在操作上的特点。3． 熟悉对栈的一些基本操作和具体的函数定义。4．会定义顺序队列和链队列的结点类型。实验内容程序1该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。/*定义DataType为int类型*/typedefintDataType; /*栈的结点类型*/#defineMAXSIZE1024typedefstruct{DataTypedata[MAXSIZE];inttop;

2、}SeqStack; /*初始化顺序栈*/SeqStackSeqStackInit() /*检查顺序栈是否为空*/intSeqStackEmpty(SeqStackS) /*把S置为空栈*/voidClearStack(SeqStack*S) /*把元素x压入栈，使其成为新的栈顶元素*/voidSeqStackPush(SeqStack*S,DataTypex) /*把栈顶元素弹出*/DataTypeSeqStackPop(SeqStack*S) /*取栈顶元素*/DataTypeSeqStackGetTop(SeqStack

3、S) /*输出顺序栈中的元素*/voidSeqStackPrint(SeqStackS)程序2：试利用堆栈将队列中的元素逆置。程序3：编写括号匹配算法。1.队列的抽象数据类型定义：ADTQueue{数据对象：D={

4、∈ElemSet,i=1,2,...,n,n>=0}数据关系：R1={<,>

5、,∈D,i=2,...,n}基本操作：InitQueue(&Q)构造一个空队列QQueueEmpty(Q)判断队列是否为空QueueLenght(Q)返回队列Q的元素个数，即队列的长度GetHead(Q,&e)取队列Q的队头元素，并用e返

6、回EnQueue(&Q,e)将元素e入队列DeQueue(&Q,&e)删除非空队列Q的队头元素，并用e返回其值}ADTQueue1.队列的表示：队列有两种表示方法：链队列、循环队列（顺序队列）。（1）链队列的表示：typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;(2)循环队列的表示1.操作系统作业调度模拟。【简要分析】假设有几个作业运行。如

7、果都需要请求CPU，则可以让作业按先后顺序排队，每当CPU处是完一个作业后，就可以接受新的作业，这时队列中队头的作业先退出进行处理。后来的作业排在队尾。此题算法跟模拟服务台前的排队现象问题相似，假定只有一个CPU，但为了防止一个作业占用CPU太久，可规定每个作业一次最长占用CPU的时间（称时间片），如果时间片到，作业未完成，则此作业重新进入等待队列，等到下次占有CPU时继续处理。