第4章 串和数组 (数据结构教程PPT课件)

《第4章 串和数组 (数据结构教程PPT课件)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。s1=“”s2=“”s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。概念：子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。例如，有下列四个串a，b，c，d：a=“WelcometoBeijing”b=“Welcome”c=“Bei”d=“welcometo”子串的位置：子串在主串中第一次出现的第一个字符的位置。两个串

3、相等：两个串的长度相等，并且各个对应的字符也都相同。例如，有下列四个串a，b，c，d：a=“program”b=“Program”c=“pro”d=“program”串的基本操作：（1）创建串StrAssign(s1,s2)（2）判断串是否为空StrEmpty(s)（3）计算串长度StrLength(s)（4）串连接StrConcat(s1,s2)（5）求子串SubStr(s,i,len)（6）串的定位StrIndex(s1,t)4.1.2串的存储结构1.顺序存储结构串的顺序存储结构与线性表的顺序存储类

4、似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式：第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：#defineMAXSIZE255chars[MAXSIZE];第二种是在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：typedefstruct{charda

5、ta[MAXSIZE];intcurlen;}SeqString;定义一个串变量：SeqStrings;不同的定义形式，算法中的处理也略有不同。下面我们将给出在第一种顺序存储方式下串的几个基本操作的算法。(1)串联接：把两个串s1和s2首尾连接成一个新串s，即：s<=s1+s2。intStrConcat1(s1,s2,s)chars1[],s2[],s[];{inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXS

6、IZE-1)return0;/*s长度不够*/j=0;while(s1[j]!=’’){s[i]=s1[j];i++;j++;}j=0;while(s2[j]!=’’){s[i]=s2[j];i++;j++;}s[i]=’’;return1;}(2)子串intStrSub(char*t,char*s,inti,intlen)/*用t返回串s中第个i字符开始的长度为len的子串1≤i≤串长*/{intslen;slen=StrLength(s);if(i<1

7、

8、i>slen

9、

10、len<0

11、

12、l

13、en>slen-i+1){printf(＂参数不对＂);return0;}for(j=0;j

14、元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：图4-3其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成，其元素总数为m×n。在C语言中，二维数组中的数据元素可以表示成a[表达式1][表达式2]，表达式1和表达式2被