数组随笔

稀疏数组储存的下标实际上是该元素之前的元素个数，这样才可以实现从0开始存储。

这是因为不能直接用下标读取元素了。

 对于十字链表的储存：

#include<bits/stdc++.h>
using namespace std;
void add();
void creat(crosslist& a);
void init();
void print();
struct node {
    int i, j;
    int value;
    node* right, *down;
};
struct crosslist {
    int row, col;
    int tu;
    node* rhead, * dhead;
};
int m, n;
crosslist a;
void creat(crosslist& a) {
    for (int i = 0; i < a.tu; i++) {
        node* temp;
        cin >> temp->i >> temp->j >> temp->value;
        temp->right = temp->down = NULL;
        if (a.rhead[temp->i].right == NULL) {
            a.rhead[temp->i].right = temp;
        }
        else {
            node* p = a.rhead[i].right;
            while (p->right && p->right->j < temp->j) {
                p = p->right;
            }
            temp->right = p->right;
            p->right = temp;
        }//行插入成功！
        if (a.dhead[temp->j].down = NULL) {
            a.dhead[temp->j].down = temp;
        }
        else {
            node* p = a.dhead[temp->j].down;
            while (p->down && p->down->i < temp->i) {
                p = p->down;
            }
            temp->down = p->down;
            p->down = temp;
        }//列插入成功！
    }
}
void init() {
    a.rhead = a.dhead = NULL;
    cin >> a.row >> a.col >> a.tu;
    a.rhead = new node[n];
    a.dhead = new node[m];
    //初始化行和列的头
    for (int i = 0; i < n; i++) {
        a.rhead[i].down = NULL;
    }
    for (int i = 0; i < m; i++) {
        a.dhead[i].right = NULL;
    }
    creat(a);
}