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

数据结构实验报告三稀疏矩阵的运算实验课程名称数据结构课程设计专业班级学⽣姓名学号指导教师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]。

#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设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。

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

十字链表存储稀疏矩阵实现相乘算法#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");}。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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