实验6：稀疏矩阵十字链表的存储

课程设计任务书学生姓名：宋吉松专业班级：软件1202班指导教师：李晓红工作单位：计算机科学与技术学院题目: 稀疏矩阵的存储实现初始条件：理论：学习了《数据结构》课程，掌握了一种计算机高级语言。

实践：计算机技术系实验中心提供计算机及软件开发环境。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）实现稀疏矩阵的三元组和十字链表两种存储结构（2）实现稀疏矩阵的基本运算（3）输出结果2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术的讨论、设计体会等；（4）结束语；（5）参考文献。

时间安排：2013年12月16日--25日指导教师签名：李晓红 2013年12月14日系主任（或责任教师）签名：年月日摘要本课程设计在学习数据结构的前提下，运用c语言，对稀疏矩阵进行三元组存储和十字链表存储，并完成稀疏矩阵的转置，相加，相乘等基本运算。

关键词稀疏矩阵三元组十字链表基本运算Abstract This course is designed on the premise of learning datastructures using c language, for sparse matrix triple store to store and cross-linked, and were achieved under the two storage sparse matrix transpose, add, multiply, and other basic operations.Keywords sparse matrix triples Crusaders basic operations目录引言 (1)1 需求分析1.1稀疏矩阵三元组表和十字链表两种存储的实现 (2)1.2稀疏矩阵转置 (2)1.3稀疏矩阵的相加相乘 (2)1.4输出结果 (2)2 数据结构设计2.1 三元组的结构体 (2)2.2 十字链表的结构体 (3)3算法设计3.1三元组3.1.1三元组的创建 (3)3.1.2三元组的转置 (5)3.1.3三元组的相加 (5)3.1.4三元组的相乘 (8)3.1.5三元组的显示 (10)3.2十字链表3.2.1十字链表的创建 (11)3.2.2十字链表的显示 (12)3.3 主函数 (13)4 设计体会 (16)5 结束语 (16)附1 参考文献 (16)附2 源代码 (17)附3 运行结果 (38)引言什么是稀疏矩阵？人们无法给出确切的定义，它只是一个凭人们的直觉来了解的概念。

⼗字链表的存储与运算#include#includetypedef int ElemType;// 稀疏矩阵的⼗字链表存储表⽰typedef struct OLNode{int i,j; // 该⾮零元的⾏和列下标ElemType e; // ⾮零元素值struct OLNode *right,*down; // 该⾮零元所在⾏表和列表的后继链域}OLNode, *OLink;typedef struct// ⾏和列链表头指针向量基址,由CreatSMatrix_OL()分配{OLink *rhead, *chead;int mu, nu, tu; // 稀疏矩阵的⾏数、列数和⾮零元个数}CrossList;// 初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错) int InitSMatrix(CrossList *M) {(*M).rhead=(*M).chead=NULL;(*M).mu=(*M).nu=(*M).tu=0;return 1;}// 销毁稀疏矩阵Mint DestroySMatrix(CrossList *M){int i;OLNode *p,*q;for(i=1;i<=(*M).mu;i++) // 按⾏释放结点{p=*((*M).rhead+i);while(p){q=p;p=p->right;free(q);}free((*M).chead);(*M).rhead=(*M).chead=NULL;(*M).mu=(*M).nu=(*M).tu=0;return 1;}// 创建稀疏矩阵M,采⽤⼗字链表存储表⽰。

