一.介绍用十字链表保存稀疏矩阵，可以节约空间。
十字链表是多链表的一种，其节点分为两类：
类型1 :数据域是另一个单链表的头指针。
类型2 :数据域是要保存的数据。
其中，“十字”表示存储数据的每个节点都属于两个单链表，构成十字型。
十字链表表示的矩阵具有以下特点。
1、整体头部指针是指第一头部节点，该头部节点通常用于存储矩阵中的行数、列数和包含除0之外的元素的数量。
2 .从第一个头节点开始，分别横向、纵向展开两个单链表。 这两个链表中的每个节点都是类型1。
3、这两个链表的每个节点代表特定的行或列，引出一个链表。
4、用于保存矩阵元素的类型2的每个节点，属于某两种类型1的节点所提取的单链表。 这允许标记元素在矩阵中的特定位置。
二、实现. general.h :总声明。
# ifndef _ gen _ h _ # define _ gen _ h _ # include stdio.h # include stdbool.htypedefunsignedintction #endif LinkGen.h :交叉链接列表和基本遍历函数声明。
# ifndef _ link _ gen _ h _ # define _ link _ gen _ h _ # include '.general.h '/* structuredeclaration */enumton typedef struct GNode *GLink； 结构节点{ enum type tag； union { GLink head； 结构{ cursor row； Cursor column； 电子类型值； (}单元； (} region； Gpos轻型飞机； GPos down； (；/*在功能描述*///gposglocateright (glink start，Cursor subs )上向右遍历； //GPOSGlocatedown(GlinkStart，Cursor subs )向下遍历； #endif LinkGen.c :函数的实现。
# include ' link gen.h ' gposglocateright (glink开始，Cursor subs ) { GPos ptr=start； for(intI=0； i subs； I ) if (！ 返回空值(ptr-right )； else ptr=ptr-right； }返回ptr； }GPOSglocatedown(glinkstart，Cursor subs ) { GPos ptr=start； for(intI=0； i subs； I ) if (！ 返回空(ptr-down )； else ptr=ptr-down； }返回ptr； 声明(} Matrix.h )矩阵和相关函数。
# ifndef _ matrix _ h _ # define _ matrix _ h _ # include ' link gen.h '/* structuredeclaration */typedefglinkmatrink //插入矩阵中的元素boolinsertunit (矩阵，ElemType E，Cursor Row，Cursor Column )； //打印矩阵boolprintmatrix () matrixm； //放弃矩阵booldestroymatrix (矩阵)； #endif Matrix.c :函数的实现。
# include ' matrix.h ' matrixcreatematrix (cursor maxrow，Cursor MaxCol ) if (！ MaxRow ||！ 返回空值；/*原始节点* /矩阵=(矩阵)矩阵) sizeof (结构节点)； if (！ m )退出(exit _ failure )； M-tag=START； M-region.unit.r
ow = MaxRow; M->region.unit.column = MaxCol; M->region.unit.value = 0; /*Row Node*/ GPos preR = M; for(int i = 0; i < MaxRow; i++) { GPos tmp = (GPos) malloc(sizeof(struct GNode)); if(!tmp) exit(EXIT_FAILURE); tmp->tag = HEAD; tmp->region.head = NULL; preR->down = tmp; if(preR != M) preR->right = NULL; preR = preR->down; } preR->right = NULL; /*Column Node*/ GPos preC = M; for(int i = 0; i < MaxCol; i++) { GPos tmp = (GPos) malloc(sizeof(struct GNode)); tmp->tag = HEAD; tmp->region.head = NULL; preC->right = tmp; if(preC != M) preC->down = NULL; preC = preC->right; } preC->down = NULL; return M;}bool InsertUnit(Matrix M, ElemType E, Cursor Row, Cursor Column){ if(M->tag != START || Row > M->region.unit.row || Column > M->region.unit.column) return false; /*Allocation*/ GPos tmp = (GPos) malloc(sizeof(struct GNode)); if(!tmp) exit(EXIT_FAILURE); tmp->tag = UNIT; tmp->region.unit.row = Row; tmp->region.unit.column = Column; tmp->region.unit.value = E; /*Row Location*/ GPos ptrR = GLocateDown(M, Row); if(ptrR->tag == HEAD && ptrR->region.head) { ptrR = ptrR->region.head; while(ptrR->right && !(ptrR->region.unit.column < Column && ptrR->down->region.unit.column > Column)) ptrR = GLocateRight(ptrR, 1); tmp->right = ptrR->right; ptrR->right = tmp; } else { if(ptrR->tag != HEAD) return false; tmp->right = NULL; ptrR->region.head = tmp; } /*Column Location*/ GPos ptrC = GLocateRight(M, Column); if(ptrC->tag == HEAD && ptrC->region.head) { ptrC = ptrC->region.head; while(ptrC->down && !(ptrC->region.unit.row < Row && ptrC->down->region.unit.row > Row)) ptrC = GLocateDown(ptrC, 1); tmp->down = ptrC->down; ptrC->down = tmp; } else { if(ptrC->tag != HEAD) return false; tmp->down = NULL; ptrC->region.head = tmp; } M->region.unit.value++; return true;}bool PrintMatrix(Matrix M){ if(M->tag != START) return false; GPos ptrR = M; for(int i = 0; i < M->region.unit.row; i++) { ptrR = GLocateDown(ptrR, 1); if(!ptrR) return false; GPos ptrC = ptrR->region.head; if(!ptrC) { //空行填0 for(int j = 0; j < M->region.unit.column; j++) printf("%-2d ", 0); putchar('n'); } else { //行前补0 for(int k = 1; k < ptrC->region.unit.column; k++) printf("%-2d ", 0); //行中补0 while(ptrC->right) { printf("%-2d ", ptrC->region.unit.value); int diff = ptrC->right->region.unit.column - ptrC->region.unit.column; for(int k = 1; k < diff; k++) printf("%-2d ", 0); putchar('n'); } //行后补0 printf("%-2d ", ptrC->region.unit.value); int excess = M->region.unit.column - ptrC->region.unit.column; for(int k = 0; k < excess; k++) printf("%-2d ", 0); putchar('n'); } } return true;} 三、运行实例main.c
#include "Matrix.h"int main(){ Matrix M = CreateMatrix(4, 3); InsertUnit(M, 62, 1, 2); InsertUnit(M, 23, 2, 1); InsertUnit(M, 18, 3, 2); InsertUnit(M, 29, 4, 3); PrintMatrix(M); return 0;}输出：