第四章 串 2018/11/13

本章学习要点 掌握串类型的相关概念及术语 掌握串存储结构（顺序串和链串）的特点 掌握串的基本算法工作原理 灵活运用串特点解决应用问题 2018/11/13

计算机上的非数值处理的对象基本上都是字符串数据。 例：学生管理系统中，学生学号、姓名、性别、院系等； 图书管理系统中，图书编号、书名、作者、简介等； 2018/11/13

由于硬件结构的特点，决定了处理字符串数据时要比数值数据复杂的多。 字符串常量 + 字符串操作 = 串类型 字符串变量 由于硬件结构的特点，决定了处理字符串数据时要比数值数据复杂的多。 (1) 字符串是由一个个字符组成的，需要对每个字符分别处理 (2) 字符串需要先转化为数值后再进行处理 ASC(‘A’) = 65 ASC(‘a’) = 97 2018/11/13

4.1 串类型的定义 s = “a1a2 … an” ( n≥0) 其中：串名— s 1. 基本概念（I） 4.1 串类型的定义 1. 基本概念（I） 串: 由零个或多个字符组成的有限序列。 s = “a1a2 … an” ( n≥0) 其中：串名— s 串值— a1a2 … an ， ai为字符 串是特殊线性表： （1）表中每个元素是一个字符 （2）由（1）而要求的一些特殊操作 2018/11/13

4.1 串类型的定义 长度：串中字符的数目， |s| 1. 基本概念（II） 空串：长度为 0 的串，φ = “”，|φ|= 0 4.1 串类型的定义 1. 基本概念（II） 长度：串中字符的数目， |s| 空串：长度为 0 的串，φ = “”，|φ|= 0 空格串：一个或多个空格组成的串称为。” ” “ ” ≠ “”=φ 相等：当且仅当这两个串的值相等，即两个串的长度相等，并且对应位置上的字符都 相等。 串 ‘bei jing’ 与串 ‘beijing’ 不相等 。 2018/11/13

4.1 串类型的定义 1. 基本概念（III） 子串：字符串 s1 中任意个连续的字符组成的子序列 s2 称为串 s1 的子串，而称 s1 是 s2 的主串。 串 “eij” 是串 “beijing” 的子串， “beijing” 称为主串。 字符位置：字符在字符串中的位置（从 1 开始）序号。 字符 ‘n’ 在串 “beijing” 中的位置为 6 。 子串位置：子串的第一个字符在主串中的位置。 子串 “eij” 在串 “beijing” 中的位置为 2 。 2018/11/13

串的基本操作和线性表区别很大。 线性表: 大多以“单个元素”为操作对象 串: 通常以“串的整体”为操作对象 线性表: 大多以“单个元素”为操作对象 例:查找某个元素；插入某个元素；删除某个元素 串: 通常以“串的整体”为操作对象 例: 查找某个子串； 截取某个子串； 在某个位置插入、删除、替换某个子串 2018/11/13

ADT串的定义 ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n } 基本操作：…… } ADT String

串的基本操作（或原子操作） 串赋值：串变量串表达式 串比较：字典比较规则 求串长： 串联接：串合并 求子串：取串内指定位置、长度的子串 子串定位：极其重要的串操作 其他操作均可在这 5 种操作基础上实现 2018/11/13

练 习 一、单项选择题 1．串是一种特殊的线性表，其特殊性体现在（ ）。 A．可以顺序存储 B．数据元素是一个字符 B 1．串是一种特殊的线性表，其特殊性体现在（ ）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链接存储 D．数据元素可以是多个字符 2．串的长度是指（ ） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 B B 2018/11/13

1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。 二、填空题 1．含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。 2．空格串是指 ， 其长度等于 。 3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。 空 字符 由空格字符组成的字符串 空格个数 长度 相等 子 主 2018/11/13

4.2 串的（机内）表示和实现 定长顺序存储表示——顺序存储 堆分配存储表示——顺序存储 块链存储表示——链式存储 2018/11/13

