十字链表存储稀疏矩阵

发表于   |   分类于

除了三元组之外, 还可以用十字链表存储稀疏矩阵.

一. 十字链表的本质

  • 首先十字链表有一行头指针(RHead), 和一列头指针(CHead), 它们都可以保存一个结点的地址(PointPtr)
  • 每个结点保存以下信息: 行号(i), 列号(j), 值(v), 下方结点(down), 右方结点(right)
  • 初始化的时候, 各头指针的值都是 NULL
  • 可以把每一行, 每一列都看成是一个链表
  • 当插入元素的时候, 假设元素的位置是(i, j), 先确定它在第 i 行链表的位置, 再确定它在第 j 列链表的位置
  • 这样就构造出了一个十字链表

二. 结点和整个矩阵的设计

1. 结点的设计

根据每个结点需要保存的信息, 可以知道结点应该如下:

1
2
3
4
5
6
//设计结点
typedef struct point
{
    int i, j, v;    //行号, 列号, 值
    struct point * right, * down;    //右侧元素, 下方元素
}Point, *PointPtr;

2. 矩阵的设计

矩阵肯定包括行数(mu), 列数(nu), 非零元素个数(tu), 而且还需要一行(RHead)和一列头指针(CHead), 每个头指针所包含的元素类型都是一样的, 所以一行和一列头指针可以分别用数组保存起来.

由于事先不知道数组的长度, 所以这两个数组应该是动态分配的.

动态分配之后肯定是赋值给指针, 那么是什么类型的指针呢?
答案是: 因为元素类型是 PointPtr , 所以是 PointPtr * 类型的.

那么问题又来了, 为什么元素类型是 PointPtr 的呢?
因为结点是 Point 类型的, 而动态分配结点的返回值是 PointPtr 类型的.
(头指针保存一个结点的地址, 结点又保存下一个结点的地址)

1
2
3
4
5
typedef struct 
{
    int mu, nu, tu;    //稀疏矩阵的行数, 列数, 元素个数
    PointPtr * Rhead, * Chead;    //两个指针数组
}TenList;

三. 矩阵的初始化

1. 输入矩阵的信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
do
    {
        flag = 0;
        printf("请输入行数, 列数, 非零元素个数: \n");
        scanf("%d %d %d", &mu, &nu, &tu);
        //输入行数, 列数, 个数, 保证输入无误
        if(mu<0 || nu<0 || tu<0 || tu>mu*nu)
        {
            flag = 1;
        }
    }while(flag);

    //保存稀疏矩阵的行数, 列数, 非零元素个数
    T->mu = mu;
    T->nu = nu;
    T->tu = tu;

2. 初始化各头指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//分配两个指针数组
T->Rhead = malloc(sizeof(PointPtr)*(mu+1));    //Rhead 是竖的
if(!T->Rhead)    exit(1);
T->Chead = malloc(sizeof(PointPtr)*(nu+1));    //Chead 是横的
if(!T->Chead)    exit(1);

//初始化每个头指针
for(k=1; k<=mu; k++)
{
    T->Rhead[k] = NULL;
}
for(k=1; k<=nu; k++)
{
    T->Chead[k] = NULL;
    }

3. 插入元素

根据元素个数循环:

1
for(k=1; k<=tu; k++)

然后输入元素, 确保元素的行号, 列号无误之后, 动态分配一个新结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
do
{
    flag = 0;
    printf("请输入结点的行号, 列号与值: \n");
    scanf("%d %d %d", &i, &j, &v);
    //确保行号, 列号无误
    if(i<=0 || j<=0)
    {
        flag = 1;
    }
}while(flag);

//动态分配一个结点, 并给结点赋值
temp = malloc(sizeof(Point));
temp->i = i;
temp->j = j;
temp->v = v;

至此, 得到了一个新的结点, 然后就到了重点: 在十字链表中插入这个结点.
插入一个结点(i, j), 首先在第 i 行链表中插入, 然后在第 j 列链表中插入. 对我而言还是有点难理解, 但就是这样做的.

在某一行链表中插入, 有两种情况, 一种是链表还没有结点, 直接插入. 还有一种是链表已经有了结点, 在合适的地方插入新结点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//先确定新结点在某一行中的位置
//如果头指针保存的是 NULL, 说明这一行还没有元素, 则进行 if 里面的操作
//如果头指针已经指向某个元素, 并且该元素的列号大于新元素的列号
//说明新元素应该放在它的前面, 同样进行 if 里面的操作 
if(T->Rhead[i]==NULL || T->Rhead[i]->j>j)
{
    temp->right = T->Rhead[i];    //新结点指向头结点的所指向的元素
    T->Rhead[i] = temp;    //头结点就指向新结点
}
else
{
    //如果新结点不是插在行首, 那么就寻找合适的位置
    //从行首元素开始查看, 如果遍历到了行尾就插在最后
    //遍历的过程中如果发现某个元素的下一个元素的列号比新结点的小
    //那么就插在这两个元素中间
    //插入的方式都是: 新结点的右指针等于 p 元素的右指针
    //然后 p 元素的右指针等于新结点, 完成插入
    for(p=T->Rhead[i]; p->right!=NULL&&p->right->j<j; p=p->right);
    temp->right = p->right;
    p->right = temp;
}

