由于一维数组的下标从0开始，因此元素aij在一维数组中的下标为i（i+1）/2+j综上可得下标k的计算公式为： 同理可得其他三种方法存同理可得其他三种方法存储时，元素，元素aij在一在一维数数组中中的下的下标计算公式：算公式：（（2）列）列优先先顺序存序存储下三角下三角（（3）行）行优先先顺序存序存储上三角上三角 （（4）列）列优先先顺序存序存储上三角上三角 2 2．三角矩阵．三角矩阵包括上三角阵和下三角阵两种上三角阵的主对角线以下（不包括对角线）元素均为常数C，通常为0而下三角阵主对角线以上（不包括对角线）元素均为常数C，通常为0利用压缩存储的原理，只为矩阵中下三角的相同元素C分配一个存储单元，且当常数C为零时，不分配存储空间则为图中的上三角阵定义一个长度n（n+1）/2+1的数组，最后一个单元存储常数C 若上三角阵以行优先顺序存储，则地址公式与对称矩阵的行优先顺序存储上三角的地址公式相似，元素的下标k为： 若上三角阵以列优先顺序存储，则地址公式与对称矩阵的列优先顺序存储上三角的地址公式相似，元素的下标k为： 下三角阵的存储同理 3 3．对角矩阵．对角矩阵所有非零元素都集中在主对角线及主对角线两侧对称的带状区域，其余部分全部为零的n阶方阵为对角矩阵。
常见的对角矩阵有三对角阵，对角阵可以按照行优先顺序、列优先顺序或对角线顺序来进行存储，每一种存储顺序下都存在非零元素的下标与一维数组中下标之间的对应关系以行优先顺序为例，n阶三对角阵以行优先顺序存储的一维数组如下：排在aij前面的i行中共2+（i-1）×3=3i-1个元素；在第i+1行中，排在它前面的还有j-（i-1）=j-i+1个元素；则排在元素aij之前的共2i+j个元素，即下标k=2i+j 01234…12…3n-3a00a01a10a11a12…a44…a n-1,n-1 二、 稀疏矩阵稀疏矩阵在一个矩阵中，若非零元素的个数远远小于矩阵元素的总个数，则该矩阵称为稀疏矩稀疏矩阵若m×n的矩阵中有t个非零元素，则定义矩阵的稀疏因子稀疏因子为δ=t/（m×n），通常取δ≤0.05的矩阵为稀疏矩阵 稀疏矩阵的压缩存储，通常采用只存储非零元素的方法由于非零元素的分布没有规律，所以在存储非零元素值的同时，还需要存储非零元素的位置，即行号和列号因此，矩阵中的每一个非零元素都由一个包括非零元素所在的行、列以及它的值构成的三元组（i，j，v）来唯一确定，这样就可以将稀疏矩阵用非零元素三元组的线性表来表示。
稀疏矩阵A6×7的三元组表可表示为（（1，2，11），（3，1，-3），（3，6，7），（4，4，6），（6，3，5））稀疏矩阵的存储就可以转化为三元组表的存储，三元组表可以采用顺序存储或链接存储，对应稀疏矩阵的三元组顺序表和十字链表 若要唯一的表示一个稀疏矩阵，在存储三元组表的同时，还需要存储该矩阵的行数和列数，同时为了运算方便，一般还要存储非零元素的个数 1 1．三元组顺序表．三元组顺序表将三元组表中的三元组按照行优先的顺序排列成一个序列，然后采用顺序存储方法存储该线性表，称为三元组顺序表矩阵A的三元组顺序表为： 01234i13346j21643v11-3765 三元组顺序表存储结构的C语言描述如下：#define MAX 16 /*大于非零元素个数的一个常数*/typedef int DataType;typedef struct{ int i,j; /*非零元素所在的行、列*/ DataType v; /*非零元素值*/}Node; /* 三元组类型 */typedef struct{ int m,n,t; /* 矩阵的行、列及非零元素的个数 */ Node data[MAX]; /* 三元组表 */}Matrix;/* 三元组顺序表的存储类型 */Matrix A,B; 下面以矩阵加法为例，分析在三元组顺序表上的算法实现。
设有同构的两个稀疏矩阵A和B，求矩阵Q=A+B三个矩阵都用三元组顺序表存储该算法的具体思想如下：（1）分别从矩阵A和B中取出编号最小的两个非零元素，并比较二者编号2）若两个编号相等（行号、列号都相等），则求两个非零元素的和v，若v不等于零，则存入Q3）若A中当前元素的编号较小（行号较小，或行号相等列号较小），则将A中当前元素存入Q；否则将B中当前元素存入Q4）若A、B其中一个矩阵中的元素全部存入Q，则将另外一个矩阵中剩余元素依次存入Q中 2 2．十字链表．十字链表十字链表是稀疏矩阵的一种链接存储结构，在插入、删除操作时，不需要移动元素，效率较高十字链表存储稀疏矩阵的基本思想是：将稀疏矩阵中的每个非零元素都用一个包含五个域的结点来表示，存储非零元素所在行的行号域i，存储非零元素所在列的列号域j，存储非零元素值的值域v，以及行指针域right和列指针域down，分别指向同一行中的下一个非零元素结点和同一列中的下一个非零元素结点，其结点结构如图所示ijvdownright 在十字链表中，同一行中的非零元素通过right域链接在一个单链表中，同一列中的非零元素通过down域也链接在一个单链表中，每个非零元素既处于某行链表中，也处于某列链表中，就形成了交叉的十字链表。
通常，为方便运算，稀疏矩阵中每一行的非零元素结点按其列号从小到大顺序由right域链成一个带表头结点的循环链表，同样每一列中的非零元素按其行号从小到大顺序由down域也链成一个带表头结点的循环链表行列链表共用一个头结点 为了方便地找到每一行或每一列，将每行（列）的头结点链接起来，因为头结点的值域空闲，所以用头结点的值域作为连接各头结点的链域，即第i行（列）的头结点的值域指向第i+1行（列）的头结点，依此类推，形成一个循环链表这个循环链表又设一个头结点，这个头结点就是总头结点，总头结点的i和j域存储矩阵的行数和列数 因为非零元素结点的值域是DataType类型，而表头结点中此域是指针类型，为了使整个结构的结点一致，该域用一个共用体类型来表示十字链表结点的存储结构C语言描述如下：typedef int DataType; /*非零元素值的类型*/typedef struct Node { int i,j; /*非零元素所在的行、列*/struct Node *down , *right; /*行指针域和列指针域*/ union v_next /*非零元素结点的值域*/ {DataType v; struct node *next; }}MNode，*MLink;/*十字链表中结点和结点指针的类型*/ 4．3 广义表 广义表是线性表的推广，它放松了对线性表中的元素必须是原子的限制，允许表中的元素具有结构。
广广义表表（General List），也称为列表列表（Lists）是n（n≥0）个元素a1， a2， …，ai，…， an的有限序列，元素ai可以是原子或者是子表（子表亦是广义表）数据元素的个数n为广义表的长度度n＝0时称为空表，即表中不含任何元素通常将非空的广义表（n>0）记为：LS =（a1， a2， …，ai，…， an）其中，LS是广义表的名字a1为广义表的第一个元素，ai 为广义表的第i个元素显然，广义表是一种递归的数据结构，因为广义表中的数据元素还可以是广义表当广义表中的所有元素都是原子时，此广义表就是线性表 下面是一些广义表的例子：（1）A=（）A是一个空表，其长度为02）B=（a，b）B是一个长度为2的广义表，它的两个元素都是原子，因此它就是一个线性表3）C=（c，B）=（c，（a，b））C是长度为2的广义表，第一个元素是原子c，第二个元素是子表B4）D=（B，C，d）=（（a，b），（c，（a，b）），d）D是长度为3的广义表，第一个元素和第二个元素都为子表，第三个元素为原子d5）E=（a，E）=（a，（a，（a，（…））） E是长度为2的广义表，第一个元素是原子，第二个元素是E自身，它是一个无限递归的广义表。
广义表还有其他的表示方法，如：（1）带名字的广义表表示：在每个表的前面冠以该表的名字A（） B（a，b）C（c，B（a，b））D（ B（a，b），C（c，（a，b）），d）E（a，E（a，E（a，E（…）））（2）广义表的图形表示 用非分支结点表示原子，用分支结点表示广义表（空表除外，空表中不含元素，所以也用非分支结点表示） 广义表分为：线性表、纯表、再入表和递归表四种当广义表中的元素全部都是原子时，广义表就是线性表，因此也可以说线性表是广义表的一种特殊形式上图中的广义表B就是一个线性表若广义表中既包含原子，又包含子表，但没有共享和递归，如广义表C，则此时的广义表就是一棵树（将在第五章讨论），称这种广义表为纯表纯表允许结点的共享但不允许递归的广义表为再入表再入表，上图中的广义表D，子表B为共享结点，它既是表D的一个元素，又是子表C的一个元素这样的广义表与数据结构的图形结构对应（将在第六章讨论）允许递归的表称为递归表递归表，上图中的广义表E为递归表，表E是其自身的子表递归表、再入表、纯表、线性表之间的关系满足：递归表 再入表 纯表 线性表 广义表可以兼容线性表、树和图等各种经典的数据结构，广义表的大部分运算都与经典数据结构的运算类似。
四个特殊的运算：取表头Head（LS）、取表尾Tail（LS）、求表深、求表长广义表的表表头（Head）为广义表的第一个元素，广义表的表尾表尾（Tail）为广义表中除第一个元素外，剩下所有的元素组成的广义表对广义表LS =（a1， a2， ……， an）来说，取表头、取表尾的运算定义为： Head（LS） =a1，Tail（LS） = （a2， ……， an ）例如：Head（（a，b））= aTail（（a，b））=（b）Head（（a））= aTail（（a，b），c，（a，b）））=（ c，（a，b））） 任何一个非空广义表LS =（a1， a2， ……， an）均可分解为表头和表尾两个部分反之，一对表头和表尾也可唯一确定一个广义表根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，但表尾必定是子表广义表（）和（（））不同前者是长度为0的空表，而后者是长度为l的非空表，其表头和表尾均是空表（）广义表是一个多层次的结构，广义表的元素可以是子表，子表的元素仍可以是子表若将广义表的子表展开成全部由原子组成，则可将广义表的深度深度定义为表中所含括号的最大层数；而广义表的长度度为表中包含的元素个数。