2.1 线性表的定义和基本操作

2.1.1 线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当 $n=0$ 时线性表是一个空表。若用 $L$ 命名线性表，则其表示为： $L=(a_1,a_2,a_3,a_4,a_5...,a_i,...,a_n)$ ，式中， $a_1称为表头元素，$ a_n$称为表为元素，除第一个元素外，所有元素都只有一个直接前驱，除最后一个元素外，所有元素都只有一个直接后驱。

故线性表的特点如下：

表中元素个数有限
表中元素具有逻辑上的顺序，元素之间有其先后顺序
表中元素都是数据元素，每个元素都是单个元素
表中元素的数据类型都相同，即每个元素占有相同大小的存储空间
表中元素具有抽象性，即仅讨论元素之间的逻辑关系，而不考虑元素究竟表示什么内容

2.1.2 线性表的基本操作

InitList(&L):初始化
Length(&L):求表长
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
GetElem(L,i)：按位查找操作。返回表中第i个位置的元素
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的怨怒是，并用e返回删除元素的值
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值
Empty(L)：判空操作。若L为空表，返回true，否则返回false
DestroyList(&L)：销毁操作。释放内存空间

2.2 线性表的顺序表示

2.2.1 顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第一个元素存储在线性表的起始位置，第i个元素存储在线性表的第i个位置，紧接着便是第i+1个元素，称i为元素 $a_i$ 在线性表中的位序。因此，顺序表的特点式表中元素的逻辑顺序与其物理顺序相同。

每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的查那个书，因此线性表中的任意数据元素都可以随机存取。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

线性表中的位序是从1开始的，而数组下标式从0开始的

静态分配的线性表的顺序存储类型可以被表述为：

#define MaxSize 50         //线性表的最大长度
typedef struct {
    ElemType data[MaxSize];//顺序表的元素
    int length;            //顺序表当前的长度
}SqList                    //顺序表的类型定义

动态分配的线性表的顺序存储类型可以被表述为：

#define InitSize 50        //线性表的初始长度
typedef struct {
    ElemType *data         //顺序表的元素
    int length;            //顺序表当前的长度
}SqList                    //顺序表的类型定义

动态分配的线性表初始化时需要对data进行内存空间分配，分配空间大小可以动态变化，若空间不足，可以额外申请一块更大的连续内存将数据复制过去后，再释放原内存，但前提是系统内存空间足够。

顺序表最主要的特点是随机访问，访问指定序号的元素的时间复杂度为 $O(1)$

顺序表的存储密度高，每个节点只存储数据元素，没有额外的指针域。

2.2.2 顺序表上基本操作的实现

······

2.3 线性表的链式表示

顺序表可以随时存取表彰的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动怨怒是，而只需要修改指针，但也会失去顺序表可以随机存取的优势。

2.3.1 单链表的定义

线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。单链表节点描述为：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
)LNode,*LinkList;

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费空间的缺点。由于节点的离散存储，所以单链表不支持随机存取。

通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。此外为了操作方便，在第一个存储数据的节点之前附加一个节点，称为头节点，头节点可以存储单链表长度，也可以不存储任何信息。