数据结构课件第4章串.ppt

《数据结构课件第4章串.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机上的非数值处理的对象基本上都是字符串数据。字符串(string)一般简称为串。1第4章串4.1串的逻辑结构4.2串的存储结构4.1串的逻辑结构4.2串的存储结构4.1串的逻辑结构例4-1x=computer以下是串的3个例子：2例4-2y=student-1例4-2z=datastructure串的定义串的基本操作3其中：串是由零个或多个字符组成的有限序列。记为：s=a1a2…an（n≥0）s是串的名，用单引号括起来的字符序列是串的值；ai（1≤i≤n）可以是字母、数字或其他字符；n是串中字符的数目，称为字符串的长

2、度。4.1.1串的定义零个字符的串称为空串(nullstring)，它的长度为零。用“”来表示空串。4当且仅当两个字符串的值相等时，也就是说，只有当两个字符串的长度相等，并且各个对应位置上的字符都相等时，则称这两个字符串是相等的。串中的任意连续的字符组成的子序列称为该串的子串；包含子串的串相应地称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。例4-4假设a、b、c、d为如下4个字符串：a=beijing，b=bei，c=jing，d=beijing则

3、：a的长度为7，b的长度为3，c的长度为4，d的长度为8；b和c都是a和d的子串，且b在a和d中的位置都是1，而c在a中的位置是4，在d中的位置是5。串a，b，c，d彼此都不相等。5由一个或者多个空格组成的串称为空格串（blankstring），它的长度为串中空格字符的个数。请注意：空格串不是空串。674.1.2串的基本操作StrAsign(S,chars)初始条件：chars是字符串常量。操作结果：生成一个其值等于chars的串S。StrLength(S)初始条件：串S已经存在。操作结果：返回串S的元素个数，称为串的长度。串的逻辑

4、结构和线性表极为相似，区别仅在于串的数据对象约束为字符集(characterset)。但是，串的基本操作和线性表有很大的差别。在线性表的基本操作中，大多是以“单个元素”作为操作对象，比如：在线性表中查找某个元素、在线性表中求取某个元素、在线性表某个位置上插入一个元素以及删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，比如：在串中查找某个子串、在串中求取某个子串、在串的某个位置上插入一个子串以及删除一个子串等。8在串的13种基本操作操作中，以下5种操作构成串类型的最小操作子集，即：这些操作不可能利用其他操作来实现：串

5、赋值StrAsign串比较StrCompare求串长StrLength串连接StrCat求子串SubString而其他串操作（除了串清除操作StrClear和串销毁操作StrDestroy外）均可以在这个最小操作子集上实现。9如果在程序设计语言中，串只是作为输入或者输出的常量出现，则只需要存储此串的串值，即字符序列即可。但是在多数非数值处理的程序中，串也以变量的形式出现。串有3种机内表示方法。定长顺序存储结构4.2串的存储结构10堆分配存储结构块链存储结构串的定长顺序存储表示类似于线性表的顺序存储结构，用一组地址连续的存储单元存

6、储串值的字符序列。在串的定长顺序存储结构中，按照予定义的大小，为每个定长的串变量分配一个固定长度的存储区，则可以用定长数组描述。予定义大小MAXSTRLEN为串变量分配一个固定长度的存储区114.2.1定长顺序存储结构1.定长顺序存储表示#defineMAXLEN40/*用户可在40以内定义最大串长*/typedefstruct{charch[MAXLEN];intlen;}SString;/*为定长顺序存储结构类型名*/12串的实际长度可以在予定义长度的范围内随意，超过予定义长度的串值则被舍去，称之为“截断”。(1)串联接StrCat

7、(SString*s,SStringt)①算法思想假设SString*s,SStringt。将串t连接在串s的后面，需要进行相应的“串值复制”操作即可，对超长部分实施“截断”操作。基于串s和串t长度的不同情况，新串（存于s中）值的产生可能有如下3种情况：132.基本操作在定长顺序存储上的实现s->len+t.len≤MAXLEN得到的串是正确的结果。s->lenlen+t.len>MAXLEN将t一部分截断，得到的新串只包含t一个子串。s->len=MAXLEN得到的新串并非联接结果，而和s相等。14ts串长s->

8、lent串长t.len新串s的串长s->len+t.lenMAXLENs剩余空间15s->len+t.len≤MAXLEN剩余空间s串长s->lentt串长t.len]s新串s长MAXLENt中被截去的字符