采用十字链表表示稀疏矩阵,并实现矩阵的加法运算

数据结构实验报告三稀疏矩阵的运算实验课程名称数据结构课程设计专业班级学⽣姓名学号指导教师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;}五：运⾏与测试进⾏数据测试六：总结与⼼得⼗字链表作为存储结构表⽰随机稀疏矩阵，进⾏两矩阵的相加运算，所以⾸先要定义⼀个⼗字链表作为存储结构。

#include<stdio.h>#include<malloc.h>#define Size 2501# define Size1 51typedef struct{int i;int j;int e;//非零元的值}triple; //定义三元组typedef struct{triple data[Size+1];//矩阵中的元素int rops[Size1+1];// rops[i]为第i行元素中的首非零元在data[]中的序号int mu;//行数int nu;//列数int tu;//非零元数} juzhen;//定义矩阵typedef struct node// 定义十字链表元素{int i,j,e;struct node *right,*down;// 该非零元所在行表和列表的后继元素}node,*link;typedef struct // 定义十字链表对象结构体{link *rhead,*chead;//行和列的头指针int m,n,t;// 系数矩阵的行数，列数，和非零元素个数}crosslist;void createcross(crosslist &M)//建立十字链表{int i,j,e,k;node *p,*q;printf("输入行，列和非零元数，空格隔开：\n");scanf("%d %d %d",&M.m,&M.n,&M.t);M.rhead=(link *)malloc((M.m+1)*sizeof(link));//给行和列的头指针分配内存M.chead=(link *)malloc((M.n+1)*sizeof(link));for(k=1;k<=M.m;k++)//初始化行，列的头指针M.rhead[k]=NULL;for(k=1;k<=M.n;k++)M.chead[k]=NULL;printf("输入非零元的行，列和值，空格隔开：\n");for(k=1;k<=M.t;k++)//输入非零元{scanf("%d %d %d",&i,&j,&e);p=(node *)malloc(sizeof(node));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{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->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;}}}void printcross(crosslist A)//输出十字链表{if(A.m==0)printf("十字链表为空!\n");else{printf("十字链表为:\n");int i,j;for(i=1;i<=A.m;i++){link p=A.rhead[i];for(j=1;j<=A.n;j++){if((p)&&(j==p->j)){printf("%5d",p->e);p=p->right; }elseprintf("%5d",0);}printf("\n");}}printf("\n");}crosslist addcross(){printf("十字链表加法:\n");crosslist a,b;// 创建两个十字链表对象，并初始化createcross(a);createcross(b);node *pre,*h[51],*pa,*pb,*q;//定义辅助指针，pa，pb分别为a,b当前比较的元素，pre为pa的前驱元素int i,j,k=0,m,n; //h[j]指向j列的当前插入位置if(a.m!=b.m||a.n!=b.n)printf("格式不对，不能相加!\n");else{for(i=1;i<=a.m;i++){pa=a.rhead[i];pb=b.rhead[i];pre=NULL;for(j=1;j<=a.n;j++)h[j]=NULL;while(pb){p=(node *)malloc(sizeof(node)); // 开辟新节点，存储b中取出的元素p->i=pb->i;p->j=pb->j;p->e=pb->e;if(pa==NULL||pa->j>pb->j)//当a此行已经检查完或者pb因该放在pa前面{if (pre==NULL)a. rhead[p->i]=p;elsepre->right=p;p->right=pa;pre=p;if (h[p->j]==NULL)//当前插入位置下面无非零元//因为是逐行处理，so,h[p->j]，依次下移//因此每次都是指向插入的位置{a. chead [p->j]= p;p->down = NULL;}else{p->down = h[p->j]->down;h[p->j]->down = p;}h[p->j]=p;//*******h[p->j]下移指向下次插入的位置pb=pb->right;//pb指向该行下个元素}else if((pa&&pa->j<pb->j))//只要移动pa的指针****先不加||(pb==NULL&&pa){pre = pa;h[pa->j]=pa;//移动h[]，使其指向下次插入的位置pa = pa->right;}else if(pa->j==pb->j){pa->e+=pb->e;if(pa->e)//不为零{pre=pa;h[pa->j]=pa;pb=pb->right;//加else//pa->e为零，删除节点{if (pre ==NULL)a.rhead [pa->i]=pa->right;else{pre->right=pa->right;}p=pa;//p指向pa，用来在下面修改列指针pa=pa->right;if (h [p->j]==NULL)a.chead [p->j]=p->down;else{h[p->j]->down=p->down;}free(p);pb=pb->right;}}}}}return a;}void multycross(crosslist &c)//十字链表乘法{node *p,*q,*u,*v,*p1,*p2;crosslist a,b;link *r;int i,j,k,e;printf("十字链表乘法:\n");createcross(a);createcross(b);if(a.n!=b.m)printf("格式错误，不能相乘！\n");else{c.m=a.m;c.n=b.n;c.t=0;c.rhead=(link *)malloc((a.m+1)*sizeof(link));//给行和列的头指针分配内存c.chead=(link *)malloc((b.n+1)*sizeof(link));for(k=1;k<=a.m;k++)//初始化行，列的头指针c.rhead[k]=NULL;for(k=1;k<=b.n;k++)c.chead[k]=NULL;r=(link *)malloc((b.n+1)*sizeof(link));for(i=1;i<=a.m;i++){u=(node *)malloc(sizeof(node));u->e=0;u->i=0;u->j=0;for(k=1;k<=b.n;k++)//初始化r[]r[k]=u;p1=p=a.rhead[i];for(j=1;j<=b.n;j++){p=p1;q=b.chead[j];v=(node *)malloc(sizeof(node));//初始化v，v为将插入c矩阵的元素v->e=0;v->i=i;v->j=j;while(p&&q){if(p->j>q->i)q=q->down;else if(p->j<q->i)p=p->right;else{v->e+=p->e*q->e;p=p->right;q=q->down;}}if(v->e)//如果不为零，则插入c矩阵中{//同建立十字链表if(c.rhead[i]==NULL||c.rhead[i]->j>j)//插入元素所在行无非零元或首非零元的列标大于插入元素的列标{v->right=c.rhead[i];c.rhead[i]=v;}else{for(p2=c.rhead[i];(p2->right)&&(p2->right->j<j);p2=p2->right);//空循环找到第一个列标大于或等于插入元素列标的元素v->right=p2->right;p2->right=v;}if(c.chead[j]==NULL||c.chead[j]->i>i)//插入元素所在列无非零元或首非零元的行标大于插入元素的行标{v->down=c.chead[j];c.chead[j]=v;}else{for(p2=c.chead[j];(p2->down)&&(p2->down->i<i);p2=p2->down);//空循环找到第一个行标大于或等于插入元素行标的元素v->down=p2->down;p2->down=v;}}}}}}void create(juzhen & M) //创建稀疏矩阵{int i,t=0;printf("输入矩阵行数和列数and非零元的个数，以空格隔开:\n");scanf("%d %d %d",&M.mu,&M.nu,&M.tu);printf("输入矩阵非零元的行，列，和数值(中间空格隔开):\n");for(i=1;i<=M.tu;i++)scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e); //输入三元组的元素for(i=1;i<=Size1;i++)//初始化rops【】M.rops[i]=0;for(i=1,t=1;i<=M.mu;i++)//得到各行第一个元素的序号{M.rops[i]=t;while(M.data[t].i<=i&&t<=M.tu)//遇到i行非零元，则t累加t++;}}void add(juzhen A,juzhen B,juzhen & C)//稀疏矩阵加法{int k=1,temp=0,k1=1, k2=1;//k1,k2,k分别控制A，B，C中非零元的序号变化printf("稀疏矩阵加法:\n");create(A);create(B);if(A.mu!=B.mu||A.nu!=B.nu)printf("格式不对，不能相加!\n");else{while(k1<=A.tu&&k2<=B.tu)//当A，B中的非零元都没用完{if(A.data[k1].i<B.data[k2].i)//A当前k1指向的元素的行标小于列标直接把data 【k1】的值赋给c中data【k】C.data[k++]=A.data[k1++];else if(A.data[k1].i>B.data[k2].i)//同上C.data[k++]=B.data[k2++];else//data[k1],data[k2]行标相同{if(A.data[k1].j>B.data[k2].j)//data[k1]列标大于data[k2]列标，则把data[k2]的值赋给data[k]C.data[k++]=B.data[k2++];else if(A.data[k1].j<B.data[k2].j)//同上C.data[k++]=A.data[k1++];else //行，列标都相同{temp=0;temp=A.data[k1].e+B.data[k2].e;if(temp)//相加后不为零{C.data[k].i=A.data[k1].i;C.data[k].j=A.data[k1].j;C.data[k].e=temp;k++;}k1++;k2++;}}}while(k1<=A.tu)//B中非零元已用完，A中还有非零元C.data[k++]=A.data[k1++];while(k2<=B.tu)//A中非零元已用完，B中还有非零元C.data[k++]=B.data[k2++];C.mu=A.mu;//确定C的行列数和非零元个数C.nu=A.nu;C.tu=k-1;}}void print(juzhen A)//输出稀疏矩阵{printf("\n矩阵为:\n");int i,j,k=1;if(A.mu==0)printf("矩阵为空！\n");else if(A.tu==0)//矩阵元素为空printf("零矩阵！\n");elsefor(i=1;i<=A.mu;i++)//逐行输出{for(j=1;j<=A.nu;j++){if(A.data[k].i==i&&A.data[k].j==j)//行和列分别对应相等则输出相应非零元，否则输出零printf("%5d",A.data[k++].e);elseprintf("%5d",0);}printf("\n");//该行输出结束，空行输出下一行}printf("\n");}void multy(juzhen A,juzhen B,juzhen &C)//稀疏矩阵乘法{int arow,brow,ccol,temp[51],p,q,t,tp,i;//各变量代表含义见下面printf("稀疏矩阵乘法:\n");create(A);create(B);if(A.nu!=B.mu)printf("格式错误，不能相乘！\n");else{C.mu=A.mu;//初始化c的行列及非零元个数C.nu=B.nu;C.tu=0;if(A.nu!=B.mu)printf("A,B格式不对不能相乘!\n");else //{for(arow=1;arow<=A.mu;arow++)//arow为当前A矩阵的行标{for(i=0;i<51;i++)//初始化temptemp[i]=0;if(arow<A.mu)tp=A.rops[arow+1];//tp为arow+1行的首非零元在data【】中的序号else //arow为最后一行tp=A.tu+1;for(p=A.rops[arow];p<tp;p++)//p为A中当前元素在data[]中的序号{brow=A.data[p].j;//brow为与B矩阵中的相应行对应的A中当前元素的列标if(brow<B.mu)t=B.rops[brow+1];//t为brow+1行的首非零元在B中data【】中的序号else //brow大小等于B.mut=B.tu+1;for(q=B.rops[brow];q<t;q++)//q为B中当前元素在B.data[]中的序号{ccol=B.data[q].j;//ccol：data[p]*data[q]所得结果所在的列temp[ccol]+=A.data[p].e*B.data[q].e;//temp【ccol】：相乘所得的C 矩阵中第arow行cool列元素的值}}for(ccol=1;ccol<=B.nu;ccol++)//if(temp[ccol])//temp【ccol】不为零，则把值赋到c中，c.tu加1。

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

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

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

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

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

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

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

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

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

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

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

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

