数据结构 教学课件 作者 叶乃文 郑晓红 第四章.ppt

《数据结构 教学课件 作者 叶乃文 郑晓红 第四章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章串和数组本章主要介绍下列内容：串的定义、存储结构和基本运算数组的定义、基本运算和存储结构特殊矩阵的压缩存储退出4.1串4.2数组4.1串4.1.1串的定义和基本运算串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。串一般记作：s=“a1a2...an”(n0)其中，s是串的名称，用双引号（“”）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。s1=“”s2=“”s1中

2、没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。概念：子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。例如，有下列四个串a，b，c，d：a=“WelcometoBeijing”b=“Welcome”c=“Bei”d=“welcometo”子串的位置：子串在主串中第一次出现的第一个字符的位置。两个串相等：两个串的长度相等，并且各个对应的字符也都相同。例如，有下列四个串a，b，c，d：a=“program”b=“Program”c=“pro”d=“program”串的基本操作：（1）创建串

3、StringAssign(s,string_constant)（2）判断串是否为空StringEmpty(s)（3）计算串长度Length(s)（4）串连接Concat(s1,s2)（5）求子串SubStr(s1,s2start,len)（6）串的定位Index(s1,s2)例如1：将s2串插入到串s1的第i个字符后面。SubStr(s3,s1,1,i);SubStr(s4,s1,i+1,Length(s1)-i);Concat(s3,s2);Concat(s3,s4);StringAssign(s1,s3);例如2：删除串s中第i个字符开始的连续j个字符。SubStr(s1,s,1,

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

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

6、ing_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;s->str[0..len]=string_constant[0..len];//对应的字符赋值s->length=len;//赋予字符串长度}returnOK;}（2）判断串是否为空i

7、ntStringEmpty(STRINGs){if(!s.length)returnTRUE;elsereturnFALSE;}（3）求串的长度intLength(STRINGs){returns.length;}（4）串连接intConcat(STRING*s1,STRINGs2){STRINGs;StringAssign(&s,s1->str);//将s1原来的内容保留在s中len=Length(s1)+Length(s2);//计算s1和