精华内容
下载资源
问答
  • 我是用vc编译的,绝对可以使用
  • #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

    展开全文
  • 数据结构课程设计 十字链表稀疏矩阵相加 本课程设计主要实现在十字链表存储结构下输入稀疏矩阵,并对稀疏矩阵进行相加,操作,最后输出运算后的结果。稀疏矩阵采用十字链表表示,并在不同的存储结构下,求两个具有...
  • //稀疏矩阵十字链表存储表示4 typedef structOLNode5 {6 int i,j; //该非零元的行和列下标7 ElemType e; //非零元素值8 struct OLNode *right,*down; //该非零元所在行表和列表的后继链域9 }OL...

    1 #include

    2 #include

    3 typedef int ElemType;//稀疏矩阵的十字链表存储表示

    4 typedef structOLNode5 {6 int i,j; //该非零元的行和列下标

    7 ElemType e; //非零元素值

    8 struct OLNode *right,*down; //该非零元所在行表和列表的后继链域

    9 }OLNode, *OLink;10 typedef struct//行和列链表头指针向量基址,由CreatSMatrix_OL()分配

    11 {12 OLink *rhead, *chead;13 int mu, nu, tu; //稀疏矩阵的行数、列数和非零元个数

    14 }CrossList;15 //初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错)

    16 int InitSMatrix(CrossList *M)17 {18 (*M).rhead=(*M).chead=NULL;19 (*M).mu=(*M).nu=(*M).tu=0;20 return 1;21 }22 //销毁稀疏矩阵M

    23 int DestroySMatrix(CrossList *M)24 {25 inti;26 OLNode *p,*q;27

    28 for(i=1;i<=(*M).mu;i++) //按行释放结点

    29 {30 p=*((*M).rhead+i);31 while(p)32 {33 q=p;34 p=p->right;35 free(q);36 }37 }38 free((*M).rhead);39 free((*M).chead);40 (*M).rhead=(*M).chead=NULL;41 (*M).mu=(*M).nu=(*M).tu=0;42 return 1;43 }44 //创建稀疏矩阵M,采用十字链表存储表示。

    45 int CreateSMatrix(CrossList *M)46 {47 inti,j,k,m,n,t;48 ElemType e;49 OLNode *p,*q;50 if((*M).rhead)51 DestroySMatrix(M);52 printf("请输入稀疏矩阵的行数 列数 非零元个数:(space)");53 scanf("%d%d%d",&m,&n,&t);54 (*M).mu=m;55 (*M).nu=n;56 (*M).tu=t;57 //初始化行链表头

    58 (*M).rhead=(OLink*)malloc((m+1)*sizeof(OLink));59 if(!(*M).rhead)60 exit(0);61 //初始化列链表头

    62 (*M).chead=(OLink*)malloc((n+1)*sizeof(OLink));63 if(!(*M).chead)64 exit(0);65 for(k=1;k<=m;k++) //初始化行头指针向量;各行链表为空链表

    66 (*M).rhead[k]=NULL;67 for(k=1;k<=n;k++) //初始化列头指针向量;各列链表为空链表

    68 (*M).chead[k]=NULL;69 printf("请按任意次序输入%d个非零元的行 列 元素值:(空格)\n",(*M).tu);70 for(k=0;ki=i; //生成结点

    77 p->j=j;78 p->e=e;79 if((*M).rhead[i]==NULL||(*M).rhead[i]->j>j)80 {81 //p插在该行的第一个结点处

    82 p->right=(*M).rhead[i];83 (*M).rhead[i]=p;84 }85 else //寻查在行表中的插入位置

    86 {87 //从该行的行链表头开始,直到找到

    88 for(q=(*M).rhead[i]; q->right && q->right->j < j;q = q->right)89 ;90 p->right=q->right; //完成行插入

    91 q->right=p;92 }93 if((*M).chead[j] == NULL || (*M).chead[j]->i >i)94 {95 //p插在该列的第一个结点处

    96 p->down = (*M).chead[j];97 (*M).chead[j] =p;98 }99 else //寻查在列表中的插入位置

    100 {101 for(q = (*M).chead[j];q->down && q->down->i < i;q = q->down)102 ;103 p->down=q->down; //完成列插入

    104 q->down=p;105 }106 }107 return 1;108 }109 //按行或按列输出稀疏矩阵M

    110 intPrintSMatrix(CrossList M)111 {112 inti,j;113 OLink p;114 printf("%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu);115 printf("请输入选择(1.按行输出 2.按列输出):");116 scanf("%d",&i);117 switch(i)118 {119 case 1:120 for(j=1;j<=M.mu;j++)121 {122 p=M.rhead[j];123 while(p)124 {125 printf("%d行%d列值为%d\n",p->i,p->j,p->e);126 p=p->right;127 }128 }129 break;130 case 2:131 for(j=1;j<=M.nu;j++)132 {133 p=M.chead[j];134 while(p)135 {136 printf("%d行%d列值为%d\n",p->i,p->j,p->e);137 p=p->down;138 }139 }140 }141 return 1;142 }143 //由稀疏矩阵M复制得到T

    144 int CopySMatrix(CrossList M,CrossList *T)145 {146 inti;147 OLink p,q,q1,q2;148

    149 if((*T).rhead)150 DestroySMatrix(T);151 (*T).mu=M.mu;152 (*T).nu=M.nu;153 (*T).tu=M.tu;154 (*T).rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink));155 if(!(*T).rhead)156 exit(0);157 (*T).chead=(OLink*)malloc((M.nu+1)*sizeof(OLink));158 if(!(*T).chead)159 exit(0);160 for(i=1;i<=M.mu;i++) //初始化矩阵T的行头指针向量;各行链表为空链表

    161 (*T).rhead[i]=NULL;162 for(i=1;i<=M.nu;i++) //初始化矩阵T的列头指针向量;各列链表为空链表

    163 (*T).chead[i]=NULL;164 for(i=1;i<=M.mu;i++) //按行复制

    165 {166 p=M.rhead[i];167 while(p) //没到行尾

    168 {169 q=(OLNode*)malloc(sizeof(OLNode)); //生成结点

    170 if(!q)171 exit(0);172 q->i=p->i; //给结点赋值

    173 q->j=p->j;174 q->e=p->e;175 if(!(*T).rhead[i]) //插在行表头

    176 (*T).rhead[i]=q1=q;177 else //插在行表尾

    178 q1=q1->right=q;179 if(!(*T).chead[q->j]) //插在列表头

    180 {181 (*T).chead[q->j]=q;182 q->down=NULL;183 }184 else //插在列表尾

    185 {186 q2=(*T).chead[q->j];187 while(q2->down)188 q2=q2->down;189 q2->down=q;190 q->down=NULL;191 }192 p=p->right;193 }194 q->right=NULL;195 }196 return 1;197 }198 //求稀疏矩阵的和Q=M+N

    199 int AddSMatrix(CrossList M,CrossList N,CrossList *Q)200 {201 inti,k;202 OLink p,pq,pm,pn;203 OLink *col;204

    205 if(M.mu!=N.mu||M.nu!=N.nu)206 {207 printf("两个矩阵不是同类型的,不能相加\n");208 exit(0);209 }210 (*Q).mu=M.mu; //初始化Q矩阵

    211 (*Q).nu=M.nu;212 (*Q).tu=0; //元素个数的初值

    213 (*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));214 if(!(*Q).rhead)215 exit(0);216 (*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));217 if(!(*Q).chead)218 exit(0);219 for(k=1;k<=(*Q).mu;k++) //初始化Q的行头指针向量;各行链表为空链表

    220 (*Q).rhead[k]=NULL;221 for(k=1;k<=(*Q).nu;k++) //初始化Q的列头指针向量;各列链表为空链表

    222 (*Q).chead[k]=NULL;223 //生成指向列的最后结点的数组

    224 col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));225 if(!col)226 exit(0);227 for(k=1;k<=(*Q).nu;k++) //赋初值

    228 col[k]=NULL;229 for(i=1;i<=M.mu;i++) //按行的顺序相加

    230 {231 pm=M.rhead[i]; //pm指向矩阵M的第i行的第1个结点

    232 pn=N.rhead[i]; //pn指向矩阵N的第i行的第1个结点

    233 while(pm&&pn) //pm和pn均不空

    234 {235 if(pm->jj) //矩阵M当前结点的列小于矩阵N当前结点的列

    236 {237 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    238 if(!p)239 exit(0);240 (*Q).tu++; //非零元素数加1

    241 p->i=i; //给结点赋值

    242 p->j=pm->j;243 p->e=pm->e;244 p->right=NULL;245 pm=pm->right; //pm指针向右移

    246 }247 else if(pm->j>pn->j)//矩阵M当前结点的列大于矩阵N当前结点的列

    248 {249 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    250 if(!p)251 exit(0);252 (*Q).tu++; //非零元素数加1

    253 p->i=i; //给结点赋值

    254 p->j=pn->j;255 p->e=pn->e;256 p->right=NULL;257 pn=pn->right; //pn指针向右移

    258 }259 //矩阵M、N当前结点的列相等且两元素之和不为0

    260 else if(pm->e+pn->e)261 {262 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    263 if(!p)264 exit(0);265 (*Q).tu++; //非零元素数加1

    266 p->i=i; //给结点赋值

    267 p->j=pn->j;268 p->e=pm->e+pn->e;269 p->right=NULL;270 pm=pm->right; //pm指针向右移

    271 pn=pn->right; //pn指针向右移

    272 }273 else //矩阵M、N当前结点的列相等且两元素之和为0

    274 {275 pm=pm->right; //pm指针向右移

    276 pn=pn->right; //pn指针向右移

    277 continue;278 }279 if((*Q).rhead[i]==NULL) //p为该行的第1个结点280 //p插在该行的表头且pq指向p(该行的最后一个结点)

    281 (*Q).rhead[i]=pq=p;282 else //插在pq所指结点之后

    283 {284 pq->right=p; //完成行插入

    285 pq=pq->right; //pq指向该行的最后一个结点

    286 }287 if((*Q).chead[p->j]==NULL) //p为该列的第1个结点288 //p插在该列的表头且col[p->j]指向p

    289 (*Q).chead[p->j]=col[p->j]=p;290 else //插在col[p->]所指结点之后

    291 {292 col[p->j]->down=p; //完成列插入293 //col[p->j]指向该列的最后一个结点

    294 col[p->j]=col[p->j]->down;295 }296 }297 while(pm) //将矩阵M该行的剩余元素插入矩阵Q

    298 {299 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    300 if(!p)301 exit(0);302 (*Q).tu++; //非零元素数加1

    303 p->i=i; //给结点赋值

    304 p->j=pm->j;305 p->e=pm->e;306 p->right=NULL;307 pm=pm->right; //pm指针向右移

    308 if((*Q).rhead[i] == NULL) //p为该行的第1个结点309 //p插在该行的表头且pq指向p(该行的最后一个结点)

    310 (*Q).rhead[i] = pq =p;311 else //插在pq所指结点之后

    312 {313 pq->right=p; //完成行插入

    314 pq=pq->right; //pq指向该行的最后一个结点

    315 }316 if((*Q).chead[p->j] == NULL) //p为该列的第1个结点317 //p插在该列的表头且col[p->j]指向p

    318 (*Q).chead[p->j] = col[p->j] =p;319 else //插在col[p->j]所指结点之后

    320 {321 col[p->j]->down=p; //完成列插入322 //col[p->j]指向该列的最后一个结点

    323 col[p->j]=col[p->j]->down;324 }325 }326 while(pn) //将矩阵N该行的剩余元素插入矩阵Q

    327 {328 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    329 if(!p)330 exit(0);331 (*Q).tu++; //非零元素数加1

    332 p->i=i; //给结点赋值

    333 p->j=pn->j;334 p->e=pn->e;335 p->right=NULL;336 pn=pn->right; //pm指针向右移

    337 if((*Q).rhead[i]==NULL) //p为该行的第1个结点338 //p插在该行的表头且pq指向p(该行的最后一个结点)

    339 (*Q).rhead[i]=pq=p;340 else //插在pq所指结点之后

    341 {342 pq->right=p; //完成行插入

    343 pq=pq->right; //pq指向该行的最后一个结点

    344 }345 if((*Q).chead[p->j]==NULL) //p为该列的第1个结点346 //p插在该列的表头且col[p->j]指向p

    347 (*Q).chead[p->j]=col[p->j]=p;348 else //插在col[p->j]所指结点之后

    349 {350 col[p->j]->down=p; //完成列插入351 //col[p->j]指向该列的最后一个结点

    352 col[p->j]=col[p->j]->down;353 }354 }355 }356 for(k=1;k<=(*Q).nu;k++)357 if(col[k]) //k列有结点

    358 col[k]->down=NULL; //令该列最后一个结点的down指针为空

    359 free(col);360 return 1;361 }362

    363 //求稀疏矩阵的差Q=M-N

    364 int SubtSMatrix(CrossList M,CrossList N,CrossList *Q)365 {366 inti,k;367 OLink p,pq,pm,pn;368 OLink *col;369

    370 if(M.mu!=N.mu||M.nu!=N.nu)371 {372 printf("两个矩阵不是同类型的,不能相加\n");373 exit(0);374 }375 (*Q).mu=M.mu; //初始化Q矩阵

    376 (*Q).nu=M.nu;377 (*Q).tu=0; //元素个数的初值

    378 (*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));379 if(!(*Q).rhead)380 exit(0);381 (*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));382 if(!(*Q).chead)383 exit(0);384 for(k=1;k<=(*Q).mu;k++) //初始化Q的行头指针向量;各行链表为空链表

    385 (*Q).rhead[k]=NULL;386 for(k=1;k<=(*Q).nu;k++) //初始化Q的列头指针向量;各列链表为空链表

    387 (*Q).chead[k]=NULL;388 //生成指向列的最后结点的数组

    389 col=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));390 if(!col)391 exit(0);392 for(k=1;k<=(*Q).nu;k++) //赋初值

    393 col[k]=NULL;394 for(i=1;i<=M.mu;i++) //按行的顺序相加

    395 {396 pm=M.rhead[i]; //pm指向矩阵M的第i行的第1个结点

    397 pn=N.rhead[i]; //pn指向矩阵N的第i行的第1个结点

    398 while(pm&&pn) //pm和pn均不空

    399 {400 if(pm->jj) //矩阵M当前结点的列小于矩阵N当前结点的列

    401 {402 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    403 if(!p)404 exit(0);405 (*Q).tu++; //非零元素数加1

    406 p->i=i; //给结点赋值

    407 p->j=pm->j;408 p->e=pm->e;409 p->right=NULL;410 pm=pm->right; //pm指针向右移

    411 }412 //矩阵M当前结点的列大于矩阵N当前结点的列

    413 else if(pm->j>pn->j)414 {415 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    416 if(!p)417 exit(0);418 (*Q).tu++; //非零元素数加1

    419 p->i=i; //给结点赋值

    420 p->j=pn->j;421 p->e=-pn->e;422 p->right=NULL;423 pn=pn->right; //pn指针向右移

    424 }425 else if(pm->e-pn->e)426 {427 //矩阵M、N当前结点的列相等且两元素之差不为0

    428 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    429 if(!p)430 exit(0);431 (*Q).tu++; //非零元素数加1

    432 p->i=i; //给结点赋值

    433 p->j=pn->j;434 p->e=pm->e-pn->e;435 p->right=NULL;436 pm=pm->right; //pm指针向右移

    437 pn=pn->right; //pn指针向右移

    438 }439 else //矩阵M、N当前结点的列相等且两元素之差为0

    440 {441 pm=pm->right; //pm指针向右移

    442 pn=pn->right; //pn指针向右移

    443 continue;444 }445 if((*Q).rhead[i]==NULL) //p为该行的第1个结点446 //p插在该行的表头且pq指向p(该行的最后一个结点)

    447 (*Q).rhead[i]=pq=p;448 else //插在pq所指结点之后

    449 {450 pq->right=p; //完成行插入

    451 pq=pq->right; //pq指向该行的最后一个结点

    452 }453 if((*Q).chead[p->j]==NULL) //p为该列的第1个结点454 //p插在该列的表头且col[p->j]指向p

    455 (*Q).chead[p->j]=col[p->j]=p;456 else //插在col[p->]所指结点之后

    457 {458 col[p->j]->down=p; //完成列插入459 //col[p->j]指向该列的最后一个结点

    460 col[p->j]=col[p->j]->down;461 }462 }463 while(pm) //将矩阵M该行的剩余元素插入矩阵Q

    464 {465 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    466 if(!p)467 exit(0);468 (*Q).tu++; //非零元素数加1

    469 p->i=i; //给结点赋值

    470 p->j=pm->j;471 p->e=pm->e;472 p->right=NULL;473 pm=pm->right; //pm指针向右移

    474 if((*Q).rhead[i]==NULL) //p为该行的第1个结点475 //p插在该行的表头且pq指向p(该行的最后一个结点)

    476 (*Q).rhead[i]=pq=p;477 else //插在pq所指结点之后

    478 {479 pq->right=p; //完成行插入

    480 pq=pq->right; //pq指向该行的最后一个结点

    481 }482 if((*Q).chead[p->j]==NULL) //p为该列的第1个结点483 //p插在该列的表头且col[p->j]指向p

    484 (*Q).chead[p->j]=col[p->j]=p;485 else //插在col[p->j]所指结点之后

    486 {487 col[p->j]->down=p; //完成列插入488 //col[p->j]指向该列的最后一个结点

    489 col[p->j]=col[p->j]->down;490 }491 }492 while(pn) //将矩阵N该行的剩余元素插入矩阵Q

    493 {494 p=(OLink)malloc(sizeof(OLNode)); //生成矩阵Q的结点

    495 if(!p)496 exit(0);497 (*Q).tu++; //非零元素数加1

    498 p->i=i; //给结点赋值

    499 p->j=pn->j;500 p->e=-pn->e;501 p->right=NULL;502 pn=pn->right; //pm指针向右移

    503 if((*Q).rhead[i]==NULL) //p为该行的第1个结点504 //p插在该行的表头且pq指向p(该行的最后一个结点)

    505 (*Q).rhead[i]=pq=p;506 else //插在pq所指结点之后

    507 {508 pq->right=p; //完成行插入

    509 pq=pq->right; //pq指向该行的最后一个结点

    510 }511 if((*Q).chead[p->j]==NULL) //p为该列的第1个结点512 //p插在该列的表头且col[p->j]指向p

    513 (*Q).chead[p->j]=col[p->j]=p;514 else //插在col[p->j]所指结点之后

    515 {516 col[p->j]->down=p; //完成列插入517 //col[p->j]指向该列的最后一个结点

    518 col[p->j]=col[p->j]->down;519 }520 }521 }522 for(k=1;k<=(*Q).nu;k++)523 if(col[k]) //k列有结点

    524 col[k]->down=NULL; //令该列最后一个结点的down指针为空

    525 free(col);526 return 1;527 }528 //求稀疏矩阵乘积Q=M*N

    529 int MultSMatrix(CrossList M,CrossList N,CrossList *Q)530 {531 inti,j,e;532 OLink q,p0,q0,q1,q2;533

    534 InitSMatrix(Q);535 (*Q).mu=M.mu;536 (*Q).nu=N.nu;537 (*Q).tu=0;538 (*Q).rhead=(OLink*)malloc(((*Q).mu+1)*sizeof(OLink));539 if(!(*Q).rhead)540 exit(0);541 (*Q).chead=(OLink*)malloc(((*Q).nu+1)*sizeof(OLink));542 if(!(*Q).chead)543 exit(0);544 for(i=1;i<=(*Q).mu;i++) //初始化矩阵Q的行头指针向量;各行链表为空链表

    545 (*Q).rhead[i]=NULL;546 for(i=1;i<=(*Q).nu;i++) //初始化矩阵Q的列头指针向量;各列链表为空链表

    547 (*Q).chead[i]=NULL;548 for(i=1;i<=(*Q).mu;i++)549 for(j=1;j<=(*Q).nu;j++)550 {551 p0=M.rhead[i];552 q0=N.chead[j];553 e=0;554 while(p0&&q0)555 {556 if(q0->ij)557 q0=q0->down; //列指针后移

    558 else if(q0->i>p0->j)559 p0=p0->right; //行指针后移

    560 else //q0->i==p0->j

    561 {562 e+=p0->e*q0->e; //乘积累加

    563 q0=q0->down; //行列指针均后移

    564 p0=p0->right;565 }566 }567 if(e) //值不为0

    568 {569 (*Q).tu++; //非零元素数加1

    570 q=(OLink)malloc(sizeof(OLNode)); //生成结点

    571 if(!q) //生成结点失败

    572 exit(0);573 q->i=i; //给结点赋值

    574 q->j=j;575 q->e=e;576 q->right=NULL;577 q->down=NULL;578 if(!(*Q).rhead[i]) //行表空时插在行表头

    579 (*Q).rhead[i]=q1=q;580 else //否则插在行表尾

    581 q1=q1->right=q;582 if(!(*Q).chead[j]) //列表空时插在列表头

    583 (*Q).chead[j]=q;584 else //否则插在列表尾

    585 {586 q2=(*Q).chead[j]; //q2指向j行第1个结点

    587 while(q2->down)588 q2=q2->down; //q2指向j行最后1个结点

    589 q2->down=q;590 }591 }592 }593 return 1;594 }595 //求稀疏矩阵M的转置矩阵T

    596 int TransposeSMatrix(CrossList M,CrossList *T)597 {598 intu,i;599 OLink *head,p,q,r;600

    601 if((*T).rhead)602 DestroySMatrix(T);603 CopySMatrix(M,T); //T=M

    604 u=(*T).mu; //交换(*T).mu和(*T).nu

    605 (*T).mu=(*T).nu;606 (*T).nu=u;607 head=(*T).rhead; //交换(*T).rhead和(*T).chead

    608 (*T).rhead=(*T).chead;609 (*T).chead=head;610 for(u=1;u<=(*T).mu;u++) //对T的每一行

    611 {612 p=(*T).rhead[u]; //p为行表头

    613 while(p) //没到表尾,对T的每一结点

    614 {615 q=p->down; //q指向下一个结点

    616 i=p->i; //交换.i和.j

    617 p->i=p->j;618 p->j=i;619 r=p->down; //交换.down.和right

    620 p->down=p->right;621 p->right=r;622 p=q; //p指向下一个结点

    623 }624 }625 return 1;626 }627 intmain()628 {629 CrossList A,B,C;630 InitSMatrix(&A); //CrossList类型的变量在初次使用之前必须初始化

    631 InitSMatrix(&B);632 printf("创建矩阵A:");633 CreateSMatrix(&A);634 PrintSMatrix(A);635 printf("由矩阵A复制矩阵B:");636 CopySMatrix(A,&B);637 PrintSMatrix(B);638 DestroySMatrix(&B); //CrossList类型的变量在再次使用之前必须先销毁

    639 printf("销毁矩阵B后:\n");640 PrintSMatrix(B);641 printf("创建矩阵B2:(与矩阵A的行、列数相同,行、列分别为%d,%d)\n",642 A.mu,A.nu);643 CreateSMatrix(&B);644 PrintSMatrix(B);645 printf("矩阵C1(A+B):");646 AddSMatrix(A,B,&C);647 PrintSMatrix(C);648 DestroySMatrix(&C);649 printf("矩阵C2(A-B):");650 SubtSMatrix(A,B,&C);651 PrintSMatrix(C);652 DestroySMatrix(&C);653 printf("矩阵C3(A的转置):");654 TransposeSMatrix(A,&C);655 PrintSMatrix(C);656 DestroySMatrix(&A);657 DestroySMatrix(&B);658 DestroySMatrix(&C);659 printf("创建矩阵A2:");660 CreateSMatrix(&A);661 PrintSMatrix(A);662 printf("创建矩阵B3:(行数应与矩阵A2的列数相同=%d)\n",A.nu);663 CreateSMatrix(&B);664 PrintSMatrix(B);665 printf("矩阵C5(A*B):");666 MultSMatrix(A,B,&C);667 PrintSMatrix(C);668 DestroySMatrix(&A);669 DestroySMatrix(&B);670 DestroySMatrix(&C);671 system("pause");672 return 0;673 }

    展开全文
  • typedef struct OLNode{int i,j; //该非零元的行列下标ElemType e;struct OLNode *right ,*down; //该非零元所在行、列表的后继域} OLNode; *OLink;typedef struct {OLink *rhead , *chead; //行...

    typedef struct OLNode{

    int  i,j;                 //该非零元的行列下标

    ElemType    e;

    struct  OLNode    *right  ,*down;      //该非零元所在行表、列表的后继链域

    }  OLNode;   *OLink;

    typedef  struct {

    OLink  *rhead ,   *chead;     //行和列 链表头指针向量基址 由CreateSMatrix分配

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

    } CrossList;

    Status CreateSMatrix_OL(CrossList  &M)

    {         //创建稀疏矩阵M    采用十字链表存储表示

    if(M)

    {

    free(M);

    }

    scanf(&m,&n,&t); //输入M的行数列数和非零元个数

    M.mu = m;

    M.nu= n;

    m.tu = t;

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

    exit(OVERFLOW);

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

    exit(OVERFLOW);

    M.rhead[] = M.chead[] = NULL;         //初始化行列头指针向量,各行列链表为空链表

    for(scanf(&i,&j,&e); i != 0 ; scanf(&i,&j,&e))

    {  //按任意次序输入非零元

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

    exit(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->j right);

    p->right = q->right;

    q->right = p;

    }   //完成行插入

    if(M.chead[j] == NULL || M.rhead[j]->i >i)

    {

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

    M.chead[j] = p;

    }

    else

    {

    for(q = M.ched[j]; (q->down) && q->down->i < i; q= q->down);

    p->down = q->down;

    q->down = p;      //完成列插入

    }

    }

    }

    展开全文
  • 十字链表表示稀疏矩阵的基本操作

    千次阅读 2006-10-31 22:38:00
    【问题描述】两个相同行数和列数的稀疏矩阵用十字链表实现加法运算【数据描述】typedef struct ele {/* 十字链表结点类型*/ int row, col; double val; struct ele *right, *down;}eleNode;【算法描述】 (1) 若q-...

     【问题描述】两个相同行数和列数的稀疏矩阵用十字链表实现加法运算

    【数据描述】

    typedef struct ele {/* 十字链表结点类型*/

      int row, col;

      double val;

      struct ele *right, *down;

    }eleNode;

    【算法描述】

    (1) 若q->j>v->j,则需要在C矩阵的链表中插入一个值为bij的结点,,修改v=v->right。

    (2) 如q->j<v->j,则需要在C矩阵的链表中插入一个值为aij的结点,修改q=q->right。

    (3) 若q->j = = v->j且q->e + v->e ! = 0,则需要在C矩阵的链表中插入一个值为aij+bij的结点,修改q=q->right,v=v->right。

    重复(1)--(3)完成一行的操作。修改p=p->down,u=u->down后,再继续下一行。【C源程序】

    #include <stdio.h>

    #include <malloc.h>

    typedef struct ele {/* 十字链表结点类型*/

    int row,col;

    int val;

    struct ele *right,*down;

    }eleNode;

    /*建立一个元素全为零的稀疏矩阵的十字链表*/

    eleNode *createNullMat(int m,int n)         / * m行n列 */

    {eleNode *h,*p;

    int k;

    h=(eleNode *)malloc(sizeof(eleNode));       /*十字链表头结点 */

    h->row=m;h->col=n;h->val=0;                 / * 行数、列数和非零元素个数 */

    h->right=(eleNode *)malloc(sizeof(eleNode)*n);

    h->down=(eleNode *)malloc(sizeof(eleNode)*m);

    for(p=h->down,k=0;k<m;k++,p++){

    p->col=1000;                             / * 设矩阵不会超过1000列 */

    p->right=p;                             / * 每个行链表是一个环 * /

    p->down=k<m-1?p+1:h->down;                / * 使全部行链表头结点构成环*/

    }

    for(p=h->right,k=0;k<n;k++,p++){

    p->row=1000;                             / * 设矩阵不会超过1000行 * /

       p->down = p;                         / * 每个列链表是一个环 * /

       p->right = k<n-1 ? p+1 : h->right;    / *使全部列链表头结点构成环 * /

    }

    return h;

    }

    //

    int insertNode(eleNode *a ,int row,int col,double val){

    /* 在十字链表中插入一个结点*/

    eleNode *p,*q,*r,*u,*v;

    if(row>=a->row||col>=a->col) return -2;    / * 不合理的行列号 * /

    r=(eleNode *)malloc(sizeof(eleNode));

    r->row=row;r->col=col;r->val=val;

    p=a->down+row;q=p->right;

    while(q->col<col){p=q;q=q->right;}

    if(q->col==col) return -1;                 / * 该行已有col列元素 * /

    u=a->right+col;v=u->down;

    while(v->row<row){u=v;v=v->down;}

    if(v->row==row) return -1;            / * 该列已有row行元素 * /

    p->right = r; r->right = q;             / * 插入到行链中 * /

    u->down = r; r->down = v;               / * 插入到列链中 * /

    a->val=val;

    return 0;                                / * 插入成功 * /

    }

     

    eleNode *readMat(){

    /*输入数据建立十字链表*/

    eleNode *h;

    int i,j,m,n;

    int v;

    printf("输入稀疏矩阵的行数和列数");

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

    h=createNullMat(m,n);

    printf("输入有非零元素的行号");

    scanf("%d",&i);

    while(i>=0)                                / * 逐行输入非零元素 * /

    {  printf("输入非零元素的列号");

        scanf("%d",&j);

        while(j>=0)                             / * 输入一行非零元素 * /

        { printf("输入非零元素的值");

        scanf("%d",&v);

        insertNode(h,i,j,v);

       printf("输入当前行下一个非零元素的列号(-1表示当前行一组数据结束)");

        scanf("%d",&j);

        }

    printf("输入下一行有非零元素的行号(-1表示输入结束)");

    scanf("%d",&i);

    }

    return h;

    }

    void showMat(eleNode *a)

    {int row,col,i,j;

    eleNode *p;

    row=a->row;

    col=a->col;

    for (i=0;i<row;i++)

       { p=a->down+i;

        p=p->right;

        for(j=0;j<col;j++)

        { if(p->row==i&&p->col==j) {printf("%d  ",p->val);p=p->right;}

         else

         printf("0  ");

         }

       printf("/n");

       }

    }

    eleNode *matAdd(eleNode *a,eleNode *b)

    {eleNode *r,*p,*q,*u,*v;

    r=createNullMat(a->row,a->col);

    p=a->down;u=b->down;

    do {                                   / * 逐行相加 * /

    q=p->right;v=u->right;

    while(q!=p||v!=u)                      / * 两矩阵中有一个一行未结束循环 */

       if(q->col==v->col){                 / * 有相同列的元素 * /

        if(q->val+v->val!=0)                / * 和非零插入 * /

        insertNode(r,q->row,q->col,q->val+v->val);

        q=q->right;v=v->right;

        }

        else if(q->col<v->col){             / * 插入a的元素 * /

        insertNode(r,q->row,q->col,q->val);

        q=q->right;

        }

       else{                                / * 插入b的元素 * /

       insertNode(r,v->row,v->col,v->val);

       v=v->right;

       }

    p=p->down;u=u->down;

    }while(p!=a->down);

    return r;

    }



    void main()

    { eleNode *a,*b,*c;

       a=readMat();

       printf("a/n");

       showMat(a);

       b=readMat();

       printf("b/n");

       showMat(b);

      c= matAdd(a,b);

      printf("c/n");

      showMat(c);

      }

    【测试数据】

    输入a 矩阵:  4  0  0  0       输入b矩阵: 0  1  0  1       输出:4  1  0  1

                           0  5  0  9                          0 –5  0  0              0  0  0  9

                           0  0  1  0                          1  0  9  0                 1  0  10 0

    输入数据注意事项:

    (1)如上面a矩阵,应输入3行4列

    (2)若某行有非零元素,则按下列格式(三元组格式)输入:

    行号  列号  值  列号  值  …  列号  值  -1,如a矩阵的第0行,应输入0  0  4  -1,最后 的-1表示该行的一组数据输入结束。

    (3)按以上格式逐行地输入数据,直到输入的行号的值为-1时,表示稀疏矩阵的全部数据输入结束。

    【说明】

    从一个结点来看,进行比较、修改指针所需的时间是一个常数;整个运算过程在于对A和B的十字链表逐行扫描,其循环次数主要取决于A和B矩阵中非零元素的个数ta和tb;由此算法的时间复杂度为O(ta+tb)。

    展开全文
  • 十字链表矩阵

    2015-04-16 14:31:00
    数据结构的十字链表矩阵要一开始的行列的表头要相互连接来表示邻接关系 这里用数组表示邻接也不浪费空间 写了Serach( i , j );函数可以寻找矩阵位置为i j数值 然后加,减,乘,也就方便了…… 至于算法复杂度嘛...
  • 稀疏矩阵十字链表存储表示

    千次阅读 2014-05-08 12:07:28
    十字链表用的不多,但是面试可能会出现,故而记录一下。 十字链表节点形态: ...十字链表形态: ...稀疏矩阵十字链表存储表示 by Rowandjj 2014/5/7 ***************************************/ #include
  • 思路:首先建立十字链表,生成A,B。然后实现加法(注意要考虑各种情况!!)。一些说明:A----矩阵A ,B----矩阵B,C----矩阵C用p,q控制A的行列用u,v控制B的行列下面是程序的代码,注释很详细,相信你们能够看懂...
  • 随机稀疏矩阵十字链表
  • 十字链表储存稀疏矩阵矩阵相乘

    千次阅读 2016-11-03 09:28:11
    在进行矩阵的加法、减法和乘法等运算时,用十字链表表示稀疏矩阵比用三元组表示更灵活,以下为结构图和代码
  • 该非零元所在行和列表的后继域 }OLNode, * OLink; typedef struct { OLink *rhead, *chead; // 行和列表头指针向量基址由CreateSMatrix分配 int mu, nu, tu; }CrossList; Status CreateSMatrix_...
  • 十字链表中的结点中不仅有行号、列号、元素值,还有指向下一行的、下一列的非零元的两个指针。 typedef struct OLNode{ int i,j;//非零元的行、列下标 ElemType e; struct OLNode *right,*down;//该非零元所在行...
  • 实现了从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构(m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号)和十字链表的转置并将转置后的三元组到另一字符文件中
  • 1 #include <stdio.h> 2 #include <malloc.h> 3 typedef int ...// 稀疏矩阵十字链表存储表示 4 typedef struct OLNode 5 { 6 int i,j; // 该非零元的行和列下标 7 ElemType e; ...
  • /*广义的定义 typedef struct GNode *... //标志域:0表示结点是单元素,1表示结点是广义 union{ //子指针域SubList与单元素数据域Data复用,即共用存储空间 ElementTtype Data; GList SubList; }URegi
  • 稀疏矩阵十字链表存储 当矩阵的非零元个数和位置在操作过程中变化较大时,就不宜采用顺序存储结构来表示三元组的线性表。对这种类型的矩阵,采用链式存储结构表示三元组的线性表更为恰当。 在链表中,每个非...
  • 采用十字链表存储的稀疏矩阵

    千次阅读 2017-05-28 16:26:20
    十字链表就是能够实现这样功能的一种数据结构。 在十字链表中,每个非零元可以用一个包含5个域的结点表示。其中i、j和e这3个域分别表示该非零元所在的行、列和非零元的值,向右域right用来链接同一行中下一个非零元...
  • 矩阵的非零个数和位置在操作过程中变化大时,就不宜采用顺序存储结构来表示三元组的线性表。例如,在作“将矩阵B加到矩阵A上”的操作时,由于非零元的插入或删除将会引起A.data中元素的移动。为此,对这种类型的...
  • #include<stdio.h> #include<stdlib.h> #define ElementType int typedef struct GNode *GList; struct GNode{ ... /*Tag作为标志域,区分union中是什么数据:0表示节点是头节点head,1表示
  • #include &lt;stdio.h&gt; #include &lt;malloc.h&...// 稀疏矩阵十字链表存储表示 typedef struct OLNode { int i,j; // 该非零元的行和列下标 ElemType e; // 非零元素值 ...
  • 稀疏矩阵的压缩存储有几种方式,如:三元组顺序表、行逻辑链接的顺序表和十字链表。 使用链表存储的好处是:便于矩阵中元素的插入和删除。 例如:“将矩阵B加到矩阵A上”,那么矩阵A存储的元素就会有变动。比如会...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 254
精华内容 101
关键字:

十字链表表示矩阵