数据结构C++版.ppt

1、2020年7月8日星期三,3.0 引例,1.函数调用顺序与返回顺序的关系：,2.走迷宫时经过路口与返回重试顺序的关系：,3.打印机接收打印指令与实际完成任务的顺序关系：,4.网站请求的顺序与响应顺序的关系,5.信息处理中处理量最大的信息： 文本信息：字符串,栈，队和字符串,调用：ab c d,返回： d c b fa,返回：d c b a,搜索：ab c d,完成： a b c d,指令： a b c d,响应： a b c d,请求： a b c d,2020年7月8日星期三,第 3 章 栈、队列和串,栈的特点，抽象数据类型及实现； 队列的特点，抽象数据类型及实现； 串的概念，抽象数据类型及

2、存储。,栈和队列的操作特性； 栈和队列基本操作的实现； 串的模式匹配算法。,两栈共享空间的实现； 循环队列的组织及队空队满的判定； 改进的模式匹配KMP算法。,2020年7月8日星期三,3.1 栈,3.1.1 栈的逻辑结构,1.栈的定义,栈（stack）是限在表尾进行插入和删除操作的线性表。,允许进行插入和删除操作的一端叫栈顶，另一端称为栈底。,（a1,a2,a3,a4,an）,栈顶,栈底,栈的示意图：,a1,a2,a3,a4,栈的几个术语： 空栈，入栈/压栈，出栈/弹栈。,2020年7月8日星期三,3.1 栈,3.1.1 栈的逻辑结构,1.栈的几个特点,线性性:相邻元素有前驱和后继关系,a1

3、,a2,a3,a4,注意，栈只限制了插入和删除的位置，并没有限制插入和删除的时间。以三个元素（a,b,c）依次入栈为例，有下列几种情况：,受限性：所有操作限于栈顶,后进先出性：元素入栈后再出栈，后进者先出（last in first out）,2020年7月8日星期三,3.1 栈,3.1.1 栈的逻辑结构,a,b,c,三个元素依次入栈（a,b,c）再出栈的情形示意：,a,b,c,a,b,c,a,b,c,a,b,c,三个元素的情形有五种，那N个元素时，如何求解全部的方案？,2020年7月8日星期三,3.1 栈,3.1.1 栈的逻辑结构,上述过程的分析树（待进栈中已出）：,abc,bca,cab,

4、abc,abc,acb,cba,cab,acb,abc,bca,cba,cba,bac,bca,cba,bca,bac,acb,cab,cab,abc,2020年7月8日星期三,3.1 栈,3.1.1 栈的逻辑结构,2.栈的抽象数据类型定义,ADT Stack Data 栈中元素具有相同类型及后进先出特性， 相邻元素具有前驱和后继关系,Operation InitStack 前置条件：栈不存在 输入：无 功能：栈的初始化 输出：无 后置条件：构造一个空栈,2020年7月8日星期三,3.1 栈,3.1.1 栈的逻辑结构,2.栈的抽象数据类型定义,DestroyStack 前置条件：栈已存在 输入

5、：无 功能：销毁栈 输出：无 后置条件：释放栈所占用的存储空间,Push 前置条件：栈已存在 输入：元素值x 功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素,2020年7月8日星期三,3.1 栈,3.1.1 栈的逻辑结构,2.栈的抽象数据类型定义,Pop 前置条件：栈已存在 输入：无 功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素,GetTop 前置条件：栈已存在 输入：无 功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变,2020年7月8日

6、星期三,3.1 栈,3.1.1 栈的逻辑结构,2.栈的抽象数据类型定义,Empty 前置条件：栈已存在 输入：无 功能：判断栈是否为空 输出：如果栈为空，返回1，否则，返回0 后置条件：栈不变 endADT,2020年7月8日星期三,3.1 栈,3.1.2 栈的顺序存储结构及实现,1.栈的顺序存储结构,栈的顺序存储结构称为顺序栈（sequential stack）。它实际上是顺序表的简化，通常我们用小下标端表示栈底，大下标端表示栈顶。,由于顺序栈的主要操作发生在栈顶，故我们用一个变量（top）来标记它。请注意它与顺序表的length的关系。,表中元素个数,栈顶元素下标,2020年7月8日星期三

