十字链表代码打卡
学习贺利坚老师数据结构
本人详细解析博客
代码仿写实操:
#include <stdio.h>
#include <malloc.h>#define M 3 //矩阵行
#define N 3 //矩阵列
#define Max ((M)>(N)? (M):(N)) //矩阵行列较大者typedef int ElemType;typedef struct mtxn
{int row; //行号int col; //列号struct mtxn *right, *down; //向右和向下的指针union{ElemType value; //数据区struct mtxn *link; //头结点指针区域}tag;}MatNode; //十字链表类型定义void CreatMat(MatNode *&mh, ElemType a[][N])
{int i,j;MatNode *h[Max],*p,*q,*r;//分配空间mh = (MatNode *)malloc(sizeof(MatNode));mh -> row = M; //行数赋值mh -> col = N; //列数赋值r = mh; //行列头结点,尾插法指针//创建行列头结点,并链接for(i = 0; i<Max; i++){h[i] = (MatNode *)malloc(sizeof(MatNode));h[i]->down = h[i]->right = h[i]; //先指向自己, 一会儿再链接//尾插法r->tag.link = h[i];r = h[i];}r->tag.link = mh; //置为循环链表//下面创建数据节点, 然后遍历插入for(i = 0; i<M; i++){for(j = 0; j<N; j++){if(a[i][j] != 0) //处理非零元素{p = (MatNode *)malloc(sizeof(MatNode));p->row = i;p->col = j;p->tag.value = a[i][j]; //创建新节点, 然后赋值//然后指针定位到对应的行头结点q = h[i];//查找在行表中的插入位置while(q->right != h[i] && q->right->col < j){q = q->right;}//尾插法p->right = q->right;q->right = p;//查找在列中的插入位置q = h[j];while(q->down != h[j] && q->down->row < i){q = q->down;}p->down = q->down;q->down = p; //完成列表的插入}}}
}void DispMat(MatNode *mh)
{MatNode *p,*q;printf("行 = %d 列 = %d\n", mh->row, mh->col);p = mh->tag.link; //指向头结点while(p != mh){q = p->right;while(p != q) //输出一行非零元素{printf("%d\t %d\t %d\n", q->row, q->col, q->tag.value);q = q->right;}p = p->tag.link;}
}int main()
{ElemType a[M][N] = {{1,0,3},{0,2,0},{0,0,5}};ElemType b[M][N] = {{-1,0,2},{0,-2,0},{1,0,-5}};MatNode *mx,*my;CreatMat(mx,a);CreatMat(my,b);printf("a的十字链表:\n");DispMat(mx);printf("a的十字链表:\n");DispMat(my);return 0;
}运行现象:
