《数据结构》 第四章
《 数据结构》 第四章
数据结构 第四章串 4.1串类型的定义 4.2串的表示和实现 4.2.1定长顺序存储表示 4.22堆分配存储表示 4.23申的块链存储表示 43串的模式匹配算法
数据结构 tjm 第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示 4.3 串的模式匹配算法
数据结构 41串类型的定义 串和基本概念 串( String)是零个或多个字符组成的有限序列。 般记作S=a1a2a3an',其中S是串名,双引号 括起来的字符序列是串值;a(1si≌n)可以是字母 数字或其它字符;串中所包含的字符个数称为该 串的长度。长度为零的串称为空串,它不包含任 何字符。 通常将仅由一个或多个空格组成的串称为空白串。 注意:空串和空白串不同。,例如‘·和“分别 表示长度为的空白串和长度为0的空串
数据结构 tjm 4.1 串类型的定义 一、串和基本概念 串(String)是零个或多个字符组成的有限序列。一 般记作S=‘a1a2a3…an ’，其中S 是串名，双引号 括起来的字符序列是串值；ai(1≦i≦n)可以是字母、 数字或其它字符；串中所包含的字符个数称为该 串的长度。长度为零的串称为空串，它不包含任 何字符。 通常将仅由一个或多个空格组成的串称为空白串。 注意：空串和空白串不同，例如‘ ’和‘’分别 表示长度为1的空白串和长度为0的空串
数据结构 子串串中任意个连续字符组成的子序列 主串包含子串的串 子串在主串中的序号(或位置):子串在主串中首次 出现时的该子串的首字符对应的主串中的序号 例设A= This is a string"B="is 则B是A的子串,A为主串B在A中的序号(或位置) 为3 特别地,空串是任意串的子串,任意串是其自身的 子串。 串的抽象数据定义 串的抽象数据类型定义见书P71
数据结构 tjm 子串:串中任意个连续字符组成的子序列 主串:包含子串的串 子串在主串中的序号（或位置）:子串在主串中首次 出现时的该子串的首字符对应的主串中的序号 例:设 A=“This is a string” B=“is” 则B是A的子串，A为主串,B在A中的序号（或位置） 为3 特别地，空串是任意串的子串，任意串是其自身的 子串。 二、串的抽象数据定义 串的抽象数据类型定义见书P71
数据结构 、串的基本操作 几种在C语言中常用的串运算 (1)求串长( ength): int strlen(char *s)i (2)串复制(copy) char *strcpy (char *to, char *from)i (3联接( concatenation): char strcat(char *to, char *from) (4)串比较( compare) int strcmp(char *s1, char *s2); (5)符定位( index) char strchr(char *s, char c)
数据结构 tjm 三、串的基本操作 几种在C语言中常用的串运算： （1）求串长(length)： int strlen(char *s); （2）串复制(copy)： char *strcpy(char *to,char *from); (3)联接(concatenation)： char strcat(char *to,char *from) (4)串比较（compare) int strcmp(char *s1,char *s2); （5）字符定位(index) char strchr(char *s,char c);
数据结构 、串的定位 iindex(s,tpos) 算法思想:在主串中取从第个字符起、长度和串 t相等的子串和t比较,若相等,则求得函数值为i, 否则值增1直至S中不存在和串t相等的子串为止。 算法参见P79
数据结构 tjm 例、串的定位index(s,t,pos) 算法思想：在主串中取从第i个字符起、长度和串 t相等的子串和t比较，若相等，则求得函数值为i， 否则值增1直至S中不存在和串t相等的子串为止。 算法参见P79
数据结构 42串的衰现和实现 421定长顺序存储表示 定长顺序存储表示也称为静态存储分配的顺序表。 它是用一组连续的存储单元来存放串中的字符序列。 所谓定长顺序存储结构,是直接使用定长的字符数 组来定义,数组的上界预先给出: #define maxstrlen 255 typedef char Sstring[MAXSTRLEN +1] 串长度的表示方法: 方法1:用下标为0的元素存储串长度。 方法2:使用一个不会出现在串中的特殊字符在串 值的尾部来表示串的结束。例如,c语言中以字符 V0表示串值的终结
数据结构 tjm 4.2 串的表现和实现 4.2.1定长顺序存储表示 定长顺序存储表示,也称为静态存储分配的顺序表。 它是用一组连续的存储单元来存放串中的字符序列。 所谓定长顺序存储结构，是直接使用定长的字符数 组来定义，数组的上界预先给出： #define MAXSTRLEN 255 typedef char Sstring[MAXSTRLEN＋1]; 串长度的表示方法： 方法1：用下标为0的元素存储串长度。 方法2：使用一个不会出现在串中的特殊字符在串 值的尾部来表示串的结束。例如，C语言中以字符 ‵\0′表示串值的终结
数据结构 42.2堆分配存储表示 这种存储表示的特点是,仍以一组地址连续的存储 单元存放串值字符序列,但它们的存储空间是在程 序执行过程中动态分配而得。所以也称为动态存储 分配的顺序表。在C语言中利用函数 malloc0 free来根据实际需要动态分配和释放字符数组空 间。这样定义的顺序串类型也有两种形式 1、 typedef char* stringi//c中的串相 当于此类型定义 2、 typedef struct char *chi int length fhstringi
数据结构 tjm 4.2.2堆分配存储表示 这种存储表示的特点是，仍以一组地址连续的存储 单元存放串值字符序列，但它们的存储空间是在程 序执行过程中动态分配而得。所以也称为动态存储 分配的顺序表。在C语言中利用函数malloc()、 free()来根据实际需要动态分配和释放字符数组空 间。这样定义的顺序串类型也有两种形式。 1、typedef char * string; //c中的串相 当于此类型定义 2、typedef struct { char *ch; int length; }hstring;
数据结构 423串的块链存储结构 链式存储结构类似线性链表,但需要考虑每个结 点是存放一个字符还是多个字符。一个字符的, 插入、删除、求长度非常方便,但存储效率低。 多个字符的,改善了效率,在处理大字符串时很 有效,可用特殊符号来填满未充分利用的结点, 但插入、删除不方便。 附设了头尾指针,并给出了当前串的长度的串的 链式存储结构称为块链存储结构。(参见P78类 型定义)
数据结构 tjm 4.2.3 串的块链存储结构 链式存储结构类似线性链表，但需要考虑每个结 点是存放一个字符还是多个字符。一个字符的， 插入、删除、求长度非常方便，但存储效率低。 多个字符的，改善了效率，在处理大字符串时很 有效，可用特殊符号来填满未充分利用的结点， 但插入、删除不方便。 附设了头尾指针，并给出了当前串的长度的串的 链式存储结构称为块链存储结构。（参见P78类 型定义）
数据结构 head s t ri nq#‖#^ head 串值所占存储位 存储密度= 实际分配的存储位
数据结构 tjm s t r i n g # # ^ head s t r i n g ^ head 串值所占存储位 存储密度＝ ————————— 实际分配的存储位