数据结构 | 十字链表完成稀疏矩阵相加

2020-12-21 21:53:33

十字链表的实现

当稀疏矩阵的非零元数量和位置在操作过程中变化较大时(如矩阵相加)，便不再适宜采用顺序存储，此时使用链式存储更为恰当。

十字链表的实现

typedef struct{

int i,j;

ElemType e;

OLNode *right,*down;

//right指示同一行下一个非零元，down指示同一列下一个非零元

}OLNode,*OLink;

typedef struct

{

OLink *rhead,*chead;

//两个一维数组，分别指示行链表的头指针和列链表的头指针

int mu,nu,tu;

}CrossList;

十字链表的创建

Status CreateMatrix(CrossList *M){

int m,n,t;

int i,j;

ElemType e;

OLNode *q,*p;

if(M){

free(M);

}

printf("输入矩阵的行数、列数和非零元素个数:");

scanf("%d%d%d",m,n,t);

M->mu=m;

M->nu=n;

M->tu=t;

//确定M的行列数和个数

M->rhead=(OLink*)malloc((m+1)*sizeof(OLink));

M->chead=(OLink*)malloc((n+1)*sizeof(OLink));

if(!M->rhead||!M->chead){

return OVERFLOW;

}

for(int i=1;i<=m;i++){

M->rhead[i]=NULL;

}

for(int j=1;j<=n;j++){

M->chead[j]=NULL;

}

//初始化行指针和列指针

for(scanf("%d%d",&i,&j,&e);i!=0;scanf("%d%d",&i,&j,&e)){

p=(OLNode*)malloc(sizeof(OLNode));

if(!p){

return OVERFLOW;

}

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->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{

for(q=M->chead[j];q->down&&q->down->idown);

p->down=q->down;

q->down=p;

}

}

return OK;

}

实现矩阵相加

int Insert(CrossList M,OLink p)`//把p所指向的节点插入到十字链表中`

{

int i,j,e;

OLink q,q1;

i=p->i;

j=p->j;

e=p->e;

if`(i<1||i>M.mu||j<1||j>M.nu||0==e) cout<

if`(!M.rhead[i]||M.rhead[i]->j>j)`

{

p->right=M.rhead[i];

M.rhead[i]=p;

}

else

{

q=M.rhead[i];

q1=q->right;

if`(!q1) { q->right=p;p->right=NULL;}`

else

{

while`(q1->j

{

q=q->right;

q1=q1->right;

if`(!q1)break`;

}

if`(q1)`

{

q->right=p;

p->right=q1;

}

else { q->right=p;p->right=NULL;}

}

}

//判断纵行插入的位置

if`(!M.chead[j]||M.chead[j]->i>i)`

{

p->down=M.chead[j];

M.chead[j]=p;

}

else

