稀疏矩阵-引用-十字链表-运算(共36页)

1、精选优质文档-倾情为你奉上 稀疏矩阵应用摘 要 本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。在程序设计中，考虑到方法的难易程度，采用了先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘操作的方法，再在十字链表下实现。程序通过调试运行，结果与预期一样，初步实现了设计目标。关键词 程序设计；稀疏矩阵；三元组；十字链表 1 引言 · 课程设计任务本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表

2、示，并在两种不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C； 求出A的转置矩阵D，输出D； 求两个稀疏矩阵A和B的相乘矩阵E，并输出E。· 课程设计性质数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和数据结构课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现，包括在三元组和十字链表下存储稀疏矩阵，并对输入的稀疏矩阵进行转置，相加，相乘等操作，最后把运算结果输出。此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。1.3课程设计目的其目的是

3、让我们在学习完C、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等基本操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 · 需求分析 2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。首先要定义两种不同的结构体类型，在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能

4、够对错误进行判别处理，初始化稀疏矩阵都为空值，特别注意在十字链表下，对变量进行动态的地址分配。在设计输出稀疏矩阵的值的函数时，也要针对两种不同的情况，分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化及输出值时，均只输出非零元素的值和它所在的所在行及所在列。2.2构造函数进行稀疏矩阵的转置并输出结果本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果，由于对稀疏函数的转置只对一个矩阵进行操作，所以实现起来难度不是很大，函数也比较容易编写。在编写函数时，要先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。2.3构造函数进行两个稀疏矩阵相加及相乘并输出最终的稀疏矩阵本模

5、块要求设计相加和相乘函数对两个矩阵进行运算，并输出最终的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，看是不是相同类型的矩阵，因为两个矩阵相加要求两个矩阵一定是同一类型的矩阵，定义相应的矩阵类型用于存放两个矩阵相加相乘后的结果矩阵，这个结果矩阵的行数列数需要综合多方面情况来确定。这四个函数也是整个程序的难点，需要灵活运用数组及指针的特点。2.4退出系统本模块要求设置选项能随时结束程序的运行，本程序中采用exit(0)函数。程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。· 概要设计3.1主界面设计为了实现在两种

6、存储结构下对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图1所示。图1主界面图3.2存储结构设计本系统采用三元组结构和十字链表结构存储稀疏矩阵的具体信息。其中：在三元组中，所有元素的信息用数组表示，每个数组元素中包含有行下标(i)，列下标(j)和对应的数值(e)，它们是整型数据，全部的信息用在十字链表中，全部结点的信息用结构体（TSMatrix）包含，包括用数组（Triple dataMAXSIZE）和总共的行数（mu）,列数（nu）以及非零元素的个数(tu)。在十字链表下，头结点为指针数组的

7、十字链表存储；每个结点里面包含行下标(i)，列下标(j)和对应的数值(e)，它们是整型数据，还有两个指针(right)、(down),属于OLNode结构体。全部的信息用结构体(crosslist)包含，包括指针数组(OLink* rhead和*chead）和总共的行数（mu）,列数（nu）以及非零元素的个数(tu)。三元组结构体定义: typedef structint i,j;int e;Triple;typedef structTriple dataMAXSIZE; int rposMAXSIZE + 1; int nu,mu,tu;TSMatrix; 十字链表结构体定义: typede

8、f struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu;OLink *rhead,*chead;CrossList; 3.3系统功能设计本系统除了要完成分别在三元组存储结构以及在十字链表下实现稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的建立及初始化在三元组存储结构下，由函数 void CreateSMatrix(TSMatrix &M)实现，在十字链表存储结构下，由函数void CreateSMatix_OL(CrossList &am

9、p;M)依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。（1）稀疏矩阵的转置：此功能在三元组存储结构下，由函数void TransposeSMatrix(TSMatrix M,TSMatrix &T)实现，在十字链表存储结构下，由函数void TurnSMatrix_OL(CrossList &M)实现。当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。（2）稀疏矩阵的加法：此功能在三元组存储结构下，由函数void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S

10、)实现，在十字链表存储结构下，由函数int SMatrix_ADD(CrossList *A,CrossList *B)实现。当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。（3）稀疏矩阵的乘法：此功能在三元组存储结构下，由函数int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)实现。在十字链表存储结构下，由函数int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q)实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵

