摘要 多维数组和广义表属于数据结构中非线性结构的基础内容。虽然较线性结构相对复杂,但是,从其递归意义上来说,组成它们的基础也是线性数据结构。本文主要以稀疏矩阵为代表探讨多维数组和广义表数据结构的存储和计算。

多维数组和广义表

多维数组可以理解为一维数组里的数据元素是一维或者多维数组,通过降维处理可以简化分析。

广义表包含表头和表尾,表头可以原子也可以是列表,表尾是由表中除表头以外的所有元素构成的子表,因此表尾一定是列表。

广义表从递归意义上也可以理解为线性表中的数据元素是普通元素或者是嵌套的线性表。

多维数组从存储习惯上主要分为按行存储和按列存储,其中C和C++以及JAVA等主流语言都是按行存储,FORTRAN语言采用按列存储的原则,按行存储,只需要先变最右边的下标即可;反之,按列存储只需要先改变最左边的下标即可。对于已知三维数组长宽高分别为m,n,l,数组基址a[0][0][0]为loc(a[0][0][0]),如何求a[i][j][k]的地址。

loc(a[i][j][k]) = loc(a[0][0][0]) + (k*m*n+j*m+i)*d

稀疏矩阵的存储

多维数组实际上就是矩阵,只是在科学计算领域,矩阵有着特殊含义。

在一个矩阵中,如果非零元素的个数远小于零元素的个数,我们称之为稀疏矩阵。

对于稀疏矩阵的存储,我们不用像普通多维数组那样,为所有的元素分配内存空间,而把注意力放在非零元的存储问题上。

下面介绍两种稀疏矩阵的存储方法,一种顺序存储方式表现为三元组表,另一种属于链式存储方式,即十字链表

三元组表

三元组表为稀疏矩阵的顺序存储方式,稀疏矩阵中的每一个非零元都表现为一个三元组,包含该非零元所在行号,所在列号,以及非零元的值。

整个稀疏矩阵只存储所有的非零元,是一个三元组顺序表,其属性包含三元组数组,稀疏矩阵行数,列数以及非零元个数。

下面分别是三元组类型定义个稀疏矩阵三元组表的类型定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class SeqMatrix{
public static final int MAX_ELE_NUM = 100;

private class TriNode{
private int i;
private int j;
private int e;
}

private TriNode data[] = null;

private int rowNum;
private int colNum;
private int count;

public SeqMatrix(){
data = new TriNode[MAX_ELE_NUM];
}

public SeqMatrix(int rowNum, int colNum, int count){
data = new TriNode[MAX_ELE_NUM];
this.rowNum = rowNum;
this.colNum = colNum;
if(count > MAX_ELE_NUM){
System.out.println("the element is too much!");
System.exit(-1);
}
this.count = count;
System.out.println("the row num is "+rowNum+", the col num is "+colNum+", the element num is "+count);
}
}

三元组表的定义类似于顺序表,底层也是数组实现,下面采用接收用户输入的方式创建三元组表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void create(){
System.out.println("please input trinode:\ni j e");
BufferedReader br = null;
try{
br = new BufferedReader(new InputStreamReader(System.in));
for(int t=0; t<count; t++){
String inputStr = br.readLine();
if(inputStr != null && inputStr.split(" ").length == 3){
String strs[] = inputStr.split(" ");

int i = Integer.parseInt(strs[0]);
int j = Integer.parseInt(strs[1]);
int e = Integer.parseInt(strs[2]);

if(i<1 || i>rowNum || j<1 || j>colNum){
System.out.println("Your input is wrong!");
System.exit(-1);
}

data[t] = new TriNode();
data[t].i = i-1;
data[t].j = j-1;
data[t].e = e;
}
}
getRowOrderMatrix();
}catch(Exception e){
e.printStackTrace();
}
}

注意以上代码中,待用户输入完所有三元组后,调用了一个getRowOrderMatrix函数目的是为了将其转换为按行有序,而三元组按行有序排列是为了便于后续的转置等运算。

