其他线性数据结构.ppt

第5章 其他线性数据结构 第5章 其他线性数据结构 5.1 串 5.2 多维数组 5.3 应用举例及分析 习题 5.1 串 串是由零个或多个字符组成的有限序列。用线性表表示，标记为： S=‘a1,a2,a3,……an’ (n=0) 串长度：串中的字符个数。引号不是串的内容。 空串：长度为0的串。空格串不是空串。 子串：串中连续字符组成的子序列。 子串在主串中的位置：以第一个字符出现位置标识。 空串是任何串的子串，任何串是自身的子串。 子串相等：两串的长度相等，并且对应字符都相等。 5.1.2 串的存储结构 5.1.3 串的基本操作的实现 1、在串的顺序定长存储结构上实现CONCAT(S,T1,T2) 在操作时需考虑可能出现的三种情况： 串T1和串T2的长度之和小于MAXSIZE，即两串联接得到的S串是T1串和T2串联接的正常结果，S串的长度等于T1串和T2串的长度之和。 串T1的长度小于MAXSIZE，而串T1和串T2的长度之和大于MAXSIZE，则两串联接得到的S串是T1串和T2串的一个子串的联接，串T2 的后面部分被截断。 S串的长度等于MAXSIZE。 串T1的长度等于MAXSIZE，则两串联接得到的S串是T1串的拷贝，串T2 全部被截断。S串的长度等于MAXSIZE。 2、在串的堆分配结构上实现CONCAT(S,T1,T2)操作 算法如下： void concat_h(HSTRING s, HSTRING t1, HSTRING t2) { int I; s.ch=malloc((t1.len+t2.len)*sizeof(char)); for(i=1;i=t1.len;i++) s.ch[i]=t1.ch[i]; for(i=1;i=t2.len;i++) s.ch[i+t1.ch]=t2.ch[i]; s.len=t1.len+t2.len; } 3、在串的顺序定长存储结构上实现子串的定位操作INDEX(S,T) 定位操作：子串的定位操作通常称作串的模式匹配，用于得到子串在主串中的位置。 定位函数的算法思路：在主串S中从i=1开始取一长度和串T长度相等的子串与串T进行比较，若相等，则函数返回i;否则i增加1，从i=2开始取一长度和串T长度相等的子串与串T进行比较，重复上述的过程，直至确定在串S中取不到和串T长度相等的子串为止，函数返回0。或在S中取到一个和串T相等的子串，函数返回i。 串小结 串是一种特殊的线性表，由有限的字符序列组成。串的应用非常广泛，凡是涉及到字符处理的领域都要用到串。很多高级语言和字符处理软件都具有较强的串处理的功能。 对串的处理可以是对整个串本身，也可以是对串的一部分(即子串)进行加工处理。串的基本运算有：串的连接、求子串、求串的长度、求子串在串中的序号和串的置换等。 5.2 多维数组 数组：数组（array）是由下标（index）和值（value）组成的序对的集合。 数组元素：在数组中，对每组有定义的下标，都存在一个与其对应的值，称为数组元素。数组中的数据元素均属于同一数据类型。 例如，二维数组： 数组的运算： 给定下标，存取相应的数据元素 给定一组下标，修改相应数据元素的值 数组一旦被定义，其维数和维界就不再改变，即数据元素的个数和元素之间的关系就不再发生变动。数组一般不做插入或删除操作。 5.2.2 二维数组的向量存储结构 一、二维数组的顺序存储规则通常有两种： 1、行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。 A的m*n个元素按行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。 2、列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。按列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。 二、数组元素存储地址、序号的运算： 设二维数组A(m×n)按行优先顺序存储，数组中第一个元素的序号为1，每个数据元素占用的存储单元数b。 求数组元素在向量中的序号： index(ai,j)=n(i-1)+j 求某个数据元素（下标i，j）的存储起地址： loc(ai,j)=loc(a1,1)+[n(i-1)+(j-1)]b 计算数组中每个元素的存储起地址所花的时