11、的详细信息。然后进行相乘，最后得到结果。（4）退出：即退出稀疏矩阵的应用系统，由exit(0)函数实现。当用户选择该功能，则退出该稀疏矩阵的应用系统。4 详细设计4.1 数据类型定义三元组结构体定义: typedef struct /三元组结构体int i,j; /行标、列表int e; /值 Triple;typedef structTriple dataMAXSIZE; /三元组表 int rposMAXSIZE + 1; int nu,mu,tu; /行数、列数、非零元个数TSMatrix; 十字链表结构体定义: typedef struct OLNode /结点结构int i,j; /

12、行标、列标 int e; /值struct OLNode *right,*down; /同一行、列的下一个结点OLNode,*OLink;typedef struct int mu,nu,tu; /行数、列数、非零元个数OLink *rhead,*chead; /行、列指针基指CrossList; 4.2系统主要子程序详细设计A. 主程序模块设计：void main()int n,i;TSMatrix M,T,S; /声明三个三元组数组CrossList MM,TT,SS; /声明三个十字链表printf(" *稀疏矩阵应用*");printf("n请你选择创建稀

13、疏矩阵的方法：n1：用三元组创建稀疏矩阵n2:用十字链表创建稀疏矩阵n3:退出程序");printf("n");scanf("%d",&n);switch(n)case 1:CreateSMatrix(M); /创建三元组矩阵printf("您输入的稀疏矩阵为（只列出非零元素）：n 行 列 大小n");ShowTMatrix(M); /显示三元组矩阵printf("已经选择三元组创建稀疏矩阵，请选择操作:n1：稀疏矩阵转置n2：稀疏矩阵相加n3：稀疏矩阵相乘n4：退出程序n");scanf(&qu

14、ot;%d",&i);switch(i)case 1:TransposeSMatrix(M,T); /对三元组矩阵进行转置printf("转置后的矩阵为（只列出非零元素）：n 行 列 大小n");ShowTMatrix(T);break;case 2:printf("请你输入另一个稀疏矩阵:"); CreateSMatrix(T); AddTMatix(M,T,S); /两个三元组矩阵相加printf("相加后的矩阵为（只列出非零元素）：n 行 列 大小n"); ShowTMatrix(S); break;case

15、3:printf("请你输入另一个稀疏矩阵:"); CreateSMatrix(T); MultSMatrix(M,T,S); /两个三元组矩阵相乘 printf("相乘后的矩阵为（只列出非零元素）：n 行 列 大小n"); ShowTMatrix(S); break;case 4:exit(0);break;case 2:CreateSMatix_OL(MM); /创建十字链表矩阵 printf("您输入的稀疏矩阵为（只列出非零元素）：n 行 列 大小n"); ShowMAtrix(&MM); /显示十字链表矩阵 print

16、f("已经选择十字链表创建稀疏矩阵，请选择操作: 1：稀疏矩阵转置n 2：稀疏矩阵相加n 3：稀疏矩阵相乘n 4：退出程序n");scanf("%d",&i);switch(i)case 1: TurnSMatrix_OL(MM); /十字链表矩阵转置 printf("转置后的矩阵为（只列出非零元素）：n 行 列 大小n"); ShowMAtrix(&MM); break;case 2: printf("请你输入另一个稀疏矩阵:"); CreateSMatix_OL(TT); SMatrix_ADD

17、(&MM,&TT); /两个十字链表矩阵相加 printf("相加后的矩阵为（只列出非零元素）：n 行 列 大小n"); ShowMAtrix(&MM);break;case 3:printf("请你输入另一个稀疏矩阵:"); CreateSMatix_OL(TT); MultSMatrix_OL(MM,TT,SS); /两个十字链表矩阵相乘 printf("相乘后的矩阵为（只列出非零元素）：n 行 列 大小n"); ShowMAtrix(&SS);break;case 4:exit(0); ;brea

18、k;case 3:exit(0);default :printf("erorr");B. 稀疏矩阵操作各子函数的定义：(1)建立与初始化稀疏矩阵：void CreateSMatrix(TSMatrix &M)/采用三元组顺序表存储表示，创建稀疏矩阵M printf("请输入稀疏矩阵的行数、列数和非零元个数：");scanf("%d%d%d",&M.mu,&M.nu,&M.tu);if(M.mu<=0)|(M.nu<=0)|(M.tu<=0)|(M.tu>M.mu*M.nu)/判断

19、行值、列值、元素个数是否合法 printf("输入有误！"); for(int i=1;i<=M.tu;i+)/输入稀疏矩阵元素 printf("请输入元素坐标(所在行，所在列）及大小："); scanf("%d%d%d",&M.datai.i,&M.datai.j,&M.datai.e); if(M.datai.i<=0)|(M.datai.j<=0) printf("输入错误，请重新输入"); scanf("%d%d%d",&M.datai.

20、i,&M.datai.j,&M.datai.e); int num100; if(M.tu) int i; for(i = 1; i <= M.mu; i+) numi = 0;/初始化 for(int t = 1; t <= M.tu; t+) +numM.datat.i;/求M中每一行含非零元素个数 /求rpos M.rpos1 = 1; for(i = 2; i <= M.mu; i+) M.rposi = M.rposi-1 + numi-1; /创建三元组int CreateSMatix_OL(CrossList &M) int i,j,e;

21、 OLink q; OLink p;printf("请输入稀疏矩阵的行数，列数，非零元素的个数"); /矩阵行数，列数下标均从开始；scanf("%d%d%d",&M.mu,&M.nu,&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.rheadi=NULL;/把矩阵每个元素置空值for( i=1;i&l

22、t;=M.nu;i+)M.cheadi=NULL;printf("请输入稀疏矩阵，如果行为，则退出n");scanf("%d%d%d",&i,&j,&e);while(i!=0)p=(OLink)malloc(sizeof(OLNode);p->i=i;p->j=j;p->e=e;if(M.rheadi=NULL|M.rheadi->j>j)p->right=M.rheadi;M.rheadi=p;else q=M.rheadi; while(q->right&&q->

23、;right->j<j)q=q->right; p->right=q->right; q->right=p;if(M.cheadj=NULL|M.cheadj->i>i)p->down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while(q->down&&q->down->i<i)q=q->down;p->down=q->down;q->down=p;scanf("%d%d%d",&i,&j,&e);re

24、turn 1;/创建十字链表（2）输出稀疏矩阵：void ShowTMatrix(TSMatrix M)for(int col=1;col<=M.mu;col+)/通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显示出来for(int p=1;p<=M.tu;p+)if(M.datap.i=col)printf("%4d %4d %4dn",M.datap.i,M.datap.j,M.datap.e);/三元组显示int ShowMAtrix(CrossList *A) int col; OLink p; for(col=1;col<=A->m

25、u;col+)if(A->rheadcol)p=A->rheadcol;/通过循环，把A结点的rheadcol赋给p while(p)printf("%3d%3d%3dn",p->i,p->j,p->e);p=p->right; return 1;/十字链表显示（3）实现矩阵的转置：void TransposeSMatrix(TSMatrix M,TSMatrix &T)T.nu=M.mu;/T矩阵存放转置后的矩阵T.mu=M.nu;T.tu=M.tu;int q=1;for(int col=1;col<=M.nu;col+

26、)/通过循环，把非零元素的行数与列数进行交换，实现转置for(int p=1;p<=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;q+;/三元组转置void TurnSMatrix_OL(CrossList &M)int col,row; /定义循环变量OLink p,q; /定义OLink结构类型变量for(col=1;col<=M.mu;col+) /通过循环，把非零元素的行数与列数进行交换，实现转置 q=p=M.rheadcol;while(q)

27、row=p->i;p->i=p->j;p->j=row;q=p->right;p->right=p->down;p->down=q;/十字链表转置（4）实现两个矩阵的相加：void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S)/矩阵S存放相加后的矩阵 S.mu=M.mu>T.mu?M.mu:T.mu;/对S矩阵的行数赋值 S.nu=M.nu>T.nu?M.nu:T.nu;/对S矩阵的列数赋值 S.tu=0; int ce; int q=1;int mcount=1,tcount=1;

28、 while(mcount<=M.tu&&tcount<=T.tu) switch(Compare(M.datamcount.i,M.datamcount.j,T.datatcount.i,T.datatcount.j) /用switch分支语句，用compare函数对需要相加的两个矩阵的某元素行数列数进行比较 case -1: S.dataq.e=M.datamcount.e;/当M.datamcount.i<T.datatcount.i或M.datamcount.j<T.datatcount.j S.dataq.i=M.datamcount.i; S

29、.dataq.j=M.datamcount.j;/把第一个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q+; mcount+; break; case 1: S.dataq.e=T.datatcount.e;/当M.datamcount.i>T.datatcount.i或M.datamcount.j>T.datatcount.j S.dataq.i=T.datatcount.i; S.dataq.j=T.datatcount.j;/把第二个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q+; tcount+; break; case 0: ce=M.datamcount.

30、e+T.datatcount.e;/其他情况下把两个矩阵的值相加 if(ce) S.dataq.e=ce; S.dataq.i=M.datamcount.i; S.dataq.j=M.datamcount.j; q+; mcount+; tcount+; else mcount+; tcount+; break; while(mcount<=M.tu)S.dataq.e=M.datamcount.e;S.dataq.i=M.datamcount.i;S.dataq.j=M.datamcount.j;q+;mcount+; /在case=-1的情况下对S矩阵的非零值，行数，列数进行赋值 w

31、hile(tcount<=M.tu) S.dataq.e=T.datatcount.e; S.dataq.i=T.datatcount.i; S.dataq.j=T.datatcount.j; q+; tcount+; /在case=1的情况下对S矩阵的非零值，行数，列数进行赋值 S.tu=q-1;/三元组相加int SMatrix_ADD(CrossList *A,CrossList *B)OLNode *pa,*pb,*pre,*p,*cp100; /定义OLNode类型的变量int i,j,t;t=A->tu+B->tu;for(j=1;j<=A->nu;j

32、+)cpj=A->cheadj;/将A矩阵的列表头指针赋给cp数组for(i=1;i<=A->mu;i+)pa=A->rheadi;pb=B->rheadi;/将A，B矩阵的行表头指针分别赋给pa，pbpre=NULL;while(pb)/当pb不等于零 if(pa=NULL|pa->j>pb->j)p=(OLink)malloc(sizeof(OLNode);/给p动态分配空间if(!pre)A->rheadi=p;else pre->right=p;p->right=pa;pre=p;p->i=i;p->j=pb

33、->j;p->e=pb->e;if(!A->cheadp->j)A->cheadp->j=cpp->j=p;p->down=NULL;/如果A->cheadp->j不等于零，则把p赋给它及cpp->jelsecpp->j->down=p;cpp->j=p;pb=pb->right;/否则把p赋给cpp->jelse if(pa->j<pb->j)pre=pa; pa=pa->right; else if(pa->e+pb->e) t-; pa->e+=

34、pb->e; pre=pa; pa=pa->right; pb=pb->right; else t=t-2; if(!pre)A->rheadi=pa->right; else pre->right=pa->right; p=pa;pa=pa->right; if(A->cheadp->j=p)A->cheadp->j=cpp->j=p->down; else cpp->j->down=p->down; free(p); pb=pb->right;A->mu=A->mu>

35、;B->mu?A->mu:B->mu;A->nu=A->nu>B->nu?A->nu:B->nu;/A的行与列为A及B当中较大的一个return 1;/十字链表相加（5）实现两个矩阵的相乘：int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) int arow, brow, ccol, i, t, ctemp100, p, q, tp; /定义相乘函数中所需要用到的变量 if(M.nu != N.mu) return 0;/如果第一个矩阵的行数不等于第二个矩阵的列数，则退出 Q.m

36、u = M.mu, Q.nu = N.nu, Q.tu = 0;/三元组结构类型Q存放相乘后的结果 if(M.tu * N.tu != 0)/如果两个矩阵元素相乘不为零，则进行运算 for(arow = 1; arow <= M.mu; +arow)；/最外侧循环以矩阵行数作为循环变量 for(i = 0; i <= N.nu; +i) ctempi = 0; Q.rposarow = Q.tu + 1; if(arow < M.mu) tp = M.rposarow + 1; else tp = M.tu +1; for(p = M.rposarow; p < tp;

37、 +p)/把每行与每列相乘 brow = M.datap.j; if(brow < N.mu) t = N.rposbrow+1; else t = N.tu + 1; for(q = N.rposbrow; q < t; +q) ccol = N.dataq.j; ctempccol += M.datap.e * N.dataq.e;/值相乘 for(ccol = 1; ccol <= Q.nu; +ccol) /把运算后的结果存放到Q中 if(ctempccol) if(+(Q.tu) > MAXSIZE) return 1; Q.dataQ.tu.i = arow

38、, Q.dataQ.tu.j = ccol, Q.dataQ.tu.e = ctempccol; return 1;/三元组相乘int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q) int i, j, e; /中间变量 OLink p0, q0, p, pl, pla; /中间变量 if(M.nu != N.mu) /检查稀疏矩阵M的列数和N的行数是否对应相等 printf ( "稀疏矩阵A的列数和B的行数不相等，不能相乘。n" ); return 0; Q.mu = M.mu, Q.nu = N.nu

39、, 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.rheadi = NULL; for(i = 1; i <= Q.nu; i+) Q.cheadi = NULL; /相乘 for(i =1; i <= Q.mu; i+) for(j = 1; j <= Q.nu; j+) p

40、0 = M.rheadi, q0 = N.cheadj, e = 0; while(p0&&q0) /M第i行和N第j列有元素 if( p0->j > q0->i) q0 = q0->down;/M的列大于N的行，则N的列指针后移 else if(p0->j < q0->i) p0 = p0->right;/M的列小于N的行，则M的行指针右移 else /M的行等于N的列 e += p0->e * q0->e; /乘积累加 q0 = q0->down, p0 = p0->right; /移动指针 if(e)

41、 /乘积不为零 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;/赋值，指针后移 /将p插入十字链表 /行插入 if(Q.rheadi = NULL) /若p为该行的第个结点 Q.rheadi = pl = p; /p插在该行的表头且pl指向p(该行的最后一个结点) else pl->right = p, pl = p; /插在pl所指结点之后，pl右移 /列插

42、入 if(Q.cheadj = NULL) /若p为该列的第一个结点 Q.cheadj = p; /该列的表头指向p else /插在列表尾 pla = Q.cheadj;/pla指向j行的第个结点 while(pla->down) pla = pla->down;/pla指向j行最后一个结点 pla->down = p; return 1;/十字链表相乘· 调试分析5.1系统运行主界面系统运行主界面如图2所示：图2 主界面图5.2 各子功能测试运行结果（1）稀疏矩阵的创建及初始化：在主菜单下，用户输入1回车，是用三元组创建稀疏矩阵，根据屏幕提示初始化一个稀疏矩阵，

43、按enter键，运行结果如图3所示。 图3 三元组创建并初始化矩阵在主菜单下，用户输入2回车，是用十字链表创建稀疏矩阵，根据屏幕提示初始化一个稀疏矩阵，按enter键，运行结果如图4所示。图4 十字链表创建并初始化矩阵（2）稀疏矩阵的转置：用三元组创建稀疏矩阵后，用户输入1回车，便显示该矩阵的转置矩阵，运行结果如图5所示。图5 三元组稀疏矩阵转置结果示意图用十字链表创建稀疏矩阵后，用户输入1回车，便显示该矩阵的转置矩阵，运行结果如图6所示。图6 十字链表稀疏矩阵转置结果示意图（3）稀疏矩阵的相加：用三元组创建并初始化一个稀疏矩阵后，输入2回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter

44、键，运行结果如图7所示。图7 三元组稀疏矩阵相加结果示意图用十字链表创建并初始化一个稀疏矩阵后，输入2回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter键，运行结果如图8所示。图8 三元组稀疏矩阵相加结果示意图（4）稀疏矩阵的相乘：用三元组创建并初始化一个稀疏矩阵后，输入3回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter键，运行结果如图9所示。图9 三元组稀疏矩阵相乘结果示意图用十字链表创建并初始化一个稀疏矩阵后，输入3回车，按屏幕提示输入第二个同类型的稀疏矩阵，按enter键，运行结果如图10所示。图10 十字链表稀疏矩阵相乘结果示意图（5）退出：在主菜单下，用户输入3回车，或

45、者在下级菜单中输入4回车，退出程序。运行结果如图11，图12。图11 主菜单退出程序图图12 下级菜单退出程序图· 总结由于本程序要求用两种办法对稀疏矩阵进行运算，特别是用十字链表这种形式来对稀疏矩阵进行运算，是实现起来有很多困难，主要包括：1、书上这种方面的东西不多，资料少，可以参考的东西不是很多；2、用十字链表进行运算比较复杂，难度较大，需要对指针掌握较好；3、在书写课程设计报告时，没有具体的模板，感觉无从下手。针对上述困难，自己对症下药，通过网络，图书馆找资料，借鉴别人的已往的优秀的课程设计报告，和同学们一起讨论，逐步地解决自己的问题。 通过此次课程设计，使我对本学期学的数据结

46、构有了更深的了解，也使自己的所学更加牢固，并能够把更方面的知识综合起来运用。· 参考文献1王立柱.C/C+与数据结构.北京：清华大学出版社，20022顾元刚.数据结构简明教程.南京：东南大学出版社等，20033郭福顺，王晓芬，李莲治数据结构（修订本），大连理工大学出版社，19974 美Mark Allen Weiss，数据结构与算法分析C语言描述(英文版第2版)，人民邮电出版社，2005.85 李春葆著，数据结构教程，清华大学出版社，2005.1附录：程序源代码#include<stdio.h>#include<stdlib.h>#define MAXSIZE

47、 100int num100;typedef struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu;OLink *rhead,*chead;CrossList; /十字链表结构体定义 typedef structint i,j;int e;Triple;typedef structTriple dataMAXSIZE; int rposMAXSIZE + 1; int nu,mu,tu;TSMatrix; /三元组结构体定义；int CreateSMatix

48、_OL(CrossList &M) int i,j,e; OLink q; OLink p;printf("请输入稀疏矩阵的行数，列数，非零元素的个数:"); /矩阵行数，列数下标均从开始；scanf("%d%d%d",&M.mu,&M.nu,&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.rh

49、eadi=NULL;/把矩阵每个元素置空值for( i=1;i<=M.nu;i+)M.cheadi=NULL;printf("请输入稀疏矩阵，如果行为，则退出n");scanf("%d%d%d",&i,&j,&e);while(i!=0)p=(OLink)malloc(sizeof(OLNode);p->i=i;p->j=j;p->e=e;if(M.rheadi=NULL|M.rheadi->j>j)p->right=M.rheadi;M.rheadi=p;else q=M.rheadi;

50、 while(q->right&&q->right->j<j)q=q->right; p->right=q->right; q->right=p;if(M.cheadj=NULL|M.cheadj->i>i)p->down=M.cheadj;M.cheadj=p;elseq=M.cheadj;while(q->down&&q->down->i<i)q=q->down;p->down=q->down;q->down=p;scanf("%d%d%d",&i,&j,&e);return 1;/创建十字链表void CreateSMatrix(TSMatrix &M)/采用三元组顺序表存储表示，创建稀疏矩阵M printf("请输入稀疏矩阵的行数、列数和非零元个数：");scanf("%d%d%d",&M.mu,&M.nu,&M.tu);if(M.mu<=0)|(M.nu<=0)|(M.tu<=0)|(M.tu>M.mu*M.nu)/判断行值、列值、元素个数是否合法 printf(&