用一组地址连续的存储单元存储串值的字符序列(字符数组) 4.2.1 定长顺序存储表示 1、 定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列(字符数组) 1 2 255 #define MAXSTRLEN 255 //最大允许长度 typedef unsigned char SString[MAXSTRLEN+1] //0 号元素存放串长度值 2018/11/13

按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。 1、 定长顺序存储表示 1 2 255 按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。 串的实际长度可在此预定义长度内随意，但超过预定义长度的串值则被舍去，称之为“截断”。 2018/11/13

1）下标 0 的分量存放串的长度，其它存放串字符。 2、串长度表示 1）下标 0 的分量存放串的长度，其它存放串字符。 1 2 255 2）在串值后面加一个不计入串长的结束标记字符。 （C语言中以“\0”表示串值的终结） 2018/11/13

3、基本操作在定长顺序存储上的实现—串联接 （1）算法思想 串变量 S1、S2、T 的数据类型为SString 串T是由S1联接串S2得到—“串值复制” “abc de” 与 “def” 联结，结果为 “abc dedef” 1 2 255 a b c d e d e f 1 2 255 d e f 2018/11/13

3、基本操作在定长顺序存储上的实现—串联接 （2）超长“截断” 约定：对联接后的超长部分实施“截断”。分以下三种情况： （a）S1的长度+S2的长度<=MAXSTRLEN 得到的串T 是正确的结果 （b）S1的长度< MAXSTRLEN 但S1的长度+S2的长度>MAXSTRLEN 将串S2的一部分截断，得到的串T 只包含串S2的一个子串。 （c）S1的长度=MAXSTRLEN 得到的串T 并非联接结果，而和串S1相等。 2018/11/13

3、基本操作在定长顺序存储上的实现—求子串 （1）算法思想 仍为“串值复制”过程，将串S1中从第pos个字符开始、长度为len的字符序列复制到串S2中。 求子串：S1=“abcde”，pos=2，len=3，结果S2=“bcd” 1 2 255 a b c d e 1 2 255 b c d 2018/11/13

4、定长顺序存储结构操作特点 1）在进行插入、删除等操作时，需要移动大量字符； 2）在进行联接、插入等操作时很容易出现越界，需要截断。 解决方案: 采用动态分配串值的存储空间。 2018/11/13

用一组地址连续的存储单元存储串值的字符序列； 4.2.2 堆分配存储表示 用一组地址连续的存储单元存储串值的字符序列； 存储空间是动态分配的。 例，C 中的 malloc()，free() C++中的 new，free 2018/11/13

//为处理方便，约定串长也作为存储结构的一部分 实现方法: 先获取串所需要的长度 再为串动态申请空间 串的堆分配存储结构 typedef struct { char * ch ； int length ； } HString ； //为处理方便，约定串长也作为存储结构的一部分 2018/11/13

串堆分配存储结构的操作 创建字符串 HString T； //初始化 T 的存储空间 T.ch = (char*) malloc ( 8*sizeof(char) ) T.ch = “abcdefgh” //对 T 赋串值 T.length = 8； //生成 T 长度 2018/11/13

串堆分配存储结构的操作 串插入：在串S中从位置pos开始插入串T Ex. StrInsert(‘abcdefg’,3,’kk’)=‘abkkcdefg’ typedef struct { char * ch ； int length ； } HString ； 2018/11/13

typedef struct node{ 4.2.3 串的链式存储结构 用单链表存储串值，这种链式存储结构简称为链串 char data; struct node *next; }lstring; (a) 结点大小为1的结点 A B C F  …. 2018/11/13

该结构便于插入和删除，但存储空间利用率太低。 4.2.3 串的链式存储结构 链串由头指针唯一确定 该结构便于插入和删除，但存储空间利用率太低。 A B C F  …. 头指针 2018/11/13

