稀疏矩阵 引用 十字链表 运算

稀疏矩阵应用

摘 要 本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。在程序设计中，考虑到方法的难易程度，采用了先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘操作的方法，再在十字链表下实现。程序通过调试运行，结果与预期一样，初步实现了设计目标。

关键词 程序设计；稀疏矩阵；三元组；十字链表

1 引言

? 课程设计任务

本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C； 求出A的转置矩阵D，输出D； 求两个稀疏矩阵A和B的相乘矩阵E，并输出E。

? 课程设计性质

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

1.3课程设计目的

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

? 需求分析

2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值

本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。首先要定义两种不同的结构体类型，在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值，特别注意在十字链表下，对变量进行动态的地址分配。在设计输出稀疏矩阵的值的函数时，也要针对两种不同的情况，分别编制函数，才能准确的输出稀疏矩阵。在对稀疏矩阵进行初始化及输出值时，均只输出非零元素的值和它所在的所在行及所在列。

2.2构造函数进行稀疏矩阵的转置并输出结果

本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果，由于对稀疏函数的转置只对一个矩阵进行操作，所以实现起来难度不是很大，函数也比较容易编写。在编写函数时，要先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。

2.3构造函数进行两个稀疏矩阵相加及相乘并输出最终的稀疏矩阵

本模块要求设计相加和相乘函数对两个矩阵进行运算，并输出最终的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，看是不是相同类型的矩阵，因为两个矩阵

相加要求两个矩阵一定是同一类型的矩阵，定义相应的矩阵类型用于存放两个矩阵相加相乘后的结果矩阵，这个结果矩阵的行数列数需要综合多方面情况来确定。这四个函数也是整个程序的难点，需要灵活运用数组及指针的特点。

2.4退出系统

本模块要求设置选项能随时结束程序的运行，本程序中采用exit(0)函数。程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。

? 概要设计

3.1主界面设计

为了实现在两种存储结构下对稀疏矩阵的多种算法功能的管理，首先设计一个含有多

个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系

统主控菜单运行界面如图1所示。

图1主界面图

3.2存储结构设计

本系统采用三元组结构和十字链表结构存储稀疏矩阵的具体信息。其中：在三元组中，所有元素的信息用数组表示，每个数组元素中包含有行下标(i)，列下标(j)和对应的数值(e)，它们是整型数据，全部的信息用在十字链表中，全部结点的信息用结构体（TSMatrix）包含，包括用数组（Triple data[MAXSIZE]）和总共的行数（mu）,列数（nu）以及非零元素的个数(tu)。在十字链表下，头结点为指针数组

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

三元组结构体定义:

typedef struct{

int i,j; int e; }Triple;

typedef struct{

Triple data[MAXSIZE];

int rpos[MAXSIZE + 1];

int nu,mu,tu; }TSMatrix;

十字链表结构体定义:

typedef struct OLNode{ int 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 &M)依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。 （1）稀疏矩阵的转置：

此功能在三元组存储结构下，由函数void TransposeSMatrix(TSMatrix M,TSMatrix &T)实现，在十字链表存储结构下，由函数void

TurnSMatrix_OL(CrossList &M)实现。当用户选择该功能，系统提示用户初始化一个矩阵，然后进行转置，最终输出结果。 （2）稀疏矩阵的加法：

此功能在三元组存储结构下，由函数void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S)实现，在十字链表存储结构下，由函数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)实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （4）退出：

即退出稀疏矩阵的应用系统，由exit(0)函数实现。当用户选择该功能，则退出该稀疏矩阵的应用系统。

4 详细设计

4.1 数据类型定义

三元组结构体定义:

typedef struct{ //三元组结构体

int i,j; //行标、列表 int e; //值 }Triple; typedef struct{

Triple data[MAXSIZE]; //三元组表

int rpos[MAXSIZE + 1];

int nu,mu,tu; //行数、列数、非零元个

数

}TSMatrix;

十字链表结构体定义:

