第四章串 2018/11/13.

第四章串 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

用一组地址连续的存储单元存储串值的字符序列(字符数组)
定长顺序存储表示 1、定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列(字符数组) 1 2 255 #define MAXSTRLEN //最大允许长度 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

用一组地址连续的存储单元存储串值的字符序列；
堆分配存储表示用一组地址连续的存储单元存储串值的字符序列；存储空间是动态分配的。例，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
串的块链存储表示结点大小＞1时，串长度不一定是结点大小的整数倍串终结：最后一个结点用特殊字符来填充 A B C D E F G H I # # ^ (b) 大小为 4 的结点头指针 2018/11/13

4.2.3 串的块链存储表示为便于操作，以链表存储串值时，需要：头指针：指示链表首结点(入口1) 尾指针：指示链表末结点(入口2)
串的块链存储表示为便于操作，以链表存储串值时，需要：头指针：指示链表首结点(入口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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

模式匹配示例：模式：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

第四章串 2018/11/13.

Similar presentations

Presentation on theme: "第四章串 2018/11/13."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

第四章 串 2018/11/13.

Similar presentations

Presentation on theme: "第四章 串 2018/11/13."— Presentation transcript:

Similar presentations

About project

反馈

第四章串 2018/11/13.

Presentation on theme: "第四章串 2018/11/13."— Presentation transcript: