关于矩阵的存储，在矩阵的元素明显规则排列的情况下，一般以一维数组压缩存储矩阵； 如果矩阵中的许多元素是0，并且只有少数元素是0以外的元素，则我们将为稀疏矩阵。
我们有排队A i j。 其中有非0元素m个。 mIj0.05时，我们把矩阵A i j称为稀疏矩阵。 我们有矩阵A_{ij}。 其中有非0元素m个。 frac{m}{ij} le 0.05时，我们称为矩阵A_{ij}
对于稀疏矩阵，非零元素的数组不规则，因此无法压缩和保存矩阵。 另外，使用二维数组保存非零元素数量较少的矩阵会浪费很多空间来保存没有意义的0元素。 因此，对于稀疏矩阵，可以选择使用十字链表进行保存。
不用说，我先打代码
# include stdio.h # include stdlib.h # define false0# define true1typedefintdatatype； 类型结构节点{ int row； int column； union{DataType value； 结构节点*下一步； }uval； 结构节点* r next； 结构节点* c next； }SNode，*SNodePtr； //创建矩阵datatype * *创建矩阵(内部，内部列)； //交叉链接列表snodeptrcreate(introw，int column )； //在交叉链接列表中添加void insert (插入snodeptrphead，SNodePtr pnode ) (如果存在)； //将稀疏矩阵转换为交叉链接列表以生成snodeptrmatrix2list (datatype * * pparr，int row，int column )； //矩阵加法snodeptrmatrixadd (snodeptrphead 1，SNodePtr phead2)； //打印矩阵void打印(snodeptrphead )； int main () {printf ) )请输入第一个矩阵(n )； datatype * * arr1=创建矩阵(4，4 )； printf(nn2请输入第二个矩阵(n )； DataType **arr2=Creat
eMatrix(4, 4);SNodePtr phead1 = Matrix2List(arr1, 4, 4);SNodePtr phead2 = Matrix2List(arr2, 4, 4);printf("nnn");// 打印两个矩阵Print(phead1);printf("nnn");Print(phead2);printf("nnn");SNodePtr phead = MatrixAdd(phead1, phead2);Print(phead);return 0;}// 创建矩阵DataType **CreateMatrix(int row, int column){DataType **ipparr = (int **)malloc(sizeof(int *) * row);for(int i = 0; i < row; ++i){ipparr[i] = (int *)malloc(sizeof(int) * column);for(int j = 0; j < column; ++j)scanf("%d", &ipparr[i][j]);}return ipparr;}// 创造十字链表SNodePtrCreate(int row, int column){// 创建头结点SNodePtr phead = (SNodePtr)malloc(sizeof(SNode));phead->row = row;phead->column = column;phead->rnext = phead->cnext = NULL;phead->uval.next = NULL;SNodePtr ptmp = phead;// 创建十字链表if(row > column){for(int i = 0; i < row; ++i){ptmp->uval.next = (SNodePtr)malloc(sizeof(SNode));ptmp = ptmp->uval.next;ptmp->row = ptmp->column = 0;ptmp->uval.next = NULL;ptmp->cnext = ptmp;if(i < column)ptmp->rnext = ptmp;else ptmp->rnext = NULL;}}else{for(int i = 0; i < column; ++i){ptmp->uval.next = (SNodePtr)malloc(sizeof(SNode));ptmp = ptmp->uval.next;ptmp->row = ptmp->column = 0;ptmp->uval.next = NULL;ptmp->rnext = ptmp;if( i < row)ptmp->cnext = ptmp;elseptmp->cnext = NULL;}}return phead;}// 向十字链表插入(如果存在则相加)voidInsert(SNodePtr phead, SNodePtr pnode){SNodePtr prtmp = phead;// 找到对应行for(int i = 0; i < pnode->row; ++i)prtmp = prtmp->uval.next;SNodePtr ptmp1 = prtmp;// 找到要插入的地方while(ptmp1->cnext != prtmp && ptmp1->cnext->column < pnode->column)ptmp1 = ptmp1->cnext;if(ptmp1->cnext->column != pnode->column){SNodePtr ptmp = (SNodePtr)malloc(sizeof(SNode));// 新开辟空间使为了不改变pnode的指针ptmp->cnext = ptmp1->cnext;ptmp1->cnext = ptmp;ptmp->column = pnode->column;ptmp->row = pnode->row;ptmp->uval.value = pnode->uval.value;ptmp->rnext = NULL;// 接下来要将行指针连接SNodePtr pctmp = phead;// 找到对应列for(int i = 0; i < pnode->column; ++i)pctmp = pctmp->uval.next;SNodePtr ptmp2 = pctmp;// 找到要插入的地方while(ptmp2->rnext != pctmp && ptmp2->rnext->row < pnode->row)ptmp2 = ptmp2->rnext;ptmp->rnext = ptmp2->rnext;ptmp2->rnext = ptmp;return ;}else// 这一行有非零元素且他们在同一列{ptmp1->cnext->uval.value += pnode->uval.value;return ;// 因为没有开辟新的空间，原来的结构不变，因此不需要对列进行操作，直接返回即可}}// 将稀疏矩阵转换成十字链表存储SNodePtrMatrix2List(DataType **pparr, int row, int column){SNodePtr phead = Create(row, column);// 创建十字链表// 创建并初始化临时指针SNodePtr ptmp = (SNodePtr)malloc(sizeof(SNode));ptmp->row = ptmp->column = 0;ptmp->uval.value = 0;ptmp->rnext = ptmp->cnext = NULL;for(int i = 0; i < row; ++i){for(int j = 0; j < column; ++j){if(pparr[i][j] != 0){ptmp->row = i + 1;ptmp->column = j + 1;ptmp->uval.value = pparr[i][j];Insert(phead, ptmp);}}}return phead;}// 矩阵相加SNodePtrMatrixAdd(SNodePtr phead1, SNodePtr phead2){if(phead1->row != phead2->row || phead1->column != phead2->column)// 矩阵无法相加return NULL;SNodePtr phead = Create(phead1->row, phead1->column);// 将phead1加入pheadSNodePtr ptmp = phead1;for(int i = 0; i < phead1->row; ++i){ptmp = ptmp->uval.next;SNodePtr ptmp2 = ptmp;while(ptmp2->cnext != ptmp){ptmp2 = ptmp2->cnext;Insert(phead, ptmp2);}}Print(phead);// 将phead2加入pheadptmp = phead2;for(int i = 0; i < phead2->row; ++i){ptmp = ptmp->uval.next;SNodePtr ptmp2 = ptmp;while(ptmp2->cnext != ptmp){ptmp2 = ptmp2->cnext;Insert(phead, ptmp2);}}return phead;}// 打印矩阵voidPrint(SNodePtr phead){SNodePtr prtmp = phead;for(int i = 0; i < phead->row; ++i){prtmp = prtmp->uval.next;SNodePtr pctmp = prtmp->cnext;if(pctmp == prtmp){printf("0 0 0 0 ");continue;}for(int j = 1; j <= pctmp->column; ++j){if(j < pctmp->column)printf("0 ");else{printf("%d ", pctmp->uval.value);pctmp = pctmp->cnext;if(pctmp == prtmp){for(int k = phead->column; k > j; --k)printf("0 ");break;}}}printf("n");}printf("n");}我的基本思想是对于矩阵的操作是不会影响原矩阵，即A + B = C，C不是将A加入B或者B加入A得到的，而是新开辟的一块空间。基于此思想，在进行插入操作的时候，我并没有对待插入的结点的指针做任何转变，而是找到要插入的位置，新开辟一块空间，将待插入结点的值，行列等赋值给新开辟的空间，然后再连接插入的结点的行列指针即可。基于此思想，我们在执行矩阵A和B的相加的时候，完全不用考虑矩阵A和矩阵B中指针的变动，只需要创建一个新的空的十字链表，然后将A和B中的元素插入即可。