第3章数据结构及运算要点解析.ppt

算法的C语言描述： 输入：线性表的存储空间V(1：m)；线性表的长度n(n≤m)；删除的位置i(表示删除第i个元素)。 输出：删除后的线性表存储空间V(1:m)及线性表的长度n。 二、栈及其运算 1. 栈的特性： 栈具有记忆作用； 栈是按照“先进后出” (FILO—First In Last Out)或“后进 先出” (LIFO—Last In First Out)的原则组织数据的，因此栈也 被称为“先进后出”表或“后进先出”表。 2. 栈的顺序存储及其运算 在程序设计语言中，用一维数组S(1：m)作为栈的顺序存 储空间，其中m为栈的最大容量。通常，栈底指针指向栈空 间的低地址一端(即数组的起始地址这一端)。 在栈的顺序存储空间S(1：m)中，S(bottom)通常为栈底 元素(在栈非空的情况下)，S(top)为栈顶元素。top = 0表示栈 空；top = m表示栈满。 栈的基本运算 初始化IniStack(S)：其作用是建立一个空栈，准备存放数据。 进栈Push(S，x)：其作用是将数据元素x插入栈S，使x成为S的 栈顶元素。 出栈Pop(S)：其作用是当栈不空时返回栈顶元素为该函数的 值，然后删去栈顶元素。 读栈顶Get Top(S)：其作用是当栈不空时返回栈顶元素为该 函数的值，但是栈顶保持不变。 初始化运算 栈的初始化是用于建立一个空栈的顺序存储空间。 栈的初始化的C语言描述为： 入栈运算 入栈运算有两个基本操作：首先，将栈顶指针进一(即 top加1)，然后，将新元素插入到栈顶指针指向的位置。 在容量为m的栈S中插入一个元素x(入栈运算)。 算法中的异常情况处理： 当栈顶指针已经指向存储空间 的最后一个位置时，说明栈空 间己满，不可能再进行入栈操 作。这种情况称为栈上溢“ 错误。 退栈运算 退栈运算有两个基本操作：首先，将栈顶元素(栈顶 指针指向的元素)赋给一个指定的变量，然后，将栈顶的指 针退一(即top-1)。 在容量为m的栈S中删除栈顶元素(退栈运算)。 算法中的异常情况处理： 当栈顶指针为0时，说明 栈空，不可能进行退栈 操作。这种情况称为栈 下溢错误。 3. 栈的应用——表达式的计算 在计算机软件设计中，栈的应用很广泛。栈除了用于 子程序嵌套调用外，还用于实现递归调用过程、表达式的处 理和中断的处理等。栈的所有应用本质上是利用了栈的记忆 作用。 利用栈来处理表达式的计算问题时，为简单起见，主要 以算术表达式为例，并且假设在表达式中只有加、减、乘、 除四个四则运算符，所有的运算对象均为单变量，在表达式 的最后有一个结束符“;。 计算机系统在具体处理表达式前，首先设置以下两个栈： 一是运算符栈，用于在表达式处理过程中存放运算符。在 开始时，运算符栈中先压入一个表达式结束符“;”。 二是操作数栈，用于在表达式处理过程中存放操作数。 表达式计算过程： 从左到右依次读出表达式中的各个符号： 若是操作数，则压入操作数栈，依次读下一个符号。 若是运算符，则作进一步判断： 若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。 若读出的是表达式结束符“;”，且运算符栈栈顶的运算符也是表达式结束符“;”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。 若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算(运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数)，并将运算结果压入操作数栈。在这种情况下，当前读出的运算符下次将重新考虑(即不再读下一个符号)。 表达式计算应用实例 计算表达式“A+B*C-D/E”的值。 三、队列及其运算 1. 队列 队列是另一种特殊的线性表。是限定只能在队尾插入、 只能在队列的头删除的线性表。 队列(Queue)是只能在一端进行插入，而在另一端删除线 性表。能进行插入的一端称为队列的尾，能进行删除的一端 称为队列的头。 先进入队列中的元素称为队列的头元素(队列的头)，用排 头指针(front)指向队列的头元素的前一个位置；最后进入队 列中的元素称为队列的尾元素(队列的尾)，用尾指针(rear)指 向队尾元素。队列称为先进先出表(First In First Out)，简称 FIFO。 往队列的队尾插