第四章 串 ￡4.1 串的定义 ￡4.2 串的顺序存储结构 ￡4.3 串的链式存储结构 ￡4.4 串的应用—文本编辑

Presentation on theme: "第四章 串 ￡4.1 串的定义 ￡4.2 串的顺序存储结构 ￡4.3 串的链式存储结构 ￡4.4 串的应用—文本编辑"— Presentation transcript:

1 第四章 串 ￡4.1 串的定义 ￡4.2 串的顺序存储结构 ￡4.3 串的链式存储结构 ￡4.4 串的应用—文本编辑
第四章 串 ￡4.1 串的定义 ￡4.2 串的顺序存储结构 ￡4.3 串的链式存储结构 ￡4.4 串的应用—文本编辑 ￡4.2.1 定长顺序存储表示 ￡4.2.2 堆分配存储表示

2 ￡4.1 串的定义 串（string）（或字符串）：是由零个或多个字符组成的有限 序列，一般记为 (n≥0)
串的长度：串中字符的数目。 空串（null string）：零个字符的串，其长度为零。记为“ ”。 Ф 空格串（blank string）：由一个或多个空格组成的串。其长度为串中空格 字符的个数。 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。 字符在串中的位置：即字符在序列中的序号。 串相等：当且仅当这两个串的值相等。即，两个串的长度相等，并且 各个对应位置的字符都相等。

3 例如：假设a、b、c、d为如下的4个串： a = ‘BEI’ , b = ‘JING’ c = ‘BEIJING’ , d = ‘BEI JING’ 它们的长度分别为3、4、7、8；并且a和b都是c和d的子串， a在c和d中的位置都是1，而b在c中的位置是4，在d中的位置则是5。 a、b、c和d彼此都不相等。 串的抽象数据类型定义： ADT String{ 数据对象：D={ ai| ai∈CharacterSet,i=1,2,…,n, n≥0} 数据关系：R1＝{< ai-1, ai >|ai-1,ai ∈D,i=2,…,n} 基本操作： StrAssign (&T, chars) 初始条件：chars是字符串常量。 操作结果：生成一个其值等于chars的串T。 StrCopy (&T, S) 初始条件：串S存在。 操作结果：由串S复制得串T。 StrEmpty(S) 操作结果：若S为空串，则返回TRUE，否则返回FALSE。

4 StrCompare(S, T) 初始条件：串S和T存在。 操作结果：若S>T，则返回值>0；若S=T，则返回值＝0； 若S<T，则返回值<0。 StrLength(S) 初始条件：串S存在。 操作结果：返回S的元素个数，称为串的长度。 ClearString (&S) 操作结果：将S清为空串。 Concat (&T, S1, S2) 初始条件：串S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。 SubString(&Sub, S, pos, len) 初始条件：串S存在,1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos＋1 操作结果：用Sub返回串S的第pos个字符长度为len的子串。 Index(S, T, pos) 初始条件：串S和T存在,T是非空串，1≤pos≤StrLength(S)。 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S 中第pos个字符之后第一次出现的位置;否则函数值为0。 Replace (&S, T, V) 初始条件：串S, T和V存在，T是非空串。 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。

5 初始条件：串S和T存在, 1≤pos≤StrLength(S)＋1。 操作结果：在串S的第pos个字符之前插入串T。
StrInsert (&S, pos, T) 初始条件：串S和T存在, 1≤pos≤StrLength(S)＋1。 操作结果：在串S的第pos个字符之前插入串T。 StrDelete (&S, pos, len) 初始条件：串S存在, 1≤pos≤StrLength(S)－len＋1。 操作结果：从串S中删除第pos个字符起长度为len的子串。 DestroyString (&S) 初始条件：串S存在。 操作结果：串S被销毁。 }ADT String 最小操作子集：串赋值StrAssign、串比较StrCompare、求串长StrLength、 串联接Concat和求子串SubString。 在上述抽象数据类型定义的13种操作中,这5种操作不可能利用其他串操作来实现,但其他串操作均可在这个最小操作子集上实现。

