数据结构—基础知识（八）：数组

数据结构—基础知识（八）：数组

数组定义

数组：按一定格式排列起来的具有相同类型的数据元素的集合。

一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组。

一位数组的逻辑结构：线性结构。定长的线性表。

声明格式：数据类型 变量名称[长度]

? 例：int num[5]={0,1,2,3,4};

二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。

二维数组的逻辑结构：

• 非线性结构：每一个数据元素既在一个行表中，又在一个列表中。
• 线性结构（定长的线性表）：该线性表的每个数据元素也是一个定长的线性表。

声明格式：数据类型 变量名称[长度]

? 例：int num[5] [8];

在C语言中，一个二维数组类型也可以定义为一维数组类型（其分量类型为一维数组类型），即：

typedf elemtype array2[m][n];

等价于：

typedf elemtype array1[n];
typedf array1 array2[m];

n维数组：若n-1维数组中的元素又是一个一维数组结构，则称作n维数组。

结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的拓展。

数组特点：结构固定—定义后，维数和维界不在改变。

对于数组，一旦规定了其维数和各维长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。假如每个数据元素占L个存储单元，则二维数组A[0…m-1,0…n-1]（即下标从0开始，共有m行n列）中任一元素aij的储存位置可由下式确定：

? LOC(i,j)=LOC(0,0)+(n*i+j)L

LOC(i,j)是aij的存储位置；LOC(0,0)是a00的存储位置，即二维数组A的起始存储位置，也称为基地址或基址。

特殊矩阵的压缩存储

压缩存储，是指为多个值相同的元只分配一个存储空间，对零元不分配空间。

1. 对称矩阵

   【特点】在n×n的矩阵a中满足性质：aij=aji (1≤i，j≤n)

   【存储方法】只存储下（或上）三角（包括主对角线）的数据元素。共占用n(n+1)/2个元素空间

   假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着对应的关系：

   当i≥j时 k=[i(i-1)/2]+j-1

   当i<j时 k=[j(j-1)/2]+i-1

2. 三角矩阵

   【特点】对角线以下（或以上）的数据元素（不包括对角线）全部为常数C。

   【存储方法】重复元素C共享一个元素存储空间，共占用n(n+1)/2个元素空间

   （1）上三角矩阵

   sa[k]和矩阵元aij之间的对应关系

   ? 当i≤j k=[(i-1)(2n-i+2)/2]+(j-1)

   ? 当i>j k=n(n+1)/2

   （2）下三角矩阵

   sa[k]和矩阵元aij之间的对应关系

   ? 当i≥j k=[i(i-1)/2]+(j-1)

   ? 当i<j k=n(n+1)/2

3. 三对角矩阵

   k=2(i-1)+j（这里得到的数组下标k是从1开始的）

   i=[k%3] (向下取整)+1