《数据结构4_串》由会员分享，可在线阅读，更多相关《数据结构4_串（93页珍藏版）》请在金锄头文库上搜索。
1、第四章 串1本章目录本章目录4.1 串的定义 4.2 串的存储结构 4.3 顺序串的实现 4.4 模式匹配 24.1 4.1 串的定义串的定义1. 1. 串的相关概念串的相关概念2. 2. 串的抽象数据类型定义串的抽象数据类型定义3. 3. 串操作解析串操作解析 3l微机上常用的字符集是标准ASCII码，由 7 位二进制数表示 一个字符，总共可以表示 128 个字符。l扩展ASCII码由 8 位二进制数表示一个字符，总共可以表示 256 个字符，足够表示英语和一些特殊符号，但无法满足国 际需要。lUnicode由 16 位二进制数表示一个字符，总共可以表示 216 个字符，即6万5千多个字符，
2、能够表示世界上所有语言的所 有字符，包括亚洲国家的表意字符。为了保持兼容性，lUnicode字符集中的前256个字符与扩展ASCII码完全相同。 串的数据对象串的数据对象串的数据对象约束为某个字符集串的数据对象约束为某个字符集4串的相关概念串的相关概念 串 (string)：是由零个或多个字符组成的有限连续序 列，即串是一串字符。一个非空串记为： S=“s1s2.sn” 空串(null string) ：由零个字符组成的串。 空格串：由一个或多个空格组成的串。 子串：字符串中任意个连续的字符构成的子序列称 为字符串的子串。空串是任何串的子串。 主串：包含子串的字符串。 位置：一个字符在序列中的
3、序号称为该字符在串中 的位置。子串在主串中的位置则以子串的第一个字符 在主串中的位置来表示。 串的比较 ：见后页5串的比较串的比较 ：例 ：“abcd”= = “abcd”“abc” “abc” 设有两个串：X=“x1x2.xm”、Y=“y1y2.yn”， 等于( = = ) ：当m = = n，且xi= = yi 时，称X = = Y。 小于 ( ) ：当m n，且xi= = yi (i=1，2，.，n)， 或存在某个kmin(m，n)，使得xi= = yi (i=1，2，.， k-1)，xk yk 时，称X Y6假设 S = abcaabcaaabc, T = bca Index(S, T
4、, 1) = Index(S, T, 3) = Index(S, T, 8) = 子串中的第一个字符在主串中的位序260子串在主串中的位置子串在主串中的位置7串的抽象数据类型定义串的抽象数据类型定义 ADT String Data：D= ai | ai CharaterSet, i=1, 2, , n, n0Relation: R= | ai-1, aiD, i=2, , n, OperationStrAssign ( &S , T ) ；/串赋值StrLength( S ) ； / 求串长StrConcat( &S , T )；/ 串联接StrSub ( S, i，len) ；/ 求子串St
5、rCmp ( S , T) ；/ 串比较StrIndex ( S , T ) ；/ 串匹配StrInsert (&S，i，T) ；/ 串插入StrDelete (&S，i，len) ；/ 串删除StrRep (&S，T，R) ；/ 串置换 ADT8a b c d e f g ei = 3, len = 3i = 7, len = 4c d ea b c d e f g eg e空串求子串求子串SubStr(sSubStr(s, i, , i, lenlen) )9例如：sub =SubString(“commander”, 4, 3)sub = ？sub =SubString(“command
6、er”, 1, 9)sub = ？sub =SubString( “commander”, 9, 1)sub =？ man “commander”“r”求子串示例求子串示例10sub=SubString( commander, 4, 7)sub = ? sub=SubString( beijing, 7, 2) = ?sub = ?SubString(student, 5, 0) = 起始位置和子串长度之间存在约束关系长度为 0 的子串为“合法”串11假设 S = abcaabcaaabca，T = bca若 V = x， 则经置换后得到S = ？若 V = bc， 则经置换后得到S = ？a
7、xaxaaxabcabcaabc串置换串置换12例如：S = chater，T = rac，则执行 StrInsert(S, 4, T)之后得到S = character串插入串插入StrInsertStrInsert (&S, pos, T) (&S, pos, T)13串串的逻辑结构和的逻辑结构和线性表线性表极为相似极为相似，区别区别仅在于仅在于串的数据对象约束为字符集串的数据对象约束为字符集。串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单个单个元素元素”作为操作对象作为操作对象；在串的基本操作中，通常以在串的基
8、本操作中，通常以“串的整体串的整体”作为作为操作对象操作对象。串与线性表144.2 4.2 串的存储结构串的存储结构本章目录1. 串的顺序存储结构 2. 串的链式存储结构 3. 串的索引存储结构4. 串的堆存储 15串的顺序存储结构串的顺序存储结构用数组的0号单元存放串的长度，串值从1号单元 开始存放在串尾存储一个不会在串中出现的特殊字符作为串的 终结符用一变量存储串长，如顺序表一样16Status Concat(SString S1, SString S2, SString &T) / 用T返回由S1和S2联接而成的新串。若未 截断, 则返回TRUE，否则FALSE。 / Concat顺序存
9、储操作示例：串联接case 1: S10+S20MAXSTRLENcase 3: S10 = MAXSTRLENS1S2TS1S2TS2一部分被截去18串的链式存储结构 结点大小为1的链式存储结构 图 4-4 串的链式存储 图4-5 块链存储结构 块链存储结构 19串的索引存储结构图4-6 带头指针的名字索引表图4-7 带长度的名字索引表 图4-8 带末指针的名字索引表 串的索引存储结构:用串变量的名字作为关键字组织起 来的索引表，表中串名与串值之间一一对应。 例：S1=“please”，S2= “seek”.20串的堆存储4-9 堆结构示意图 堆存储中，多个串连续存放在堆中，因此需建立 一张
10、索引表记载各个串的位置(如4.2.3所述)， 另 需设一指针，指示未分配空间的首地址，如图4-9 中的avail。 基本思路：在内存中开辟能存储足够多的串，且地 址连续的存储空间作为应用程序中所有串的可利用存 储空间，称为“堆空间”。 214.3 4.3 顺序串的实现顺序串的实现本章目录1. 1. 常用常用C+C+串操作函数串操作函数2. 2. 顺序串类的定义顺序串类的定义3. 3. 操作举例操作举例 22常用C+字符串函数l串长度函数： int strlen(char * str)l串复制函数： char *strcpy (char *str1,char &str2)l串比较函数： int
11、strcmp (char *str1,char &str2)l串联结函数： char *strcat(char *str1,char &str2)l串输入： cin、getchar、getline23串长度函数 int strlen(char *str) 设：char s1=“I was a good students”；char s2=“3 years ago”；char s3=“ “；char s440；/ 空串coutstr2，返回1；例： cout ( operator (AStringAString &ob) &ob) 判断当前实例串是否大判断当前实例串是否大 于于obob串串, ,
12、若小于则返回若小于则返回1,1,否则为否则为0 0 intint operator = ( operator = (AStringAString &ob) &ob) / /判断当前实例串是否判断当前实例串是否 大于等于大于等于obob串串, ,若大于等于则返回若大于等于则返回1,1,否则为否则为0 0 29/ /与与C+C+串的比较运算串的比较运算int operator = (char *str) /判断当前实例是否与C+ 串相等,若相等则返回1,否则返回0int operator != (char *str) /判断当前实例是否与C+ 串不相等,若不等则返回1,否则返回0int opera
13、tor (char *str) /判断当前实例是否与大于 C+串,若小于则返回1,否则返回0int operator =(char *str) /判断当前实例是否与大 于等于C+串,若大于等于则返回1,否则返回0 30AString& operator = (AString &ob)； /将串ob赋值 给当前实例. AString& operator = (const char *str)； /将字符串 赋值给字符串对象AString& operator +=(AString &ob)； /若当前实例 串长度与ob串长度之和不超过maxSize则把ob串接在 当前实例的后面.AString&
14、operator +=(const char *str)； /若当前 实例串长度与str串长度之和不超过maxSize,则把str 串接到串对象后面.char& operator(int i)； /取当前实例的第i个字符返 回 31串操作举例构造函数 赋值 串连接 串比较 求子串32构造函数构造函数：实现串的创建，通过多态考虑三种 情况： l创建一个空串 l用C+串生成串对象l用串对象来生成串对象33构造函数操作步骤功能：创建一个空串 Step 1：申请串对象所需空间 Step 2：若申请成功，为串属性赋值 类C+语言描述： AString:AString() maxSize = defaul
15、tSize； / 串容量等于缺省容 量ch = new charmaxSize； / 申请串空间ch0 = 0； /串结束符curLength = 0； /空串，串长为0 34构造函数AString:AString(const char *init)用C+串生成串对象操作步骤： Step 1：根据C+串常量的长度，申请串对象所需空间 Step 2：若申请成功，为串属性赋值 Step 3：把C+串常量的值复制给串对象 类C+语言描述： AString:AString(const char *init) int initLength = strlen(init)；maxSize = (initLength defaultSize) ? initLength : defaultSize；ch = new charmaxSize+1；curLength = initLength；strcpy(ch,init)； 35构造函数用串对象来生成串对象操作步骤： Step 1：根据串常量对象的长度，申请串对象所需空间 Step 2：若申请成功，为串属性赋值 Step 3：把串常量对象的值复制给串对象 类C+语言描述： AString:AString(const AString &ob) maxSize = ob.m