数 据 结 构课 程 设 计 报 告日期: 年 月 日122009 30 学 号班 级卫熙 姓 名指 导 教 师 王 平2007级信息与计算科学 20070744044 题目：基于正交链表的矩阵运算说明本组成员名单：卫熙谢武杰孙洋洋王帅吴波组长：卫熙本人承担的课程设计的工作情况：程序的算法设计以及部分功能实现，后期程序调试、测试，主函数的设计。

目录1 任务概述 (3)1.1 问题描述 (3)1.2 编程的基本要求 (3)1.3 程序的主要功能 (3)1.4 编程语言及选择的操作平台 (3)2 概要设计 (4)2.1 数据结构 (4)2.2 总体结构 (4)3 详细设计 (5)3.1 数据结构中的函数 (6)3.2 主函数及其他函数 (7)4 调试分析 (9)4.1调试过程 (9)4.2测试结果 (9)4.2改进设想 (14)5 用户手册 (15)6 总结 (17)参考文献 (18)附件源程序代码清单 (19)1 任务概述1.1 问题描述应用三元组和正交链表存储稀疏矩阵，并实现稀疏矩阵的转置、加法和乘法运算。

1.2 编程的基本要求1）应用三元组和正交链表的数据结构。

2）矩阵运算由正交链表类的成员函数实现，矩阵的输入输出由类的友元重载函数实现。

3）主函数用于实现菜单和调用。

1.3 程序的主要功能1. 按《数据结构课程设计》报告格式所给出的框架撰写。

2. 具体内容应尽量包含文字叙述、图表（表格，框图，流程图，UML图等）和程序代码。

3. 每个同学要提交电子文档和一份打印稿。

1.4 编程语言及选择的操作平台编程语言选用C++程序设计语言。

程序开发平台选用Mcrosoft Visual Studio 6.0的Microsoft Visual C++ 6.0开发环境。

程序运行在DOS界面。

