敦黎 串、数组和广义表 程序设计—数据结构 基本概念及应用 目录 4.1串类型定义 4.2串的表示与实现 2 4.2.1定长顺序存储表示 4 …4 4.2.2堆分配存储表示... 4 4.2.3串的块链存储表示… 4.3串操作应用举例. 4.3.1文本编辑 5 5 4.3.2建立词索引表5 文档编号 完成时间 完成人张昱 修改时间 第1页
程序设计——数据结构 串、数组和广义表 基本概念及应用 文档编号 文 档 编号 完 成 人 完 成 人 张 昱 张 昱 完成时间 完 成 时间 修改时间 修 改 时间 第 1 页 第 1 页 目 录 4.1 串类型定义...............................................................................................................2 4.2 串的表示与实现........................................................................................................4 4.2.1 定长顺序存储表示...........................................................................................4 4.2.2 堆分配存储表示..............................................................................................4 4.2.3 串的块链存储表示...........................................................................................5 4.3 串操作应用举例........................................................................................................5 4.3.1 文本编辑.........................................................................................................5 4.3.2 建立词索引表..................................................................................................5
教案 串、数组和广义表 程序设计—数据结构 基本概念及应用 第4章串 4.1串类型定义 1、串与一般线性表的关系 串是特殊的线性表，这种特殊性表现在： ·串的元素是字符型 ·串的操作不仅仅是针对元素个体，还包括整体的操作，如串的复制、联接等。 2、一些概念 串：由零个或多个字符组成的有限序列： 串的长度：串中字符的数目： 空串：零个字符的串： 子串：串中任意个连续字符组成的子序列： 主串：包含子串的串： 字符在串中的位置：字符在序列中的序号： 子串在主串中的位置：子串的第一个字符在主串中的位置： 两个串的相等：两个串的值相等，即串长相等，且各对应位置的字符都相等： 3、串值的表示 用一对单引号括起来（一些程序设计语言用双引号将传串值括起来）。 空格串与空串的区别：空格串是指由一个或多个空格组成的串：空串是指包含零个字符的 串。 4、串的抽象数据类型定义 ADT String 数据对象：D={ala∈CharacterSet,i=l,2,…,n,n≥0} 数据关系：R={R1},R1={a-l,a>a1,a∈D,=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,则返回值=O:若串S<T, 则返回值<0 StrLength(S) 初始条件：串S己存在 操作结果：返回串S中数据元素的个数 文档编号 完成时间 完成人张昱 修改时间 第2页
程序设计——数据结构 串、数组和广义表 基本概念及应用 文档编号 文 档 编号 完 成 人 完 成 人 张 昱 张 昱 完成时间 完 成 时间 修改时间 修 改 时间 第 2 页 第 2 页 第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<T， 则返回值<0 StrLength(S) 初始条件：串 S 已存在 操作结果：返回串 S 中数据元素的个数
敦黎 串、数组和广义表 程序设计—数据结构 基本概念及应用 ClearString(&S) 初始条件：串S已存在 操作结果：将串S清为空串 Concat(&T,S1,S2) 初始条件：串S1和S2存在 操作结果：用T返回由S1和S2联接而成的新串 SubString(&Sub,S,pos,len) 初始条件：串S存在，l≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+l 操作结果：用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+l 操作结果：从串S中删除第pos个字符起长度为len的子串 DestroyString(&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、定位函数ndex(S,T,pos)的实现 利用求串长函数、求子串函数和比较函数。 参数：S主串，T子串，pos查找的起始位置 返回值：T在S中第pos个字符后第一次出现的位置 步骤： I)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)return0;/体未找到*/ 文档编号 完成时间 完成人张昱 修改时间 第3页
程序设计——数据结构 串、数组和广义表 基本概念及应用 文档编号 文 档 编号 完 成 人 完 成 人 张 昱 张 昱 完成时间 完 成 时间 修改时间 修 改 时间 第 3 页 第 3 页 ClearString(&S) 初始条件：串 S 已存在 操作结果：将串 S 清为空串 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 typedef unsigned char SString[MAXSTRLEN+l,/体0号单元存放串的长度*/ 串长表示： 1)利用下标为0的分量存放串长 局限性：对于MAXSTRLEN超过255的串，此存储结构不适合，需要修改。 2)串值后加入一个不计入串长的结束标记字符，如C语言中的0 不足：串长是隐含的，需要遍历整个串才能得出。 2、串联接Concat(&TS1,S2) ,是定长存储，联接后T的串长为S1和S2串长之和，该长度可能会超出MAXSTRLEN ∴分情况处理，超出部分要“截断” S1[0]>=MAXSTRLEN: T[1..MAXSTRLEN]=S1[1..MAXSTRLEN]; T[O]=MAXSTRLEN; S2全被截去 S1[O]MAXSTRLEN: T[1.S1[0]=s1[1.S1[0 TIS1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; TIO]=MAXSTRLEN: /S2部分截断 S1[0]+S2[0]0&&len>=O&&pos<=StrLength(S)-len+1 2)串的复制：Sub[l.len]=S[pos.-pos+len-l;Subf0=len; 4、评价 ·串长超出最大长度，约定采用截尾法 ·串长过小，则串空间浪费较大 4.2.2堆分配存储表示 1、类型定义 typedef struct{ char *ch; 体约定空串时，ch为NULL*/ int length; }HString: 串本身利用动态分配函数分配一块连续的串值存储空间。 借助堆结构的两个域可以在串名和串值之间建立对应关系一一串名的存储映像。 2、实现说明 ·基于复制： 利用malloc(O分配一块足够的空间，再按要求完成复制任务：如StrAssign(&T,chars)), 文档编号 完成时间 完成人张昱 修改时间 第4页
程序设计——数据结构 串、数组和广义表 基本概念及应用 文档编号 文 档 编号 完 成 人 完 成 人 张 昱 张 昱 完成时间 完 成 时间 修改时间 修 改 时间 第 4 页 第 4 页 4.2 串的表示与实现 4.2.1 定长顺序存储表示 1、类型定义 #define MAXSTRLEN 255 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] 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,TD, ·基于链接 建立串名和串值的映射关系，StrAssign(&T,chars) 4.2.3串的块链存储表示 1、块链结构的定义 #define CHUNKSIZE 80 typedef struct Chunk 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页
程序设计——数据结构 串、数组和广义表 基本概念及应用 文档编号 文 档 编号 完 成 人 完 成 人 张 昱 张 昱 完成时间 完 成 时间 修改时间 修 改 时间 第 5 页 第 5 页 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{ 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 建立词索引表 算法思想：词表——须提取的关键词集合
