1. 类似顺序表，用一个指针来指向最后一个字符。 描述如下：
#define MAXLEN 256 typedef struct { char ch[MAXLEN]; int len; 如图4.1所示。 ch a b c d e
} SeqString;
…
len
SeqString s; 串的长度：s.len+1
串名
起始地址
如图4.4所示
name length stradr s1 5
s2 …
3 …
…
… a
b
c
d
e
h
i
j
…
图 4.4 带长度的索引表
2. 末尾指针的索引表
索引项的结点类型为： typedef struct { char name[MAXNAME]; char *stradr; char *enadr; } ENode; 如图4.5所示：
•4.1.1 串的基本概念
定义： 是零个或多个字符组成的有限序列。 一般记为：s=“a1a2...an” (n≥0) 其中: s是串的名字; n是串中字符的个数, 称为串的长度 字符在串中的序号称为该字符在串中的位置
术语：
1. 子串 串中任意个连续的字符组成的子序列称为该串的子串。 2. 主串
包含子串的串相应地称为主串。
name enadr stradr
s1 s2 … … …
串名
起始地址
末尾地址
… a
b
c
d
e
h
i
j
…
图 4.5 带末尾指针的索引表
3. 带特征位的索引表
当一个串的存储空间不超过一个指针的存储空间，可以直接将该串存
在索引项的指针域，这样即节约了存储空间，又提高查找速度，但这
时要加一个特征位tag以指出指针域存放的是指针还是串。 索引项的结点类型为： typedef struct { char name[MAXNAME]; int tag; 特征位 union { char *stradr; name tag char value[4]; s1 0 }uval; s2 1 … … }TNode;
4 判断串相等算法 串相等是指两个串的长度及其对应位置的字符完全相同 两个串t和s相等时返回1 int strEqual(SeqString s,SeqString t) {int i=0; if(s.len!=t.len) return 0; else {for(i=0;i<s.len+1;i++) if(s.ch[i]!=t.ch[i]) return 0; return 1;} }
f
g
h
i
\0
…
图4.2 串 的 顺 序 存 储 方 式2
3. 设定长串存储空间 char s[MAXLEN+1] 用s[0]存放串的实际长度，串值存放在s[1]~s[MAXLEN]，字符的 序号和存储位置一致，应用更为方便。 如图所示：
0 1 2 3 4 5 6 7 8 … MAXLEN
5
a
b
c
d
5 串连接运算算法
SeqString strConcat(SeqString s,Seqstring t) {SeqString r; int i,j; for(i=0;i<=s.len;i++) r.ch[i]=s.ch[i]; for(j=0;j<=t.len;j++) r.ch[s.len+j+1]=t.ch[j]; r.len=i+j-1; return r; }
对串的存储方式取决于我们对串所进行的运算。
4.2.1 串的定长顺序存储
用一组地址连续的存储单元存储串值中的字符序列。 为每一个串变量预分配一个固定长度的存储区，如： #define MAXLEN 256 char s[MAXLEN]; 则串的最大长度不能超过256。 可用以下方法 如何标识实际长度 ？
(7) 删除子串操作：StrDelete(S, pos, len)
初始条件: 串S存在，1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果: 从串S中删除第pos个字符起长度为len
(8) 串复制操作：StrCopy(S, T) 初始条件: 串S 操作结果: 由串T复制得串S。 (10) 串比较操作：StrCompare(S, T)
4.3 串的堆存储结构
特点：
每个串值各自存储在一组地址连续的存储单元中。 但存储地址在程序执行过程中 动态分配 而得。
4.3.1 串名的存储映象
串名的存储映像是串名----串值内存分配对照表，也称为索引表。
表示形式有多种 常见的串名－串值存储映象索引表有如下几种：

