一、学习内容

一、算法

1、算法的概念：解决问题的步骤与方法。

2、特点：可行性、确定性、有穷性（与程序的最大区别）、输出（n>=1） 

3、设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。 

4、复杂度：时间和空间（没有直接关系）

二、数据结构

1、概念：相互有关联的数据元素集合，即数据的组织形式。

2、逻辑结构

3、存储结构：顺序存储、链式存储、索引存储、散列存储。

4、分类：线性结构（有且只有一个根节点，每个节点最多有一个前驱和一个后继的非空数据结构）；非线性结构

三、栈和队列——线性表

1、栈：插入或删除只在一端进行，称为“先进后出”或“后进先出”表

2、队列：允许在一端进行插入，另一端进行删除的线性表，称“先进先出”表

3、循环队列：队列中的元素个数随队头指针与队尾指针的变化而动态变化

四、线性链表

1、概念：在定义的链表中，若只含有一个指针域来存放一个元素地址，称这样的链表为单链表或线性链表。

2、节点由两部分组成：数据域、指针域

五、树

1、非线性结构，有且仅有一个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限集合，称为子树。

2、父节点（根）、子节点（叶子）、度（最大后件个数）、深度（最大层）

  根节点：A   ；叶子节点：J、M、N、L、C、G、H、I；度：3；深度：5

六、二叉树

1、特殊的树——二叉树（满二叉树、完全二叉树）

2、二叉树的基本性质（重要）

    1）第k层节点最多

    2）深度为m的二叉树至多有-1个节点

    3）二叉树的叶子节点总比度为2的节点多一个

    4）具有n个节点的二叉树深度至少为[]取整+1

3、遍历：前序遍历、中序遍历、后续遍历

图2-18    前序：MNAEPQFRBGHOCIJDKL           中序：PEQARFNGBHMICJOKDL     

               后序：PQERFAGHBNIJCKLDOM

七、查找和排序

1、查找：顺序、二分

2、排序

    1）交换类：冒泡、快速

    2）插入类：简单插入n（n-1）/2、希尔排序

    3）选择类：简单选择、堆排序O（n）

二、随堂测验