数据结构与算法学习笔记（第四章串、数组、广义表）（2）数组

男娘i 2023-03-12 09:04 3阅读 0赞

### 目录 ###

*  数组
 *   *  维度：
     *   *  一维
         *  二维
         *  三维
         *  N维
     *  结论，特点
     *  定位某个元素
     *  顺序存储方式
     *   *  二维数组的顺序存储方式（行序为主序）
     *  矩阵
     *   *  特殊矩阵的压缩存储

# 数组 #

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

## 维度： ##

### 一维 ###

*  若线性表中的数据元素是非结构的简单元素
 *  就称该数组是一维数组
 *  逻辑结构是线性结构，定长线性表
 *  声明格式：数据类型 变量名称\[长度\];

### 二维 ###

*  一维数组的数据元素又是一维数组，可以这么理解
 *  逻辑结构
    
     *  非线性结构：每个数据元素既在一个行表中（行一维数组），又在一个列表中（列一维数组）
     *  线性结构的定长线性表：二维数组的每个数据元素也是一个定长的线性表
 *  声明格式：数据类型 变量名称\[行数(数组第一维)\]\[列数(数组第二维)\];
 *  骚操作：`typedef elemtype array2[m][n];`等价于：t`ypedef elemtype array1[n];typedef array1 array2[m];`（elemtype为数据类型）

### 三维 ###

*  二维数组中的元素又是一个一维数组
 *  a\[m1\]\[m2\]\[m3\]各维元素个数为m1,m2,m3
 *  下标为i1,i2,i3的数组元素存储位置为LOC(i1,i2,i3)=a+i1*m2*m3+i2\*m3+i3
 *  a为数组首元素的存储位置，i1*m2*m3是前i1页（表示维度的量词）总元素个数,i2\*m3是第i1页的前i2行总元素个数，i3是第i2行前i3列的元素个数（注意每列一个，因为限定在了第i2行）

### N维 ###

*  n-1维数组中的元素又是一个一维数组结构
 *  这类似于嵌套定义然后展开嵌套的内容  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]

## 结论，特点 ##

