数据结构-C语言描述(本科)第3章

第3章 堆 栈 和 队 列
第3章 堆 栈 和 队 列 队列运算需要两个指针，Front指向队头元素，Rear指向队 尾元素。MaxQueue为队列的最大允许长度，它应不大于整型常 量 MaxSize 。一维数组 Elments 用以存放队列中的元素，实现队 列的顺序存储。 初始状态下，我们将Front和Rear两个指针均置成－1，代表 空队列，见图3－6（a）。图中，f和r分别代表Front和Rear。
第3章 堆 栈 和 队 列
ADT 3－2 Queue{ 数据： 零个或多个元素的线性序列（a0,a1,...,an－1)，其最大允许长度为ＭaxQueue。 运算： void CreateQueue(Queue * q,int maxsize); 后置条件:已构造一个空队列。 BOOL IsEmpty（Queue q） 后置条件: 若队列为空，则返回TRUE，否则返回FALSE。
第3章 堆 栈 和 队 列
3.2 队
3.2.1 队列ADT源自列队列是限定只能在表的一端插入元素，在表的另一端删除 元素的线性数据结构。允许插入元素的一端称队尾（rear），允 许删除元素的另一端称队头（ front ）。若队列中无元素，则称 为空队列。若给定队列 Q=(a0,a1,…,an － 1) ，则称 a0 是队头元素， an－1是队尾元素。若元素a0,…,an－1依次入队列，则元素出队列的 次序与入队列一致，a0出队列后，a1才能出队列，见图3-4。由于 队列的这种先进先出的特点，因此队列是先进先出（ First In First Out－FIFO）的线性数据结构。
第3章 堆 栈 和 队 列 进栈操作是：首先令栈顶指针进一（++s->Top），然后将 新元素x存放在新的栈顶位置（s->Elements[++s->Top]=x）。出 栈操作只是简单地令栈顶指针退一（s->Top--;）。所有这些运 算均包含参数s。对于那些会改变堆栈内容的运算，参数s为指 针类型Stack*，否则为Stack类型。主程序main用于测试已实现 的栈运算，起着驱动程序的作用。请注意主程序应严格按照每 个函数的参数类型调用它们。对于Stack*类型的参数，其对应 的实参前必须加上取地址运算符&。主程序中使用的PrintStack （Stack s）函数，输出栈中元素值，我们将其留作练习，请自 行实现之。PrintElement(x)函数的功能见2.3.2节。
第3章 堆 栈 和 队 列 程序3－1 顺序栈实现 void CreateStack(Stack *s,int maxsize) { s->Top=-1; s->MaxStack=maxsize; } BOOL IsEmpty(Stack s) { return s.Top<0; } BOOL IsFull(Stack s) { return s.Top>=s.MaxStack-1; }
第3章 堆 栈 和 队 列
我们可以使用测试顺序栈完全相同的主程序作为测试链式 栈的驱动程序。只要链式栈实现的各栈运算的接口（即函数原 型）与ADT 3－1 Stack中定义的完全相同，则主程序中调用栈 函数的语句可以不加任何改动。这就是所谓的使用与实现分离。 实现的改变应不影响客户程序。这正是抽象数据类型的宗旨。
第3章 堆 栈 和 队 列
ADT 3－1 Stack { 数据： 零个或多个元素的线性序列（a0,a1,...,an－1)，其最大允许长度为ＭaxStack。 运算： void CreateStack(Stack * s，int maxsize ); 后置条件:已构造一个空堆栈。 BOOL IsEmpty（Stack s） 后置条件: 若堆栈为空，则返回TRUE，否则返回FALSE。 BOOL IsFull（Stack s）
第3章 堆 栈 和 队 列
x=*InputElement(); Push(&s,x); /*调用InputElement函数接受新元素x，并 令其进栈*/ PrintStack(s); Pop(&s); Pop(&s); if(IsEmpty(s)) printf("Is empty."); else printf("Is not empty."); PrintStack(s); } /*显示栈中元素*/ /*显示栈中元素*/ /*在栈中依次弹出两个元素*/ /* 判断此时栈是否为空栈*/
第3章 堆 栈 和 队 列
第3章 堆 栈 和 队 列 栈的基本运算包括构造一个空堆栈，判定一个栈是否为空 栈，判定一个栈是否已满，在一个未满的栈中插入一个新元 素，从一个非空的栈中删除栈顶元素等。当然我们还可以根据 应用需要增加其它必要的栈运算，如求栈的长度，清除一个 栈，以及遍历一个栈等。堆栈的抽象数据类型定义见ADT 3-1。 函数CreateStack是抽象数据类型的构造函数，有时可以根据需 要定义多个构造函数。
第3章 堆 栈 和 队 列 3.2.2 队列的顺序表示 与堆栈一样，队列可以采用顺序存储，也可以采用链接存 储。当我们用一维数组存储队列时，被称为顺序队列 （sequential queue），图3－5是队列的顺序表示示意图。队列 的链接表示在下一小节讨论。 队列的顺序实现可以用下面的C语言结构定义： typedef struct queue{ int Front，Rear,MaxQueue; T Elements[MaxSize]; } Queue
第3章 堆 栈 和 队 列 在 上 面 定 义 的 结 构 类 型 Stack 中 ， Top 是 栈 顶 指 针 ， MaxStack为栈的最大允许长度，它应不大于整型常量MaxSize。 一维数组 Elements 用以存放队列中的元素，实现堆栈的顺序存 储。标识符BOOL被定义为整型。 程序3－1是ADT 3－1中规定的栈运算在顺序表示下的实现。 当堆栈为空时，令栈顶指针Top＝－1。栈的容量MaxStack由用 户通过参数maxsize设定，但不能超过MaxSize。
第3章 堆 栈 和 队 列 void Push(Stack* s, T x) { if ( IsFull(*s)) printf("Overflow"); else s->Elements[++s->Top]=x; } void Pop(Stack* s) { if (IsEmpty(*s))printf("Underflow"); else s->Top--; } void StackTop(Stack s,T* x) {
第3章 堆 栈 和 队 列
if (IsEmpty(s)) printf("Underflow"); else *x=s.Elements[s.Top]; } void main(void) { Stack s; T x; CreateStack(&s,10); Push(&s,10); Push(&s,15); PrintStack(s); /* 构造一个容量为10的空整数栈*/ /*在栈中依次压入元素10和15*/ /*显示栈中元素*/
第3章 堆 栈 和 队 列 程序3－2 链式栈的进栈和出栈运算 void Push(Stack *s, T x) { Node* p=NewNode2(x); p->Link=s->Top; s->Top=p; } void Pop(Stack *s) { Node *p=s->Top; s->Top=p->Link; free(p); }
第3章 堆 栈 和 队 列
第3章 堆 栈 和 队 列
3.1 堆栈 3.2 队列 3.3* 表达式的计算 3.4* 递归和递归过程 3.5* 演示和测试 习题3
第3章 堆 栈 和 队 列
3.1 堆 栈
3.1.1堆栈ADT 堆栈(或栈）是限定插入和删除运算只能在同一端进 行的线性数据结构。允许插入和删除元素的一端称为栈顶 （ top ），另一端称为 栈底 （ bottom）。若栈中无元素，则为空 栈。若给定堆栈S=(a0,a1,…,an－1)，则称a0是栈底元素，an－1是栈 顶元素。若元素 a0,…,an － 1 依次进栈时，则出栈的顺序与进栈相 反，即元素an－1必定最先出栈，然后an-2才能出栈（见图3-1）。 由于栈的这种后进先出的特点，因此栈是后进先出（Last In First Out－LIFO）的线性数据结构。
第3章 堆 栈 和 队 列
BOOL IsFull（Queue q） 后置条件: 若队列已满，则返回TRUE，否则返回FALSE。 void Append（Queue *q, T x） 后置条件：若队列已满，则指示Overflow，否则值为x的新元素进队列。 void Serve（Queue *q） 后置条件：若队列为空，则指示Underflow，否则从队列中删除队头元素。 void QueueFront（Queue q,T* x） 后置条件：若队列为空，则指示Underflow，否则在参数x中返回队头元素值。 }
第3章 堆 栈 和 队 列
第3章 堆 栈 和 队 列 队列的基本运算包括构造一个空队列，判定一个队列是 否为空队列，判定一个队列是否已满，在一个未满的队列中 插入一个新元素，从一个非空的队列中删除队头元素等。当 然我们还可以根据应用需要增加其它必要的队列运算，如求 队列的长度，清除一个队列，以及遍历一个队列等。队列的 抽象数据类型定义见ADT 3－2。
第3章 堆 栈 和 队 列 3.1.3 堆栈的链接表示 堆栈也可用单链表实现之，堆栈在链接存储方式下的实现 称为链式栈(linked stack)，如图3－3所示。由于堆栈具有后进先 出特性，所以，栈顶指针 Top 指示的结点是 an-1 ，它是栈顶元 素，堆栈的栈底元素是单链表的尾结点。其结点类型与单链表 相同，
第3章 堆 栈 和 队 列