数据结构4 串课件.ppt

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

1、1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握串的堆存储结构以及在其上实现串操作的基本方法。4.了解串操作的应用方法和特点。学习提要4.1串的定义和基本运算串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符。串：由零个或多个字符组成的有限序列。人们经常又这样定义串：串：是一个有穷字符序列。串一般记作：s=‘a1a2...an’(n0)其中

2、，s是串的名称，用单引号（‘’）括起的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。s1=“”s2=“”s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。概念：子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。例如，有下列四个串a，b，c，d：a=“WelcometoBeijing”b=“Welcom

3、e”c=“Bei”d=“welcometo”子串的位置：子串在主串中第一次出现的第一个字符的位置。两个串相等：两个串的长度相等，并且各个对应的字符也都相同。例如，有下列四个串a，b，c，d：a=“program”b=“Program”c=“pro”d=“program”串的基本操作：（1）创建串StringAssign(s,string_constant)（2）判断串是否为空StringEmpty(s)（3）计算串长度Length(s)（4）串连接Concat(s1,s2)（5）求子串SubStr(

4、s1,s2start,len)（6）串的定位Index(s1,s2)4.2串的存储结构1.顺序存储结构串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式：第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：#defineMAX_STRING255//0号单元存放串的长度，字符从1号单元开始存放typeunsignedcharString[MAX_STRING];第二种是在程序执行过程中，利用标准函数mallo

5、c和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：typedefstruct{char*str;intlength;}STRING;不同的定义形式，算法中的处理也略有不同。下面我们将给出在第二种顺序存储方式下串的几个基本操作的算法。（1）串的赋值intStringAssign(STRING*s,char*string_constant){if(s->str

6、)free(s->str);//若s已经存在，将它占据的空间释放掉for(len=0,ch=string_constant;ch;len++,ch++);//求string_constant串的长度if(!len){s->str=(char*)malloc(sizeof(char));s->str[0]=’’;s->length=0;}//空串else{s->str=(char*)malloc((len+1)*sizeof(char));//分配空间if(!s->str)returnERROR;

7、s->str[0..len]=string_constant[0..len];//对应的字符赋值s->length=len;//赋予字符串长度}returnOK;}（2）判断串是否为空intStringEmpty(STRINGs){if(!s.length)returnTRUE;elsereturnFALSE;}（3）求串的长度intLength(STRINGs){returns.length;}（4）串连接intConcat(STRING*s1,STRINGs2){STRINGs;StringAs

8、sign(&s,s1->str);//将s1原来的内容保留在s中len=Length(s1)+Length(s2);//计算s1和s2的长度之和free(s1->str);//释放s1原来占据的空间s1->str=(char*)malloc((len+1)*sizeof(char));//重新为s1分配空间if(!s1)returnERROR;else{//连接两个串的内容s1->str[0..Length(s)-1]=s.str[0..Length(s)-1)];s