数据结构3Word格式.docx

1、 输入：销毁栈释放栈所占用的存储空间 Push 元素值x在栈顶插入一个元素x如果插入不成功，抛出异常如果插入成功，栈顶增加了一个元素 Pop 删除栈顶元素如果删除成功，返回被删元素值，否则，抛出异常如果删除成功，栈顶减少了一个元素 GetTop读取当前的栈顶元素若栈不空，返回当前的栈顶元素值栈不变 Empty 判断栈是否为空如果栈为空，返回1，否则，返回0endADT3.1.2 栈的顺序存储结构及实现1. 栈的顺序存储结构顺序栈栈的顺序存储结构称为顺序栈。1. 顺序栈的实现const int StackSize=10; /10只是示例性的数据，可以根据实际问题具体定义template /定义模

2、板类SeqStackclass SeqStackpublic: private:; 3. 两栈共享空间提出问题：在一个程序中如果需要同时使用具有相同数据类型的两个栈时，如何处理呢？解决方案一：为每个栈开辟一个数组空间；解决方案二：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸，如图3-3所示。其中，top1和top2分别为栈1和栈2的栈顶指针，StackSize为整个数组空间的大小，栈1的底固定在下标为0的一端；栈2的底固定在下标为StackSize-1的一端。const int StackSize=100; /100只是示例

3、数据，需根据具体问题定义class BothStack 在栈i中插入元素x的算法用伪代码描述为：在栈i中删除栈顶元素的算法用伪代码描述为：3.1.3 栈的链接存储结构及实现链栈的示意图：链栈中是否需要头结点？为什么？1. 栈的链接存储结构链栈栈的链接存储结构称为链栈。2. 链栈的实现class LinkStack链栈的基本操作示意图如图3-5所示。链栈的插入算法如下：链栈的删除算法如下：3.1.4 顺序栈和链栈的比较顺序栈和链栈的基本操作的时间性能比较顺序栈和链栈的基本操作的空间性能比较3.2 队列3.2.1 队列的逻辑结构1. 队列的定义队列是只允许在一端进行插入操作，而另一端进行删除操作的

4、线性表。允许插入（也称入队）的一端称为队尾，允许删除（也称出队）的一端称为队头。2. 队列的抽象数据类型定义ADT Queue 队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系队列的抽象数据类型可定义为抽象类： InitQueue队列不存在初始化队列创建一个空队列 DestroyQueue队列已存在销毁队列释放队列所占用的存储空间 EnQueue 在队尾插入一个元素如果插入成功，队尾增加了一个元素 DeQueue 删除队头元素如果删除成功，返回被删元素值，否则，抛出删除异常如果删除成功，队头减少了一个元素 GetQueue读取队头元素若队列不空，返回队头元素队列不变判断队列是否

5、为空如果队列为空，返回1，否则，返回0endADT 3.2.2 队列的顺序存储结构及实现1. 队列的顺序存储结构循环队列 放宽队列的所有元素必须存储在数组的前n个单元这一条件，入队和出队操作时间性能为O（1），但由此造成了队列的单向移动。1继续分析图3-8示意图，发现会产生什么新问题（如图3-8（a）所示。）？ 队列的单向移动造成了顺序队列的假溢出。2解决的方案（如图3-8（b）所示）3结论：队列的这种头尾相接的顺序存储结构称为循环队列设存储循环队列的数组长度为QueueSize，则循环队列的长度为（rear-front+QueueSize） % QueueSize。4这时又会产生什么新问题？

6、（如图3-9所示）队空和队满的判定问题，如何解决？2. 循环队列的实现const int QueueSize=100; /定义存储队列元素的数组的最大长度 /定义模板类CirQueueclass CirQueue循环队列的入队算法如下：循环队列的出队算法如下： 循环队列的基本操作的实现非常简单，且时间复杂度均为O（1）。3.2.3 队列的链接存储结构及实现1. 队列的链接存储结构链队列队列的链接存储结构称为链队列。链队列什么设队头指针和队尾指针？为什么加头结点？可不可以不加头结点？2. 链队列的实现将队列的抽象数据类型定义在链队列存储结构下用C+中的类实现。class LinkQueue创建链

7、队列（即构造函数）的算法。入队算法。出队算法用伪代码描述为：链队列的出队算法，注意在队列长度为1时的特殊处理。3.2.4 循环队列和链队列的比较循环队列和链队列的基本操作的时间性能的比较：循环队列和链队列的空间性能的比较：3.3 串3.3.1 串的逻辑结构1. 串的定义串是零个或多个字符组成的有限序列，只包含空格的串称为空格串。串中所包含的字符个数称为串的长度，长度为0的串称为空串，记作 ，一个非空串通常记作：S=s1 s2 sn 其中，S是串名，双引号是定界符，不属于串的内容，双引号引起来的部分是串值，si（1in）是一个任意字符，si在串中出现的序号称为该字符在串中的位置。串的例子：串中任

8、意个连续的字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串，子串的第一个字符在主串中的序号称为子串在主串中的位置。2. 串的抽象数据类型定义串操作的特点：ADT String 串中的数据元素仅由一个字符组成，相邻元素具有前驱和后继关系 StrLength串S已存在求串S的长度串S中的字符个数串S不变 StrAssign 串T串赋值，将T的串值赋值给串S串S串T不变 StrConcat串S，串T串连接，将串T放在串S的后面连接成一个新串SStrSub位置i，长度len求子串，返回从串S的第i个字符开始长为 len 的子串S的一个子串StrCmp串比较若S=T，返回0；若ST, 返回1

9、串S和T不变 StrIndex子串定位子串T在主串S中首次出现的位置StrInsert串T，位置i串插入，将串T插入到串S 的第i个位置上StrDelete串删除，删除串S中从第i个字符开始连续len个字符串S的长度减少了lenStrRep串T，串R串替换，在串S中用串R 替换所有与串T相等的子串串T和R不变3. 串的比较给定两个串： X=x1x2xn Y=y1y2ym则当n=m且x1=y1，xn=ym时，称X=Y；当下列条件之一成立时，称XY： nm，且xi=yi（i=1，2，n）； 存在某个kmin（m，n），使得xi=yi（i=1，2，k-1），xkyk。3.3.2 串的存储结构1串的顺

10、序存储结构串的顺序存储结构是用数组来存储串中的字符序列。在串的顺序存储中，一般有三种方法表示串的长度： 用一个变量来表示串的长度，如图3-13所示。 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，如图3-14所示。 用数组的0号单元存放串的长度，串值从1号单元开始存放，如图3-15所示。2串的链接存储结构串的链接存储结构有以下两种解决方案： 非压缩形式。一个结点只存储一个字符，其优点是操作方便，但存储利用率低。 压缩形式。为了提高存储空间利用率，一个结点可存储多个字符。这实质上是一种顺序与链接相结合的结构。这种存储结构增加了实现基本操作的复杂性，比如对改变串长的操作，可能涉及结点的增加

11、与删除问题。3.3.3 模式匹配给定两个串S=s1s2sn 和T=t1t2tm，在主串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 n，因此最坏情况下的时间复杂度是O（nm）。2改进的模式匹配算法