中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第4章 串

数据结构 串 第四章串 主讲：张显 知识点：串的定义、表示与实现， yuzhang@ustc.edu 定位函数 0551-3603804 说明：KMP算法移至 课中讲 1/15 215 第四章串 4.1串类型的定义 4.1串类型的定义 。串 4.2电的表示和实现 C中的字符事：一对双引号拾起的孝将序列，如abcd ef 一散地，市是由章个成多个字将恒成的有限序列 4.3电的模式匹配算法 一些额客：率的长度、空率、子串、主串、 4.4电操作应用举例 牛将/于率在串/主率中的位置 如：S=“Data Structure”,S为串名，"Data Structure”为串值， 长度为14：“at归S女“为主率S的子率，它在5中的位置为2 麻两个亭是相擦的，业且枚幽这两个率的值湘普。 空格率v5.空率0 是钟弹的战性表1)元素夹型为字符： 2)操作对桌：个（牛将）与量于◆) 3到15 415 圆 4.1串类型的定义-ADT String 4.1串类型的定义-操作间的关系 。ADT String事的整体操作 ■ 申的最小操作子集 ·减值StrAssign(S,“Data Structure) 赋值、求奉长、比校、联接、取于事 ,复StrCopy(T,S/T<=s,T为-Data Structure ■定位函数Index(S,Tpos】 ,比装StrCompare(s,T) ,t楼Concat(T,“Data“,“Structure)/T为-DataStructure (p)(P():1pos: 。k于◆SubString(sub,5,Z,5)/∥sub为“atas while(i<=n-m+1){ SubString(sub,S,i,m); 。于◆在主◆中的发位Index(S,“a”,3)//4 if (StrCompare(sub,T)!=0)++; 。于事置换Replace(S,"a“,b)/∥S为-Dbt地Structure else return//返回子率在生率中的位置 }/while ,于◆插入StrInsert(S,3,“aha")/“Daahata Structure” 30 ,于率测膝StrDelete(S,3,5)/∥"Daructure" rn 0; /S中不存在与T帽等的子 回 }/∥Index 5/15 6/15 回 1

1 1/15 数据结构——串 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/15 知识点：串的定义、表示与实现， 定位函数 说明：KMP算法移至 课中讲 第四章 串 3/15 第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 4/15 4.1 串类型的定义 „ 串 C中的字符串：一对双引号括起的字符序列，如“abcd ef” 一般地，串是由零个或多个字符组成的有限序列 一些概念：串的长度、空串、子串、主串、 字符/子串在串/主串中的位置 如：S=“Data Structure”，S为串名，“Data Structure”为串值， 长度为14；“ata Str”为主串S的子串，它在S中的位置为2 称两个串是相等的，当且仅当这两个串的值相等。 空格串 vs. 空串Ø 是特殊的线性表 1)元素类型为字符； 2)操作对象：个体(字符)与整体(子串) 5/15 4.1 串类型的定义-ADT String „ ADT String 串的整体操作 „ 赋值 StrAssign(S, “Data Structure”) „ 复制 StrCopy(T, S) // T0){ // pos的合法性 n = StrLength(S); m = StrLength(T); i = pos; while( i<=n-m+1) { SubString(sub, S, i, m); if (StrCompare(sub, T) != 0) ++i; else return i; // 返回子串在主串中的位置 } // while } // if return 0; // S中不存在与T相等的子串 } // Index

4.2串的表示和实现-定长顺序存储 4.2串的表示和实现-定长顺序存储 ■定长顺序在储表示一顺序映像 申联接Concat(&T,S1,S2) ■类型定义 .S1[0]>=MAXSTRLEN typedef unsigned char SString[MAXSTRLEN+1]; T[1..MAXSTRLEN]=S1[1..MAXSTRLEN]; 约定：1)下标为0的分量存放事的长度 TO)=MAXSTRLE(;/S2全被去 或2)事值后加入一个不计入亭长的站来标记孝 S1[0]MAXSTRLEN T151[oj=s11.s10] 将，如C语言中的”0 T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; ·申联接Concat(&T,S1,s2) T[O]=MAXSTRLEN; /52蒂分檬解 华是定长存铺，联换后T的申长为S1和52申长之和，该长度 S1[0]+S2[0]0&&len>=0&&posLString; 1/H5 回 12/15 回 2

