类型定义
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MAX 100
/*稀疏矩阵的十字链表表示：非零元素节点与表头节点公用一种类型
*/
typedef struct matrixnode
{int row,col;struct matrixnode *right,*down;union{int val;//非零元素节点的值struct matrixnode*next;//指向下一个表头节点}tag;
}matrixnode;
typedef matrixnode*spmatrix;
typedef spmatrix headspmatrix[MAX];//保存i行/i列的表头节点指针
void say(spmatrix p)
{printf("row:%d\ncol:%d\n",p->row,p->col);printf("right---%p\ndown---%p\n",p->right,p->down);
}
void Createspmatrix (headspmatrix h)
{int m,n,t,s,i,r,c,v;spmatrix p,q;printf("矩阵的行数.列数.和非零元素的个数:\n");scanf("%d%d%d",&m,&n,&t);//初始化一个表头节点，储存链表的行数，列数p=(spmatrix)malloc(sizeof(matrixnode));h[0]=p;p->row=m;p->col=n;s=m>n?m:n;//表头节点个数取行列数的较大值h[0]->tag.val=s;for(i=1;i<=s;i++){p=(spmatrix)malloc(sizeof(matrixnode));h[i]=p;h[i-1]->tag.next=p;//将上一个表头节点与该表头节点连接p->row=p->col=0;//表头节点的row和col置空p->down=p->right=p;//当前表头节点初始化为空，down和right指向自身。}h[s]->tag.next=h[0];//最后一个表头节点与头节点连接，形成环for(i=1;i<=t;i++){printf("请输入非零元素的行号，列号，值:\n");scanf("%d%d%d",&r,&c,&v);p=(spmatrix)malloc(sizeof(matrixnode));//printf("46\n");p->row=r;p->col=c;p->tag.val=v;//printf("47\n");q=h[r];//取得该行表头节点指针//printf("49\n");while(q->right!=h[r]&&q->right->col<c)//连接到相应行{q=q->right;//printf("52\n");}// printf("51\n");p->right=q->right;q->right=p;q=h[c];//取得该列表头节点指针while(q->down!=h[c]&&q->down->row<r)//连接到相应列q=q->down;p->down=q->down;q->down=p;}
}相关操作
//在十字链表中查找元素，通过指针返回对应坐标，函数返回1表示查找成功
int locatespmatrix(headspmatrix h,int x,int *rowx,int *colx)
{spmatrix p,q;p=h[0]->tag.next;while(p!=h[0]){q=p->right;while(p!=q){if(q->tag.val==x){*rowx=q->row;*colx=q->col;return 1;}q=q->right;}p=p->tag.next;}return 0;
}
//遍历稀疏矩阵的十字链表并按行优先输出
void matrix_display(headspmatrix h)
{spmatrix p,q;p=h[0]->tag.next;while(p!=h[0]){q=p->right;while(p!=q){printf("%d %d %d",q->row,q->col,q->tag.val);q=q->right;}printf("\n");p=p->tag.next;}
}
//销毁整个十字链表
void matrix_destory(headspmatrix h)
{spmatrix p,q,t;p=h[0]->tag.next;int s=0;while(p!=h[0]){q=p->right;while(p!=q){t=q->right;free(q);printf("%d is kill\n",++s);q=t;}p=p->tag.next;}
}版权声明：本文为博主原创文章，未经博主允许不得转载。
