chapter 5 数组和广义表

《chapter 5 数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章数组和广义表13-Aug-211数组是一种应用非常广泛的数据类型，几乎所有的程序设计语言都支持数组类型第一节数组的定义二维数组[aij],i=0…M-1,j=0..N-1M是第一维的长度（矩阵的行数）N是第二维的长度（矩阵的列数）通常一维、二维以及三维数组有比较明显的物理含义，而高维或多维数组物理含义不明确13-Aug-212数组的定义数据对象：13-Aug-213数据关系：数组的特点数组中的总元素个数为：数组是一种结构固定，且操作有限制的线性表数组的结构固定，通常不能改变它的维数，也不能改变每个维

2、数的长度通过给定数组元数的下标，人们可以存取相应的数据元素通过给定数组元数的下标，人们可以修改数据元素的值通常情况下不能对数组元素做插入和删除操作，常用的操作是对数组元素赋值或取得数组元素的值。因此数组通常用顺序存储结构来表示。13-Aug-214数组的两种表示方法写成列向量为13-Aug-215写成行向量为第二节数组的顺序存储结构计算机中存储单元是一维的存储结构，而数组是多维结构.用一维结构来存储多维结构就存在次序的约定问题。13-Aug-216行序或列序为主序的存储结构采用行序为主的存储方式和采用列序

3、为主的存储方式，对应的存储结构如下图：13-Aug-217123456789行序为主序147258369列序为主序计算多维数组元素的位置在标准C中，数组存储采用行序为主方式假定每个数组元素占用L个单元，且采用行序为主序的存储结构，则n维数组中任意一个元素的位置可以表示为：13-Aug-218二维数组在一维存储结构中的位置如果数据结构是M×N的二维数组，在计算机内用一维存储结构存储时，那么元素aij在的存储位置为：Loc=Loc(a11)+(i-1)×N+j-1举例：在640×480的二维数组中，第320行

4、、123列数据元素的存储位置为（假定起始位置为0）：0+(320-1)×480+(123-1)注意：减1是因为C语言中元素下标从0开始13-Aug-219数组元素的位置计算示例Example51.c13-Aug-2110第三节矩阵的压缩存储问题矩阵是数学的研究对象之一高级语言通常用数组来存储矩阵元素实际应用中经常出现高阶矩阵，且有很多元素的值相同的或是零为节省存储空间，可对这类矩阵进行压缩存储矩阵中值相同的元素或零元素分布如果有规律，这样的矩阵称为特殊矩阵，反之则称为稀疏矩阵13-Aug-2111对称矩阵

5、的压缩存储矩阵满足下列条件则被称为对称矩阵13-Aug-211236　4　7　8628　4　24　816　97　4　6058　2　9　57A＝对称矩阵的压缩存储可将对称矩阵中一对对称元素分配一个存储空间，从而将空间从压缩到以存储下三角矩阵为例：任意元素与存储位置的关系为13-Aug-2113012345kn(n+1)/2第1行第0行a00a10a11a20a21aij…an-1n-1…第2行a22稀疏矩阵稀疏矩阵的定义：假定矩阵的元素个数为，其中非零元素个数为，当满足下列条件时，矩阵称为稀疏矩阵被称为稀疏

6、因子13-Aug-2114稀疏矩阵的压缩存储将稀疏矩阵中的每个非零元素表示为(行号，列号，非零元素值)——三元组将稀疏矩阵的非零元素对应的三元组所构成的集合按行优先的顺序排列成一个线性表。13-Aug-2115三元组表示示例三元组表＝((0,0,15),(1,1,11),(2,3,6),(4,0,9))三元组的顺序存储结构rowcolitem0015032205-1511111232364097(非零元素个数)5(行数)6(列数)稀疏矩阵的转置稀疏矩阵的转置算法1基本思想：直接取，顺序存。在A的三元组顺序

7、表中依次找第0列、第1列、…直到最后一列的三元组将找到的每个三元组的行、列交换后顺序存储到B的三元组顺序表中。三元组表的转置算法1示例rowcolitem0015032205-1511111232364097(非零元素个数)5(行数)6(列数)rowcolitem7(非零元素个数)6(行数)5(列数)三元组表的转置算法1示例rowcolitem0015032205-1511111232364097(非零元素个数)5(行数)6(列数)rowcolitem00157(非零元素个数)6(行数)5(列数)三元组表

8、的转置算法1示例rowcolitem0015032205-1511111232364097(非零元素个数)5(行数)6(列数)rowcolitem00150497(非零元素个数)6(行数)5(列数)三元组表的转置算法1示例rowcolitem0015032205-1511111232364097(非零元素个数)5(行数)6(列数)rowcolitem001504911117(非零元素个数)6(行数)5(列数)三元组表的转置算法