1. 带串长度的索引表 索引项的结点类型为： typedef struct { char name[MAXNAME]； int length; 串长 char *stradr; } LNode;
9 子串替换算法 将串s中所有出现的字串s1替换成s2 SeqString RepString(SeqString s,SeqString s1,SeqString s2) {int i; i=Index(s,s1); while(i>=0) {DelString(&s,i,s1.len); InserString(&s,i,s2); i=index(s,s1); } return s; }
e
…
图4.3 串 的 定 长 顺 序 存 储
4.2.2 定长顺序串的基本操作
(以第一种方式作为串的存储结构) 请学生试着完成基本操作算法。可参考书P91~P94 列举几个算法如下：可略讲 1 串赋值操作 将一个数组t赋给串s void assign(SeqString*s,char t[]) {int i=0; while(t[i]!=‘\0’) {s->ch[i]=t[i]; i++;} s->len=i; }
3. 子串在主串中的位置 通常以子串的第一个字符在主串中的位置来表示。
4. 串相等 当两个串的长度相等, 并且每个对应位置的字符都相等， 称两个串是相等的。
4.1.2 串的基本运算
(1) 赋值操作：StrAsign(S, chars) 初始条件: chars是字符串常量。 操作结果: 生成一个值等于chars的串S。 (2) 求串长度：StrLength(S) 初始条件: 串S存在。 操作结果: 返回串S的长度，即串S中的元素个数。 (3) 联接函数：StrCat(S, T) 初始条件: 串S和T存在。 操作结果: 将串T的值连接在串S的后面。
起始地址 或串值
stradr/value
hij\0 …
… a
b
c
d
e
\0
…
图 4.6 带 特 征 位 的 索 引 表
4.3.2 堆存储结构
堆存储结构的基本思想是：在内存中开辟足够多的地址连续的存 储空间作为应用程序中所有串的可利用存储空间，称为堆空间。
3．教学重点：
①熟悉串的七种基本运算的定义及实现方法。 ②熟练掌握基本串匹配算法。
4．教学难点：
模式匹配算法。
第四章 串
4.1 串的定长及基本操作 4.2 串的定长顺序存储及基本操 4.3 串的堆存储结构
4.4 块链存储结构
4.1 串的定义
串是一种特殊的线性表。数据元素仅由一个字符组成。 1 保持线性表前驱、后继的关系； 2 对串整体进行操作。
8 主要讲述定位函数 算法思想如下： 首先将s1与t1进行比较，若不同，就将s2与t1进行比较，...，直到s的某 一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如 此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本 趟开始字符的下一个字符，即si-j+1，t返回到t1，继续开始下一趟的比较， 重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的 起始位置是i-j+1或i-t[0]，否则，匹配失败。
2串复制运算算法
(将一个串t赋给串s)
void strCopy(SeqString *s,SeqString t) {int i; for(i=0;i<=t.len;i++) s->ch[i]=t.ch[i]; s->len=t.len; } 3 求串长算法 int strLength(SeqString s) { return(s.len+1); }
2. 在串尾存储一个特殊字符作为串的终结符 比如C语言中用’\0’来表示串的结束。 char s[MAXLEN]; 这种存储方法不能直接得到串的长度，是用判断当前字符 是否是’\0’来确定串是否结束，从而求得串的长度。 如图所示：
0 1 2 3 4 5 6 7 8 … MAXLEN -1
a
b
c
d
e
算法实现如下： StrIndex(SeqString s, int pos, SeqString t) {int i, j; if (t.len==0) return(0); i=pos; j=0; while(i<s.len&&j<t.len) if(s.ch[i]==t.ch[j]) { i++; j++;} else { i=i-j+1; j=0;} if(j>=t.len) return(i-j); else return(0); } StrIndex(SeqString s, int pos, SeqString t) {int i, j,start; if (t.len==0) return(0); i=pos; j=0; start=pos; while(i<s.len&&j<t.len) if(s.ch[i]==t.ch[j]) { i++; j++;} else {start++; i=start; j=0;} if(j>=t.len) return(start); else return(0); }