资源描述：
《第4章 数组、字符串与广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4章数组、字符串与广义表（4课时）数组这种数据结构可以看成是线性表的推广，几乎所有的高级程序设计语言都支持这种数据结构。科学计算中涉及到大量的矩阵运算，在高级语言编程时，通常用二维数组来描述一个矩阵，从而可以对矩阵中的元素进行随机存取。当矩阵规模很大且具有特殊结构时，如对角矩阵、三角矩阵、对称矩阵、稀疏矩阵等，为减少程序的时间和空间需求，一般需要对这类矩阵进行压缩存储。在非数值处理、事务处理等问题中要大量使用字符串，字符串的逻辑结构是一种由字符构成的线性表，但字符串与一般线性表的操作有所不同。广义表也是线性表的
2、推广和扩充，具有广泛的应用价值，特别是在人工智能领域。本章主要介绍数组、矩阵、字符串和广义表的特性和存储表示等相关知识。4.1数组与矩阵本节先介绍数组的特性和基本操作，并给出一维和二维数组的表示和实现；然后介绍矩阵的特性和基本操作，并给出矩阵的表示和实现方法；最后介绍特殊矩阵的压缩存储处理方法。4.1.1数组及数组的抽象数据类型1.什么是数组数组可以看成是形如（index,value）的数据集合，其中，index是元素的索引，表示数据的逻辑位置，任意两个数据的index都不相同；value表示数据元素的值。元素的
3、索引index由一个因素构成的数组是一维数组。如果数组元素的索引由多个因素构成，这样的数组就是多维数组。很多问题都可以抽象成数组这样的数据结构。【例4-1】一维数组实例。下面关于学生编号和姓名的问题可用一维数组表示。{(1,安华)，(2,李响),（3,刘晓）,(4,张肖)}由于每一个元素的值（姓名）都仅由一个因素“编号”就可以唯一确定，所以，这个问题可以用一维数组表示。假设用A来描述这个一维数组，数组中的元素为ai，i=1,2,…,n。其中，i称为元素的下标，n是一维数组的长度。对于【例4-1】，n=4，则数组A
4、的逻辑关系如图4-1所示。4.1.1数组及数组的抽象数据类型【例4-2】二维数组实例。下面关于各班级的学生编号和姓名的问题可用二维数组表示。{（1班,1,梁冰),（1班,2,李小天),（2班,1,张爽）,(2班,2,徐成城)（3班,1,江涛）,(3班,2,郭敏敏)}由于每一个元素的值（姓名）都需要由两个因素“班级”和“编号”才能唯一确定，所以，这个问题可以用二维数组表示。可以将二维数组直观地看成是一个定长的一维数组，它的每个元素又是一个定长的一维数组。假设用A来描述这个二维数组，首先将数组A看成是以某一因素为索引
5、的一个一维数组，数组元素为Ai，i=1,2,…,m，其中，i称为元素的下标，m称为一维数组的长度。每一个元素Ai又是以另一个因素为索引的一维数组，数组元素为aij，i=1,2,…,m;j=1,2,…,n,其中，i和m同上；j是第2个下标，n是第2个下标的长度。4.1.1数组及数组的抽象数据类型对于【例4-2】，如果将数组A看成是以“班级”为索引的一维数组，则m=3，数组元素分别是A1,A2,A3。他们又分别是以“编号”为索引的一维数组，则n=2，数组元素分别为A1=（a11,a12）,A2=(a21,a22),A
6、3=(a31,a32)。二维数组A的逻辑关系如图4-2(a)所示。如果将数组A看成是以“编号”为索引的一维数组，则m=2，数组元素分别是A1、A2。他们又分别是以“班级”为索引的一维数组，n=3，数组元素分别为A1=（a11,a21,a31）,A2=（a21,a22,a32）。二维数组A的逻辑关系如图4-2(b)所示。4.1.1数组及数组的抽象数据类型从图4-2中可以看出，对于同一个二维数组问题，可以采用按行或按列的方式来组织数组。图4-2（a）中，数组A的数据元素Ai构成了一个行向量。图4-2（b）中，数组A的
7、数据元素Ai构成了一个列向量。n（n≥3）维数组的情况类似，即每个数据元素都受到n维关系的约束。在此不再赘述。4.1.1数组及数组的抽象数据类型2.数组在计算机中的存储数组一般都是采用顺序存储的方法来表示。采用顺序方法表示数组时，每个元素的存储地址可以通过简单的线性函数计算出来，因此，可以对数组元素进行随机存取。计算机的内存结构是一维地址结构，对于多维数组，将其存放(映射)到内存一维结构时，需要由数组元素的索引值来确定该元素在内存中的位置，以便实现相应的读写操作。多维数组在计算机中有两种映射：行映射和列映射。行映
8、射：左边下标变化最慢，右边下标变化最快，右边下标变化一轮，与之相邻的左边下标才变化一次。列映射：右边下标变化最慢，左边下标变化最快，左边下标变化一轮，与之相邻的右边下标才变化一次。4.1.1数组及数组的抽象数据类型以二维数组为例，假设二维数组A的数据元素为aij，则：按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…,a2n,……,am1,am2