2 概要设计2.1 数据结构稀疏矩阵类（matrix）稀疏矩阵的节点类（node）2.2总体结构说明：表达式i!=0 True,向下执行，False 结束退出3 详细设计3.1 数据结构中的函数（其中函数的实现请参看源代码部分）1) 矩阵结点（matrix）中的函数：Private:friend istream&operator>>(istream&,matrix&);friend ostream&operator<<(ostream&,matrix&);//int Row,Col,Terms,temp; //矩阵的总行数，总列数，和非零元素个数和临时变量；//node*headnode; //稀疏矩阵的总表头public:matrix(int m,int n); //重载构造函数matrix(); //对矩阵进行构造matrix(matrix& T); //拷贝构造函数~matrix(){makeEmpty();} //析构函数void Init(int m,int n); //初始化函数，又来初始化无参构造函数构造的矩阵void makeEmpty(); //清空矩阵void Insert(int m,int n,float p); //插入矩阵元素void Delete(int m,int n); //删除特定行列元素node *Locate(int i); //定位附加头结点matrix transpose(); //矩阵的转置运算matrix Add( matrix b); //两个矩阵相加matrix Mul(matrix b); //两个矩阵相乘matrix &operator=(matrix &T); //重载赋值号2）节点类（node）的函数：node():head(TRUE){ right=down=this;} //建立附加头结点node(element *t){// 建立非零元素结点triple.col=t->col; triple.row=t->row; triple.item=t->item; right=down=this; head=FALSE;}3.2 主函数及其他函数#include"matrix.h"#include<conio.h>void main(){int i;matrix B,B1,B2,C;while(i!=0){cout<<" ----------------基于正交链表的稀疏矩阵的运算-----------------"<<endl<<endl;cout<<" 1.转置 2.加法 3.乘法0.退出程序"<<endl<<endl;cout<<"请选择:";cin>>i; cout<<endl;switch(i){case 0: break;case 1: cout<<" -------稀疏矩阵的转置------\n"<<endl;cout<<"请输入矩阵："<<endl<<endl;cin>>B;system("cls");cout<<"原矩阵为："<<endl;cout<<B<<endl;cout<<"转置后为"<<endl;cout<<B.transpose()<<endl; break;case 2: cout<<" --------稀疏矩阵的加法-------\n"<<endl;cout<<"请输入矩阵1："<<endl<<endl;cin>>B1;cout<<"请输入矩阵2："<<endl<<endl;cin>>B2;system("cls");cout<<"矩阵1为："<<endl;cout<<B1<<endl;cout<<"矩阵2为："<<endl;cout<<B2<<endl;cout<<"两个矩阵之和为："<<endl;cout<<B1.Add(B2)<<endl;break;case 3: cout<<" --------稀疏矩阵的乘法-------\n"<<endl;cout<<"注意：输入的矩阵必须满足矩阵相乘的条件，并且按顺序输入(即1和2的顺序)\n"<<endl;cout<<"请输入矩阵1："<<endl;cin>>B1;cout<<"请输入矩阵2："<<endl;cin>>B2;system("cls");cout<<"矩阵1为:"<<endl;cout<<B1<<endl;cout<<"矩阵2为:"<<endl;cout<<B2<<endl;cout<<"两个矩阵之积为："<<endl;cout<<B1.Mul(B2)<<endl;break;default:break;}if(i!=0){cout<<"按任意继续......"<<endl; getch();system("cls");}}}//YEAH!!!!终于于31日9:19调试成功了!!!4.1 调试过程再调试过程中，出现最多的问题是控制循环的终止条件，由于指针用的比较多，导致有时用指针做循环终止条件时没有考虑到其值的改变。

十字链表法存储稀疏矩阵稀疏矩阵是指其中大部分元素为0的矩阵。

在实际应用中，稀疏矩阵的存储和计算都会带来一定的困扰。

为了高效地存储和处理稀疏矩阵，我们可以使用十字链表法。

一、稀疏矩阵的特点稀疏矩阵的特点是其中绝大部分元素为0，而只有少部分非零元素。

这导致稀疏矩阵的存储空间浪费很大，因此需要采取一种有效的存储方式。

二、十字链表法的原理十字链表法是一种组合了链表和线性表的数据结构，用于存储稀疏矩阵。

具体实现如下：1. 定义两个链表headRow和headCol，分别用于存储行和列的头节点；2. 每个非零元素都对应一个结点，结点包含四个属性：行号row、列号col、值value以及指向下一个非零元素的指针nextRow和nextCol；3. headRow链表中的每个节点都指向同一行中的第一个非零元素，而headCol链表中的每个节点都指向同一列中的第一个非零元素；4. 非零元素之间通过nextRow和nextCol指针连接。

通过这种方式，我们可以高效地存储稀疏矩阵，并可以方便地进行矩阵的各种操作。

三、十字链表法的优势相比于其他存储稀疏矩阵的方法，十字链表法有以下几个优势：1. 空间利用率高：相比于使用二维数组存储，十字链表法可以大大减少存储空间的浪费，因为只存储非零元素及其位置信息；2. 支持高效的插入和删除操作：十字链表法可以通过调整指针的指向来进行插入和删除操作，而不需要像其他方法那样移动元素；3. 方便进行矩阵操作：通过十字链表法，我们可以方便地进行稀疏矩阵的各种操作，如矩阵相加、矩阵相乘等。

四、十字链表法的应用十字链表法广泛地应用于各个领域，特别是在图论和网络分析中。

在这些领域中，往往需要处理大规模的稀疏矩阵，而十字链表法能够有效地解决这个问题。

以社交网络为例，社交网络中的用户和用户之间往往存在着复杂的关系。

通过将社交网络建模成稀疏矩阵，可以使用十字链表法来存储和处理这些关系。

这样可以方便地进行各种网络分析操作，如查找某个用户的好友、计算两个用户之间的距离等。

数据结构十字链表数据结构是计算机科学中非常重要的一个概念，它指的是各种不同的数据元素之间的关系，以及这些关系的操作和处理方式。

而在数据结构中，十字链表是一种常用的数据结构之一。

它是用于表示稀疏矩阵的一种链表存储结构，通过它可以高效地存储和操作稀疏矩阵。

本文将详细介绍十字链表的概念、特点以及应用。

一、十字链表的定义和特点十字链表是一种多重链表，它由两个链表组成：行链表和列链表。

行链表按照行的顺序连接各个非零元素，列链表按照列的顺序连接各个非零元素。

每个非零元素节点除了包含自身的数值外，还包含了它在行链表和列链表中的前后指针。

这样，通过行链表和列链表的组织，我们可以快速地找到某个元素的上一个元素和下一个元素。

相比于其他存储稀疏矩阵的方法，十字链表具有以下几个特点：1. 空间利用率高：十字链表只存储非零元素，对于稀疏矩阵而言，节省了大量的存储空间。

而且，十字链表的存储结构相对简单，不会浪费额外的空间。

2. 查找效率高：通过行链表和列链表的组织，我们可以快速地找到某个元素的上一个元素和下一个元素，从而提高了查找的效率。

而且，十字链表还可以支持按行或按列的遍历，方便进行各种操作。

3. 插入和删除效率高：十字链表的插入和删除操作只需要修改相应节点的指针，不需要移动其他节点，因此效率较高。

4. 支持稀疏矩阵的各种操作：十字链表不仅仅可以用于存储稀疏矩阵，还可以支持各种基本操作，如矩阵相加、相乘、转置等。

这是因为十字链表可以方便地找到某个元素的上一个元素和下一个元素，从而实现对稀疏矩阵的灵活操作。

二、十字链表的应用十字链表作为一种存储稀疏矩阵的数据结构，被广泛应用于各种领域。

