数据结构ch5_数组和广义表

数组和广义表 课件

数

据

结

构

Data Structure主讲人： 刘 玮

数组和广义表 课件

第五章 数组和广义表

5.1 5.2 5.3 5.4

数组的定义

数组的顺序表示和实现矩阵的压缩存储 广义表的基本概念和存储结构

数组和广义表 课件

5.1 数组的定义5.1.1 什么是数组 数组是n(n≥0)个相同数据类型数据元素构成 的有限序列。 数组可以看成是一种特殊的线性表，即线性表 中数据元素本身也是一个线性表。

数组和广义表 课件

二维数组同样满足数组的定义。二维数组可以看成 一个特殊的一维数组，其中的每个元素又是一个一 维数组。) ) )

Am n

(

a11 a12 a 21 a 22 ... ... a m1 a m 2 ) ( (

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

Am n

a11 a12 ( a 21 a 22 ( ... ... ( a m1 a m 2 (

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

数组和广义表 课件

数组的特点： 数组中的数据元素数目固定(结构固定); 数组中的数据元素具有相同的数据类型(元素同构); 数组中的每个数据元素都与一组唯一的下标值相对应； 数组是一种随机存储结构。

数组和广义表 课件

5.1.2 数组的抽象数据类型ADT

数组和广义表 课件

5.2 数组的顺序表示和实现 在数组中插入或者删除一个元素有意义吗？

数组应该采用何种方式存储？

顺序存储方式

数组和广义表 课件

5.2 数组的顺序表示和实现 用一组连续的存储单元来表示数组。

有两种存储方式 以行为主:对二维数组进行“按行切分”,即将数组中 的数据元素“按行依次排放”在存储器中； 以列为主：对二维数组进行“按列切分”,即将数组 中的数据元素“按列依次排放”在存储器中。

数组和广义表 课件

按行序为主序存放

每个数据元素占L个存储单元； LOC(0,0)表示数据元素a00的存储地址， 是数组的起始地址(基地址); LOC(i,j)表示下标为(i,j)的数据元素aij 的存储地址。 LOC(i,j)=LOC(0,0)+(i*n+j)*L

数组和广义表 课件

按列序为主序存放

每个数据元素占L个存储单元； LOC(0,0)表示数据元素a00的存储地址， 是数组的起始地址(基地址); LOC(i,j)表示下标为(i,j)的数据元素aij 的存储地址。 LOC(i,j)=LOC(0,0)+(i*m+j)*L

数组和广义表 课件

5.3 矩阵的压缩存储

压缩存储 为多个值相同的矩阵只分配一个存储空间；

对零元不分配空间。

数组和广义表 课件

5.3.1 特殊矩阵

1. 特殊矩阵值相同的元素或者0元素在矩阵中的分布有一定规律。

数组和广义表 课件

2. 特殊矩阵的压缩存储 对称矩阵仅存储下 三角

i(i 1) / 2 j 1, i j k j ( j 1) / 2 i 1, i j

数组和广义表 课件

下三角矩阵

i(i 1) / 2 j 1, i j k n(n 1) 2 ,i j

数组和广义表 课件

对角矩阵

数组和广义表 课件

5.3.2 稀疏矩阵

1. 稀疏矩阵 非零元较零元少，且分布没有一定规律的矩阵。 压缩原则：

尽量少存或不存0元；尽量减少没有意义的运 算；运算要方便。

压缩存储方法：三元组顺序表、行逻辑连接和十字链表。

数组和广义表 课件

2. 三元组顺序表

存储特点 对于矩阵中每个非0元素，用它的行号、列号、 元素值，即(i, j, aij)表示。

将表示稀疏矩阵的所有非0元素的三元组按行优 先(列优先)顺序排列，则可得到一个其结点均 是三元组的线性表，称为三元组表。 以顺序存储结构来表示三元组。 要唯一确定一个稀疏矩阵，还必须存储该矩阵 的行数和列数。

数组和广义表 课件

数据类型定义# define MAXSIZE 12500 三元组结点： typedef struct{ int i, j; ElemType e; } Triple; 稀疏矩阵： typedef struct{ Triple data[MAXSIZE+1] ]; int mu, nu, tu; /*行、列、非零元素个数*/ } TSMatrix ;

数组和广义表 课件

i 0 1 2 3 4 5data[0].i, data[0].j, data[0].e 分别存放矩阵行列维数和非零 元个数。

j 7 2 3 1 6 3 2 1 4data

e 8 12 9 -3 14 24 18 15 -7

6 1 1 3 3 4 5 6 6

6 7 8