串多维数组与广义表

《串多维数组与广义表》由会员分享，可在线阅读，更多相关《串多维数组与广义表（54页珍藏版）》请在金锄头文库上搜索。

1、第4章 串、多维数组与广义表朱昌杰 肖建于 编著 清华大学出版社4.1 串串又称字符串，是一种特殊的线性表，它的每个 元素仅由一个字符组成。计算机上非数值处理 的对象基本上是字符串数据。在较早的程序设 计语言中，字符串仅作为输入和输出的常量出 现。随着计算机应用的发展，在越来越多的程 序设计语言中，字符串也可作为一种变量类型 出现，并产生了一系列字符串的操作。在信息 检索系统、文字编辑程序、自然语言翻译系统 等等应用中，都是以字符串数据作为处理对象 的。朱昌杰 肖建于 编著 清华大学出版社4.1.1 串的定义 串(string)(或字符串)是由零个或多个字符组成的 有限序列，一般记为： S=“

2、a1 a2 an“ (n0) 串名：串的名字S。 串值：用双引号括起来的字符串序列，ai(1in) 可以是字母、数字或其他字符。 串的长度：串中字符的个数n称为串的长度。 串相等：只有当两个串的长度相等，并且各个对 应位置上的字符都相等时，才能称为串相等。朱昌杰 肖建于 编著 清华大学出版社4.1.1 串的定义 子串：串中任意个连续的字符组成的子序列称为该串的 子串。 主串：包含子串的串称为该子串的主串。 例如：S1“anhui“，S2=“huaibei“，S“anhui huaibei“，其中S1、S2都是S的子串。S为S1、S2的 主串。 空格串：由一个或多个空格组成的串称为空格串，空格