下面是转换成按行有序的程序代码,先以行号排列,如果行号相等,再以列号排列,注意下面采用的是冒泡排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void getRowOrderMatrix(){
for(int t=0; t<count-1; t++){
for(int x=count-t-1; x>= 1; x--){
if(data[x].i < data[x-1].i){
TriNode temp = data[x];
data[x] = data[x-1];
data[x-1] = temp;
}
}
}

for(int t=0; t<count-1; t++){
for(int x=count-t-1; x>= 1; x--){
if(data[x].i == data[x-1].i && data[x].j < data[x-1].j){
TriNode temp = data[x];
data[x] = data[x-1];
data[x-1] = temp;
}
}
}
}

例如本程序定义一个三元组表,用户按以下顺序输入三元组2 2 1,2 1 2,1 2 3。经过按行排序之后,三元组表为1 2 3,2 1 2,2 2 1。三元组表按行排序之后,我们就可以对其方便的进行转置操作了。一个矩阵经转置之后,原始矩阵中的第i行变成转置矩阵的第i列。

即矩阵中行列数互换,每一个元素行列号互换。稀疏矩阵转置之后仍然是稀疏矩阵,为了保证转置之后的稀疏矩阵仍然是按行有序的。

这里我们选择对原始矩阵按列进行转置,原始矩阵的每一列就是转置矩阵的每一行,因此对原始矩阵按列运算,得到的转置矩阵就是按行有序的。

对原始矩阵的每一列,在三元组表中查找列号等于该列的元素,如果有的话,直接将其行列号互换,就得到了转置矩阵中的某一行非零元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public SeqMatrix transpose(){
SeqMatrix tMatrix = new SeqMatrix(colNum, rowNum, count);

if(tMatrix.count < 1)
return null;

int q = 0;
for(int col=0; col<this.colNum; col++){
for(int t=0; t<count; t++){
if(this.data[t].j == col){
tMatrix.data[q] = new TriNode();
tMatrix.data[q].i = this.data[t].j;
tMatrix.data[q].j = this.data[t].i;
tMatrix.data[q].e = this.data[t].e;
q++;
}
}
}

return tMatrix;
}

稀疏矩阵的三元组表存储方式比较易于理解,但不利于插入或改变某个非零元,如果要频繁地进行插入或删除非零元的工作,则需要采用链式存储方式,即下面要介绍的十字链表存储。

十字链表

在原有三元组的基础之上,再增加两个指针域right和down,构成五元组,right指向该行下一个五元组,down指向该列下一个五元组,这便是十字链表中的结点。同样十字链表除了具有稀疏矩阵行数,列数以及非零元个数之外,还需要维护一份行链表数组和列链表数组,因为稀疏矩阵的每一行和每一列都是一个链表,链表表头为该行或该列第一个非零元,因此行链表数组的大小是稀疏矩阵的行数,列链表数组的大小是稀疏矩阵的列数。下面是五元组和十字链表的定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class LinkMatrix{
private class LinkNode{
private int i;
private int j;
private int e;
private LinkNode right;
private LinkNode down;

public LinkNode(){

}

public LinkNode(int i, int j, int e, LinkNode right, LinkNode down){
this.i = i;
this.j = j;
this.e = e;
this.right = right;
this.down = down;
}
}

private LinkNode rHead[];
private LinkNode dHead[];
private int rowNum;
private int colNum;
private int count;

public LinkMatrix(){

}

public LinkMatrix(int rowNum, int colNum, int count){

this.rowNum = rowNum;
this.colNum = colNum;
this.count = count;
this.rHead = new LinkNode[rowNum];
this.dHead = new LinkNode[colNum];

}
}

下面以接收用户输入方式创建十字链表,十字链表的创建过程有点复杂,考察的是单链表的知识,因此,如果这里有什么不清楚的,再回过头去查看线性表中单链表的相关知识。下面是十字链表创建代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public void create(){
System.out.println("please input trinode:\ni j e");
BufferedReader br = null;
try{
br = new BufferedReader(new InputStreamReader(System.in));
for(int t=0; t<count; t++){
String inputStr = br.readLine();
if(inputStr != null && inputStr.split(" ").length == 3){
String strs[] = inputStr.split(" ");

int i = Integer.parseInt(strs[0])-1;
int j = Integer.parseInt(strs[1])-1;
int e = Integer.parseInt(strs[2]);

if(i<0 || i>rowNum-1 || j<0 || j>colNum-1){
System.out.println("Your input is wrong!");
System.exit(-1);
}

LinkNode s = new LinkNode(i,j,e,null,null);

if(this.rHead[i] == null || this.rHead[i].j > s.j){
s.right = this.rHead[i];
this.rHead[i] = s;
}else{
LinkNode p = this.rHead[i];//first row node
while(p.j < s.j){
p = p.right;
}
s.right = p.right;
p.right = s;
}


if(this.dHead[j] == null || this.rHead[j].i > s.i){
s.down = this.dHead[j];
this.dHead[j] = s;
}else{
LinkNode p = this.dHead[j];//first row node
while(p.i < s.i){
p = p.down;
}
s.down = p.down;
p.down = s;
}
}
}
}catch(Exception e){
e.printStackTrace();
}
}

