当前课程知识点：数据结构 > 第2章 线性表 > 2.1 概念及ADT > 讲解
同学们，今天我们来学习第二章——线性表
本章主要包含以下四节内容
先进入第一节——概念及ADT。先来看线性表的相关概念
线性表是由若干元素构成的有限序列
这里要强调的是序列。若干个元素
它们之间是有位序
区分的。比如，记一个线性表L
它等于n个元素
a1
到an，如果把它抽象成图
就是元素与元素之间有一对一的关系
第一个元素是表头，最后一个元素是表尾
这里的n
就是表长
也就是一个线性表当中，包含的元素个数
如果
n等于0
那就是空表
a(i-1)称为ai的前驱
注意，a1是没有前驱的
a(i+1)是ai的后继
同样，最后一个元素
an是没有后继的
下面是线性表的特性
在讲线性表的特性的时候
包括以后每一个数据结构的特性的时候
我们讲的都是它的逻辑特性
跟计算机实现是没有任何关系的
对于任何一个非空的线性表，有以下的一些特性
第一，有且仅有一个表头元素
也就是刚才说的a1
有且仅有一个表尾元素
也就是an。除表头外
其他元素有且仅有一个前驱
也就是说
除了a1没有前驱，其他的n-1个元素都是有
一个而且仅有一个前驱
类似地
除了表尾外
除了an外
每一个元素都有一个后继
下面是线性表的抽象数据类型定义
元素和关系，采用自然语言
数学语言来描述都可以
这里的每一个元素来自于一个集合，叫ElementSet——元素集合
这个元素集合到底是什么呢
取决于你要表达的现实应用
比如，你描述的是一个由若干学生构成的序列
那这里的元素集合可能是学生
如果你描述的是
若干个订单构成的序列
那么，它可能是一个订单。关系呢
a(i-1)和ai
它们是前驱和后继的关系
是一种偏序关系
下面，我们来看操作部分。第一个操作init——初始化
L从无到有
在内存当中，建立出一个线性表L的结构
那么，肯定要修改L
所以，在L的前面有一个引用参数
第二个操作——销毁，L在内存当中，从有到无，L也要被修改
所以，它也有引用参数
第三个操作
isEmpty，判断线性表
L是否为空
也就是，它的表长n
是否等于0。这个操作
并没有用返回值
而是用第二个参数empty，来接收最后的结果
如果表长为空
我们把empty修改成1
否则修改成0
所以，第二个参数前面有引用参数的语法。第四个操作getElem——得到线性表
L第i个位置的元素，把它放到e里面
e需要被修改
第五个操作
在线性表L的第i个位置之前，插入元素e
L也要被修改
最后一个操作，删除线性表L的第i个元素
我们把被删除的元素也放到e里面
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
