数据结构第3章

⑺ 栈和队列的主要区别在于（ ）。 A 它们的逻辑结构不一样 B 它们的存储结构不一样 C 所包含的运算不一样 D 插入、删除运算的限定不一样 【解答】D
⑻ 设数组 S[n]作为两个栈 S1 和 S2 的存储空间，对任何一个栈只有当 S[n]全满时才不能进行进栈操作。为这两个栈 分配空间的最佳方案是（ ）。 A S1 的栈底位置为 0，S2 的栈底位置为 n-1 B S1 的栈底位置为 0，S2 的栈底位置为 n/2 C S1 的栈底位置为 0，S2 的栈底位置为 n D S1 的栈底位置为 0，S2 的栈底位置为 1 【解答】A ⑼ 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作（ ）。 A 连接 B 模式匹配 C 求子串 D 求串长 【解答】B
⑷ 设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳 A 顺序表 B 栈 C 队列 D 链表 【解答】B
⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构。 A 栈 B 队列 C 数组 D 线性表 【解答】B
⑹ 一个队列的入队顺序是 1，2，3，4，则队列的输出顺序是（ ）。 A 4321 B 1234 C 1432 D 3241 【解答】B
5. 举例说明顺序队列的“假溢出”现象。 【解答】假设有一个顺序队列，如图 3-6 所示，队尾指针 rear=4，队头指针 front=1，如果再有元素入队，就会产生“上 溢”，此时的“上溢”又称为“假溢出”，因为队列并不是真的溢出了，存储队列的数组中还有 2 个存储单元空闲，其下标 分别为 0 和 1。
⑷ 对于采用顺序存储结构的串 S，编写一个函数删除其值等于 ch 的所有字符。 【解答】从后向前删除值为 ch 的所有元素，这样所有移动的元素中没有值为 ch 的元素，能减少移动元素的次数，提 高算法的效率。算法如下：

Data Structure
2013-8-6
Page 13
栈的顺序存储（顺序栈）
利用一组地址连续的存储单元依次存放自栈底到栈顶的数 据元素。 结构定义： #define STACK_INIT_SIZE 100; // 存储空间初始分配量 #define STACKINCREMENT 10; // 存储空间分配增量 typedef struct { SElemType *base; // 存储空间基址 SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素位单位 } SqStack;
解决方案2：
顺序栈单向延伸——使用一个数组来存储两个栈
Data Structure 2013-8-6 Page 21
两栈共享空间 两栈共享空间：使用一个数组来存储两个栈，让一个 栈的栈底为该数组的始端，另一个栈的栈底为该数组 的末端，两个栈从各自的端点向中间延伸。
Data Structure
2013-8-6
链栈需要加头结点吗？ 链栈不需要附设头结点。
Data Structure
2013-8-6
Page 27
栈的链接存储结构及实现
Data Structure
2013-8-6
Page 11
GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回S的栈顶元素。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。
Data Structure

0
1
2
3
4
5
6
7
a1
a2
a3
a4
a5
a6
a7
队头 F＝0
队尾 R＝7
a3 2 1 3 0 4 7 a3 5 6 3 a2 2 1 a1 0 F=0 a4 4 a5 5 6 a6 7 a7 R=0 R=7 3 a2 2 1 a1 0
a4 4 a5 5 6 a6 7
a8
F=0
a7
R=0
F=0
删除所有元素
top X W … B top
top=0 空栈
top
W
…
B A
top=m-1 元素X出栈
top
A
A
top=m 满栈
top=1 元素A入栈
例：堆栈的插入、删除操作。 出栈操作程序如下： # define m 1000; /*最大栈空间*/ 出栈操作算法： 1）栈顶指针top是否为0： typedef struct stack_stru 若是，则返回；若不是， { int s[m]; int top; }; 则执行2。 void pop (stack, y) 2）将栈顶元素送给y， struct stack_stru stack; 栈顶指针减1。 int *y; { if (stack.top = = 0) printf (“The stack is empty ! \n”); top Y Y else { top B B *y=stack.s[stack.top]; A A stack.top - -; } 出栈操作 }
top=p;
} 栈的入栈、出栈操作的时间复杂度都为O(1)。
栈的应用
一、 表达式求值 表达式由操作数、运算符和界限符组成。 运算符可包括算术运算符、关系运算符、逻辑运算符。

实用数据结构基础
第3章 栈
第 3 章 栈
知
识点
栈的定义和特点 栈的基本运算和算法 栈的典型应用
难
点
后缀表达式的算法 数制的换算 利用本章的基本知识设计相关的应用问题
要
求
掌握栈的特点 掌握栈的基本运算 熟悉栈的各种实际应用 能设计栈应用的典型算法 了解栈的运算时间复杂度分析
第3章 目录

2．顺序栈运算的基本算法 （1）置空栈 首先建立栈空间，然后初始化栈顶指针。 SeqStack *Snull( ) { SeqStack *s； s=new (SeqStack)；
// 在C语言中用s=malloc（sizeof（SeqStack）） ；
s->top= –1； return s； }
3-1 栈的定义与运算 3-2 栈的存储和实现 3-3 栈的应用举例 小 结 验证性实验3: 栈子系统 自主设计实验3：后缀表达式求值 单元练习3
3-1 栈的定义和运算
3-1-1 栈（Stack）的定义
1. 栈的定义 栈是限制在表尾进行插入和删除的线性表。 进栈 出栈
an …… a3 a2 a1
图3-1栈的 示意图
3-3.
3-3-1 数制转换
栈的应用举例
数值进位制的换算是计算机实现计算和处理的 基本问题。比如将十进制数N转换为j进制的数，其 解决的方法很多，其中一个常用的算法是除j取余法。 将十进制数每次除以j，所得的余数依次入栈，然后 按“后进先出”的次序出栈便得到转换的结果。 其算法原理是： N =（N / j）* j + N % j
由于栈的操作只能在栈顶进行的，所以用链表的头部做
栈顶是最合适的。链栈结构如图3-4所示。