接收用户收入将其转换成三元组,并实例化LinkNode是比较容易理解了,初始化时,right和down都为空,设新结点为s。

先构造行链表数组:

  • 如果s中行号所在的行链表即rHead[i]为空,说明这一行还没有非零元加入或者rHead[i].j > s.j说明这一行表头结点的列号大于用户新输入的三元组列号,这两种情况,都只需要将新结点直接加入表头即可,对应单链表的头插法。
  • 如果这两个条件都不满足,说明这一行已经有非零元,为了保证行链表中结点按列号有序,需要为新结点找到合适的插入位置,我们先获取表头结点赋值给工作结点p,只要p.j < s.j,继续让p = p.right,直到找到p的下一个结点列号大于用户输入的三元组列号,按照单链表中的插入结点方法,s.right = p.right;p.right = s。

再构造列链表数组:

  • 如果s中列号所在的行链表即dHead[j]为空,说明这一列还没有非零元加入或者dHead[j].i > s.i说明这一列表头结点的行号大于用户新输入的三元组行号,这两种情况,都只需要将新结点直接加入表头即可,对应单链表的头插法。
  • 如果这两个条件都不满足,说明这一列已经有非零元,为了保证列链表中结点按行号有序,需要为新结点找到合适的插入位置,我们先获取表头结点赋值给工作结点p,只要p.i < s.i,继续让p = p.down,直到找到p的下一个结点行号大于用户输入的三元组行号,按照单链表中的插入结点方法,s.down = p.down;p.down = s。

完成了行链表数组和链表数组的构建工作,也就完成十字链表的创建工作。

采用十字链表表示的稀疏矩阵的转置运算,主要也是在于行链表和列链表数组的调整,将之前的行链表数组调整为列链表数组,将之前的列链表数组调整为行链表数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public LinkMatrix transpose(){
LinkMatrix linkMatrix = new LinkMatrix(colNum, rowNum, count);

for(int i=0; i<rowNum; i++){
LinkNode p = this.rHead[i];
LinkNode r = new LinkNode(0,0,0,null,null);//rear node
while(p != null){
LinkNode q = new LinkNode(p.j,p.i,p.e,p.down,p.right);

if(linkMatrix.dHead[i] == null){
linkMatrix.dHead[i] = q;
}else{
r.down = q;
r = q;
}
p = p.right;
}
}

for(int i=0; i<colNum; i++){
LinkNode p = this.dHead[i];
LinkNode r = new LinkNode(0,0,0,null,null);//rear node
while(p != null){
LinkNode q = new LinkNode(p.j,p.i,p.e,p.down,p.right);

if(linkMatrix.rHead[i] == null){
linkMatrix.rHead[i] = q;
}else{
r.right = q;
r = q;
}
p = p.down;
}
}

return linkMatrix;
}

对原始稀疏矩阵行链表数组,将其转换为对应的转置矩阵的列链表数组。这里采用单链表尾插法构造。下面是本程序的测试类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class TestSMatrix{
public static void main(String[] args) {
System.out.println("text sequence matrix");
SeqMatrix seqMatrix = new SeqMatrix(3,2,3);
seqMatrix.create();
seqMatrix.print();
System.out.println("after transpose:");
SeqMatrix tSeqMatrix = seqMatrix.transpose();
tSeqMatrix.print();


System.out.println("text link matrix");
LinkMatrix linkMatrix = new LinkMatrix(3,2,3);
linkMatrix.create();
linkMatrix.print();
System.out.println("after transpose:");
LinkMatrix tLinkMatrix = linkMatrix.transpose();
tLinkMatrix.print();
}
}

程序输入和输出如下所示:

smatrix