2 7/15 4.2 串的表示和实现-定长顺序存储 „ 定长顺序存储表示----顺序映像 „ 类型定义 typedef unsigned char SString[MAXSTRLEN+1]; 约定：1) 下标为0的分量存放串的长度 或 2)串值后加入一个不计入串长的结束标记字 符，如C语言中的'\0' „ 串联接Concat(&T, S1, S2) ∵是定长存储，联接后T的串长为S1和S2串长之和，该长度 可能会超出MAXSTRLEN ∴分情况处理，超出部分要“截断” 8/15 4.2 串的表示和实现-定长顺序存储 „ 串联接Concat(&T, S1, S2) „ 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<= S[0]-len+1 „ 串的复制 Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; „ 评价 „ 串长超出最大长度，约定采用截尾法 „ 串长过小，则串空间浪费较大 10/15 4.2 串的表示和实现-堆分配存储 „ 堆分配存储表示----顺序映像 „ 类型定义 typedef struct { char *ch; // 串值所在的存储区的起始地址 int length; // 串长度 } HString; „ 一些操作的实现 „ 基于复制 利用malloc()分配一块足够的空间，再按要求完成复制； 如StrAssign(&T,chars), Concat(&T, S1, S2), SubString(&Sub, S, pos, len) 11/15 4.2 串的表示和实现-堆分配存储 „ 堆分配存储表示----顺序映像 „ 一些操作的实现 „ 基于链接 建立串名和串值的映射关系， 如: StrAssign(&T, chars) „ 评价 „ 基于动态存储管理 „ 建立串名和串值的映射关系 „ 处理方便、串值共享 12/15 4.2 串的表示和实现-块链存储 „ 块链存储表示----链式映像 „ sizeof(char) < sizeof(链域) Æ 存储密度不高 存储密度 = 串值所占的存储位/实际分配的存储位 „ 类型定义 typedef struct Chunk { char ch[CHUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString;

4.2串的表示和实现-块链存储（续） 4.3串的模式匹配算法 存储密度的影响 。求子串位置的定位函数Index(S,T,pos) 存情密康小，运算处理方便，但存情占用量大 模式匹配(T:模式事) 。评价 基于堆分配存情的算法 。存储密度校低 int Index(HString S,HString T,int pos X 。块链使率的操作复杂化 1=p05】=1; while (iT.length)return (i-T.length); ■插入、测除、里换操作带来的移动 else return O; 13/15 回 14/15 圈 4.4串操作应用举例 ▣文本编辑 ·处理规则：行插入/刷除，页插入/删 除， ,数据结构：页表、行表（行号，起始地址，长 度) 。建立词索引表 ·数据结构 ,词表一书名中的关健词集合 。关健词家引表 15/15 回回 3

3 13/15 4.2 串的表示和实现-块链存储(续) „ 存储密度的影响 存储密度小，运算处理方便，但存储占用量大 „ 评价 „ 存储密度较低 „ 块链使串的操作复杂化 „ 顺序映像的缺点 „ 空间利用率低 „ 空间不可扩充，使串的某些操作（联接、置换） 受到限制 „ 插入、删除、置换操作带来的移动 14/15 4.3 串的模式匹配算法 „ 求子串位置的定位函数 Index(S, T, pos) ——模式匹配(T:模式串) 基于堆分配存储的算法 int Index( HString S, HString T, int pos ){ i = pos; j = 1; while ( iT.length) return (i – T.length); else return 0; } 15/15 4.4 串操作应用举例 „ 文本编辑 „ 处理规则：行插入/删除，页插入/删 除，…… „ 数据结构：页表、行表(行号，起始地址，长 度) „ 建立词索引表 „ 数据结构 „ 词表——书名中的关键词集合 „ 关键词索引表