数据结构
多浪费存储空间。
2.动态分配
在定义线性表的存储类型时，只定义一个指针，待程序运行是可以通过基本函数malloc申请一个恰当大小的用于存储线性表的空间，并把该空间的首地址赋给这个指针。访问动态存储分配的线性表中的元素与访问静态时的情况相同，既可以采用指针方式，也可以采用数组下标方式。
5、线性表顺序存储结构的优缺点 1.优点
（1）结构简单（2）可直接定位到表中任意元素，并可随机存取元素，连续存取速度快。 2.缺点
（1）存储空间难于准确静态分配，分配大了浪费空间，分配小了又可能不够用。（2）插入、删除操作不大方便，需要移动大量数据元素，效率较低。
6、线性表的链式存储结构
在链式存储结构下，线性表的存储空间可以是分散不连续的。因此，存储结点的物理次序和原有的逻辑次序不一定相同。为了能正确表示结点的逻辑关系，每个存储结点不仅含有数据元素本身的信息，还含有一个或多个指针（地址）信息，指示结点间的逻辑关系。结点中data表示数据域，用来存储数据元素本身；p称为指针域。注意，一个存储结点的存储空间是连续的。
7、线性表的链式存储结构的优缺点 1.优点
（1）存储空间动态分配，可以按需要使用。（2）插入、删除结点操作通常只需要修改指针，不必移动数据元素。
2.缺点
（1）每一个结点附加指针域（存储密度小于1），空间利用率低。（2）非随机存储结构，查找定位操作需从头指针处罚顺着链表扫描。
- 6 -
数据结构
第五章 数组和广义表
一、定义
数组中的每个数据元素都对应于一组下标( j1，j2，…，jn)，每个下标的取值范围是0≤ji≤bi-1， bi称为第i维的长度(i=1，2，…，n)。
我们可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。
数组只有存取元素和修改元素值的操作。一般不作插入或删除操作。
二、顺序表示和实现：以列序为主序( column major order)和以行序为主序(row major order)。 假设每个数据元素占L个存储单元，则二维数组A中任一元素的存储位置可由下式确定： LOC(i，j) = LOC(0，0) + (b2*i+j) L
其中LOC(i，j)是aij的存储位置；LOC(0，0)是a00的存储位置，即二维数组A的起始存储位置，亦称为基地址或基址。
三、压缩存储：为多个值相同的元只分配一个存储空间；对零元不分配空间。
1、特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律；反之，称为稀疏矩阵。
（1）对称矩阵：为每一对对称元分配一个存储空间，则可将n2个元压缩存储到，n(n+1)/2个元的空间中。以行序为主序存储其下三角(包括对角线)中的元。
假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系。
（2）三角矩阵。所谓下(上)三角矩阵是指矩阵的上 (下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵。除了和对称矩阵一样，只存储其下(上)三角中的元之外，再加一个存储常数c的存储空间即可。
（3）对角矩阵。所有的非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其它的元皆为零。按某个原则(或以行为主，或以对角线的顺序)将其压缩存储到一维数组上。
- 7 -
数据结构
2、稀疏矩阵
假设在m*n的矩阵中，有t个元素不为零。令δ=t/(m*n),称δ为矩阵的稀疏因子。通常认为δ≤0.05时称为稀疏矩阵。
稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。一个三元组（i, j, aij)唯一确定了矩阵A的一个非零元。
例如：三元组表((1，2，12),(1，3，9),(3，1，-3),(3，6，14),(4，3，24),(5，2，18),(6，1，15),(6，4，-7)) 加上(6，7)这一对行、列值表示的矩阵：
（1）三元组顺序表
转置运算：(1)将矩阵的行列值相互交换；(2)将每个三元组中的i和j相互调换；(3)重排三元组之间的次序。
（2）行逻辑链接的顺序表 （3）十字链表
当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。
在链表中，每个非零元可用一个含五个域的结点表示，其中i，j和e三个域分别表示该非零元所在的行、列和非零元的值，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。
[例如]：矩阵M的十字链表
三元组顺序表的转置
四、广义表
1、定义：LS= (α1， α 2，… αn ) 其中，LS是广义表(α1， α2，… αn )的名称，n是它的长度。
在线性表的定义中，αi(1≤i≤n)只限于是单个元素。而在广义表的定义中，αi可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS非空时，称第一个元素α1为LS的表头(Head)，称其余元素组成的表(α2， α 3，… αn )是LS的表尾(Tail)。
- 8 -
数据结构
例如：
(1)A=( )——A是一个空表，它的长度为零。
(2)B=(e)——列表B只有一个原子e，B的长度为1。
(3)C=(a，(b，c，d))——列表C的长度为2，两个元素分别为原子a和子表(b，c， d)。
(4)D=(A，B，C)——列表D的长度为3，三个元素都是列表。显然，将子表的值代入后，则有D=(( )，(e)，(a，(b，c，d)))。
(5)E=(a，E)——这是一个递归的表，它的长度为2。正相当于一个无限的列表E=(a，(a，(a，… )))。 2、存储：链式
需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。一个表结点可由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。
- 9 -
数据结构 第7章 图
一、在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 二、概述
顶点（数据元素） 顶点之间关系 例：
V VR 有向图 弧（弧头v，弧尾w） 无向图 边
（a)有向图G1 (b)无向图G2
G1=(V1,{A1})，其中：V1={v1,v2,v3,v4}；A1={
G2=(V2,{A2})，其中：V2={v1,v2,v3,v4,v5}；A2={(v1,v2),(v1,v4),(v2,v3) ,(v2,v5),(v3,v4),(v3,v5)} 三、术语
用n表示图中顶点数目，用e表示边或弧的数目，不考虑顶点到其自身的弧或边：
1、无向图，e的取值范围是0到n(n—1)/2。有n(n—1)/2条边的无向图称为完全图(Completedgraph)。 2、有向图，e的取值范围是0到n(n—1)。具有n(n—1)条弧的有向图称为有向完全图。
3、有很少条边或弧(如e 4、有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权(Weight)。表示从一个顶点到另一个顶点的距离或耗费。 5、带权的图通常称为网(Network)。 6、子图：假设两个图G=(V,{E})和G’=(V’,{E’})，如果V’是V的子集，且E’是E的子集，则称G’为G的子图（Subgraph)。 7、度 对于无向图G=(V，{E})，如果边(v，v’)∈E，则称顶点v和v’互为邻接点(Adjacent)，即v和v’相邻接。边(v, v’)依附(Incident)于顶点v和v’，或者说(v, v’)和顶点v和v’相关联。顶点v的度(Degree)是和v相关联的边的数目，记为TD(v)。[例如]，G2中顶点v3的度是3。 对于有向图G=(V，{A})，如果弧 8、路径 - 10 -