*  结论：线性表结构是数组结构的特例，数组结构是线性表结构的扩展
 *  特点：结构固定——定义数组后维数和维界(\[0,维长度-1\]的闭区间两边分别为维下界和维上界）不再改变，所以数组不适用于增删操作
 *  **适用于查（取）改和数组初始化/销毁操作**

## 定位某个元素 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]

*  其中a为数组名，也是数组首地址
 *  i为数组下标值，L是数组元素所占的内存字节数（比如int型变量在32位机是4字节）

## 顺序存储方式 ##

*  以行序为主序（低下标优先）
 *  以列序为主序（高下标优先）

### 二维数组的顺序存储方式（行序为主序） ###

*  求存储位置都是求数组元素的地址，但地址又分小地址（因为不同类型占不同内存字节的缘故），以第一个小地址作为数组元素的存储位置
 *  a\[i\]\[j\]的存储位置Loc(i,j)=Loc(0,0)+(n\*i+j)\*L，存储位置取存储单元的首地址（假设int型数组元素占4个字节，即一个int型存储单元由4个小存储单元组成，这个数组元素的存储位置就取头个小存储单元）
 *  Loc(0,0)为数组开始存储位置，每个数组元素需要L个存储单元，(n*i+j)是a\[i\]\[j\]前面所有元素的个数，i代表前面一共有i行，因为数组从0开始，到i-1这一行经过i行，n就是每一行的元素个数，j就是数组元素a\[i\]\[j\]这一行前面的元素个数（前面有多少列(0~j-1共j列）就有多少个元素个数在a\[i\]\[j\]这一行这一个元素的前面，然后加起来*L就是a\[i\]\[j\]前面所有元素所需要的内存单元，然后加上首位置（首地址）就是a\[i\]\[j\]的存储位置（存储地址）
 *  例题：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 2]

## 矩阵 ##

*  一个由mxn个元素排列成的m行n列的表
 *  常规存储形式：二维数组（还有非常规存储形式，在下面介绍）
 *  常规存储特点：随机存取，存储密度1，运算简单
 *  常规存储弱点：相同值的元素很多且呈某种规律分布/零元素多，这些情况不适宜常规存储
 *  非常规存储：**压缩存储——为多个相同的非零元素只分配一个空间，零元素不分配空间——用于特殊矩阵**

### 特殊矩阵的压缩存储 ###

*  对称矩阵
    
     *  特点：**对角线为对称轴，对角线上下的三角区域元素对称**
     *  对称矩阵上下三角的元素数（包括对角线的元素）均为n(n+1)/2 （1+2+…+n)
     *  压缩存储方法：以行序为主序（先存第一行元素从左往右依次存，再第二行从左往右，再第三行。。。第N行从左往右这样存储在一个一维数组中）将一个三角存在一维数组sa\[n(n+1)/2\]中，如图所示
     *  求a\[i\]\[j\]在压缩存储所用的一维数组的位置  
        ![在这里插入图片描述][20200514162036497.png]
 *  三角矩阵
    
     *  特点：**矩阵对角线以下（或以上）的数据元素（不包括对角线）全部为常数C**
     *  压缩存储方法：重复的矩阵元素C共享一个元素存储空间，剩下的上/下三角矩阵按行序主序和共享元素空间存在一维数组里，共占用n(n+1)/2 +1个元素空间，即sa\[n(n+1)/2+1\]
     *  求a\[i\]\[j\]求a\[i\]\[j\]在压缩存储所用的一维数组的位置  
        ![在这里插入图片描述][20200514162056118.png]  
        其中上三角矩阵是说上三角矩阵有意义，不全都是一个常数C。下三角矩阵是说下三角矩阵有意义，不全都是一个常数C。
 *  对角矩阵（带状矩阵）
    
     *  压缩存储方法及对角矩阵特点及举例：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 3]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 4]
 *  稀疏矩阵
    
     *  特点：**设在mxn的矩阵中有t个非零元素，令δ=t/(mxn)，当δ<=0.05时称为稀疏矩阵**，如图所示：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 5]
     *  压缩存储方法：三元组法或十字链表法
     *  压缩原则：存各非零元素的值、行，列位置、和矩阵的行列数
        
         *  三元组法（有序的双下标法）
            
             *  三元组(i,j,aij)唯一确定矩阵的一个非零元，i代表第i行，j代表第j列，aij代表一个非零元素，注意这里i、j从1开始，也就是考虑普通矩阵而非矩阵的存储形式——矩阵数组。三元组法代表矩阵二维数组的方式我举个例子给你说明：  
                ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 6]
             *  三元组的不同表示方法决定稀疏矩阵不同的压缩存储方法
             *  **三元组顺序表（以下标1开始，下标0用来描述稀疏矩阵总体信息：总行数，总列数，非零元素总个数**，如图所示：  
                ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 7]
             *  优点：非零元素在表中按行序有序存储，因此便于进行依次顺序处理的矩阵运算（取某矩阵元素，改某矩阵元素）
             *  缺点：不可随机存取，必须像链表一样从头找我想找的行号来存取某一行的非零元素
         *  十字链表法
            
             *  **两个指针数组：一个行头指针数组，一个列头指针数组，就像这样**，如图所示：  
                ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 8]  
                ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 9]
             *  优点：灵活插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素。从而简便实现矩阵各种运算
             *  特点：矩阵的每一个非零元素用一个结点表示，该结点结构为：  
                ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 10]  
                **row是非零元素值所在矩阵二维数组的行，col是非零元素值所在矩阵二维数组的列，value是非零元素值**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: /images/20230312/7b09dec646854022a511351250a3c6b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]: /images/20230312/cd4a5d0e73614ecfa0054f48bc8e407c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 2]: /images/20230312/3f9a68aee91a4af4865a695fd80c259c.png
[20200514162036497.png]: /images/20230312/a0a42eac96aa4bd0bf24195108f26865.png
[20200514162056118.png]: /images/20230312/ffb14059fc7b4b46adbe3cfded4b336c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 3]: /images/20230312/7d5a7f8e10434876b90b27ac92ea69c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 4]: /images/20230312/c81ad7ea7fcc441a8cb3b194cf14e668.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 5]: /images/20230312/f5b894bf54164198ba91c9d266395c9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 6]: /images/20230312/6f245056090b4ebfbbcd2c696eabf16c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 7]: /images/20230312/f696c866ff03405cb0813fc6f3cb80e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 8]: /images/20230312/d9ff95dd30b24a4984c462453cdddab4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 9]: /images/20230312/f488899e0daf4f61b569fa2f2d2cb877.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 10]: /images/20230312/c73650c4bb934c5eb3cb8b21769899a1.png