41 串的抽象数据类型的定义.ppt

void StrInsert (Hstring S, int pos, HString T) { // 1≤pos≤StrLength(S)＋1。在串 S 的 // 第 pos 个字符之前插入串 T slen=S.length; tlen=T.length; // 取得S和T的串长 if(pos 1||pos slen+1) return; // 插入位置不合法 S1.ch = new char[slen] ; // S1作为辅助串 S1.ch[0..slen-1] = S.ch[0..slen-1]; // 暂存 S if (tlen0) // T 非空，则为S重新分配空间并插入T { } } // StrInsert _HSq …… S.ch = new char[slen + tlen ]; // 为 S 重新分配空间 for ( i=0, k=0; ipos-1; i++) S.ch[k++] = S1.ch[i]; // 保留插入位置之前的子串 for ( i=0; itlen; i++) S.ch[k++] = T.ch[i]; // 插入T for ( i=pos; islen; i++ ) S.ch[k++] = S1.ch[i]; // 复制插入位置之后的子串 S.length = slen+tlen; delete S1.ch; 三、串的块链存储表示 也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。 存储密度 = 数据元素所占存储位 实际分配的存储位 #define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString; 例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。 实际应用时，可以根据问题所需来设置结点的大小。 这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。 4.3 串的模式匹配算法 * * 4.1 串的抽象数据类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 字符串： 简称串，是特殊的线性表，其特殊性主要在于表中的每个元素是一个字符，以及由此而要求的一些特殊操作。 长度：一个串中包括的字符个数。长度为零的串称为空串。 4.1 串的抽象数据类型的定义 子串：字符串s1中任意个连续的字符组成的子序列s2被称为是s1的子串，而称s1是s2的主串。 位置：子串在主串中的位置是以子串的第一个字符在主串中的字符序号(下标+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) 基本操作：