数据结构3Word格式.docx
《数据结构3Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构3Word格式.docx(22页珍藏版)》请在冰点文库上搜索。
![数据结构3Word格式.docx](https://file1.bingdoc.com/fileroot1/2023-4/28/95fd8f2e-2026-49a9-99ca-e4f1ab08cdac/95fd8f2e-2026-49a9-99ca-e4f1ab08cdac1.gif)
输入:
销毁栈
释放栈所占用的存储空间
Push
元素值x
在栈顶插入一个元素x
如果插入不成功,抛出异常
如果插入成功,栈顶增加了一个元素
Pop
删除栈顶元素
如果删除成功,返回被删元素值,否则,抛出异常
如果删除成功,栈顶减少了一个元素
GetTop
读取当前的栈顶元素
若栈不空,返回当前的栈顶元素值
栈不变
Empty
判断栈是否为空
如果栈为空,返回1,否则,返回0
endADT
3.1.2栈的顺序存储结构及实现
1.栈的顺序存储结构——顺序栈
栈的顺序存储结构称为顺序栈。
1.顺序栈的实现
constintStackSize=10;
//10只是示例性的数据,可以根据实际问题具体定义
template<
classT>
//定义模板类SeqStack
classSeqStack
{
public:
private:
};
3.两栈共享空间
提出问题:
在一个程序中如果需要同时使用具有相同数据类型的两个栈时,如何处理呢?
解决方案一:
为每个栈开辟一个数组空间;
解决方案二:
使用一个数组来存储两个栈,让一个栈的栈底为该数组的始端,另一个栈的栈底为该数组的末端,每个栈从各自的端点向中间延伸,如图3-3所示。
其中,top1和top2分别为栈1和栈2的栈顶指针,StackSize为整个数组空间的大小,栈1的底固定在下标为0的一端;
栈2的底固定在下标为StackSize-1的一端。
constintStackSize=100;
//100只是示例数据,需根据具体问题定义
classBothStack
在栈i中插入元素x的算法用伪代码描述为:
在栈i中删除栈顶元素的算法用伪代码描述为:
3.1.3栈的链接存储结构及实现
链栈的示意图:
链栈中是否需要头结点?
为什么?
1.栈的链接存储结构——链栈
栈的链接存储结构称为链栈。
2.链栈的实现
classLinkStack
链栈的基本操作示意图如图3-5所示。
链栈的插入算法如下:
链栈的删除算法如下:
3.1.4顺序栈和链栈的比较
顺序栈和链栈的基本操作的时间性能比较
顺序栈和链栈的基本操作的空间性能比较
3.2队列
3.2.1队列的逻辑结构
1.队列的定义
队列是只允许在一端进行插入操作,而另一端进行删除操作的线性表。
允许插入(也称入队)的一端称为队尾,允许删除(也称出队)的一端称为队头。
2.队列的抽象数据类型定义
ADTQueue
队列中元素具有相同类型及先进先出特性,相邻元素具有前驱和后继关系
队列的抽象数据类型可定义为抽象类:
InitQueue
队列不存在
初始化队列
创建一个空队列
DestroyQueue
队列已存在
销毁队列
释放队列所占用的存储空间
EnQueue
在队尾插入一个元素
如果插入成功,队尾增加了一个元素
DeQueue
删除队头元素
如果删除成功,返回被删元素值,否则,抛出删除异常
如果删除成功,队头减少了一个元素
GetQueue
读取队头元素
若队列不空,返回队头元素
队列不变
判断队列是否为空
如果队列为空,返回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;
//定义存储队列元素的数组的最大长度
//定义模板类CirQueue
classCirQueue
循环队列的入队算法如下:
循环队列的出队算法如下:
循环队列的基本操作的实现非常简单,且时间复杂度均为O
(1)。
3.2.3队列的链接存储结构及实现
1.队列的链接存储结构——链队列
队列的链接存储结构称为链队列。
链队列什么设队头指针和队尾指针?
为什么加头结点?
可不可以不加头结点?
2.链队列的实现
将队列的抽象数据类型定义在链队列存储结构下用C++中的类实现。
classLinkQueue
创建链队列(即构造函数)的算法。
入队算法。
出队算法用伪代码描述为:
链队列的出队算法,注意在队列长度为1时的特殊处理。
3.2.4循环队列和链队列的比较
循环队列和链队列的基本操作的时间性能的比较:
循环队列和链队列的空间性能的比较:
3.3串
3.3.1串的逻辑结构
1.串的定义
串是零个或多个字符组成的有限序列,只包含空格的串称为空格串。
串中所包含的字符个数称为串的长度,长度为0的串称为空串,记作"
"
,一个非空串通常记作:
S="
s1s2……sn"
其中,S是串名,双引号是定界符,不属于串的内容,双引号引起来的部分是串值,si(1≤i≤n)是一个任意字符,si在串中出现的序号称为该字符在串中的位置。
串的例子:
串中任意个连续的字符组成的子序列称为该串的子串,相应地,包含子串的串称为主串,子串的第一个字符在主串中的序号称为子串在主串中的位置。
2.串的抽象数据类型定义
串操作的特点:
ADTString
串中的数据元素仅由一个字符组成,相邻元素具有前驱和后继关系
StrLength
串S已存在
求串S的长度
串S中的字符个数
串S不变
StrAssign
串T
串赋值,将T的串值赋值给串S
串S
串T不变
StrConcat
串S,串T
串连接,将串T放在串S的后面连接成一个新串S
StrSub
位置i,长度len
求子串,返回从串S的第i个字符开始长为len的子串
S的一个子串
StrCmp
串比较
若S=T,返回0;
若S<
T,返回-1;
若S>
T,返回1
串S和T不变
StrIndex
子串定位
子串T在主串S中首次出现的位置
StrInsert
串T,位置i
串插入,将串T插入到串S的第i个位置上
StrDelete
串删除,删除串S中从第i个字符开始连续len个字符
串S的长度减少了len
StrRep
串T,串R
串替换,在串S中用串R替换所有与串T相等的子串
串T和R不变
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号单元开始存放。
1.朴素的模式匹配算法
BF算法的基本思想是:
从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;
否则,从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;
否则匹配失败。
BF算法用伪代码描述如下:
设串S长度为n,串T长度为m,在匹配成功的情况下,考虑两种极端情况:
⑴在最好情况下,每趟不成功的匹配都发生在串T的第一个字符。
平均的比较次数是:
即最好情况下的时间复杂度是O(n+m)。
⑵在最坏情况下,每趟不成功的匹配都发生在串T的最后一个字符。
平均比较的次数是:
一般情况下,m<
<
n,因此最坏情况下的时间复杂度是O(n×
m)。
2.改进的模式匹配算法