typedef struct OLNode{ //结点结构 int i,j; //行标、列标 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(\请你选择创建稀疏矩阵的方法：\\n1：用三元组创建稀疏矩阵\\n2:用十字链表创建稀疏矩阵\\n3:退出程序\printf(\scanf(\switch(n){ case 1:

CreateSMatrix(M); //创建三元组矩阵

printf(\您输入的稀疏矩阵为（只列出非零元素）：\\n 行 列 大小\\n\

ShowTMatrix(M); //显示三元组矩阵

printf(\已经选择三元组创建稀疏矩阵，请选择操作:\\n1：稀疏矩阵转置\\n2：稀疏矩阵相加\\n3：稀疏矩阵相乘\\n4：退出程序\\n\scanf(\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 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); //显示十字链表矩阵

printf(\已经选择十字链表创建稀疏矩阵，请选择操作: 1：

稀疏矩阵转置\\n 2：稀疏矩阵相加\\n 3：稀疏矩阵相乘\\n 4：退出程序\\n\scanf(\

switch(i){ case 1:

TurnSMatrix_OL(MM); //十字链表矩阵转置

printf(\转置后的矩阵为（只列出非零元素）：\\n 行 列 大小\\n\ ShowMAtrix(&MM); break; case 2:

printf(\请你输入另一个稀疏矩阵:\ CreateSMatix_OL(TT);

SMatrix_ADD(&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); }};break; case 3:exit(0); default :printf(\} }

B. 稀疏矩阵操作各子函数的定义：

(1)建立与初始化稀疏矩阵：

void CreateSMatrix(TSMatrix &M){//采用三元组顺序表存储表示，创建稀疏矩阵M

printf(\请输入稀疏矩阵的行数、列数和非零元个数：\scanf(\

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(M.tu>M.mu*M.nu)) //判断行值、列值、元素个数是否合法 printf(\输入有误！\

for(int i=1;i<=M.tu;i++){//输入稀疏矩阵元素

printf(\请输入元素坐标(所在行，所在列）及大小：\ scanf(\ if((M.data[i].i<=0)||(M.data[i].j<=0)){ printf(\输入错误，请重新输入\

scanf(\ } } int num[100]; if(M.tu) {int i;

for(i = 1; i <= M.mu; i++) num[i] = 0;//初始化 for(int t = 1; t <= M.tu; t++) ++num[M.data[t].i];

//求M中每一行含非零元素个数

//求rpos M.rpos[1] = 1;

for(i = 2; i <= M.mu; i++) M.rpos[i] = M.rpos[i-1] + num[i-1]; }

} //创建三元组

int CreateSMatix_OL(CrossList &M){ int i,j,e; OLink q; OLink p;

printf(\请输入稀疏矩阵的行数，列数，非零元素的个数\ //矩阵行数，列数下标均从开始；

scanf(\

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; printf(\请输入稀疏矩阵，如果行为，则退出\\n\scanf(\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->jright; 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->idown; p->down=q->down; q->down=p; }

scanf(\} return 1;

}//创建十字链表

（2）输出稀疏矩阵：

void ShowTMatrix(TSMatrix M){

for(int col=1;col<=M.mu;col++)

//通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显示出来

for(int p=1;p<=M.tu;p++)

if(M.data[p].i==col)printf(\a[p].e);

}//三元组显示

int ShowMAtrix(CrossList *A){ int col; OLink p;

for(col=1;col<=A->mu;col++)if(A->rhead[col]){p=A->rhead[col]; //通过循环，把A结点的rhead[col]赋给p

while(p){printf(\ } 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++)//通过循环，把非零元素的行数与列数进行交换，实现转置 for(int p=1;p<=M.tu;p++) if(M.data[p].j==col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e; q++; }

}//三元组转置

void TurnSMatrix_OL(CrossList &M){ int col,row; //定义循环变量

OLink p,q; //定义OLink结构类型变量

for(col=1;col<=M.mu;col++) //通过循环，把非零元素的行数与列数进行交换，实现转置 { q=p=M.rhead[col]; while(q){ 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; while(mcount<=M.tu&&tcount<=T.tu){

switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data[tcount].j))

//用switch分支语句，用compare函数对需要相加的两个矩阵的某元

素行数列数进行比较

{case -1: S.data[q].e=M.data[mcount].e;//当

M.data[mcount].i

//把第一个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q++; mcount++; break;

case 1: S.data[q].e=T.data[tcount].e;//当M.data[mcount].i>T.data[tcount].i或M.data[mcount].j>T.data[tcount].j S.data[q].i=T.data[tcount].i; S.data[q].j=T.data[tcount].j;

//把第二个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q++; tcount++; break;

case 0: ce=M.data[mcount].e+T.data[tcount].e; //其他情况下把两个矩阵的值相加 if(ce){ S.data[q].e=ce; S.data[q].i=M.data[mcount].i; S.data[q].j=M.data[mcount].j; q++; mcount++; tcount++;}

else {mcount++; tcount++;} break; }}

while(mcount<=M.tu){ S.data[q].e=M.data[mcount].e; S.data[q].i=M.data[mcount].i; S.data[q].j=M.data[mcount].j; q++;

mcount++; }//在case=-1的情况下对S矩阵的非零值，行数，列数进行赋值

while(tcount<=M.tu){

S.data[q].e=T.data[tcount].e; S.data[q].i=T.data[tcount].i; S.data[q].j=T.data[tcount].j; q++; tcount++;

}//在case=1的情况下对S矩阵的非零值，行数，列数进行赋值 S.tu=q-1;

}//三元组相加

int SMatrix_ADD(CrossList *A,CrossList *B){

OLNode *pa,*pb,*pre,*p,*cp[100]; //定义OLNode类型的变量 int i,j,t; t=A->tu+B->tu;

for(j=1;j<=A->nu;j++)cp[j]=A->chead[j];//将A矩阵的列表头指针赋给cp数组

for(i=1;i<=A->mu;i++){ pa=A->rhead[i];

pb=B->rhead[i];//将A，B矩阵的行表头指针分别赋给pa，pb pre=NULL;

while(pb){//当pb不等于零 if(pa==NULL||pa->j>pb->j){

p=(OLink)malloc(sizeof(OLNode));//给p动态分配空间 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;

}//如果A->chead[p->j]不等于零，则把p赋给它及cp[p->j] else{

cp[p->j]->down=p; cp[p->j]=p; }

pb=pb->right;

}//否则把p赋给cp[p->j] else if(pa->jj){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;//A的行与列为A及B当中较大的一个 return 1; }//十字链表相加 （5）实现两个矩阵的相乘：

int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) {

int arow, brow, ccol, i, t, ctemp[100], p, q, tp; //定义相乘函数中所需要用到的变量 if(M.nu != N.mu) return 0;

//如果第一个矩阵的行数不等于第二个矩阵的列数，则退

出

Q.mu = 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) ctemp[i] = 0; Q.rpos[arow] = Q.tu + 1;

if(arow < M.mu) tp = M.rpos[arow + 1];

else tp = M.tu +1;

for(p = M.rpos[arow]; p < tp; ++p)//把每行与每列相乘

{

brow = M.data[p].j; if(brow < N.mu) t = N.rpos[brow+1]; else t = N.tu + 1;

for(q = N.rpos[brow]; q < t; ++q) {

ccol = N.data[q].j;

ctemp[ccol] += M.data[p].e * N.data[q].e;//值相乘

} }

for(ccol = 1; ccol <= Q.nu; ++ccol) //把运算后的结果存放到Q中

{

if(ctemp[ccol]) {

if(++(Q.tu) > MAXSIZE) return 1; Q.data[Q.tu].i = arow, Q.data[Q.tu].j = ccol, Q.data[Q.tu].e = ctemp[ccol]; } } } } 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, 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) //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) //乘积不为零

{

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.rhead[i] == NULL) //若p为该行的第个结点 Q.rhead[i] = pl = p; //p插在该行的表头且pl指向p(该行的最后一个结点)

else pl->right = p, pl = p; //插在pl所指结点之后，pl右移 //列插入

if(Q.chead[j] == NULL) //若p为该列的第一个结点

Q.chead[j] = p; //该列的表头指向p

else {//插在列表尾

pla = Q.chead[j];//pla指向j行的第个结点 while(pla->down) pla = pla->down;//pla指向j行最后一个结点

pla->down = p; } }

} return 1;

}//十字链表相乘

? 调试分析

5.1系统运行主界面

系统运行主界面如图2所示：

图2 主界面图

5.2 各子功能测试运行结果

（1）稀疏矩阵的创建及初始化：

在主菜单下，用户输入1回车，是用三元组创建稀疏矩阵，根据屏幕提示初始化一个稀疏矩阵，按enter键，运行结果如图3所示。

图3 三元组创建并初始化矩阵

? 参考文献

[1] 王立柱.C/C++与数据结构.北京：清华大学出版社，2002 [2] 顾元刚.数据结构简明教程.南京：东南大学出版社等，2003

[3] 郭福顺，王晓芬，李莲治《数据结构》（修订本），大连理工大学出版社，1997 [4] [美]Mark Allen Weiss，数据结构与算法分析——C语言描述(英文版?第2版)，人民邮电出版社，2005.8

[5] 李春葆著，数据结构教程，清华大学出版社，2005.1

附录：程序源代码

#include #include #define MAXSIZE 100 int num[100];

typedef struct OLNode{ int i,j; int e;

struct OLNode *right,*down; }OLNode,*OLink;

typedef struct { int mu,nu,tu;

OLink *rhead,*chead;

}CrossList; //十字链表结构体定义

typedef struct{ int i,j; int e; }Triple;

typedef struct{

Triple data[MAXSIZE];

int rpos[MAXSIZE + 1];

int nu,mu,tu;

}TSMatrix; //三元组结构体定义；

int CreateSMatix_OL(CrossList &M){ int i,j,e; OLink q; OLink p;

printf(\请输入稀疏矩阵的行数，列数，非零元素的个数:\ //矩阵行数，列数下标均从开始；

scanf(\

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;

printf(\请输入稀疏矩阵，如果行为，则退出\\n\scanf(\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->jright; 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->idown; p->down=q->down; q->down=p; }

scanf(\}

return 1;

}//创建十字链表

void CreateSMatrix(TSMatrix &M){

//采用三元组顺序表存储表示，创建稀疏矩阵M

printf(\请输入稀疏矩阵的行数、列数和非零元个数：\

scanf(\

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(M.tu>M.mu*M.nu)) //判断行值、列值、元素个数是否合法 printf(\输入有误！\

for(int i=1;i<=M.tu;i++){//输入稀疏矩阵元素

printf(\请输入元素坐标(所在行，所在列）及大小：\ scanf(\ if((M.data[i].i<=0)||(M.data[i].j<=0)){ printf(\输入错误，请重新输入\

scanf(\ }//if }//for i

int num[100]; if(M.tu)

{int i;

for(i = 1; i <= M.mu; i++) num[i] = 0;//初始化

for(int t = 1; t <= M.tu; t++) ++num[M.data[t].i];//求M中每一行含非零元素个数

//求rpos

M.rpos[1] = 1;

for(i = 2; i <= M.mu; i++) M.rpos[i] = M.rpos[i-1] + num[i-1]; }

}//创建三元组

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++)//通过循环，把非零元素的行数与列数进行交换，实现转置

for(int p=1;p<=M.tu;p++) if(M.data[p].j==col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; q++; }

}//三元组转置

int Compare(int a1,int b1,int a2,int b2){ if(a1>a2)return 1;

else if(a1b2)return 1; if(b1

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;

while(mcount<=M.tu&&tcount<=T.tu){

switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data[tcount].j)) //用switch分支语句，用compare函数对需要相加的两个矩阵的某元素行数列数进行比较

{case -1: S.data[q].e=M.data[mcount].e;//当M.data[mcount].i

S.data[q].j=M.data[mcount].j;//把第一个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q++;

mcount++; break;

case 1: S.data[q].e=T.data[tcount].e;//当M.data[mcount].i>T.data[tcount].i或M.data[mcount].j>T.data[tcount].j S.data[q].i=T.data[tcount].i;

S.data[q].j=T.data[tcount].j;//把第二个矩阵的行数i，列数j赋值给S矩阵的行数i，列数j q++;

tcount++; break;

case 0: ce=M.data[mcount].e+T.data[tcount].e;//其他情况下把两个矩阵的值相加 if(ce){ S.data[q].e=ce; S.data[q].i=M.data[mcount].i; S.data[q].j=M.data[mcount].j; q++;

mcount++; tcount++;}

else {mcount++; tcount++;} break; }}

while(mcount<=M.tu){

S.data[q].e=M.data[mcount].e; S.data[q].i=M.data[mcount].i; S.data[q].j=M.data[mcount].j; q++;

mcount++; }//在case=-1的情况下对S矩阵的非零值，行数，列数进行赋值 while(tcount<=M.tu){

S.data[q].e=T.data[tcount].e; S.data[q].i=T.data[tcount].i; S.data[q].j=T.data[tcount].j; q++; tcount++;

}//在case=1的情况下对S矩阵的非零值，行数，列数进行赋值 S.tu=q-1; }//三元组相加

int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) {

int arow, brow, ccol, i, t, ctemp[100], p, q, tp;//定义相乘函数中所需要用到的变量

if(M.nu != N.mu) return 0;//如果第一个矩阵的行数不等于第二个矩阵的列数，则退出

Q.mu = 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) ctemp[i] = 0; Q.rpos[arow] = Q.tu + 1;

if(arow < M.mu) tp = M.rpos[arow + 1]; else tp = M.tu +1;

for(p = M.rpos[arow]; p < tp; ++p)//把每行与每列相乘 {

brow = M.data[p].j;

if(brow < N.mu) t = N.rpos[brow+1]; else t = N.tu + 1;

for(q = N.rpos[brow]; q < t; ++q) {

ccol = N.data[q].j;

ctemp[ccol] += M.data[p].e * N.data[q].e;//值相乘 } }

for(ccol = 1; ccol <= Q.nu; ++ccol) //把运算后的结果存放到Q中 {

if(ctemp[ccol]) {

if(++(Q.tu) > MAXSIZE) return 1;

Q.data[Q.tu].i = arow, Q.data[Q.tu].j = ccol, Q.data[Q.tu].e = ctemp[ccol]; } } } }

return 1; }//三元组相乘

void ShowTMatrix(TSMatrix M){

for(int col=1;col<=M.mu;col++)//通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显示出来

for(int p=1;p<=M.tu;p++)

if(M.data[p].i==col)printf(\}//三元组显示

void TurnSMatrix_OL(CrossList &M){ int col,row; //定义循环变量

OLink p,q; //定义OLink结构类型变量

for(col=1;col<=M.mu;col++) //通过循环，把非零元素的行数与列数进行交换，实现转置

{ q=p=M.rhead[col]; while(q){ row=p->i; p->i=p->j; p->j=row; q=p->right;

p->right=p->down; p->down=q; } }

}//十字链表转置

int SMatrix_ADD(CrossList *A,CrossList *B){

OLNode *pa,*pb,*pre,*p,*cp[100]; //定义OLNode类型的变量 int i,j,t;

t=A->tu+B->tu;

for(j=1;j<=A->nu;j++)cp[j]=A->chead[j];//将A矩阵的列表头指针赋给cp数组 for(i=1;i<=A->mu;i++){ pa=A->rhead[i];

pb=B->rhead[i];//将A，B矩阵的行表头指针分别赋给pa，pb pre=NULL;

while(pb){//当pb不等于零

if(pa==NULL||pa->j>pb->j){

p=(OLink)malloc(sizeof(OLNode));//给p动态分配空间 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;

}//如果A->chead[p->j]不等于零，则把p赋给它及cp[p->j] else{

cp[p->j]->down=p; cp[p->j]=p; }

pb=pb->right;

}//否则把p赋给cp[p->j] else if(pa->jj){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;//A的行与列为A及B当中较大的一个

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, 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) //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) //乘积不为 {

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.rhead[i] == NULL) //若p为该行的第个结点

Q.rhead[i] = pl = p; //p插在该行的表头且pl指向p(该行的最后一个结点)

else pl->right = p, pl = p; //插在pl所指结点之后，pl右移

//列插入

if(Q.chead[j] == NULL) //若p为该列的第一个结点

Q.chead[j] = p; //该列的表头指向p

else {//插在列表尾

pla = Q.chead[j];//pla指向j行的第个结点

while(pla->down) pla = pla->down;//pla指向j行最后一个结点

pla->down = p; } } } return 1; }//十字链表相乘

int ShowMAtrix(CrossList *A){ int col;

OLink p;

for(col=1;col<=A->mu;col++)if(A->rhead[col]){p=A->rhead[col]; while(p){printf(\ }

return 1;

}//十字链表显示

void main(){ int n,i; char b;

TSMatrix M,T,S;

CrossList MM,TT,SS;

printf(\ ***稀疏矩阵应用***\

printf(\请你选择创建稀疏矩阵的方法：\\n1：用三元组创建稀疏矩阵\\n2:用十字链表创建稀疏矩阵\\n3:退出程序\printf(\scanf(\switch(n){ case 1:

CreateSMatrix(M);

printf(\您输入的稀疏矩阵为（只列出非零元素）：\\n 行 列 大小\\n\ShowTMatrix(M);

printf(\已经选择三元组创建稀疏矩阵，请选择操作:\\n1：稀疏矩阵转置\\n2：稀疏矩阵相加\\n3：稀疏矩阵相乘\\n4：退出程序\\n\scanf(\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 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); printf(\已经选择十字链表创建稀疏矩阵，请选择操作:\\n1：稀疏矩阵转置\\n2：稀疏矩阵相加\\n3：稀疏矩阵相乘\\n4：退出程序\\n\scanf(\switch(i){ case 1:

TurnSMatrix_OL(MM);

printf(\转置后的矩阵为（只列出非零元素）：\\n 行 列大小\\n\ ShowMAtrix(&MM); break;

case 2:

printf(\请你输入另一个稀疏矩阵:\ CreateSMatix_OL(TT);

SMatrix_ADD(&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);

}};break; case 3:exit(0);

default :printf(\} }

本文来源：https://www.bwwdw.com/article/l3jt.html