[广义表](3)十字链表
十字链表
当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表，例如，在作：“将矩阵B加到矩阵A上”的操作时，由于非零元的插入或删除将会引起A.data中元素的移动，为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。
在链表中，每个非零元可用一个含5个域的结点表示，其中i、j和e这3个域分别表示该非零元所在的行、列和非零元的值。
向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元，同一行的非零元通过right域链接成为一个线性链表，同一列的非零元通过down域链接成一个线性链表
每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点
整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之，如矩阵M的十字链表示意图如下所示：
以下是三元十字链的测试代码，包括：构造十字链，由行列打印三元十字链的三元表，通过三元十字链打印二维矩阵：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int i, j;//该非零元的行和列下标
int e;
struct OLNode* right, * down;//该非零元所在行表和列表的后继链域
}OLNode, * OLink;
typedef struct
{
OLink* rhead, * chead;//行和列链表头指针向量基址由CreateSMatrix分配
int mu, nu, tu;//稀疏矩阵的行数、列数和非零元个数
}CrossList;
int CreateSMatrix_OL(CrossList* M);//插入
int RowPrint(CrossList* M);//按行打印
int ColPrint(CrossList* M);//按列打印
int PrintArray(CrossList* M);//按三元十字链来打印二维数组
int main()
{
CrossList L;
CreateSMatrix_OL(&L);
ColPrint(&L);
PrintArray(&L);
return 0;
}
int CreateSMatrix_OL(CrossList* M)
{
/*if (M!= NULL)
{
free(M);
}
*/
int m, n, t;
printf("请依次输入矩阵的行数、列数、非零元个数：");
scanf("%d,%d,%d", &m, &n, &t);
M->chead = (OLink*)malloc(sizeof(OLink) * (m + 1));
M->mu = m;
M->nu = n;
M->tu = 0;
if (M->chead == NULL)
{
return -1;
}
M->rhead = (OLink*)malloc(sizeof(OLink) * (n + 1));
if (M->rhead == NULL)
{
return -1;
}
for (int i = 0; i < m; i++)
{
M->chead[i] = NULL;
M->chead[i] = NULL;
}
for (int j = 0; j < n; j++)
{
M->rhead[j] = NULL;
M->rhead[j] = NULL;
}
OLink p, s, s1;
int i, j, e, count;
printf("\n请依次输入行数、列数、非零元值：");
scanf("%d,%d,%d", &i, &j, &e);
while (i < m && j < n)
{
count = 1;
if (e == 0)//输入0无效
{
count = 0;
}
else
{
p = (OLink)malloc(sizeof(OLNode));
p->i = i; p->j = j, p->e = e;
s = M->chead[i];
s1 = s;//跟着指针s
if (M->chead[i] == NULL)
{
p->right = M->chead[i];
M->chead[i] = p;
}
if (M->rhead[j] == NULL)
{
p->down = M->rhead[j];
M->rhead[j] = p;
}
else
{
//插入行表
while (s->right != NULL)
{
if (s->j >= j)
{
break;
}
s1 = s;
s = s->right;
}
if (s->j > j)
{
p->right = s1->right;
s1->right = p;
}
else
{
s->e = e;
count = 0;
}
s = M->rhead[j];
//插入列表
while (s->down != NULL)
{
if (s->i >= i)
{
break;
}
s1 = s;
s = s->down;
}
if (s->i > i)
{
p->down = s1->down;
s1->down = p;
}
else
{
s->e = e;
}
}
}
//如果count=0的话，就是代表遇到同行同列，则覆盖，不需要总元素先加
if (count)
{
M->tu++;
}
//当总添加元素小于输入值的时候，继续添加
if (M->tu < t)
{
printf("\n请依次输入行数、列数、非零元值：");
scanf("%d,%d,%d", &i, &j, &e);
}
else
{
break;
}
}
system("pause");
}
int RowPrint(CrossList* M)
{
int i = 0;
OLink p;
while (i < M->mu)
{
p = M->chead[i];
while (p != NULL)
{
printf("%d,%d,%d\n", p->i, p->j, p->e);
p = p->right;
}
i++;
}
return 1;
}
int ColPrint(CrossList* M)
{
int i = 0;
OLink p;
while (i < M->nu)
{
p = M->rhead[i];
while (p != NULL)
{
printf("%d,%d,%d\n", p->i, p->j, p->e);
p = p->down;
}
i++;
}
return 1;
}
int PrintArray(CrossList* M)
{
char** Array;
OLink p;
Array = (char**)malloc(sizeof(char*) * (M->mu + 1));//加+放置内存溢出
for (int i = 0; i < M->mu; i++)
{
Array[i] = (char*)malloc(sizeof(char) * (M->nu + 1));
for (int k = 0; k < M->nu; k++)
{
Array[i][k] = 0;
}
}
for (int j = 0; j < M->mu; j++)
{
p = M->chead[j];
while (p != NULL)
{
Array[p->i][p->j] = p->e;
p = p->right;
}
}
for (int i = 0; i < M->mu; i++)
{
for (int j = 0; j < M->nu; j++)
{
printf("%d", Array[i][j]);
}
printf("\n");
}
}对于m行n列且有t个非零元的稀疏矩阵，上述代码中的CreateSMatrix_OL的时间复杂度为O(t*s),s=max{m,n}，这是因为每建立一个非零元的结点时都要寻查它在行表和列表中的插入位置。
下边是在三元十字链中两矩阵相加，因为矩阵中每个非零元有两个变元(行值和列值)，每个结点既在行表中又在列表中，致使插入和删除时指针的修改稍微复杂，故需要更多的辅助指针。
假设两个矩阵相加后的结果为A'，则和矩阵A'中的非零元a(ij)'只可能有三种情况：
- 它或是a(ij)+b(ij)
- 或是a(ij)(b(ij)=0时)
- 或是b(ij)(a(ij)=0时)
由此，当B加到A上去的时候，对A矩阵的十字链表来说
- 或是改变结点的val域值(a(ij)+b(ij)!=0)
- 或者不变(b(ij)=0)
- 或者插入一个新的结点(a(ij)=0)
- 还有一种可能的情况：和A矩阵中的某个非零元相对应，和矩阵A'中是零元，则对A的操作是删除一个结点(a(ij)+b(ij)=0)
由此，整个运算过程可从矩阵的第一行起逐行进行，对每一行都从行表头出发分别找到A和B在该行中的第一个非零元结点后开始比较，然后按上述四种情况分别处理之
同时要注意的是，在删除和添加的结点的时候，同时也要修改列表的结点，有一点需要特别注意，由于在行中删除结点后，还需要在列中删除该结点，则free结点应该在对列操作中进行
同时，在复制B的行表中的每个结点的时候，每次使用完需要free空间，避免出现脏内存来导致数据的不准确
思路就是拿B表去遍历B表，对应上述情况来进行操作.
Status Add_toTSMatrix(CrossList* A,CrossList *B)
{
if (A->mu != B->mu || A->nu != B->nu)
return ERROR;
//拿B遍历A
for (int i = 0; i < B->mu; i++)
{
OLink p = B->rhead[i];
while(p!=NULL)
{
OLink node = (OLink)malloc(sizeof(OLNode));
OLink AR = A->rhead[i]; OLink AD = A->chead[p->y];
node->x = p->x; node->y = p->y; node->e = p->e; node->down = NULL; node->right = NULL;
if (!AR || AR->y > node->y)//A中行无此结点
{
node->right = A->rhead[i];//插入后需要在列中插入
A->rhead[i] = node;
if (!AD || AD->x > node->x)
{
node->down = A->chead[p->y];
A->chead[p->y] = node;
}
else
{
OLink ADr = NULL;
while (AD)
{
if (AD->x > node->x)
break;
ADr = AD;
AD = AD->down;
}
node->down = AD;
ADr->down = node;
}
A->tu++;
}
else
{
OLink ARr = NULL;
while (AR)
{
if (AR->y >= p->y)
break;
ARr = AR;
AR = AR->right;
}
if (AR && AR->y == node->y)
{
if (AR->e + node->e != 0)
{
AR->e = AR->e + node->e;
}
else//等于0的情况需要删除结点
{
//删除需要考虑是否在头端
if (ARr == NULL)//删除在头端
{
A->rhead[i] = A->rhead[i]->right;
}
else
{
ARr->right = AR->right;
}
/*删除在行中的结点后还需要删除在列中的结点*/
OLink ADr = NULL;
while (AD)
{
if (AD->x == node->x)
break;
ADr = AD;
AD = AD->down;
}
if (ADr == NULL)
{
A->chead[p->y] = A->chead[p->y]->down;
free(AD); AD = NULL;
}
else
{
ADr->down = AD->down;
free(AD); AD = NULL;
}
A->tu--;
}
}
else
{
ARr->right = node;
node->right = AR;
if (!AD || AD->x > p->x)
{
node->down = A->chead[p->y];
A->chead[p->y] = node;
}
else
{
OLink ADr = NULL;
while (AD)
{
if (AD->x > node->x)
break;
ADr = AD;
AD = AD->down;
}
ADr->down = node;
node->down = AD;
}
A->tu++;
}
}
node = NULL;
p = p->right;
}
}
PrintRowMatrix(*A);
printf("\n");
PrintColMatrix(*A);
return OK;
}通过对这个算法的分析可以得出下列结论：
- 从一个结点来看，进行比较、修改指针所需的时间是一个常数；
- 整个运算过程在于A和B的十字链表逐行扫描，其循环次数主要取决于A和B矩阵中非零元的个数ta和tb，由此算法的时间复杂度为O(ta+tb)