特殊线性表栈队列和串.docx
《特殊线性表栈队列和串.docx》由会员分享，可在线阅读，更多相关《特殊线性表栈队列和串.docx（22页珍藏版）》请在冰点文库上搜索。
特殊线性表栈队列和串
第3章特殊线性表——栈、队列和串
3.1栈
3.1.1栈的逻辑结构
1.栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。
2.栈的抽象数据类型定义
ADTStack
Data
栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系
Operation
栈的抽象数据类型可定义为抽象类：
InitStack
前置条件：
栈不存在
输入：
无
功能：
栈的初始化
输出：
无
后置条件：
构造一个空栈
DestroyStack
前置条件：
栈已存在
输入：
无
功能：
销毁栈
输出：
无
后置条件：
释放栈所占用的存储空间
Push
前置条件：
栈已存在
输入：
元素值x
功能：
在栈顶插入一个元素x
输出：
如果插入不成功，抛出异常
后置条件：
如果插入成功，栈顶增加了一个元素
Pop
前置条件：
栈已存在
输入：
无
功能：
删除栈顶元素
输出：
如果删除成功，返回被删元素值，否则，抛出异常
后置条件：
如果删除成功，栈顶减少了一个元素
GetTop
前置条件：
栈已存在
输入：
无
功能：
读取当前的栈顶元素
输出：
若栈不空，返回当前的栈顶元素值
后置条件：
栈不变
Empty
前置条件：
栈已存在
输入：
无
功能：
判断栈是否为空
输出：
如果栈为空，返回1，否则，返回0
后置条件：
栈不变
endADT
3.1.2栈的顺序存储结构及实现
1.栈的顺序存储结构——顺序栈
栈的顺序存储结构称为顺序栈。
1.顺序栈的实现
constintStackSize=10;//10只是示例性的数据，可以根据实际问题具体定义
template//定义模板类SeqStack
classSeqStack
{
public:
private:
};
3.两栈共享空间
提出问题：
在一个程序中如果需要同时使用具有相同数据类型的两个栈时，如何处理呢？
解决方案一：
为每个栈开辟一个数组空间；
解决方案二：
使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸，如图3-3所示。
其中，top1和top2分别为栈1和栈2的栈顶指针，StackSize为整个数组空间的大小，栈1的底固定在下标为0的一端；栈2的底固定在下标为StackSize-1的一端。
constintStackSize=100;//100只是示例数据，需根据具体问题定义
template
classBothStack
{
public:
private:
};
在栈i中插入元素x的算法用伪代码描述为：
在栈i中删除栈顶元素的算法用伪代码描述为：
3.1.3栈的链接存储结构及实现
链栈的示意图：
链栈中是否需要头结点？
为什么？
1.栈的链接存储结构——链栈
栈的链接存储结构称为链栈。
2.链栈的实现
template
classLinkStack
{
public:
private:
};
链栈的基本操作示意图如图3-5所示。
链栈的插入算法如下：
链栈的删除算法如下：
3.1.4顺序栈和链栈的比较
顺序栈和链栈的基本操作的时间性能比较
顺序栈和链栈的基本操作的空间性能比较
3.2队列
3.2.1队列的逻辑结构
1.队列的定义
队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。
允许插入（也称入队）的一端称为队尾，允许删除（也称出队）的一端称为队头。
2.队列的抽象数据类型定义
ADTQueue
Data
队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系
Operation
队列的抽象数据类型可定义为抽象类：
InitQueue
前置条件：
队列不存在
输入：
无
功能：
初始化队列
输出：
无
后置条件：
创建一个空队列
DestroyQueue
前置条件：
队列已存在
输入：
无
功能：
销毁队列
输出：
无
后置条件：
释放队列所占用的存储空间
EnQueue
前置条件：
队列已存在
输入：
元素值x
功能：
在队尾插入一个元素
输出：
如果插入不成功，抛出异常
后置条件：
如果插入成功，队尾增加了一个元素
DeQueue
前置条件：
队列已存在
输入：
无
功能：
删除队头元素
输出：
如果删除成功，返回被删元素值，否则，抛出删除异常
后置条件：
如果删除成功，队头减少了一个元素
GetQueue
前置条件：
队列已存在
输入：
无
功能：
读取队头元素
输出：
若队列不空，返回队头元素
后置条件：
队列不变
Empty
前置条件：
队列已存在
输入：
无
功能：
判断队列是否为空
输出：
如果队列为空，返回1，否则，返回0
后置条件：
队列不变
endADT
3.2.2队列的顺序存储结构及实现
1.队列的顺序存储结构——循环队列
放宽队列的所有元素必须存储在数组的前n个单元这一条件，入队和出队操作时间性能为O
（1），但由此造成了队列的单向移动。
1．继续分析图3-8示意图，发现会产生什么新问题（如图3-8（a）所示。
）？
队列的单向移动造成了顺序队列的假溢出。
2．解决的方案（如图3-8（b）所示）
3．结论：
队列的这种头尾相接的顺序存储结构称为循环队列
设存储循环队列的数组长度为QueueSize，则循环队列的长度为（rear-front+QueueSize）%QueueSize。
4．这时又会产生什么新问题？
（如图3-9所示）队空和队满的判定问题，如何解决？
2.循环队列的实现
constintQueueSize=100;//定义存储队列元素的数组的最大长度
template//定义模板类CirQueue
classCirQueue
{
public:
private:
};
循环队列的入队算法如下：
循环队列的出队算法如下：
循环队列的基本操作的实现非常简单，且时间复杂度均为O
（1）。
3.2.3队列的链接存储结构及实现
1.队列的链接存储结构——链队列
队列的链接存储结构称为链队列。
链队列什么设队头指针和队尾指针？
为什么加头结点？
可不可以不加头结点？
2.链队列的实现
将队列的抽象数据类型定义在链队列存储结构下用C++中的类实现。
template
classLinkQueue
{
public:
private:
};
创建链队列（即构造函数）的算法。
入队算法。
出队算法用伪代码描述为：
链队列的出队算法，注意在队列长度为1时的特殊处理。
3.2.4循环队列和链队列的比较
循环队列和链队列的基本操作的时间性能的比较：
循环队列和链队列的空间性能的比较：
3.3串
3.3.1串的逻辑结构
1.串的定义
串是零个或多个字符组成的有限序列，只包含空格的串称为空格串。
串中所包含的字符个数称为串的长度，长度为0的串称为空串，记作""，一个非空串通常记作：
S="s1s2……sn"
其中，S是串名，双引号是定界符，不属于串的内容，双引号引起来的部分是串值，si（1≤i≤n）是一个任意字符，si在串中出现的序号称为该字符在串中的位置。
串的例子：
串中任意个连续的字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串，子串的第一个字符在主串中的序号称为子串在主串中的位置。
2.串的抽象数据类型定义
串操作的特点：
ADTString
Data
串中的数据元素仅由一个字符组成，相邻元素具有前驱和后继关系
Operation
StrLength
前置条件：
串S已存在
输入：
无
功能：
求串S的长度
输出：
串S中的字符个数
后置条件：
串S不变
StrAssign
前置条件：
无
输入：
串T
功能：
串赋值，将T的串值赋值给串S
输出：
串S
后置条件：
串T不变
StrConcat
前置条件：
无
输入：
串S，串T
功能：
串连接，将串T放在串S的后面连接成一个新串S
输出：
串S
后置条件：
串T不变
StrSub
前置条件：
串S已存在
输入：
位置i，长度len
功能：
求子串，返回从串S的第i个字符开始长为len的子串
输出：
S的一个子串
后置条件：
串S不变
StrCmp
前置条件：
无
输入：
串S，串T
功能：
串比较
输出：
若S=T，返回0；若ST,返回1
后置条件：
串S和T不变
StrIndex
前置条件：
串S已存在
输入：
串T
功能：
子串定位
输出：
子串T在主串S中首次出现的位置
后置条件：
串S和T不变
StrInsert
前置条件：
串S已存在
输入：
串T，位置i
功能：
串插入，将串T插入到串S的第i个位置上
输出：
串S
后置条件：
串T不变
StrDelete
前置条件：
串S已存在
输入：
位置i，长度len
功能：
串删除，删除串S中从第i个字符开始连续len个字符
输出：
串S
后置条件：
串S的长度减少了len
StrRep
前置条件：
串S已存在
输入：
串T，串R
功能：
串替换，在串S中用串R替换所有与串T相等的子串
输出：
串S
后置条件：
串T和R不变
endADT
3.串的比较
给定两个串：
X="x1x2…xn"
Y="y1y2…ym"
则当n=m且x1=y1，…，xn=ym时，称X=Y；
当下列条件之一成立时，称X＜Y：
⑴n＜m，且xi=yi（i=1，2，…，n）；
⑵存在某个k≤min（m，n），使得xi=yi（i=1，2，…，k-1），xk＜yk。
3.3.2串的存储结构
1．串的顺序存储结构
串的顺序存储结构是用数组来存储串中的字符序列。
在串的顺序存储中，一般有三种方法表示串的长度：
⑴用一个变量来表示串的长度，如图3-13所示。
⑵在串尾存储一个不会在串中出现的特殊字符作为串的终结符，如图3-14所示。
⑶用数组的0号单元存放串的长度，串值从1号单元开始存放，如图3-15所示。
2．串的链接存储结构
串的链接存储结构有以下两种解决方案：
⑴非压缩形式。
一个结点只存储一个字符，其优点是操作方便，但存储利用率低。
⑵压缩形式。
为了提高存储空间利用率，一个结点可存储多个字符。
这实质上是一种顺序与链接相结合的结构。
这种存储结构增加了实现基本操作的复杂性，比如对改变串长的操作，可能涉及结点的增加与删除问题。
3.3.3模式匹配
给定两个串S="s1s2…sn"和T="t1t2…tm"，在主串S中寻找子串T的过程称为模式匹配，T称为模式。
如果匹配成功，返回T在S中的位置，如果匹配失败，返回0。
假设串采用顺序存储结构，串长存放在数组的0号单元，串值从1号单元开始存放。
１．朴素的模式匹配算法
BF算法的基本思想是：
从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；否则匹配失败。
BF算法用伪代码描述如下：
设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况：
⑴在最好情况下，每趟不成功的匹配都发生在串T的第一个字符。
平均的比较次数是：
即最好情况下的时间复杂度是O（n+m）。
⑵在最坏情况下，每趟不成功的匹配都发生在串T的最后一个字符。
平均比较的次数是：
一般情况下，m<2．改进的模式匹配算法
升级会员 