《数据结构数组和广义表》由会员分享，可在线阅读，更多相关《数据结构数组和广义表（48页珍藏版）》请在金锄头文库上搜索。
1、第五章数组和广义表n教学目的n通过本章的学习，要求学生了解数组及广义 表的定义，掌握数组的存储结构n5.1 数组的定义n5.2 数组的顺序表示和实现n5.3 矩阵的压缩存储5.3.1 特殊矩阵5.3.2 稀疏矩阵n重点：数组的两种存储表示方式及元素存储 地址的计算公式；特殊矩阵和稀疏矩阵的压 缩存储方法； n难点：特殊矩阵和稀疏矩阵的压缩存储方法 及运算的实现。n数组可看成是一种特殊的线性表，其特殊在于，表中的 数据元素本身也是一种线性表。 5.1 数组的定义数组是我们最熟悉的数据类型，在早期的高级语言 中，数组是唯一可供使用的数据类型。由于数组中各元 素具有统一的类型，并且数组元素的下标一般
2、具有固定 的上界和下界，因此，数组的处理比其它复杂的结构更 为简单。多维数组是向量的推广。例如，二维数组：a00 a01 a0,n-1a10 a11 a1,n-1 am-1,1 am-1,2 am-1,n-1 在C语言中，一个二维数组类型可以定义 为其分量类型为一维数组类型的一维数组类 型.也就是说，typedef elemtype array2mn;等价于：typedef elemtype array1n;typedef array1 array2m;数组一旦被定义，它的维数和维界就不再改变。 因此，除了结构的初始化和销毁之外，数组只有 存取元素和修改元素值的操作。同理，三维数组类型可以定义
3、为其数据元素为二 维数组类型的一维数组类型。数组的抽象数据类型定义ADT Array 数据对象：ji=0,bi-1 i=1,2,nD=aj1j2jn|n称为数组的维数, bi称为第i维的长度数据关系：R=R1,R2,RnRi=| 0 jkbk-1,1 k n,且ki, 0 jibi-2, i=2,n 基本操作： 二维数组的抽象数据类型定义ADT TArray D=ai,j|ai,jElemType， R=R1,R2R1=Row= R2=Col= 0ib1-10jb2-10ib1-10 jb2-10 ib1-10jb2-1a00, ,a0,b2-1. . . . ab1-1,0,ab1-1,b2
4、-1（下标 ， 元素）（i ， ai ）（(i,j) , ai,j ） （(j1jn)， aj1jn ）基本操作nInitArray(for(int j = 0;jscore.GetLength(1);j+)/score.GetLength(1)方法可以获得第二维的长度sum = sum + scorei,j;return sum;static void Main() int, score = new int10,3;for (int i = 0; i 10; i+)for (int j = 0; j 3; j+)scorei,j = (i + 1) * (j + 1);/为第i个学生的第j门
5、课赋 值Console.Write(scorei,j.ToString()+“ “);Console.WriteLine();for (int i = 0; i 10; i+)int sum = Student_Sum(score, i);Console.WriteLine(“第0位同学的总分是 1“,i+1,sum);Console.ReadLine(); 求第j门课程总分数的算法为：static public int Course_Sum(int, score, int j)int sum = 0;for (int i = 0; i score.GetLength(0); i+)sum +
6、= scorei, j;return sum;5.3 矩阵的压缩存储n矩阵是数值计算程序设计中经常用到的数学模型， 它是由 m 行和 n 列的数值构成（当m=n 时称为方 阵）。n在高级程序设计语言中，通常用二维数组表示矩阵 。n然而在数值分析过程中经常遇到一些比较特殊的矩 阵，它们的阶数很高，矩阵中元素数量很大，而且 有很多元素的值相同或零值元素，如对称矩阵、三 角矩阵、带状矩阵和稀疏矩阵等。n为了节省存储空间并且加快处理速度，需要对这类 矩阵进行压缩存储，压缩存储的原则是：不重复存不重复存 储相同元素；不存储零值元素储相同元素；不存储零值元素。特殊矩阵的压缩存储方法n n特殊矩阵是指非零元
7、素或零元素的分布有一特殊矩阵是指非零元素或零元素的分布有一 定规律的矩阵。主要形式有对称矩阵、三角定规律的矩阵。主要形式有对称矩阵、三角 矩阵、对角矩阵等矩阵、对角矩阵等。 1 1、对称矩阵的压缩存储、对称矩阵的压缩存储 对称矩阵是一个n阶方阵。若一个n阶矩阵A中的元素满足 : ai,j=aj,i (0i，jn-1)，则称A为n阶对称矩阵。1 5 1 3 7 a005 0 8 0 0 a10 a 111 8 9 2 6 a20 a21 a233 0 2 5 1 .7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-11 5 1 3 7 a005 0 8 0 0 a
8、10 a 111 8 9 2 6 a20 a21 a233 0 2 5 1 .7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1a00a10a11a20a21a23an-1n-1an-1n-3an-1n-2Sa数组只需存储 n(n+1)/2 个元素共n(n+1)/2个元素012345n(n+1)/2-1由于对称矩阵中的元素关于主对角线对称，因此可以为 每一对对称的矩阵元素分配 1 个存储空间，n阶矩阵中 的nn个元素就可以被压缩到 n(n+1)/2 个元素的存储空 间中去。 称一维数组San(n+1)/2 为n 阶对称矩阵A的压缩存储矩阵中的元素Aij和Sak
9、的关系？ki(i+1)/2+j 当ij j(j+1)/2+i 当ij 当Aij为下三角中的元素时（即ij ）：此元素前共有i行按照下三角存储的元素， Aij所处列之 前共有j个元素 当Aij为上三角中的与元素时（即ij ）：和此元素对应相等的元素为Aji，此时Aji为下三角元素稀疏矩阵的压缩存储 n如果一个矩阵中有很多元素的值为零，即零元素的 个数远远大于非零元素的个数时，称该矩阵为稀疏 矩阵稀疏因子若m行n列的矩阵中含有t个非零元素 则称： 为稀疏因子问题？通常认为稀疏因子0.05的矩阵为稀疏矩阵零值元素占用空间很大计算中进行了很多零值运算t mn解决问题的原则n尽可能少存或者不存零值元素n
10、尽可能减少没有实际意义的运算n运算方便，即：n能尽可能快的找到与下标值(i,j)对应的元素n能尽可能快地找到同一行或同一列的非零值元使用A67的数组存储？行列值 (0,2,1) (1,1,2) (2,0,3) (3,3,5) (4,4,6) (5,5,7) (5,6,4)三元组表示法n三元组表示法就是在存储非零元的同时，存储该元 素所对应的行下标和列下标。稀疏矩阵中的每一个 非零元素由一个三元组(i，j，aij)唯一确定。矩阵中 所有非零元素存放在由三元组组成的数组中。三元组表中的第一行分别表示稀疏矩 阵A的行数、列数和非零元的个数。 显然，非零元素的三元组是按行号递 增的顺序、相同行号的三元
11、组按列号 递增的顺序排列的。n三元组顺序表假设以行序为主序，且以一维数组作为三元组表 的存储结构，可以得到稀疏矩阵的一种压缩存储 方法，称为三元组顺序表。三元组顺序表的数据 结构定义如下：public class MatrixNode /三元组结点类private int row; /行号private int col; /列号private int item; /元素值public class TsMatrix /三元组类public int Rows; /矩阵总行数public int Cols; /矩阵总列数private int nums; /三元组个数public MatrixNod
12、e Data; /三元组表1稀疏矩阵的转置运算n转置是矩阵中最简单的一种运算。0 1 0 0 4 0 2 0 0 0 0 0 0 0 0 5 0 2 0 0 0 0 6 1A46=0 2 0 0 1 0 0 0 0 0 0 0 0 0 5 0 4 0 0 6 0 0 2 1B64=转置后对于一个mn的矩阵其转置矩阵是一个nm的矩 阵，设为Bnm 且满足aij=bji 即：aij=bji，其中：0im-1，0jn-1即A的行是B的列，A的列是B的行。0 1 0 0 4 0 2 0 0 0 0 0 0 0 0 5 0 2 0 0 0 0 6 1A46=0 2 0 0 1 0 0 0 0 0 0 0
13、 0 0 5 0 4 0 0 6 0 0 2 1B64=行列值 (0,1,1) (0,4,4) (1,0,2) (2,3,5) (2,5,2) (3,4,6) (3,5,1)(1,0,1) (4,0,4) (0,1,2) (3,2,5) (5,2,2) (4,3,6) (5,3,1) 行下标列下标互换 (0,1,2) (1,0,1) (3,2,5) (4,0,4) (4,3,6) (5,2,2) (5,3,1)以行下标为主序 n矩阵A是按行序为主序存储的，若按列序为主序进 行转置就可以得到A阵的转置矩阵B。n算法思想1：在存储三元组的数组Ma中按三元组的 列域cols的值开始扫描每一个三元组，
14、从第0列至第 n-1列，依序将三元组列域与行域之值对换，并顺次 存人数组Mb中。public void TransPose(TsMatrix mb) /初始化转置三元组，使得长度相等，行数变为列数，列数变为行数mb.nums = this.nums; mb.Cols = this.Rows;mb.Rows = this.Cols; int index = 0;/三元组下标if (mb.nums != 0)/若mb.nums为没有转置的必要for (int i = 0; i this.Cols; i+)/从矩阵A的列值开始for (int j = 0; j this.nums; j+)/比较每一个三元组，看是否是第i列的(即矩阵B的第i行)if (this.Dataj.Col = i)/如果此三元组属于第i列，开始置换
