十字链表

#include <bits/stdc++.h> using namespace std; typedef int datatype; #define smax 1e5 typedef struct lnode { int i, j; struct lnode *cptr, *rptr; union { struct lnode *next; datatype v; } uval; } link; link *CREATLINKMAT() { link *p, *q, *l, *cp[(int) smax]; int i, j, m, n, t, s; datatype v; cin >> m >> n >> t; s = max(m, n); l = (link *) malloc(sizeof(link)); l->i = m; l->j = n; cp[0] = l; for (i = 1; i <= s; i++) { p = (link *) malloc(sizeof(link)); p->i = 0; p->j = 0; p->rptr = p; p->cptr = p; cp[i] = p; cp[i - 1]->uval.next = p; } cp[s]->uval.next = l; for (int u = 1; u <= t; u++) { cin >> i >> j >> v; p = (link *) malloc(sizeof(link)); p->i = i; p->j = j; p->uval.v = v; q = cp[i]; while (q->rptr != cp[i] && q->rptr->j < j) q = q->rptr; p->rptr = q->rptr; q->rptr = p; q = cp[j]; while (q->cptr != cp[j] && q->cptr->i < i) q = q->cptr; p->cptr = q->cptr; q->cptr = p; } return l; } void PRTNTLINKMAT(link *l) { int m, n; link *q = l; m = l->i; n = l->j; for (int i = 1; i <= m; i++) { q = q->uval.next; link *p = q->rptr; int last = 1, flag = 1; for (int j = 1; j <= n; j++) { if (flag) { if (p == q) { flag = 0; cout << 0 << ' '; continue; } for (int k = last; k < p->j; k++) cout << 0 << ' '; cout << p->uval.v << ' '; last = p->j; p = p->rptr; j = last; } else cout << 0 << ' '; } cout << endl; } } int main() { PRTNTLINKMAT(CREATLINKMAT()); return 0; }