{

q=M.chead[j];

q1=q->down;

if`(!q1) { q->down=p;p->down=NULL;}`

else

{

while`(q1->i

{

q=q->down;

q1=q1->down;

if`(!q1)break`;

}

if`(q1)`

{

q->down=p;

p->down=q1;

}

else { q->down=p;p->down=NULL;}

}

}

return 0;

}

int Delete(CrossList M,OLink p)`//把p所指向的节点从十字链表中删除`

{

int i,j;

OLink q,q1;

i=p->i;

j=p->j;

q=M.rhead[i];

q1=q->right;

if`(j==q->j)`

{

M.rhead[i]->right=q->right;

free`(q);`

}

else

{

while`(q1->j!=j)`

{

q=q->right;

q1=q1->right;

}

q->right=q1->right;

free`(q1);`

}

return 0;

}

OLink IsExist(CrossList M,OLink p)`//判断p所指向的节点是否存在于M十字链表中`

{

int i,j;

OLink q;

i=p->i;

j=p->j;

q=M.rhead[i];

while`(q)`

{

if`(j==q->j)returnq;`

else q=q->right;

}

return 0;

}

int SMatrix_Add(CrossList &M1,CrossList M2)

{

int k;

OLink p,pr=NULL;

if`(M1.mu!=M2.mu||M1.nu!=M2.nu)return0;`

for`(k=1;k<=M2.mu;k++)`//按M2逐行进行

{

p=M2.rhead[k];

while`(p)`//每行用指针逐个后移

{

pr=IsExist(M1,p);

if`(!pr) Insert(M1,p);`//如果p所指向的节点在M1中不存在，则直接插入M1

else

{

pr->e+=p->e;

if`(!pr->e) Delete(M1,pr);`

}

Display(M1);

p=p->right;

}

}

return 0;

}

更多相关内容

十字链表存储稀疏矩阵

2021-11-23 10:29:03

若矩阵中的元素多数为0，只有少数的元素为非0元素时，我们成该矩阵为稀疏矩阵。我们有矩阵Aij，其中有非0元素m个，若mij≤0.05，则我们称矩阵Aij为稀疏矩阵 我们有矩阵A_{ij}，其中有非0元素m个，若\frac{m}{ij} \...

对于矩阵的存储，如果矩阵的元素呈有明显规律的排列的话，我们一般用一个一维数组对矩阵进行压缩存储；若矩阵中的元素多数为0，只有少数的元素为非0元素时，我们成该矩阵为稀疏矩阵。
$我们有矩阵A_{ij}，其中有非0元素m个，若\frac{m}{ij} \le 0.05，则我们称矩阵A_{ij}为稀疏矩阵$
对于稀疏矩阵，因为非零元素的排列是没有规律的，因此我们无法采用压缩的方法存储矩阵，而若用一个二维数组去存储含有为数不多的非零元素的矩阵，会有大量的空间浪费在存储毫无意义的0元素上，因此，对于稀疏矩阵，我们可以选择用十字链表来存储。

话不多说，先上代码

#include<stdio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1


typedef int DataType;
typedef struct SNode
{
	int row;
	int column;

	union
	{
		DataType value;
		struct SNode *next;
	}uval;

	struct SNode *rnext;
	struct SNode *cnext;
}SNode, *SNodePtr;


// 创建矩阵
DataType **
CreateMatrix(int row, int column);

// 创造十字链表
SNodePtr
Create(int row, int column);

// 向十字链表插入(如果存在则相加)
void
Insert(SNodePtr phead, SNodePtr pnode);

// 将稀疏矩阵转换成十字链表存储
SNodePtr
Matrix2List(DataType **pparr, int row, int column);

// 矩阵相加
SNodePtr
MatrixAdd(SNodePtr phead1, SNodePtr phead2);

// 打印矩阵
void
Print(SNodePtr phead);


int main()
{
	printf("请输入第一个矩阵\n");
	DataType **arr1 = CreateMatrix(4, 4);
	printf("\n\n请输入第二个矩阵\n");
	DataType **arr2 = CreateMatrix(4, 4);

	SNodePtr phead1 = Matrix2List(arr1, 4, 4);
	SNodePtr phead2 = Matrix2List(arr2, 4, 4);

	printf("\n\n\n");
	// 打印两个矩阵
	Print(phead1);
	printf("\n\n\n");
	Print(phead2);
	printf("\n\n\n");

	SNodePtr phead = MatrixAdd(phead1, phead2);
	Print(phead);
	return 0;
}


// 创建矩阵
DataType **
CreateMatrix(int row, int column)
{
	DataType **ipparr = (int **)malloc(sizeof(int *) * row);

	for(int i = 0; i < row; ++i)
	{
		ipparr[i] = (int *)malloc(sizeof(int) * column);
		for(int j = 0; j < column; ++j)
			scanf("%d", &ipparr[i][j]);
	}
	return ipparr;
}

// 创造十字链表
SNodePtr
Create(int row, int column)
{
	// 创建头结点
	SNodePtr phead = (SNodePtr)malloc(sizeof(SNode));
	phead->row = row;
	phead->column = column;
	phead->rnext = phead->cnext = NULL;
	phead->uval.next = NULL;
	SNodePtr ptmp = phead;

	// 创建十字链表
	if(row > column)
	{
		for(int i = 0; i < row; ++i)
		{
			ptmp->uval.next = (SNodePtr)malloc(sizeof(SNode));
			ptmp = ptmp->uval.next;
			ptmp->row = ptmp->column = 0;
			ptmp->uval.next = NULL;
			ptmp->cnext = ptmp;
			if(i < column)
				ptmp->rnext = ptmp;
			else 
				ptmp->rnext = NULL;
		}
	}
	else
	{
		for(int i = 0; i < column; ++i)
		{
			ptmp->uval.next = (SNodePtr)malloc(sizeof(SNode));
			ptmp = ptmp->uval.next;
			ptmp->row = ptmp->column = 0;
			ptmp->uval.next = NULL;
			ptmp->rnext = ptmp;
			if( i < row)
				ptmp->cnext = ptmp;
			else
				ptmp->cnext = NULL;
		}
	}
	return phead;
}

// 向十字链表插入(如果存在则相加)
void
Insert(SNodePtr phead, SNodePtr pnode)
{
	SNodePtr prtmp = phead;
	// 找到对应行
	for(int i = 0; i < pnode->row; ++i)
		prtmp = prtmp->uval.next;

	SNodePtr ptmp1 = prtmp;
	// 找到要插入的地方
	while(ptmp1->cnext != prtmp && ptmp1->cnext->column < pnode->column)
		ptmp1 = ptmp1->cnext;

	if(ptmp1->cnext->column !=  pnode->column)		
	{
		SNodePtr ptmp = (SNodePtr)malloc(sizeof(SNode));		// 新开辟空间使为了不改变pnode的指针
		ptmp->cnext = ptmp1->cnext;
		ptmp1->cnext = ptmp;
		ptmp->column = pnode->column;
		ptmp->row = pnode->row;
		ptmp->uval.value = pnode->uval.value;
		ptmp->rnext = NULL;

		// 接下来要将行指针连接
		SNodePtr pctmp = phead;
		// 找到对应列
		for(int i = 0; i < pnode->column; ++i)
			pctmp = pctmp->uval.next;

		SNodePtr ptmp2 = pctmp;
		// 找到要插入的地方
		while(ptmp2->rnext != pctmp && ptmp2->rnext->row < pnode->row)
			ptmp2 = ptmp2->rnext;
		ptmp->rnext = ptmp2->rnext;
		ptmp2->rnext = ptmp;
		return ;
	}
	else		// 这一行有非零元素且他们在同一列
	{
		ptmp1->cnext->uval.value += pnode->uval.value;
		return ;		// 因为没有开辟新的空间，原来的结构不变，因此不需要对列进行操作，直接返回即可
	}

}

	

// 将稀疏矩阵转换成十字链表存储
SNodePtr
Matrix2List(DataType **pparr, int row, int column)
{
	SNodePtr phead = Create(row, column);		// 创建十字链表

	// 创建并初始化临时指针
	SNodePtr ptmp = (SNodePtr)malloc(sizeof(SNode));
	ptmp->row = ptmp->column = 0;
	ptmp->uval.value = 0;
	ptmp->rnext = ptmp->cnext = NULL;

	for(int i = 0; i < row; ++i)
	{
		for(int j = 0; j < column; ++j)
		{
			if(pparr[i][j] != 0)
			{
				ptmp->row = i + 1;
				ptmp->column = j + 1;
				ptmp->uval.value = pparr[i][j];
				Insert(phead, ptmp);
			}
		}
	}
	return phead;
}


// 矩阵相加
SNodePtr
MatrixAdd(SNodePtr phead1, SNodePtr phead2)
{
	if(phead1->row != phead2->row || phead1->column != phead2->column)		// 矩阵无法相加
		return NULL;

	SNodePtr phead = Create(phead1->row, phead1->column);

	// 将phead1加入phead
	SNodePtr ptmp = phead1;
	for(int i = 0; i < phead1->row; ++i)
	{
		ptmp = ptmp->uval.next;
		SNodePtr ptmp2 = ptmp;
		while(ptmp2->cnext != ptmp)
		{
			ptmp2 = ptmp2->cnext;
			Insert(phead, ptmp2);
		}
	}

	Print(phead);

	// 将phead2加入phead
	ptmp = phead2;
	for(int i = 0; i < phead2->row; ++i)
	{
		ptmp = ptmp->uval.next;
		SNodePtr ptmp2 = ptmp;
		while(ptmp2->cnext != ptmp)
		{
			ptmp2 = ptmp2->cnext;
			Insert(phead, ptmp2);
		}
	}

	return phead;
}

// 打印矩阵
void
Print(SNodePtr phead)
{
	SNodePtr prtmp = phead;
	for(int i = 0; i < phead->row; ++i)
	{
		prtmp = prtmp->uval.next;
		SNodePtr pctmp = prtmp->cnext;
		if(pctmp == prtmp)
		{
			printf("0 0 0 0 ");
			continue;
		}

		for(int j = 1; j <= pctmp->column; ++j)
		{
			if(j < pctmp->column)
				printf("0 ");
			else
			{
				printf("%d ", pctmp->uval.value);
				pctmp = pctmp->cnext;
				if(pctmp == prtmp)
				{
					for(int k = phead->column; k > j; --k)
						printf("0 ");
					break;
				}
			}
		}
		printf("\n");
	}
	printf("\n");
}

我的基本思想是对于矩阵的操作是不会影响原矩阵，即A + B = C，C不是将A加入B或者B加入A得到的，而是新开辟的一块空间。基于此思想，在进行插入操作的时候，我并没有对待插入的结点的指针做任何转变，而是找到要插入的位置，新开辟一块空间，将待插入结点的值，行列等赋值给新开辟的空间，然后再连接插入的结点的行列指针即可。基于此思想，我们在执行矩阵A和B的相加的时候，完全不用考虑矩阵A和矩阵B中指针的变动，只需要创建一个新的空的十字链表，然后将A和B中的元素插入即可。

收起

展开全文

数据结构

十字链表实现稀疏矩阵的乘法
2014-09-03 16:55:28

用C++编写的稀疏矩阵乘法运算，稀疏矩阵采用十字链表存储及计算

收起
基于十字链表存储的稀疏矩阵的转置
2019-04-28 14:29:32

实现了从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构（m、n分别表示矩阵行数和列数；i, j为非零元素行号和列号）和十字链表的转置并将转置后的三元组到另一字符文件中

收起

C++

十字链表实现稀疏矩阵，包含十二大功能

2021-11-19 09:38:15

用十字链表存储和表示稀疏矩阵，并实现如下功能 2．基本要求初始化：创建十字链表并从文件中读取稀疏矩阵数据（文件数据可以是三元组结构）；在十字链表上设置坐标为（i，j）的位置值为value；获取坐标为（i...

题目：

十字链表实现稀疏矩阵

1．问题描述

用十字链表存储和表示稀疏矩阵，并实现如下功能

2．基本要求

初始化：创建十字链表并从文件中读取稀疏矩阵数据（文件数据可以是三元组结构）；
在十字链表上设置坐标为（i，j）的位置值为value；
获取坐标为（i，j）的位置的值；
插入一项、删除某项的值；
输出十字链表表示的稀疏矩阵；
实现两个稀疏矩阵的加法、减法、乘法的功能，结果保存到新的十字链表中；
实现把十字链表表示的稀疏矩阵存入文件；
可以用菜单选择所有功能，设计良好的操作界面；
在需求分析阶段完成未尽功能需求，适当扩充功能（例如矩阵转置、求最值等）。

实现：

技术难点1：uthash存储十字链表矩阵，给每个矩阵进行命名，以名字作为key，十字链表作为value,实现相对自动化的功能；（需要自己在github上找到相关资源）

技术难点2：十字链表矩阵的插入函数是整个代码的核心，需要对十字链表的存储结构比较熟悉

技术难点3：十字链表矩阵的相加函数，针对两个矩阵不同对应的情况进行相加

代码前面的声明：

#include<iostream>
#include<cstdlib>
#include<iomanip>
#include"uthash.h" 
using namespace std;

/*                 稀疏矩阵的十字链表存储                                       */

typedef struct OLNode
{
    int row;                                                    			//非零元素的行下标
    int col;    															//非零元素的列下标
    int elem;    															//非零元素值
    struct OLNode *right;   												//右节点
    struct OLNode *down;   												    //下节点

}OLNode, *OLink;

typedef struct 
{
    OLink *rhead;   														//行指针链表
    OLink *chead;   														//列指针链表
    int rowSum;     														//矩阵的行数
    int ColSum;     														//矩阵的列数
    int NumSum;     														//矩阵的非零元素个数
}CrossList; 


/*                 uthash哈希表的结构体声明                                      */

struct HashCross{															//哈希表
    char name[10];															//矩阵名称  key
    CrossList crosslist;													//十字链表结构体  value
    UT_hash_handle hh;												
}HashCross;

/*                          全局hash表，存储矩阵                                */

struct HashCross *cross = NULL;											
 
/*   ************************************************************************** */

/*                          函数声明                                            */


void menu();						                    					//主菜单
void menu1(); 						               							//初始化部分
void menu2();						                						//基础操作部分
void menu3();  						                						//进阶操作部分   
void InitSMatrix(CrossList &M);				  								//初始化矩阵
void CreateMatrix(CrossList &M);											//创建矩阵	
void PrintSMatrix(CrossList M);												//输出矩阵
void InsertElem(OLink &newnode,CrossList &M);								//插入元素到矩阵M中
void changeValue(CrossList &M);												//寻找矩阵M中的某个值
void findValue(CrossList &M);												//查找矩阵中的某个值
void deleteValue(CrossList &M);												//删除矩阵中的某个值
void AddMatrix(CrossList &M,CrossList &N,CrossList &out);					//两个矩阵的相加
void SubtractMatrix(CrossList &M,CrossList &N,CrossList &out);				//两个矩阵的相减
void MultiplyMatrix(CrossList &M,CrossList &N,CrossList &out);				//两个矩阵的相乘
void TransposeSMatrix(CrossList &M, CrossList &out);						//矩阵的转置 
void findMaxOrMin(CrossList &M);										    //矩阵求最值 
void CopySMatrix(CrossList &M, CrossList &out);								//复制矩阵 
void ReadFromFile(CrossList &M);											//从文件中读取矩阵 
void WriteToFile(CrossList &M);												//把矩阵写入文件 
CrossList HashFind(char *name);												//哈希查找函数(没有该矩阵，手动创建)
CrossList HashFind2( char *name);											//哈希查找函数(没有该矩阵，文件读取创建)
CrossList getCrossList();													//控制台获取矩阵名称(没有该矩阵，手动创建)



/*   ************************************************************************** */

具体每个功能的函数：

/*                        实现功能的函数                                        */



/*                        1. 主菜单                                             */
void menu()    
{
    int c=0;
	printf("--------------------------------------------------------------------------------\n");
	printf("******************<-----欢迎使用十字链表存储的稀疏矩阵进行操作----->*****************\n\n");
	printf("\t\t\t     1.*--<矩阵初始化>--*\n\n");
	printf("\t\t\t     2.*--<矩阵基本操作（插入、删除、查找）>--*\n\n");
	printf("\t\t\t     3.*--<矩阵进阶操作（四则运算、求逆、求转置、求最值等）>--*\n\n");
	printf("\t\t\t     4.*--<退出本程序>--*\n\n");
	printf("\n\n********************************************************************************\n");
	printf("--------------------------------------------------------------------------------\n");
	printf("*请输入相应功能的编号:");
	do
	{
		cin >> c;
		if(c<1||c>4)
			printf("*无该选项!请重新输入:");
	}while(c<1||c>4);
     switch(c)
     {
    	case 1:menu1();break;
	    case 2:menu2();break;
	   	case 3:menu3();break;
    	case 4:exit(0);break;
      }
}

/*   ************************************************************************** */

/*                        2.初始化菜单                                          */ 

void menu1()   
{
	int c=0;
	while(c != 1){
		printf("--------------------------------------------------------------------------------\n");
		printf("******************<-----欢迎来到矩阵初始化菜单----->*****************\n\n");
		printf("\t\t\t     1.*--<返回主菜单>--*\n\n");
		printf("\t\t\t     2.*--<手动输入矩阵>--*\n\n");
		printf("\t\t\t     3.*--<从文件中读取矩阵>--*\n\n");
		printf("\t\t\t     4.*--<退出本程序>--*\n\n");
		printf("\n\n********************************************************************************\n");
		printf("--------------------------------------------------------------------------------\n");
		printf("*请输入相应功能的编号:");
		do
		{
			cin >> c;
			if(c<1||c>4)
				printf("*无该选项!请重新输入:");
		}while(c<1||c>4);
	     switch(c)
	     {
	    	case 1:
				menu();
				break;
		    case 2:{
                getCrossList();
				break;
			}

	    	case 3:{
	    		CrossList M;
		    	printf("请输入需要操作的矩阵名称:（长度小于10）\n");
	            char name[10];
	            cin >> name;
				M = HashFind2(name); 
				break;
			}
	    	case 4:exit(0);
				break;
	      }
	  }
}

/*   ************************************************************************** */

/*                        3.  矩阵基本操作菜单                                  */

void menu2()     
{   
	int c=0;
    while(c != 1){
		printf("--------------------------------------------------------------------------------\n");
		printf("******************<-----欢迎来到矩阵基本操作菜单----->*****************\n\n");
		printf("\t\t\t     1.*--<返回主菜单>--*\n\n");
		printf("\t\t\t     2.*--<查看矩阵下标的值>--*\n\n");
		printf("\t\t\t     3.*--<删除矩阵下标的值>--*\n\n");
		printf("\t\t\t     4.*--<增加矩阵下标的值>--*\n\n");
		printf("\t\t\t     5.*--<退出本程序>--*\n\n");
		printf("\n\n********************************************************************************\n");
		printf("--------------------------------------------------------------------------------\n");
		printf("*请输入相应功能的编号:");
		do
		{
			cin >> c;
			if(c<1||c>5)
				printf("*无该选项!请重新输入:");
		}while(c<1||c>5);
	     switch(c)
	     {
	    	case 1:menu();break;
		    case 2:{
		    	CrossList M;
		    	M = getCrossList(); 
				findValue(M);
				break;
			}

	    	case 3:{
	    		CrossList M;
	    		M = getCrossList();
				deleteValue(M);
				break;
			}

	    	case 4:{
	    		CrossList M;
	    		M = getCrossList();
				changeValue(M);
				break;
			}		

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

/*   ************************************************************************** */

/*                        4.  矩阵进阶操作菜单                                  */

void menu3()     
{
    int c=0;
    while(c != 1){
		printf("--------------------------------------------------------------------------------\n");
		printf("******************<-----欢迎来到矩阵进阶操作菜单----->*****************\n\n");
		printf("\t\t\t     1.*--<返回主菜单>--*\n\n");
		printf("\t\t\t     2.*--<求稀疏矩阵的加法>--*\n\n");
		printf("\t\t\t     3.*--<求稀疏矩阵的减法>--*\n\n");
		printf("\t\t\t     4.*--<求稀疏矩阵的乘法>--*\n\n");
		printf("\t\t\t     5.*--<求稀疏矩阵的转置>--*\n\n");
		printf("\t\t\t     6.*--<输出稀疏矩阵>--*\n\n");
		printf("\t\t\t     7.*--<求稀疏矩阵的最值>--*\n\n");
		printf("\t\t\t     8.*--<将稀疏矩阵存入文件>--*\n\n");
		printf("\t\t\t     9.*--<退出本程序>--*\n\n");
		printf("\n\n********************************************************************************\n");
		printf("--------------------------------------------------------------------------------\n");
		printf("*请输入相应功能的编号:");
		do
		{
			cin >> c;
			if(c<1||c>9)
				printf("无该选项!请重新输入:");
		}while(c<1||c>9);
	     switch(c)
	     {
	    	case 1:
				menu(); break;
		    case 2:{
		    	CrossList M,N,out;
	    		M = getCrossList();
	    		N = getCrossList();
				AddMatrix(M,N,out);
				break;
			}
				
	    	case 3:{
	    		CrossList M,N,out;
	    		M = getCrossList();
	    		N = getCrossList();
				SubtractMatrix(M,N,out);
				break;
			}
				
	    	case 4:{
	    		CrossList M,N,out;
	    		M = getCrossList();
	    		N = getCrossList();
				MultiplyMatrix(M,N,out);
				break;
			}
				
	    	case 5:{
	    		CrossList M,out;
	    		M = getCrossList();
				TransposeSMatrix(M,out);
				break;
			}
				
	    	case 6:{
	    		CrossList M;
	    		M = getCrossList();
	    		PrintSMatrix(M);	
				break;
				} 
				
	    	case 7:{
	    		CrossList M;
	    		M = getCrossList();
				findMaxOrMin(M);
				break;
				}
	    	case 8:{
				CrossList M;
	    		M = getCrossList();
	    		WriteToFile(M);
				break;
			} 
	    	case 9:exit(0);break;
	      }
	  }
}
/*   ************************************************************************** */


/*                        5.  初始化稀疏矩阵                                    */

void InitSMatrix(CrossList &M){
    M.rhead = (OLink *)malloc((M.rowSum+1)*sizeof(OLink));
    M.chead = (OLink *)malloc((M.ColSum+1)*sizeof(OLink));
    
    //将所有结点赋为空值
    for(int i = 1; i<=M.rowSum; i++)
    {
        M.rhead[i]=NULL;
    }
    for(int i = 1; i <= M.ColSum; i++)
    {
        M.chead[i]=NULL;
    }
}

/*   ************************************************************************** */


/*                        6.  创建稀疏矩阵                                      */
void CreateMatrix(CrossList &M){
    int rowSum,ColSum,NumSum;
    int row, col, elem;
    cout << "请输入创建的稀疏矩阵的行数、列数、非0元素个数：\n" << endl;
	cin >> rowSum >> ColSum >> NumSum;
    M.rowSum = rowSum;
    M.ColSum = ColSum;
    M.NumSum = NumSum;
    //初始化矩阵
    InitSMatrix(M);
    //对矩阵进行赋值
    cout << "请按任意次序输入" << M.NumSum <<"个非零元的行 列 元素值:" << endl;

    for(int i = 1; i <= NumSum; i++){
    	cin >> row; 
		cin >> col;
		cin >> elem;
        OLink newNode = (OLink)malloc(sizeof(OLNode));
        newNode -> row = row;
        newNode -> col = col;
        newNode -> elem = elem;
        InsertElem(newNode,M);
    }
    cout << "创建成功！创建的矩阵为：\n" << endl;
//    printf("创建成功！创建的矩阵为：\n");
    PrintSMatrix(M); 
    
}

/*   ************************************************************************** */

/*                        7.  插入结点值                                        */

void InsertElem(OLink &newnode, CrossList &M){
    //将非零元素结点插入矩阵中
    OLink rowNode = M.rhead[newnode->row];
    //行的插入
    if (rowNode == NULL || rowNode -> col > newnode -> col) // 插在该行的第一个结点处 
		{
			newnode->right = rowNode;
			M.rhead[newnode->row] = newnode;
		}
	else 
		{
            //寻找插的位置的前一个结点
			for (; !(rowNode->col < newnode->col && (rowNode->right == NULL||rowNode -> right -> col > newnode->col)); rowNode = rowNode->right);
			newnode->right = rowNode->right; //完成行插入 
			rowNode->right = newnode;
		}

    //列的插入
    OLink colNode = M.chead[newnode -> col];
    if (colNode == NULL || colNode -> row > newnode -> row) // 插在该行的第一个结点处 
		{
			newnode->down = colNode;
			M.chead[newnode->col] = newnode;
		}
	else 
		{
            //寻找插的位置的前一个结点
			for (; !(colNode -> row < newnode->row && (colNode -> down == NULL || colNode -> down -> row > newnode->row)); colNode = colNode->down);
			newnode->down = colNode->down; //完成列插入 
			colNode->down = newnode;
		}
}

/*   ************************************************************************** */

/*                        8.  输出矩阵                                          */

void PrintSMatrix(CrossList M){
    //初始条件: 稀疏矩阵M存在
    int i, j;
	for (i = 1; i <= M.rowSum; i++)
	{ // 从第1行到最后1行
		OLink p = M.rhead[i]; // p指向该行的第1个非零元素
		for (j = 1; j <= M.ColSum; j++) // 从第1列到最后1列
			if (!p || p->col != j) // 已到该行表尾或当前结点的列值不等于当前列值
				printf("%-5d", 0); // 输出0
			else
			{
				printf("%-5d", p->elem);
				p = p->right;
			}
		printf("\n");
	}
}

/*   ************************************************************************** */

/*                        9. 修改矩阵中某个元素的值(如果没有就增加）            */

void changeValue(CrossList &M){
	//如果不存在对应下标的值，则直接插入新的值
	int row;
	int col;
	int elem;
	cout << "请输入需要修改的矩阵的行 列 元素值:\n" << endl;
	cin >> row >> col >> elem;
	OLink rowNode = M.rhead[row];
	OLink newnode = (OLink)malloc(sizeof(OLNode));
    newnode->row = row;
    newnode->col = col;
    newnode->elem = elem;

	if(rowNode == NULL || rowNode -> col > col){
		//如果行链表的头结点为空或者是当前修改的结点的列值大于头结点的列值，直接插入
		cout << "插入新值！\n" << endl;
//		printf("插入新值！\n");
		InsertElem(newnode,M);
	}
	else{
		OLink nextNode = rowNode;
		//头结点不为空，进行判断
		while(nextNode){
			if(nextNode -> col == col){
				nextNode -> elem = elem;
				cout << "修改成功！\n" << endl;
//				printf("修改成功！\n");
				break;
			}
			else if(nextNode -> col > col){
				cout << "插入新值！\n" << endl;
//				printf("插入新值！\n");
				InsertElem(newnode,M);
				break;
			}
			else{
				nextNode = nextNode -> right;
			}
		}
		//头结点为空时，直接插入
		if(nextNode == NULL){
			cout << "插入新值！\n" << endl;
//			printf("插入新值！\n");
			InsertElem(newnode,M);
		}
	}
	cout << "修改后的矩阵为:\n" << endl;
//	printf("修改后的矩阵为:\n");
	PrintSMatrix(M);
}

/*   ************************************************************************** */

/*                        10. 查找矩阵中某个元素的值                            */

void findValue(CrossList &M){
	int row;
	int col;
	cout << "请输入需要查找的矩阵的对应的行 列 下标值（如：10 10）:\n" << endl;
    cin >> row >> col;
	OLink rowNode = M.rhead[row];
	if(rowNode == NULL || rowNode -> col > col){
		//如果行链表的头结点为空或者是当前修改的结点的列值大于头结点的列值，该元素的值为0
		cout << "下标为：(" << row << "," << col << ")值elem = 0\n" << endl;
	}
	else{
		OLink nextNode = rowNode;
		//头结点不为空，进行判断
		while(nextNode){
			if(nextNode -> col == col){
				int val = nextNode -> elem;
				cout << "下标为：(" << row << "," << col << ")值elem =" << val << endl;
				break;
			}
			else if(nextNode -> col > col){
				cout << "下标为：(" << row << "," << col << ")值elem = 0\n" << endl;
				break;
			}
			else{
				nextNode = nextNode -> right;
			}
		}
		//头结点为空时，值为0 
		if(nextNode == NULL){
			cout << "下标为：(" << row << "," << col << ")值elem = 0\n" << endl;
		}
	}

}

/*   ************************************************************************** */

/*                        11. 删除矩阵中某个元素的值                            */

void deleteValue(CrossList &M){
	int row;
	int col;
	cout << "请输入1需要删除的矩阵的对应的行 列 的下标值（如：10 10）:\n" << endl;
	scanf("%d %d", &row, &col);

	//行指针的删除
	OLink rowNode = M.rhead[row];
	if(rowNode == NULL || rowNode -> col > col){
		//如果行链表的头结点为空或者是当前的结点的列值大于头结点的列值，该元素的值为0
		cout << "该下标对应的值为0，无需删除\n" << endl;
		return;
	}
	else{
		OLink p = NULL, q = NULL;
		p = rowNode;
		while(rowNode){
			if(rowNode -> col == col){
				if(p == rowNode){
					M.rhead[row] = p -> right;
				}
				else{
					q ->right = p -> right;
				}
				break;
			}
			else if(rowNode -> col > col){
				return;
			}
			else{
				q = p;
				p = p -> right;
			}
		}
	}

	//列指针的删除
	OLink ColNode = M.chead[col];
	if(ColNode == NULL || ColNode -> row > row){
		cout << "该下标对应的值为0，无需删除\n" << endl;
		return;
	}
	else{
		OLink p = NULL, q = NULL;
		p = ColNode;
		while(ColNode){
			if(ColNode -> col == col){
				if(p == ColNode){
					M.chead[col] = p -> down;
				}
				else{
					q -> down = p -> down;
				}
				break;
			}
			else if(ColNode -> row > row){
				return;
			}
			else{
				q = p;
				p = p -> down;
			}
		}
	}
	cout << "删除成功！\n" << endl;
	cout << "删除后的矩阵为：\n" << endl;
	PrintSMatrix(M);
}

/*   *************************************************************************  */

/*                        12. 两个矩阵相加                                      */

void AddMatrix(CrossList &M,CrossList &N, CrossList &out){

	//判断矩阵是否满足相加条件
	if(M.ColSum != N.ColSum || M.rowSum != N.rowSum){
		cout << "两个矩阵不是同类型的,不能相加\n" << endl;
		return;
	}

	//对out矩阵进行初始化
	out.ColSum = M.ColSum;
	out.rowSum = M.rowSum;
	out.NumSum = 0;
	InitSMatrix(out);

	//进行相加
	for(int row = 1; row <= M.rowSum; row++){
		OLink Node1 = M.rhead[row];
		OLink Node2 = N.rhead[row];
		for(int col = 1; col <= M.ColSum; col++){
			//M,N在相同位置都有值
			if(Node1 && Node1 -> col == col && Node2 && Node2 -> col == col){
//               //中间变量保存
//				OLink Node3 = Node1;
//				OLink temp = Node1 -> right;
//				int tmp = Node1 -> elem;
//
//                //插入
//				Node3 -> elem = Node1-> elem + Node2 -> elem;
//				InsertElem(Node3, out);
//				out.NumSum++;
//
//                //移动指针
//                Node1->elem = tmp;
//                Node1 = temp;
//				Node2 = Node2 -> right;

				//赋值
				OLink Node3 = (OLink)malloc(sizeof(OLNode));
				Node3 -> elem = Node1-> elem + Node2 -> elem;
				Node3 -> row = Node1 -> row;
				Node3 -> col = Node1 -> col;
				cout << Node1 -> elem;
				cout << Node2 -> elem;
				cout <<  Node3 -> elem  <<  Node3 -> row  << Node3 -> col << endl;

				//插入 
				InsertElem(Node3, out);
				out.NumSum++;
				
				//移动指针 
                Node1 = Node1 -> right;
				Node2 = Node2 -> right;
			}
			//M位置没有值，N位置有值
			if((Node1==NULL||Node1->col!=col)&& Node2 && Node2->col == col)
            {
//            	//中间变量保存
//				OLink Node3 = Node2;
//				OLink temp = Node2 -> right;
//
//                //插入
//				InsertElem(Node3, out);
//				out.NumSum++;
//
//                //移动指针
//                Node2 = temp;
				
				//赋值 
				OLink Node3 = (OLink)malloc(sizeof(OLNode));
				Node3 -> elem = Node2 -> elem;
				Node3 -> row = Node2 -> row;
				Node3 -> col = Node2 -> col;
				
				//插入 
				InsertElem(Node3,out);
                out.NumSum++;
                
                //移动指针 
                Node2 = Node2->right;
            }
			//M位置有值，N位置没有值
		   if(Node1 && Node1->col == col && (Node2 == NULL||Node2 ->col != col))
            {
//            	//中间变量保存
//            	OLink Node3 = Node1;
//            	OLink temp = Node1 -> right;
//            	
//            	//插入
//				InsertElem(Node3, out);
//				out.NumSum++;
//				
//				//移动指针
//                Node1 = temp;

			
				//赋值 
				OLink Node3 = (OLink)malloc(sizeof(OLNode));
				Node3 -> elem = Node1 -> elem;
				Node3 -> row = Node1 -> row;
				Node3 -> col = Node1 -> col;
				
				//插入 
				InsertElem(Node3,out);
                out.NumSum++;
                
                //移动指针 
                Node1 = Node1->right;
            }
		}
	}
	cout << "相加后的矩阵为：\n" << endl;
	PrintSMatrix(out);
}

/*   *************************************************************************  */

/*                        13. 两个矩阵相减                                      */

void SubtractMatrix(CrossList&M,CrossList &N, CrossList &out){

	//判断矩阵是否满足相减 条件
	if(M.ColSum != N.ColSum || M.rowSum != N.rowSum){
		cout << "两个矩阵不是同类型的,不能相减 \n" << endl;
		return;
	}

	//对out矩阵进行初始化
	out.ColSum = M.ColSum;
	out.rowSum = M.rowSum;
	out.NumSum = 0;
	InitSMatrix(out);

	//进行相减 
	for(int row = 1; row <= M.rowSum; row++){
		OLink Node1 = M.rhead[row];
		OLink Node2 = N.rhead[row];
		for(int col = 1; col <= M.ColSum; col++){
			//M,N在相同位置都有值
			if(Node1 && Node1 -> col == col && Node2 && Node2 -> col == col){
//				//中间变量保存
//				OLink Node3 = Node1;
//				OLink temp = Node1 -> right;
//
//                //插入
//				Node3 -> elem = Node1-> elem - Node2 -> elem;
//				InsertElem(Node3, out);
//				out.NumSum++;
//
//                //移动指针
//                Node1 = temp;
//				Node2 = Node2 -> right;


				//赋值
				OLink Node3 = (OLink)malloc(sizeof(OLNode));
				Node3 -> elem = Node1-> elem - Node2 -> elem;
				Node3 -> row = Node1 -> row;
				Node3 -> col = Node1 -> col;

				//插入 
				InsertElem(Node3, out);
				out.NumSum++;
				
				//移动指针 
                Node1=Node1->right;
				Node2 = Node2 -> right;
			}
			//M位置没有值，N位置有值
			if((Node1 == NULL || Node1 -> col != col) && Node2 && Node2 -> col == col)
            {
//            	//中间变量保存
//				OLink Node3 = Node2;
//				OLink temp = Node2 -> right;
//
//                //插入
//				Node3 -> elem = - Node2-> elem;
//				InsertElem(Node3, out);
//				out.NumSum++;
//
//                //移动指针
//                Node2 = temp;

				//赋值 
				OLink Node3 = (OLink)malloc(sizeof(OLNode));
				Node3 -> elem = - Node2 -> elem;
				Node3 -> row = Node2 -> row;
				Node3 -> col = Node2 -> col;
				
				//插入 
				InsertElem(Node3,out);
                out.NumSum++;
                
                //移动指针 
                Node2 = Node2->right;
            }
			//M位置有值，N位置没有值
		   if(Node1 && Node1 -> col == col && (Node2 == NULL || Node2 -> col != col))
            {
//            	//中间变量保存
//            	OLink Node3 = Node1;
//            	OLink temp = Node1 -> right;
//            	
//            	//插入
//				InsertElem(Node3, out);
//				out.NumSum++;
//				
//				//移动指针
//                Node1 = temp;

				//赋值 
				OLink Node3 = (OLink)malloc(sizeof(OLNode));
				Node3 -> elem = Node1 -> elem;
				Node3 -> row = Node1 -> row;
				Node3 -> col = Node1 -> col;
				
				//插入 
				InsertElem(Node3,out);
                out.NumSum++;
                
                //移动指针 
                Node1 = Node1->right;
            }
		}
	}
	cout << "相减后的矩阵为：\n" << endl;
	PrintSMatrix(out);
}

/*   *************************************************************************  */
 
/*                        14. 两个矩阵相乘                                      */

void MultiplyMatrix(CrossList &M,CrossList &N, CrossList &out){

	//判断矩阵是否满足相乘条件
	if(M.ColSum != N.rowSum){
		cout << "两个矩阵不满足相乘条件 \n" << endl;
		return;
	}
	//对out矩阵进行初始化
	out.rowSum = M.rowSum;
	out.ColSum = N.ColSum;
	out.NumSum = 0;
	InitSMatrix(out);

	//进行相乘

	//行列遍历
	for(int row = 1; row <= out.rowSum; row++){
		for(int col = 1; col <= out.ColSum; col++){
			int elem = 0;
			OLink Node1 = M.rhead[row];
			OLink Node2 = N.chead[col];

			//对M的行，N的列进行遍历
			for(; Node1; Node1 = Node1 -> right){
				for(; Node2 && Node2 -> row <= Node1 -> col; Node2 = Node2 -> down){ 
					if(Node2 -> row == Node1 -> col){//执行相乘
						elem = elem + Node1-> elem * Node2 -> elem;
						break;
					}
				}
			}

			//满足条件插入矩阵
			if(elem){
				out.NumSum++;
                OLink newnode = (OLink)malloc(sizeof(OLNode));
                newnode -> row = row;
                newnode -> col = col;
                newnode -> elem = elem;
                InsertElem(newnode, out);
			}
		}
	}
	cout << "相乘后的矩阵为：\n" << endl;
	PrintSMatrix(out);
}

/*   *************************************************************************  */

/*                        15. 矩阵转置                                   	    */

void TransposeSMatrix(CrossList &M, CrossList &out){

	//out对M进行复制一份
	CopySMatrix(M, out);

	//进行转置
	for(int row = 1; row <= out.rowSum; row++){
		OLink rowNode = out.rhead[row];
		while(rowNode){
			//当结点不为空时，进行指针和下标的交换
			OLink nextRightNode = rowNode -> right;
			
				//下标更换
			int row = rowNode -> row;
			rowNode -> row = rowNode -> col;
			rowNode -> col = row;
				//指针交换
			OLink down = rowNode -> down;
			rowNode -> down = rowNode -> right;
			rowNode -> right = down;
				//对下一个进行判断
			rowNode = nextRightNode;
		}
	}

	//进行转置后的交换
	int rowSum = out.rowSum;
	int ColSum = out.ColSum;
	OLink* rhead = out.rhead;
	out.ColSum = rowSum;
	out.rowSum = ColSum;
	out.rhead = out.chead;
	out.chead = rhead;
    cout << "转置后的矩阵为：\n" << endl;
	PrintSMatrix(out);
	
}

/*   *************************************************************************  */

/*                        16. 矩阵求最值                                    	*/

void findMaxOrMin(CrossList &M){
	int min = INT_MAX;
	int max = INT_MIN;

	//矩阵最大值
    for(int i = 1; i <= M.rowSum; i++){
        OLink p = M.rhead[i];
        while(p != NULL){
            if(max < p -> elem)
             max = p -> elem;
            p = p -> right;
        }
    }
	
	//矩阵最小值
	for(int i = 1; i <= M.rowSum; i++){
        OLink p = M.rhead[i];
        while(p != NULL){
            if(min > p -> elem)
             min = p -> elem;
            p = p -> right;
        }
    }
    cout << "矩阵的最大值为: \n" <<  max << endl;
    cout << "矩阵的最小值为: \n" << min << endl;
}

/*   *************************************************************************  */

/*                        17. 复制矩阵                                          */

void CopySMatrix(CrossList &M, CrossList &out){

	//对out进行初始化
	out.NumSum = M.NumSum;
	out.ColSum = M.ColSum;
	out.rowSum = M.rowSum;
	InitSMatrix(out);
	
	//复制
	for (int row = 1; row <= M.rowSum; row++) 
	{
		OLink rowNode = M.rhead[row];
		while(rowNode)
		{
			OLink newnode = (OLink)malloc(sizeof(OLNode));
			newnode -> row = rowNode -> row;
			newnode -> col = rowNode -> col;
			newnode -> elem = rowNode -> elem;
			InsertElem(newnode, out);
			rowNode = rowNode -> right;
		}
	}
	// printf("复制得到的矩阵为：\n");
	// PrintSMatrix(out);
}

/*   *************************************************************************  */

/*                        18. 从文件中读取                                      */

void ReadFromFile(CrossList &M){
	FILE* fpread;
	char str[100];
	int count=0;
	int num[1000];
	cout << "请输入文件名称:\n" << endl;
	cin >> str;
	fpread = fopen(str, "r");
	if (fpread == NULL)
	{
		cout << "不存在该文件！\n" << endl;
		return ;
	}

	//读取数据
	while(1) { 
		int ch = fgetc(fpread);
		if(ch == EOF)
		 break;
		else
		 fscanf(fpread, "%d", &num[count++]);
	}
	fclose(fpread);

	//初始化矩阵并输出
	M.rowSum = num[0];
	M.ColSum = num[1];
	M.NumSum = num[2];
	InitSMatrix(M);
	cout << num[0] << M.ColSum << M.NumSum << endl;
	for(int i = 3; i < count; i+=3){
		OLink newNode = (OLink)malloc(sizeof(OLNode));
        newNode -> row = num[i];
        newNode -> col = num[i+1];
        newNode -> elem = num[i+2];
        InsertElem(newNode,M);
	}

	//显示矩阵
	cout << "文件中读取的矩阵为：\n" << endl;
	PrintSMatrix(M);
}

/*   *************************************************************************  */

/*                        19. 把矩阵写入文件                                    */

void WriteToFile(CrossList &M){
    char str[1024];
    cout << "请输入需要保存到的文件名:\n" << endl;
	cin >> str;
    FILE* fid = fopen(str, "wt");
	if (fid == NULL)
	{
		cout << "文件不存在！\n" << endl;
		return;
	}

	//写入文件
    fprintf(fid," ");
    fprintf(fid,"%d ",M.rowSum);
    fprintf(fid,"%d ",M.ColSum);
    fprintf(fid,"%d\n",M.NumSum);

    for(int i = 1; i <= M.rowSum; i++){
        OLink Node = M.rhead[i];
        while(Node != NULL){
            fprintf(fid,"%d ",Node -> row);
            fprintf(fid,"%d ",Node -> col);
            fprintf(fid,"%d\n",Node -> elem);
            Node =  Node -> right;
        }
    }
    fclose(fid);
    cout << "文件写入成功！\n" << endl;
}

/*   *************************************************************************  */

/*                        20. 哈希查找函数(用于手动写入矩阵)                    */

CrossList HashFind(char name[10]){
    struct HashCross *tmp = NULL;
    HASH_FIND_STR(cross,name,tmp);
    if(tmp == NULL){
        cout << "该矩阵不存在，系统已经自动为您生成该名称的矩阵\n" << endl;
        CrossList M;
        tmp = (struct HashCross *)malloc(sizeof(struct HashCross));
        strcpy(tmp -> name, name);
        CreateMatrix(M);
        tmp -> crosslist = M;
        HASH_ADD_STR(cross,name,tmp);
        if(cross == NULL) cout << "hash还是空" << endl; 
        return M;
    }
    else{
        cout << "该矩阵存在！\n" << endl;
        return tmp -> crosslist;
    }
}

/*   *************************************************************************  */

/*                        21. 哈希查找函数(用于读文件写入矩阵)                  */

CrossList HashFind2(char name[10]){
    struct HashCross *tmp = NULL;
    HASH_FIND_STR(cross,name,tmp);
    if(tmp == NULL){
    	cout << "该矩阵不存在，系统已经自动为您生成该名称的矩阵\n" << endl;
        tmp = (struct HashCross *)malloc(sizeof(struct HashCross));
        strcpy(tmp -> name, name);
        CrossList M;
        ReadFromFile(M);
        tmp -> crosslist = M;
        HASH_ADD_STR(cross,name,tmp);
        return M;
    }
    else{
    	cout << "该矩阵存在！\n" << endl;
        return tmp -> crosslist;
    }
}

/*   *************************************************************************  */

/*                        21. 获取矩阵名（没有的话，自动创建矩阵）              */

CrossList getCrossList(){
    CrossList M;
    cout << "请输入需要操作的矩阵名称:（长度小于10）\n" << endl;
    char name[10];
    cin >> name;
    M = HashFind(name);
    return M;
}

/*   *************************************************************************  */

/*                       22.主函数调用                                          */


int main(){
	menu();
    return 0;
}

/*   ************************************************************************** */

收起

展开全文

c语言数据结构链表 hash

十字链表实现稀疏矩阵的各种功能
2021-11-19 09:43:47

十字链表实现稀疏矩阵的加法、减法、乘法、转置、求最值、插入、查看、删除等基本功能，菜单栏采用hash表存储稀疏矩阵，给每个矩阵存储一个名字，hash函数进行寻找。

收起
十字链表稀疏矩阵相加
2018-11-11 16:48:08

数据结构课程设计 十字链表稀疏矩阵相加本课程设计主要实现在十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行相加，操作，最后输出运算后的结果。稀疏矩阵采用十字链表表示，并在不同的存储结构下，求两个具有...

收起
十字链表实现稀疏矩阵的加法
2013-12-10 15:18:22

十字链表实现稀疏矩阵的加法

收起

数据结构 - 十字链表之稀疏矩阵的存储

千次阅读 多人点赞 2019-02-19 14:51:33

当数组中非零元素非常少时，我们可以称之为稀疏矩阵。为了减少空间的浪费，在存储稀疏矩阵的时候，我们对它进行压缩存储，即指存储非零信息。一、数组的顺序存储在存储稀疏矩阵的时候，除了存储非零元素的值，还...

当数组中非零元素非常少时，我们可以称之为稀疏矩阵。为了减少空间的浪费，在存储稀疏矩阵的时候，我们对它进行压缩存储，即指存储非零信息。

一、数组的顺序存储

在存储稀疏矩阵的时候，除了存储非零元素的值，还需要存储其行列号i和j，故每个非零元素要用一个三元组（i, j, v）来描述。因为要与矩阵的对应关系，我们还需要在三元组表中增设非零元素的个数和矩阵行列大小。

那么，稀疏矩阵的数组表达如下所示。

struct CrossNode{ //三元组结构
    int i, j; //行列号
    ElementType value; //元素值
    CrossNode(int idx, int jdx, ElementType val):
        i(idx), j(jdx), value(val){}
};

class CrossList{ //三元组表结构
    int row, col, count; //行列数、非零元素个数
    CrossNode data[maxnum];
}

二、十字链表

当三元组按行列序组成一个线性表，如果数组的非零元素个数较大，元素定位的效率就会比较低下。为此，我们可以采用行列两个方向交叉的十字链表，来表示稀疏矩阵。

在这里插入图片描述

每个非零节点不仅要存放(i, j, e)，还要存放它横向的下一个结点的地址以及纵向的下一个结点的地址，形成一个类似十字形的链表的结构，具体定义如下：

//节点结构
struct CrossNode{
	int i, j, value;
	CrossNode *right, *down;
	CrossNode(int idx, int jdx, int val) : i(idx), j(jdx), value(val), right(NULL), down(NULL){}
};

typedef struct CrossNode CLNode, *CrossLine;

//十字链表
class CrossList{
public:
	CrossList(){}
	CrossList(vector< vector<int> > &arr);
	//...
private:
   //...
	int row, col, count;
	CrossLine *rowHead, *colHead;
};

这里需要注意的是，十字链表结构里的rowHead和colHead的类型是CorssLine *，也就是CrossNode * * 。

如果把它们设置为CrossNode *类型，那么后期元素的定位和访问需要行和列的遍历，效率不高。

完整程序

#include <iostream>
#include <vector>
using namespace std;

//Node Denifition
struct CrossNode{
	int i, j, value;
	CrossNode *right, *down;
	CrossNode(int idx, int jdx, int val) : i(idx), j(jdx), value(val), right(NULL), down(NULL){}
};

typedef struct CrossNode CLNode, *CrossLine;


//Orthogonal List Definition
class CrossList{
public:
	CrossList(){}
	CrossList(vector< vector<int> > &arr);
	void Insert(CLNode* &node);
	void print();
	int getCount();
private:
	void InsertIntoRow(CLNode* &node);
	void InsertIntoColumn(CLNode* &node);
	void CreateSparseMatrix(vector< vector<int> > &arr);

	int row, col, count;
	CrossLine *rowHead, *colHead;
};

//Constructor
CrossList::CrossList(vector< vector<int> > &arr){
	if(arr.empty()) return;
	row = arr.size();
	col = arr[0].size();
	rowHead = new CrossLine[row];
	for(int m = 0; m < row; ++m)
		rowHead[m] = NULL;
	colHead = new CrossLine[col];
	for(int n = 0; n < col; ++n)
		colHead[n] = NULL;
	CreateSparseMatrix(arr);
}

//Insertion
void CrossList::Insert(CLNode* &node){
	InsertIntoRow(node);
	InsertIntoColumn(node);
}

//Update rowHead when insertion
void CrossList::InsertIntoRow(CLNode* &node){
	int m = node->i;
	if(!rowHead[m]){
		rowHead[m] = node;
	}
	
	else{
		if(rowHead[m]->j > node->j){
			node->right = rowHead[m];
			rowHead[m] = node;
		}
		else{
			CLNode* cur = rowHead[m]; 
			while(cur->right && cur->right->j < node->j){
				cur = cur->right;
			}
			if(!cur->right){
				cur->right = node;
			}
			else{
				node->right = cur->right;
				cur->right = node;
			}
		}
	}
}

//Update colHead when insertion
void CrossList::InsertIntoColumn(CLNode* &node){
	int n = node->j;
	if(!colHead[n]){
		colHead[n] = node;
	}
	else{
		if(colHead[n]->i < node->i){
			node->down = colHead[n];
			colHead[n] = node;
		}
		else{
			CrossLine cur = colHead[n]; //CLNode *
			while(cur->down && cur->down->i < node->i){
				cur = cur->down;
			}
			if(!cur->down){
				cur->down = node;
			}
			else{
				node->down = cur->down;
				cur->down = node;
			}
		}
	}
}

//Store sparse matrix
void CrossList::CreateSparseMatrix(vector< vector<int> > &arr){
	for(int m = 0; m < row; ++m){
		for(int n = 0; n < col; ++n){
			if(arr[m][n] != 0){
				CLNode *newNode = new CLNode(m, n, arr[m][n]);
				Insert(newNode);
				++count;
			}
		}
	}
}

//Print sparse matrix
void CrossList::print(){
	for(int m = 0; m < row; ++m){
		CrossLine cur = rowHead[m];
		int n = 0;
		while(n < col){
			if(cur && n == cur->j){
				cout << cur->value << " ";
				cur = cur->right;
			}
			else cout << "0 ";
			++n;
		}
		cout << endl;
	}
}

int CrossList::getCount(){ 
	return count; 
}

//Test case
int main(){
	vector< vector<int> > arr = {
		{0,  18, 0,  0,  0,  0},
		{0,  0,  67, 0,  0,  0},
		{0,  0,  0,  0,  0,  41},
		{0,  0,  47, 62, 0,  0},
		{0,  0,  0,  0,  0,  35}
	};
	CrossList testList(arr);
	testList.print();
}

收起

展开全文

数组

38、稀疏矩阵的十字链表表示和创建
千次阅读 2020-02-24 12:09:51

用三元数组的结构来表示稀疏矩阵，在某些情况下可以节省存储空间并加快运算速度。但在运算过程中，若稀疏矩阵的非零元素位置发生...十字链表适用于操作过程中非零元素的个数及元素位置变动频繁的稀疏矩阵。一、...

收起
数据结构学习(C )稀疏矩阵(十字链表1)
2020-12-21 21:53:32

CSDN先说说什么叫稀疏矩阵。你说，这个问题很简单吗，那你一定不知道中国学术界的嘴皮子仗，对一个字眼的“抠”将会导致两种相反的结论。这是清华2000年的一道考研题：“表示一个有1000个顶点，1000条边的有向图的...

收起
看数据结构写代码(21) 稀疏矩阵（十字链表方式）
2021-01-13 05:15:23

比如在销毁十字链表时。多次释放节点空间，造成_CrtIsValidHeapPointer(pUserData) 异常。当使用malloc 分配一个空间时，会将这个空间的起始地址和长度加到一个链表中去。free(p)的时候,会从链表里查找是否有...

收起
稀疏矩阵十字链表
2015-10-05 15:19:53

稀疏矩阵十字链表

收起
数据结构之十字链表——稀疏矩阵的链式存储及加法运算
2021-01-16 02:33:32

该楼层疑似违规已被系统折叠隐藏此楼查看此楼以下简单实现了数据结构中的十字链表(Java实现)：代码为添加(add)方法及求和(sum)方法，其它方法后续有时间再添加，最下面有测试方法CrossList交叉链表实现代码如下：...

收起
十字链表存储稀疏矩阵算法（乘法）
2010-04-27 16:55:51

十字链表存储稀疏矩阵算法，实现两个矩阵的乘法运算

收起
数据结构实验报告4-数组与广义表-基于十字链表的稀疏矩阵转置-实验内容及要求.docx
2019-07-06 20:45:49

编写程序，从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构。其中，m、n分别表示矩阵行数和列数；i, j为非零元素行号和列号。编写算法，实现矩阵转置，输出转置后的三元组到...

收起
十字链表法，十字链表压缩存储稀疏矩阵详解
2021-05-22 14:55:08

对于压缩存储稀疏矩阵，无论是使用图 1 十字链表示意图可以看到，使用十字链表压缩存储稀疏矩阵时，矩阵中的各行各列都各用一各链表存储，与此同时，所有行链表的表头存储到一个数组(rhead)，所有列链表的表头存储到...

收起
十字链表实现稀疏矩阵系列2----输出十字链表
2021-11-22 21:22:05

十字链表实现稀疏矩阵系列2----输出十字链表

收起

数据结构 c++ c语言链表
数据结构-十字链表稀疏矩阵基本操作代码实现
2022-01-08 00:46:23

#include <iostream> #include <iomanip> using namespace std; typedef int ElemType;...//该十字链表结点的右指针与下指针 }OLNode,*OLink;//十字链表结点 typedef struct { OLin.

收起

数据结构链表
十字链表48稀疏矩阵的压缩存储数据结构Java语言描述.PPT
2020-12-21 21:53:29

十字链表48稀疏矩阵的压缩存储数据结构Java语言描述1) 尽可能少存或不存零值元素；解决问题的原则: 2) 尽可能减少没有实际意义的运算； 3) 操作方便。即：能尽可能快地找到与下标值(i，j) 对应的元素，能尽可能快...

收起
稀疏矩阵的十字链表表示方法：矩阵加减乘法运算、矩阵转置运算、矩阵项的插入、矩阵行列链表的排序
2014-06-08 15:39:45

稀疏矩阵的十字链表表示方法：矩阵加减乘法运算、矩阵转置运算、矩阵项的插入、矩阵行列链表的排序

收起
稀疏矩阵十字链表存储
2012-12-26 20:45:45

资源有限，请谅解。原创作品，不喜勿喷。若有类似资源，请君主动共享。

收起
（转载）十字链表法，十字链表压缩存储稀疏矩阵详解
2021-02-25 19:05:45

对于压缩存储稀疏矩阵，无论是使用三元组顺序表，还是使用行逻辑链接的顺序表，归根结底是使用数组存储稀疏矩阵。介于数组 “不利于插入和删除数据” 的特点，以上两种压缩存储方式都不适合解决类似 “向矩阵中添加...

收起

链表数据结构算法 c语言
请大侠帮忙，怎么利用十字链表存储稀疏矩阵并进行完整输出
2021-05-23 08:31:12

该楼层疑似违规已被系统折叠隐藏此楼查看此楼我利用三元组进行了输出，却没有输出零元。求大侠帮忙！...// 稀疏矩阵的十字链表存储表示typedef struct OLNode{int i,j; // 该非零元的行和列下标int ...

收起
数据结构课程设计报告 (十字链表实现稀疏矩阵的加法)
2021-01-16 02:33:31

一、问题描述十字链表实现稀疏矩阵的加法1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个...

收起
十字链表在稀疏矩阵的应用
2010-10-28 10:04:47

稀疏矩阵的应用（十字链表）一、设计要求 1．问题描述设计程序用十字链表实现稀疏矩阵的加、乘、转置。 2．需求分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行...

收起
稀疏矩阵的存储和乘法操作
2021-01-13 05:15:16

一 稀疏矩阵的存储1.三元组顺序表三元组表示法就是在存储非零元的同时...所以三元组的逻辑结构如下：//————稀疏矩阵的三元组表示法————//#define MAX_SIZE 1500 //表示稀疏矩阵的非零元素的最大个数class T...

收起
【数据结构】稀疏矩阵的链式存储（十字链表）
千次阅读 2022-03-13 16:57:36

稀疏矩阵的十字链表表示：十字链表中结点的结构：创建稀疏矩阵的十字链表表示： 稀疏矩阵十字链表的查找： 稀疏矩阵的十字链表表示：每一行的非零元素构成一个带表头的环形链表每一列的非零元素构成一个...

收起

数据结构

十字链表存储稀疏矩阵

十字链表实现稀疏矩阵的乘法

基于十字链表存储的稀疏矩阵的转置

十字链表实现稀疏矩阵，包含十二大功能

题目：

实现：

技术难点1：uthash存储十字链表矩阵，给每个矩阵进行命名，以名字作为key，十字链表作为value,实现相对自动化的功能；（需要自己在github上找到相关资源）

技术难点2：十字链表矩阵的插入函数是整个代码的核心，需要对十字链表的存储结构比较熟悉

技术难点3：十字链表矩阵的相加函数，针对两个矩阵不同对应的情况进行相加

代码前面的声明：

具体每个功能的函数：

十字链表实现稀疏矩阵的各种功能

十字链表稀疏矩阵相加

十字链表实现稀疏矩阵的加法

数据结构 - 十字链表之稀疏矩阵的存储

一、数组的顺序存储

二、十字链表

完整程序

38、稀疏矩阵的十字链表表示和创建

数据结构学习(C )稀疏矩阵(十字链表1)

看数据结构写代码(21) 稀疏矩阵（十字链表方式）

稀疏矩阵十字链表

数据结构之十字链表——稀疏矩阵的链式存储及加法运算

十字链表存储稀疏矩阵算法（乘法）

数据结构实验报告4-数组与广义表-基于十字链表的稀疏矩阵转置-实验内容及要求.docx

十字链表法，十字链表压缩存储稀疏矩阵详解

十字链表实现稀疏矩阵系列2----输出十字链表

数据结构-十字链表稀疏矩阵基本操作代码实现

十字链表48稀疏矩阵的压缩存储数据结构Java语言描述.PPT

稀疏矩阵的十字链表表示方法：矩阵加减乘法运算、矩阵转置运算、矩阵项的插入、矩阵行列链表的排序

稀疏矩阵十字链表存储

（转载）十字链表法，十字链表压缩存储稀疏矩阵详解

请大侠帮忙，怎么利用十字链表存储稀疏矩阵并进行完整输出

数据结构课程设计报告 (十字链表实现稀疏矩阵的加法)

十字链表在稀疏矩阵的应用

稀疏矩阵的存储和乘法操作

【数据结构】稀疏矩阵的链式存储（十字链表）

十字链表表示稀疏矩阵

十字链表存储稀疏矩阵

十字链表实现稀疏矩阵的乘法

基于十字链表存储的稀疏矩阵的转置

十字链表实现稀疏矩阵，包含十二大功能

题目：

实现：

技术难点1：uthash存储十字链表矩阵，给每个矩阵进行命名，以名字作为key，十字链表作为value,实现相对自动化的功能；（需要自己在github上找到相关资源）

技术难点2：十字链表矩阵的插入函数是整个代码的核心，需要对十字链表的存储结构比较熟悉

技术难点3：十字链表矩阵的相加函数，针对两个矩阵不同对应的情况进行相加

代码前面的声明：

具体每个功能的函数：

十字链表实现稀疏矩阵的各种功能

十字链表稀疏矩阵相加

十字链表实现稀疏矩阵的加法

数据结构 - 十字链表之稀疏矩阵的存储

一、数组的顺序存储

二、十字链表

完整程序

38、稀疏矩阵的十字链表表示和创建

数据结构学习(C )稀疏矩阵(十字链表1)

看数据结构写代码(21) 稀疏矩阵（十字链表方式）

稀疏矩阵十字链表

数据结构之十字链表——稀疏矩阵的链式存储及加法运算

十字链表存储稀疏矩阵算法（乘法）

数据结构实验报告4-数组与广义表-基于十字链表的稀疏矩阵转置-实验内容及要求.docx

十字链表法，十字链表压缩存储稀疏矩阵详解

十字链表实现稀疏矩阵系列2----输出十字链表

数据结构-十字链表稀疏矩阵基本操作代码实现

十字链表48稀疏矩阵的压缩存储数据结构Java语言描述.PPT

稀疏矩阵的十字链表表示方法：矩阵加减乘法运算、矩阵转置运算、矩阵项的插入、矩阵行列链表的排序

稀疏矩阵十字链表存储

（转载）十字链表法，十字链表压缩存储稀疏矩阵详解

请大侠帮忙，怎么利用十字链表存储稀疏矩阵并进行完整输出

数据结构课程设计 报告 (十字链表实现稀疏矩阵的加法)

十字链表在稀疏矩阵的应用

稀疏矩阵的存储和乘法操作

【数据结构】稀疏矩阵的链式存储（十字链表）

十字链表表示稀疏矩阵

数据结构课程设计报告 (十字链表实现稀疏矩阵的加法)