一、数组

1、地址计算

二维：
注意是地址！不是坐标哦，每一个元素都会占用内存。

Loc[i][j]=Loc[1][1]+n(i-1)+(j-1).

三维：

Loc[i][j][k]=Loc[1][1][1]+mn(i-1)+n(j-1)+(k-1)

2、下三角矩阵

每一行的数量满足等差数列

Loc[i][j]=Loc[1][1]+i(i-1)/2+(j-1)

同理，上三角矩阵：

Loc[i][j]=Loc[1][1]+j(j-1)/2+(i-1)

下三角矩阵坐标计算（二维转一维的映射关系）：

3、带状矩阵

第i行的A[i][j]前面有j-i+1个元素
所需要的一维向量空间大小：3n-2
计算地址：

Loc[i][j]=Loc[1][1]+(3(i-1)-1)size+(j-i+1)size

4、稀疏矩阵

三元组表
用 行 列 值 表示非零元素

#define MAXSIZE 1001
//定义三元组表
typedef struct{
	int row, col;
	ElementType e;
}Triple;
//定义矩阵
typedef struct{
	Triple data[MAXSIZE];
	int m, n, len; //矩阵行列 非零个数
}TSMatrix;

矩阵转置即将row和col交换

5、矩阵相乘

for(i=1;i<=m1;i++){
	for(j=1;j<=n2;j++){
		Q[i][j]=0;
		for(k=1;k<=n1;k++) Q[i][j]+=M[i][k]*N[k][j]
	}
}

6、十字链表

十字链表的结构：

typedef struct OLNode{
    int row,col;
    ElementTyope value;
    struct OLNode *right,*down;
}OLNode;*OLink;

typedef struct{
    OLink *row_head,*col_head;
    int m,n,len;
}CrossList;

建立十字链表：

CreateCrossList(CrossList* M){
    //清空
    if(M!=NULL) free(M); 
    cin>>m>>n>>t;
    M->m=m; M->n=n; M->len=t;
    //申请内存空间溢出
    if(!(M->row_head=(Olink*)malloc((m+1)sizeof(Olink)))) exit(OVERFLOW);
    if(!(M->col_head=(Olink*)malloc((m+1)sizeof(Olink)))) exit(OVERFLOW);
    //初始化行列头指针向量
    M->row_head[]=M->col_head=NULL;
    for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e){
        if(!(p=(Olink*)malloc((m+1)sizeof(Olink)))) exit(OVERFLOW);
        //生成新结点
        p->row=i; p->col=j; p->value=e;
        if(M->row_head==NULL) M->row_head[i]=p; //该行第一结点
        else{
            //寻找插入结点位置
            for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right){
                p->right=q->right; q->right=p;
            }
        if(M->col_head[j]==NULL) M->col_head[j]=p;
        else{
           for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down){
                p->down=q->down; q->down=p;
            }
        }
    })
}

二、广义表

递归定义，多层结构，相互共享

typedef enum{ATOM,LIST}ElemTag;
typedef struct GLNode{
    ElemTag tag;
    union{
        AtomType atom;
        struct GLNode *hp;
    }atom_hp;
    struct GLNode *tp;
}*GList;

更新至2020.7.16

---