数组的定义
数组的定义
数组是下标index 和值value 组成的序对的集合。
在数组中，每个有定义的下标都与一个值对应，这个值称做数组元素。
每个序对形如： (index,value)
数组的顺序表示和实现
由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。
一般都是采用顺序存储的方法来表示数组
一维数组的顺序表示
设第一个数组元素a[0]的存储地址是loc(a[0])，若已知每个数组元素占k个存储单元，则下标为i的数组元素a[i]的存储地址loc(a[i])为
loc(a[i])=loc(a[0])+i*k
i=0,1,2,…,n-1。
二维数组的顺序表示
二维数组a[m][n]映射到一维的存储空间时有两种顺序：行优先和列优先。
大多数语言如PASCAL、BASIC、C、C++等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。
矩阵的压缩存储
矩阵的存储――二维数组
考虑：若矩阵阶数很高，且有许多值相同的元素或零元素，怎么提高存储效率？
特殊矩阵――值相同的元素或者零元素在矩阵中的分布有一定规律
稀疏矩阵――矩阵中有大量零元素，非零元素比较少。
压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
对称矩阵的压缩存储
若i?j，则aij 在下三角矩阵中。 aij 之前的i-1行（从第1行到第i-1行）一共有1+2+…+i-1=i(i-1)/2个元素，在第i行上， aij 之前恰有j-1个元素（即ai0,ai1,ai2,…,aij-1），因此有：
k=i*(i-1)/2+j-1 当 i?j
若i
三角矩阵的压缩存储
三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到一维数组sa[n(n+1)/2+1]中，其中c存放在数组的第1个位置（亦可放在最后一个位置）。
上三角矩阵元素aij保存在数组sa中时，下标值k与（i,j）之间的对应关系是？
下三角矩阵元素aij保存在数组sa中时，下标值k与（i,j）之间的对应关系是？
稀疏矩阵的存储
解决方法：在存储非零元素的同时，同时记下它所在的行和列的位置（i, j)。
由于三元组(i, j, aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
例如，下列三元组表
( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (4,6,2), (5,2,18), (6,7,-7), (7,4,-6) ) 和行列信息(7,8,9)便可描述如图5.6所示的稀疏矩阵
注：行列信息(7,8,9)中，7：行；8：列；9：非零元个数
三元组顺序表
以顺序存储结构来表示三元组表，则得到稀疏矩阵的一种压缩存储方法――三元顺序表。
⑴ 三元组结点定义
#define MAX_SIZE 1000
typedef int elemtype ;
typedef struct
{ int row ; /* 行下标 */
int col ; /* 列下标 */
elemtype value; /* 元素值 */
}Triple ;
⑵ 三元组顺序表定义
typedef struct
{ int rn ; /* 行数 */
int cn; /* 列数 */
int tn ; /* 非0元素个数 */
Triple data[MAX_SIZE] ;
}TMatrix ;
TMatrix a；//定义了一个用三元组顺序表表示的稀疏矩阵
矩阵的转置
设稀疏矩阵A是按行优先顺序压缩存储在三元组表a.data中，若仅仅是简单地交换a.data中i和j的内容，得到三元组表b.data，b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组表b.data中元素的顺序。
由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。
转置矩阵的算法
按方法一求转置矩阵的算法如下：
void TransMatrix(TMatrix a , TMatrix * b)
{ int i , j , col ;
b->rn=a.cn ; b->cn=a.rn ; b->tn=a.tn ;
/* 置三元组表b->data的行、列数和非0元素个数 */
if (b->tn==0) printf(“ The Matrix A=0\n” );
else{ j=0; //b中三元组 数组下标
for (col=1; col<=a.cn ; col++)
/* 每次循环扫描 a的第col 列非零元，得到b的第col行非零元 */
for (i=0 ;i data[j].row=a.data[i].col ;
b-> data[j].col=a.data[i].row ;
b-> data[j].value=a.data[i].value;
j++ ;
}
} }
快速转置算法
快速转置算法如下
void FastTransMatrix(TMatrix a, TMatrix b)
{ int p , q , col , k ;
int num[N] , copt[N] ; //N为矩阵列数
b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ;
/* 置三元组表b.data的行、列数和非0元素个数 */
if (b.tn==0) printf(“ The Matrix A=0\n” ) ;
else
{ for (col=1 ; col<=a.cn ; ++col) num[col]=0 ;
/* 向量num[ ]初始化为0 */
for (k=0 ; k
十字链表（链式存储）
对于稀疏矩阵，当非0元素的个数和位置在操作过程中变化较大时，采用链式存储结构表示比三元组的线性表更方便。
矩阵中非0元素的结点所含的域有：行、列、值、行指针(指向同一行的下一个非0元)、列指针(指向同一列的下一个非0元)。其次，十字交叉链表还有一个头结点
稀疏矩阵中同一行的非0元素的由right指针域 链接成一个行链表， 由down指针域链接成一个列链表。
每个非0元素既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，所有的非0元素构成一个十字交叉的链表，称为十字链表。
此外，用两个一维数组rhead和chead分别存储行链表的头指针和列链表的头指针。
结点的描述如下：
typedef struct OLnode
{ int row , col ; /* 行号和列号 */
elemtype value ; /* 元素值 */
struct OLnode *down , *right ;
} OLNode, *OLink ; /* 非0元素结点 */
typedef struct
{ int rn; /* 矩阵的行数 */
int cn; /* 矩阵的列数 */
int tn; /* 非0元素总数 */
OLink * rhead ; //行链表头指针向量基址
OLink * chead ; //列链表头指针向量基址
} CrossList
广义表
广义表是线性表的推广和扩充，在人工智能领域中应用十分广泛。
第2章中的线性表定义为n(n?0 )个元素a1, a2 ,…, an的有穷序列，该序列中的所有元素具有相同的数据类型且只能是原子项(Atom)。所谓原子项可以是一个数或一个结构，在结构上不可再分。若放松对元素的这种限制，容许它们具有其自身结构，就产生了广义表的概念。
广义表(Lists，又称为列表 )：是由n(n ?0)个元素组成的有穷序列： LS=(a1，a2，…，an) ，其中ai或者是原子项，或者是一个广义表。LS是广义表的名字，n为它的长度。若ai是广义表，则称为LS的子表。
习惯上：原子项用小写字母，子表用大写字母。
若广义表LS非空时：
◆ a1(表中第一个元素)称为表头