#define nodesize 80 typedef struct node{ char data[nodesize]; 每个结点存放多个字符 可提高存储密度 结点大小＝结点存放的字符个数 #define nodesize 80 typedef struct node{ char data[nodesize]; struct node *next; } lstring; 2018/11/13

4.2.3 串的块链存储表示 结点大小＞1时，串长度不一定是结点大小的整数倍 串终结：最后一个结点用特殊字符来填充 A B C D 4.2.3 串的块链存储表示 结点大小＞1时，串长度不一定是结点大小的整数倍 串终结：最后一个结点用特殊字符来填充 A B C D E F G H I # # ^ (b) 大小为 4 的结点 头指针 2018/11/13

4.2.3 串的块链存储表示 为便于操作，以链表存储串值时，需要： 头指针：指示链表首结点(入口1) 尾指针：指示链表末结点(入口2) 4.2.3 串的块链存储表示 为便于操作，以链表存储串值时，需要： 头指针：指示链表首结点(入口1) 尾指针：指示链表末结点(入口2) 串长度 这样定义的存储结构称为串的块链结构 2018/11/13

1、块链存储表示 #define CHUNKSIZE 80 //结点块大小(用户定义) typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk ; //链表结点定义 typedef struct { Chunk *head, *tail; //串头/尾指针 int curlen; //串长度 } LString ; //链表定义 2018/11/13

块链存储密度=串值存储位数÷分配存储位数 存储密度小（即结点中所含字符少时），运算处理方便，但是存储占用量大 存储密度大（即结点中所含字符多时），存储占用量小，运算处理不便 A B C D E F G H I # # ^ (b) 大小为 4 的结点 头指针 2018/11/13

串存储结构小结 定长顺序存储、堆分配存储 链式存储 通常在各种高级程序设计语言中采用 堆分配存储的串既有顺序存储结构的特点：处理方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中常常被采用 链式存储 对某些串操作（如联接）有一定方便之处，但总的不如定长顺序存储结构和堆分配存储结构灵活，它占用存储空间大并且操作复杂 2018/11/13

4.3 串的模式匹配 模式匹配：子串的定位运算，又称串匹配 主串：s = a b a b c a b c a c b a b c 一般将子串 t 称为模式(串) 若在主串 s 中找到了模式 t，则模式匹配成功 Ex.1 主串：s = a b a b c a b c a c b a b c 模式：t = a b c 2018/11/13

4.3 串的模式匹配 4.3.1 模式匹配算法思路 主串 S=“S0S1S2…Sn-1”，模式 t=“t0t1t2…tm-1” 从主串 S 的第 1 个字符开始，与模式 t 的第 1 个字符比较 若相等，继续逐个比较后续字符； 否则，从 S 的第 2 个字符开始与 t 的第 1 个字符比较 依次类推，若匹配成功，则返回模式 t 第 1 个字符在主串 s 中的位置；否则匹配失败 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第一趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第一趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第一趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第一趟匹配 失配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第二趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第二趟匹配 失配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第三趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第三四趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第三趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第三趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第三趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第三趟匹配 失配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第四趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第四趟匹配 失配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第五趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第五趟匹配 失配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第六趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第六趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第六趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第六趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第六趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第六趟匹配 2018/11/13

a b a b c a b c a c b a b a b c a c 主串：s = a b a b c a b c a c b a b c 模式匹配示例： 模式：t = a b c a c a b a b c a b c a c b a b a b c a c 第六趟匹配 模式的字符已全部比较 均与主串对应位置的字符相同 模式被发现！ 匹配位置＝？ 2018/11/13

