表(a1, a2,……,an)的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。
有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点，它指向表中第一个结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。
在单链表中，取得第I个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构 链表的形式：单向，双向
2.线性单链表的存储结构
3带链
3.带列的栈与队列
栈也是线性表，也可以采用链式存储结构。
队列也是线性表，也可以采用链式存储结构。
十三.线性链表的基本运算 1.线性链表的插入 2.线性链表的删除
十四.双向链表的结构及其基本运算
在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。
十五.循环链表的结构及其基本运算
是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任一结点出发均可找到表中其他结点。
十六.树的定义
树是一种简单的非线性结构。树型结构的特点：
1.每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。
2.每一个结点可以有多个后件结点，称为该结点的子结点。没有后件的结点称为叶子结点
3.一个结点所拥有的后件个数称为树的结点度
4.树的最大层次称为树的深度。
十七.二叉树的定义及其基本性质
1.二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
2.二叉树的基本性质
①在二叉树的第I层上至多有2i-1个结点。
②深度为k的二叉树至多有2k-1个结点(k>=1)
③在任意一个二叉树中，度为0的结点总是比度为2的结点多一个；
④具有n 个结点的二叉树，其深度至少为[log2n]+1。
一棵深度为k且有2k-1个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。
3.满二叉树与完全二叉树
满二叉树：除最后一层以外，每一层上的所有结点都有两个子结点。在满二叉树的第K层上有2K-1个结点，且深度为M的满二叉树右2M-1个结点
完全二叉树：除最后一层以外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有N个结点的完全二叉树的深度为[log2n]+1
完全二叉树总结点数为N，
若N为奇数，则叶子结点数为（N+1）/2 若N为偶数，则叶子结点数为N/2
4.二叉树的存储结构
二叉树通常采用链式存储结构
二叉树具有下列重要特性：
性质1 在二叉树的第i层上至多有2i-1个结点(i≥1)。
利用归纳法容易证得此性质。
i=1时，只有一个根结点。 显然，2i-1=20=1是对的。
现在假定对所有的j，1≤j 由归纳假设：第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为 2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i-2=2i-1。
性质2 深度为k的二叉树至多有2k-1个结点，(k≥1)。
由性质1可见，深度为k的二叉树的最大结点数为
k k
∑(第i层上的最大结点数) =∑2i-1=2k -1
i=1 i=1
性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
设n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2所以其结点总数为
n=n0+n1+n2 (6—1)
再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点射出的，所以又有B=n1+ 2n2。
n=n1+2*n2+1 (6—2)
于是得由式(6—1)和(6—2)得 n0=n2+1
十八.二叉树的遍历
就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。一般先左后右。
1.前序遍历DLR 首先访问根结点，然后遍历左子树，最后遍历右子树。
2.中序遍历LDR 首先遍历左子树，然后根结点，最后右子树
3.后序遍历LRD 首先遍历左子树，然后遍历右子树，最后访问根结点。
十九.顺序查找与二分查找
1.顺序查找 在两种情况下只能用顺序查找：线性表为无序表、链式存储结构的有序表
2.二分查找 只适用于顺序存储的有序表（从小到大）。
对于长度为N的有序线性表，在最坏情况下，二分查找只需要比较log2N次，而顺序查找要比较N次。 排序：指将一个无序序列整理成按值非递减顺序排列的有序序列。
二十.交换类排序法
冒泡排序与快速排序法属于交换类的排序方法
1.冒泡排序法 假设线性表的长度为N，则在最坏的情况下，冒跑排序需要经过N/2遍的从前往后的扫描和N/2遍的从后往前的扫描，需要的比较次数为N（N-1）/2
2.快速排序法
二十一.选择类排序法 1.简单选择排序法 2.堆排序法
二十三.插入类排序法 1.简单插入排序法2.希尔排序法
最坏情况下 最好情况下 说明
交换排序 冒泡排序 n(n-1)/2 最简单的交换排序。在待排序的元素序列基本有序的前提下，效率最高
快速排序 n(n-1)/2 O(Nlog2 N)
插入排序 简单插入排序 n(n-1)/2 每个元素距其最终位置不远时适用
希尔排序 O(n1.5)
选择排序 简单选择排序 n(n-1)/2
堆排序 O(nlog2n) 适用于较大规模的线性表
练习：
1.栈和队列的共同特点是（只允许在端点处插入和删除元素）
2.如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（e2,e4,e3,e1）
3.栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（DCBEA）
4.栈通常采用的两种存储结构是（线性存储结构和链表存储结构）
5.下列关于栈的叙述正确的是（D）
A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征
6.链表不具有的特点是（B）A.不必事先估计存储空间 B.可随机访问任一元素
C.插入删除不需要移动元素 D.所需空间与线性表长度成正比
7.用链表表示线性表的优点是（便于插入和删除操作）
8.在单链表中，增加头结点的目的是（方便运算的实现）
9.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表）
10.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D）
A.每个元素都有一个直接前件和直接后件 B.线性表中至少要有一个元素
C.表中诸元素的排列顺序必须是由小到大或由大到小
D.除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件
11.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）
A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续不连续都可以
12.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构）
13.树是结点的集合，它的根结点数目是（有且只有1）
14.在深度为5的满二叉树中，叶子结点的个数为（31）
1