7、,3.1 栈,3.1.2 栈的顺序存储结构及实现,1.栈的顺序存储结构,空栈,满栈,top=-1,top= StackSize-1,2020年7月8日星期三,private: int StackSize; /存储栈的允许个数 int top; /存储栈顶元素下标 T *data; /存储数组的初地址,template /模板类 class SeqStack ;,public: SeqStack(int n ) ; /构造函数 SeqStack( ) ; /析构函数 void Push(T x); /入栈 T Pop(); /出栈 T GetTop(); /取栈顶元素 bool Empty();

8、 /判断栈空否,3.1 栈,3.1.2 栈的顺序存储结构及实现,2020年7月8日星期三,3.1 栈,3.1.2 栈的顺序存储结构及实现,2. 顺序栈的主要算法实现,（1）顺序栈的构造函数,操作接口：SeqStack() / SeqStack(int n),算法： SeqStack: SeqStack(int n) data=new Tn /申请数组空间 StackSize=n; /栈中元素个数初值 top=-1; /栈顶位置初值 ,2020年7月8日星期三,3.1 栈,3.1.2 栈的顺序存储结构及实现,2. 顺序栈的主要算法实现,（2）顺序栈的入栈函数,操作接口：void Push(T x

9、),主要操作？,边界条件？,2020年7月8日星期三,3.1 栈,3.1.2 栈的顺序存储结构及实现,2. 顺序栈的主要算法实现,（2）顺序栈的入栈函数,算法： void SeqStack: Push(T x) if (top=StackSize-1) throw “上溢” top+; datatop=x ,2020年7月8日星期三,3.1 栈,3.1.2 栈的顺序存储结构及实现,2. 顺序栈的主要算法实现,（2）顺序栈的出栈函数,操作接口：T Pop(),算法： T SeqStack: T Pop() if (top=-1) throw “下溢”; x=datatop-; return x;

10、 ,2020年7月8日星期三,3.1 栈,3.1.3 两栈共享空间,1. 两栈共享空间原由,在应用中，当我们使用两个类型相同的栈时，极有可能出现下列情形，一个栈已满，而另一栈可能还接近空。两个栈是不能直接共享的。？,top1,top2,2020年7月8日星期三,3.1 栈,2. 两栈共享空间的方式,共享栈就是两个栈（分别标为1号和2号栈）使用一个公共的数组空间，两个栈分别从下标增加和下标减少的两个方向入栈，出栈时则相反。只要数组没有完全被装满，任意一个栈都可以入栈；而当数组被装满时，两个栈同时为满。栈为空的条件两个栈是独立的。,top1,top2,共享栈满和空的条件？,3.1.3 两栈共享空间

11、,2020年7月8日星期三,3.1 栈,3. 两栈共享空间的ADT,P85-86 ,3.1.3 两栈共享空间,注意主要区别： 入，出栈等需要指明栈号 ,2020年7月8日星期三,private: int StackSize; /存储栈的总个数 int top1,top2; /存储各栈顶元素下标 T *data; /存储数组的初地址,template /模板类 class BothStack ;,public: BothStack(int n ) ; /构造函数 BothStack( ) ; /析构函数 void Push(int i,T x); /入栈 T Pop(int i); /出栈 T

12、GetTop(int i); /取栈顶元素 bool Empty(int i); /判断栈空,3.1 栈,4. 共享栈的C+实现,3.1.3 两栈共享空间,2020年7月8日星期三,3.1 栈,5. 主要算法实现,3.1.3 两栈共享空间,(1)共享栈的入栈函数,操作接口：void Posh(int i,T x),操作：当栈不满时，加入到指定的栈顶,算法： void SeqStack: Push(T x) if (top1+1=top2 ) throw “上溢”; if (i=1) data+top1=x; if (i=2) data-top2=x; ,2020年7月8日星期三,3.1 栈,3

13、.1.3 两栈共享空间,(1)共享栈的出栈函数,操作接口：T Pop(int i),操作：当指定栈不空时，弹出指定栈顶元素,算法： T SeqStack: Pop(int i) switch (i) case 1: if (top1=-1 ) throw “下溢”; return datatop1-;break; case 2: if (top2=StackSize ) throw “下溢”; return datatop2+; ,2020年7月8日星期三,3.1 栈,3.1.4 栈的链接存储结构及实现,1.栈的链接存储结构链栈,栈的链接存储结构称为链栈（linked stack）。,由于栈的