int CreateSMatrix(CrossList *M){int i,j,k,m,n,t;ElemType e;OLNode *p,*q;if((*M).rhead)DestroySMatrix(M);printf("请输⼊稀疏矩阵的⾏数列数⾮零元个数:(space) ");scanf("%d%d%d",&m,&n,&t);(*M).mu=m;(*M).nu=n;(*M).tu=t;//初始化⾏链表头(*M).rhead=(OLink*)malloc((m+1)*sizeof(OLink));if(!(*M).rhead)exit(0);//初始化列链表头(*M).chead=(OLink*)malloc((n+1)*sizeof(OLink));if(!(*M).chead)exit(0);for(k=1;k<=m;k++) // 初始化⾏头指针向量;各⾏链表为空链表(*M).rhead[k]=NULL;for(k=1;k<=n;k++) // 初始化列头指针向量;各列链表为空链表(*M).chead[k]=NULL;printf("请按任意次序输⼊%d个⾮零元的⾏列元素值:（空格）\n",(*M).tu); for(k=0;k{if(!p)exit(0);p->i=i; // ⽣成结点p->j=j;p->e=e;if((*M).rhead[i]==NULL||(*M).rhead[i]->j>j){// p插在该⾏的第⼀个结点处p->right=(*M).rhead[i];(*M).rhead[i]=p;}else // 寻查在⾏表中的插⼊位置{//从该⾏的⾏链表头开始，直到找到for(q=(*M).rhead[i]; q->right && q->right->j < j;q = q->right);p->right=q->right; // 完成⾏插⼊q->right=p;}if((*M).chead[j] == NULL || (*M).chead[j]->i > i){// p插在该列的第⼀个结点处p->down = (*M).chead[j];(*M).chead[j] = p;}else // 寻查在列表中的插⼊位置{for(q = (*M).chead[j];q->down && q->down->i < i;q = q->down) ;p->down=q->down; // 完成列插⼊q->down=p;}}// 按⾏或按列输出稀疏矩阵Mint PrintSMatrix(CrossList M){int i,j;OLink p;printf("%d⾏%d列%d个⾮零元素\n",M.mu,M.nu,M.tu); printf("请输⼊选择(1.按⾏输出2.按列输出): ");scanf("%d",&i);switch(i){case 1:for(j=1;j<=M.mu;j++){p=M.rhead[j];while(p){printf("%d⾏%d列值为%d\n",p->i,p->j,p->e);p=p->right;}}break;case 2:for(j=1;j<=M.nu;j++){p=M.chead[j];while(p){printf("%d⾏%d列值为%d\n",p->i,p->j,p->e);p=p->down;}}}return 1;int CopySMatrix(CrossList M,CrossList *T){int i;OLink p,q,q1,q2;if((*T).rhead)DestroySMatrix(T);(*T).mu=M.mu;(*T).nu=M.nu;(*T).tu=M.tu;(*T).rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink));if(!(*T).rhead)exit(0);(*T).chead=(OLink*)malloc((M.nu+1)*sizeof(OLink));if(!(*T).chead)exit(0);for(i=1;i<=M.mu;i++) // 初始化矩阵T的⾏头指针向量;各⾏链表为空链表(*T).rhead[i]=NULL; for(i=1;i<=M.nu;i++) // 初始化矩阵T的列头指针向量;各列链表为空链表(*T).chead[i]=NULL; for(i=1;i<=M.mu;i++) // 按⾏复制{p=M.rhead[i];while(p) // 没到⾏尾{q=(OLNode*)malloc(sizeof(OLNode)); // ⽣成结点if(!q)exit(0);q->i=p->i; // 给结点赋值q->j=p->j;q->e=p->e;if(!(*T).rhead[i]) // 插在⾏表头(*T).rhead[i]=q1=q;else // 插在⾏表尾q1=q1->right=q;if(!(*T).chead[q->j]) // 插在列表头q->down=NULL;}else // 插在列表尾{q2=(*T).chead[q->j];while(q2->down)q2=q2->down;q2->down=q;q->down=NULL;}p=p->right;}q->right=NULL;}return 1;}// 求稀疏矩阵的和Q=M+Nint AddSMatrix(CrossList M,CrossList N,CrossList *Q) {int i,k;OLink p,pq,pm,pn;OLink *col;if(M.mu!=N.mu||M.nu!=N.nu){printf("两个矩阵不是同类型的,不能相加\n");exit(0);}(*Q).mu=M.mu; // 初始化Q矩阵(*Q).nu=M.nu;(*Q).tu=0; // 元素个数的初值(*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink)); if(!(*Q).rhead)exit(0);exit(0);for(k=1;k<=(*Q).mu;k++) // 初始化Q的⾏头指针向量;各⾏链表为空链表(*Q).rhead[k]=NULL; for(k=1;k<=(*Q).nu;k++) // 初始化Q的列头指针向量;各列链表为空链表(*Q).chead[k]=NULL; // ⽣成指向列的最后结点的数组col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!col)exit(0);for(k=1;k<=(*Q).nu;k++) // 赋初值col[k]=NULL;for(i=1;i<=M.mu;i++) // 按⾏的顺序相加{pm=M.rhead[i]; // pm指向矩阵M的第i⾏的第1个结点pn=N.rhead[i]; // pn指向矩阵N的第i⾏的第1个结点while(pm&&pn) // pm和pn均不空{if(pm->jj) // 矩阵M当前结点的列⼩于矩阵N当前结点的列{p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移}else if(pm->j>pn->j)// 矩阵M当前结点的列⼤于矩阵N当前结点的列{p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->e=pn->e;p->right=NULL;pn=pn->right; // pn指针向右移}// 矩阵M、N当前结点的列相等且两元素之和不为0 else if(pm->e+pn->e){p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=pm->e+pn->e;p->right=NULL;pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移}else // 矩阵M、N当前结点的列相等且两元素之和为0 {pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移continue;}if((*Q).rhead[i]==NULL) // p为该⾏的第1个结点// p插在该⾏的表头且pq指向p(该⾏的最后⼀个结点) (*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成⾏插⼊pq=pq->right; // pq指向该⾏的最后⼀个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向pcol[p->j]->down=p; // 完成列插⼊// col[p->j]指向该列的最后⼀个结点col[p->j]=col[p->j]->down;}}while(pm) // 将矩阵M该⾏的剩余元素插⼊矩阵Q{p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移if((*Q).rhead[i] == NULL) // p为该⾏的第1个结点// p插在该⾏的表头且pq指向p(该⾏的最后⼀个结点) (*Q).rhead[i] = pq = p;else // 插在pq所指结点之后{pq->right=p; // 完成⾏插⼊pq=pq->right; // pq指向该⾏的最后⼀个结点}if((*Q).chead[p->j] == NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j] = col[p->j] = p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插⼊// col[p->j]指向该列的最后⼀个结点col[p->j]=col[p->j]->down;}p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=pn->e;p->right=NULL;pn=pn->right; // pm指针向右移if((*Q).rhead[i]==NULL) // p为该⾏的第1个结点// p插在该⾏的表头且pq指向p(该⾏的最后⼀个结点)(*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成⾏插⼊pq=pq->right; // pq指向该⾏的最后⼀个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插⼊// col[p->j]指向该列的最后⼀个结点col[p->j]=col[p->j]->down;}}}for(k=1;k<=(*Q).nu;k++)if(col[k]) // k列有结点col[k]->down=NULL; // 令该列最后⼀个结点的down指针为空free(col); return 1;}{int i,k;OLink p,pq,pm,pn;OLink *col;if(M.mu!=N.mu||M.nu!=N.nu){printf("两个矩阵不是同类型的,不能相加\n");exit(0);}(*Q).mu=M.mu; // 初始化Q矩阵(*Q).nu=M.nu;(*Q).tu=0; // 元素个数的初值(*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));if(!(*Q).rhead)exit(0);(*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!(*Q).chead)exit(0);for(k=1;k<=(*Q).mu;k++) // 初始化Q的⾏头指针向量;各⾏链表为空链表(*Q).rhead[k]=NULL; for(k=1;k<=(*Q).nu;k++) // 初始化Q的列头指针向量;各列链表为空链表(*Q).chead[k]=NULL; // ⽣成指向列的最后结点的数组col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!col)exit(0);for(k=1;k<=(*Q).nu;k++) // 赋初值col[k]=NULL;for(i=1;i<=M.mu;i++) // 按⾏的顺序相加{pm=M.rhead[i]; // pm指向矩阵M的第i⾏的第1个结点pn=N.rhead[i]; // pn指向矩阵N的第i⾏的第1个结点while(pm&&pn) // pm和pn均不空{if(pm->jj) // 矩阵M当前结点的列⼩于矩阵N当前结点的列{p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移}// 矩阵M当前结点的列⼤于矩阵N当前结点的列else if(pm->j>pn->j){p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=-pn->e;p->right=NULL;pn=pn->right; // pn指针向右移}else if(pm->e-pn->e){// 矩阵M、N当前结点的列相等且两元素之差不为0p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=pm->e-pn->e;p->right=NULL;pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移}else // 矩阵M、N当前结点的列相等且两元素之差为0 {pm=pm->right; // pm指针向右移pn=pn->right; // pn指针向右移continue;}if((*Q).rhead[i]==NULL) // p为该⾏的第1个结点// p插在该⾏的表头且pq指向p(该⾏的最后⼀个结点) (*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成⾏插⼊pq=pq->right; // pq指向该⾏的最后⼀个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->]所指结点之后{col[p->j]->down=p; // 完成列插⼊// col[p->j]指向该列的最后⼀个结点col[p->j]=col[p->j]->down;}}while(pm) // 将矩阵M该⾏的剩余元素插⼊矩阵Q{p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pm->j;p->e=pm->e;p->right=NULL;pm=pm->right; // pm指针向右移if((*Q).rhead[i]==NULL) // p为该⾏的第1个结点// p插在该⾏的表头且pq指向p(该⾏的最后⼀个结点) (*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成⾏插⼊pq=pq->right; // pq指向该⾏的最后⼀个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插⼊// col[p->j]指向该列的最后⼀个结点col[p->j]=col[p->j]->down;}}while(pn) // 将矩阵N该⾏的剩余元素插⼊矩阵Q{p=(OLink)malloc(sizeof(OLNode)); // ⽣成矩阵Q的结点if(!p)exit(0);(*Q).tu++; // ⾮零元素数加1p->i=i; // 给结点赋值p->j=pn->j;p->e=-pn->e;p->right=NULL;pn=pn->right; // pm指针向右移if((*Q).rhead[i]==NULL) // p为该⾏的第1个结点// p插在该⾏的表头且pq指向p(该⾏的最后⼀个结点) (*Q).rhead[i]=pq=p;else // 插在pq所指结点之后{pq->right=p; // 完成⾏插⼊pq=pq->right; // pq指向该⾏的最后⼀个结点}if((*Q).chead[p->j]==NULL) // p为该列的第1个结点// p插在该列的表头且col[p->j]指向p(*Q).chead[p->j]=col[p->j]=p;else // 插在col[p->j]所指结点之后{col[p->j]->down=p; // 完成列插⼊// col[p->j]指向该列的最后⼀个结点col[p->j]=col[p->j]->down;}}}for(k=1;k<=(*Q).nu;k++)if(col[k]) // k列有结点col[k]->down=NULL; // 令该列最后⼀个结点的down指针为空free(col);return 1;}// 求稀疏矩阵乘积Q=M*Nint MultSMatrix(CrossList M,CrossList N,CrossList *Q){int i,j,e;OLink q,p0,q0,q1,q2;InitSMatrix(Q);(*Q).mu=M.mu;(*Q).nu=N.nu;(*Q).tu=0;(*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));if(!(*Q).rhead)exit(0);(*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));if(!(*Q).chead)exit(0);for(i=1;i<=(*Q).mu;i++) // 初始化矩阵Q的⾏头指针向量;各⾏链表为空链表(*Q).rhead[i]=NULL; for(i=1;i<=(*Q).nu;i++) // 初始化矩阵Q的列头指针向量;各列链表为空链表(*Q).chead[i]=NULL; for(i=1;i<=(*Q).mu;i++)for(j=1;j<=(*Q).nu;j++)p0=M.rhead[i];q0=N.chead[j];e=0;while(p0&&q0){if(q0->ij)q0=q0->down; // 列指针后移else if(q0->i>p0->j)p0=p0->right; // ⾏指针后移else // q0->i==p0->j{e+=p0->e*q0->e; // 乘积累加q0=q0->down; // ⾏列指针均后移p0=p0->right;}}if(e) // 值不为0{(*Q).tu++; // ⾮零元素数加1q=(OLink)malloc(sizeof(OLNode)); // ⽣成结点if(!q) // ⽣成结点失败exit(0);q->i=i; // 给结点赋值q->j=j;q->e=e;q->right=NULL;q->down=NULL;if(!(*Q).rhead[i]) // ⾏表空时插在⾏表头(*Q).rhead[i]=q1=q;else // 否则插在⾏表尾q1=q1->right=q;if(!(*Q).chead[j]) // 列表空时插在列表头(*Q).chead[j]=q;else // 否则插在列表尾q2=(*Q).chead[j]; // q2指向j⾏第1个结点while(q2->down)q2=q2->down; // q2指向j⾏最后1个结点q2->down=q;}}}return 1;}// 求稀疏矩阵M的转置矩阵Tint TransposeSMatrix(CrossList M,CrossList *T) {int u,i;OLink *head,p,q,r;if((*T).rhead)DestroySMatrix(T);CopySMatrix(M,T); // T=Mu=(*T).mu; // 交换(*T).mu和(*T).nu(*T).mu=(*T).nu;(*T).nu=u;head=(*T).rhead; // 交换(*T).rhead和(*T).chead (*T).rhead=(*T).chead;(*T).chead=head;for(u=1;u<=(*T).mu;u++) // 对T的每⼀⾏{p=(*T).rhead[u]; // p为⾏表头while(p) // 没到表尾,对T的每⼀结点{q=p->down; // q指向下⼀个结点i=p->i; // 交换.i和.jp->i=p->j;p->j=i;r=p->down; // 交换.down.和rightp->down=p->right;p->right=r;p=q; // p指向下⼀个结点}}return 1;}int main(){CrossList A,B,C;InitSMatrix(&A); // CrossList类型的变量在初次使⽤之前必须初始化InitSMatrix(&B);printf("创建矩阵A: ");CreateSMatrix(&A);PrintSMatrix(A);printf("由矩阵A复制矩阵B: ");CopySMatrix(A,&B);PrintSMatrix(B);DestroySMatrix(&B); // CrossList类型的变量在再次使⽤之前必须先销毁printf("销毁矩阵B后:\n"); PrintSMatrix(B);printf("创建矩阵B2:(与矩阵A的⾏、列数相同，⾏、列分别为%d,%d)\n",A.mu,A.nu);CreateSMatrix(&B);PrintSMatrix(B);printf("矩阵C1(A+B): ");AddSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&C);printf("矩阵C2(A-B): ");SubtSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&C);printf("矩阵C3(A的转置): ");TransposeSMatrix(A,&C);PrintSMatrix(C);DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);printf("创建矩阵A2: ");CreateSMatrix(&A);PrintSMatrix(A);printf("创建矩阵B3:(⾏数应与矩阵A2的列数相同=%d)\n",A.nu); CreateSMatrix(&B);PrintSMatrix(B);printf("矩阵C5(A*B): ");MultSMatrix(A,B,&C);PrintSMatrix(C);DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);system("pause");return 0;}。

数据结构实验报告三稀疏矩阵的运算实验课程名称数据结构课程设计专业班级学⽣姓名学号指导教师2012 ⾄ 2013 学年第⼀学期第 1 ⾄ 18 周⽬录实验题⽬：稀疏矩阵的运算 (3)⼀：概述 (3)⼆：系统分析 (3)三：概要设计 (3)四：详细设计 (4)五：运⾏与测试 (9)六：总结与⼼得 (9)实验题⽬：稀疏矩阵的运算⼀：概述本实验设计主要实现在⼗字链表存储结构输⼊稀疏矩阵，并对稀疏矩阵进⾏相加操作，最后输出运算结果。

⼆：系统分析本实验要求设计函数在⼗字链表结构下建⽴稀疏矩阵并初始化，在创建稀疏矩阵时，需要设计在⼗字链表下创建稀疏矩阵，在输⼊出现错误时，能够对错误进⾏判别处理，初始化稀疏矩阵都为空值。

在设计输出稀疏矩阵的值的函数时，根据情况编制函数，才能准确的输出稀疏矩阵。

在对稀疏矩阵进⾏初始化时，只输⼊⾮零元素的值和它所在的所在⾏及所在列。

在对稀疏矩阵输出时，以矩阵的完整形式输出。

除此之外还要求设计相加对两个矩阵进⾏运算，并输出最终的稀疏矩阵，定义相应的矩阵类型⽤于存放两个矩阵操作后的结果矩阵，这个结果矩阵的⾏、列数需要综合多⽅⾯情况来确定。

这些函数也是整个程序的难点，需要灵活运⽤数组及指针的特点。

三：概要设计⼗字链表结构体定义:typedef struct sex{int row,col,val; //⾮零元素的⾏、列下标及值struct sex *right,*dowm; //该⾮零元素所在⾏表和列表的后继元素}Node;矩阵的加法：此功能在⼗字链表存储结构下，由函数void addition(Node *cp1, Node *cp2, Node *cp3)实现。

当⽤户选择该功能，系统即提⽰⽤户初始化要进⾏加法的两个矩阵的信息。

然后进⾏加法，最后输出结果。

四：详细设计#include#includetypedef struct sex{int row,col,val; //⾮零元素的⾏、列下标及值struct sex *right,*dowm; //该⾮零元素所在⾏表和列表的后继元素}Node;Node * Init(int m, int n){int t,i;Node *cp;t=(m>=n)?m:n;cp=(Node *)malloc( (t+1)*sizeof(Node) ); //开辟⼀串连续的内存空间(*cp).row=m;(*cp).col=n;(*cp).val=t; //此表头结点的值域⽤来记录⾏列的最⼤值，以便于后⾯的开辟空间for(i=1;i<=t;i++){cp[i].right=cp+i;cp[i].dowm=cp+i; //构成带表头结点的空循环单链表}return cp;}void CreatCrossList(Node *cp){int t,i;Node *s,*temp;printf("请输⼊⾮零元素的个数N：");scanf("%d",&t);printf("\n请输⼊其对应坐标及元素值：\n");for(i=0;i{s=(Node *)malloc( sizeof(Node));scanf("%d%d%d",&s->row,&(*s).col,&s->val);temp=cp+s->row;if( temp->right!=cp+s->row )while( temp->right!=cp+s->row && temp->right->col<=s->col )temp=temp->right;s->right=temp->right;temp->right=s; //修改⾏链表插⼊位置temp=cp+s->col;if( temp->dowm!=cp+s->col )while( temp->dowm!=cp+s->col && temp->dowm->row<=s->row )temp=temp->dowm;s->dowm=temp->dowm;temp->dowm=s; //修改列链表插⼊位置}}void output(Node *cp){int i;Node *temp;printf("\n稀疏矩阵如下：\n");for(i=1;i<=cp->row;i++){temp=cp+i;while( temp->right!=cp+i ){printf("(%d,%d %d)",temp->right->row,temp->right->col,temp->right->val); temp=temp->right;}printf("\n");}}void Insert(Node *cp, Node *s){//此插⼊函数的作⽤是：⽣成⽬标矩阵Node *temp;temp=cp+s->row; //修改⾏链表指针if( temp->right!=cp+s->row )while( temp->right!=cp+s->row && temp->right->col<=s->col ) temp=temp->right;s->right=temp->right;temp->right=s;temp=cp+s->col; //修改列链表指针if( temp->dowm!=cp+s->col )while( temp->dowm!=cp+s->col && temp->dowm->row<=s->row ) temp=temp->dowm;s->dowm=temp->dowm;temp->dowm=s;}void addition(Node *cp1, Node *cp2, Node *cp3){int i;Node *w,*p,*q;for( i=1; i<=cp2->row && i<=cp3->row; i++){p=cp2+i;q=cp3+i;while( p->right!=cp2+i && q->right!=cp3+i ){w=(Node *)malloc( sizeof(Node) );w->row=p->right->row;if( p->right->col==q->right->col ){w->col=p->right->col;w->val=p->right->val+q->right->val; //相同位置上的元素值相加p=p->right;q=q->right;if( w->val )Insert(cp1,w); //把⾮零元插⼊到⽬标矩阵中}else if( p->right->colright->col ){w->col=p->right->col;w->val=p->right->val;p=p->right;Insert(cp1,w); //把cp2中的⾮零元插⼊到⽬标矩阵中}else{w->col=q->right->col;w->val=q->right->val;q=q->right;Insert(cp1,w); //把cp2中的⾮零元插⼊到⽬标矩阵中}}if( p->right==cp2+i )while( q->right!=cp3+i ){w=(Node *)malloc( sizeof(Node) );w->row=q->right->row;w->col=q->right->col;w->val=q->right->val;q=q->right;Insert(cp1,w); //把cp3中剩余的⾮零元插⼊⽬标矩阵中} else if( q->right==cp3+i )while( p->right!=cp2+i ){w=(Node *)malloc( sizeof(Node) );w->row=p->right->row;w->col=p->right->col;w->val=p->right->val;p=p->right;Insert(cp1,w); //把cp2中剩余的⾮零元插⼊到⽬标矩阵中} else; //两个矩阵同⼀⾏中同时结束}if( i>cp2->row)while(i<=cp3->row){//把cp3中剩余⾏中的⾮零元插⼊到⽬标矩阵中q=cp3+i;while( q->right!=cp3+i ){w=(Node *)malloc( sizeof(Node) );w->row=q->right->row;w->col=q->right->col;w->val=q->right->val;q=q->right;Insert(cp1,w);}i++; //继续下⼀⾏}else if(i>cp3->row)while( i<=cp2->row ){p=cp2+i;while( p->right!=cp2+i ){w=(Node *)malloc( sizeof(Node) );w->row=p->right->row;w->col=p->right->col;w->val=p->right->val;p=p->right;Insert(cp1,w);}i++; //继续下⼀⾏}}int main(){Node *cp1, *cp2, *cp3;int a, b;printf("\t\t\t*****稀疏矩阵的加法*****\n\n");printf("请输⼊cp2的⾏、列数：");scanf("%d%d",&a,&b);cp2=Init(a,b);printf("请输⼊cp3的⾏、列数：");scanf("%d%d",&a,&b);cp3=Init(a,b);a=cp2->row>=cp3->row?cp2->row:cp3->row;b=cp2->col>=cp3->col?cp2->col:cp3->col;cp1=Init(a,b); //开始初始化结果矩阵printf("\n\t>>>>>>>创建稀疏矩阵cp2\n");CreatCrossList(cp2);printf("\n\t>>>>>>>创建稀疏矩阵cp3\n");CreatCrossList(cp3);output(cp2);output(cp3);addition(cp1,cp2,cp3);printf("\n\n相加后的"); output(cp1);return 0;}五：运⾏与测试进⾏数据测试六：总结与⼼得⼗字链表作为存储结构表⽰随机稀疏矩阵，进⾏两矩阵的相加运算，所以⾸先要定义⼀个⼗字链表作为存储结构。

目录前言 (1)正文 (1)1.课程设计的目的和任务 (1)2.课程设计报告的要求 (1)3.课程设计的内容 (2)4.稀疏矩阵的十字链表存储 (2)5.稀疏矩阵的加法思想 (4)6.代码实现 (5)7.算法实现 (5)结论 (8)参考文献 (9)附录 (10)前言采用三元组顺序表存储稀疏矩阵，对于矩阵的加法、乘法等操作，非零元素的插入和删除将会产生大量的数据移动，这时顺序存储方法就十分不便。

稀疏矩阵的链接存储结构称为十字链表，它具备链接存储的特点，因此，在非零元素的个数及位置都会发生变化的情况下，采用链式存储结构表示三元组的线性更为恰当。

正文1.课程设计的目的和任务(1) 使我我们进一步理解和掌握所学的程序的基本结构。

(2) 使我们初步掌握软件开发过程的各个方法和技能。

(3) 使我们参考有关资料，了解更多的程序设计知识。

(4) 使我们能进行一般软件开发，培养我们的能力并提高我们的知识。

2.课程设计报告的要求(1)课程设计目的和任务，为了达到什么要求(2)课程设计报告要求(3)课程设计的内容，都包含了什么东西(4)稀疏矩阵和十字链表的基本概念，稀疏矩阵是怎么用十字链表存储(5)十字链表矩阵的加法(6)代码实现(7)算法检测3.课程设计的内容(1)根据所学知识并自主查找相关资料 (2)进行算法设计与分析(3)代码实现，组建并运行结果查看是否正确 (4)书写课程设计说明书4.稀疏矩阵的十字链表存储稀疏矩阵是零元素居多的矩阵，对于稀疏矩阵，人们无法给出确切的概念，只要非零元素的个数远远小于矩阵元素的总数，就可认为该矩阵是稀疏的。

十字链表有一个头指针hm ，它指向的结点有五个域，如图1所示。

row 域存放总行数m ，col 域存放总列数n ，down 和right 两个指针域空闲不用，next 指针指向第一个行列表头结点。

c o lr o w图1 总表点结点有S 个行列表头结点h[1]，h[2]，......h[s]。

目录1.需求分析 (1)2.概要设计 (2)2.1链表对稀疏矩阵进行定义 (2)2.3程序一共有五个功能 (2)3.详细设计 (3)3.1稀疏矩阵存储算法分析 (3)3.2稀疏矩阵各运算算法分析 (3)4.调试分析 (8)4.1调试过程中的问题及解决方法 (8)4.2算法的时间复杂度和空间复杂 (8)4.3经验和体会 (8)5.用户使用说明 (9)6.测试结果 (10)6.1程序主界面 (10)6.2其他函数操作界面显示 (10)参考文献 (15)致谢 (16)1.需求分析矩阵在日常生活中应用广泛，尤其是有些特殊矩阵的运算。

但是在实际应用中有一种矩阵，在m×n的矩阵中有t个非零元素，且t远小于m×n，我们这样的矩阵被称为稀疏矩阵。

由于这类矩阵中通常零元素是没有规律的，为了能够找到相应的元素，仅存储非零元素的值是不行的，还要存储其所在的行和列等信息。

本程序主要的任务是创建稀疏矩阵，并且利用C++算法程序实现相应的运算（转置，加法，减法，乘法）（1）输入的形式以及范围：键盘输入符合要求的稀疏矩阵。

（2）输出形式：最终运算结果以矩阵的形式输出。

（3）程序功能实现：输入矩阵通过程序运算出相应的转置矩阵以及两个符合要求的矩阵的加减乘除法的运算。

（4）测试数据：如果输入正确，程序会显示最后的运算结果；否则错误时则会返回上层。

2.概要设计要存储稀疏矩阵并且进行运算，那么就要了解稀疏矩阵的存储结构，这里采用链表的形式存储稀疏矩阵并进行运算。

2.1链表对稀疏矩阵进行定义typedef struct OLNode{ // 定义链表元素int i,j;int e;struct OLNode *next; // 该非零元所在行表和列表的后继元素}OLNode,*OLink;typedef struct{ // 定义链表对象结构体OLink *head; //头指针int mu,nu,tu; // 行数，列数，和非零元素个数}CrossList;2.3程序一共有五个功能1.用CreateSMatrix_OL(M)函数来实现稀疏矩阵的存储，用OutPutSMatrix_OL(M)函数实现稀疏矩阵的输出。

稀疏矩阵应用摘要本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。

在程序设计中，考虑到方法的难易程度，采用了先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘操作的方法，再在十字链表下实现。

程序通过调试运行，结果与预期一样，初步实现了设计目标。

关键词程序设计；稀疏矩阵；三元组；十字链表1 引言•课程设计任务本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。

稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；求出A的转置矩阵D，输出D；求两个稀疏矩阵A和B的相乘矩阵E，并输出E。

•课程设计性质数据结构课程设计是重要地实践性教学环节。

在进行了程序设计语言课和《数据结构》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。

本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现，包括在三元组和十字链表下存储稀疏矩阵，并对输入的稀疏矩阵进行转置，相加，相乘等操作，最后把运算结果输出。

此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。

1.3课程设计目的其目的是让我们在学习完C、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等基本操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

•需求分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。

首先要定义两种不同的结构体类型，在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值，特别注意在十字链表下，对变量进行动态的地址分配。

十字链表存储稀疏矩阵实现相乘算法#include <stdio.h>#include <stdlib.h>#include <assert.h>#define OK 1#define ERROR 0typedef struct list{int row;int colum;int value;struct list *right;struct list *down;}node,*element;typedef struct link{int row_size;int colum_size;int non_zero_amount;element *rhead;element *chead;}crosslist;int init_matrix(crosslist &one){one.row_size=0;one.colum_size=0;one.non_zero_amount=0;one.rhead=NULL;one.chead=NULL;return OK;}int creat_matrix(crosslist &one){int i;element news,temp;printf("Input the row size of the matrix:");scanf("%d",&one.row_size);printf("Input the colum size of the matrix:"); scanf("%d",&one.colum_size);printf("Input the non zero amount of the matrix:");scanf("%d",&one.non_zero_amount);one.rhead=(element*)malloc(sizeof(element)*(one.row_size+1));assert(one.rhead!=NULL);one.chead=(element*)malloc(sizeof(element)*(one.colum_size+1));assert(one.chead!=NULL);for(i=1;i<=one.row_size;i++)one.rhead[i]=NULL;for(i=1;i<=one.colum_size;i++)one.chead[i]=NULL;printf("/********************************/\n");for(i=1;i<=one.non_zero_amount;i++){news=(element)malloc(sizeof(node));assert(news!=NULL);do{printf("Input the script of the row:");scanf("%d",&news->row);}while(news->row>one.row_size);do{printf("Input the script of the colum:");scanf("%d",&news->colum);}while(news->colum>one.colum_size);printf("Input the value of the node:");scanf("%d",&news->value);if(!one.rhead[news->row]){news->right=NULL;one.rhead[news->row]=news;}else{for(temp=one.rhead[news->row];temp->right!=NULL;temp=temp->right)NULL;news->right=temp->right;temp->right=news;}if(!one.chead[news->colum]){news->down=NULL;one.chead[news->colum]=news;}else{for(temp=one.chead[news->colum];temp->down!=NULL;temp=temp->down)NULL;news->down=temp->down;temp->down=news;}printf("/*******************************/\n");}return OK;}int print_matrix(crosslist &one){element temp;int count;for(count=1;count<=one.row_size;count++){if(!one.rhead[count])continue;else{for(temp=one.rhead[count];temp!=NULL;temp=temp->right){printf("\t%d\t%d\t%d\n",temp->row,temp->colum,temp->value);printf("--------------------------------\n");}}}return OK;}int multi_matrix(crosslist one,crosslist two,crosslist &three){assert(one.colum_size==two.row_size);int i,j;int value;element insert;element pone,ptwo;element prow,pcolum;three.row_size=one.row_size;three.colum_size=two.colum_size;three.non_zero_amount=0;three.rhead=(element*)malloc(sizeof(element)*(three.row_size+1)); assert(three.rhead!=NULL);three.chead=(element*)malloc(sizeof(element)*(three.colum_size+1)); assert(three.chead!=NULL);for(i=1;i<=three.row_size;i++)three.rhead[i]=NULL;for(i=1;i<=three.colum_size;i++)three.chead[i]=NULL;for(i=1;i<=one.row_size;i++){for(j=1;j<=two.colum_size;j++){pone=one.rhead[i];ptwo=two.chead[j];value=0;while(pone!=NULL&&ptwo!=NULL){if(pone->colum==ptwo->row){value+=pone->value*ptwo->value;pone=pone->right;ptwo=ptwo->down;while(pone!=NULL&&ptwo!=NULL){if(pone->colum==ptwo->row){value+=pone->value*ptwo->value;pone=pone->right;ptwo=ptwo->down;}else if(pone->colum>ptwo->row){ptwo=ptwo->down;continue;}else{pone=pone->right;continue;}}if(value==0)break;insert=(element)malloc(sizeof(node));assert(insert!=NULL);insert->row=i;insert->colum=j;insert->value=value;insert->right=NULL;insert->down=NULL;three.non_zero_amount++;if(three.rhead[i]==NULL)three.rhead[i]=prow=insert;else{prow->right=insert;prow=insert;}if(three.chead[j]==NULL)three.chead[j]=pcolum=insert;else{pcolum->down=insert;pcolum=insert;}}else if(pone->colum>ptwo->row){ptwo=ptwo->down;continue;}else{pone=pone->right;continue;}}}}return OK;}int main(void){crosslist one,two,three;char flag;printf("<Creat the first matrix>\n");creat_matrix(one);putchar('\n');printf("Print the first matrix\n");printf("Row\tColum\tValue\n");printf("-----------------------------------\n");print_matrix(one);printf("<Initialization>\n");init_matrix(two);putchar('\n');printf("<Creat the second matrix>\n");creat_matrix(two);putchar('\n');printf("Print the second matrix\n");printf("Row\tColum\tValue\n");printf("-----------------------------------\n");print_matrix(two);printf("Multiply the two matrix\n");init_matrix(three);multi_matrix(one,two,three);printf("The result is below:\n");print_matrix(three);system("pause");}。

案例教学法在数据结构稀疏矩阵十字链表存储与运算教学中的应用徐聚星【摘要】For undergraduates in junior grade,data structure is comparatively difficult because their logic thinking is finite.This paper takes the storage and operation of sparse matrix cross chain table for example,case preparation,case analysis and discussion,and case analysis report writing and so on are been expatiated.Problems met with in teaching process are analyzed and worked out,so as to emphasize student-centered teaching mode,stimulate students＇ initiative and autonomy and optimize teaching reform eventually.%数据结构课程作为一门较难的课程开设于低年级本科生教学中,由于学生的抽象逻辑思维有限造成了学习较为困难。

通过以稀疏矩阵十字链表存储与运算为例,简单从案例准备、案例分析与讨论以及案例分析报告撰写等环节进行阐述,分析授课过程中遇到的问题,并予以研究和解决。

以起到学生在教学中的主体地位、激发学生学习主动性和自主性的目的,实现教学改革的优化。

【期刊名称】《兴义民族师范学院学报》【年(卷),期】2011(000)003【总页数】4页(P59-62)【关键词】数据结构;稀疏矩阵;案例教学【作者】徐聚星【作者单位】贵州财经学院,贵州贵阳550000【正文语种】中文【中图分类】G623.58数据结构是计算机专业及相关专业的一门重要的专业基础课程。

稀疏矩阵的⼗字链表存储稀疏矩阵的压缩存储有⼏种⽅式，如：三元组顺序表、⾏逻辑链接的顺序表和⼗字链表。

使⽤链表存储的好处是：便于矩阵中元素的插⼊和删除。

例如：“将矩阵B加到矩阵A上”，那么矩阵A存储的元素就会有变动。

⽐如会增加⼀些⾮零元，或者删除⼀些元素（因为b ij+a ij=0）。

下图是矩阵M和M的⼗字链表存储：⼗字链表及其结点可⽤如下结构体表⽰：typedef struct OLNode{int i, j; // ⾮零元的⾏列下标ElemType e;struct OLNode *right, *down; // 向右域和向下域} OLNode, *OLink;typedef struct{OLink *rhead, *chead; // ⾏链表和列链表的头指针数组int mu, nu, tu; // 稀疏矩阵的⾏数、列数和⾮零元个数} CrossList;在通过代码创建⼗字链表时，要特别注意right、down和rhead、chead这些指针的赋值。

现在来看“将矩阵B加到矩阵A上”这个问题。

所要做的操作：a ij +b ij，其结果⼀共会有4种情况：1. a ij（b ij = 0）（不做变化）2. b ij（a ij = 0）（在A中插⼊⼀个新结点）3. a ij +b ij ≠ 0 （改变结点a ij的值域）4. a ij +b ij = 0 （删除结点a ij）假设指针pa和pb分别指向矩阵A和B中⾏值相同的两个结点，对于上述4种情况的处理过程为：1. 若“pa == NULL”或“pa->j⼤于pb->j”，则在矩阵A中插⼊⼀个值为b ij的结点。

并且需要修改同⼀⾏前⼀结点的right指针，和同⼀列前⼀结点的down指针。

2. 若“pa->j⼩于pb-j”，则pa指针右移⼀步。

3. 若“pa->j等于pb-j”，并且“pa->e + pb->e != 0”，则修改pa->e即可。

数据结构课程设计《数据结构》课程设计一.题目：稀疏矩阵应用（限1 人完成）要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。

（1）稀疏矩阵的存储（2）稀疏矩阵加法（3）矩阵乘法（4）矩阵转置二.算法思想描述：1．需求分析（1）设计函数建立稀疏矩阵，初始化值。

（2）设计函数输出稀疏矩阵的值。

（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。

（4）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。

（5）构造函数进行稀疏矩阵的转置，并输出结果。

（6）退出系统。

1.算法概述：首先用两个结构体来定义十字链表元素：typedef struct OLNode{int i,j;int e;struct OLNode *right,*down;}OLNode,*OLink;OLNode结构为链表结点，i,j,e分别表示稀疏矩阵中元素的行，列和值。

typedef struct {int mu,nu,tu; //行数mu，列数nu，非零元素的个数tuOLink *rhead,*chead;}CrossList;CrossList结构用于连接起各个结点，mu,nu,tu分别表示整个矩阵的行数列数和非零元素的个数。

整个程序包含CreateSMatix_OL（用于创建十字链表），SMatrix_ADD（十字链表相加），ShowMAtrix(十字链表显示)，MultSMatrix_OL（十字链表相乘），TurnSMatrix_OL（十字链表转置），DestroySMatrix_OL（十字链表销毁）六个函数。

CreateSMatix_OL的功能如下：首先输入稀疏矩阵的行数，列数，非零元素的个数，为*rhead和*chead分配内存空间，并将十字链表中节点初始化为NULL。

然后依次输入非零元素的行，列，值，以0 0 0为结尾结束链表的连接和while循环。

SMatrix_ADD 的功能如下：在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵，连接结束后SMatrix_ADD 函数以循环的方式比较非零元素是否为同一行列，如果是则两值相加，如果不是则把第二个元素加入链表中。

稀疏矩阵的存储和乘法操作⼀稀疏矩阵的存储1.三元组顺序表三元组表⽰法就是在存储⾮零元的同时，存储该元素所对应的⾏下标和列下标。

稀疏矩阵中的每⼀个⾮零元素由⼀个三元组(i,j,a ij)唯⼀确定。

矩阵中所有⾮零元素存放在由三元组组成的顺序表中(通常⽤数组)。

所以三元组的逻辑结构如下：//————稀疏矩阵的三元组表⽰法————//#define MAX_SIZE 1500 //表⽰稀疏矩阵的⾮零元素的最⼤个数class Triple{int i,j;//表⽰⾮零元素的⾏下表和列下标int val;//⾮零元素的值，此处以int类型为例};class TSMatrix{Triple data[MAX_SIZE];int row_num,col_num,cnt;//稀疏矩阵的⾏数、列数以及⾮零元素的个数};注意，此处的⾮零元素的三元组是以⾏序为主序顺序排列的。

2.⾏逻辑链接顺序表⾏逻辑链接顺序表的实质就是在三元组顺序表的基础上加了⼀个数组，这个数组⽤于存储稀疏矩阵中每⾏的第⼀个⾮零元素的在三元组顺序表中的位置(此处⼀定要理解对，是在三元组顺序表中的位置)。

所以其逻辑结构如下：//————稀疏矩阵的⾏逻辑链接表⽰法————//#define MAX_SIZE 1500 //表⽰稀疏矩阵的⾮零元素的最⼤个数#define MAX_ROW 1500 //表⽰稀疏矩阵的⾏数的最⼤个数class Triple{int i,j;//表⽰⾮零元素的⾏下表和列下标int val;//⾮零元素的值，此处以int类型为例};class RLSMatrix{Triple data[MAX_SIZE]; //⾮零元三元组表int rpos[MAX_ROW];//每⾏第⼀个⾮零元素的位置int row_num,col_num,cnt;//稀疏矩阵的⾏数、列数以及⾮零元素的个数};3.⼗字链表当稀疏矩阵的⾮零元个数和位置在操作过程中变化较⼤时，就不易采⽤顺序存储结构来表⽰三元组的线性表。

采⽤⼗字链表存储的稀疏矩阵Description当矩阵的⾮零元个数和位置在操作过程中变化较⼤时，就不宜采⽤顺序存储的结构来表⽰三元组的线性表了。

因此，在这种情况下，采⽤链式存储结构表⽰三元组更为恰当。

⼗字链表就是能够实现这样功能的⼀种数据结构。

在⼗字链表中，每个⾮零元可以⽤⼀个包含5个域的结点表⽰。

其中i、j和e这3个域分别表⽰该⾮零元所在的⾏、列和⾮零元的值，向右域right⽤来链接同⼀⾏中下⼀个⾮零元，⽽向下域down⽤来链接同⼀列中下⼀个⾮零元。

同⼀⾏的⾮零元通过right域链接成⼀个线性链表，同⼀列的⾮零元通过down域链接成⼀个线性链表。

每个⾮零元既是某个⾏链表中的⼀个结点，⼜是某个列链表中的⼀个结点，整个矩阵通过这样的结构形成了⼀个⼗字交叉的链表。

稀疏矩阵的⼗字链表类型可以描述如下：下⾯是建⽴稀疏矩阵⼗字链表的算法描述：给出⼀个稀疏矩阵，请将其存储到⼀个⼗字链表中，并将存储完毕的矩阵输出。

Input输⼊的第⼀⾏是两个整数r和c（r<200, c<200, r*c <= 12500），分别表⽰⼀个包含很多0的稀疏矩阵的⾏数和列数。

接下来有r⾏，每⾏有c个整数，⽤空格隔开，表⽰稀疏矩阵的各个元素。

Output输出读⼊的矩阵。

输出共有r⾏，每⾏有c个整数，每个整数后输出⼀个空格。

请注意⾏尾输出换⾏。

Sample Input5 60 18 0 0 0 00 0 67 0 0 00 0 0 0 0 410 0 47 62 0 00 0 0 0 0 35Sample Output0 18 0 0 0 00 0 67 0 0 00 0 0 0 0 410 0 47 62 0 00 0 0 0 0 35HINT提⽰：对于m⾏n列且有t个⾮零元的稀疏矩阵，算法5.4的执⾏时间为O(t×s)，其中s=max(m,n)。

这是由于每建⽴⼀个⾮零元结点时，都需要通过遍历查询它所在的⾏表和列表中的插⼊位置。

稀疏矩阵的压缩存储及运算一、实验内容实现稀疏矩阵的压缩存储方法以及在特定存储方法下的基本运算二、实验母的掌握数组的应用，包括稀疏矩阵、特殊矩阵的压缩存储方法。

矩阵的基本运算的实现，包括矩阵相加、转置、乘法等。

三、问题描述1）用行逻辑链接顺序表和十字链表分别实现稀疏矩阵的压缩存储2）编程实现矩阵的转置运算和乘法运算（运用行逻辑链接顺序表或十字链表作为存储结构）四、问题的实现稀疏矩阵的抽象数据类型定义：ADT SpareseMatrix{数据对象：;,,2,1;,,2,1|{n j m i D a ij ===},,列数分别称为矩阵的行数和和n m ElemSet a j i ∈数据关系： ：}1,11|,{}11,1|,{},{,1,1,,n j m i Col n j m i Row Col Row R a a a a j i j i j i j i ≤≤-≤≤><=-≤≤≤≤><==++基本操作：CreateSMatrix(&M)；操作结果：创建稀疏矩阵M 。

PrintSMatrix(M)；初始条件：稀疏矩阵M 存在。

操作结果：输出稀疏矩阵M 。

AddSMatrix(M ，N ，&Q)；初始条件：稀疏矩阵M 和N 的行数和列数对应相等。

操作结果：求稀疏矩阵的和Q=M+N 。

MultSMatrix(M ，N ，&Q)；初始条件：稀疏矩阵M 的列数等于N 的行数。

操作结果：求稀疏矩阵乘积Q=M*N 。

TransposeSMatrix(M,&T)；初始条件：稀疏矩阵M 存在。

操作结果：求稀疏矩阵M 的转置矩阵T 。

}ADT SpareseMatrix五、主要源程序代码#include <iostream>using namespace std;#define MAXSIZE 100;typedef struct OLNode{int i,j;int e;struct OLNode *right,*down;}OLNode,*OLink;typedef struct{OLink *rhead,*chead;int mu,nu,tu;}CrossList; //十字链表结构体定义int CreatSMatrix_OL(CrossList &M){int i,j,e;OLink q;OLink p;cout<<"请输入稀疏矩阵的行数，列数，非零元素的个数：";cin>>M.mu;cin>>M.nu;cin>>M.tu;M.rhead=(OLink *)malloc((M.mu+1)*sizeof(OLNode));M.chead=(OLink *)malloc((M.nu+1)*sizeof(OLNode));for(i=1;i<=M.mu;i++) M.rhead[i]=NULL;for(i=1;i<=M.nu;i++) M.chead[i]=NULL;cout<<"请输入稀疏矩阵，若为空，则退出"<<endl;cin>>i;cin>>j;cin>>e;while (i!=0){p=(OLink)malloc(sizeof(OLNode));p->i=i;p->j=j;p->e=e;if (M.rhead[i]==NULL || M.rhead[i]->j>j) {p->right=M.rhead[i];M.rhead[i]=p;}else{q=M.rhead[i];while (q->right && q->right->j<j)q=q->right;p->right=q->right;q->right=p;}if (M.chead[j]==NULL || M.chead[j]->i>i) {p->down=M.chead[j];M.chead[j]=p;}else{q=M.chead[j];while (q->down && q->down->i<i)q=q->down;p->down=q->down;q->down=p;}cin>>i;cin>>j;cin>>e;}} //创建十字链表void TurnSMatrix_OL(CrossList &M){int a,b;OLink p,q;for(a<1;a<=M.mu;a++){q=p=M.rhead[a];while(q){b=p->i;p->i=p->j;p->j=b;q=p->right;p->right=p->down;p->down=q;}}} //十字链表实现稀疏矩阵转置int AddSMatrix_OL(CrossList *A,CrossList *B){OLNode *pa,*pb,*p,*pre,*cp[100];int i,j,t;t=A->tu+B->tu;for(j=1;j<=A->nu;j++) cp[j]=A->chead[j];for(i=1;i<=A->mu;i++){pa=A->rhead[i];pb=B->rhead[i];pre=NULL;while(pb){if(pa==NULL || pa->j>pb->j){p=(OLink)malloc(sizeof(OLNode));if(!pre)A->rhead[i]=p;else pre->right=p;p->right=pa;pre=p;p->i=i;p->j=pb->j;p->e=pb->e;if(!A->chead[p->j]){A->chead[p->j]=cp[p->j]=p;p->down=NULL;}else{cp[p->j]->down=p;cp[p->j]=p;}pb=pb->right;}else if(pa->j<pb->j) {pre=pa;pa=pa->right;}else if(pa->e+pb->e){t--;pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;}else{t=t-2;if(!pre)A->rhead[i]=pa->right;else pre->right=pa->right;p=pa;pa=pa->right;if(A->chead[p->j]==p) A->chead[p->j]=cp[p->j]=p->down;else cp[p->j]->down=p->down;free(p);pb=pb->right;}}}A->mu=A->mu>B->mu? A->mu:B->mu;A->nu=A->nu>B->nu? A->nu:B->nu;return 1;} //十字链表实现两稀疏矩阵相加int MultSMatrix_OL(CrossList M,CrossList N,CrossList &Q){int i,j,e;OLink p0,q0,p,p1,p1a;if(M.nu!=N.mu){cout<<"稀疏矩阵A的列数和B的行数不相等，不能相乘";return 0;}Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(!(Q.rhead=(OLink *)malloc((Q.mu+1)*sizeof(OLink))))exit(-2);if(!(Q.chead=(OLink *)malloc((Q.nu+1)*sizeof(OLink))))exit(-2);for(i=1;i<=Q.mu;i++) Q.rhead[i]=NULL;for(i=1;i<=Q.nu;i++) Q.chead[i]=NULL;for(i=1;i<=Q.mu;i++)for(j=1;j<=Q.nu;j++){p0=M.rhead[i];q0=N.chead[j];e=0;while(p0 && q0){if(p0->j>q0->i) q0=q0->down;else if(p0->j<q0->i) p0=p0->right;else{e+=p0->e*q0->e;q0=q0->down;p0=p0->right;}}if(e){if(!(p=(OLink)malloc(sizeof(OLNode))))exit(-2);Q.tu++;p->i=i;p->j=j;p->e=e;p->right=NULL;p->down=NULL;if(Q.rhead[i]==NULL)Q.rhead[i]=p1=p;else p1->right=p;p1=p;if(Q.chead[j]==NULL)Q.chead[j]=p;else{p1a=Q.chead[j];while(p1a->down)p1a=p1a->down;p1a->down=p;}}}return 1;} //十字链表实现两稀疏矩阵相乘int ShowSMatrix(CrossList *A){int a;OLink p;for(a=1;a<=A->mu;a++)if(A->rhead[a]) {p=A->rhead[a];}while(p){printf("%3d%3d%3d\n",p->i,p->j,p->e);p=p->right;}return 1;} //十字链表显示void main(){int n;char c;CrossList MM,TT,SS;CreatSMatrix_OL(MM);cout<<"您输入的稀疏矩阵（只列出非零元素）："<<endl;cout<<"行列大小"<<endl;ShowSMatrix(&MM);cout<<"请选择操作："<<endl;cout<<"1：实现稀疏矩阵的转置"<<endl;cout<<"2：实现两稀疏矩阵的相加"<<endl;cout<<"3：实现两稀疏矩阵的相乘"<<endl;cout<<"4：退出程序"<<endl;cin>>n;switch(n){case 1:TurnSMatrix_OL(MM);cout<<"转置后的稀疏矩阵：行列大小"<<endl;ShowSMatrix(&MM);break;case 2:cout<<"请输入另一个稀疏矩阵："<<endl;CreatSMatrix_OL(TT);AddSMatrix_OL(&MM,&TT);cout<<"相加后的矩阵为："<<endl;ShowSMatrix(&MM);break;case 3:cout<<"请输入另一个稀疏矩阵："<<endl;CreatSMatrix_OL(TT);MultSMatrix_OL(MM,TT,SS);cout<<"相乘后的矩阵为："<<endl;ShowSMatrix(&SS);break;case 4:exit(0);default:cout<<"error!"<<endl;}system("pause");}六、总结整个实验中学会了稀疏矩阵的压缩存储方法，用十字链表来存储，以及在特定存储方法下的基本运算。