C++实现基于十字链表的稀疏矩阵的转置_基于十字链的压缩存储转置

使用的数据结构

十字链表的定义如下:

typedef struct node {
 int i, j;//行号，列号
 int e;//存储的数据
 struct node *right, *down;//right,down分别为行指针和列指针
}OLNode;
1
2
3
4
5

通过上述定义创建下图所示的十字链表结点:

基于十字链表存储的稀疏矩阵的创建这里不做详细讲解，这里只展示本人创建的示例:

转置算法的思路

矩阵转置实现的核心思想：将原矩阵的行变成列，列变成行，即仅通过改变结点的行列号以及对每个结点的指向进行改变从而得到转置后的矩阵，这里我用了一个例子来解释。

第一步：将矩阵中元素的行，列号交换并将其行指针与列指针指向的地址交换。如:

第2步：将十字链表中的行头结点和列头结点的行，纵坐标交换并将其行，列指针指向的值交换，结果如下:

第3步：将总头结点的行，列号值交换并将其行，列号指针指向的值交换，如图:

结果演示

经过以上三步就完成了对原矩阵的转置，而且并不需要进行结点的删增加等操作，最终的效果如图所示:

程序运行结果如下:

说明:本人是从文件中读取的数据，并将结果保存到另一个文件中。

矩阵转置实现代码

void swap(int &i, int &j)//交换
{
 int temp;
 temp = i;
 i = j;
 j = temp;
}
void Transposition(OLNode &s)//十字链表的转置
{
 OLNode *p, *save, *temp;
 //将原十字链表中的元素的行坐标和列坐标，行指针和列指针交换
 for (int i = 0; i < s.i; i++)
 {
  p = s.down[i].right;
  while (p != &s.down[i])
  {
   swap(p->i, p->j);
   save = p;
   p = p->right;
   temp = save->right;
   save->right = save->down;
   save->down = temp;
  }
 }
 //将列头结点的行,列坐标以及行指针和列指针交换
 for (int i = 0; i < s.j; i++)
 {
  swap(s.right[i].i, s.right[i].j);
  temp = s.right[i].right;
  s.right[i].right = s.right[i].down;
  s.right[i].down = temp;
 }
 //将行头结点的行,列坐标以及行指针和列指针交换
 for (int i = 0; i < s.i; i++)
 {
  swap(s.down[i].i, s.down[i].j);
  temp = s.down[i].right;
  s.down[i].right = s.down[i].down;
  s.down[i].down = temp;
 }
 //将总头结点的行指针和列指针以及
 temp = s.right;
 s.right = s.down;
 s.down = temp;
 swap(s.i, s.j);
}
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

以上便是本文的全部内容，如果觉得好的话就点个赞吧！！！