例：用“堆”实现串插入操作(教材P75)
Status StrInsert ( HString &S, int pos, HString T ){
//在串S的第pos个字符之前（包括尾部）插入串T
if (pos<1||pos>S.length+1) return ERROR; //pos不合法则告警if(T.length){ //只要串T不空，就需要重新分配S空间，以便插入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而腾出pos之后的位置
S.ch[i+T.length] = S.ch[i]; //从S的pos位置起全部字符均后移S.ch[pos-1…pos+T.length-2] = T.ch[0…T.length-1]; //插入T，略/0S.length + = T.length; //刷新S串长度
}return OK;
}//StrInsert
附：堆分配存储表示
Status StrAssign(HString &T, char *chars){
if (T.ch) free(T.ch);
for (i=0, c=chars; c; ++i, ++c); //求串长度if (!i) {T.ch = NULL; T.length = 0;}else{直到终值为“假”停止，串尾特征是‘/0?＝NUL=0if (!(T.ch = (char*)malloc(i*sizeof(char))))exit(OVERFLOW);T.ch[0..i-1] = chars[0..i-1];T.length =i;}
Return OK;
指针变量C也可以自增！意即每次后移一个数据单元。}//StrAssign
链式存储特点：用链表存储串值，易插入和删除。
法1：链表结点（数据域）大小取1
head
A?B?C?I NULL法2：链表结点（数据域）大小取n(例如n=4)
head
A B C D ?E F G H ?I # # # NULL讨论：法1存储密度为1/2；法2存储密度为9/15=3/5；显然，若数据元素很多，用法2存储更优—称为块链结构
块链类型定义：
#define CHUNKSIZE 80 //可由用户定义的块大小typedef struct Chunk { //首先定义结点类型
char ch [ CHUNKSIZE ]; //结点中的数据域struct Chunk * next ; //结点中的指针域
}Chunk;
typedef struct { //其次定义用链式存储的串类型
Chunk *head; //头指针Chunk *tail; //尾指针int curLen; //结点个数
} Lstring; //串类型只用一次，前面可以不加Lstring
例略
再次强调：串与线性表的运算有所不同，是以?串的整体?作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。
这类操作中均涉及到定位问题，称为串的模式匹配。它是串处理系统中最重要的操作之一。
4.3 串的模式匹配算法
模式匹配(Pattern Matching) 即子串定位运算（Index函数）。
算法目的：确定主串中所含子串第一次出现的位置（定位）
——即如何实现Index(S,T,pos)函数（见教材P71）初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(s)操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。注：S称为被匹配的串，T称为模式串。若S包含串T，则称“匹配成功”。否则称“匹配不成功”。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课件- 河南大学精品课程网 - 图文 -(3)在线全文阅读。
相关推荐：