2.1 线性表的定义和类型

建议：最好先学语言，再学数据结构。

什么是线性表？

我的理解是，线性餐桌就是你去烧烤店吃的羊肉串。 上面的羊羔数量有限，顺序也是有顺序的。 每块羊肉的正面和背面称为前身或后继者。 现在的前、后无前无后，其他的都在。

真实的说法是这样的：

如果该结构是非空有限集，则只有一个起始节点和一个终止节点，并且所有节点最多有一个直接前驱和一个直接后继。 可以表示为：(a1,a2,...,an)；

真实的特征表述是这样的：

① 只有一个第一个节点和一个最后一个节点；

② 除头节点和尾节点外，其他节点只有 1 个直接前驱节点和 1 个直接后继节点。

不管怎样，只要记住它们之间的逻辑关系是一对一的。

线性结构可以包括：线性表、栈、队列、字符串、数组等。

当然，最常用的就是线性表。

粗略地看一下下面的图片。 其实你只需要了解它、理解它就可以了。 没什么好说的。 我这里主要讲一下如何使用，尝试用自己对概念性东西的理解。

2-2 单链表的顺序存储结构

线性表的内容很多。 这里我们分几个章节来介绍。 让我们从最简单的单链表开始。

什么是单链表

节点只有一个指针字段的链表称为单链表或线性链表。

这是这个东西的示意图：

上图中，head为头指针，a1为头节点，a2为第一个节点。

头指针是指向链表中第一个节点的指针。

第一节点是指链表中存储第一数据元素a1的节点。

头节点是附加在链表第一个节点之前的节点； 数据字段中仅放置空表标记和表长度等信息。

当然这个东西可以是无头节点，也可以是头节点。

如图所示：

2-3 单链表的定义与实现

在实现之前，我们先来看看它们的优缺点：

优势

数据元素数量可以自由扩展，插入、删除等操作不需要移动数据，只需要修改链接指针，修改效率高。

缺点

存储密度小，存取效率不高。 必须采用顺序访问，即访问数据元素时只能按照链表的顺序访问（羊肉串到底）

如何表示空表？

当存在头节点时，头节点的指针字段为空，表示链表为空。

头节点的数据域包含什么？

头节点的数据字段可以为空，也可以存储线性表的长度等附加信息，但该节点不能包含在链表的长度值中。

下图是空表和非空表的示意图：

好了，进入今天的主题：

其实单链表的操作无非就是以下几点：初始化、链表长度、读取元素、判断是否为空、清空单链表、查找、插入等。

算法1：单链表初始化

/* 宏定义 */
#define LIST_INIT_SIZE 100 //顺序表存储空间的初始分配量 
#define LISTINCREMENT 10 //顺序表存储空间的分配增量
typedef int LElemType_Sq;
/* 状态码识别类型 */
typedef int Status;
typedef struct
{
LElemType_Sq *elem; //存储空间基址（指向第一个结点的指针） 
int length; //当前顺序表长度 
int listsize; //当前分配的存储容量 
}SqList; //顺序表0号单元正常使用 
Status InitList_Sq(SqList *L)
//构造一个空的线性结构L
{
(*L).elem = (LElemType_Sq*)malloc(LIST_INIT_SIZE*sizeof(LElemType_Sq));
if(!(*L).elem)
exit(OVERFLOW); //分配内存失败
(*L).length = 0; //初始化顺序表长度为0
(*L).listsize = LIST_INIT_SIZE; //顺序表初始内存分配量
return OK; //初始化成功 
}