第五章 数组的与广义表.ppt

public class Sparse1_ex { public static void main(String args[]) { int mat1[][]={{1,0,0,0}, //稀疏矩阵 {0,0,0,0}, {2,0,7,0}, {0,0,8,9}}; Sparse1 s1=new Sparse1(mat1); //一个对象表示一个稀疏矩阵 s1.output(); } } 【例5.2】 稀疏矩阵三元组的顺序存储结构。 程序运行结果如下： 稀疏矩阵: 1 0 0 0 0 0 0 0 2 0 7 0 0 0 8 9 稀疏矩阵三元组的顺序表示: 行下标 列下标 值 table[0] = 1 1 1 table[1] = 3 1 2 table[2] = 3 3 7 table[3] = 4 3 8 table[4] = 4 4 9 table[5] = null table[6] = null table[7] = null 【例5.2】 稀疏矩阵三元组的顺序存储结构。 顺序存储结构的稀疏矩阵有两个缺点： 数组长度不易设定，可能存在溢出与浪费问题。 插入、删除操作不方便。若矩阵元素的值发生变化，一个为零的元素变成非零元素，就要向线性表中插入一个三元组；若非零元素变成零元素，就要从线性表中删除一个三元组。为了保持线性表元素间的相对次序，进行插入和删除操作时，就必须移动元素。 （3） 三元组的链式存储结构 1．行的单链表示 将稀疏矩阵每行上的若干个非零元素作为结点链接成一个单向链表，每条链表第1个结点的引用存放在数组中。 常用的链式存储结构有两种：行（列）的单链表示和 十字链表示。 table 1 2 3 4 ^ column data next 1 1 ^ 1 2 3 8 3 7 ^ 4 9 ^ 图5.1 稀疏矩阵的行的单链表示 （3） 三元组的链式存储结构 其中，链表的每个结点由3个成员组成：column（列下标），data（值）和next（后继结点的引用）。Table数组元素存放每条链表第1个结点的引用。 声明稀疏矩阵以行的单链表示为如下的SparseNode2类： （3） 三元组的链式存储结构 下面的Sparse2类实现稀疏矩阵的行的单链表示，成员table是一个数组，元素类型为SparseNode2类。构造方法是将一个稀疏矩阵转换成行的单链表示。 public class Sparse2_ex { public static void main(String args[]) { int mat1[][]={{1,0,0,0}, {0,0,0,0}, {2,0,7,0}, {0,0,8,9}}; Sparse2 s1=new Sparse2(mat1); s1.output(); } } 【例5.3】 稀疏矩阵行的单链表示。 程序运行结果如下： 稀疏矩阵行的单链表示: table[0]=null table[1]= 1 1 - null table[2]=null table[3]= 1 2 - 3 7 - null table[4]= 3 8 - 4 9 - null 【例5.3】稀疏矩阵行的单链表示。 按行的单链表示的稀疏矩阵，每个结点可以很容易地 找到行的后继结点，但很难找到列的后继结点。为充分表示行和列的后继结点，可以采用十字链表示。 2．十字链表示 将行的单链表示和列的单链表示结合起来存储稀疏矩阵称为十字链表示。 1 2 3 4 ^ 1 2 3 4 ^ 1 1 1 ^ 3 3 7 ^ 4 3 8 ^ 4 4 9 ^ ^ 3 1 2 ^ 说明 每个结点表示一个非零元素。每个结点有5个成员：行下标，列下标，值，行后继引用以及列后继引用。 从行的角度看，需要一个数组存放行