14、操作仅限栈顶，故在链栈中，不再需要附加表头。,2020年7月8日星期三,3.1 栈,3.1.4 栈的链接存储结构及实现,2. 链栈的C+实现,private: Node *top; /存储栈顶元素指针,template /模板类 class LinkStack ;,public: LinkStack( ) ; /构造函数 LinkStack( ) ; /析构函数 void Push(T x); /入栈 T Pop(); /出栈 T GetTop(); /取栈顶元素 bool Empty(); /判断栈空否,2020年7月8日星期三,3.1 栈,3.1.4 栈的链接存储结构及实现,3. 链栈主要

15、算法实现,（1）入栈函数,操作接口：void Push(T x),操作：创建结点，压入栈顶,算法： void LinkStack: Push(T x) s=new Node; s-data=x; s-next=top; top=s; ,2020年7月8日星期三,3.1 栈,3.1.4 栈的链接存储结构及实现,3. 链栈主要算法实现,（2）出栈函数,操作接口：T Pop(),操作：栈非空时，栈顶元素出栈,算法： T LinkStack: Pop() if (top=NULL) throw “下溢”; x=top-data; s=top;top=top-next;delete s; return

16、x; ,2020年7月8日星期三,3.1 栈,3.1.4 栈的链接存储结构及实现,3. 链栈主要算法实现,（3）取栈顶元素函数,操作接口：T GetTop(),操作：栈非空时，返回栈顶元素（不出栈）,算法： T LinkStack: TetTop() if (top=NULL) throw “下溢”; return top-data; ,2020年7月8日星期三,3.1 栈,3.1.4 栈的链接存储结构及实现,3. 链栈主要算法实现,（4）判断栈空否函数,操作接口：bool Empty(),操作：返回栈空否的状态,算法： bool LinkStack: Empty() return (top=

17、NULL); ,2020年7月8日星期三,3.1 栈,3.1.5 顺序栈与链栈的比较,由于栈的主要操作都在栈顶进行，故无论是顺序栈，还是链栈，其时间复杂性都为O（1）。,从空间性能比较，顺序栈需要预分配空间，存在栈满和个数的限制；链栈根据实际需要分配空间，但它的每一个结点都需要附加的指针域。,一般建议：栈使用过程中元素个数变化范围较大时，建议使用链栈，否则使用顺序栈。,2020年7月8日星期三,作业,利用栈（stack）的基本操作（假设已有，直接利用即可），写一算法，完成十进制数n向P进制数（P在2-9之间）的转换。 接口建议： void nToP(int n) 或：void nToP(int

18、 n,int p) 转换后直接输出到屏幕， 格式如： 14=1110 6=110,2020年7月8日星期三,栈：,a1,a2,a3,a4,操作受限的线性表,后进先出（last in first out）,另一种先进先出的线性表：队列,2020年7月8日星期三,3.2 队列,3.2.1 队列的逻辑结构,1.队列的定义,队列（queue）也是特殊的线性表，与栈不同的是，它的插入和删除分别在线性表的两端分别进行。与生活中的排队一样，允许插入的一端叫队尾，删除的一端则称作队首。,2020年7月8日星期三,3.2 队列,3.2.1 队列的逻辑结构,2.队列的特性,线性性:相邻元素有前驱和后继关系,受限性

19、：插入和删除限在不同的两端,先进先出性：元素先入队必先出（ first in first out）,2020年7月8日星期三,3.2 队列,3.2.2 队列的抽象数据类型定义,ADT Queue Data 队列中元素具有相同类型及先进先出特性， 相邻元素具有前驱和后继关系,Operation InitQueue 前置条件：队列不存在 输入：无 功能：初始化队列 输出：无 后置条件：创建一个空队列,2020年7月8日星期三,3.2 队列,DestroyQueue 前置条件：队列已存在 输入：无 功能：销毁队列 输出：无 后置条件：释放队列所占用的存储空间,EnQueue 前置条件：队列已存在 输

