定义：线性表L是n(n>=0)个具有相同属性的数据元素组成的有限序列。其中，序列中元素的个数n称为线性表的长度。
1. 顺序表：线性表的顺序存储（物理地址连续），存取速度高效，通过下标来直接存储。其结构定义如下：
struct SqList
{
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
};
在上述定义中，数组指针elem指示线性表的基地址，length表示线性表的的当前长度，listsize表示当前分配的存储空间大小。其算法实现在bo2-1.cpp中。
2. 链表：用一组任意的存储单元存储线性表的数据元素。
- 单链表类型的链表结构定义如下：
//线性表的单链表存储结构
struct LNode
{
ElemType data;
LNode *next;
};
typedef LNode *LinkList;
假设，L是Linklist型的变量，则L为单链表的头指针，一般情况下单链表包含一个头结点，L指向该head头，heda存储第一个结点的地址。算法实现在CH2中的bo2-2.cpp中。其结构图如下：
单链表结构图
- 循环单链表：表中最后一个结点的指针指向头结点，整个链表形成一个环。算法实现在bo2-4.cpp中。其结构图如下：
循环单链表结构图
- 双向链表：双向链表有两条方向不一样的链，即每个节点中除了next域存放后继结点地址外，还增加一个指向其直接前驱的指针prior。算法实现在bo2-5.cpp中。其结构图如下：
双向链表结构图
- 更完善的链表 上述介绍的链表和实际运用有一定的差距。定义如下链表结构：
typedef struct LNode // 结点类型
{
ElemType data;
LNode *next;
}*Link,*Position;
struct LinkList // 链表类型
{
Link head,tail; // 分别指向线性链表中的头结点和最后一个结点
int len; // 指示线性链表中数据元素的个数
};
其算法由bo2-6.cpp实现，并由main2-6.cpp验证其算法。链表结构图如下所示：
链表结构图
节点结构如下图：
节点结构图
空表结构如下图：
空表结构
具有两个节点（并含有一个头结点）的链表如图：
具有两个节点的链表结构
关键算法：
1）创建结点
void MakeNode(Link &p,ElemType e)
{ // 分配由p指向的值为e的结点。若分配失败，则退出
p=(Link)malloc(sizeof(LNode));
if(!p)
exit(ERROR);
p->data=e;
}
2）初始化一个链表
void InitList(LinkList &L)
{
Link p;
p=(Link)malloc(sizeof(LNode)); // 生成头结点
if(p)
{
p->next=NULL;
L.head=L.tail=p;
L.len=0;
}
else
exit(ERROR);
}
3）往一个结点h后面插入一个节点s,当h为(L.head)头结点时，将s插入在头结点之后;当h为(L.tail)最后一个节点时，把s插在最后面。
void InsFirst(LinkList &L,Link h,Link s)
{ // h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前
s->next=h->next;
h->next=s;
if(h==L.tail) // h指向尾结点
L.tail=h->next; // 修改尾指针
L.len++;
}
4）将指针s(s->data为第一个数据元素)所指(彼此以指针相链，以NULL结尾)的一串结点链接在线性链表L的最后一个结点之后，并改变链表L的尾指针指向新的尾结点
void Append(LinkList &L,Link s)
{
int i=1;
L.tail->next=s;
while(s->next)
{
s=s->next;
i++;
}
L.tail=s;
L.len+=i;
}