下面列举了一些常见的应用场景：1. 图的存储：图是一种非常常见的数据结构，而且在很多实际问题中都需要使用图进行建模和分析。

十字链表可以用于存储和操作图的邻接矩阵，从而实现图的各种操作，如遍历、查找、删除等。

2. 网络拓扑分析：在计算机网络中，网络拓扑分析是一项重要的任务。

408考稀疏矩阵十字链表稀疏矩阵是指大部分元素为零的矩阵。

在很多实际应用中，如图像处理、网络分析等领域，大型矩阵中的非零元素只占很小一部分。

为了节省存储空间和提高运算效率，我们可以使用稀疏矩阵来表示这些矩阵。

408考稀疏矩阵十字链表是一种常用的稀疏矩阵存储结构。

它通过将非零元素按行和列分别排列，并使用链表将它们连接在一起，从而实现对稀疏矩阵的高效存储和操作。

在408考中，稀疏矩阵十字链表是一种常用的数据结构，用于表示稀疏矩阵。

它是由徐仲恺老师于1971年提出的，是一种改进的稀疏矩阵链表存储结构。

相比于其他存储结构，稀疏矩阵十字链表具有存储空间小、插入和删除元素方便等优点。

稀疏矩阵十字链表的基本思想是将矩阵分解为行链表和列链表两部分，通过链表将非零元素连接起来。

具体来说，稀疏矩阵十字链表包含三个链表：行链表、列链表和非零元素链表。

行链表是由一组头指针组成的链表，每个头指针指向一行的第一个非零元素。

列链表是由一组头指针组成的链表，每个头指针指向一列的第一个非零元素。

非零元素链表则是将矩阵中的非零元素按照行优先的顺序连接起来。

通过这种方式，我们可以通过行链表和列链表快速找到某一行或某一列的非零元素，并可以在常数时间内插入和删除元素。

同时，由于非零元素链表是按照行优先的顺序连接的，因此可以按照矩阵的行优先顺序遍历非零元素。

使用稀疏矩阵十字链表存储稀疏矩阵可以大大减少存储空间的占用。

对于一个m×n的矩阵，如果非零元素的个数为k，那么稀疏矩阵十字链表的存储空间复杂度为O(k+max(m,n))。

相比之下，使用普通的二维数组存储矩阵需要O(m×n)的存储空间。

稀疏矩阵十字链表还可以实现矩阵的加法、减法和乘法等基本运算。

在进行运算时，我们只需要遍历非零元素链表，并根据链表中的信息进行相应的计算，而无需考虑矩阵中的零元素，从而提高了运算效率。

408考稀疏矩阵十字链表是一种高效的稀疏矩阵存储结构。

数据结构课程设计十字链表xx学院一、问题的分析和任务定义：该设计是采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。

还要检查有关运算的条件，并对错误的条件产生报警。

根据对该程序任务的理解，对本程序分别从以下几个方面进行分析： 1．输入数据的的类型和输入的范围该程序首先输入稀疏矩阵的行数和列数，再输入一个有非零元素的行号，有非零元素的列号，再输入非零元素的值，然后输入当前行下一个元素所在的列，如果该行只有一个非零元素就直接输入-1结束当前行的一组数据，如果还有其他的非零元素的话就输入当前行下一个非零元素所在的列，就这样，直到该当前行的非零元素输入完。

然后再输入当前列下一个非零元素的所在的行，其步骤与前一步相同。

其输入值都为稀疏矩阵的数据，类型都为整型。

2．输出数据的形式这样得到一个稀疏矩阵a,以同样的方法就可以得到另一个稀疏矩阵b,最后就可以得到稀疏矩阵a和稀疏矩阵b的和矩阵.输出是以稀疏矩阵的标准形式输出的。

输出值的有两种：一种是字符，一种是整数。

输出的字符型数据是稀疏矩阵的代号，输出的整型数据为稀疏矩阵的值。

3．测试数据测试数据一：测试数据二：稀疏矩阵的行数与列数：3 3 稀疏矩阵的行数与列数：3 3 矩阵a：矩阵b：矩阵a：矩阵b： 2 0 0 0 0 2 2 0 0 0 0 00 0 6 3 0 0 0 0 0 0 0 07 0 0 2 0 5 0 0 0 7 0 0二、概要设计和数据结构的选择：1．算法（程序）中用到的所有各种数据类型的定义：定义整型数据为int m,int n，分别代表矩阵的行和列；定义十字链表类型结点OLnode *h,*p分别代表为头结点开辟空间和指向下一结点；在主函数中定义OLnode *a,*b，分别表示a,b两个稀疏矩阵。

2．各程序模块之间的层次关系：程序中用到的函数：1 OLnode *create(int m,int n); 创建以十字链表表示的一个元素全为零的稀疏矩阵。

稀疏矩阵十字链表算法稀疏矩阵是指矩阵中绝大多数元素为0的矩阵。

在实际应用中，很多矩阵都具有稀疏性，即元素中大部分为0，而只有少数非零元素。

对于这种类型的矩阵，为了节省内存空间并提高计算效率，可以采用稀疏矩阵的存储方式。

稀疏矩阵的一种常用存储方式是十字链表。

十字链表是一种将稀疏矩阵以链表形式存储的数据结构，它能够有效地表示稀疏矩阵的非零元素，并且能够方便地进行插入、删除和查找操作。

稀疏矩阵十字链表的基本思想是将矩阵中的每个非零元素存储为一个结点，并将这些结点以行列坐标的方式进行链接。

具体来说，稀疏矩阵十字链表由两个链表组成：行链表和列链表。

行链表是一个以行为主的链表，每个结点表示矩阵中的一行。

每个结点包含三个字段：行号、列号和值。

行链表中的结点按照行号从小到大的顺序进行排列，同一行中的结点按照列号从小到大的顺序进行排列。

列链表是一个以列为主的链表，每个结点表示矩阵中的一列。

每个结点也包含三个字段：行号、列号和值。

列链表中的结点按照列号从小到大的顺序进行排列，同一列中的结点按照行号从小到大的顺序进行排列。

通过行链表和列链表，可以方便地进行插入、删除和查找操作。

插入操作可以通过在行链表和列链表中找到对应的位置，将新结点插入到相应的位置上。

删除操作可以通过在行链表和列链表中找到对应的位置，将对应的结点删除。

查找操作可以通过在行链表和列链表中找到对应的位置，获取对应的结点。

稀疏矩阵十字链表算法的优点是能够有效地存储稀疏矩阵，并且可以方便地进行插入、删除和查找操作。

相比于其他存储方式，稀疏矩阵十字链表可以节省更多的内存空间，并且具有更高的计算效率。

总结来说，稀疏矩阵十字链表算法是一种有效地存储稀疏矩阵的方法。

通过行链表和列链表的链接，可以方便地进行插入、删除和查找操作。

稀疏矩阵十字链表算法在实际应用中具有广泛的应用，能够节省内存空间并提高计算效率。