20、入：元素值x 功能：在队尾插入一个元素 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，队尾增加了一个元素,3.2.2 队列的抽象数据类型定义,2020年7月8日星期三,3.2 队列,DeQueue 前置条件：队列已存在 输入：无 功能：删除队头元素 输出：如果删除成功，返回被删元素值 后置条件：如果删除成功，队头减少了一个元素,GetQueue 前置条件：队列已存在 输入：无 功能：读取队头元素 输出：若队列不空，返回队头元素 后置条件：队列不变,3.2.2 队列的抽象数据类型定义,2020年7月8日星期三,3.2 队列,Empty 前置条件：队列已存在 输入：无 功能：判断队列是否

21、为空 输出：如果队列为空，返回1，否则，返回0 后置条件：队列不变 endADT,3.2.2 队列的抽象数据类型定义,2020年7月8日星期三,3.2 队列,3.2.3 队列的顺序存储结构及实现,1.从顺序表到顺序队的改进,入队,出队,如何提高性能？,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,1.队从顺序表到顺序队的改进,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,注意到，随着入队和出队的进行，元素向数组的尾部聚集，会出现前边空而后边“满”的情形。,解决这种 “假满”的方法是使用循环数组。,1.队从顺序表到顺序队的改进,20

22、20年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,顺序队列空与满问题,循环顺序队列空的条件是：？,front=rear,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,循环顺序队列满的条件是：？,front=rear,顺序队列空与满问题,如何区分 队空与队满？,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,解决循环顺序队列空和满的条件都是front=rear的问题，一般有下列两个方案：,方案一：增加一个实际元素个数计数变量，当front与rear相等时，通过元素个数来判断为空还是满的情况。,方案二：在队接近满

23、的临界情况，就停止入队，代价是浪费一个单元，但有校的区分出了队空和队满的条件。,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,2 .循环顺序队列C+的类实现,private: int front,rear,QueueSize; /头指针，尾指针，总个数 T data ; /存储元素的数组首地址,template /模板类 class CirQueue ;,public: CirQueue(int n ) ; /构造函数 CirQueue( ) ; /析构函数 void EnQueue(T x); /入队 T DeQueue(); /出队 T GetQueue()

24、; /取队首顶元素 bool Empty(); /判断队空否,需要存储 什么信息？,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,3 . 基本操作的算法,（1）构造函数,操作接口：CirQueue(int n),算法： CirQueue: CirQueue(int n) data=new Tn; QueueSize=n; front=rear=0; ,主要操作：申请空间，头、尾指针初始化,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,3 . 基本操作的算法,（2）入队函数,操作接口：void EnQueue(T x),算法： vo

25、id CirQueue:EnQueue(T x) if (front=(rear+1)% QueueSize) throw “上溢”; rear=(rear+1) % QueueSize; datarear=x; ,主要操作：判断，赋值，移动尾指针,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,3 . 基本操作的算法,（3）出队函数,操作接口：T DeQueue(),算法： T CirQueue:DeQueue() if (front=rear) throw “下溢”; front=(front+1) % QueueSize; return datafront;

26、 ,主要操作：判断，移动头指针，返回值,2020年7月8日星期三,3.2 队列,3.2.2 队列的顺序存储结构及实现,3 . 基本操作的算法,（4）取队首元素函数,操作接口：T GetQueue(),算法： T CirQueue:GetQueue() if (front=rear) throw “下溢”; i=(front+1) % QueueSize; return datai; ,主要操作：判断，返回值,2020年7月8日星期三,3.2 队列,3.2.3 队列的链接存储结构及实现,1 . 链接队的C+实现,如何改进链接表的存储结构来实现链队？,附加表头的存在使得空队入队是规范的。,2020

27、年7月8日星期三,3.2 队列,private: Node *front,*rear; /头指针，尾指针,template /模板类 class LinkQueue ;,public: LinkQueue( ) ; /构造函数 LinkQueue( ) ; /析构函数 void EnQueue(T x); /入队 T DeQueue(); /出队 T GetQueue(); /取队首顶元素 bool Empty(); /判断队空否,3.2.3 队列的链接存储结构及实现,1 . 链接队的C+实现,2020年7月8日星期三,3.2 队列,3.2.3 队列的链接存储结构及实现,2 . 链接队的基本算