在某一列中插入结点的方法跟上面很相似:

1
2
3
4
5
6
7
8
9
10
11
if(T->Chead[j]==NULL || T->Chead[j]->i>i)
        {
            temp->down = T->Chead[j];
            T->Chead[j] = temp;
        }
        else
        {
            for(p=T->Chead[j]; p->down!=NULL && p->down->i<i; p=p->down);
            temp->down = p->down;
            p->down = temp;
        }

四. 完整代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdlib.h>

//设计结点
typedef struct point
{
    int i, j, v;    //行号, 列号, 值
    struct point * right, * down;    //右侧元素, 下方元素
}Point, *PointPtr;


//首先数组的元素保存的是结点的地址(结点是动态分配的, 通过地址来访问)
//数组元素是 PointPtr, 而这个数组又是动态分配的(因为事先不知道数组有多长), 动态分配返回的类型应该是 PointPtr *.
typedef struct 
{
    int mu, nu, tu;    //稀疏矩阵的行数, 列数, 元素个数
    PointPtr * Rhead, * Chead;    //一行头指针, 一列头指针, 它们都是两个数组
}TenList;

int CreateTenList(TenList * T);    //创建十字链表
void PrintTenList(TenList * T);    //输出非零元素的位置与值

int main(int argc, char const *argv[])
{
    TenList T;
    CreateTenList(&T);
    PrintTenList(&T);
    
    return 0;
}

int CreateTenList(TenList * T)
{
    int mu, nu, tu, flag, k, i, j, v;
    //mu:行数; nu:列数; tu:个数; flag:保证输入无误; k:用于循环; i,j,v:元素的行号, 列号, 值
    PointPtr temp, p;
    //temp:新结点; P:用来遍历链表的行或列

    do
    {
        flag = 0;
        printf("请输入行数, 列数, 非零元素个数: \n");
        scanf("%d %d %d", &mu, &nu, &tu);
        //输入行数, 列数, 个数, 保证输入无误
        if(mu<0 || nu<0 || tu<0 || tu>mu*nu)
        {
            flag = 1;
        }
    }while(flag);

    //保存稀疏矩阵的行数, 列数, 非零元素个数
    T->mu = mu;
    T->nu = nu;
    T->tu = tu;

    //分配一行/列头指针
    T->Rhead = malloc(sizeof(PointPtr)*(mu+1));    //Rhead 是竖的
    if(!T->Rhead)    exit(1);
    T->Chead = malloc(sizeof(PointPtr)*(nu+1));    //Chead 是横的
    if(!T->Chead)    exit(1);

    //初始化每个头指针
    for(k=1; k<=mu; k++)
    {
        T->Rhead[k] = NULL;
    }
    for(k=1; k<=nu; k++)
    {
        T->Chead[k] = NULL;
    }

    //输入结点, 并插入矩阵中
    for(k=1; k<=tu; k++)
    {
        do
        {
            flag = 0;
            printf("请输入结点的行号, 列号与值: \n");
            scanf("%d %d %d", &i, &j, &v);
            //确保行号, 列号无误
            if(i<=0 || j<=0)
            {
                flag = 1;
            }
        }while(flag);

        //动态分配一个结点, 并给结点赋值
        temp = malloc(sizeof(Point));
        temp->i = i;
        temp->j = j;
        temp->v = v;

        //先确定新结点在行中的位置
        //如果头指针保存的是 NULL, 说明这一行还没有元素, 则进行以下操作
        //如果头指针指向某个元素, 并且该元素的列号大于新元素的列号
        //说明新元素应该放在它的前面, 同样进行以下操作 
        if(T->Rhead[i]==NULL || T->Rhead[i]->j>j)
        {
            temp->right = T->Rhead[i];    //新结点指向头结点的所指向的元素
            T->Rhead[i] = temp;    //头结点就指向新结点
        }
        else
        {
            //如果新结点不是插在行首, 那么就寻找合适的位置
            //从行首元素开始查看, 如果遍历到了行尾就插在最后
            //遍历的过程中如果发现某个元素的下一个元素的列号比新结点的小
            //那么就插在这两个元素中间
            //插入过程都是 新结点的右指针等于 p 元素的右指针
            //然后 p 元素的右指针等于新结点, 完成插入
            for(p=T->Rhead[i]; p->right!=NULL&&p->right->j<j; p=p->right);
            temp->right = p->right;
            p->right = temp;
        }

        if(T->Chead[j]==NULL || T->Chead[j]->i>i)
        {
            temp->down = T->Chead[j];
            T->Chead[j] = temp;
        }
        else
        {
            for(p=T->Chead[j]; p->down!=NULL && p->down->i<i; p=p->down);
            temp->down = p->down;
            p->down = temp;
        }
    }

    

    return 1;
}

void PrintTenList(TenList * T)
{
    int i;
    PointPtr temp;
    for(i=1; i<=T->mu; i++)
    {
        temp = T->Rhead[i];
        while(temp!=NULL)
        {
            printf("%2d %2d %2d\n", temp->i, temp->j, temp->v);
            temp = temp->right;
        }
    }
}

五. 参考文章

稀疏矩阵的十字链表存储的思路