《特殊线性表》由会员分享，可在线阅读，更多相关《特殊线性表（137页珍藏版）》请在金锄头文库上搜索。
1、数据结构（ C版） 清华大学出版社 第 3章 特殊线性表 栈、队列和串 本章的基本内容是： 三种特殊的线性表 栈、队列、串 从数据结构角度看，栈和队列是 操作受限 的线性表，他们的逻辑结构相同。 串是重要的非数值处理对象，它是以 字符 作为数据元素的线性表。 数据结构（ C版） 清华大学出版社 特殊线性表 栈 栈的逻辑结构 空栈： 不含任何数据元素的栈。 （ a1, a2, , an） 栈： 限定仅在 表尾 进行插入和删除操作的 线性表 。 栈顶 栈底 允许插入和删除的一端称为栈顶，另一端称为栈底。 数据结构（ C版） 清华大学出版社 a1 a2 a3 入栈 出栈 栈底 栈顶 特殊线性表 栈
2、插入：入栈、进栈、压栈 删除：出栈、弹栈 栈顶 栈顶 栈的示意图 数据结构（ C版） 清华大学出版社 栈的操作特性： 后进先出 a1 a2 a3 入栈 出栈 栈底 栈顶 特殊线性表 栈 插入：入栈、进栈、压栈 删除：出栈、弹栈 栈顶 栈的示意图 数据结构（ C版） 清华大学出版社 例：有三个元素按 a、 b、 c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 特殊线性表 栈 栈底 栈顶 ab 栈顶 c 栈顶 情况 1： 栈的逻辑结构 数据结构（ C版） 清华大学出版社 特殊线性表 栈 栈底 栈顶 ab 栈顶 c 栈顶 出栈序列： c 出栈序列： c、 b 出栈序列： c、
3、 b、 a 例：有三个元素按 a、 b、 c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 栈的逻辑结构 情况 1： 数据结构（ C版） 清华大学出版社 特殊线性表 栈 栈底 栈顶 ab 栈顶 出栈序列： b 情况 2： 例：有三个元素按 a、 b、 c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 栈的逻辑结构 数据结构（ C版） 清华大学出版社 特殊线性表 栈 栈底 a 出栈序列： b 出栈序列： b、 c 出栈序列： b、 c、 a c 栈顶 栈顶 注意： 栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。 例：有三
4、个元素按 a、 b、 c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 栈的逻辑结构 情况 2： 数据结构（ C版） 清华大学出版社 栈的抽象数据类型定义 特殊线性表 栈 ADT Stack Data 栈中元素具有相同类型及后进先出特性， 相邻元素具有前驱和后继关系 Operation InitStack 前置条件：栈不存在 输入：无 功能：栈的初始化 输出：无 后置条件：构造一个空栈 数据结构（ C版） 清华大学出版社 DestroyStack 前置条件：栈已存在 输入：无 功能：销毁栈 输出：无 后置条件：释放栈所占用的存储空间 Push 前置条件：栈已存在 输入：元
5、素值 x 功能：在栈顶插入一个元素 x 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素 栈的抽象数据类型定义 特殊线性表 栈 数据结构（ C版） 清华大学出版社 Pop 前置条件：栈已存在 输入：无 功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素 GetTop 前置条件：栈已存在 输入：无 功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变 栈的抽象数据类型定义 特殊线性表 栈 数据结构（ C版） 清华大学出版社 Empty 前置条件：栈已存在 输入：无 功能：判断栈是否
6、为空 输出：如果栈为空，返回 1，否则，返回 0 后置条件：栈不变 endADT 栈的抽象数据类型定义 特殊线性表 栈 数据结构（ C版） 清华大学出版社 栈的顺序存储结构及实现 顺序栈 栈的顺序存储结构 如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6 7 8 a1 确定用数组的哪一端表示栈底。 特殊线性表 栈 附设指针 top指示栈顶元素在数组中的位置。 top 数据结构（ C版） 清华大学出版社 出栈： top减 1 进栈： top加 1 栈空： top= -1 0 1 2 3 4 5 6 7 8 特殊线性表 栈 a1 top a2 top a3 top 栈满： top= MA
7、X_SIZE 栈的顺序存储结构及实现 数据结构（ C版） 清华大学出版社 顺序栈类的声明 const int MAX_SIZE=100; template class seqStack public: seqStack ( ) ; seqStack ( ); void Push ( T x ); T Pop ( ); T GetTop ( ); bool Empty ( ); private: T dataMAX_SIZE; int top; 特殊线性表 栈 数据结构（ C版） 清华大学出版社 顺序栈的实现 入栈 template void seqStack:Push ( T x) if (t
8、op=MAX_SIZE-1) throw “溢出 ” ; top+; datatop=x; 特殊线性表 栈 操作接口： void Push( T x ); 时间复杂度？ 数据结构（ C版） 清华大学出版社 顺序栈的实现 出栈 template T seqStack: Pop ( ) if (top=-1) throw “溢出 ” ; x=datatop-; return x; 特殊线性表 栈 操作接口： T Pop( ); 时间复杂度？ 数据结构（ C版） 清华大学出版社 两栈共享空间 解决方案 1： 直接解决：为每个栈开辟一个数组空间。 解决方案 2： 顺序栈单向延伸 使用一个数组来存储两个
9、栈 特殊线性表 栈 在一个程序中需要 同时 使用具有 相同 数据类型的两个栈 ， 如何顺序存储这两个栈？ 会出现什么问题？如何解决？ 数据结构（ C版） 清华大学出版社 两栈共享空间： 使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。 特殊线性表 栈 两栈共享空间 数据结构（ C版） 清华大学出版社 栈 1的底固定在下标为 0的一端； 栈 2的底固定在下标为 StackSize-1的一端。 top1和 top2分别为栈 1和栈 2的栈顶指针； Stack_Size为整个数组空间的大小（图中用 S表示）； a1 a2 ai to
10、p1 0 1 2 S-1 两栈共享空间 两栈共享空间 top2 bj b2 b1 栈 1底 栈 2底 数据结构（ C版） 清华大学出版社 两栈共享空间 top1= -1 什么时候栈 1为空？ a1 a2 ai top1 0 1 2 S-1 两栈共享空间 top2 bj b2 b1 top1 数据结构（ C版） 清华大学出版社 两栈共享空间 top1= -1 什么时候栈 1为空？ a1 a2 ai top1 0 1 2 S-1 两栈共享空间 top2 bj b2 b1 什么时候栈 2为空？ top2 top2= Stack_Size 数据结构（ C版） 清华大学出版社 两栈共享空间 top1=
11、-1 什么时候栈 1为空？ a1 a2 ai top1 0 1 2 S-1 两栈共享空间 top2 bj b2 b1 什么时候栈 2为空？ top2= Stack_Size 什么时候栈满？ top2= top1+1 数据结构（ C版） 清华大学出版社 const int Stack_Size=100; template class BothStack public: BothStack( ); BothStack( ); void Push(int i, T x); T Pop(int i); T GetTop(int i); bool Empty(int i); private: T dat
12、aStack_Size; int top1, top2; ; 两栈共享空间类的声明 两栈共享空间 数据结构（ C版） 清华大学出版社 1. 如果栈满 ， 则抛出上溢异常； 2. 判断是插在栈 1还是栈 2； 2.1 若在栈 1插入 ， 则 2.1.1 top1加 1; 2.1.2 在 top1处填入 x； 2.2 若在栈 2插入 ， 则 2.2.1 top2减 1; 2.2.2 在 top2处填入 x； 两栈共享空间 两栈共享空间的实现 插入 操作接口： void Push(int i, T x) ; 数据结构（ C版） 清华大学出版社 1. 若是在栈 1删除 ， 则 1.1 若栈 1为空栈 ， 抛出下溢异常； 1.2 删除并返回栈 1的栈顶元素； 2. 若是在栈 2删除 ， 则 2.1 若栈 2为空栈 ， 抛出下溢异常； 2.2 删除并返回栈 2的栈顶元素； 两栈共享空间 两栈共享空间的实现 删除 操作接口： T Pop(int i) ; 数据结构（ C版） 清华大学出版社 栈的链接存储结构及实现 链栈： 栈的链接存储结构 特殊线性表 栈 first a1 a2 an ai 链栈需要加头结点吗？ 如何改造链表实现栈的链接存储？ 将哪一端作为栈顶？ 将链头作为栈顶，方便操作。 链栈不需要附设头结点
