[数据结构与算法]稀疏矩阵-正交链表表示

//自己写出来的，测试过
#include<stdio.h>
#include<stdlib.h>
#define MaxSize  100
typedef   enum { H, E }   TagField;
typedef struct term {
	int row, col, value;
}Term;
typedef struct mnode {
	struct mnode* Right, * Down;
	TagField Tag;
	union {
		struct mnode* Next;
		Term Element;
	}U;
}MNode;
typedef struct linkedmatrix {
	MNode* Head;
	MNode* HD[MaxSize];
}LinkedMatrix;
MNode* NewNode() {
	MNode* temp = (MNode*)malloc(sizeof(MNode));
	temp->Down = NULL;
	temp->Right = NULL;
	return temp;
}
//建立正交链表
LinkedMatrix  MRead(void) {
	int rows, cols, nozeros, heads;
	int row, col, value, current_row, i;
	MNode* ptemp, * prow_last, *pcol_last, * pnode, * Temp;
	LinkedMatrix A;
	printf("Enter tyhe number of rows, columns  and number of nozero terms:  ");
	scanf_s("%d%d%d", &rows, &cols, &nozeros);
	//建立正交链表的表头结点
	heads = (cols > rows) ? cols : rows;
	pnode = NewNode();
	pnode->Tag = E;
	pnode->U.Element.row = rows;
	pnode->U.Element.col = cols;
	pnode->U.Element.value = nozeros;
	pnode->Down = NULL;
	A.Head = pnode;
	Temp = A.Head;
	if (!heads) {
		pnode->Right=pnode;
	}
	else {
		//建立heads 个行/列表头结点， 形成一个包含有Heads个元素的包含有表头节点的空循环链表，
		for (i = 0; i < heads; i++) {
			A.HD[i] = NewNode();
			A.HD[i]->Tag = H;
			A.HD[i]->Right = A.HD[i];
			A.HD[i]->Down = A.HD[i];
			if (i==0) {
				Temp->Right = A.HD[i];
			}
			else {
				Temp->U.Next = A.HD[i];
			}
			Temp = A.HD[i];
		}
		Temp->U.Next = A.Head;
		//包含有Heads个元素的包含有表头节点的空循环链表创建完成
		//从第0行起，按行插入非0元素
		for (i = 0; i < nozeros;i++) {
			printf("Enter row , col   and  value: ");
			scanf_s("%d%d%d", &row, &col, &value);
			ptemp = NewNode();
			ptemp->Tag = E;
			ptemp->U.Element.row = row;
			ptemp->U.Element.col = col;
			ptemp->U.Element.value = value;
			ptemp->Right = A.HD[row];
			ptemp->Down = A.HD[col];

			prow_last = A.HD[row];
			for (; prow_last->Right != A.HD[row]; prow_last = prow_last->Right);
			prow_last->Right = ptemp;
			prow_last = ptemp;

			pcol_last=A.HD[col];
			for (; pcol_last->Down != A.HD[col]; pcol_last = pcol_last->Down);
			pcol_last->Down=ptemp;
			pcol_last=ptemp;
		}

	}
	return A;
}
//打印正交链表
void PrintLinkedMatrix(LinkedMatrix A) {
	MNode* ptemp, * prow_temp;
	ptemp = A.Head->Right;
	for (; ptemp != A.Head; ptemp= ptemp->U.Next) {
		prow_temp = ptemp->Right;
		for (; prow_temp != ptemp; prow_temp = prow_temp->Right) {
			printf("%d    %d    %d\n", prow_temp->U.Element.row, prow_temp->U.Element.col, prow_temp->U.Element.value);
		}
	}
}
void main() {
	LinkedMatrix A = MRead();
	PrintLinkedMatrix(A);
	system("pause");
}