苗火 Nicholas

[Data structures]Orthogonal link

2019-8-19 萧 写技术

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

#define MAX 1024

typedef struct _OLNode{
	int i,j;
	int e;
	struct _OLNode *right, *down;
}OLNode;

typedef struct _CrossList{
	OLNode **rhead;
	OLNode **chead;
	int m,n,t; //m rows, n cols, t none zero
}CrossList;

int CreateMatrix(CrossList *M)
{
	int i,j,k,e;
	OLNode *p,*q;

	scanf(" %d %d %d", &M->m, &M->n, &M->t);
	M->rhead = (OLNode **)malloc( sizeof(OLNode *) * (M->m + 1) );
	M->chead = (OLNode **)malloc( sizeof(OLNode *) * (M->n + 1) );
	for(i=1; i<=M->m; i++){
		M->rhead[i] = NULL;
	}
	for(i=1; i<=M->n; i++){
		M->chead[i] = NULL;
	}
	for(k=1; k<=M->t; k++){
		scanf(" %d %d %d", &i, &j, &e);
		p = (OLNode *)malloc( sizeof(OLNode) );
		p->i = i;
		p->j = j;
		p->e = e;
		if(M->rhead[i] == NULL || M->rhead[i]->j > j){
			p->right = M->rhead[i];
			M->rhead[i] = p;
		}else{
			for(q = M->rhead[i]; q->right && q->right->j < j; 
					q = q->right);
			p->right = q->right;
			q->right = p;
		}

		if(M->chead[j] == NULL || M->chead[j]->i > i){
			p->down = M->chead[j];
			M->chead[j] = p;
		}else{
			for(q = M->chead[j]; q->down && q->down->i < i; 
					q = q->down);
			p->down = q->down;
			q->down = p;
		}
	}
	return 1;
}

void PrintMatrix(CrossList M)
{
	int i,j,k;
	OLNode *pc;
	for(i=1; i<=M.m; i++){
		pc = M.chead[i];
		for(j=1; j<=M.n; j++){
			if(pc && pc->i == i && pc->j == j){
				printf(" %2d", pc->e);
				pc = pc->right;
			}else{
				printf(" %2d", 0);
			}	
		}	
		printf("\n");
	}
}

void main()
{
	CrossList M;

	printf("log.anycle.com\n\n");
	printf("Create matrix M:\n");
	CreateMatrix(&M);

	PrintMatrix(M);
	printf("\n");
}

标签: Data Structures data_structures