数据结构详细教案 - 串

数据结构教案

第四章 串

数据结构教案 第4章 串

目 录

4.1 串类型定义 ............................................................................................................................. 2 4.2 串的表示与实现 ..................................................................................................................... 3

4.2.1 定长顺序存储表示 ...................................................................................................... 3 4.2.2 堆分配存储表示 .......................................................................................................... 4 4.2.3 串的块链存储表示 ...................................................................................................... 4 4.3 串操作应用举例 ..................................................................................................................... 5

4.3.1 文本编辑 ...................................................................................................................... 5 4.3.2 建立词索引表 .............................................................................................................. 5

1

数据结构教案 第4章 串

第4章 串

4.1 串类型定义

1、串与一般线性表的关系

串是特殊的线性表，这种特殊性表现在： ·串的元素是字符型

·串的操作不仅仅是针对元素个体，还包括整体的操作，如串的复制、联接等。 2、一些概念

串：由零个或多个字符组成的有限序列； 串的长度：串中字符的数目； 空串：零个字符的串；

子串：串中任意个连续字符组成的子序列； 主串：包含子串的串；

字符在串中的位置：字符在序列中的序号；

子串在主串中的位置：子串的第一个字符在主串中的位置；

两个串的相等：两个串的值相等，即串长相等，且各对应位置的字符都相等； 3、串值的表示

用一对单引号括起来(一些程序设计语言用双引号将传串值括起来)。

空格串与空串的区别：空格串是指由一个或多个空格组成的串；空串是指包含零个字符的

串。 4、串的抽象数据类型定义

ADT String{

数据对象：D={ai|ai∈CharacterSet, i=1,2,?,n, n≥0} 数据关系：R={R1},R1={|ai-1,ai∈D, i=2,3,?,n } 基本操作：

StrAssign(&T, chars)

初始条件：chars是字符串常量

操作结果：生成一个其值等于chars的串T StrCopy(&T, S)

初始条件：串S存在

操作结果：由串S复制得串T StrEmpty(S)

初始条件：串S存在

操作结果：若S为空串，则返回TRUE，否则返回FALSE StrCompare(S, T)

初始条件：串S和T存在

操作结果：若串S>T，则返回值>0；若串S=T，则返回值=0；若串S

则返回值<0

StrLength(S)

初始条件：串S已存在

操作结果：返回串S中数据元素的个数 ClearString(&S)

初始条件：串S已存在 操作结果：将串S清为空串

2

数据结构教案 第4章 串

Concat(&T, S1, S2)

初始条件：串S1和S2存在

操作结果：用T返回由S1和S2联接而成的新串 SubString(&Sub, S, pos, len)

初始条件：串S存在，1 ≤ pos ≤ StrLength(S)且0 ≤ len ≤ StrLength(S)-pos+1 操作结果：用Sub返回串S的第pos个字符起长度为len的子串 Index(S, T, pos)

初始条件：串S和T存在，T非空，1 ≤ pos ≤ StrLength(S)

操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中

第pos个字符之后第一次出现的位置；否则函数值为0

Replace(&S, T, V)

初始条件：串S，T和V存在，T是非空串

操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串 StrInsert(&S, pos, T)

初始条件：串S和T存在，1 ≤ pos ≤ StrLength(S)+1 操作结果：在串S的第pos个字符之前插入串T StrDelete(&S, pos, len)

初始条件：串S存在，1 ≤ pos ≤ StrLength(S)-len+1

操作结果：从串S中删除第pos个字符起长度为len的子串 DestroyString(&S))

初始条件：串S存在 操作结果：串S被销毁

}ADT String

5、串的基本操作

1) 赋值操作 StrAssign(&T, chars) 2) 比较函数 StrCompare(T, S) 3) 求串长函数 StrLength(S) 4) 联接函数 Concat(&T, S1, S2)

5) 求子串函数 SubString(&Sub, S, pos, len) 其他操作可在此最小操作集上实现。 6、定位函数Index(S, T, pos)的实现

