第4章串.ppt

《第4章串.ppt》由会员分享，可在线阅读，更多相关《第4章串.ppt（22页珍藏版）》请在麦多课文档分享上搜索。

1、第4章 串,数据结构（类C语言描述）,目录,4.1串的类型的定义,4.2 串的表示和实现,结束放演,4.1串类型的定义,4.1.1 基本概念,1串的定义串( string) 是由零个或多个字符组成的有限序列，记作s=a1a2an（n=0），其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的单引号不算串值，不包含在串中。ai(1in)可以是字母、数字或其它字符。n为串中字符的个数，称为串的长度。,2空串 不含任何字符的串称为空串，它的长度n=0，记为s=，通常记为 。,3空白串(空格串)含有一个或多个空格的串，称为空白串，它的长度n=串中空格字符的个数，例如：s= ，长度为1。,

2、4子串、主串若一个串是另一个串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。,另外，空串是任意串的子串，任意串是自身的子串。问题：若一个串的长度为n，则它的子串数目和真子串个数分别为多少(除串本身以外的子串都称为真子串)？,5. 子串在主串中的位置既子串的第一个字符在主串中的位置表示。例如：串s1=CD在s=ABCDECFG中的位置,6. 串相等两个串的长度相等 当且仅当两个串的值相等各个对应位置的字符都相等,串的基本操作,StrAssign(&T,char

3、s) 生成一个值等于chars的串T SubString(&sub,s,pos,len) 用sub 返回串S的第pos个字符起长度为len 的子串 Concat(&T,s1,s2) T为s1,s2连接而成的新串 Replace(&S,T,V) 用V替换S中出现的所有与T相等的不重叠子串。 Index(S,T) 若S中存在串T值相同的子串，返回其在主串S中第一次出现的位置，否则函数返回值为0 Strcompare(S,T) ST 返回值0S=T 返回值=0ST 返回值0,例:S=I am a Student T=Good Q=worker Strlength(S)=14 SubString(S,

4、8,7)=Student Index(S, a)=3 Index(S,T)=0 Replace(S,Student,Q)= I am a worker Concat(SubString(S,6,2),Concat(T,SubString(S,7,8)=Concat(a ,Concat(Good, Student)=a Good Student,4.1.2 串的抽象数据类型的定义描述 P71 注意： 串的逻辑结构与线性表及相似，但基本操作和线性表有很大差别，操作对象而言，线性表为单个对象作为操作对象，而串以串的整体（子串）作为操作对象。 串类型的最小操作子集：StrAssign、StrCompa

5、re、StrLength、Concat、SubString例如：算法 4.1,4.2 串的表示和实现,4.2.1 定长顺序存储表示 4.2.2 串的指针表示 4.2.3 串的块链存储表示 4.2.4 串的堆分配存储表示,4.2.1 定长顺序存储表示,4.2.1.1 定义 定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：#define MAXSTRLEN 255 /一个固定长度的存储区/串的长度在这个范围内随意，超过这个长/度的串值则被舍去，既串被截断typedef unsign

6、ed char sstringMAXSTRLEN+1;/0号单元存放串的长度sstring s; /s是一个可容纳255个字符的顺序串,串的顺序存储方式1,串的顺序存储方式2-定长顺序存储方式,4.2.1.2 运算,1.串联接Concat( /Concat,2.求子串SubString( /SubString,4.2.1.3 优缺点优点： 连续顺序存储，特别适合于子串的搜索缺点：a.对串进行插入或删除子串操作时，要移动大量字符，耗时太多b.串的长度必须预先确定，这不容易做到。,4.2.2 串的指针表示,例如：S=“abcdef”的存储结构具体形式见图4-4。,优缺点：优点：a. 在对串进行子串

7、的插入和删除时，只要修改相应的指针就可以完成b. 对串的长度没有限制，在存储空间足够大的情况下，可以表示任意长度的串缺点：a. 以增加存储空间为代价b. 沿着指针作在子串的顺序搜索需要比定长顺序表示下子串的搜索花更多的时间,4.2.3 串的块链存储表示（很少使用，前面两种的折中方式）,例如：串S=“abcdef”的存储结构具体形式见图4-5。每块大小为4，划分成两块，并且链表带头结点。,4.2.4 串的堆分配存储表示（根据串的具体长度分配空间，应用最多）,1. 特点所有串的串值都存储在地址连续的一个存储单元序列中，而每个串的首地址是在算法执行过程中动态分配的，串的操作仍是基于”字符序列的复制“进行。,2. 串的堆分配存储表示typedef struct int length; /串长char *ch; /若是非空串，则按串长分配存储区，否则ch为NULL HString;,Status StrInsert(HString /StrInsert,注意：第pos个字符的时间存储位置：定长顺序 pos 实际串存储位置下标从1开始堆分配存储 pos-1 下标从0开始,作业：4.54.6,