28、法,（1）构造函数,操作接口：LinkQueue(),主要操作：申请附加表头，头、尾指针初始化,算法： LinkQueue :LinkQueue() front=rear=new Node; rear-next=NULL; ,2020年7月8日星期三,3.2 队列,3.2.3 队列的链接存储结构及实现,2 . 链接队的基本算法,（2）入队函数,操作接口：void EnQueue(T x),主要操作：申请结点，赋值、加于尾部,算法： void LinkQueue :EnQueue(T x) rear-next=new Node; rear=rear-next;rear-next=NULL; re

29、ar-data=x; ,2020年7月8日星期三,3.2 队列,3.2.3 队列的链接存储结构及实现,2 . 链接队的基本算法,（3）出队函数,操作接口：T DeQueue(),主要操作：判断，取值、删除结点，返回值,算法： T LinkQueue :DeQueue() if(front=rear) throw “下溢”; p=front-next;front-next=p-next; x=p-data; if(p-next=NULL) rear=front;/删最后一个的特例 return x; ,2020年7月8日星期三,3.2 队列,3.2.3 队列的链接存储结构及实现,3 . 循环链接

30、队,事实上，我们也可以使用单循环链表来实现链队，它的只需要设一个指向队尾的尾指针即可。,2020年7月8日星期三,3.2 队列,3.2.4 循环顺序队与链接队的比较,存储结构：？,空间复杂性？,2020年7月8日星期三,第 3 章 栈、队队列和串,栈、队列的模块化引用,stack S queue Q /定义栈S 定义队Q Initstack(S) Initqueue(Q) /初始化栈S 和队Q queueempty(Q) /判断队Q是否为空 enqueue(Q,d) /入队(在队尾插入一个元素d) dequeue(Q,d) /出队(删除队头元素给d) stackempty(S) /判断栈S是否

31、为空 push(S,d) /入栈（在栈顶插入一个元素d) pop(S,d) /出栈(删除栈顶元素给d),2020年7月8日星期三,实验小结与提示,上次的实验：,结果不太理想！ 准备不够充分！ 环境不太熟悉！ 态度不太端正！,下次实验：括号匹配问题 在算述表达式中，可能出现嵌套的大、中、小括号，设计一个算法，可以判断给定的表达式串中的括号是否是匹配的。,要求：首先，分别先定义一个栈和一个队；其次，将表达式串中的各种括号字符依次入队（其它字符不予考虑）；最后利用栈来判断队中的括号是否是匹配的。,2020年7月8日星期三,实验小结与提示,下次实验：括号匹配问题,无论是什么括号，最后出现的左括号，必须