稀疏矩阵十字链表算法稀疏矩阵是指矩阵中大部分元素为0的矩阵。

在实际应用中，稀疏矩阵常常出现，比如图像处理、网络分析等领域。

由于稀疏矩阵中存在大量的0元素，传统的二维数组存储方式会造成内存空间的浪费，因此需要一种高效的数据结构来表示和存储稀疏矩阵。

稀疏矩阵十字链表算法就是一种解决这个问题的方法。

稀疏矩阵十字链表算法是一种基于链表的数据结构，用于表示和存储稀疏矩阵。

它通过两个链表来分别表示行和列，同时还使用了一个数据链表来存储非零元素的值和位置信息。

这种算法的核心思想是将稀疏矩阵的非零元素存储在链表中，并记录它们在矩阵中的位置信息，从而节省了存储空间。

具体来说，稀疏矩阵十字链表算法中，我们可以使用三个结构体来表示矩阵的行、列和非零元素。

其中，行和列的结构体包含了指向非零元素的指针和矩阵的维度信息。

非零元素的结构体包含了元素的值、行列坐标以及指向下一个非零元素的指针。

使用稀疏矩阵十字链表算法存储稀疏矩阵的好处是，它不仅节省了存储空间，还可以提高对稀疏矩阵的操作效率。

比如，对于稀疏矩阵的遍历操作，我们可以通过遍历链表的方式来实现，而不需要遍历整个矩阵，从而减少了时间复杂度。

除了存储和遍历操作，稀疏矩阵十字链表算法还可以支持其他一些常见的矩阵操作，比如矩阵的相加、相乘等。

对于这些操作，我们只需要按照链表的顺序进行遍历，并根据矩阵的位置信息进行计算即可。

稀疏矩阵十字链表算法的实现过程相对简单，但需要注意一些细节。

首先，我们需要确定稀疏矩阵的维度信息，并创建相应的行和列的链表头结点。

然后，我们可以按照行优先的方式遍历整个矩阵，将非零元素插入到链表中，并更新行和列的指针。

最后，我们可以根据需要进行各种矩阵操作。

稀疏矩阵十字链表算法是一种高效的存储和表示稀疏矩阵的方法。

它通过链表来存储非零元素，并记录它们在矩阵中的位置信息，从而节省了存储空间。

同时，它还可以支持各种常见的矩阵操作。

在实际应用中，稀疏矩阵十字链表算法可以提高程序的运行效率，减少内存的占用，是一种非常实用的数据结构算法。

