第四章 串.

Presentation on theme: "第四章 串."— Presentation transcript:

1 第四章 串

2 4.1 串的抽象数据类型的定义 4.2 串的表示和实现 4.3 文本编辑 —串的应用举例

3 数据关系： ADT String { D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 }
串是有限长的字符序列，由一对双引号相括，如:  a string  数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n }

4 基本操作： StrAssign (&T, chars) DestroyString(&S) StrCopy (&T, S) StrLength(S) StrEmpty (S) Concat (&T, S1, S2) StrCompare (S, T)

5 SubString (&Sub, S, pos, len)
ClearString (&S) Index (S, T, pos) Replace (&S, T, V) StrInsert (&S, pos, T) StrDelete (&S, pos, len) } ADT String

6 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 初始条件：串 S 存在。
StrAssign (&T, chars) (串赋值) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (&T, S) (串复制) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。

7 初始条件：串 S 存在。 操作结果：若 S 为空串，则返回 TRUE, 否则返回 FALSE。(为空串) 初始条件：串 S 存在。
StrEmpty (S) (判空) 初始条件：串 S 存在。 操作结果：若 S 为空串，则返回 TRUE, 否则返回 FALSE。(为空串) StrLength (S) (求长度) 初始条件：串 S 存在。 操作结果：返回串 S 中字符的个数。

8 例如：StrCompare( data ,  state ) < 0
StrCompare (S, T) (串比较) 初始条件：串 S 和 T 都存在。 操作结果：由串 S 小于或等于或大于串 T 分别返回小于或等于或大于 0 的值 。 例如：StrCompare( data ,  state ) < 0 StrCompare( cat ,  case ) > 0

9 Concat (&T, S1, S2) (串联接) 初始条件：串 S1 和 S2 存在。 操作结果： T 为由串 S1 和串 S2 联接
所得的串。 例如： Concat( T, man, kind) 求得 T = mankind Concat( T, kind, man) 求得 T = kindman

10 (求子串) 初始条件： 操作结果： 以 Sub 返回串 S 中第 pos 个字符起 串 S 存在，1≤pos≤StrLength(S)
SubString (&Sub, S, pos, len) (求子串) 初始条件： 操作结果： 以 Sub 返回串 S 中第 pos 个字符起 长度为 len 的子串。 串 S 存在，1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。

11 子串为“串”中的一个字符子序列 例如： SubString( sub, commander , 4, 3) 求得 sub = man  SubString( sub, commander  , 1, 9) 求得 sub = commander  SubString( sub, commander , 9, 1) 求得 sub = r 

12 SubString(sub, commander, 4, 7)
SubString(sub, beijing, 7, 2) = ? sub = ? 起始位置和子串长度之间存在约束关系 SubString(student, 5, 0) =  长度为 0 的子串为“合法”串

13 串 S 和 T 存在，且 T 是非空串， 1≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同的
Index ( S, T, pos) (定位函数) 初始条件： 串 S 和 T 存在，且 T 是非空串， ≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同的 子串，则返回它在主串 S 中第 pos 个字符之后第一次出现的位置; 否则函数值为0。

14 “子串在主串中的位置”意指子串 中的第一个字符在主串中的“位序” 。 假设 S = abcaabcaaabc , T = bca  Index(S, T, 1) = 2; Index(S, T, 3) = 6; Index(S, T, 8) = 0;

15 初始条件： 串 S, T 和 V 均已存在， 且 T 是非空串。 操作结果： 用 V 替换主串 S 中出现的所有与
Replace ( S, T, V) (串置换) 初始条件： 串 S, T 和 V 均已存在， 且 T 是非空串。 操作结果： 用 V 替换主串 S 中出现的所有与 （模式串）T 相等的不重叠的子串。

16 例如： 假设 S = abcaabcaaabca, T = bca  bca bca bca 若 V = x , 则经置换后得到 S = axaxaax  若 V = bc , 则经置换后得到 S = abcabcaabc

17 StrInsert (&S, pos, T) (插入)
1≤pos≤StrLength(S)＋1。 操作结果：在串 S 的第 pos 个字符之前 插入串T。 例如：S = chater ，T = rac ， 则执行 StrInsert(S, 4, T) 之后得到 S = character 

