下载文档原格式
408考稀疏矩阵十字链表稀疏矩阵是指矩阵中绝大部分元素为0的情况下，只存储非零元素及其位置信息的一种存储方式。
在计算机科学中，稀疏矩阵的存储方式有多种，其中一种较为常见的方式是使用十字链表。
十字链表是一种基于链表的数据结构，用于表示稀疏矩阵。
它通过两个链表和一个头节点来表示稀疏矩阵的行和列。
具体来说，十字链表由以下几个部分组成：1. 头节点：头节点用于存储稀疏矩阵的行数、列数和非零元素的个数等基本信息。
2. 行链表：行链表由多个节点组成，每个节点代表稀疏矩阵的一行。
每个节点包含三个属性：行号、列号和值。
行链表按照行号从小到大的顺序排列。
3. 列链表：列链表由多个节点组成，每个节点代表稀疏矩阵的一列。
每个节点包含三个属性：行号、列号和值。
列链表按照列号从小到大的顺序排列。
4. 节点链接：行链表和列链表中的节点通过行号和列号进行链接。
对于每个节点，除了存储自身的行号、列号和值外，还需存储其所在行的下一个节点和所在列的下一个节点。
使用十字链表来存储稀疏矩阵的好处是可以大大减少存储空间的使用，尤其适用于稀疏矩阵中非零元素的个数相对较少的情况。
通过十字链表，我们可以快速访问稀疏矩阵中的非零元素，并且可以方便地进行行和列的插入、删除和修改操作。
下面举一个具体的例子来说明408考稀疏矩阵十字链表的应用。
假设有一个3行4列的稀疏矩阵，其中非零元素分别为6、8、9、7，它们的位置分别是(1, 2)、(2, 1)、(2, 3)、(3, 4)。
我们可以使用十字链表来表示这个稀疏矩阵。
我们创建一个头节点，存储稀疏矩阵的行数、列数和非零元素的个数，即3、4和4。
然后，我们创建4个节点，分别表示这4个非零元素。
这些节点的属性分别为：(1, 2, 6)、(2, 1, 8)、(2, 3, 9)和(3, 4, 7)。
同时，我们需要将这些节点链接到行链表和列链表中相应的位置。
在行链表中，我们将这些节点按照行号从小到大的顺序插入。
首先，我们插入节点(1, 2, 6)，因为它的行号最小。
稀疏矩阵的⼗字链表存储稀疏矩阵的压缩存储有⼏种⽅式，如：三元组顺序表、⾏逻辑链接的顺序表和⼗字链表。
使⽤链表存储的好处是：便于矩阵中元素的插⼊和删除。
例如：“将矩阵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即可。
数据结构课程设计十字链表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); 创建以十字链表表示的一个元素全为零的稀疏矩阵。
一、问题描述十字链表实现稀疏矩阵的加法1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。
2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。
再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。
这样，一个稀疏矩阵就输入完成。
若输入4 3 2则表示这个稀疏矩阵有4行3列2个非零元然后用户需要为这两个非零元输入行、列、非零元的值如：1 2 24 1 1表示第一个非零元行为1，列为2,，值为2；第二个非零元行为4，列为1，值为1。
此过程输入的稀疏矩阵为：0 2 00 0 00 0 01 0 03、输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非零元则输出“0”。
各元素之间用空格隔开。
最后输出完整的矩阵。
二、概要设计1．稀疏矩阵的抽象数据类型定义如下：ADT SparseMatrix {数据对象： D={a ij|i=1,2,3……m,j=1,2,3……n;a ij属于ElemSet,m和n分别是稀疏矩阵的行数和列数}数据关系： R={ Row, Col }Row={<a ij,a ij+1>|1<=i<=m,1<=j<=n-1}Col={<a ij,a i+1j>|1<=i<=m-1,1<=j<=n}基本操作：CreateSMatrix(&M);//建立稀疏矩阵MDestroySMatrix(&M);//销毁稀疏矩阵M；TransposeSMatrix(M);//求稀疏矩阵的转置矩阵AddSMatrix(&M,&N);//求稀疏矩阵M和N之和MulSMatrix(&M,&N);//求稀疏矩阵M和N之积}ADT SparseMatrix2、存储结构选择采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。
稀疏矩阵加法链表稀疏矩阵加法是计算机科学领域中经常使用的一种算法，它的优势在于可以使用链表来代表稀疏矩阵，从而提高了计算的效率。
本文将介绍稀疏矩阵加法和链表的相关知识，并分步骤阐述稀疏矩阵加法链表的算法过程。
一、稀疏矩阵稀疏矩阵是指矩阵中大部分元素都是0的矩阵，他们在实际应用中常常出现，例如在图像处理、网络流分析等领域中。
为了避免浪费空间和资源，对于稀疏矩阵的存储和计算的方法需要特殊处理。
二、链表链表是一种由一系列结点组成的数据结构，结点之间通过指针相互连接。
链表的优势在于可以灵活地插入、删除结点，并且占用的空间相对更加紧凑。
因此，链表是表示稀疏矩阵的一种优秀的数据结构选择。
三、算法过程稀疏矩阵加法的过程与普通矩阵加法相似，只不过在计算过程中需要注意稀疏元素的位置和数量。
算法的具体步骤如下：1.创建链表：首先，需要使用链表来表示稀疏矩阵。
链表中的每个结点对应矩阵中的一个非零元素，结点分别保存行号、列号和非零元素的值。
链表需要按照行号递增的顺序排列。
2.读取输入：读取两个需要相加的稀疏矩阵，将它们转换为链表的形式，并按照行号递增的顺序排列。
3.遍历链表：接着从链表的头部开始遍历两个链表，将相同位置的元素相加。
具体而言，如果两个结点的行号和列号相同，则将两个元素的值相加，并将结果保存在一个新的链表中。
4.合并链表：最后将所有剩余的元素添加到结果链表中。
5.输出结果：输出结果链表所表示的矩阵。
四、时间复杂度稀疏矩阵加法链表的时间复杂度取决于两个输入矩阵中的非零元素数量，以及链表遍历的次数。
由于稀疏矩阵通常包含大量的0，因此非零元素的数量相对较小，从而可以大大提高计算效率。
在最坏情况下，算法的时间复杂度为$O(n)$，其中n表示两个稀疏矩阵中的非零元素数量的总和。
五、总结稀疏矩阵加法链表是一种高效的算法，它能够利用链表的特性来存储和计算稀疏矩阵。
通过链表的方式，可以避免浪费大量的内存和空间，同时提高了计算的效率。
稀疏矩阵的十字链表
稀疏矩阵是指在大多数元素都为零的情况下，只有少部分元素非零的矩阵。
与之相对应的是稠密矩阵，即大多数元素都非零的矩阵。
为了节省存储空间，我们可以采用特殊的数据结构来存储稀疏矩阵。
其中，十字链表是一种常用的数据结构。
十字链表是一种链式存储结构，用于存储稀疏矩阵。
它的基本思想是先将矩阵按行分解成一组行链表，再将矩阵按列分解成一组列链表。
每个非零元素在行链表和列链表中各有一个结点，这个结点包括该元素在矩阵中的行、列编号以及该元素的值。
通过行链表和列链表，我们可以快速地访问矩阵中的非零元素。
具体来说，十字链表包括两种结点，分别为行结点和列结点。
行结点的数据成员包括该非零元素所在的行号、列号、该元素的值，以及指向同一行中下一个非零元素的指针和同一列中下一个非零元素的指针。
列结点的数据成员包括该非零元素所在的行号、列号、该元素的值，以及指向同一列中下一个非零元素的指针和同一行中下一个非零元素的指针。
通过这样的链式存储结构，我们可以实现在O(k)的时间复杂度内访问矩阵中任意一个非零元素，其中k为矩阵中非零元素的个数。
总的来说，十字链表是一种用于存储稀疏矩阵的高效数据结构，它采用链式存储方式，能够快速地访问矩阵中的非零元素，并且能够有效地节省存储空间。
稀疏矩阵十字链表算法稀疏矩阵是指矩阵中大部分元素为0的矩阵。
在实际应用中，稀疏矩阵常常出现，比如图像处理、网络分析等领域。
由于稀疏矩阵中存在大量的0元素，传统的二维数组存储方式会造成内存空间的浪费，因此需要一种高效的数据结构来表示和存储稀疏矩阵。
稀疏矩阵十字链表算法就是一种解决这个问题的方法。
稀疏矩阵十字链表算法是一种基于链表的数据结构，用于表示和存储稀疏矩阵。
它通过两个链表来分别表示行和列，同时还使用了一个数据链表来存储非零元素的值和位置信息。
这种算法的核心思想是将稀疏矩阵的非零元素存储在链表中，并记录它们在矩阵中的位置信息，从而节省了存储空间。
具体来说，稀疏矩阵十字链表算法中，我们可以使用三个结构体来表示矩阵的行、列和非零元素。
其中，行和列的结构体包含了指向非零元素的指针和矩阵的维度信息。
非零元素的结构体包含了元素的值、行列坐标以及指向下一个非零元素的指针。
使用稀疏矩阵十字链表算法存储稀疏矩阵的好处是，它不仅节省了存储空间，还可以提高对稀疏矩阵的操作效率。
比如，对于稀疏矩阵的遍历操作，我们可以通过遍历链表的方式来实现，而不需要遍历整个矩阵，从而减少了时间复杂度。
除了存储和遍历操作，稀疏矩阵十字链表算法还可以支持其他一些常见的矩阵操作，比如矩阵的相加、相乘等。
对于这些操作，我们只需要按照链表的顺序进行遍历，并根据矩阵的位置信息进行计算即可。
稀疏矩阵十字链表算法的实现过程相对简单，但需要注意一些细节。
首先，我们需要确定稀疏矩阵的维度信息，并创建相应的行和列的链表头结点。
然后，我们可以按照行优先的方式遍历整个矩阵，将非零元素插入到链表中，并更新行和列的指针。
最后，我们可以根据需要进行各种矩阵操作。
稀疏矩阵十字链表算法是一种高效的存储和表示稀疏矩阵的方法。
它通过链表来存储非零元素，并记录它们在矩阵中的位置信息，从而节省了存储空间。
同时，它还可以支持各种常见的矩阵操作。
在实际应用中，稀疏矩阵十字链表算法可以提高程序的运行效率，减少内存的占用，是一种非常实用的数据结构算法。
稀疏矩阵的十字链表存储的思路
稀疏矩阵是指大部分元素都是零的矩阵。
为了避免浪费存储空间，可以采用十字链表存储法。
具体实现思路如下：
1. 定义结构体Node，表示矩阵中的一个非零元素。
2. 定义结构体CrossListNode，表示十字链表中的一个节点，
包含4个指针，分别指向同一行中的下一个非零元素、同一列中的下一个非零元素、上一个非零元素以及左一个非零元素。
3. 定义结构体CrossListMatrix，表示十字链表矩阵，包含三
个变量：矩阵的行数、列数和非零元素数目，以及两个指针，分别指向行和列的头节点。
4. 创建行和列的头节点，依次扫描矩阵中的非零元素，创建一
个Node节点，并把它插入到行和列的链表中。
同时，记录该元素在
行和列中的位置，以便于更新节点的指针。
5. 最后建立行和列之间的链接，即将同一行中的节点按照列的
顺序链接起来，同理，将同一列中的节点按照行的顺序链接起来。
6. 完成十字链表矩阵的存储。
通过以上方法，可以有效地减少存储空间的浪费，提高矩阵的存储效率，同时也方便了对矩阵中非零元素的操作。
- 1 -。
C语言稀疏矩阵十字链#include "stdio.h"#include "stdlib.h"#define MAX 100#define elemtype inttypedef struct node{int i;int j;elemtype Value;struct node*Down;struct node*Right;}cross2type;typedef struct{int m;int n;cross2type*pc[MAX];}clinktype;void CrtCross(clinktype**Head){int m,n,s,t,k,i,j,Value;cross2type*p,*q;printf("请输入行数：");scanf("%d",&m);printf("请输入列数：");scanf("%d",&n);s=m<n?n:m;(*Head)=(clinktype*)malloc(sizeof(clinktype)); (*Head)->m=m;(*Head)->n=n;for(k=0;k<s;k++){(*Head)->pc[k]=(cross2type*)malloc(sizeof(cro ss2type));(*Head)->pc[k]->i=0;(*Head)->pc[k]->j=0;(*Head)->pc[k]->Down=NULL;(*Head)->pc[k]->Right=NULL; printf("%d",k);}printf("请输入非零元素个数：");scanf("%d",&t);for(k=0;k<t;k++){printf("输入第%d个三元组：",k+1);scanf("%d%d%d",&i,&j,&Value);p=(cross2type*)malloc(sizeof(cross2type));p->i=i;p->j=j;p->Value=Value;q=(*Head)->pc[i];while(q->Right!=NULL&&q->Right->j<j)q=q->Right;p->Right=q->Right;q->Right=p;q=(*Head)->pc[j];while(q->Down!=NULL&&q->Down->i<i)q=q->Down;p->Down=q->Down;q->Down=p;}}void print_Cross(clinktype **head){clinktype *p;cross2type*p1;int i,j;p=*head;for(i=0;i<p->n;i++)printf("输出列号");//输出列序号。
采用十字链表表示稀疏矩阵,并实现矩阵的加法运算课程设计所抽题目: 采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。
要求:要检查有关运算的条件，并对错误的条件产生报警。
问题分析和建立模型:本题目主要是运用所学知识，用十字链表的方法去表示稀疏矩阵，并使之可以在两矩阵间进行相加。
而后，若有错误，则对错误进行警报。
框架搭建: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)定义两个矩阵的非零元素，及两个矩阵的行和列数。
采⽤⼗字链表存储的稀疏矩阵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)。
这是由于每建⽴⼀个⾮零元结点时，都需要通过遍历查询它所在的⾏表和列表中的插⼊位置。
