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

第4章串和数组4.1串
4.2数组
4.3应用举例4.1串串一般记作：
s=“a1a2...an”(n0)
其中，s是串的名称，用双引号（“”）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。
s1=“”
s2=“”
s1中没有字符，是一个空串；而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）创建串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.顺序存储结构
串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。在C语言中，有两种实现方式：
第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：
#defineMAXSIZE255
chars[MAXSIZE];第二种是在程序执行过程中，利用标准函数malloc和free动态地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目的存储空间，从而提高存储资源的利用率。类型定义如下所示：
typedefstruct
{chardata[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>MAXSIZE-1)return0;/*s长度不够*/
j=0;
while(s1[j]!=’\0’){s[i]=s1[j];i++;j++;}
j=0;
while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;}
s[i]=’\0’;return1;
}(2)子串
intStrSub(char*t,char*s,inti,intlen)
/*用t返回串s中第个i字符开始的长度为len的子串1≤i≤串长*/
{intslen;
slen=StrLength(s);
if(i<1||i>slen||len<0||len>slen-i+1)
{printf(＂参数不对＂);return0;}
for(j=0;j<len;j++)
t[j]=s[i+j-1];
t[j]=’\0’;
return1;
}(3)串比较
intStrComp(char*s1,char*s2)
{inti=0;
while(s1[i]==s2[i]&&s1[i]!=’\0’)i++;
return(s1[i]-s2[i]);
}
4.2数组图4-3其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成，其元素总数为m×n。在C语言中，二维数组中的数据元素可以表示成a[表达式1][表达式2]，表达式1和表达式2被称为下标表达式，比如，a[i][j]。
数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。
二维数组结构的基本操作：
（1）赋值操作。给定一组下标，存储或修改与之对应的数据元素。
（2)取值操作。给定一组下标，读其对应的数据元素元素。4.2.2数组的存储结构
从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。
组成数组结构的元素可以是多维的