32、与其后最先出现的右括号匹配，这符合栈的后进先出的特点，故我们可以用栈和进行匹配性判断（手动演示）。,),(,),(,2020年7月8日星期三,实验小结与提示,下次实验：括号匹配问题,调用关系：,Main(): 初始化串， 调用测试函数 进行处理,测试函数： 利用栈，队， 进行测试，并返回结果,栈,队,判断字符 类型函数: 左/右括号:1/2,2020年7月8日星期三,实验小结与提示,下次实验：括号匹配问题的测试函数,根据要求，串(括号) 队 栈,操作接口：bool match(char *s),主要操作：？,队，栈初始化 括号字符入队 出队为左括号：进栈 出队为右括号：弹栈，栈空？ 队空？ 栈

33、空？,2020年7月8日星期三,实验小结与提示,算法N-S图（草）：,初始化栈S和队Q,所有括号字符入队Q,当队Q非空,出队,压栈,栈S非空？,少左括号,不匹配,是左括号？,两者匹配？,出栈,匹配成功,少右括号,栈S空？,2020年7月8日星期三,作业,P112：9.1 若以不带附加表头的循环链表作为队列，且只设指向队尾的尾指针，试设计相应的入队和出队的算法。 （设循环链队的类名为LinkQueue，队尾指针是：rear，仅写出入队和出队的函数）,2020年7月8日星期三,3.3 串,3.3.1 串的逻辑结构,1 . 串的定义,串（string）也是特殊的线性表，它是由字符构成的线性表。也就是

34、字符序列，通常记为： S= s1s2s3s4sn,2.串的几个要点,123 a b 计算机 ,1）串是字符线性表（有限，有序） 2）字符在串中的位置也称为位序号 3）每个字符都取自某个特殊的字符集,常见字符集： ASCII码(7bit) 扩展ASCII码(8bit) Unicode(16bit) 统一码、万国码,2020年7月8日星期三,3.3 串,3.3.1 串的逻辑结构,3.串的几个术语,空串：不含字符的串 空格串：仅含空格字符的串 串长：串中含有字符的个数 子串/母串：子串包含在母串中 子串在母串的位置：子串在母串的起始位置,“计算机科学与技术” “科学” 后者是前者的子串。,2020年

35、7月8日星期三,3.3 串,3.3.1 串的逻辑结构,4. 串的比较,串的比较是通过组成串的字符整体比较来完成的。,两个串相等，当且仅当两串同长且各个对应字符相同。,以两个串中首次出现不等字符的关系来表示串的不等的关系（比较结果为一整数 0）,2020年7月8日星期三,3.3 串,3.3.1 串的逻辑结构,5. 串的抽象数据类型定义,串作为特殊的线性表，它的操作与普通的线性表有很大的不同，主要是它更多的关注整体性的操作。比如，串的比较，子串的定位，插入，更新等。,具体的ADT定义见P98-P99。,由于串是最常见的输入/输出数据，所以，许多高级语言都提供了比较丰富的字符串的处理功能。,下面仅就

36、比较常用的串操作作简单的说明。,2020年7月8日星期三,3.3 串,3.3.1 串的逻辑结构,5. 串的抽象数据类型定义, StrLength (s)：求串s的长度。 StrAssign (s1, s2)：赋值，将s2的值赋值给串s1。 StrConcat (s1, s2, s)：连接，将串s2放在串s1的后面连接成一个新串s。 SubStr (s, i, len)：求子串，返回从串s的第i个字符开始取长为 len 的子串。 StrCmp (s1, s2)：串比较，若s1=s2，返回0；若s1s2, 返回1。,2020年7月8日星期三,3.3 串,3.3.1 串的逻辑结构,5. 串的抽象数据

37、类型定义, StrIndex (s, t)：定位，返回子串t在主串s中首次出现的位置。若t不是s的子串，则返回0。 StrInsert (s, i, t)：插入，将串t插入到串s中的第i个位置。 StrDelete (s, i, len)：删除，在串s中删除从第i个字符开始的连续len个字符。 StrRep (s, t, r)：替换，在串s中用串r替换所有与串t相等的子串。,2020年7月8日星期三,3.3 串,3.3.2 串的存储结构,1. 串的顺序存储结构,串的顺序存储结构就是使用数组来存储字符串，即字符数组，由于串的长度可能发生变化，故对于串长需要专门的处理。通常的方案有三种：,1）象C

38、语言一样，在串的尾部存储一个特殊的符号来表示串的结束,2020年7月8日星期三,3.3 串,3.3.2 串的存储结构,1. 串的顺序存储结构,2）同普通的线性表一样，除存储字符串的数组外，外加一个专门存储实际串长的变量,2020年7月8日星期三,3.3 串,3.3.2 串的存储结构,3. 串的顺序存储结构,3）存储字符串的数组中，在零下标处，存储实际实际的串长，真正的字符从下标1处开始存储。,事实上，顺序存储的三种存储方案中，都应该考虑到串的允许长度Maxsize，因为数组都需要预分配空间。,本教材后面的串示例中，重点在介绍串的操作方法，直接使用方案三的简化版：字符数组来表示,2020年7月8

39、日星期三,3.3 串,3.3.2 串的存储结构,2. 串的链接存储结构,串的链接存储就是字符链表，由于串常与其它的串进行联接，故通常为分设指向串头和串尾的两个指针。,串的链接存储又分非压缩存储与压缩存储两种方法，以下是它们的存储示意图。请关注其时空特点？,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,1. 模式匹配问题,在任意一个文本编辑器中，都允许用户进行查找或替换操作，其主要功能是在文本中查找指定的字符串，甚至进行替换操作，查找或替换的关键是定位。,我们称这种在主串中定位子串位置的过程称为模式匹配（子串也称为模式串）,模式匹配的特点：,1）主串通常较大，甚至要多次匹配

40、； 2）使用频繁。,以上两点都要求算法高效。,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,BF算法的基本思想就是用模式串在主串中一一进行比较，直到找到全部相等的一段字符，或找完。,例如：主串S=“ababcabcacbab” 模式串 T=“abcac” ，其BF算法的匹配过程如下：,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,主串S=“ababcabcacbab” 与模式串 T=“abcac”的匹配过程：,第1趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配

41、问题,2. 朴素的模式匹配算法-BF算法,主串S=“ababcabcacbab” 与模式串 T=“abcac”的匹配过程：,第2趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,主串S=“ababcabcacbab” 与模式串 T=“abcac”的匹配过程：,第3趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,主串S=“ababcabcacbab” 与模式串 T=“abcac”的匹配过程：,第4趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的

42、模式匹配算法-BF算法,主串S=“ababcabcacbab” 与模式串 T=“abcac”的匹配过程：,第5趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,主串S=“ababcabcacbab” 与模式串 T=“abcac”的匹配过程：,匹配成功！,第6趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,操作接口：int BF(char S,char T),N-S图：,两个指针初始化,当没有找完且没有找到,对应字符相等？,比下一对,两指针回溯,模式比较完？,返回位置,返回0,2

43、020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,进一步细化的N-S图：,i=j=1,while (i=S0j+,i=i-j+2;j=1,jT0？,return i-j+1,return 0,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,BF算法： int BF(char S,char T) i=j=1； while(iT0) return i-j+1; return 0; ,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,2. 朴素的模式匹配算法-BF算法,BF算

44、法的时间性能分析：,若设主串的长度为n，模式串的长度为m，则：,1）最好情况，失败发生在第一对字符，进行比较的时间为：O(n)；,2）最坏情况，失败发生在最后一对字符，进行比较的时间为：O(n*m)；,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,在BF算法的匹配过程中，存在着多次的主串指针和模式串指针的回溯。,改进的主要思想是： 主串指针不回溯，模式串指针少回溯。,第1趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,在BF算法的匹配过程中，存在着多次的主串指针和模式串指针

45、的回溯。,改进的主要思想是： 主串指针不回溯，模式串指针少回溯。,第2趟,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,在BF算法的匹配过程中，存在着多次的主串指针和模式串指针的回溯。,改进的主要思想是： 主串指针不回溯，模式串指针少回溯。,第3趟,匹配成功！,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,当主串指针不回溯时，模式串指针最坏情况也是回溯到1，好的情况时，指针可以从1向右滑动一段距离，我们来反推一下，发生这种情况特点：,某位置失配,可向右滑到某位置,-,-,-,

46、2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,通过上面的分析我们知道，当上趟匹配串在第j个位置失匹时，下趟并非一定回溯到1，回溯的位置与主串无关，仅与匹配串的结构有关。,具体地讲，当匹配串第j个位置前有连续的k-1个子串与匹配串的最前k-1个子串相同时，下趟匹配就可以从下标k=(1+k-1)处开始。,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,于是我们得到了下列的当匹配串在第j个位置失匹时，求匹配串右滑距离next(j)的公式如下：,next(j)=,0 当j=1,Maxk

47、| j前的子串，最前和最后的k-1个字符相同,1 其它情况,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,模式串 T=“abcac”的next(j)值计算如下： j:12345 next(j):01112,模式串 T=“aaaab”的next(j)值计算如下： j:12345 next(j):01234,故在主串S=“aaaaab”中 对模式串 T=“aaaab”进行匹配的趟数是？,“aaaaab” “aaaab”,“aaaaab” “aaaab” J滑到4的位置,2,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题

48、,3. 改进的模式匹配算法-BMP算法,有了上边的next(j)函数，则有BMP算法的N-S图：,i=j=1,while (i=S0j+,j=next(j),jT0？,return i-j+1,return 0,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,next(3)=1 指针回溯到1 （从第1个开始比较）,BMP算法演示：,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,3. 改进的模式匹配算法-BMP算法,BMP算法演示：,next(5)=2 指针回溯到2（从第2个开始比较）,BMP算法仅对主串扫描一遍，故

49、算法的时间复杂性为O(n)，而对长度为m的匹配串求next()函数的算法也仅需扫描一遍匹配串，时间复杂性为O(m)（该算法处理很巧，留作自学）。,2020年7月8日星期三,3.3 串,3.3.3 串的模式匹配问题,4.匹配串求next()函数的算法,求next()函数的N-S图：,i=1;next1=0;j=0,while (iT0),Ti=Tj | j=0 ?,i+;j+;nexti=j,j=next(j),2020年7月8日星期三,实验,本周实验：括号匹配问题,调用关系：,Main(): 初始化串， 调用测试函数 进行处理,测试函数： 利用栈，队， 进行测试，并返回结果,栈,队,判断左右括

50、号 匹配函数： true/false,判断字符 类型函数: 左/右括号:1/2,程序演示,2020年7月8日星期三,作业,P113：9.3 用顺序存储结构存储串S（零下标处存储串长），编写算法，删除S中的第i个起连续的j个字符。特别说明，若第i个起连续的字符不足j个，就删除到串尾。,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,1.递归,递归（recursion）是函数直接或间接地调用自己，是一种描述问题和解决问题的基本方法。,递归通常用来解决结构自相似问题。,所谓结构自相似问题，是指原问题的结构与构成原问题的子问题的结构是相似的。,如：求n!，而n!=n*(n-1

51、)! （0！=1）,求n!的方法与求(n-1)!的方法是相似的。只是问题的规模不同，当然，也有直接计算的时候，如n=0，则有 0！=1 。,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,2.递归问题的两个要素,1）递归模式：大问题可以分解成相似结构的小问题；,2）递归边界：有不需要递归的简单情形。,3.递归算法,4.递归算法执行轨迹,利用递归问题的递归特性，写出的自己直接或间接调用自己的函数来求解问题的算法.,n!的递归定义如下,n!=,n*(n-1)! n0,1 n=0,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,4.递归算法执行轨迹

52、,求n!的操作接口：int jc(int n),n=0 ？,int jc(int n) if (n=0) return 1; return n*jc(n-1); ,return 1;,返回n与n-1的阶乘的积,根据n!的递归定义，容易得到下列的求n!的N-S图：,jc(n-1),算法很简洁！,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,以下是求4！的调用过程的示意图：,jc(4),4*jc(3),3*jc(2),2*jc(1),1*jc(0),1,1,2,6,24,24,1,4.递归算法执行轨迹,递 归 过 程,返 回 过 程,执行很麻烦！,2020年7月8日星期

53、三,3.4 应用举例,3.4.1 栈的应用举例递归,递归算法可转换为非递归算法：,1）直接转换法：通常用来消除尾递归和单向递归，将递归结构用循环结构来代替。,尾递归是指在递归算法中，递归调用语句只有一个，并且是在算法的最后。如求n!的非递归算法,int jc(int n) int s=1; for (int i=1;i=n;i+) s=si; return s; ,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,递归算法可转换为非递归算法：,单向递归是指在递归算法中有多个递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句是在算法的最后。如求费波那奇

54、数列的算法（见后）,2）间接转换法：使用栈保存中间结果，一般根据递归函数在执行过程中栈的变化得到。,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,再来看著名的汉诺塔问题：,4.递归算法执行轨迹,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,先将上面的n-1个从A移到B；,再将最下面的一个从A移到C；,最后将B上的n-1个移到C；OK！,可问题是那n-1个是怎么移动的呢？,与原来的移动n个是相似的：递归！,4.递归算法执行轨迹,算法思想(大事化小)：,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,将n个碟子从A移

55、到C的操作接口：,void Hanoi (int n,char a,char b,char c),N-S图：,n=1 ?,a移到c,上面n-1个a移到b,a移到c,b上n-1个移到c,4.递归算法执行轨迹,Hanoi(n-1,a,c,b),Hanoi(n-1,b,a,c),2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,将n个碟子从A移到C的操作的算法：,void Hanoi (int n,char a,char c, char b) if (n=1) Move(a,c); /移动一个的函数 else Hanoi(n-1,a, c, b); /ab 利用c Move(

56、a,c); Hanoi(n-1,b, a, c); /bc 利用a ,4.递归算法执行轨迹,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,Hanio(3,A,B,C),Hanio(2,A,C,B),Hanio(1,A,B,C),Move (A,C),Move (A,B),Hanio(1,C,A,B),Move (C,B),Move (A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move (B,C),Hanio(1,A,B,C),Move (A,C),Move (B,A),4.递归算法执行轨迹,2020年7月8日星期三,3.4 应用举例,3.4.1 栈的应用举例递归,5.递归函数的内部执行过程,由于递归函数是对自己的嵌套调用，调用与返回的顺序满足后进先出的特点，故递归函数的内部执行过程是通过栈来实现的。, 运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址； 每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈； 每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部