#include<stdio.h>
#include<stdlib.h>

#define maxSize 20

/* 十字链表中普通结点的结构体定义 */
typedef struct OLNode {
	int row;// 行号
	int col;// 列号
	struct OLNode *right;// 指向右方的结点
	struct OLNode *down;// 指向下方的结点
	float val;// 表示非零元素的值
} OLNode;
/* 十字链表中头结点的结构体定义 */
typedef struct {
	OLNode *rhead;// 指向头结点的指针
	OLNode *chead;// 指向头结点的指针
	int m;// 矩阵行数
	int n;// 矩阵列数
	int k;// 稀疏矩阵非零结点总数
} CrossList;

/* 创建十字链表 */
/* A[][maxSize]指的是稀疏矩阵；m指的是稀疏矩阵的行数；n指的是稀疏矩阵的列数；k指的是稀疏矩阵的非零结点数；&M指的是十字的头结点 */
int createCrossListmat(float A[][maxSize],int m,int n,int k,CrossList &M) {
	if(M.rhead) {
		free(M.rhead);
	}
	if(M.chead) {
		free(M.chead);
	}
	M.m=m;
	M.n=n;
	M.k=k;// 赋予头结点指针k值（稀疏矩阵的非零结点数）
	/* 申请头结点数组空间 */
	if(!(M.rhead=(OLNode*)malloc(sizeof(OLNode)*m))) {
		return 0;
	}
	if(!(M.chead=(OLNode*)malloc(sizeof(OLNode)*n))) {
		return 0;
	}
	/* 头结点数组right和down指针置空 */
	for(int i=0; i<m; i++) {
		M.chead[i].right=NULL;
		M.chead[i].down=NULL;
	}
	for(int i=0; i<n; i++) {
		M.chead[i].right=NULL;
		M.chead[i].down=NULL;
	}
	OLNode *temps[maxSize];// 建立列链表的辅助指针数组
	for(int j=0; j<n; j++) {
		temps[j]=&(M.rhead[j]);
	}
	for(int i=0; i<m; i++) {
		OLNode *r=&(M.chead[i]);
		for(int j=0; j<n; j++) {
			if(A[i][j]!=0) {
				OLNode *p=(OLNode*)malloc(sizeof(OLNode));
				p->row=i;
				p->col=j;
				p->val=A[i][j];
				p->down=NULL;
				p->right=NULL;
				r->right=p;
				r=p;
				temps[j]->down=p;
				temps[j]=p;
			}
		}
	}
	return 1;
}

int main() {
	// 稀疏矩阵
	float A[][maxSize]= {
		{0,0,0,1},
		{0,0,3,2},
		{1,0,0,0},
		{0,2,0,0},
		{1,0,0,0}
	};
	CrossList M;
	createCrossListmat(A,5,4,6,M);
	return 0;
}