数据结构chap串学习教案

1、数据结构数据结构(sh j ji u)chap串串第一页，共22页。目录(ml)4.1串的类型串的类型(lixng)的定义的定义4.2 串的表示串的表示(biosh)和实现和实现结束放演第1页/共22页第二页，共22页。4.1串类型串类型(lixng)的定义的定义4.1.1 基本概念 1串的定义串的定义 串串( string) 是由零个或多个字符组成的有限序列，记是由零个或多个字符组成的有限序列，记作作s=a1a2an（n=0），其中），其中s为串的名字，用成对的单为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的单引号不算串引号括起来的字符序列为串的值，但两边的单引号不算串值，不包

2、含值，不包含(bohn)在串中。在串中。ai(1in)可以是字母、数字可以是字母、数字或其它字符。或其它字符。n为串中字符的个数，称为串的长度。为串中字符的个数，称为串的长度。2空串空串不含任何字符的串称为不含任何字符的串称为(chn wi)空串，它的长度空串，它的长度n=0，记为，记为s=，通常记为，通常记为 。 第2页/共22页第三页，共22页。3空白串空白串(空格串空格串) 含有含有(hn yu)一个或多个空格的串，称为空白串，它的长度一个或多个空格的串，称为空白串，它的长度n=串中空格字符的个数，例如：串中空格字符的个数，例如：s= ，长度为，长度为1。4子串、主串子串、主串 若一个串

3、是另一个串中连续若一个串是另一个串中连续(linx)的一段，则这个串称的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如为另一个串的子串，而另一个串相对于该串称为主串。例如,串串s1=“abcdefg”，s2=“fabcdefghxyz”，则，则s1为为s2的子串，的子串，s2相对于相对于s1为主串。为主串。 另外，空串是任意串的子串，任意串是自身的子串。 问题：若一个串的长度为n，则它的子串数目(shm)和真子串个数分别为多少(除串本身以外的子串都称为真子串)？第3页/共22页第四页，共22页。5. 子串在主串中的位置 既子串的第一个字符在主串中的位置表示(biosh)。

4、 例如：串s1=CD在s=ABCDECFG中的位置6. 串相等 两个串的长度(chngd)相等当且仅当两个串的值相等 各个对应位置的字符都相等第4页/共22页第五页，共22页。第5页/共22页第六页，共22页。第6页/共22页第七页，共22页。4.1.2 串的抽象数据类型的定义描述串的抽象数据类型的定义描述 P71注意：注意：串的逻辑结构与线性表及相似，但基本操作串的逻辑结构与线性表及相似，但基本操作(cozu)和线性和线性表有很大差别，操作表有很大差别，操作(cozu)对象而言，线性表为单个对象对象而言，线性表为单个对象作为操作作为操作(cozu)对象，而串以串的整体（子串）作为操作对象，而

5、串以串的整体（子串）作为操作(cozu)对象。对象。串类型的最小操作串类型的最小操作(cozu)子集：子集：StrAssign、StrCompare、StrLength、Concat、SubString 例如：算法例如：算法 4.1第7页/共22页第八页，共22页。4.2 串的表示串的表示(biosh)和实现和实现第8页/共22页第九页，共22页。第9页/共22页第十页，共22页。01 2345678910.MAXSIZE-110abcdefghij 012345678910.MAXSIZE-1abcdefghijk0 串的顺序存储方式(fngsh)1串的顺序存储方式(fngsh)2 -定长顺

6、序存储方式(fngsh)第10页/共22页第十一页，共22页。1.串联(chunlin)接Concat(&T,S1,S2)Status Concat(SString &T,SString S1,SString S2)/用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。 if(S10+S20=MAXSTRLEN) /未截断 T1.S10 = S11.S10; TS10+1.S10+S20 = S21.S20 ; T0 = S10 + S20; uncut = TRUE; else if(S10MAXSTRLEN) T 1.S10 = S11.S10 ;

7、 T S10+1.MAXSTRLEN = S21. MAXSTRLEN S10 ; T0 = MAXSTRLEN; uncut = FLASE ; else T 0. MAXSTRLEN = S11. MAXSTRLEN ; /T0 = S10 = MAXSTRLEN uncut = FLASE ; return uncute;/Concat第11页/共22页第十二页，共22页。2.求子串SubString(&Sub , S, pos, len)Status SubString(SString &Sub, SString S, int pod, int len) /用Sub返回

8、(fnhu)串S的第pos个字符起长度为len的子串 /其中，1=pos =StrLengh(S)且0=len= StrLength(S)- pos+1 if( posS0 | lenS0 pos +1) return EEROR; Sub1.len = Spos . pos+len - 1 ; Sub0 = len; return OK;/SubString第12页/共22页第十三页，共22页。4.2.1.3 优缺点 优点： 连续顺序存储，特别适合于子串的搜索 缺点：a.对串进行插入(ch r)或删除子串操作时，要移动大量字符， 耗时太多 b.串的长度必须预先确定，这不容易做到。第13页/共

9、22页第十四页，共22页。4.2.2 串的指针(zhzhn)表示 例如：S=“abcdef”的存储结构(jigu)具体形式见图4-4。 a S b c d e f 图4-4 S串的链式存储示意图 charnext第14页/共22页第十五页，共22页。优缺点： 优点：a. 在对串进行子串的插入(ch r)和删除时，只要修改相应的指针就可 以完成 b. 对串的长度没有限制，在存储空间足够大的情况下，可以表 示任意长度的串 缺点：a. 以增加存储空间为代价 b. 沿着指针作在子串的顺序搜索需要比定长顺序表示下子串的 搜索花更多的时间第15页/共22页第十六页，共22页。4.2.3 串的块链存储表示

10、（很少使用(shyng)，前面两种的折中方式）例如：串S=“abcdef”的存储(cn ch)结构具体形式见图4-5。每块大小为4，划分成两块，并且链表带头结点。 a b c d e f S 头结点 图4-5 S串的结点大小为 4的链式存储 #第16页/共22页第十七页，共22页。4.2.4 串的堆分配(fnpi)存储表示 （根据串的具体长度分配(fnpi)空间，应用最多）（已分配区域）free（未分配区域）storestoreMAXSIZE; 图4.8 堆结构示意图50705021sCh lengthMAXSIZE第17页/共22页第十八页，共22页。1. 特点 所有串的串值都存储在地址连续的一个存储单元序列中，而每个串的首地址是在算法执行过程中动态分配的，串的操作仍是基于”字符(z f)序列的复制“进行。2. 串的堆分配存储表示(biosh) typedef struct int length;/串长 char *ch; /若是非空串，则按串长分配存储区，否则ch为NULL HStri