03受限的线性表 — 栈、队列和串

1、中国铁道出版中国铁道出版社社 第三章 受限的线线性表 栈栈、队队列和串数据结构数据结构基础教程基础教程史九林史九林 编著编著ISBN978-7-113-15395-3 中国铁道出版社中国铁道出版社本章目录本章目录3.1 3.1 栈栈3.2 3.2 队列队列3.3 3.3 串串中国铁道出版社中国铁道出版社主要内容主要内容栈的定义及其基本操作栈的定义及其基本操作1顺序栈及链栈的实现顺序栈及链栈的实现2队列的定义及其基本操作队列的定义及其基本操作3循环队列及链队列的实现循环队列及链队列的实现4栈、队列和串的应用栈、队列和串的应用6串定义及串的操作串定义及串的操作5中国铁道出版社中国铁道出版社教学要求

2、教学要求目标和要求1.理解栈的定义、特征及其所定义的基本操作2. 掌握在两种存储结构上对栈的基本操作的实现3.理解队列的定义、特征及其所定义的基本操作4. 掌握在两种存储结构上对队列的基本操作的实现4. 理解串的定义、特征串表达式、串基本操作及串匹配算法教学重点1.栈的定义及逻辑特点2. 顺序栈和链栈的存储结构及操作实现3. 队列的定义及逻辑特点4. 顺序队列、循环队列和链队列的存储结构及操作实现5.串的定义、逻辑和存储特点，6.串表达式和匹配运算算法教学难点难点1.顺序栈的溢出条件；2.栈操作的综合应用；3.递归算法的思想，栈与递归算法的关系；4.循环队列的对空、满判断条件；5.循环队列上的

3、插入、删除操作；6.无回溯串匹配算法及失败函数。中国铁道出版社中国铁道出版社3.1 栈栈中国铁道出版社中国铁道出版社1. 栈的定义栈的定义栈：限制结点插入和删除只能在同一端进行的线性表栈：限制结点插入和删除只能在同一端进行的线性表 anan-1.a2a1进栈进栈 出栈出栈 栈顶指针栈顶指针(top) 栈底指针栈底指针(bottom) 栈底元素栈底元素 一个重要特点：最后压入的结点最先弹出，最先压入的结点只能最后弹出LIFO表表(Last In First Out )栈顶指针栈顶指针 (top) 栈底指针栈底指针(bottom)空栈空栈栈顶指针和栈底指针都等于0时，栈为空中国铁道出版社中国铁道出

4、版社2.栈的基本操作1u 创建栈 建立一个空栈2u 判栈空 栈为空吗？3u 压栈 把新结点置为栈顶结点4u 弹栈 删除栈顶结点5u 读栈 读取栈顶结点数据6u 置栈空 置栈为空7u 求栈长度 统计栈中当前结点个数8u 更新 用一个新结点数据替换原栈顶结点中国铁道出版社中国铁道出版社3. 顺序栈顺序栈1.1.栈的顺序存储结构栈的顺序存储结构顺序存储结构存储的栈称为顺序栈，用一个一维数组存储 C语言描述顺序栈语言描述顺序栈 #define MAXSIZE 10 typedef struct char StackNodeMAXSIZE; int top; SeqStack;指示栈顶元素在顺序栈中的位

5、置A：栈顶指针不是指针类型，而是一个整数中国铁道出版社中国铁道出版社顺序栈上的操作顺序栈上的操作1,1,创建栈创建栈: :首先根据栈的数据类型说明一个栈S，再置栈顶指针为0栈顶栈顶(top)=0StackCreate ( S ) StackCreate S; S.top = 0; return S;算法描述算法描述:中国铁道出版社中国铁道出版社顺序栈上的操作顺序栈上的操作2,2,判栈空：判栈空： 检查指定的栈当前是否不含有任何结点。检查指定的栈当前是否不含有任何结点。 特点是，当栈顶指针值为0时，栈必为空。 栈为空时返回“1”，反之返回“0”。top=0M1栈空栈空栈顶指针值等于 0算法描述：

6、算法描述：SeqStackEmpty ( S ) if (S.top=0) return 1; else return 0;中国铁道出版社中国铁道出版社顺序栈上的操作顺序栈上的操作topM1压栈压栈.BCDEFtoptoptoptoptop栈满（顺序栈的大小是有限的）设数组大小为Mtop=M,栈满，此时入栈，则上溢（overflow)3,3,压栈：压栈： 插入一个新结点并成为栈顶结点； 方法是把栈顶指针推进一个结点位置，把新结点存入这个位置； 条件是栈还有空闲结点。算法描述：算法描述：SeqStackPush(S,x) if(S.top M-1) return 0; else S.top S.

7、top+1; S.StackNodeS.top x; return 1;中国铁道出版社中国铁道出版社顺序栈上的操作顺序栈上的操作123M1ABCD弹栈弹栈toptoptoptoptop栈空无删除设数组大小为Mtop=0,栈空，此时弹栈为下溢（underflow)注意注意：弹栈算法并未说明对删除了的结点的处置4,4,弹栈：弹栈： 把栈顶结点删除掉；并使栈顶把栈顶结点删除掉；并使栈顶指针移至下一个结点处；指针移至下一个结点处； 实际是把栈顶指针回退一个结实际是把栈顶指针回退一个结点位置；点位置； 条件是栈不为空时。条件是栈不为空时。算法描述：算法描述：SeqStackPop(S) if (！Seq

8、StackEmpty(S) S.top S.top-1;return 1; else return 0;中国铁道出版社中国铁道出版社顺序栈上的操作顺序栈上的操作5,5,读栈：读栈：把栈顶结点数据读出作为函数的返回值12340ABCDEtop返回值读栈读栈算法描述：算法描述：SeqStackGet(S,y) if (S.top=0 return 0； else y S.StackNodeS.top; return 1 S.dataS.top注意：该算法并未改变栈的状态，即已读出的结点仍保存在原处不变中国铁道出版社中国铁道出版社4. 链栈链栈栈的链存储结构栈的链存储结构 链存储结构存储的栈称为链栈

9、，链存储结构存储的栈称为链栈，是一个单向链表；是一个单向链表； 链栈的结点由结点数据和链栈的结点由结点数据和nextnext指针构成。指针构成。 链栈的头指针也是栈顶指针链栈的头指针也是栈顶指针链栈的结点类型描述：链栈的结点类型描述： typedef struct snodetypedef struct snode char StackNode; char StackNode; struct snode struct snode * *next; next; LinkStackNode;LinkStackNode;结点通过next指针链接起来链栈的结点数据注意注意: : 链栈链栈中指针的方向中

10、指针的方向top为栈顶指针，始终指向当前栈顶结点栈名、链头指针、栈顶指针定义一个链栈：定义一个链栈： LinkStackNode LinkStackNode * *toptop 栈顶结点栈顶结点top 栈底结点栈底结点DCBA.非空栈底非空栈底top空栈空栈中国铁道出版社中国铁道出版社链栈上的操作链栈上的操作 S 栈顶结点栈顶结点栈底结点栈底结点.Xp新结点新结点 S 算法描述：算法描述：LinkStackPush(S,x)LinkStackPush(S,x) LinkStackNode LinkStackNode * *p;p; P P 申请一个申请一个LinkStackNodeLinkSt

11、ackNode结点结点; ; P -StackNode x;P -StackNode x; p-next S;p-next S; S p;S p; 1,1,压栈：压栈： 插入一个新结点并使成为栈顶结点； 方法是把新结点链接为链栈的首结点； 链栈的插入无空间的限制。中国铁道出版社中国铁道出版社链栈上的操作链栈上的操作栈底结点栈底结点.栈顶结点栈顶结点Sp算法描述：算法描述：LinkStackPop(S) LinkStackNode *p; if( S = )return 0; else p S; S = p -next; free(p);return 1; 2,2,弹栈：弹栈： 删除栈顶结点；

12、方法是把栈顶指针移到下一个结点,并释放原栈顶结点； 条件是栈不为空。栈顶结点栈顶结点中国铁道出版社中国铁道出版社q=NULL,返回返回n链栈上的操作链栈上的操作3,3,求栈长度求栈长度: : 统计链栈S中当前所含结点个数。 算法描述：算法描述：LinkStackLength(S)LinkStackLength(S) int n 0; int n 0; LinkStackNode LinkStackNode * *p;p; for(p S;pfor(p S;p空空;p p-next);p p-next)n n+1;n n+1; return n;return n; 栈顶结点栈顶结点栈底结点栈底结

13、点. S qn=1qn=2qn=3qn=?中国铁道出版社中国铁道出版社5. 栈的应用示例栈的应用示例1. 1. 算术表达式括号配对语法处理算术表达式括号配对语法处理 算术表达式中如果出现括号，则必须配对出现。算法描述：算法描述：BracketsPairCheck(B) int i; SeqStackPutEmpty(K); for(i1; ii+1) if(B.ci=#) if(SeqStackEmpty(K) return 1; else return 0; else if(B.ci=() SeqStackPush(K, B.ci); else if(B.ci=) if(SeqStackEm

14、pty(K) return 0; else SeqStackPop(K); 实例：实例：a a* *(b+c)-bc(b+c)-bc* *(ab-d(ab-d* *(x+1)/(2+k)#(x+1)/(2+k)#K_栈（栈空栈空括号配对正确括号配对正确中国铁道出版社中国铁道出版社5. 栈的应用示例栈的应用示例2 2，计算算术表达式的应用，计算算术表达式的应用这是栈应用的典型例子设为无括号算术表达式求值（中缀表达式直接求值 ）(1)规定优先级表：乘除优先于加减；(2) 设置两个栈：DNS(运算数栈)和OPS(运算符栈)；(3) 自左向右扫描，遇操作符则与OPS栈顶优先级比较：当前操作符OPS栈顶

15、则进OPS栈；当前操作符 OPS栈顶，DNS栈顶、次顶和OPS栈顶，退栈形成运算， 运算结果进DNS栈。例：例：实现实现5+4*78/2#的运算过程时栈区变化情况的运算过程时栈区变化情况5 + 4 7 8 / 2 #5+47288操作数或结果操作数或结果 33/2429运算符运算符中国铁道出版社中国铁道出版社5. 栈的应用示例栈的应用示例3 3，在数制转换中的应用：，在数制转换中的应用： 简单算法是逐次除以基数 d 取余法。如10-2转换（d2）。例：例： (67)10=(100011)2，其运算过程如下，其运算过程如下： 输 出 顺 序 NN / 2 余数余数673313316116 80

16、8 40 4 20 2 10 1 01计 算 顺 序 商为 0 时得到的余数是 Bn 的最高位中国铁道出版社中国铁道出版社5. 栈的应用示例栈的应用示例top算法描述：算法描述：DtoB(d) SeqStackCreate(B); int x = 0; do SeqStackPush(B,d % 2); d = d/2; while(d0); while(!SeqStackEmpty (B ) SeqStackGet(B,x); SeqStackPop(B) printf(%d ,x); printf(n);67111033top16top8top40top20top10top0top3 3，

17、在数制转换中的应用：，在数制转换中的应用： 简单算法是逐次除以基数 d 取余法。如10-2转换（d2）。中国铁道出版社中国铁道出版社5. 栈的应用示例栈的应用示例递归递归算法描述：算法描述：RecDtoB(d) if(d/2 0) RecDtoB (d/2); printf(%d ,d%2); 3 3，在数制转换中的应用：，在数制转换中的应用： 数制转换算法可以应用递归算法实现，使算法更为简洁。2%848)2()2(RecDtoB(33)RecDtoB(16)RecDtoB(8)RecDtoB(4)RecDtoB(2)RecDtoB(1)RecDtoB(67)printf(%d ,1%2)1p

18、rintf(%d ,2%2)10printf(%d ,4%2)100printf(%d ,8%2)1000printf(%d ,16%2)10000printf(%d ,33%2)100001printf(%d ,67%2)1000011压栈过程（算法的返回点信息）弹栈过程（返回到算法继续执行）这里的栈是系统内这里的栈是系统内部提供和管理的栈部提供和管理的栈中国铁道出版社中国铁道出版社3.2 队列队列中国铁道出版社中国铁道出版社1， 队列的定义队列的定义限定在表的一端插入、另一端删除。限定在表的一端插入、另一端删除。 线性表线性表 先进先出先进先出 (FIFO(FIFO结构结构) )。 队头队

19、头 下图是队列的示意图： a1a2an 出队方向 入队方向队头指针队头指针 队尾指针队尾指针 删除端删除端插入端插入端中国铁道出版社中国铁道出版社2 ，队列的基本操作1u 建立队列 创建一个新队列且为空2u 判队空 检验队列是否为空3u 入队 把新结点插入队列4u 出队 删除队列的结点5u 读队 读取对头结点信息 6u 队列置空 删除队列所有结点使其为空7u 求队列长度 统计队列中结点个数中国铁道出版社中国铁道出版社3，顺序队列，顺序队列顺序存储结构存储的队列称为顺序队列，用一个一维数组存储顺序存储结构存储的队列称为顺序队列，用一个一维数组存储 #define M 100typedef str

20、uct char QueueNodeM； int Front = 0,Rear = 0； SeqQueue；类型描述：类型描述： 队头、队尾指针不是指针类型，而是数组元素下标队头指针始终指向队头结点的前一个结点位置队尾指针总是指向队尾结点位置队头、队尾指队头、队尾指针初始值为针初始值为0Front=Rear=0 Front=Rear=0 初始空队列初始空队列Rear=M Rear=M 队列满队列满Rear=Front Rear=Front 队列空队列空中国铁道出版社中国铁道出版社顺序队列上的操作顺序队列上的操作插入插入“c”cfront23456=M1abrear1 1，入队：，入队： 在队列

21、尾端插入一个新结点。在队列尾端插入一个新结点。算法描述：算法描述：SeqQueueIn(Q,x) if(Q.rear M)return 0; else Q.rear Q.rear+1; Q.GoodsListQ.rear x; return 1; 第一步 移动Rear指针第二步 存入c到Rear指向的结点注意！注意！若队列已满，若队列已满，则拒绝插入。则拒绝插入。中国铁道出版社中国铁道出版社顺序队列上的操作顺序队列上的操作删除删除“a”front23456=M1abrear2 2，出队：，出队： 从队列头端删除一个结点。从队列头端删除一个结点。算法描述：算法描述：SeqQueueOut( Q

22、) if(Q.front = Q.rear) return 0; else Q.front Q.front + 1; return 1; 注意！注意！1，删除只移动，删除只移动Front指针而已；指针而已；2，若队列空则拒绝删除。，若队列空则拒绝删除。中国铁道出版社中国铁道出版社顺序队列上的操作顺序队列上的操作读出读出“c”3 3，读队列：，读队列： 把队列头端结点的信息作为操作结构返回出去。把队列头端结点的信息作为操作结构返回出去。算法描述：算法描述：SeqQueueGet(Q) if(FrontRear) return Q.QueueNodeQ.Front+1; else return 0

23、 注意！注意！1，读队列操作不改变队列的状态；，读队列操作不改变队列的状态；2，若队列空则拒绝操作。，若队列空则拒绝操作。front23456=M1rearcdc中国铁道出版社中国铁道出版社4. 循环队列循环队列顺序队列存在的问题之一：顺序队列存在的问题之一： 当队头指针当队头指针 0 0，而队尾指针，而队尾指针 = = M M时，不能执行入队操作（尽时，不能执行入队操作（尽管有空闲结点存在）管有空闲结点存在） rear234561假溢出假溢出abcfront“假溢出假溢出”的解决方案：的解决方案： (1) 平移结点：出队操作时向队首平移其余结点；但算法效率低。效率低。 (2) 构建“循环队列

24、”；操作效率高、空间利用率好。操作效率高、空间利用率好。rear234561真溢出真溢出abcfrontdef中国铁道出版社中国铁道出版社循环队列的结构循环队列的结构 循环队列是逻辑上把顺序队列的头和尾相接形成一个圆环；把第循环队列是逻辑上把顺序队列的头和尾相接形成一个圆环；把第1 1号结点看作为号结点看作为M M号结点的后继结点处理。号结点的后继结点处理。 1 2 3 4 5 6 7如队列如队列 Q0123456逻辑地逻辑地构建成构建成 R逻辑地认为，逻辑地认为，6 6号结点号结点的后继结点是的后继结点是0 0号结点。号结点。M=7中国铁道出版社中国铁道出版社循环队列的结构循环队列的结构 队

25、头指针和队尾指针的运作。队头指针和队尾指针的运作。0123456队头指针队头指针队尾指针队尾指针创建初始循环队列时创建初始循环队列时初始循环队列初始循环队列 队列为空队列为空 队头指针队头指针=0 队尾指针队尾指针=0仍然规定：仍然规定： 队头指针队头指针指向队头结点的前一结点 队尾指针队尾指针指向队尾结点中国铁道出版社中国铁道出版社循环队列的结构循环队列的结构 队头指针和队尾指针的运作。队头指针和队尾指针的运作。操作循环队列过程中操作循环队列过程中0123456队头指队头指针针队尾指队尾指针针BCDif（队头指针 M-1） 队头指针队头指针+ 1;else 队头指针 0;或者：或者：队头指针

26、 （队头指针+1）% Mif（队尾指针 front=申请一个LinkQueueNode类型的结点; LQ-front-QueueNode#; LQ-front-next=NULL; LQ-rear=LQ-front; return(LQ);# 队头指针队头指针 队尾指针队尾指针LQ输出一个输出一个“空空”队列队列输出一个输出一个“空空”队列队列中国铁道出版社中国铁道出版社链队列上的操作链队列上的操作1 1，入队，入队 rearfrontxyt算法描述：算法描述：LinkQueueIn(Q,x) LinkQueueIn(Q,x) LinkQueue LinkQueue * *t;t; t t 申

27、请一个申请一个LinkQueueNodeLinkQueueNode类型结点类型结点; ; t- QueueNode x;t- QueueNode x; t-next NULL; t-next NULL; Q-rear-next t; Q-rear-next t; Q-rear t; Q-rear t; 插入插入“x”reary链队列没有队列已满而不能插入的问题中国铁道出版社中国铁道出版社链队列上的操作链队列上的操作2 2，出队，出队 frontxyp算法描述：算法描述：LinkQueueOut( Q )LinkQueueOut( Q ) LinkQueue LinkQueue * *p;p;

28、if(Q.front = Q.rear)if(Q.front = Q.rear) return 0;return 0; elseelse p Q.front -next;p Q.front -next; Q.front -next p -next; Q.front -next p -next; if(Q-rear = p)if(Q-rear = p) Q.rear Q.front;Q.rear Q.front; 释放释放(p);(p); return 1;return 1; rear删除删除“x“x中国铁道出版社中国铁道出版社6，队列结构应用，队列结构应用配对的应用配对的应用 问题描述：已知一

29、个队列，其结点的数据域为一个自然数。输入一个自然数n，与队头结点数据配对。如果相等，则删除队头结点；如果不相等或队列为空，则把n插入队列。如果输入数为0，则结束处理。实例演示：队列的当前状态为：（5，9，8）思路：把输入的数存入n。先判n为何值。若n = 0，就终止算法。否则判队列是否为空；若为空则执行队列插入操作。若队列不为空，则与队头结点比较。比较相等，则执行队列的删除操作；否则执行插入操作。这个过程重复进行，直到输入0时结束 中国铁道出版社中国铁道出版社小结小结讨论：讨论：线性表、栈与队的异同点线性表、栈与队的异同点相同点：逻辑结构相同，都是线性表结构；都可以用顺序存储或链存储。不同点：

30、 操作自由度不同：u 线性表为一般的表，对其可以随意进行操作；u 栈和队列是两种操作受限的线性表；即限制其插入和删除的位置。 用途不同：u 线性表的通用性好；适用于任意处理结点的问题；u 栈适用于具有后进先出特征地处理结点的问题。如用程序调用控制，递归等；u 队列适用于具有先进先出特征地处理结点的问题。如排队问题等。中国铁道出版社中国铁道出版社3.3 串串中国铁道出版社中国铁道出版社必须的定界符！必须的定界符！但不属于串的值！但不属于串的值！ 串的串的 1，串的定义串的串的 串的串的 是由计算机字符组成的有限序列。是由计算机字符组成的有限序列。 表示为：表示为：s = c1 c2 c3 ci

31、cn ( ( n n0 )0 )。例：例： x x =123 =123 其中，其中，123 123 是串是串 x x = 123 = 123 其中，其中， 123123 是数值是数值test =testtest =test 其中，其中，testtest是串名，是串名，testtest是串是串 字符序号字符序号 中国铁道出版社中国铁道出版社1，串的定义 当当 n n 0 0 时，时， 称称 S S 为为“实串实串”或或“非空串非空串” ” s s = =This is a string.This is a string. 当当 n n 0 0 时，时， 称称 S S 为为“空串空串” ” 当当

32、c ci i 都为空格字符时，称都为空格字符时，称 S S 为为“空格串空格串”或或“空白串空白串” ” 空串空串空白串空白串s s =s =s = （表示不可见的空格字符表示不可见的空格字符）中国铁道出版社中国铁道出版社2，（1）相等关系相等关系 精确相等 左对齐相等 两串长度相等自左至右逐对对应字符相等 两串长度未必相等按较短串长度自左至右逐对对应字符相例：例： S S =NanJing =NanJing S1S1 =Nan Jing =Nan Jing S S2 2 =“NanJing” =“NanJing” S S3 3 =“Nan” =“Nan” S = S2 S 精确等于精确等于

33、S2 S = S3 S 左对齐等于左对齐等于 S2S1 = S3 S1 左对齐等于左对齐等于 S3中国铁道出版社中国铁道出版社2，（2 2）不等关系）不等关系： 例：例： S S =NanJing =NanJing S1S1 =Nan=NanN Ning ing S S2 2 =“Nan” =“Nan” S S1 S S2 S1 S2 如果两串不等长，则在较短串右端补足空格字符使等长；然后如果两串不等长，则在较短串右端补足空格字符使等长；然后自自左至右逐对比较两串的对应字符，当碰到不等字符时停止比较；左至右逐对比较两串的对应字符，当碰到不等字符时停止比较；则较大字符所在串为较大串，较小字符所在

34、串为较小串。则较大字符所在串为较大串，较小字符所在串为较小串。 中国铁道出版社中国铁道出版社2，（3 3）子串关系：）子串关系：主串例：例：S S =“I am a student now.”=“I am a student now.” S S1 1 =“student” =“student” S S2 2=“I am a student”=“I am a student”串串 S S 中的任意中的任意 m m（mnmn）个连续字符构成的串）个连续字符构成的串 M M 称为称为 S S 的子串的子串子串“studentstudent”是是 S S 的子串的子串“I am a studentI

35、am a student”是是 S S 的子的子串串“now.now.”是是 S S 的子串的子串如果一个串如果一个串 M M 是另一个串是另一个串 S S 的子串，则的子串，则 S S 与与 M M 之间有子串关之间有子串关系系S1 S1 是是 S S 的子串，的子串，S S包含包含S1S1S2 S2 是是 S S 的子串，的子串，S S包含包含S2S2S 包含包含 M特殊情况：特殊情况： 空串是任意串的子串空串是任意串的子串 任意串是其自身的子串任意串是其自身的子串中国铁道出版社中国铁道出版社3，串的基本操作，串的基本操作1u 串赋值 把一个串存入串变量2u 串精确相等 判别两串是否精确相

36、等3u 串比较 判别两串是小于、相等、还是大于 4u 求串长度 计算串中字符个数5u 取子串 取串的指定位置的子串6u 串匹配 在主串中查找与给定子串相等的子串7u 并串 拼接两串成为一串8u 串置换 用某串去替换一个串中的指定子串9u 串插入 在串的指定位置插入一个串10u 串删除 删除串中指定位置的连续若干字符11u 判判串空 判别串是否为空串12u 置空置空串 把串改变为空串13u 串表达式 对串执行或运算（并串） 中国铁道出版社中国铁道出版社4. 串的存储结构串的存储结构串串与线性表十分相似与线性表十分相似 但，串的结点数据限制为只一个但，串的结点数据限制为只一个单字单字符符 串顺序存

37、储结构串顺序存储结构静态顺序存储结构（静态顺序存储结构（顺序串顺序串）动态顺序存储结构（动态顺序存储结构（堆串堆串）一次性为串分配好足够的存储单元一次性为串分配好足够的存储单元随时扩充和释放空间随时扩充和释放空间 顺序串顺序串结构类型描述结构类型描述#define MAXSIZE 100typedef struct char chMAXSIZE；int length ；SeqStaticStr ；堆串结构类型描述堆串结构类型描述typedef struct char *ch； int length； HeapString；串的实际长度在预定义长度范围内随意变化，超出部分被截断。可以一个特殊的字

38、符作为字符串的结束标志，串长是一个隐含值。中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法串的基本操作和线性表有很大差别串的基本操作和线性表有很大差别线性表：线性表：大多以大多以“单个结点单个结点”作为操作对象作为操作对象串：串：通常以通常以“串的整体串的整体”作为操作对象作为操作对象 如：在线性表中查找某个结点、读取某个结点、在某个位置上插入一个结点和删除一个结点等； 如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法（1 1）判串精确相等）判串精确

39、相等串串S：串串R：s t u d e n t . s t u d e n t . S.lengthR.length算法描述：算法描述：SeqStrEqual(S,R) int k; if(S.lengthR.length) return 0; else for(k=1;S.chk=R.chk且且kS.length;k k+1); if(i S.length) return 1; else return 0; =i=1=i=2=i=3=i=4=i=5=i=6=i=7=i=8等长且全部字符对应相等，判串精确相等判串精确相等成功。中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基

40、本运算算法（1 1）判串精确相等）判串精确相等串串S：串串R：s t u d e n t . s t u d u n t . S.lengthR.length算法描述：算法描述：SeqStrEqual(S,R) int k; if(S.lengthR.length) return 0; else for(k=1;S.chk=R.chk且且kS.length;k k+1); if(i S.length) return 1; else return 0; =i=1=i=2=i=3=i=4i=5等长，但遇到不相等字符，判串精确相等判串精确相等失败。中国铁道出版社中国铁道出版社5，对串的几个基本运算算

41、法，对串的几个基本运算算法（1 1）判串精确相等）判串精确相等串串S：串串R：s t u d e n t a b c s t u d e n t . S.lengthR.length算法描述：算法描述：SeqStrEqual(S,R) int k; if(S.lengthR.length) return 0; else for(k=1;S.chk=R.chk且且kS.length;k k+1); if(i S.length) return 1; else return 0; 两串不等长，判串精确相等判串精确相等失败。中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法

42、（2 2）串比较）串比较串串S：串串R：s t u d e n t . s t u d u n t . S.lengthR.length算法描述：算法描述：SeqStrCompare(S,R) int k; for(k=1;S.chk=R.chk且且kS.length且且kR.length;k k+1); if(i S.length或或i R.length) return 0; else if(S.chkR.chk) return 1; else return -1; =i=1=i=2=i=3=i=4i=5S串小于R串，输出-1。中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几

43、个基本运算算法（3 3）取子串）取子串 算法描述：算法描述：SeqStrSubstring(S,i,l) int k; SeqStaticStr T; if(1iS.length且1lS.length-i+1) for(k=1;kl;k k+1) T.chkS.chi+k-1;T.Length l; elseT.Length 0; return T;中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法d a t a s t r u c t u r e主串主串S：子串子串T：4a7kkksktkrkukci=1i=7注意：注意：可能出现可能出现“参数非法情参数非法情况况

44、（3 3）取子串）取子串 例如，例如，SeqStrSubstring(S,4,7)SeqStrSubstring(S,4,7)；中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法（4 4）并串）并串在串的静态顺序存储结构上并串时，必须在串的静态顺序存储结构上并串时，必须考虑可能出现的四种情况：考虑可能出现的四种情况：采用串的堆存储结构上实现并串就不存在串连接时被截断的问题采用串的堆存储结构上实现并串就不存在串连接时被截断的问题把两个串按出现的次序拼接成一个串把两个串按出现的次序拼接成一个串设有串设有串 S S 和和 R R 欲并串，串长度分别为欲并串，串长度分别为S

45、.nMS.nM，R.nR.n第第1 1种情况：种情况： R.n = 0 R.n = 0 直接输出直接输出S S第第2 2种情况：种情况： S.n + R.n S.n + R.n M M 完全并串完全并串第第3 3种情况：种情况： S.n S.n M M 而而 S.n + R.nS.n + R.nM RM R右端截断右端截断 第第4 4种情况：种情况： S.n S.n M RM R全部截断全部截断 中国铁道出版社中国铁道出版社 x u a n w u h uR: 1 2 3 4 5 6 7 8 9 10 11 12=M S.n n a n S: 1 2 3 4 5 6 7 8 9 10 11 1

46、2=M 5，对串的几个基本运算算法，对串的几个基本运算算法（4 4）并串）并串把两个串按出现的次序拼接成一个串把两个串按出现的次序拼接成一个串并串有两种方式：原串并串（并串有两种方式：原串并串（“”方式）和去空格并串（方式）和去空格并串（ “ “”方式）方式）SeqStrConcat (S,R, )xuanwuhuS.n第第2种情况种情况中国铁道出版社中国铁道出版社 x u a n w u h uR: 1 2 3 4 5 6 7 8 9 10 11 12=M S.n n a n S: 1 2 3 4 5 6 7 8 9 10 11 12=M 5，对串的几个基本运算算法，对串的几个基本运算算法（

47、4 4）并串）并串把两个串按出现的次序拼接成一个串把两个串按出现的次序拼接成一个串并串有两种方式：原串并串（并串有两种方式：原串并串（“”方式）和去空格并串（方式）和去空格并串（ “ “”方式）方式）SeqStrConcat (S,R, )xuanwuhuS.n第第2种情况种情况中国铁道出版社中国铁道出版社 1 2 3 4 5 6 7 8 9 10 11 12=M u n i v e r s i t yR:S.n n a n S: 1 2 3 4 5 6 7 8 9 10 11 12=M 5，对串的几个基本运算算法，对串的几个基本运算算法（4 4）并串）并串把两个串按出现的次序拼接成一个串把两

48、个串按出现的次序拼接成一个串并串有两种方式：原串并串（并串有两种方式：原串并串（“”方式）和去空格并串（方式）和去空格并串（ “ “”方式）方式）SeqStrConcat (S,R, )universiS.n第第3种情况种情况右端截断右端截断中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法（4 4）并串）并串算法描述：算法描述：SeqStrConcat(S,R,F) int k; if(R.length0) if(F=-) k=1; while(R.chk=) k k+1; R.length R.length-k+1 R SeqStrSubstring(R,k,R

49、.length); if(S.length+R.lengthMAXSIZE) for(k 1;kR.length) S.chS.length+k R.chk; S.length S.length+R.length else if(S.lengthMAXSIZE)for(k 1;kMAXSIZE - S.length) S.chS.length+k R.chk; S.length MAXSIZE; 中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 在目标串中找出与模式串匹配的子串出现的位置（第一个匹配字符位置在目标串中找出与模式串匹配

50、的子串出现的位置（第一个匹配字符位置）匹配成功cdbacdbai=5输出此结点序号输出此结点序号cdcbabbaa 主串主串S S：模式串模式串T T： 1 2 3 4 5 6 7 8 9中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 简单串匹配算法：简单串匹配算法：基本思路：基本思路： c d b acdcbabbaa 主串主串S S：模式串模式串T T：ij相相等等匹配开始：匹配开始：i=1i=1，j=1j=1ij不不等等 1

51、2 3 4 5 6 7 8 9匹配失败匹配失败 !中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 简单串匹配算法：简单串匹配算法：基本思路：基本思路： c d b acdcbabbaa 主串主串S S：模式串模式串T T：重新开始：重新开始：i=i-j+2=2i=i-j+2=2，j=1j=1ij相相等等ij相相等等ij不不 等等 1 2 3 4 5 6 7 8 9匹配失败匹配失败 !中国铁道出版社中国铁道出版社5，对串的几个基本运算

52、算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 简单串匹配算法：简单串匹配算法：基本思路：基本思路： c d b acdcbabbaa 主串主串S S：模式串模式串T T：再重新开始：再重新开始：i=i-j+2=3i=i-j+2=3，j=1j=1ij不不 等等 1 2 3 4 5 6 7 8 9匹配失败匹配失败 !中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串

53、匹配算法简单串匹配算法，无回溯串匹配算法 简单串匹配算法：简单串匹配算法：基本思路：基本思路： c d b acdcbabbaa 主串主串S S：模式串模式串T T：再重新开始：再重新开始：i=i-j+2=4i=i-j+2=4，j=1j=1ij不不 等等 1 2 3 4 5 6 7 8 9匹配失败匹配失败 !中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 简单串匹配算法：简单串匹配算法：基本思路：基本思路： c d b acdcba

54、bbaa 主串主串S S：模式串模式串T T：再重新开始：再重新开始：i=i-j+2=5i=i-j+2=5，j=1j=1ij相相 等等 1 2 3 4 5 6 7 8 9匹配成功匹配成功 !ij相相 等等ij相相 等等ij相相 等等中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 简单串匹配算法：简单串匹配算法：SeqStrMatch(S，T) int i=1,j=1; if(S.Length=0或T.Length=0) return -1; else While(iS.length且jT.length) if(S.chi=T.ch

55、j) ii+1; jj+1; else i=i-j+2 j1; if(jT.length) return i-T.length+1; else return -1; 中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 简单串匹配算法的弱点：简单串匹配算法的弱点： 一但匹配失败一但匹配失败, ,简单匹配算法只简单地把模式串简单匹配算法只简单地把模式串相对于目标串向后只滑动一个字符继续重新比较。这相对于目标串向后只滑动一个字符继续重新比较。这种比较存在着大量的重复；种比较存在着大量的重复；i=i-j+2=i-(j-2)i=i-j+2=i-

56、(j-2)就意味着就意味着每次重复比较每次重复比较(j-2)(j-2)次；使匹配的时间效率降低。次；使匹配的时间效率降低。 采用采用无回溯串匹配无回溯串匹配算法可以避免这个缺陷。算法可以避免这个缺陷。中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 无回溯串匹配算法无回溯串匹配算法：基本思路：基本思路：模式串模式串T T：ij相相等等匹配开始：匹配开始：i=1i=1，j=1j=1 c d c b a b a b a 主串主串S S：

57、1 2 3 4 5 6 7 8 9匹配失败匹配失败 ! c b a b a 1 2 3 4 5 ij相相等等ij相相等等ij相相等等ij不不等等中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 无回溯串匹配算法无回溯串匹配算法：基本思路：基本思路：模式串模式串T T：ij相相等等重新开始：重新开始：i=5i=5，j=3j=3 c d c b a b a b a 主串主串S S： 1 2 3 4 5 6 7 8 9匹配失败匹配失败 !

58、c b a b a 1 2 3 4 5 ij相相等等ij相相等等而不从而不从i=2i=2，j=1j=1重新开始重新开始不重复参与比较了不重复参与比较了中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 无回溯串匹配算法无回溯串匹配算法：思路的关键：思路的关键：模式串模式串T T：重新开始：重新开始：i=5i=5，j=3j=3 c d c b a b a b a目标串目标串S S： 1 2 3 4 5 6 7 8 9 c b a b a

59、1 2 3 4 5 i=5 i=5 目标串位置保持，即目标串位置保持，即无回溯无回溯 j=3j=3 根据模式串特征和上次比较结根据模式串特征和上次比较结 果决定，即计算果决定，即计算失败函数失败函数的值的值 中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 无回溯串匹配算法无回溯串匹配算法：失败函数：失败函数： 当一次匹配失败后需继续匹配时，计算模式串开始位置值的函数当一次匹配失败后需继续匹配时，计算模式串开始位置值的函数Kj=max

60、m|（0mj）且“t1t2tm”=“tj- mtj-1tj” 当集合非空0 其他情况 j = next(j) = K j-1 +1其中，中国铁道出版社中国铁道出版社5，对串的几个基本运算算法，对串的几个基本运算算法( (5 5) ) 串匹配串匹配 两种匹配算法两种匹配算法 - - 简单串匹配算法，无回溯串匹配算法简单串匹配算法，无回溯串匹配算法 无回溯串匹配算法无回溯串匹配算法：失败函数：失败函数： 当一次匹配失败后需继续匹配时，计算模式串开始位置值的函数当一次匹配失败后需继续匹配时，计算模式串开始位置值的函数例如，模式串例如，模式串T的值的值Kj为：为： j = 1 2 3 4 5T= a