【数据结构（18）】4.4 数组 |
您所在的位置：网站首页 › 简述数据类型和抽象数据类型的定义 › 【数据结构（18）】4.4 数组 |
【数据结构（18）】4.4 数组
|
文章目录
一、数组的定义及特点二、数组的抽象数据类型定义三、数组的顺序存储1. 一维数组2. 二维数组2.1 以行序为主序2.2 以列序为主序
四、特殊矩阵的压缩存储1. 对称矩阵2. 三角矩阵3. 对角矩阵4. 稀疏矩阵4.1 十字链表
一、数组的定义及特点
数组 按照一定格式排列起来的，具有相同类型的数据元素的集合。一维数组 若线性表中的数据元素为非结构的简单元素，则称为一维数组。逻辑结构：线性结构。定长的线性表声明格式：数据类型 变量名 [数组长度]。 如：int num [5] = {0，1，2，3，4};二维数组
三维数组 若二维数组中的元素又是一个一维数组，则称之为三维数组。n 维数组 若 n-1 维数组中的元素又是一个一维数组结构，则称作 n 维数组。结论 线性表结构时数组结构的一个特立，而数组结构又是线性表结构的扩展。数组特点 结构固定 —— 定义后，维数和维界不再改变。数组基本操作 除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。不会说有什么插入或者删除数组中的某个元素的操作。 二、数组的抽象数据类型定义n 维数组的抽象数据类型
举个例子： 二维数组的抽象数据类型的数据对象和数据关系的定义。 n = 2（维数为2，二维数组）。 b₁：第 1 维长度（行数）；b₂：第 2 维长度（列数）。 aj₁j₂：第 1 维下标为 j₁，第 2 维下标为 j₂。
基本操作 构造数组 A：==InitArray(&A,n,bound1,…boundn)。销毁数组 A：DestroyArray(&A)。取数组元素值：Value(A,&e,index1,…,indexn)。给数组元素赋值：Assign(A,&e,index1…,indexn)。 三、数组的顺序存储数组特点 结构固定，固定以后，维数和维界不再改变，所以比较适合采用顺序存储结构。数组基本操作 除了结构的初始化和销毁之外，只有取元素合修改元素值的操作。不会说有什么插入或者删除数组中的某个元素的操作。注意 数组可以是多维的，但存储数据元素的内存单元地址是一维的；因此，在存储数据结构之前，需要解决将多维关系映射到一维关系的问题。 1. 一维数组 例，有数组定义：int a [5]; 每个元素占用4个字节，假设 a[0] 存储在2000单元的位置，a[3] 应该在 2012 的位置上，2000 + （3 - 0）* 4。
假设一个 m 行 n 列的二维数组，每一行都有 n 个元素，每列都有 m 个元素。 这样一个二维数组可以看成是由若干行组成的，每一行都是一个一维数组。 也可以看成是由若干列组成的，每一列都是一个一维数组。
两种顺序存储方式 以行为主序（低下标优先）BASIC、COBOL 和 PASCAL。以列为主序（高下标优先）FORTRAN。 2.1 以行序为主序 存储单元是一维结构，而数组是个多维结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。按照行来存储，存储完第一行之后再存储第二行，以此类推。要查找某个元素的话就要找到对应的行列位置，如：第一行一列的元素就在 [0][0] 的位置，第二行第二列的元素就在下标为 [1][1] 的位置。
以行序为主序的存储位置计算
矩阵 一个由 m * n 个元素排成的 m 行 n 列的表。有时为了节省存储空间，可以对这类矩阵进行压缩存储。矩阵的常规存储 将矩阵描述为一个二维数组。矩阵的常规存储的特点 可以对其元素进行随机存取。矩阵运算非常简单，存储的密度为1。 不需要额外的空间存放地址，分配100个字节的空间就能存储100字节的数据。不适合常规存储的矩阵 值相同的元素很多且呈某种归路分布；零元较多。矩阵的压缩存储 为多哥相同的非零元素只分配一个存储空间；对零元素不分配空间。1. 什么是压缩存储 若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2. 什么样的矩阵能够压缩？ 一些分布有规律的矩阵；对称矩阵、对角矩阵、三角矩阵、稀疏矩阵等。3. 什么是稀疏矩阵 矩阵中非零元素的个数较少（一般小于 5%）有 95% 以上的元素是零，不需要给这些元素分配空间，一下节省 95% 的空间。 1. 对称矩阵 沿着对角线相等的矩阵就称为对称矩阵。
特点 在 n x n 的矩阵 a 中，满足如下性质：aij = aji (1 |
【本文地址】