3、串的长度不为零。 空串：长度为0的串称为空串，通常用来表示，在C程序 中表示成“,它是任意串的子串。 模式匹配：求子串在主串中的起始位置称为子串定位或 模式匹配。例如：S1在S中的位置是1，而S2在S中 的位置是7。朱昌杰 肖建于 编著 清华大学出版社4.1.1 串的定义 ADT String 数据对象D：D=ai|aiElemSet，i=1,2, ,n,n0 数据关系R：R=| ai-1,aiD，i=2,3, ,n 基本操作P： 串赋值StrAssign(m=StrLength(T); i=pos;while(iS0|lenS0-pos+1) printf(“参数错误”);T0=0；T1=

4、0; else for(i=1;iS.length|lenS.length-pos+1) printf(“参数错误”); T.ch=NULL; T.length=0; else T.ch=(char *)malloc(len *sizeof(char);for(i=0;i1)个相同类型的数据元素a0，al， ，ai，an-1构成的有限序列。n是数组的 长度。其中数组中的数据元素ai是一个数据结 构，它可以是整型、实型等简单数据类型，也 可以是数组、结构体、指针等构造类型。根据 数组元素ai的组织形式不同，数组可以分为一 维数组、二维数组以及多维（n维）数组。朱昌杰 肖建于 编著 清华大学出版社

5、4.2.1 数组的定义1.一维数组 一维数组可以看成是一个线性表或一个向量， 它在计算机内是存放在一块连续的存储单元中 ，适合于随机查找。一维数组记为An或A=( a0，al，ai，an-1)。 一维数组中，已知a0的存储地址是LOC(a0)、一 个数据元素占k个字节，则ai的存储地址 LOC(ai)为： LOC(ai)=LOC(a0)+ik (0in)朱昌杰 肖建于 编著 清华大学出版社4.2.1 数组的定义2.二维数组 二维数组，又称矩阵(matrix)。每个数组元素都 要受到两个关系即行关系和列关系的约束。例 如：m行n列的二维数组 Amn可以表示为：朱昌杰 肖建于 编著 清华大学出版社

6、4.2.2 数组的顺序存储结构对于二维数组，常用两种存储方式：以行序(row major order)为主序的存储方式和以列序 (column major order)为主序的存储方式。也 称行优先顺序和列优先顺序，如图4.7所示。(b)行优先顺序(c)列优先顺序a00a01a02a10a11a12a00a10a01a11a02a12朱昌杰 肖建于 编著 清华大学出版社4.2.2 数组的顺序存储结构行优先顺序 将数组元素按行排列，先存储第0行的全部元素，再存放第1 行的元素、第2行的元素，直到第m-1行的元素。其线性序 列为： a00,a01,a0(n-1),a10,a11,a1(n-1),a

7、(m-1)0,a(m-1)1,a(m-1)(n-1) 在C语言、VB等程序设计语言中，数组就是按行优先顺序存 储的。 对一个已知以行序为主序的计算机系统中，当二维数组第一 个数据元素a00的存储地址是LOC(a00)，每个数据元素占k 个字节，则aij的存储地址为: LOC(aij)=LOC(a00)+(in+j)k 其中n为每行中的列数。 朱昌杰 肖建于 编著 清华大学出版社4.2.2 数组的顺序存储结构例如，二维数组float a34，若数组a的起始地址为 2000，且每个数组元素长度为32位(即4个字节)， 计算数组元素a23 在行优先顺序存储时的内存 地址。 LOC(a23)=LOC(

8、a00)+(in+j)k=2000+(24+3)4=2 044朱昌杰 肖建于 编著 清华大学出版社4.2.2 数组的顺序存储结构列优先顺序 将数组元素按列向量排列，先存储第0列的全部元素，再存放第1列 的元素、第2列的元素，直到第n-1列的元素。其线性序列为： a00,a10,a(m-1)0,a01,a11,a(m-1)1,a0(n-1),a1(n-1),a(m-1)(n-1) 在FORTRAN等少数程序设计语言中，数组就是按列优先顺序存储 的。 该二维数组中任一数据元素aij的存储地址为: LOC(aij)=LOC(a00)+(jm+i)k 其中m为每列中的行数。 如上例条件，计算数组元素a

9、23在列优先顺序存储时的内存地址 。 LOC(a23)=LOC(a00)+(jm+i)k=2000+(33+2)4=2011朱昌杰 肖建于 编著 清华大学出版社4.2.2 数组的顺序存储结构两种顺序存储方式，数组元素的存放地址都可以利用基地址、行列数 以及每个数组元素所占用的字节数表示。如果m行n列的二维数组 Amn表示为：以行优先顺序存储的二维数组中任一数据元素aij的存储地址为: LOC(aij)=LOC(a11)+(i-1)n+(j-1)k 以列优先顺序存储的二维数组中任一数据元素aij的存储地址为: LOC(aij)=LOC(a11)+(j-1)m+(i-1)k朱昌杰 肖建于 编著 清

10、华大学出版社4.3 矩阵的压缩存储矩阵是数值计算程序设计中经常用到的数学模型，通 常用二维数组表示。然而在数值分析过程中经常遇 到一些比较特殊的矩阵，如对称矩阵、三角矩阵、 带状矩阵和稀疏矩阵等。为了节省存储空间并且加 快处理速度，下面讨论这些特殊矩阵的存储方法。朱昌杰 肖建于 编著 清华大学出版社4.3.1特殊矩阵（对称矩阵）1。对称矩阵 对称矩阵是一个n阶方阵。其 元素满足:aij=aji (0i，jn- 1)。 对称矩阵中的元素是关于主对 角线对称的，因此在存储时 只存储上三角或下三角(包括 对角线)，使得对称的元素共 享一个存储空间。这样，n 阶矩阵中的nn个元素就可 以被压缩到 n(

11、n+1)/2 个元素 的存储空间中。 朱昌杰 肖建于 编著 清华大学出版社4.3.1特殊矩阵（对称矩阵）第0行有1个元素，第1行有2个元素 ，第i行有i+1个元素，因此元素 总数为：以行优先顺序对上面的对称矩阵存储其 下三角，存储序列为： 2，4，0，1，8，1，3，6，2，0，7，1 ，6，5，3朱昌杰 肖建于 编著 清华大学出版社4.3.1特殊矩阵（对称矩阵）按行优先顺序存储到b数组后，数组元素aij，其下标特点是 ：ij且0in1。行下标为0的行有一个元素，行下标为 1的行有2个元素，.，行下标为i1的行有i个元素，则0 行到i1行共有1+2+3+i=i(i+1)/2个元素，在i行，ai

12、j 的前面有j个元素，因此A中任一元素aij和bk之间存在着 如下对应关系：当ij时，aij是上三角中的元素，因为aij=aji，访问上三角中 的元素aij时则去访问和它对应的下三角中的aji即可，因 此将上式中的行列下标交换就是上三角中元素在数组b中 的对应关系。朱昌杰 肖建于 编著 清华大学出版社4.3.1特殊矩阵（三角矩阵 ）2. 三角矩阵 三角矩阵也是一个n阶方阵，有上三角和下三角矩阵。下(上) 三角矩阵是主对角线以上（下）元素均为常数或零的n阶 矩阵，如图4.11所示。朱昌杰 肖建于 编著 清华大学出版社4.3.1特殊矩阵（三角矩阵 ）2。三角矩阵 下三角矩阵 下三角矩阵与对称矩阵的

13、压缩存储类似，不同之处在于存储完下三角 中的元素以后，紧接着存储对角线上方的常量，因为是同一个常 数，只需存储一个即可。数组下标与元素之间存在着如下对应关 系：上三角矩阵 对于上三角矩阵，第一行存储n个元素，第二行存储n1个元素，依 次类推，aij的前面有i行，共存储n+(n1)+(n(i1)=i(2n i+1)/2个元素，在i行，aij前有ji个元素，因此数组下标与元素之 间存在着如下对应关系：朱昌杰 肖建于 编著 清华大学出版社4.3.1特殊矩阵（对角矩阵）3.对角矩阵 若一个n阶方阵A满足所有的非零元素都集中在以主对角线 为中心的带状区域中，则称其为n阶对角矩阵(或带状矩阵 )。常见的有

14、三对角矩阵、五对角矩阵、七对角矩阵等。 如图4.12是一个三对角矩阵A。朱昌杰 肖建于 编著 清华大学出版社4.3.1特殊矩阵（对角矩阵）对于三角矩阵，只存储其非零元素，按行优先顺序存储到数 组b中。A中第0行和第n-1行都只有两个非零元素，其余 各行均为3个非零元素。对于不在第0行的非零元素aij， 在它前面存储了矩阵的前i行元素，这些元素共2+3(i-1)个 。若aij是本行中要存储的第1个非零元素，则k=2+3(i-1) ，此时，j=i-1，即k=2i+i-1=2i+j；若aij第是本行中要存储 的第2个非零元素，则k=2+3(i-1)+1=3i，此时，j=i，即 k=2i+i=2i+j

15、；若aij第是本行中要存储的第3个非零元素， 则k=2+3(i-1)+2=3i+1，此时，j=i+1，即k=2i+i+1=2i+j。 因此，非零元素aij与数组b的下标之间存在着如下对应关 系：k=2i+j。朱昌杰 肖建于 编著 清华大学出版社4.3.2 稀疏矩阵如果矩阵中有很多零元素，即零元素的个数远远大于非零元 素的个数时，称该矩阵为稀疏矩阵。为了节省存储空间， 稀疏矩阵一般都采用压缩存储的方法来存储矩阵中的元素 。这类矩阵一般零元素的分布没有规律，为了能找到相应 的元素，在存储非零元素值的同时也要存储其所在的行和 列信息。有两种常用的存储稀疏矩阵的方法：三元组表示 法和十字链表法。朱昌杰 肖建于 编著 清华大学出版社4.3.2 稀疏矩阵1.三元组表示法朱昌杰 肖建于 编著 清华大学出版社4.3.2 稀疏矩阵2.十字链表ijv/nextdownright结点中三元组（i,j,v）表示非零元素 所在的行、列和值，两个链域：行指 针域（right）用来指向本行中下一个 非零元素；列指针域（down）用来指 向本列中下一个