下载文档原格式
数据结构实验报告三稀疏矩阵的运算实验课程名称数据结构课程设计专业班级学⽣姓名学号指导教师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]。
十字链表法存储稀疏矩阵稀疏矩阵是指其中大部分元素为0的矩阵。
在实际应用中，稀疏矩阵的存储和计算都会带来一定的困扰。
为了高效地存储和处理稀疏矩阵，我们可以使用十字链表法。
一、稀疏矩阵的特点稀疏矩阵的特点是其中绝大部分元素为0，而只有少部分非零元素。
这导致稀疏矩阵的存储空间浪费很大，因此需要采取一种有效的存储方式。
二、十字链表法的原理十字链表法是一种组合了链表和线性表的数据结构，用于存储稀疏矩阵。
具体实现如下：1. 定义两个链表headRow和headCol，分别用于存储行和列的头节点；2. 每个非零元素都对应一个结点，结点包含四个属性：行号row、列号col、值value以及指向下一个非零元素的指针nextRow和nextCol；3. headRow链表中的每个节点都指向同一行中的第一个非零元素，而headCol链表中的每个节点都指向同一列中的第一个非零元素；4. 非零元素之间通过nextRow和nextCol指针连接。
通过这种方式，我们可以高效地存储稀疏矩阵，并可以方便地进行矩阵的各种操作。
三、十字链表法的优势相比于其他存储稀疏矩阵的方法，十字链表法有以下几个优势：1. 空间利用率高：相比于使用二维数组存储，十字链表法可以大大减少存储空间的浪费，因为只存储非零元素及其位置信息；2. 支持高效的插入和删除操作：十字链表法可以通过调整指针的指向来进行插入和删除操作，而不需要像其他方法那样移动元素；3. 方便进行矩阵操作：通过十字链表法，我们可以方便地进行稀疏矩阵的各种操作，如矩阵相加、矩阵相乘等。
四、十字链表法的应用十字链表法广泛地应用于各个领域，特别是在图论和网络分析中。
在这些领域中，往往需要处理大规模的稀疏矩阵，而十字链表法能够有效地解决这个问题。
以社交网络为例，社交网络中的用户和用户之间往往存在着复杂的关系。
通过将社交网络建模成稀疏矩阵，可以使用十字链表法来存储和处理这些关系。
这样可以方便地进行各种网络分析操作，如查找某个用户的好友、计算两个用户之间的距离等。
十字链表存储稀疏矩阵实现相乘算法#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");}。
数据结构学习（C++）—稀疏矩阵（十字链表【1】）happycock（原作）转自CSDN先说说什么叫稀疏矩阵。
你说，这个问题很简单吗，那你一定不知道中国学术界的嘴皮子仗，对一个字眼的“抠”将会导致两种相反的结论。
这是清华2000年的一道考研题：“表示一个有1000个顶点，1000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？”如果你是个喜欢研究出题者心理活动的人，你可以看出这里有两个陷阱，就是让明明会的人答错，我不想说出是什么，留给读者思考。
姑且不论清华给的标准答案是什么，那年的参考书是严蔚敏的《数据结构（C语言版）》，书上对于稀疏矩阵的定义是这样的：“非零元较零元少（注：原书下文给出了大致的程度），且分布没有一定规律”，照这个说法，那题的答案应该是不一定是稀疏矩阵，因为可能是特殊矩阵（非零元分布有规律）。
自从2002年换参考书后，很多概念都发生了变化，最明显的是从多少开始计数（0还是1），从而导致的是空树的高度变成了－1，只有一个根节点的树高度是0。
很不幸的是树高的问题几乎年年都考，在你下笔的时候，总是犯点嘀咕，总不是一朝天子一朝臣吧，会不会答案是个兼容版本？然后，新参考书带的习题集里引用了那道考研题，答案是是稀疏矩阵。
你也许会惊讶这年头咸鱼都会游泳了，但这个答案和书并不矛盾，因为在这本黄皮书里，根本就没有什么特殊矩阵，自然就一定是稀疏矩阵了。
其实，这两本书在这个问题上也没什么原则上的问题，C版的是从数据结构实现区分出特殊矩阵和稀疏矩阵，毕竟他们实现起来很不相同；新书一股脑把非零元少的矩阵都当成稀疏矩阵，当你按照这种思路做的时候就会发现，各种结构特殊的非零元很少的矩阵，如果用十字链表来储存的话，比考虑到它的特殊结构得出的特有储存方法，仅仅是浪费了几个表头节点和一些指针域，再有就是一些运算效率的降低。
从我个人角度讲，我更喜欢多一些统一，少一些特别，即使牺牲一点效率；所以在这一点上我赞同新参考书的做法。
采⽤⼗字链表存储的稀疏矩阵Description当矩阵的⾮零元个数和位置在操作过程中变化较⼤时，就不宜采⽤顺序存储的结构来表⽰三元组的线性表了。
因此，在这种情况下，采⽤链式存储结构表⽰三元组更为恰当。
⼗字链表就是能够实现这样功能的⼀种数据结构。
在⼗字链表中，每个⾮零元可以⽤⼀个包含5个域的结点表⽰。
其中i、j和e这3个域分别表⽰该⾮零元所在的⾏、列和⾮零元的值，向右域right⽤来链接同⼀⾏中下⼀个⾮零元，⽽向下域down⽤来链接同⼀列中下⼀个⾮零元。
同⼀⾏的⾮零元通过right域链接成⼀个线性链表，同⼀列的⾮零元通过down域链接成⼀个线性链表。
每个⾮零元既是某个⾏链表中的⼀个结点，⼜是某个列链表中的⼀个结点，整个矩阵通过这样的结构形成了⼀个⼗字交叉的链表。
稀疏矩阵的⼗字链表类型可以描述如下：下⾯是建⽴稀疏矩阵⼗字链表的算法描述：给出⼀个稀疏矩阵，请将其存储到⼀个⼗字链表中，并将存储完毕的矩阵输出。
Input输⼊的第⼀⾏是两个整数r和c（r<200, c<200, r*c <= 12500），分别表⽰⼀个包含很多0的稀疏矩阵的⾏数和列数。
接下来有r⾏，每⾏有c个整数，⽤空格隔开，表⽰稀疏矩阵的各个元素。
Output输出读⼊的矩阵。
输出共有r⾏，每⾏有c个整数，每个整数后输出⼀个空格。
请注意⾏尾输出换⾏。
Sample Input5 60 18 0 0 0 00 0 67 0 0 00 0 0 0 0 410 0 47 62 0 00 0 0 0 0 35Sample Output0 18 0 0 0 00 0 67 0 0 00 0 0 0 0 410 0 47 62 0 00 0 0 0 0 35HINT提⽰：对于m⾏n列且有t个⾮零元的稀疏矩阵，算法5.4的执⾏时间为O(t×s)，其中s=max(m,n)。
这是由于每建⽴⼀个⾮零元结点时，都需要通过遍历查询它所在的⾏表和列表中的插⼊位置。
