精华内容
下载资源
问答
  • 对于压缩存储稀疏矩阵,无论是使用图 1 十字链表示意图可以看到,使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到...

    对于压缩存储稀疏矩阵,无论是使用

    3f8036b7ebfab3106d783e0471975c69.png

    图 1 十字链表示意图

    可以看到,使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到另一个数组(chead)中。

    因此,各个链表中节点的结构应如图 2 所示:

    ca1b3fe64d3a7ab0e74ca2f7f15dfc6f.png

    图 2 十字链表的节点结构

    两个指针域分别用于链接所在行的下一个元素以及所在列的下一个元素。

    链表中节点的 C 语言代码表示应为:

    typedef struct OLNode{

    int i,j;//元素的行标和列标

    int data;//元素的值

    struct OLNode * right,*down;//两个指针域

    }OLNode;

    同时,表示十字链表结构的 C 语言代码应为:

    #include

    #include

    typedef struct OLNode

    {

    int i, j, e; //矩阵三元组i代表行 j代表列 e代表当前位置的数据

    struct OLNode *right, *down; //指针域 右指针 下指针

    }OLNode, *OLink;

    typedef struct

    {

    OLink *rhead, *chead; //行和列链表头指针

    int mu, nu, tu; //矩阵的行数,列数和非零元的个数

    }CrossList;

    CrossList CreateMatrix_OL(CrossList M);

    void display(CrossList M);

    int main()

    {

    CrossList M;

    M.rhead = NULL;

    M.chead = NULL;

    M = CreateMatrix_OL(M);

    printf("输出矩阵M:\n");

    display(M);

    return 0;

    }

    CrossList CreateMatrix_OL(CrossList M)

    {

    int m, n, t;

    int i, j, e;

    OLNode *p, *q;

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

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

    M.mu = m;

    M.nu = n;

    M.tu = t;

    if (!(M.rhead = (OLink*)malloc((m + 1) * sizeof(OLink))) || !(M.chead = (OLink*)malloc((n + 1) * sizeof(OLink))))

    {

    printf("初始化矩阵失败");

    exit(0);

    }

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

    {

    M.rhead[i] = NULL;

    }

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

    {

    M.chead[j] = NULL;

    }

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

    if (!(p = (OLNode*)malloc(sizeof(OLNode))))

    {

    printf("初始化三元组失败");

    exit(0);

    }

    p->i = i;

    p->j = j;

    p->e = e;

    //链接到行的指定位置

    if (NULL == M.rhead[i] || 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 (NULL == M.chead[j] || 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;

    }

    }

    return M;

    }

    void display(CrossList M) {

    for (int i = 1; i <= M.nu; i++)

    {

    if (NULL != M.chead[i])

    {

    OLink p = M.chead[i];

    while (NULL != p)

    {

    printf("%d\t%d\t%d\n", p->i, p->j, p->e);

    p = p->down;

    }

    }

    }

    }

    运行结果:

    输入矩阵的行数、列数和非0元素个数:3 3 3

    2 2 3

    2 3 4

    3 2 5

    0 0 0

    输出矩阵M:

    2       2       3

    3       2       5

    2       3       4

    展开全文
  • 数据结构课程设计 十字链表稀疏矩阵相加 本课程设计主要实现在十字链表存储结构下输入稀疏矩阵,并对稀疏矩阵进行相加,操作,最后输出运算后的结果。稀疏矩阵采用十字链表表示,并在不同的存储结构下,求两个具有...
  • #ifndef CCROSS_SPARSE_H #define CCROSS_SPARSE_H /****************************************************************.../* 以下是C++ 矩阵 类, 十字链表; /**************************************************
    #ifndef CCROSS_SPARSE_H
    #define CCROSS_SPARSE_H
    
    /************************************************************************/  
    /* 以下是C++ 矩阵 类, 十字链表; 
    /************************************************************************/  
    
    //三元组类
    template<class Elemplent>
    class CTriple
    {
    public:
    	int rows,cols;
    	CTriple(int r,int c,Elemplent tempelemplent);
    	CTriple();
    	Elemplent value;
    };
    
    //构造函数
    template <class Elemplent>
    CTriple<Elemplent>::CTriple()
    {
    
    }
    
    //构造函数
    template<class Elemplent>
    CTriple<Elemplent>::CTriple(int r,int c,Elemplent tempelemplent)
    {
    	rows =r;
    	cols =c;
    	value = tempelemplent;
    }
    
    
    //三元组节点定义
    template<class Elemplent>
    class CCrossNode
    {
    public:
    	CTriple<Elemplent> nodectriple;
    	CCrossNode<Elemplent> *right,*down;
    
    	CCrossNode();
    	CCrossNode(const CTriple<Elemplent> & tempctriple,
    		CCrossNode<Elemplent>* tempright = NULL,CCrossNode<Elemplent>*tempdown = NULL);
    };
    
    //构造函数
    template <class Elemplent>
    CCrossNode<Elemplent>::CCrossNode()
    {
    	right= NULL;
    	down = NULL;
    }
    
    //构造函数
    template <class Elemplent>
    CCrossNode<Elemplent>::CCrossNode(const CTriple<Elemplent> & tempctriple, CCrossNode<Elemplent>* tempright /* = NULL */,CCrossNode<Elemplent>*tempdown /* = NULL */)
    {
    	nodectriple.cols = tempctriple.cols;
    	nodectriple.rows = tempctriple.rows;
    	nodectriple.value = tempctriple.value;
    	right = tempright;
    	down = tempdown;
    }
    
    //十字链表类定义
    template<class Elemplent>
    class CCrossSparseMatrix
    {
    protected:
    	int row,col,num;
    	CCrossNode<Elemplent> **rightHead,**downHead;
    public:
    	CCrossSparseMatrix(int temprow =111,int tempcol =111);
    	CCrossSparseMatrix(const CCrossSparseMatrix<Elemplent> & tempcopy);
    	CCrossSparseMatrix<Elemplent> &operator = (const CCrossSparseMatrix<Elemplent> & tempcopy);
    	~CCrossSparseMatrix();
    	void DestroyAll();
    public:
    	void DistroyMatrix();
    	bool InsertNode(const CTriple<Elemplent> &temptriple);
    	int Getrow()const;
    	int Getcol()const;
    	int Getnum()const;
    	bool SetElemplent(int r,int c,const Elemplent & tempelemplent);
    	bool GetElemplent(int r,int c,Elemplent &tempeleplent);
    	
    
    
    };
    
    //构造函数
    template<class Elemplent>
    CCrossSparseMatrix<Elemplent>::CCrossSparseMatrix()
    {
    	row = 0;
    	col = 0;
    	num = 0;
    	rightHead = NULL;
    	downHead = NULL;
    }
    
    //构造函数
    template<class Elemplent>
    CCrossSparseMatrix<Elemplent>::CCrossSparseMatrix(int temprow /* =111 */,int tempcol /* =111 */)
    {
    	row = temprow;
    	col = tempcol;
    	num = 0;
    	//行列的两个指针数组,用到二级指针
    	rightHead =new CCrossNode<Elemplent> *[row+1];
    	downHead = new CCrossNode<Elemplent> *[col+1];
    	//初始化
    	for (int i = 1;i<=row;i++)
    	{
    		rightHead[i] = NULL;
    	}
    
    	for (int j = 1;j<=col ;j++)
    	{
    		downHead[i]=NULL;
    	}
    }
    
    //销毁所有节点,析构函数用到
    template <class Elemplent>
    void CCrossSparseMatrix<Elemplent>::DestroyAll()
    {
    	int i;
    	for (i = 1;i<row;i++)
    	{
    		if (rightHead[i] !=NULL)
    		{
    			CCrossNode<Elemplent> *ptr = rightHead[i];
    			rightHead[i] = ptr->right;
    			delete ptr;
    		}
    	}
    	delete []rightHead;
    	delete []downHead;
    }
    
    //析构函数
    template <class Elemplent>
    CCrossSparseMatrix::~CCrossSparseMatrix()
    {
    	DestroyAll();
    }
    
    //得到列数
    template <class Elemplent>
    int CCrossSparseMatrix<Elemplent>::Getcol()const
    {
    	return col;
    }
    
    //得到行数
    template <class Elemplent>
    int CCrossSparseMatrix<Elemplent>::Getrow()const
    {
    	return row;
    }
    
    //得到非零元总数
    template <class Elemplent>
    int CCrossSparseMatrix<Elemplent>::Getnum()const
    {
    	return num;
    }
    
    //设置元素值
    template <class Elemplent>
    bool CCrossSparseMatrix<Elemplent>::SetElemplent(int r,int c,const Elemplent &tempeleplent)
    {
    	if (r>row || c>col || c<1 || r <1)
    	{
    		return false;
    	}
    
    	CTriple<Elemplent> e(r,c,tempeleplent);
    	CCrossNode<Elemplent> *preptr,*ptr;
    	CCrossNode<Elemplent> *newptr = new CCrossNode<Elemplent>(e);
    	//如果在列数的开始处
    	if (rightHead[r] == NULL || c<rightHead[r]->nodectriple.cols )
    	{
    		newptr->right = rightHead[r];
    		rightHead[r] = newptr;
    	}
    	else
    	{
    		preptr = NULL; ptr = rightHead[r];
    		//往下遍历
    		while(ptr!=NULL && ptr->nodectriple.cols < c)
    		{
    			preptr = ptr; ptr=ptr->right ;
    		}
    		if (ptr !=NULL && ptr->nodectriple.cols == c&& ptr->nodectriple.rows = r)
    		{
    			//如果设置元素不为空,赋值
    			if (tempeleplent  != 0)
    			{
    				ptr->nodectriple.value = tempeleplent;
    				//释放空间,前面定义的,用不到
    				delete newptr;
    			}
    			//如果为空,删除节点
    			else
    			{
    				preptr->right = ptr->right;
    				//释放空间,前面定义的,用不到
    				delete newptr;
    			}
    
    		}
    		//查找不到节点,建立一个新节点插进去
    		else
    		{
    			preptr->right = newptr; newptr->right = ptr;
    		}
    	}
    	//是不是在行数的第一个
    	if (downHead[c]==NULL || downHead[c]->nodectriple.rows >=r)
    	{
    		newptr->down = downHead[c];
    		downHead[c] = newptr;
    		num++;
    		return true;
    	}
    	else
    	{
    		preptr =NULL; ptr = downHead[c];
    		//往下遍历
    		while(ptr!=NULL && ptr->nodectriple.cols < c)
    		{
    			preptr = ptr; ptr = ptr->down;
    		}
    		if (ptr !=NULL && ptr->nodectriple.cols = c && ptr->nodectriple.rows = r)
    		{
    			//如果元素之为空,删除节点,非零元--
    			if (tempeleplent == 0)
    			{
    				preptr->down = ptr->down;
    				delete newptr;
    				num--;
    				return true;
    			}
    			//元素不为空,赋值
    			else
    			{
    				ptr->nodectriple.value = tempeleplent;
    				delete newptr;
    				return true;
    			}
    		}
    		//查找不到位置,说明不存在,添加一个节点,非零元++
    		else
    		{
    			preptr->down = newptr;newptr->down = ptr;
    			num++;
    			return true;
    		}
    	}
    	return false;
    
    }
    
    //得到元素值
    template<class Elemplent>
    bool CCrossSparseMatrix<Elemplent>::GetElemplent(int r,int c, Elemplent & tempelemplent)
    {
    	if (r <1 || c<1 ||r>row || c> col )
    	{
    		return false;
    	}
    
    	CCrossNode<Elemplent> * ptr = rightHead[r];
    	//遍历
    	while(ptr !=NULL && ptr->nodectriple.cols <c)
    	{
    		ptr= ptr->right;
    	}
    	//找到
    	if (ptr!=NULL && ptr->nodectriple.cols == c && ptr->nodectriple.rows == r)
    	{
    		tempelemplent = ptr->nodectriple.value;
    		return true;
    	}
    	else 
    	{
    		tempelemplent = 0;
    		return false;	
    	}
    }
    
    //通过三元组,插入,构造函数用到,和设置一个元素差不多,不在注释
    template <class Elemplent>
    bool CCrossSparseMatrix<Elemplent>::InsertNode(const CTriple<Elemplent> &temptriple)
    {
    	if (temptriple.cols>col || temptriple >row || temptriple<1 ||temptriple <1)
    	{
    		return false;
    	}
    	int temprow = temptriple.rows;
    	int tempcol = temptriple.cols;
    	CCrossNode<Elemplent> *preptr,*ptr;
    	CCrossNode<Elemplent> *newptr = new CCrossNode<Elemplent>(temptriple);
    	if (rightHead[temprow] == NULL && rightHead[temprow]->nodectriple.cols >= tempcol)
    	{
    		newptr->right = rightHead[temprow];
    		rightHead[temprow] = newptr;
    	}
    
    	else
    	{
    		preptr = NULL;ptr = rightHead[temprow];
    		while(ptr!=NULL && ptr->nodectriple.cols < tempcol)
    		{
    			preptr = ptr;ptr=ptr->right;
    		}
    		if (ptr!=NULL  && ptr->nodectriple.rows == temprow && ptr->nodectriple.cols == tempcol)
    		{
    			return false;
    		}
    		else
    		{
    			preptr->right = newptr;
    			newptr->right = ptr;
    		}
    	}
    	
    	if (downHead[tempcol] == NULL && downHead[tempcol]->nodectriple.rows > temprow)
    	{
    		newptr->down = downHead[tempcol];
    		downHead[tempcol]->down = newptr;
    		num++;
    		return true;
    	}
    	else
    	{
    		preptr =NULL ;ptr = downHead[tempcol];
    		while(ptr!=NULL && ptr->nodectriple.rows <temprow)
    		{
    			preptr = ptr;ptr = preptr->down;
    		}
    		if (ptr !=NULL && ptr->nodectriple.cols ==tempcol && ptr->nodectriple.rows == temprow)
    		{
    			return false;
    		}
    		else
    		{
    			preptr->down = newptr ; newptr->down = ptr;
    			num++;
    		}
    		
    	}
    }
    
    //赋值构造函数
    template<class Elemplent>
    CCrossSparseMatrix<Elemplent>::CCrossSparseMatrix(const CCrossSparseMatrix<Elemplent> & tempcopy)
    {
    	row = tempcopy.row;
    	col = tempcopy.col;
    	num = 0;
    	rightHead = new CCrossNode<Elemplent> *[row+1];
    	downHead = new CCrossNode<Elemplent> * [col+1];
    	int i;
    	for (i =1;i<=row;i++)
    	{
    		rightHead[i] = NULL;
    	}
    	for (i = 1;i<col;i++)
    	{
    		downHead[i] = NULL;
    	}
    
    	for (i =1;i<row;i++)
    	{
    		for(CCrossNode<Elemplent> * node= tempcopy.rightHead[i];node !=NULL;node =node->right)
    		{
    			//调用
    			InsertNode(node->nodectriple);
    		}
    	}
    
    }
    
    //重载=
    template <class Elemplent>
    CCrossSparseMatrix<Elemplent> & CCrossSparseMatrix<Elemplent>::operator= (const CCrossSparseMatrix<Elemplent> & tempcopy)
    {
    	if (this == tempcopy)
    	{
    		return *this;
    	}
    
    	row = tempcopy.row;
    	col = tempcopy.col;
    	num = 0;
    	downHead = new CCrossNode<Elemplent> *[col+1];
    	rightHead = new CCrossNode<Elemplent> *[row+1];
    	int i;
    	for (i = 1; i<row ;i++)
    	{
    		rightHead[i] = NULL;
    	}
    	for (i = 1;i<col;i++)
    	{
    		downHead[i] =NULL;
    	}
    	for (i =1;i<row;i++)
    	{
    		for (CCrossNode<Elemplent> * node = tempcopy.rightHead[i];node = node->right;)
    		{
    			InsertNode(node->nodectriple);
    		}
    	}
    	return *this;
    }
    
    #endif

    展开全文
  • ./*从行中删除*/ /*还要从列中删除,找*pa 的列前驱结点*/ q= Find_JH ( Ha,pa->col ); /*从列链表的头结点找起*/ while ( q->down->row < pa->row ) q=q->down; q->down=pa->down; free ( pa ); pa=qa; } /*if...

    [c]代码库typedef struct node

    {

    int row, col;

    struct node *down , *right;

    union v_next

    {

    datatype v;

    struct node *next;

    }

    } MNode,*MLink;

    MLink AddMat ( Ha,Hb )

    MLink Ha,Hb;

    {

    Mnode *p,*q,*pa,*pb,*ca,*cb,*qa;

    if ( Ha->row!=Hb->row || Ha->col!=Hb->col ) return NULL;

    ca=Ha->v_next.next; /*ca 初始指向A 矩阵中第一行表头结点*/

    cb=Hb->v_next.next; /*cb 初始指向B 矩阵中第一行表头结点*/

    do

    {

    pa=ca->right; /*pa 指向A 矩阵当前行中第一个结点*/

    qa=ca; /*qa 是pa 的前驱*/

    pb=cb->right; /*pb 指向B 矩阵当前行中第一个结点*/

    while ( pb->col!=0 ) /*当前行没有处理完*/

    {

    if ( pa->col < pb->col && pa->col !=0 ) /*第三种情况*/

    {

    qa=pa;

    pa=pa->right;

    }

    else if ( pa->col > pb->col || pa->col ==0 ) /*第四种情况*/

    {

    p=malloc ( sizeof ( MNode ) );

    p->row=pb->row;

    p->col=pb->col;

    p->v=pb->v;

    p->right=pa;

    qa->right=p; /* 新结点插入*pa 的前面*/

    pa=p;

    /*新结点还要插到列链表的合适位置,先找位置,再插入*/

    q=Find_JH ( Ha,p->col ); /*从列链表的头结点找起*/

    while ( q->down->row!=0 && q->down->rowrow )

    q=q->down;

    p->down=q->down; /*插在*q 的后面*/

    q->down=p;

    pb=pb->right;

    } /* if */

    else /*第一、二种情况*/

    {

    x= pa->v_next.v+ pb->v_next.v;

    if ( x==0 ) /*第二种情况*/

    {

    qa->right=pa->right;

    ./*从行链中删除*/

    /*还要从列链中删除,找*pa 的列前驱结点*/

    q= Find_JH ( Ha,pa->col ); /*从列链表的头结点找起*/

    while ( q->down->row < pa->row )

    q=q->down;

    q->down=pa->down;

    free ( pa );

    pa=qa;

    } /*if (x==0)*/

    else /*第一种情况*/

    {

    pa->v_next.v=x;

    qa=pa;

    }

    pa=pa->right;

    pb=pb->right;

    }

    } /*while*/

    ca=ca->v_next.next; /*ca 指向A 中下一行的表头结点*/

    cb=cb->v_next.next; /*cb 指向B 中下一行的表头结点*/

    }

    while ( ca->row==0 ) /*当还有未处理完的行则继续*/

    return Ha;

    }


    本文来自【C语言中文网】:http://see.xidian.edu.cn/cpp/html/970.html

    694748ed64b9390909c0d88230893790.png

    展开全文
  • 十字链表存储稀疏矩阵,可以起到节省空间的作用。 十字链表作为多重链表的一种,其结点分为两种: 类型1:数据域为另一个单链表的头指针。 类型2:数据域为待存储的数据。 其中,“十字”体现在:每一个存储...

    一、介绍

    用十字链表存储稀疏矩阵,可以起到节省空间的作用。

    十字链表作为多重链表的一种,其结点分为两种:

    类型1:数据域为另一个单链表的头指针。

    类型2:数据域为待存储的数据。

    其中,“十字”体现在:每一个存储数据的节点都属于两个单链表,从而构成十字形。

     

    用十字链表表示的矩阵,有着以下特征:

    1、整体的头指针指向最初的头结点,该头结点一般用于存储矩阵的行数、列数以及其中包含非0元素的数量。

    2、由最初的头结点分别横向、纵向展开两个单链表,这两个链表中的每个结点都为类型1。

    3、这两个链表中的每个结点代表特定的行或列,引出单链表。

    4、每个用于储存矩阵元素的类型2结点都属于某两个类型1结点引出的单链表。由此可标记元素在矩阵中的具体位置。

    二、实现

    .general.h:总声明。

    #ifndef _GEN_H_
        #define _GEN_H_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    typedef unsigned int Cursor;
    #define ERROR 0xABCDEF
    typedef int ElemType;
    
    #endif

    LinkGen.h:十字链表和基本的遍历函数声明。

    #ifndef _LINK_GEN_H_
        #define _LINK_GEN_H_
    #include ".general.h"
    
    /*Structure Declaration*/
    enum Type {HEAD, UNIT, START};
    typedef struct GNode *GPos;
    typedef struct GNode *GLink;
    struct GNode {
        enum Type tag;
        union {
            GLink head;
            struct {
                Cursor row;
                Cursor column;
                ElemType value;
            } unit;
        } region;
        GPos right;
        GPos down;
    };
    
    /*Function Declaration*/
    //向右遍历
    GPos GLocateRight(GLink start, Cursor subs);
    //向下遍历
    GPos GLocateDown(GLink start, Cursor subs);
    
    #endif

    LinkGen.c:函数实现。

    #include "LinkGen.h"
    
    GPos GLocateRight(GLink start, Cursor subs)
    {
        GPos ptr = start;
        for(int i = 0; i < subs; i++) {
            if(!ptr->right)
                return NULL;
            else 
                ptr = ptr->right;
        }
        return ptr;
    }
    
    GPos GLocateDown(GLink start, Cursor subs)
    {
        GPos ptr = start;
        for(int i = 0; i < subs; i++) {
            if(!ptr->down)
                return NULL;
            else 
                ptr = ptr->down;
        }
        return ptr;
    }

    Matrix.h:声明矩阵和相关函数。

    #ifndef _MATRIX_H_
        #define _MATRIX_H_
    #include "LinkGen.h"
    
    /*Structure Declaration*/
    typedef GLink Matrix;
    
    /*Function Declaration*/
    //创建矩阵
    Matrix CreateMatrix(Cursor MaxRow, Cursor MaxCol);
    //插入矩阵中的元素
    bool InsertUnit(Matrix M, ElemType E, Cursor Row, Cursor Column);
    //打印矩阵
    bool PrintMatrix(Matrix M);
    //销毁矩阵
    bool DestroyMatrix(Matrix M);
    
    #endif

    Matrix.c:函数实现。

    #include "Matrix.h"
    
    Matrix CreateMatrix(Cursor MaxRow, Cursor MaxCol)
    {
        if(!MaxRow || !MaxCol)
            return NULL;
        /*Origin Node*/
        Matrix M = (Matrix) malloc(sizeof(struct GNode));
        if(!M)
            exit(EXIT_FAILURE);
        M->tag = START;
        M->region.unit.row = MaxRow;
        M->region.unit.column = MaxCol;
        M->region.unit.value = 0;
        /*Row Node*/
        GPos preR = M;
        for(int i = 0; i < MaxRow; i++) {
            GPos tmp = (GPos) malloc(sizeof(struct GNode));
            if(!tmp)
                exit(EXIT_FAILURE);
            tmp->tag = HEAD;
            tmp->region.head = NULL;
            preR->down = tmp;
            if(preR != M)
                preR->right = NULL;
            preR = preR->down;
        }
        preR->right = NULL;
        /*Column Node*/
        GPos preC = M;
        for(int i = 0; i < MaxCol; i++) {
            GPos tmp = (GPos) malloc(sizeof(struct GNode));
            tmp->tag = HEAD;
            tmp->region.head = NULL;
            preC->right = tmp;
            if(preC != M)
                preC->down = NULL;
            preC = preC->right;
        }
        preC->down = NULL;
        return M;
    }
    
    bool InsertUnit(Matrix M, ElemType E, Cursor Row, Cursor Column)
    {
        if(M->tag != START || Row > M->region.unit.row || Column > M->region.unit.column)
            return false;
        /*Allocation*/
        GPos tmp = (GPos) malloc(sizeof(struct GNode));
        if(!tmp)
            exit(EXIT_FAILURE);
        tmp->tag = UNIT;
        tmp->region.unit.row = Row;
        tmp->region.unit.column = Column;
        tmp->region.unit.value = E;
        /*Row Location*/
        GPos ptrR = GLocateDown(M, Row);
        if(ptrR->tag == HEAD && ptrR->region.head) {
            ptrR = ptrR->region.head;
            while(ptrR->right && !(ptrR->region.unit.column < Column && ptrR->down->region.unit.column > Column)) 
                ptrR = GLocateRight(ptrR, 1);
            tmp->right = ptrR->right;
            ptrR->right = tmp;
        } else {
            if(ptrR->tag != HEAD)
                return false;
            tmp->right = NULL;
            ptrR->region.head = tmp;
        }
        /*Column Location*/
        GPos ptrC = GLocateRight(M, Column);
        if(ptrC->tag == HEAD && ptrC->region.head) {
            ptrC = ptrC->region.head;
            while(ptrC->down && !(ptrC->region.unit.row < Row && ptrC->down->region.unit.row > Row)) 
                ptrC = GLocateDown(ptrC, 1);
            tmp->down = ptrC->down;
            ptrC->down = tmp;
        } else {
            if(ptrC->tag != HEAD)
                return false;
            tmp->down = NULL;
            ptrC->region.head = tmp;
        }
        M->region.unit.value++;
        return true;
    }
    
    bool PrintMatrix(Matrix M)
    {
        if(M->tag != START)
            return false;
        GPos ptrR = M;
        for(int i = 0; i < M->region.unit.row; i++) {
            ptrR = GLocateDown(ptrR, 1);
            if(!ptrR)
                return false;
            GPos ptrC = ptrR->region.head;
            if(!ptrC) {
                //空行填0
                for(int j = 0; j < M->region.unit.column; j++) 
                    printf("%-2d ", 0);
                putchar('\n');
            } else {
                //行前补0
                for(int k = 1; k < ptrC->region.unit.column; k++)
                    printf("%-2d ", 0);
                //行中补0
                while(ptrC->right) {
                    printf("%-2d ", ptrC->region.unit.value);
                    int diff = ptrC->right->region.unit.column - ptrC->region.unit.column;
                    for(int k = 1; k < diff; k++) 
                        printf("%-2d ", 0);
                    putchar('\n');
                }
                //行后补0
                printf("%-2d ", ptrC->region.unit.value);
                int excess = M->region.unit.column - ptrC->region.unit.column;
                for(int k = 0; k < excess; k++)
                    printf("%-2d ", 0);
                putchar('\n');
            }
        }
        return true;
    }

    三、运行实例

    main.c

    #include "Matrix.h"
    
    int main()
    {
        Matrix M = CreateMatrix(4, 3);
        InsertUnit(M, 62, 1, 2);
        InsertUnit(M, 23, 2, 1);
        InsertUnit(M, 18, 3, 2);
        InsertUnit(M, 29, 4, 3);
        PrintMatrix(M);
        return 0;
    }

    输出:

    展开全文
  • 实现了从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构(m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号)和十字链表的转置并将转置后的三元组到另一字符文件中
  •   对于矩阵的存储,如果矩阵的元素呈有明显规律的排列的话,我们一般用一个一维数组对矩阵进行压缩存储;若矩阵中的元素多数为0,只有少数的元素为非0元素时,我们成该矩阵为稀疏矩阵。 我们有矩阵Aij,其中有非0...
  • 我是用vc编译的,绝对可以使用
  • typedef struct OLNode{int i,j; //该非零元的行列下标ElemType e;struct OLNode *right ,*down; //该非零元所在行、列表的后继域} OLNode; *OLink;typedef struct {OLink *rhead , *chead; //行...
  • //稀疏矩阵十字链表存储表示4 typedef structOLNode5 {6 int i,j; //该非零元的行和列下标7 ElemType e; //非零元素值8 struct OLNode *right,*down; //该非零元所在行和列表的后继链域9 }OL...
  • 数据结构稀疏矩阵实验课程设计 /********function definition********/ int init_matrix(crosslist &one) {//initialization one.row_size=0; one.colum_size=0; one.non_zero_amount=0; one.rhead=NULL; one...
  • 十字链表存储和表示稀疏矩阵,并实现如下功能 2.基本要求 初始化:创建十字链表并从文件中读取稀疏矩阵数据(文件数据可以是三元组结构); 在十字链表上设置坐标为(i,j)的位置值为value; 获取坐标为(i...
  • 十字链表常用于表示稀疏矩阵,可视作稀疏矩阵的一种链式表示,因此,这里以稀疏矩阵为背景介绍十字链表。不过,十字链表的应用远不止稀疏矩阵,一切具有正交关系的结构,都可用十字链表存储。1、存储方式(a)稀疏矩阵...
  • 稀疏矩阵十字链表表示方法:矩阵加减乘法运算、矩阵转置运算、矩阵项的插入、矩阵行列链表的排序
  • 应用十字链表存储稀疏矩阵元素,实现矩阵相加
  • 数据结构 - 十字链表之稀疏矩阵的存储

    千次阅读 多人点赞 2019-02-19 14:51:33
    当数组中非零元素非常少时,我们可以称之为稀疏矩阵。为了减少空间的浪费,在存储...因为要与矩阵的对应关系,我们还需要在三元组中增设非零元素的个数和矩阵行列大小。 那么,稀疏矩阵的数组表达如下所示。 st...
  • #include<stdio.h> #include<stdlib.h> #define ElementType int typedef struct GNode *GList; struct GNode{ ... /*Tag作为标志域,区分union中是什么数据:0表示节点是头节点head,1表示
  • 对于压缩存储稀疏矩阵,无论是使用三元组顺序,还是使用行逻辑链接的顺序,归根结底是使用数组存储稀疏矩阵。介于数组 “不利于插入和删除数据” 的特点,以上两种压缩存储方式都不适合解决类似 “向矩阵中添加...
  • 十字链表-稀疏矩阵 C++ 代码 十字链表-稀疏矩阵 C++ 代码
  • 一、问题描述十字链表实现稀疏矩阵的加法1、功能要求:根据用户输入的矩阵,实现稀疏矩阵的求和运算,并输出结果。2、输入要求:矩阵的数据在程序运行的时候由用户提供,先由用户输入稀疏矩阵的行数、列数和非零元个...
  • 38、稀疏矩阵十字链表表示和创建

    千次阅读 2020-02-24 12:09:51
    这时,采用链式存储结构(十字链表)表示三元组的线性表更为恰当。 十字链表(orthogonallist)是稀疏矩阵的另一种存储结构。它是用多重链表来存储稀疏矩阵十字链表适用于操作过程中非零元素的个数及元素位置变动频繁...
  • 十字链表表示矩阵例如,用十字链表法表示矩阵 A ,为:图2 矩阵用十字链表法表示由此可见,采用十字链表表示矩阵时,矩阵的每一行和每一个列都可以看作是一个单独的链表,而之所以能够表示矩阵,是因...
  • 编写程序,从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构。其中,m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号。编写算法,实现矩阵转置,输出转置后的三元组到...
  • 稀疏矩阵十字链表

    2015-10-05 15:19:53
    稀疏矩阵十字链表
  • 十字链表实现矩阵

    2015-04-29 16:46:36
    十字链表实现矩阵的加减乘转置
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼我利用三元组进行了输出,却没有输出零元。求大侠帮忙!...// 稀疏矩阵十字链表存储表示typedef struct OLNode{int i,j; // 该非零元的行和列下标int ...
  • 十字链表表示稀疏矩阵 只是很简单的程序 应该能看懂
  • 采用三元组表示稀疏矩阵,并定义矩阵的加、减、乘运算 正交链表表示稀疏矩阵

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,390
精华内容 1,756
关键字:

十字链表表示矩阵