数据结构课件chap004章节幻灯片.ppt

typedef struct { char *ch; // 若是非空串，则按串长分配存储区， // 否则ch为NULL int length; // 串长度 } HString; 二、串的堆分配存储表示 通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。 C语言中的串以一个空字符为结束符， 串长是一个隐含值。 这类串操作实现的算法为： 先为新生成的串分配一个存储空间，然后 进行串值的复制。 Status Concat(HString T, HString S1, HString S2) { // 用T返回由S1和S2联接而成的新串 if (T.ch) free(T.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 Status SubString(HString Sub, HString S, int pos, int len) { // 用Sub返回串S的第pos个字符起长度为len的子串 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 { } // 完整子串 return OK; } // SubString … … Sub.ch = (char *)malloc(len*sizeof(char)); Sub.ch[0..len-1] = S[pos-1..pos+len-2]; Sub.length = len; 第四章 串 4.1 串的抽象数据类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.1 串的抽象数据类型的定义如下： ADT String { 数据对象： D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai ∈D, i=2,...,n } 串是有限长的字符序列，由一对单引号相括，如: ?a string? 基本操作： StrAssign (T, chars) StrCopy (T, S) DestroyString(S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (T, S1, S2) SubString (Sub, S, pos, len) Index (S, T, pos) Replace (S, T, V) StrInsert (S, pos, T) StrDelete (S, pos, len) ClearString (S) } ADT String StrAssign (T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。  StrCopy (T, S) 初始条件：串 S 存在。