数据结构 串 第四章串 主讲：张显 知识点：串的定义、表示与实现， 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 回 11 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) // T<=S, T为“Data Structure” „ 比较 StrCompare(S, T) „ 连接 Concat(T, “Data”, “Structure”) //T为“DataStructure” „ 取子串 SubString(sub, S, 2, 5) // sub为“ata S” „ 子串在主串中的定位 Index(S, “a”, 3) // 4 „ 子串置换 Replace(S, “a”, “b”) // S为“Dbtb Structure” „ 子串插入 StrInsert(S, 3, “aha”) // “Daahata Structure” „ 子串删除 StrDelete(S, 3, 5) // “Daructure” 6/15 4.1 串类型的定义-操作间的关系 „ 串的最小操作子集 赋值、求串长、比较、联接、取子串 „ 定位函数 Index(S, T, pos) int Index(String S, String T, int pos) { if (pos>0){ // 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