1、线性表的逻辑结构

    

    线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基

    

    本特点是线性表中的数据元素是有序且是有限的。在这种结构中：

    

    1 存在一个唯一的被称为“第一个”的数据元素；

    

    2 存在一个唯一的被称为“最后一个”的数据元素；

    

    3 除第一个元素外，每个元素均有唯一一个直接前驱；

    

    4 除最后一个元素外，每个元素均有唯一一个直接后继。

    

    例如： 线性序列 a1，a2， …an 线性表：是由 n(n≧0)个数据元素(结点)a1，a2， …an 组成的有限序列。该序列中的

    

    所有结点具有相同的数据类型。其中数据元素的个数 n 称为线性表的长度。

    

    当 n=0 时，称为空表。

    

    当 n＞0 时，将非空的线性表记作： (a1，a2，…an)

    

    a1 称为线性表的第一个(首)结点，an 称为线性表的最后一个(尾)结点。

    

    a1，a2，…ai-1 都是 ai(2≦i≦n)的前驱，其中 ai-1 是 ai 的直接前驱;

    

    ai+1，ai+2，…an 都是 ai(1≦i ≦n-1)的后继，其中 ai+1。

    

    2、顺序表

    

    顺序存储 ：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这

    

    种方法存储的线性表简称顺序表。

    

    有非空的线性表：(a1，a2，…an) 。顺序存储如图所示。

    

    顺序存储的线性表的特点：

    

    ◆ 线性表的逻辑顺序与物理顺序一致;

    

    ◆ 数据元素之间的关系是以元素在计算机内

    

    “物理位置相邻”来体现。设有非空的线性表：(a1，

    

    a2，…an) 。顺序存储如图所示。

    

    设线性表的每个元素需占用 l 个存储单元，以所

    

    占的第一个单元的存储地址作为数据元素的存储位

    

    置。则线性表中第i+1个数据元素的存储位置Loc(ai+1)

    

    和第 i 个数据元素的存储位置 Loc(ai)之间满足下列关

    

    系： Loc(ai+1)=Loc(ai)+l

    

    线性表的第 i 个数据元素 ai 的存储位置为：数组具有随机存取的特性

    

    Loc(ai)=Loc(a0)+(i)*l

    

    在高级语言(如 c 语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序

    

    表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用

    

    结构类型来定义顺序表类型。

    

    #defe AxSIZE 100 \/\/数组最大长度

    

    typedef struct { \/\/定义线性表结构体

    

    t data[AxSIZE]; \/\/线性表存储元素的数组

    

    ih; \/\/记录线性表的长度

    

    } *SqList; \/\/线性表的名称

    

    顺序表小结。

    

    1、单链表的定义

    

    链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表

    

    简称线性链表。

    

    为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后

    

    继结点的地址(或位置)，称为指针(poter)或链(lk)，这两部分组成了链表中的结点结构，

    

    链表是通过每个结点的指针域将线性表的 n 个结点按其逻辑次序链接在一起的。