实验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数据结构是计算机专业及相关专业的一门重要的专业基础课程。