#include<stdio.h>#include<malloc.h>#define Size 2501# define Size1 51typedef struct{int i;int j;int e;//非零元的值}triple; //定义三元组typedef struct{triple data[Size+1];//矩阵中的元素int rops[Size1+1];// rops[i]为第i行元素中的首非零元在data[]中的序号int mu;//行数int nu;//列数int tu;//非零元数} juzhen;//定义矩阵typedef struct node// 定义十字链表元素{int i,j,e;struct node *right,*down;// 该非零元所在行表和列表的后继元素}node,*link;typedef struct // 定义十字链表对象结构体{link *rhead,*chead;//行和列的头指针int m,n,t;// 系数矩阵的行数，列数，和非零元素个数}crosslist;void createcross(crosslist &M)//建立十字链表{int i,j,e,k;node *p,*q;printf("输入行，列和非零元数，空格隔开：\n");scanf("%d %d %d",&M.m,&M.n,&M.t);M.rhead=(link *)malloc((M.m+1)*sizeof(link));//给行和列的头指针分配内存M.chead=(link *)malloc((M.n+1)*sizeof(link));for(k=1;k<=M.m;k++)//初始化行，列的头指针M.rhead[k]=NULL;for(k=1;k<=M.n;k++)M.chead[k]=NULL;printf("输入非零元的行，列和值，空格隔开：\n");for(k=1;k<=M.t;k++)//输入非零元{scanf("%d %d %d",&i,&j,&e);p=(node *)malloc(sizeof(node));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{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->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;}}}void printcross(crosslist A)//输出十字链表{if(A.m==0)printf("十字链表为空!\n");else{printf("十字链表为:\n");int i,j;for(i=1;i<=A.m;i++){link p=A.rhead[i];for(j=1;j<=A.n;j++){if((p)&&(j==p->j)){printf("%5d",p->e);p=p->right; }elseprintf("%5d",0);}printf("\n");}}printf("\n");}crosslist addcross(){printf("十字链表加法:\n");crosslist a,b;// 创建两个十字链表对象，并初始化createcross(a);createcross(b);node *pre,*h[51],*pa,*pb,*q;//定义辅助指针，pa，pb分别为a,b当前比较的元素，pre为pa的前驱元素int i,j,k=0,m,n; //h[j]指向j列的当前插入位置if(a.m!=b.m||a.n!=b.n)printf("格式不对，不能相加!\n");else{for(i=1;i<=a.m;i++){pa=a.rhead[i];pb=b.rhead[i];pre=NULL;for(j=1;j<=a.n;j++)h[j]=NULL;while(pb){p=(node *)malloc(sizeof(node)); // 开辟新节点，存储b中取出的元素p->i=pb->i;p->j=pb->j;p->e=pb->e;if(pa==NULL||pa->j>pb->j)//当a此行已经检查完或者pb因该放在pa前面{if (pre==NULL)a. rhead[p->i]=p;elsepre->right=p;p->right=pa;pre=p;if (h[p->j]==NULL)//当前插入位置下面无非零元//因为是逐行处理，so,h[p->j]，依次下移//因此每次都是指向插入的位置{a. chead [p->j]= p;p->down = NULL;}else{p->down = h[p->j]->down;h[p->j]->down = p;}h[p->j]=p;//*******h[p->j]下移指向下次插入的位置pb=pb->right;//pb指向该行下个元素}else if((pa&&pa->j<pb->j))//只要移动pa的指针****先不加||(pb==NULL&&pa){pre = pa;h[pa->j]=pa;//移动h[]，使其指向下次插入的位置pa = pa->right;}else if(pa->j==pb->j){pa->e+=pb->e;if(pa->e)//不为零{pre=pa;h[pa->j]=pa;pb=pb->right;//加else//pa->e为零，删除节点{if (pre ==NULL)a.rhead [pa->i]=pa->right;else{pre->right=pa->right;}p=pa;//p指向pa，用来在下面修改列指针pa=pa->right;if (h [p->j]==NULL)a.chead [p->j]=p->down;else{h[p->j]->down=p->down;}free(p);pb=pb->right;}}}}}return a;}void multycross(crosslist &c)//十字链表乘法{node *p,*q,*u,*v,*p1,*p2;crosslist a,b;link *r;int i,j,k,e;printf("十字链表乘法:\n");createcross(a);createcross(b);if(a.n!=b.m)printf("格式错误，不能相乘！\n");else{c.m=a.m;c.n=b.n;c.t=0;c.rhead=(link *)malloc((a.m+1)*sizeof(link));//给行和列的头指针分配内存c.chead=(link *)malloc((b.n+1)*sizeof(link));for(k=1;k<=a.m;k++)//初始化行，列的头指针c.rhead[k]=NULL;for(k=1;k<=b.n;k++)c.chead[k]=NULL;r=(link *)malloc((b.n+1)*sizeof(link));for(i=1;i<=a.m;i++){u=(node *)malloc(sizeof(node));u->e=0;u->i=0;u->j=0;for(k=1;k<=b.n;k++)//初始化r[]r[k]=u;p1=p=a.rhead[i];for(j=1;j<=b.n;j++){p=p1;q=b.chead[j];v=(node *)malloc(sizeof(node));//初始化v，v为将插入c矩阵的元素v->e=0;v->i=i;v->j=j;while(p&&q){if(p->j>q->i)q=q->down;else if(p->j<q->i)p=p->right;else{v->e+=p->e*q->e;p=p->right;q=q->down;}}if(v->e)//如果不为零，则插入c矩阵中{//同建立十字链表if(c.rhead[i]==NULL||c.rhead[i]->j>j)//插入元素所在行无非零元或首非零元的列标大于插入元素的列标{v->right=c.rhead[i];c.rhead[i]=v;}else{for(p2=c.rhead[i];(p2->right)&&(p2->right->j<j);p2=p2->right);//空循环找到第一个列标大于或等于插入元素列标的元素v->right=p2->right;p2->right=v;}if(c.chead[j]==NULL||c.chead[j]->i>i)//插入元素所在列无非零元或首非零元的行标大于插入元素的行标{v->down=c.chead[j];c.chead[j]=v;}else{for(p2=c.chead[j];(p2->down)&&(p2->down->i<i);p2=p2->down);//空循环找到第一个行标大于或等于插入元素行标的元素v->down=p2->down;p2->down=v;}}}}}}void create(juzhen & M) //创建稀疏矩阵{int i,t=0;printf("输入矩阵行数和列数and非零元的个数，以空格隔开:\n");scanf("%d %d %d",&M.mu,&M.nu,&M.tu);printf("输入矩阵非零元的行，列，和数值(中间空格隔开):\n");for(i=1;i<=M.tu;i++)scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e); //输入三元组的元素for(i=1;i<=Size1;i++)//初始化rops【】M.rops[i]=0;for(i=1,t=1;i<=M.mu;i++)//得到各行第一个元素的序号{M.rops[i]=t;while(M.data[t].i<=i&&t<=M.tu)//遇到i行非零元，则t累加t++;}}void add(juzhen A,juzhen B,juzhen & C)//稀疏矩阵加法{int k=1,temp=0,k1=1, k2=1;//k1,k2,k分别控制A，B，C中非零元的序号变化printf("稀疏矩阵加法:\n");create(A);create(B);if(A.mu!=B.mu||A.nu!=B.nu)printf("格式不对，不能相加!\n");else{while(k1<=A.tu&&k2<=B.tu)//当A，B中的非零元都没用完{if(A.data[k1].i<B.data[k2].i)//A当前k1指向的元素的行标小于列标直接把data 【k1】的值赋给c中data【k】C.data[k++]=A.data[k1++];else if(A.data[k1].i>B.data[k2].i)//同上C.data[k++]=B.data[k2++];else//data[k1],data[k2]行标相同{if(A.data[k1].j>B.data[k2].j)//data[k1]列标大于data[k2]列标，则把data[k2]的值赋给data[k]C.data[k++]=B.data[k2++];else if(A.data[k1].j<B.data[k2].j)//同上C.data[k++]=A.data[k1++];else //行，列标都相同{temp=0;temp=A.data[k1].e+B.data[k2].e;if(temp)//相加后不为零{C.data[k].i=A.data[k1].i;C.data[k].j=A.data[k1].j;C.data[k].e=temp;k++;}k1++;k2++;}}}while(k1<=A.tu)//B中非零元已用完，A中还有非零元C.data[k++]=A.data[k1++];while(k2<=B.tu)//A中非零元已用完，B中还有非零元C.data[k++]=B.data[k2++];C.mu=A.mu;//确定C的行列数和非零元个数C.nu=A.nu;C.tu=k-1;}}void print(juzhen A)//输出稀疏矩阵{printf("\n矩阵为:\n");int i,j,k=1;if(A.mu==0)printf("矩阵为空！\n");else if(A.tu==0)//矩阵元素为空printf("零矩阵！\n");elsefor(i=1;i<=A.mu;i++)//逐行输出{for(j=1;j<=A.nu;j++){if(A.data[k].i==i&&A.data[k].j==j)//行和列分别对应相等则输出相应非零元，否则输出零printf("%5d",A.data[k++].e);elseprintf("%5d",0);}printf("\n");//该行输出结束，空行输出下一行}printf("\n");}void multy(juzhen A,juzhen B,juzhen &C)//稀疏矩阵乘法{int arow,brow,ccol,temp[51],p,q,t,tp,i;//各变量代表含义见下面printf("稀疏矩阵乘法:\n");create(A);create(B);if(A.nu!=B.mu)printf("格式错误，不能相乘！\n");else{C.mu=A.mu;//初始化c的行列及非零元个数C.nu=B.nu;C.tu=0;if(A.nu!=B.mu)printf("A,B格式不对不能相乘!\n");else //{for(arow=1;arow<=A.mu;arow++)//arow为当前A矩阵的行标{for(i=0;i<51;i++)//初始化temptemp[i]=0;if(arow<A.mu)tp=A.rops[arow+1];//tp为arow+1行的首非零元在data【】中的序号else //arow为最后一行tp=A.tu+1;for(p=A.rops[arow];p<tp;p++)//p为A中当前元素在data[]中的序号{brow=A.data[p].j;//brow为与B矩阵中的相应行对应的A中当前元素的列标if(brow<B.mu)t=B.rops[brow+1];//t为brow+1行的首非零元在B中data【】中的序号else //brow大小等于B.mut=B.tu+1;for(q=B.rops[brow];q<t;q++)//q为B中当前元素在B.data[]中的序号{ccol=B.data[q].j;//ccol：data[p]*data[q]所得结果所在的列temp[ccol]+=A.data[p].e*B.data[q].e;//temp【ccol】：相乘所得的C 矩阵中第arow行cool列元素的值}}for(ccol=1;ccol<=B.nu;ccol++)//if(temp[ccol])//temp【ccol】不为零，则把值赋到c中，c.tu加1。

稀疏矩阵的十字链表存储结构
稀疏矩阵是指矩阵中绝大多数元素为0，而仅有少数元素非0，这种矩阵的存在会占用大量的存储空间，而且在进行一些操作时也会变得非常低效。

为了解决这个问题，可以采用十字链表的方式对稀疏矩阵进行存储。

十字链表存储结构是一种非常高效的稀疏矩阵存储方法。

它将矩阵中所有非零元素按行列坐标分别存储到两个链表中，并且在每个节点中还包含指向该元素左右上下四个方向节点的指针，形成一个类似于十字路口的结构。

