前言：
2、3、4章讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。本章讨论的两种数据结构---数组和广义表可以看成是线性表在下述含以上的扩展：表中的数据元素本身也是一个数据结构。
其中、数组是一种比较熟知的数据类型，几乎所有程序语言都把数组类型设定为固有类型，前两节节以抽象数据类型的形式讨论数组的定义和实现，使读者加深对数组的理解。
目录：
1.数组的定义
2.数组的顺序表示和实现
3.矩阵的压缩存储
4.广义表的定义
5.广义表的存储结构
6.m元多项式的表示
7.广义表的递归算法
正文：
一、数组的定义
类似于线性表，抽象数据类型数组可形式地定义为：
ADT Array{
数据对象：
ji=0，... ，bi-1， i=1,2，...，n
D={aj1 j2 ... jn | n(>0) 称为数组的维数，bi 是数组第 i 维的长度，ji 是数组元素的第 i 维下标， aj1 j2 ... jn ∈ElmeSet}
数据关系：
R={R1，R2...Rn}
Ri={
< aj1 ... ji ... jn ，aj1 ... ji+1 ... jn > |
0<= jk <=bk-1，1<= k <=n 且 k <> i
0<= ji <=bk-2，
aj1 ... ji ... jn ，aj1 ... ji+1 ... jn ∈ D ，i = 2 , ... n
}
基本操作：
InitArray();
DestoryArray();
Value();
Assign();
}ADT Array;
二、数组的顺序表示及实现
由于数组一般不作插入和删除操作，也就是说，一旦建立了数组，则结构中的数据元素和元素之间的关系就不再变动。因此，采用顺序存储结构表示数组是自然而然的事了
由于存储单元是一维的结构，而数组是多维的结构，则用一组连续的存储单元存放数组的数据元素有个次序问题。
例如、对于二维数组来说，可以看成是一维数组，一维数组的每一个数组元素又是一个一维数组。对应的对于二维数组有两种存储方式：
1.以列序为主序的存储方式
2.以行序为主序的存储方式
由此，对于数组，一旦规定了他的维度和各维度的长度，便可为它分配存储空间。反之，至于给出一组下标便可求出相应数组元素的存储位置。
大部分程序设计语言都采用了以行序为主序的存储方式。以下采用以行序为主序的存储方式为例予以说明
假设每个数据元素占L个存储单元，则二维数组A 中任一元素 aij 的存储位置可由下式确定：
LOC(i , j) = LOC(0，0) + (b2 * i +j )*L
LOC(i , j)是 a ij 的存储位置， LOC(0，0) 是a00 的存储位置，即二维数组A 的起始存储位置，也称基址，基地址。
将其推广到一般，得n 维数组的数据元素存储位置的公式为：
LOC(j1, ...jn) = LOC(0，...0) + (b2*b3*...*bn*j1+ b3*b4*...*bn*j2+ ... + bn*jn-1 + jn) * L
=LOC(0，...0) + ∑ ci ji 其中 cn=L , ci-1 = bi * ci ，1< i <n
LOC(0，...0) + ∑ ci ji 称为 n维数组的映像函数。一旦确定了数组的各维长度，ci 就是一个常数。
数组的顺序存储结构：
typedef struct{ ElemType *base; //数组元素基址，由InitArray 分配 int dim; //数组维数 int *bounds; //数组维界基址，由InitArray 分配 int *constants; //数组映像函数常量基址，由InitArray 分配（constants[i]=ci） }Array;
代码实现：
#include<stdio.h> #include<stdlib.h> #include<stdarg.h> //stdarg.h 头文件定义了一个变量类型 va_list 和三个宏， //这三个宏可用于在参数个数未知（即参数个数可变）时获取函数中的参数。 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define UNDERFLOW -3 #define MAX_ARRAY_DIM 8 //Status是函数的类型，其值是函数结果状态码 typedef int Status; typedef char ElemType; typedef struct{ ElemType *base; //数组元素基址，由InitArray 分配 int dim; //数组维数 int *bounds; //数组维界基址，由InitArray 分配 int *constants; //数组映像函数常量基址，由InitArray 分配(constants[i]=ci) }Array; //初始化数组A] Status InitArray(Array &A,int dim,...){ if(dim<1||dim>MAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim*sizeof(int)); if(!A.bounds) exit(OVERFLOW); //初始化每一维度的长度，并计算总的元素个数 int ElemTotal=1; va_list ap; va_start(ap, dim); for(int i=0;i<dim;i++){ A.bounds[i]=va_arg(ap, int); //依次接收dim 参数后面的未确定的参数 if(A.bounds[i]<0) return UNDERFLOW; ElemTotal *= A.bounds[i]; //计算元素总数（ 累乘维度 ） } va_end(ap); //为dim 维数组A 分配所有的存储空间 A.base=(ElemType *)malloc(ElemTotal*sizeof(ElemType)); if(!A.base) exit(OVERFLOW); A.constants=(int *)malloc(dim*sizeof(int)); if(!A.constants) exit(OVERFLOW); A.constants[dim-1]=sizeof(ElemType); for(int j=dim-2;j>=0;j--){ A.constants[j]=A.bounds[j+1]*A.constants[j+1]; } return OK; } Status DestoryArray(Array &A){ //销毁数组A if(!A.base) return ERROR; free(A.base); A.base=NULL; if(!A.bounds) return ERROR; free(A.bounds); A.bounds=NULL; if(!A.constants) return ERROR; free(A.constants); A.constants=NULL; return OK; } //计算 元素在 A 的相对位置，并用off返回 Status LocateArray(Array &A,va_list ap,int &off){ off=0; for(int i=0;i<A.dim;i++){ int locate=va_arg(ap, int); if(locate<0||locate>A.bounds[i]) return OVERFLOW; off+=A.constants[i]*locate; } return OK; } //返回某个合法下标对应的值。 Status Value(Array &A,ElemType *e,...){ va_list ap; va_start(ap,e); int off; LocateArray(A,ap,off); va_end(ap); *e=*(A.base+off); return OK; } //给A数组的合法下标赋值 Status Assign(Array &A,ElemType e,...){ va_list ap; va_start(ap, e); int off; LocateArray(A,ap,off); va_end(ap); *(A.base+off)=e; return OK; } void main(){ Array A; InitArray(A,4,3,4,5,6); //赋值 Assign(A,'b',2,1,4,1); ElemType e; //取值 Value(A,&e,2,1,4,1); printf("value:%c ",e); }