数据结构(C语言版)第5章数组

10.1

概述

1. 什么是排序？ 将一组杂乱无章的数据按一定的规律顺次排列起来。存放在数据表中 按关键字排序

定义：设有记录序列：{ R1、R2 ……….. Rn } 其相应的关键字序列为： { K1、K2 ……….. Kn }; 若存在一种确定的关系： Kx <= Ky <= … <= Kz则将记录序列 { R1、R2 ……….. Rn } 排成按该关键字有序的序列： { Rx、Ry ……….. Rz } 的操作，称之为排序。数据结构

第五章一、教学内容：1、 2、 3、 4、 数组的定义和顺序存储方式； 特殊矩阵的压缩存储； 稀疏矩阵

数组和广义表

广义表的概念、表示及基本操作；广义表存储结构的实现。

二、教学要求：1、 法； 2、 3、 掌握对特殊矩阵进行压缩存储时的下标变换公式； 了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表示稀疏矩阵 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方

时进行矩阵运算采用的处理方法； 4、 掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。

数据结构

第五章 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构

数组和广义表

数据结构

数组和广义表可看成是一种特殊的线性表，其特 殊在于，表中的数据元素本身也是一种线性表。

5.1 数组的定义由于数组中各元素具有统一的类型，并且数组元素的下标一 般具有固定的上界和下界，因此，数组的处理比其它复杂 的结构更为简单。多维数组是向量的推广。例如，二维数 组： (a11 (a 21 ( ... ( m1 a

)

a12 a 22 ... am2

Am n

数据结构

(

( ( (

(

a1n ) ... ... a 2 n ) ... ... ... ) ... ... a mn ) ... ...

) ) )

)

可以看成是由一个行向量组成的向量，也可以看成 是由一个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分 量类型为一维数组类型的一维数组类型，也就是说 ， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 数组一旦被定义，它的维数和维界就不再改变 。因此，除了结构的初始化和销毁之外，数组只有 存取元素和修改元素值的操作。数据结构

5.2

数组的顺序表示和实现

由于计算机的内存结构是一维的，因此用一维内存来 表示多维数组，就必须按某种次序将数组元素排成一列 序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说 ，数组一旦建立，结构中的元素个数和元素间的关系就 不再发生变化。因此，一般都是采用顺序

存储的方法来 表示数组。

数据结构

通常有两种顺序存储方式： 以行序为主序 以列序为主序 按列序为主序存放 按行序为主序存放

0 1 1 n-1 m-1 m n

a11 11 a21 12 …….

am1 1na12 21 a22 22 …….. am2 2n ………. a1n m1 a2n m2 …….. amn mn

a11 a12 …….. a1n a11 a12 …….. a1n a21 a22 …….. a2n a21 a22 …….. a2n …………………. …………………. a a m1 am2 …….. aa a …….. mnm1 m2

mn

Loc(aij)=Loc(aa )+[(j-1)m+(i-1)]*l Loc( aij)=Loc( 11 )+[(i-1)n+(j-1)]*l 11m*n-1 m*n-1

数据结构

无论规定行优先或列优先，只要知道以下三要素便可随时求出 任一元素的地址(这样数组中的任一元素便可以随机存取！): ①开始结点的存放地址(即基地址) ②维数和每维的上、下界； ac1,c2 … ac1,d2 ③每个数组元素所占用的单元数 Amn= … aij … ad1,c2 … ad1,d2 计算二维数组元素地址的通式设一般的二维数组是A[c1..d1, c2..d2],这里c1,c2不一定是0。

则行优先存储时的地址公式为： LOC(aij)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L数组基址 aij之前的 行数 总列数，即 第2维长度 aij本行前面 的元素个数 单个元素 长度

二维数组列优先存储的通式为： LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 数据结构

例1〖软考题〗:一个二维数组A,行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节存储， 存储器按字节编址。那么，这个数组的体积是 288 个字节。 答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 例2:已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 按列存储的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K (尽管是方阵，但公式仍不同)

例3:〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048,每个元素占2个存储单元，若以列序为主序顺 8950 序存储，则元素a[32,58]的存储地址为 。 答：请注意审题！利用列优先通式： LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2=8950数据结构

5.3 矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数 学对象，在高级语言编制程序时，简单而又自然的 方法，就是将一个矩阵描述为一个二维数组。矩阵 在这种存储表示之下，可以对其元素进行随机存取 ，各种矩阵运算也非常简单，并且存储的密度为1 。但是在矩阵中非零元素呈某种规律分布或者矩阵 中出现大量的零元素的情况下，看起来存储密度仍 为1,但实际上占用了许多单元去存储重复的非零 元素或零元素，这对高阶矩阵会造成极大的浪费， 为了节省存储空间， 我们可以对这类矩阵进行压 缩存储：即为多个相同的非零元素只分配一个存储 空间；

对零元素不分配空间。数据结构

5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一 定规律的矩阵，下面我们讨论几种特殊矩阵的压 缩存储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵 。 对称矩阵中的元素关于主对角线对称，故只要 存储矩阵中上三角或下三角中的元素，让每两个 对称的元素共享一个存储空间，这样，能节约近 一半的存储空间。不失一般性，我们按“行优先数据结构

顺序”存储主对角线(包括对角线)以下的元素，其存储形式如 图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 ……………….. 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1图 5.1 对称矩阵

在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在 一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的 元素，我们必须在aij和sa[k]

数据结构

之间找一个对应关系。 若i≧j,则ai j在下三角形中。 ai j之前的i行(从第0 行到第i-1行)一共有1+2+…+i=i(i+1)/2个元素，在第i 行上， ai j之前恰有j个元素(即ai0,ai1,ai2,…,aij-1),因 此有： k=i*(i+1)/2+j 0≦k<n(n+1)/2 若i<j,则aij是在上三角矩阵中。因为aij=aji,所以只要 交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0≦ k<n(n+1)/2

数据结构

2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角(不包括主对角线) 中的元素均为常数。下三角矩阵正好相反，它的主对 角线上方均为常数，如图所示。在大多数情 …… 此处隐藏：2825字，全部文档内容请下载后查看。喜欢就下载吧 ……