华北电力大学：数据结构_第4章(数组和广义表)

North China Electric Power University 数据结构 Data Structure 华北电力大喾计算机斛学与工程柰 Dept of Computer Science& Engineering of North China Electric Power University

数据结构 North China Electric Power University Data Structure 华北电力大学计算机科学与工程系 Dept. of Computer Science&Engineering of North China Electric Power University

North China Electric Power University 第四章数组和广义表 ★数組的逻辑结构 ★数組的顺序存储分配 ★矩阵的瓜缩存储 ★稀減矩阵

第四章 数组和广义表 ★ 数组的逻辑结构 ★ 数组的顺序存储分配 ★ 矩阵的压缩存储 North China Electric Power University ★ 稀疏矩阵 ★ 广义表

North China Electric Power University ★數组的逻辑结构 个二维数组的类型定义如下: A: arraylc.m, dn] of Elem Type 其中c,d设为1,数组可表示为: 它可以看成是由m个行向量或 12 n个列向量组成的线性表。也即,A=4122…a2n 二维数组可以看成是一种推广的 线性表,这种线性表的每一个数 am1am2∴amn 据元素本身也是一个线性表。 类似地, 个三维数组可以看成是数据元素为二维数组的线性表 个n维数组可视为其数据元素为n-1维数组的线性表 华电计算机系

★数组的逻辑结构 North China Electric Power University 华电计算机系 一个二维数组的类型定义如下： 其中c,d设为1，数组可表示为： A:array[c..m,d..n] of ElemType A= a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn 它可以看成是由m个行向量或 n个列向量组成的线性表。也即， 二维数组可以看成是一种推广的 线性表，这种线性表的每一个数 据元素本身也是一个线性表。 类似地， 一个三维数组可以看成是数据元素为二维数组的线性表 一个n维数组可视为其数据元素为n-1维数组的线性表

North China Electric Power University ★数组的顺序存储分配 维数组A[:nl All:n]=(a1,a2,a a1 a1 a, a ani a 若已知每个元素占k个存储单元,并且知道第 一个元素的存储地址Loc(a1),则 Loc( ai =loc( a1+(i-1)x k 华电计算机系

North China Electric Power University 华电计算机系 ★数组的顺序存储分配 一. 一维数组A[1:n] a1 a2 a3 … an-1 an Loc(ai ) = Loc(a1 ) + (i-1)  k A[1:n] = ( a1, a2, a3, … , an ) 若已知每个元素占k 个存储单元，并且知道第 一个元素的存储地址Loc(a1 ), 则

North China Electric Power University 二维数组A[1 m。I:n a11a12a13 aIn a21a22a23 a2n eml n aml am2 am3 In 行序为主分配方式 列序为主分配方式一 华电计算机系

North China Electric Power University 华电计算机系 二. 二维数组A[1:m, 1:n] a11 a12 a13 … … a1n a21 a22 a23 … … a2n A[1:m, 1:n] = … … … … am1 am2 am3 … … amn 行序为主分配方式 列序为主分配方式

North China Electric Power University 1.行序为主序分配方式 a11 a12 a in a21a22a23…a2n A[:m, I: n am2am3∴.amn a a n 2n a a nn 第行 第2行 华电计算机系

North China Electric Power University 华电计算机系 a11 . . . a1n a21 . . . a2n a31 . . . aij . . . amn 第1行 第2行 …… a11 a12 a13 … … a1n a21 a22 a23 … … a2n A[1:m, 1:n] = … … … … am1 am2 am3 … … amn 1. 行序为主序分配方式

North China Electric Power University a a a 21 a a 23 a 2n :a31a32a33 a3 行 3n: All: m, I: n a am2 am3 amn 若已知每个元素占k个存储单元,并且知道第 个元素的存储地址LOC(a1),则 Loc(a)=Loc(a1)+(-1)×n×k+(j-1)×k Loc(a1)+[(i-1)×n+(j-1)×k 华电计算机系

North China Electric Power University 华电计算机系 a11 a12 a13 … … a1n a21 a22 a23 … … a2n a31 a32 a33 … … a3n A[1:m, 1:n] = … … … … aij … … am1 am2 am3 … … amn i-1 行 若已知每个元素占k个存储单元，并且知道第一 个元素的存储地址 LOC(a11), 则 Loc(aij) = Loc(a11) + (i−1)nk + (j−1)k = Loc(a11) + [ (i−1)n+(j−1) ]k

North China Electric Power University 2.列序为主序分配方式 a11a12a13 ain 21 a a n A[l: m, I: n am1 am2 am3 mn 第1列 第2列 华电计算机系

North China Electric Power University 华电计算机系 a11 . . . am1 a12 . . . am2 a13 . . . aij . . . amn 第1列 第2列 …… a11 a12 a13 … … a1n a21 a22 a23 … … a2n A[1:m, 1:n]= … … … … am1 am2 am3 … … amn 2. 列序为主序分配方式

North China Electric Power University :a11a12a13 a a2182423 a n a31a32a33∴:a3n A:m,1:n= am1 am2 am3 mn 看0000看0D0000D0垂 1列 若已知每个元素占k个存储单元,并且知道第 个元素的存储地址LOC(a1),则 Loc(a;)=Loc(a1)+(-1×mxk+(i-1)×k Loc(a1)+[(-1)xm+(i-1)]×k

North China Electric Power University a11 a12 a13 … … a1n a21 a22 a23 … … a2n a31 a32 a33 … … a3n A[1:m, 1:n] = … … … … aij … … am1 am2 am3 … … amn j-1 列 若已知每个元素占k个存储单元，并且知道第一 个元素的存储地址 LOC(a11), 则 Loc(aij) = Loc(a11) + (j−1)mk + (i−1)k = Loc(a11) + [ (j−1)m+(i−1) ]k

North China Electric Power University ★矩阵的瓜缩存储 所谓压缩存情是指为多个值相同的元素,或者 位置分布有规律的那些元素分配尽可能少的存储空 间,而对0元素一般情况下不分配存储空间。 a11a12a13 a a21a22a23 a2n All: m, I:n I 2 am3 mn 传统做法 /华电计算机系

North China Electric Power University 华电计算机系 a11 a12 a13 … … a1n a21 a22 a23 … … a2n A = … … … … am1 am2 am3 … … amn A[ 1:m, 1:n ] 所谓压缩存储是指为多个值相同的元素, 或者 位置分布有规律的那些元素分配尽可能少的存储空 间，而对0元素一般情况下不分配存储空间。 传统做法 ★矩阵的压缩存储