这样一来，我们就可以在O(n)的时间内轻松地遍历矩阵中所有的非零元素，而且还能够快速地定位和更新某个元素的值，大大提高了存储和处理的效率。

在十字链表存储结构中，我们通常会使用头节点来记录矩阵的大小和非零元素的总数，以及行列链表的头指针。

节点中的数据需要同时包含行列坐标和元素的值，这样才能够快速地进行查找和替换。

同时，在插入或删除一个元素时，我们需要更新该元素所在节点的邻接节点的指针，以保证整个结构的完整性和正确性。

总的来说，十字链表存储结构是一种非常高效和灵活的稀疏矩阵存储方案，可以大大减小矩阵的存储空间和处理时间，同时也可以满足各种复杂的操作需求。

在实际应用中，我们可以根据具体的问题和数据特征灵活地选择适合的数据结构和算法，来达到更好的效果和效率。

十字链表实现矩阵的加法：/*---------------------------------------------------------------------------------用十字链表实现稀疏矩阵的加法--------------------------------------------编译环境：VS 2013---------------------------------------------------------------------------------------*/#define_CRT_SECURE_NO_WARNINGS//用于取消VS 2013对printf、scanf等函数的警告#include<stdio.h>#include<stdlib.h>#define MAXSIZE 50typedef int ElemType;typedef struct matrixnode//结构体和共用体的定义{int i, j;struct matrixnode *right, *down;union{ElemType value;struct matrixnode *next;}tag;}manode;manode *creatcroslist(); //建立稀疏矩阵的函数，返回十字链表头指针void insert(int i, int j, int value, manode *cp[]);//插入结点函数manode *add(manode *A, manode *B); //矩阵相加void print(manode *M); //输出十字链表的函数void main(){manode *A, *B, *C;printf("正在获取稀疏矩阵A......\n");A = creatcroslist();system("cls");printf("正在获取稀疏矩阵B......\n");B = creatcroslist();system("cls");printf("稀疏矩阵A：\n");print(A);printf("稀疏矩阵B：\n");print(B);C = add(A, B);puts("稀疏矩阵A与稀疏矩阵B的和为：");print(C);}manode *creatcroslist(){manode *p, *q, *head, *cp[MAXSIZE];int i, j, k, m, n, t, s;ElemType value;printf("请输入行、列、非零元素个数（中间用逗号隔开）：");scanf("%d,%d,%d", &m, &n, &t);if (m > n)s = m;elses = n;head = (manode *)malloc(sizeof(manode));//建立十字链表头结点head->i = m;head->j = n;cp[0] = head;//cp[]是临时指针数组，分别指向头结点和行、列表头结点for (i = 1; i <= s; i++)//建立头结点循环链表{p = (manode *)malloc(sizeof(manode));p->i = 0;p->j = 0;p->right = p;p->down = p;cp[i] = p;cp[i - 1]->tag.next = p;}cp[s]->tag.next = head;for (k = 1; k <= t; k++){printf("第%d个非零元素的行号、列号、元素值（中间用逗号隔开）:", k);scanf("%d,%d,%d", &i, &j, &value);p = (manode *)malloc(sizeof(manode));p->i = i;p->j = j;p->tag.value = value;q = cp[i];while ((q->right != cp[i]) && (q->right->j < j))q = q->right;p->right = q->right;q->right = p;q = cp[j];while ((q->down != cp[j]) && (q->down->i < i))q = q->down;p->down = q->down;q->down = p;}return head;}void insert(int i, int j, int value, manode *cp[]){manode *p, *q;p = (manode *)malloc(sizeof(manode));p->i = i;p->j = j;p->tag.value = value;//以下是经*p结点插入第i行链表中q = cp[i];while ((q->right != cp[i]) && (q->right->j < j))q = q->right;//在第i行中找第一个列号大于j的结点*(q->right)//找不到时，*q是该行表上的尾结点p->right = q->right;q->right = p;//*p插入在*q之后//以下是将结点插入第j列链表中q = cp[j];//取第j列表头结点while ((q->down != cp[j]) && (q->down->i < i))q = q->down;//在第j行中找第一个列号大于i的结点*(q->down)//找不到时，*q是该行表上的尾结点p->down = q->down;q->down = p;//*p插入在*q之后}manode *add(manode *A, manode *B){manode *p, *q, *u, *v, *r, *cp[MAXSIZE], *C;//p,q控制十字链A的行列,u,v控制十字链B的行列int s, i;if (A->i != B->i || A->j != B->j){puts("稀疏矩阵A与稀疏矩阵B不能相加！");exit(0);}//建立C的表头环链C = (manode *)malloc(sizeof(manode));C->i = A->i; C->j = A->j;if (C->i > C->j)s = C->i; else s = C->j;cp[0] = C;for (i = 1; i <= s; i++){r = (manode *)malloc(sizeof(manode));r->i = 0; r->j = 0;r->right = r; r->down = r;cp[i] = r;cp[i - 1]->tag.next = r;}cp[s]->tag.next = C;//矩阵相加p = A->tag.next; u = B->tag.next;while (p != A && u != B){q = p->right;v = u->right;if (q == p && v != u)//矩阵A中第p行为空，矩阵B的第u行不为空while (v != u)//将B的行的都复制到和矩阵中{insert(v->i, v->j, v->tag.value, cp);v = v->right;}else if (v == u && q != p)//矩阵A中第p行不为空，矩阵B的第u行为空while (q != p){insert(q->i, q->j, q->tag.value, cp);q = q->right;}else if (q != p && v != u)//矩阵B的第u行和矩阵A的第p行都不为空{while (q != p && v != u){if(q->j<v->j)//如果A中有元素的列数小于B的，将A中的所有小于B的值都插到C中{insert(q->i, q->j, q->tag.value, cp);q = q->right;}else if (q->j>v->j)//如果B中有元素的列数小于A的，将A中的所有小于B的值都插到C中{insert(v->i, v->j, v->tag.value, cp);v = v->right;}else//A、B当前是在同一个位置，判断加的和是否为零，不为零才做加法运算{if (q->tag.value + v->tag.value != 0)insert(q->i, q->j, (q->tag.value + v->tag.value), cp);q = q->right; v = v->right;}}if (q == p && v != u)//如果B未处理完，将B中未处理的值都插入到和矩阵中while (v != u){insert(v->i, v->j, v->tag.value, cp);v = v->right;}else if (v == u && q != p)//如果A未处理完，将A中未处理的值都插入到和矩阵中while (q != p){insert(q->i, q->j, q->tag.value, cp);q = q->right;}}p = p->tag.next;u = u->tag.next;//A，B都指向下一行}return C;}void print(manode *M){manode *p, *q, *r;//p是指向行，q是指向列，r是指向某一节点的临时指针int k, t, col, row;col = M->j;//矩阵M的列数p = M->tag.next;//p指向第一个结点，不是头结点row = 1;while (row <= M->i)//判断行是否循环完{q = p->right;//p指向这一行的一个值r = p;//r指向这一行的头结点while (q != p)//判断列是否循环完{for (k = 1; k < (q->j - r->j); k++)//输出同一行上两非零数据间的零printf(" 0");printf("%4d", q->tag.value);//输出那个非零值q = q->right;//q指向这一行的下一个元素r = r->right;//r指向q前面的一个非零元素}k = r->j;//k的值是某一行的最后一个非零元的列数for (t = k; t < col; t++)//输出一行上最后一个非零元后面的零printf(" 0");printf("\n\n");p = p->tag.next;//p指向下一行row++;}}程序运行结果图：。

