2.1 线性表的基本概念

• 线性表（linear list）是数据结构的一种，一个线性表是 n 个具有相同特性的数据元素的有限序列，数据元素又称为结点。
• 线性表的特征：
  • 结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点有且仅有一个直接前驱；除终端结点没有直接后继外，其他每个结点有且仅有一个直接后继。
• 线性表的基本运算：
  • 1.初始化；2.求表长；3.读表元素；4.定位；5.插入；6.删除。
• 线性表的存储结构
  • 1.顺序存储结构
  • 2.链式存储结构：（单链表、对链表）
• 参考阅读
  • 线性表的基本概念

2.2 线性表的顺序存储

1. 线性表顺序存储的类型定义
   • 一般使用数组来表示顺序表
   • 顺序表主要指数组，顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中逻辑相邻的元素也物理相邻，采用顺序存储结构的线性表通常称为顺序表。
2. 线性表的基本运算在顺序表上的实现

2.3 线性表的链接存储

1. 单链表的类型定义
2. 线性表的基本运算在单链表上的实现

2.4 其他运算在单链表上的实现

2.5 其他链表

1. 循环链表
2. 双向循环链表

2.6 顺序实现与链接实现的比较

2.7 小结

• 本章主要介绍线性表的基本概念、基本运算、线性表的顺序存储结构及基本运算的实现、线性表的链式存储结构及基本运算的实现。

思考与练习

1.填空题

1. 设 r 指向单链表的最后一个结点，要在最后一个结点之后插入 s 所指定的结点，需要执行的语句序列是；r=s; r->next=NULL。

2.应用题或解答题

1. 何时选用顺序表，何时选用链表作为线性表的存储结构？
2. 论述以下概念：指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。

3.算法设计题

1. 设线性表存放在数组 A[arrsize]的前 elenum 个分量中，且递增有序。试写一算法，将 x 插入到线性表的适当位置上，以保持线性表的元素仍然是递增有序的，并分析算法的时间复杂度。
2. 设带头结点的单链表的结点结构如下：

   struct node {
     DataType data;
     struct node *next;
   } Node, *LinkList;

   试编写一个函数 int count(LinkList head, DataType x)统计单链表中数据域为 x 的结点个数。
3. 试编写在不带头结点的单链表上实现线性表基本运算 LENGTH(L)的算法。
4. 假设有两个按元素值递增有序排列的且带头结点的单链表 A 和表 B，请编写算法将表 A 和表 B 合并成一个按元素值递减有序排列的单链表 C，并要求利用原表(即表 A 和表 B)的结点空间存放表 C。
5. 写出判断带头结点的单链表 L 的元素值是否是递增的算法。