利用求串长函数、求子串函数和比较函数。 参数：S主串, T子串, pos查找的起始位置

返回值：T在S中第pos个字符后第一次出现的位置 步骤： 1) pos的合法性判断：

if ( pos<=0 ) return 0;

2) n=StrLength(S); m=StrLength(T); 3) for ( i = pos; i <=n-m+1; i ++ ){

SubString(sub, S, i, m)

if ( StrCompare(sub, T)==0) return i; }

4) return 0; /* 未找到 */

4.2 串的表示与实现

4.2.1 定长顺序存储表示 1、类型定义

#define MAXSTRLEN 255

3

数据结构教案 第4章 串

typedef unsigned char SString[MAXSTRLEN+1]; /* 0号单元存放串的长度 */ 串长表示：

1） 利用下标为0的分量存放串长

局限性：对于MAXSTRLEN超过255的串，此存储结构不适合，需要修改。 2） 串值后加入一个不计入串长的结束标记字符，如C语言中的’\\0’

不足：串长是隐含的，需要遍历整个串才能得出。 2、串联接Concat(&T, S1, S2)

∵是定长存储，联接后T的串长为S1和S2串长之和，该长度可能会超出MAXSTRLEN ∴分情况处理，超出部分要“截断” S1[0]>=MAXSTRLEN： T[1..MAXSTRLEN]=S1[1..MAXSTRLEN];

T[0] = MAXSTRLEN; //S2全被截去

S1[0] MAXSTRLEN：

T[1..S1[0]]=S1[1..S1[0]];

T[S1[0]+1.. MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; T[0]=MAXSTRLEN; //S2部分截断

S1[0]+S2[0] <= MAXSTRLEN： T[1..S1[0]]=S1[1..S1[0]];

T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]]; T[0]=S1[0]+S2[0];

本做法基于复制，可进一步考虑利用原S1空间时的处理方法。 3、求子串SubString(&Sub, S, pos, len)

1） 合法的pos和len：pos>0 && len>=0 && pos<=StrLength(S)-len+1 2） 串的复制：Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; 4、评价

·串长超出最大长度，约定采用截尾法 ·串长过小，则串空间浪费较大 4.2.2 堆分配存储表示

1、类型定义

typedef struct {

char *ch; /* 约定空串时，ch 为NULL */ int length; }HString;

串本身利用动态分配函数分配一块连续的串值存储空间。

借助堆结构的两个域可以在串名和串值之间建立对应关系——串名的存储映像。 2、实现说明

·基于复制：

利用malloc()分配一块足够的空间，再按要求完成复制任务；如StrAssign(&T,chars), Concat(&T, S1, S2), SubString(&Sub, S, pos, len)

利用realloc()重新分配空间，如StrInsert(&S, pos, T), ·基于链接

建立串名和串值的映射关系，StrAssign(&T, chars) 4.2.3 串的块链存储表示 1、块链结构的定义

#define CHUNKSIZE 80 typedef struct Chunk{

4

数据结构教案 第4章 串

char ch[CHUNKSIZE]; struct Chunk *next; }Chunk;

typedef struct{

Chunk *head, *tail; int curlen; }LString;

引入尾指针目的：便于进行联接操作。

存储密度=（串值所占的存储位）/（实际分配的存储位） 存储密度小，则运算处理方便（串尾的无效字符的处理），但存储占用量大（内、外存交换操作多）；

串的字符集小，则字符的机内编码短，影响串值的存储方式的选取。 2、顺序映像和块链映像的缺点

顺序映像： 1）空间利用率低；

2）空间不可扩充，使串的某些操作（联接、置换）受到限制； 3）插入、删除的移动。

块链映像： 1）存储密度较低；

2）块链使串的操作复杂化。

4.3 串操作应用举例

4.3.1 文本编辑

处理规则：行插入/删除，页插入/删除，??

算法思想：定义页表、行表(行号，起始地址，长度)， 4.3.2 建立词索引表

算法思想：词表——须提取的关键词集合

5

本文来源：https://www.bwwdw.com/article/umb5.html