第五章 队列及其应用.pptVIP

01/06/2002 数据结构讲义 第五章 队列及其应用 队列的基本概念 顺序队列及其基本算法 循环队列基本算法 队列应用--迷宫最短路径 * 队列的基本概念 顺序队列及其基本算法 链队列及其基本算法 队列应用 队列的定义。队列是一种运算受限制的线性表，又叫先进先出表。队列是满足以下条件的顺序表：插入只能在表尾进行，删除只能在表头进行。把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。 队列的逻辑结构。为线性逻辑结构。 队列的基本算法：置空队：将队列置成空队列；判队空：判断队列是否为空队列；判队满：判断队列是否满；入队：在队列尾插入数据元素；出队：从队列中删除队头元素。 队列的存储结构。有两种存储方式： 顺序存储。用地址连续的空间依次存储队列中的元素，同时记录队头及队尾位置。这种存储结构的队列称为顺序队列。 链式存储。采用链式存储结构的队列称为链队列。 顺序队列的数据类型 define maxlen 100 typedef struct { datatype data[maxlen]; int front,rear; }SeqQueue; a b c d e front rear 假溢出现象：由于出队后元素位置被空出，而入队无法使用这些空出的位置。此时造成的队满为假溢出现象。 顺序循环队列：为解决假溢出现象，规定：队头指针总是指向队头元素的前一个位置， data[maxlen-1]的后继单元为data[0]。这种队列称为顺序循环队列。 a b c d e f g h front rear 假溢出 i a b c d e f g h front rear 循环队列 为便于队列操作，一般让front指向的空间永远为空。 队列置空： Q-front=0;Q-rear=0; 出队： Q-front=(Q-front+1)%maxlen 判队满： Q-front=(Q-rear+1)%maxlen 判队空： Q-front=Q-rear 入队： Q-rear=(Q-rear+1)%maxlen Q-data[Q-rear]=x front rear front rear a b c d e f g front rear a b c d e rear front rear b c d front 链队列及其基本算法 结点类型定义： typedef struct node { datatype data; struct node *next; }LinkList; 链队列定义： typedef struct { LinkList *front,*rear; }LinkQueue; /*将头尾指针封装在一起的链队*/ LinkQueue *Q; a b c ^ front rear 建立链队： LinkQueue *SetQueue(){ LinkQueue *Q;Q=malloc(sizeof(LinkQueue)); Q-front=malloc(sizeof(LinkQueue)); Q-rear=Q-front;} 判队空：Q-front=Q-rear 入队：学生完成 出队：学生完成 置空：学生完成 队列应用--基数排序 多关键字排序 高位优先法：先按主关键字得到子序列，再对子序列按次关键字排序，最后按主关键字收集子序列完成排序。 低位优先法：先按次关键字得到子序列，最后按主关键字收集完成排序。 链式基数排序 基本思想：在链式存储结构下通过低位优先法进行排序。 示例：对序列278,109,63,930,589,184,505,269,8,83递增排序。 先按个位分类 个位为：0 1 2 3 4 5 6 7 8 9 930 063 083 184 505 278 008 109 589 269 再按十位分类 十位为：0 1 2 3 4 5 6 7 8 9 930 063 083 184 505 278 008 109 589 269 最后按百位分类后，依次收集即完成排序（由学生完成）。 队列应用--基数排序练习 部分学生成绩表按下表所示。请按数学成绩降升序排序。数学成绩相同者按语文成绩降序排序；语文成绩再相同者，按英语成绩降序排序。要求使用基数排序法。 82 76 85 胡胜 81 80 85 龚鹏 78 86 92 陈大为 85 92 87 李汉 90 87 95 张化生 75 87 90 洪媚 80 87 95 李为 80 90 87 刘心怡 70 85 90 张其 英语 语文 数学