6 例如：利用判等、求串长和求子串等操作实现定位函
数Index(S, T, pos)。 算法4.1如下： int Index (String S, String T, int pos) { //T为非空串。若主串S中第pos个字符之后存在与T相等的子 //串，则返回第一个这样的子串在S中的位置，否则返回0。 if (pos > 0) { n = StrLength (S); m = StrLength (T); i = pos; while (i <= n-m+1) { SubString (sub, S, i, m); if (StrCompare (sub, T) != 0) ++i; else return i; //返回子串在主串中的位置 } // while } //if return 0; //S中不存在与T相等的子串 } // Index

7 ￡4.1 串的定义 ￡4.2.1 定长顺序存储表示 （1）定义 定长顺序存储结构：用一组地址连续的存储单元存储串值的字符序列。
截断：超过预定义长度的串值被舍去。 （2）C语言描述 在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量 分配一个固定长度的存储区，则可用定长数组如下描述之： #define MAXSTRLEN //用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度 （3）串长的表示方法 ①以下标为0的数组分量存放串的实际长度。如，PASCAL语言中的串 类型采用这种表示方法。 ②在串值后面加一个不计入串长的结束标记字符。此时的串长为隐含 值。如，C语言中以“\0”表示串值的终结。

8 （4）串联接和求子串操作 ①串联接Concat (&T, S1, S2) 假设S1、S2和T都是SString型的串变量，且串T是由串S1 链结串S2得到的。基于串S1和S2长度的不同情况，串T值的产生 可能有如下3种情况： A. S1[0]+S2[0]≤MAXSTRLEN,得到的串T是正确的结果。如图4.1(a)所示 S1[0] S2[0] S1 S2 T T[0] MAXSTRLEN (a) S1[0]+S2[0]≤MAXSTRLEN

9 B.S1[0]<MAXSTRLEN，而S1[0]+S2[0]>MAXSTRLEN，
则将串S2的一部分截断，得到的串T只包含串S2的一个子串。 如图4.1(b)所示。 S1[0] S2[0] S1 S2 T T[0] MAXSTRLEN S2中被截去的字符序列 (b) S1[0]<MAXSTRLEN而S1[0]+S2[0]>MAXSTRLEN

10 C. S1[0]=MAXSTRLEN，则得到的串T并非联接结果， 而和串S1相等。
图4.1 串的联结操作Concat(T,S1,S2)示意图

11 串联接 算法4.2如下： Status Concat (SString &T, SString S1, SString S2) { //用T返回由S1和S2联接而成的新串。若未截断， //则返回TRUE,否则FALSE. if (S1[0] + S2[0] <= MAXSTRLEN) { //未截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0] + 1..S1[0] + S2[0]] = S2[1..S2[0]]; T[0] = S1[0] + S2[0]; uncut = TRUE; } else if (S1[0] < MAXSTRLEN) { //截断 T[S1[0] + 1..MAXSTRLEN] = S2[1..MAXSTRLEN – S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; else { //截断（仅取S1） T[0..MAXSTRLEN] = S1[0.. MAXSTRLEN]; //T[0] = = S1[0] = = MAXSTRLEN return uncut; } // Concat

12 ②求子串SubString(&Sub, S, pos, len)
个字符开始长度为len的字符序列复制到串Sub中。 算法4.3如下： Status SubString (SString &Sub, SString S, int pos, int len) //用Sub返回串S的第pos个字符起长度为len的子串。 //其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)－pos+1。 if (pos < 1| | pos > S[0] | | len < 0 | | len > S[0]- pos + 1) return ERROE; Sub[1..len] = S[pos..pos + len - 1]; Sub[0] = len; return OK; } // SubString

13 ￡4.2.2 堆分配存储表示 （1）定义 堆分配存储结构：用一组地址连续的存储单元存储串值
的字符序列，但它们的存储空间是在程序执行过程中动态分 配而得。 （2）C语言描述 typedef struct { char *ch; //若是非空串,则按串长分配存储区, //否则ch为NULL int length; //串长度 } HString

14 （3）插入操作 算法思想：为串S重新分配大小等于串S和串T长度之和 的存储空间,然后进行串值复制。 Status StrInsert (HString &S, int pos, HString T) { //1≤pos≤StrLength(S) + 1。在串S的第pos个字符之前插入串T。 if (pos < 1 | | pos > S.length + 1) return ERROR; //pos不合法 if (T.length) { //T非空，则重新分配空间，插入T if (!(S.ch = (char *)realloc(S.ch, (S.length + T.length)*sizeof(char)))) exit (OVERFLOW); for (i = S.length－1; i >= pos－1;――i) //为插入T而腾出位置 S.ch[i + T.length] = S.ch[i]; S.ch[pos－1..pos + T.length－2] = T.ch[0..T.length－1]; //插入T S.length += T.length; } return OK; } // StrInsert

15 （4）ADT String的表示和实现 以下所示为只含最小操作子集的HString串类型的模块说明。 // 串的堆分配存储表示 typedef struct { char *ch; //若是非空串，则按串长分配存储区， //否则ch为NULL int length; //串长度 } HString; // 基本操作的函数原型说明 Status StrAssign (HString &T, char *chars); //生成一个其值等于串常量chars的串T int StrLength(HString S)； //返回S的元素个数，称为串的长度。 int StrCompare(HString S, HString T) //若S>T，则返回值>0；若S=T，则返回值＝0；若S<T，则返回值<0。 Status ClearString (HString &S)； //将S清为空串，并释放S所占空间。 Status Concat (HString &T, HString S1, HString S2)； //用T返回由S1和S2联接而成的新串。 HString SubString(HString S, int pos, int len); //1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos＋1 //返回串S的第pos个字符起长度为len的子串。

16 //-------------------基本操作的算法描述--------------------
Status StrAssign (HString &T, char *chars) { //生成一个其值等于串常量chars的串T if (T.ch) free (T.ch); //释放T原有空间 for (i = 0, c = chars; c; ++i, ++c); //求chars的长度i if (!i) { T.ch = NULL; T.length = 0; } else { if (!(T.ch = (char *) malloc (i*sizeof (char)))) exit (OVERFLOW); T.ch[0..i-1] = chars[0..i-1]; T.length = i; return OK; } // StrAssign

17 int StrLength(HString S) {
return S.length; } // StrLength int StrCompare (HString S, HString T) { //若S>T,则返回值>0;若S=T,则返回值＝0;若S<T,则返回值<0。 for (i = 0; i < S.length & & i < T.length; ++i) if (S.ch[i] != T.ch[i]) return S.ch[i]－T.ch[i]; return S.length－T.length; } // StrCompare

18 Status ClearString (HString &S) {
//将S清为空串，并释放S所占空间。 if (S.ch) { free (S.ch); S.ch = NULL; } S.length = 0; return OK; } // ClearString Status Concat (HString &T, HString S1, HString S2) { //用T返回由S1和S2联接而成的新串。 if (T.ch) free (S.ch); //释放旧空间 if (!(T.ch = (char *) malloc ((S1.length + S2.length) * sizeof (char)))) exit (OVERFLOW); T.ch[0..S1.length－1] = S1.ch[0..S1.length－1]; T.length = S1.length + S2.length; T.ch[S1.length..T.length－1] = S2.ch[0..S2.length－1]; return OK; } // Concat

19 HString SubString(HString S, int pos, int len) {
//用Sub返回串S的第pos个字符起长度为len的子串。 //其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos＋1 if (pos < 1| | pos > S.length| | len < 0| | len > S.length－pos + 1) return ERROR; if (Sub.ch) free (Sub.ch); //释放旧空间 if (!len) { //空子串 Sub.ch = NULL; Sub.length = 0; } else { Sub.ch = (char *) malloc (len * sizeof (char)); Sub.ch[0..len－1] = S.ch[pos－1..pos + len －2]; Sub.length = len; return OK; } // SubString

20 ￡4.3 串的链式存储结构 （串的块链存储表示） （1）定义 块链结构：采用链表方式存储串值，每个结点可以存放一
个字符，也可以存放多个字符。 （2）图形表示 head A B C I ^ (a) 结点大小为1的链表 head A B C D E F G H I # # # ^ (b) 结点大小为4的链表 图4.2 串值的链表存储方式

21 （3）C语言描述 #define CHUNKSIZE 80 //可由用户定义的块大小 typedef struct Chunk { char ch [CHUNKSIZE]; struct Chunk * next; } Chunk; typedef struct { Chunk * head, * tail; //串的头和尾指针 int curlen; //串的当前长度 } LString; （4）存储密度 显然，存储密度小（如结点大小为1），运算处理方便，然而， 存储占用量大。如果在串处理过程中需进行内、外存交换的话，则 会因为内外存交换操作过多而影响处理的总效率。

22 ￡4.4 串的应用—文本编辑 文本编辑的实质是修改字符数据的形式或格式。 文本串：把整个文本看成是一个字符串。页则是文本串的子
串，行又是页的子串。 例如：以下程序便可看成是一个文本串。 main ( ){ float a,b,max; scanf(“%f,%f”,&a,&b); if a>b max=a; else max=b; }; 输入到内存后如图4.3所示。 m a i n ( ) { f l o t , b x ; s c “ % ” & > = e } 图4.3 文本格式示例

23 为了管理文本串的页和行，在进入文本编辑的时候，编辑
程序先为文本串建立相应的页表和行表，即建立各子串的存储 映像。页表的每一项给出了页号和该页的起始行号。而行表的 每一项则指示每一行的行号、起始地址和该行子串的长度。 假设图4.3所示文本串只占一页，且起始行号为100，则该 文本串的行表如图4.4所示。 行号 起始地址 长度 图4.4 图4.3所示文本串的行表

24 几种文本编辑的操作： ①插入（文本行）：把新插入的行存到文本的末尾。并按行号次序 把新行的行号,起始位置及该行字符串的长度信息插入到行表的合适位置。 ②删除（文本行）：把被删除行的行号,起始位置及该行字符串的长 度信息从行表中删去即可（若存储空间较紧张时，应同时从内存中删去 该行）。若被删除的行是所在页的起始行,则还要修改页表中相应页的起 始行号（修改为下一行的行号）。 ③修改（文本行）： 1．若新行长≤原行长，则把新行字符串仍存于原行字符串的位 置，并修改行表中该行子串的长度信息即可。 2．若新行长≥原行长，则把新行字符串存于文本末尾（即为该 行重新分配存储空间）（并可删去文本中的原行），并修改 行表中该行的起始位置及行长信息。