数据结构课件概要.ppt

* * * * * * * * * * * * * * 在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片，一次只移动一片，不管在哪根针上，小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 队列的示意图 是一种先进先出的线性表（First In First Out, 也称作FIFO表)，只允许在表的一端（队尾）进行插入，另一端（队头）进行删除。 q=(k0 k1 k2 … kn-1) k0 k1 k2 … kn-1 入队列 出队列 队头 队尾 队头 队尾 * 队列的基本运算 创建一个空队列或将队列置成空队列； 判断队列是否为空队列； 往队列中插入一个元素； 从队列中删除一个元素； 求队列头部元素的值。 * 内容提要 栈及其基本运算 栈的实现 栈的应用 队列及其基本运算 队列的实现 队列的应用 * 队列的实现 顺序表示 队列的顺序表示 顺序队列中基本运算的实现 链接表示 队列的链接表示 链接队列中基本运算的实现 * 队列的顺序表示 用顺序的形式表示队列时，要分配一块连续的存储区域来存放队列里的元素，并用两个变量分别指示当前队列的头和尾元素的位置。 约定：队头变量f指出实际队头元素所在的位置，而队尾变量r指出实际队尾元素所在位置的下一个位置 顺序表示的队列可说明为： #define MAXNUM 100 /*队列中最大元素个数*/ struct SeqQueue /*顺序队列类型定义*/ { int MAXNUM; int f,r; DataType *q; }; typedef struct SeqQueue *PSeqQueue; *顺序队列类型的指针类型*/ struct SeqQueue { DataType q[MAXNUM]; int f,r; }; * 队列顺序表示的特征 PSeqQueue paqu; 头变量paqu-f存放即将要被删除的元素的下标。 尾变量paqu-r存放即将要被插入的元素的下标 paqu-q[paqu-f]表示当前队列头部的元素 paqu-q[paqu-r]表示当前队列尾部的即将插入的元素 初始时：paqu-f=paqu-r=0 当前队列中元素的个数可以用paqu-r-paqu-f计算得到 当paqu-r=paqu-f时，元素个数为0，即为空队列 * 顺序表示中基本运算的实现 PSeqQueue creatEmptyQueue_seq(void); 创建一个空队列，返回指向空队列的指针 int isEmptyQueue_seq(PSeqQueue paqu); 判断papu所指的队列是否为空队列，当papu所指的队列为空队列时，则返回1，否则返回0 void enQueue_seq(PSeqQueue papu，DataType x); 进队列运算，表示往papu所指的队列中插入一个值为x的元素 void deQueue_seq(PSeqQueue papu); 出队列运算，表示从papu所指的队列中删除一个元素 DataType frontQueue_seq(PSeqQueue papu) 当papu所指的队列不空时，求队列头部元素的值，队列保持不变 * 一个队列的变化过程 r f MaxNUM-1 … 4 3 2 1 0 空队列 a r f a进队 b a r f b进队 b f r a出队 c b r f c进队 c r f b出队 r f c出队 空队列 顺序队列的操作 * 普通顺序队列的缺陷 队列溢出： 当队列满时，再做进队列操作，这种现象称为上溢。 当队列空时，再做删除操作，这种现象称为下溢。 插入 paqu-q[paqu-r]=x paqu-r=paqu-r+1 删除 papu-f= papu-f+1 当paqu-r=MAXNUM时， 再做插入就会产生溢出，而实际上这时队列的前端还有许多空的可用的位置，这种现象称为假溢出。 f r f r * 环形队列 解决方法： 把数组paqu-q[MAXNUM]从逻