数据结构-采用十字链表存储的稀疏矩阵 （C语言代码）

参考代码:

#include<stdio.h>
#include<malloc.h>

typedef struct node {
	int i, j;
	int data;
	struct node *right, *down;
} node;

typedef struct CrossList {
	node **rhead, **chead;
	int mu, nu, tu;
} CrossList;

void CreateCrossList(CrossList *M);
void DisplayCrossList(CrossList *M);

int main()
{
	CrossList M;
	CreateCrossList(&M);
	DisplayCrossList(&M);
	return 0;
}

void CreateCrossList(CrossList *M) {
	int i, j, data;
	node *p, *q;
	scanf("%d%d", &M->mu, &M->nu);
	M->tu = 0;
	M->rhead = (node **)malloc(sizeof(node *) * (M->mu + 1));
	M->chead = (node **)malloc(sizeof(node *) * (M->nu + 1));
	for (i = 1; i <= M->mu; i++) {
		p = (node *)malloc(sizeof(node));
		M->rhead[i] = p;
		p->right = NULL;
	}
	for (j = 1; j <= M->nu; j++) {
		q = (node *)malloc(sizeof(node));
		M->chead[j] = q;
		q->down = NULL;
	}
	for (i = 1; i <= M->mu; i++) {
		for (j = 1; j <= M->nu; j++) {
			scanf("%d", &data);
			if (data) {
				p = (node *)malloc(sizeof(node));
				p->i = i;
				p->j = j;
				p->data = data;
				p->right = NULL;
				p->down = NULL;
				// 找到插入位置上一个结点
				for (q = M->rhead[i]; q->right && j > q->right->j; q = q->right);
				p->right = q->right;
				q->right = p;
				for (q = M->chead[j]; q->down && i > q->down->i; q = q->down);
				p->down = q->down;
				q->down = p;
				M->tu++;
			}
		}
	}
}

void DisplayCrossList(CrossList *M) {
	int i, j;
	node *p;
	for (i = 1; i <= M->mu; i++) {
		for (j = 1, p = M->rhead[i]->right; j <= M->nu; j++) {
			if (p && j == p->j) {
				printf("%d ", p->data);
				p = p->right;
			}
			else {
				printf("0 ");
			}
		}
		printf("\n");
	}
}