int index ( char *s, char *t, int pos) { //pos 主串中的起始位置 朴素模式匹配算法实现 int index ( char *s, char *t, int pos) { //pos 主串中的起始位置 int i= pos - 1, j = 0; while ( s [ i ] != '\0' && t [ j ] != '\0' ) if ( s [ i + j ] == t [ j ] ) j ++; else { i = i + 1; j = 0;} if( t [ j ] == '\0' ) return i; return 0; } 2018/11/13

最坏情况：每次都在最末字符失配 且 模式在主串的最后才出现 设主串长度=n，模式串长度=m，则： 需比较 n – m + 1 趟 朴素模式匹配算法分析 最坏情况：每次都在最末字符失配 且 模式在主串的最后才出现 设主串长度=n，模式串长度=m，则： 需比较 n – m + 1 趟 总比较次数＝m * (n-m+1) 故：T worst (n) = O ( n * m ) 2018/11/13

4.4 串操作应用举例 例：求串 S 中出现的第一个最长重复子串及其位置 例1：S=“abc123abc123!”，输出“无重复子串” 4.4 串操作应用举例 例：求串 S 中出现的第一个最长重复子串及其位置 (1)某子串(其长度大于1)各个字符相同，称之为重复子串 (2)若不存在重复子串，则输出信息“无重复子串”；否则求出(输出)第一个长度最大的重复子串及其位置。 例1：S=“abc123abc123!”，输出“无重复子串” 例2： S=“abceebccadddddaaaaa!”，输出“ddddd” 2018/11/13

【题目分析】 1、程序结构 while ( exist(新重复子串) ) if ( len(新重复子串)＞len(记录的最长重复子串) ) record(新重复子串、长度、位置); output(记录的 最长重复子串、长度、位置) ; 2018/11/13

【题目分析】 2、数据结构 （1）被搜索串：用字符串变量 str （2）当前最长重复子串：字符串变量 maxrepeat 当前最长重复子串位置：整数变量 index （3）新重复子串：若该子串更长，记入 maxrepeat （4）新重复子串长度：整数变量 length （5）新重复子串位置：整数变量 start 2018/11/13

【题目分析】 3、处理操作 发现新重复子串：从串第 1 个字符开始扫描，只要前后字符相同，就是重复子串，直到发现不同字符为止 记录：当前重复子串长度、开始位置 取串：根据记录的开始位置、长度从原串中复制子串 2018/11/13

int LongestString (char *s , int n) { //串 s 长度＝n int index=0, max=0; 【算法】 int LongestString (char *s , int n) { //串 s 长度＝n int index=0, max=0; int length=1, i=0, start=0; char* maxrepeat = (char*) malloc ( sizeof(char*) ); 2018/11/13

i++ ; length ++ ; //若字符重复，继续扫描 } else { //上一个重复子串结束 【算法】（续1） while ( i < n - 1 ) if ( s[i+1]==s[i] ) { i++ ; length ++ ; //若字符重复，继续扫描 } else { //上一个重复子串结束 if (max < length) { max=length; index=start; } i++; start=i; length=1;//初始化下次搜索位置和长度 } 2018/11/13

for ( i=index, i < index + max ; i ++ ) 【算法】（续2） for ( i=index, i < index + max ; i ++ ) maxrepeat [i - index]=s [i]; //复制最长重复子串 maxrepeat [i - index]=‘\0’; printf (“串=%s\n”, s); printf (“最长重复子串=%s\n”, maxrepeat ); printf (“其长度=%d, 位置=%d\n”, max, index ); } //算法结束 2018/11/13

子串长度的初值数为1，表示一个字符自然等于其自身 时间复杂度＝Θ(n)：因为每个字符只与其后继比较一次 [讨论] 子串长度的初值数为1，表示一个字符自然等于其自身 时间复杂度＝Θ(n)：因为每个字符只与其后继比较一次 2018/11/13

练习 用 C 编写函数 int f(char* s) 判断 s 是否“回文” 是返回 1，不是返回 0 如 f (“abba”)返回1，f ("abab")返回0 int f ( char* s) { int i=0, j=0; while ( s [j] ) j++; // j 移到串尾 for ( j--; i<j && s[i]==s[j]; i++, j--); //相向比较字符 return i>=j; } 2018/11/13