队列与处理机调度——数据结构与操作系统详解.ppt

* 课 程：数据结构综合实践 知识点：队列与处理机调度 单 位：计算机科学与技术学院 教 师：陈博 目 录 导入 —— 数据结构的核心地位 数据结构 —— 队列 操作系统 —— 处理机调度 综合实践 —— 算法实现 导入 —— 数据结构的核心地位 《操作系统》是计算机学科最重要的专业核心 课程 。主要介绍操作系统的基本原理和实现技术 ， 是理解计算机系统工作、用户与计算机系统交互和 设计开发应用系统等基本知识结构的重要途径。 操作系统(Operating System，简称OS)是管理 计算机系统的全部硬件资源包括软件资源及数据资 源；控制程序运行；改善人机界面；为其它应用软 件提供支持等，使计算机系统所有资源最大限度地 发挥作用，为用户提供方便的、有效的、友善的服 务界面。 数据结构 —— 队列 队列：限定仅在一端进行插入，而在另一端进行删除操作的线性表。 a1 a2 a3 ………… an 出队列 入队列 队尾 rear 队头 front 允许删除的一端称为队头(front) 允许插入的一端称为队尾(rear) 队列中没有元素时称为空队列 队列的特点： 根据队列的定义可知，最先放入队列的元素最先出队列。 特点 ：先进先出 也就是说，队列是一种后进先出的线性表，简称为FIFO (First In First Out)表。 队列的抽象数据类型： ADT Queue { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n } 约定an 端为队尾，a1 端为队头。 基本操作： InitQueue (Q) //操作结果：构造一个空队列Q 。 DestroyQueue ( Q) //操作结果：队列Q被销毁。 ClearQueue ( Q) //操作结果：将Q清为队列 QueueEmpty (Q) //操作结果：若队列Q为空队列，则返回TRUE，否则FALSE。 QueueLength (Q) //操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, e) //操作结果：用e返回Q的队头元素。 EnQueue (Q, e) //操作结果：插入元素e为新的队尾元素。 DeQueue (Q, e) //操作结果：删除Q的队头元素，并用e返回其值。 }//ADT Stack 显然，仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。 链队列：用链表来存储队列 队头指针 为 Q.front 队尾指针 为 Q.rear a2 an ∧ a1 front rear 头结点 队头结点 队尾结点 Q typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 } LinkQueue; Status InitQueue (LinkQueue Q) Status DestroyQueue (LinkQueue Q) Status EnQueue (LinkQueue Q, QElemType e) Status DeQueue (LinkQueue Q, QElemType e) void InitQueue (LinkQueue Q) front rear 一个空队列： { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode )); if(!Q.front) exit(OVERFLOW); Q.front-next = NULL; } Q 队尾 队头 front rear Status DestroyQueue (LinkQueue Q) { while (Q.front) { Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; }//从前到后，逐个摘下结点并释放结点所用的内存空间 return OK; } 队尾 队头 front rear Q p