数组和广义表.ppt

本章学习要求1.了解数组的逻辑结构和基本运算；2.熟练掌握数组的两种存储表示方式，并掌握数组在以行为主存储的地址计算方法；3.掌握对特殊矩阵进行压缩存储时的下标变换公式；4.掌握特殊矩阵和稀疏矩阵的定义及其压缩存储原理、特点、适用范围，了解以三元组表示稀疏矩阵时进行矩阵运算的方法；5．掌握广义表的结构特点及存储表示方法。第2页,共27页，星期六，2024年，5月5.1数组的定义数组由一组名字相同、下标不同的同类型的元素组成，它有两个特点：（1）表长固定（2）数据元素类型统一数组的分类：（1）一维数组，即向量；（2）二维数组；（3）多维数组。第3页,共27页，星期六，2024年，5月5.1数组的定义数组结构不存在插入、删除运算。常见的操作： 值检索：给定一组下标，查取相应的数组元素的值。 值存储：给定一组下标和值，存入或修改相应数组元素的值。第4页,共27页，星期六，2024年，5月5.2数组的顺序存贮结构理论上，数组可以用两种存储结构，即顺序存储结构和链式存储结构。实际：顺序存储结构更为适宜。m行n列的二维数组按行优先顺序(以行为主序)存储：数组元素aij的存储位置由下式决定：LOC（A[i,j]）=LOC（A[0,0]）+（i*n+j）*L每个元素占L个存贮单元第5页,共27页，星期六，2024年，5月5.2数组的顺序存贮结构m行n列的二维数组按列优先顺序(以列为主序)存储：数组元素aij的存储位置由下式决定：LOC（A[i,j]）=LOC（A[0,0]）+（j*m+i）*L每个元素占L个存贮单元第6页,共27页，星期六，2024年，5月5.2数组的顺序存贮结构练习：1、二维数组A[20][10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的存储地址是＿＿＿＿。A．1208B．1212C．1368 D．13362、二维数组A中，每个数据元素占4个字节，行下标从0到4，列下标从0到5，按行优先存储时元素A[3][5]的地址域同按列优先存储时元素＿＿＿＿的地址相同。A．A[2][4]B．A[3][4]C．A[3][5]D．A[4][4]第7页,共27页，星期六，2024年，5月5.3矩阵的压缩存储特殊矩阵:值相同的元素或零元素在矩阵中的分布有一定的规律。稀疏矩阵:矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律。压缩存储原理：为相等的多个非零元只分配一个存储空间，零元不分配空间。第8页,共27页，星期六，2024年，5月5.3.1特殊矩阵的压缩存储特殊矩阵常见的特殊矩阵有对称矩阵、下（上）三角矩阵、对角矩阵等等。1.对称矩阵若一个n阶矩阵A中的元素满足aij=aji（1≤i，j≤n），则称为n阶对称矩阵。压缩存储原理：为每一对对称元素分配一个存储空间，则可将原本需要n×n个元素空间压缩为n(n+1)/2个元素空间中。第9页,共27页，星期六，2024年，5月假设以一维数组s[1：n(n+1)/2]作为n阶对称矩阵A的存储结构，则s[k]和矩阵元素aij之间存在一一对应关系，矩阵下标(i,j)与k的关系如下：第10页,共27页，星期六，2024年，5月2.三角矩阵下（上）三角矩阵的特点是以主对角线为界的上（下）半部分所有元素的值都相同，而下（上）半部分的元素值则没有任何规律。将上半部分的常量值存储在0单元，下半部分和主对角上的元素从1号单元开始存放对于任意的（i,j），在一维数组中的存放位置可利用下列公式求得：第11页,共27页，星期六，2024年，5月3.对角矩阵若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k阶对角矩阵。非零元素以行为主序，从下标为1的位置开始依次存放在一维数组中，而位置1存放数值0对于任意的（i,j），可按以下公式求得矩阵元素在一维数组中的存储位置k：第12页,共27页，星期六，2024年，5月假设在m×n的矩阵中，有t个元素不为零。令δ=t/m×n,称δ为矩阵的稀疏因子。通常认为δ≤0.05的矩阵为稀疏矩阵。三元组顺序表将三元组按行优先顺序排列，同一行中按列号从小到大的顺序排列，组成一个线性表，称为三元组表，再采用顺序存储方法存储该表，称为三元组顺序表。5.3.2稀疏矩阵第13页,共