#include <iostream>
#include<fstream>
#include<cstdlib>
typedef int ElemTp;
using namespace std;
typedef struct node
{
int i, j;
ElemTp e;
struct node *right, *down;
} OLNode, *Olink;
Olink init(int m, int n) //建空十字链表(不含元素结点)
{
Olink h, row, col;
int i, j;
h = new OLNode;
h->i = m;
h->j = n; //建总头结点
//以下建行头结点数组
row = h->down = new OLNode[m];
if (!h->down) return NULL; //返回NULL表示失败
for (i = 0; i<m; i++)
{
row[i].i = i;
row[i].right = &row[i];
}
//以下建列头结点数组
col = h->right = new OLNode[n];
if (!h->right) return NULL; //返回NULL表示失败
for (j = 0; j<n; j++)
{
col[j].j = j;
col[j].down = &col[j];
}
return h;
}
//十字链表中插入结点
bool insert(Olink h, int i, int j, ElemTp e)
//h为总头结点地址
{
Olink pr, s, p;
int m, n;
m = h->i; n = h->j;
if (i<0 || i >= m || j<0 || j >= n) return false;
//建新元素结点
s = new OLNode; if (!s) return false;
s->i = i; s->j = j; s->e = e;
//以下插入新结点*s到第i行循环链表
//插入后使第i行循环链表各结点按列下标升序连接
pr = &h->down[i]; p = pr->right;
while (p != &h->down[i] && j>p->j) { pr = p; p = p->right; }
pr->right = s; s->right = p;
//以下插入新结点*s到第j列循环链表
//插入后使第j列循环链表各结点按行下标升序连接
pr = &h->right[j]; p = pr->down;
while (p != &h->right[j] && i>p->i) { pr = p; p = p->down; }
pr->down = s; s->down = p;