18 StrDelete (&S, pos, len) (删除)
初始条件： 串 S 存在，且 1≤pos≤StrLength(S)-len+1。 操作结果： 从串 S 中删除第 pos 个字符起 长度为len的子串。

19 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。
在上述抽象数据类型定义的13种操作中， 串赋值 StrAssign、串复制 Strcopy、 串比较 StrCompare、求串长 StrLength、 串联接 Concat 以及求子串 SubString 等六种操作构成串类型的最小操作子集。

20 ? 利用串比较、求串长和求子串等操作实现定位函数 Index( S, T, pos )算法的基本思想为：
StrCompare(SubString(S, i, StrLength(T)), T ) pos S 串 T 串 i T 串 i T 串 i T 串 i 或者 = n-m+1

21 int Index (String S, String T, int pos) {
// T为非空串。若主串S中第pos个字符之后存在与 T相等的子串， // 则返回第一个这样的子串在S中的 位置，否则返回0 if (pos > 0) { } // if return 0; // S中不存在与T相等的子串 } // Index n = StrLength(S); m = StrLength(T); i = pos; while ( i <= n-m+1) { } // while SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) ++i ; else return i ;

22 news 串 实现置换函数 Replace( S, T, V)算法的基本思想为： pos = i+m pos= n-tn+1 pos i
sub T 串 V 串 tn news 串 sub V 串

23 void replace(String& S, String T, String V) {
} n=StrLength(S); m=StrLength(T); pos = 1; StrAssign(news, NullStr); i=1; while ( pos <= n-m+1 && i) { i=Index(S, T, pos); if (i!=0) { SubString(sub, S, pos, i-pos); // 不置换子串 Concat(news, news, sub, V); pos = i+m; }//if }//while SubString(sub, S, pos, n-pos+1); // 剩余串 Concat( S, news, sub );

24 串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 而在串的基本操作中，通常以“串的整体”作为操作对象。

25 在早期的程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。之后在多数非数值处理的程序中，串均以变量的形式出现，因此作为一个数据类型也就存在一个存储表示和实现的问题。

26 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示

27 char str[10]; 用一组地址连续的存储单元存储串值。 例如，在 C 语言中可以定义串为
这表示，为串变量 str 分配了一个固定长度为 10 的数组空间，而 str 的实际长度可以在这个定义范围内随意，但最大长度不得超过 9 (串的结束符\0也占一个字符的空间，但它不属串值本身)。

28 void Concat( char T[ ], char S1[ ], char S2[ ] )
{ // T 串为由 S2 串联接到 S1 串构成的新串 j=0; k=0; while ( S1[j] != \0 ) T[k++] = S1[j++]; // 复制串S1 j = 0; while ( S2[j] != \0 ) T[k++] = S2[j++]; // 接着复制串S2 T[k] = \0; // 置结果串T的结束标志 } // Concat

29 bool SubString_Sq(char Sub[], char S[],int pos, int len){
// 以 Sub 返回串 S 中第 pos 个字符起长度为 len 的子串 if (pos<1) return FALSE; }//SubString_Sq i=0; while (i<pos-1 && S[i]!= \0  ) i++; if ( i<pos-1 || S[i]==  \0  ) return FALSE; else { k=0; while ( k< len && S[i] !=  \0  ) Sub[k++] = S[i++]; if ( k<len ) return FALSE; else { Sub[k] =  \0  ; return TRUE; } }//else

30 int Index (char S[ ], char T[ ], int pos) {
// T为非空串。若主串S中第 pos 个字符之后存在与 T相等的子串， // 则返回第一个这样的子串在S中的 位置，否则返回0 if (pos > 0) { } // if return 0; // S中不存在与T相等的子串 } // Index i = pos-1; j = 0; while ( S[i+j] != \0 && T[j] != \0 ) { if ( S[i+j] == T[j] ) j ++; // 继续比较后继字符 else { i ++; j = 0; } // 重新开始新的一轮比较 if ( T[j] == \0 ) return (i+1); // 匹配成功 else return 0; // 不存在和串T相同的子串

31 i i i i 算法的基本思想: S 串 T 串 pos n-m+1 具体实现时的两种情况: j j S 串 j j j T 串 T 串
或者继续重复新一轮匹配过程，如此反复直至 (i+j)>Strlength(S)表明匹配不成功 具体实现时的两种情况: 比较不等，i增1，j回退至T串的起始位置 i i i j j S 串 j j j T 串 T 串 开始新一轮的匹配直至匹配成功此时 j>Strlength(T) T 串

32 C 语言中提供的串类型就是以这种存储方式实现的。
仍以一组地址连续的存储空间存储串值，只是串变量的存储空间是在程序执行过程中利用 new 进行动态分配得到的。程序中出现的所有串变量的值都存储在一个称之为“堆”的共享空间中。此时的串操作仍基于“字符序列的复制”进行。 C 语言中提供的串类型就是以这种存储方式实现的。

33 void Concat( char *T, char *S1, char *S2 ) {
// T 串为由 S2 串联接到 S1 串构成的新串 slen1 = StrLength(S1); slen2 = StrLength(S2); T = new char[slen1+slen2]; j=0; k=0; while ( S1[j] != \0 ) T[k++] = S1[j++]; //复制串S1 j = 0; while ( S2[j] != \0 ) T[k++] = S2[j++]; // 接着复制串S2 T[k] = \0; // 置结果串T的结束标志 } // Concat

34 bool StrInsert (char* S, int pos, char* T) {
// 在串 S 的第 pos(1≤pos≤StrLength(S)＋1) 个字符 // 之前插入串T slen=StrLength(S); tlen=StrLength(T); // 求串长 char S1 [slen +1] ; // 设S1为辅助串空间 if (pos < 1 || pos > slen+1) return FALSE; // 插入位置不合法; if (tlen>0) { } } // StrInsert // T非空，则为S重新分配空间并插入T

35 i=0; while ((S1[i]=S[i]) != \0) i++; // 暂存串S S = new char[slen + tlen +1]; // 重新分配空间 for ( i=0, k=0; i<pos-1; i++) S[k++] = S1[i]; // 保留插入位置之前的子串 j = 0; while ( T[j]!= \0) S[k++] = T[j++]; // 插入T while ( S1[i] != \0) S[k++] = S1[i++]; // 复制插入位置之后的子串 S[k] = \0; // 置串S的结束标志

36 和线性表类似，串也有链式存储结构，即以链表存储串值。由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储串值时，通常一个结点中存放的不是一个字符，而是一个“子串” 。
数据元素所占存储位 存储密度 = 实际分配的存储位

37 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next;
#define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链式存储映象 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString;

38 实际应用时，结点的大小可以根据问题所需来设置。
例如，在编辑系统中，可以将整个文本编辑区看成是一个“串” ，每一行是一个子串。采用链表结构，可设结点大小为一行中的字符个数。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。

39 正文编辑程序是一个面向用户的系统服务程序，广泛用于源程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色等。
正文编辑的实质是修改字符数据的形式或格式。虽然各种正文编辑程序的功能强弱不同，但其基本功能大致相同，一般都包括串的查找、插入、删除和修改等基本操作。

40 为了编辑方便起见，用户可以通过换页符和换行符将正文划分为若干页和若干行(或者直接划分为若干行)。在编辑程序中，则可将整个正文看成是一个“正文串”，页是正文串的子串，而行则是页的子串。
为了管理正文串中的页和行，编辑程序要为正文串建立相应的页表和行表，页表的每一项列出页号和该页的起始行号，行表的每一项则指示每一行的行号、起始地址和该行子串的长度。

41 main(){ float a,b,max; scanf(%f,%f,&a,&b); if a>b max=a;
else max=b; }; (a>b) max=a; m a i n ( ) { ↙ f l o t , b x ; s c  % & > = e } i f ( a > b ) m a x = a ; 284

42 假设该正文串只占一页，起始行号为100，起始的存储地址为200,则其行表如下:
起始地址 长度 100 200 8 102 208 17 104 225 24 105 249 106 266 15 108 281 3 284 19 2

43 在正文编辑程序中设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。
如果在某行内插入或删除若干字符，则要修改行表中该行的长度，若该行长度因插入而超出了原分配给它的存储空间，则要为该行重新分配存储空间，并修改该行的起始位置。

44 1. 熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。
2. 了解串的各种存储结构的特点及其适用场合。