采用十字链表表示稀疏矩阵,并实现矩阵的加法运算课程设计所抽题目: 采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。

要求:要检查有关运算的条件，并对错误的条件产生报警。

问题分析和建立模型:本题目主要是运用所学知识，用十字链表的方法去表示稀疏矩阵，并使之可以在两矩阵间进行相加。

而后，若有错误，则对错误进行警报。

框架搭建:1选择File|New菜单项，弹出New对话框，选择Files标签，选中C++ Source File项，在File编辑器中输入项目名称“十字链表表示稀疏矩阵实现加法”，在Location编辑框中输入项目所在目录，按下OK按钮即可。

2在操作界面中输入，程序代码。

(1) 结构体和共用体的定义#include<stdio.h>#include<malloc.h>#define smax 45typedef int datatype;typedef struct lnode(2) 建立稀疏矩阵的函数，返回十字链表头指针 int i,j;struct lnode *cptr,*rptr;union{struct lnode *next;datatype v;}uval;}link;int flag=0;建立十字链表头结点 head=(link *)malloc(sizeof(link)); 建立头结点循环链表 for(i=1;i<=s;i++)(3) 插入结点函数 p=(link *)malloc(sizeof(link));p->i=0;p->j=0;p->rptr=p;p->cptr=p;cp[i]=p; cp[i-1]->uval.next=p;}cp[s]->uval.next=head;for(k=1;k<=t;k++){printf("\t 第%d个元素(行号i 列号j 值v，数字间用空格分隔):",k);scanf("%d%d%d",&i,&j,&v);p=(link *)malloc(sizeof(link));p->i=i;p->j=j;p->uval.v=v;q=cp[i];while((q->rptr!=cp[i])&&(q->rptr->j<j))q=q->rptr;p->rptr=q->rptr;q->rptr=p;q=cp[j];while((q->cptr!=cp[j])&&(q->cptr->i<i))q=q->cptr;p->cptr=q->cptr;q->cptr=p;}return head;(4) 输出十字链表的函数 link *p,*q;p=(link *)malloc(sizeof(link));p->i=i;p->j=j;p->uval.v=v;q=cp[i];while((q->rptr!=cp[i])&&(q->rptr->j<j))q=q->rptr;p->rptr=q->rptr;q->rptr=p;q=cp[j];while((q->cptr!=cp[j])&&(q->cptr->i<i))q=q->cptr ;p->cptr=q->cptr;q->cptr=p;(5)定义两个矩阵的非零元素，及两个矩阵的行和列数。

c语言稀疏矩阵应用代码实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。

在C语言中，实现稀疏矩阵的加法、转置和乘法涉及复杂的数据结构和算法。

其中，常用的表示稀疏矩阵的两种数据结构是三元组和十字链表。

下面我将为您提供一个简单的示例代码，用C语言实现稀疏矩阵的加法、转置和乘法操作，使用三元组表示法来表示稀疏矩阵。

首先，我们需要定义表示稀疏矩阵的三元组结构体：```c#include<stdio.h>#define MAX_SIZE100typedef struct{int row;int col;int value;}Element;typedef struct{int rows;int cols;int num_elements;Element data[MAX_SIZE];}SparseMatrix;```接下来，我们实现稀疏矩阵的加法、转置和乘法函数：```c#include<stdbool.h>//加法函数SparseMatrix addSparseMatrix(SparseMatrix matrix1,SparseMatrix matrix2){ SparseMatrix result;result.rows=matrix1.rows;result.cols=matrix1.cols;result.num_elements=0;int i=0,j=0;while(i<matrix1.num_elements&&j<matrix2.num_elements){if(matrix1.data[i].row<matrix2.data[j].row||(matrix1.data[i].row==matrix2.data[j].row&&matrix1.data[i].col<matrix2.data[j].col)){ result.data[result.num_elements++]=matrix1.data[i++];}else if(matrix1.data[i].row>matrix2.data[j].row||(matrix1.data[i].row==matrix2.data[j].row&&matrix1.data[i].col>matrix2.data[j].col)){ result.data[result.num_elements++]=matrix2.data[j++];}else{Element element;element.row=matrix1.data[i].row;element.col=matrix1.data[i].col;element.value=matrix1.data[i].value+matrix2.data[j].value;if(element.value!=0){result.data[result.num_elements++]=element;}i++;j++;}}while(i<matrix1.num_elements){result.data[result.num_elements++]=matrix1.data[i++];}while(j<matrix2.num_elements){result.data[result.num_elements++]=matrix2.data[j++];}return result;}//转置函数SparseMatrix transposeSparseMatrix(SparseMatrix matrix){ SparseMatrix result;result.rows=matrix.cols;result.cols=matrix.rows;result.num_elements=matrix.num_elements;int count[matrix.cols];int index[matrix.cols];for(int i=0;i<matrix.cols;i++){count[i]=0;}for(int i=0;i<matrix.num_elements;i++){count[matrix.data[i].col]++;}index[0]=0;for(int i=1;i<matrix.cols;i++){index[i]=index[i-1]+count[i-1];}for(int i=0;i<matrix.num_elements;i++){int j=index[matrix.data[i].col];result.data[j].row=matrix.data[i].col;result.data[j].col=matrix.data[i].row;result.data[j].value=matrix.data[i].value;index[matrix.data[i].col]++;}return result;}//乘法函数SparseMatrix multiplySparseMatrix(SparseMatrix matrix1,SparseMatrix matrix2){ SparseMatrix result;if(matrix1.cols!=matrix2.rows){result.rows=0;result.cols=0;result.num_elements=0;return result;}result.rows=matrix1.rows;result.cols=matrix2.cols;result.num_elements=0;bool visited[matrix2.cols];for(int i=0;i<matrix2.cols;i++){visited[i]=false;}for(int i=0;i<matrix1.num_elements;i++){for(int j=0;j<matrix2.num_elements;j++){if(matrix1.data[i].col==matrix2.data[j].row){Element element;element.row=matrix1.data[i].row;element.col=matrix2.data[j].col;element.value=matrix1.data[i].value*matrix2.data[j].value; result.data[result.num_elements++]=element;visited[matrix2.data[j].col]=true;}}}for(int i=0;i<matrix2.cols;i++){if(!visited[i]){for(int j=0;j<matrix1.rows;j++){Element element;element.row=j;element.col=i;element.value=0;result.data[result.num_elements++]=element;}}}return result;}```请注意，上述代码只是一个简单示例，实际应用中可能需要根据具体需求进行优化和扩展。