第一章 数据结构与算法
1．1 算法
一、算法的基本概念
算法是指解题方案的准确而完整的描述。
　　 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个算法是可解的。
程序的编制不可能优于算法的设计。
　　 1、算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。
　　 2、算法的基本要素
　　 对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输。
　　 算法的控制结构：指算法中各操作之间的执行顺序。
　　 3、算法的基本设计方法
　　 列举法：根据提出的问题，列举所有可能的情况，并用给定的条件检验哪些是需要的。
　　 归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。
　　 递推：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
　　 递归：
　　 减半递推技术
二、算法复杂度
　　 1、算法的时间复杂度
　　 算法的时间复杂度是指执行算法所需要的计算工作量。
　　 算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。即：算法的工作量=f(n)。
　　 对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，这时分析算法工作量的方法可以用平均性态法和最坏情况复杂性法。
　　 2、算法的空间复杂度
1．2 数据结构的基本概念
　　 数据结构研究三方面内容：数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算。
一、数据结构的基本概念
　　 1、数据的逻辑结构：有两个要素，一是数据元素的集合，记作D；二是D上的各数据元素的前后件关系，记作R，即：B=（D，R）。
　　 2、数据的存储结构：数据的逻辑结构在计算机存储空间中的存放形式（也称物理结构），常用的有顺序、链接、索引等。
二、数据结构的图形表示
数据集合中的每一个元素用中间标有值的方框表示，称作数据结点，用一条有向线段表示其前后件关系，形成数据结构的图形化表示。
三、线性结构与非线性结构
　　 如果一个非空的数据结构满足下列两个条件：
　　 （1）有且只有一个根结点
　　 （2）每一个结点最多有一个前件，也最多有一个后件。
　　 则称此数据结构为线性结构，也称线性表。
1．3 线性表及其顺序存储结构
一、线性表的基本概念
　　 结构特征：
　　 （1）有且只有一个根结点，它没有前件。
　　 （2）有且只有一个终端结点，它没有后件。
　　 （3）除根结点和终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。
　　 线性表中结点的个数n称线性表的长度，当n=0时，称为空表。
二、线性表的顺序存储结构
　　 特点：
　　 （1）线性表中所有元素所占空间是连续的。
　　 （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
三、顺序表的插入运算算法
四、顺序表的删除运算算法
1．4 栈和队列
一、栈及其基本运算
　　 1、栈是从一端进行插入与删除的线性表。它的特点是先进后出。
　　 2、基本运算
　　 （1）入栈运算：TOP增1，将数据插入TOP的位置。
　　 （2）退栈运算：取栈顶元素，TOP减1。
　　 （3）读栈顶元素。
二、队列及其基本运算
　　 1、队列是允许在一端进行插入、在另一端进行删除的线性表。它的特点是先进先出。
　　 2、循环队列：队列首尾相接
　　 （1）入队运算：队尾指针（rear）进一，插入数据，如果rear=m+1，则rear=1。
　　 （2）退队运算：队首指针（front）进一，读取数据，如果front=m+1，则front=1。
　　 循环队列要有一个标志s：s=0表示队列为空，s=1且front=rear，表示循环队列满。
1．5 线性链表
　　 1、线性表的链式存储结构称作线性链表，在线性表中的每一个数据元素为一个存储结点，把存储结点所占空间分成两部分，一部分用于存储数据，称作数据域，另一部分用于存储下一个数据元素的存储地址，称作指针域。
　　 2、线性链表的运算：查找指定元素的方法、插入结点的方法、删除指定结点的方法。
　　 3、循环链表
　　 （1）在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
　　 （2）循环链表中最后一个结点的指针域指向表头结点。
1．6 树与二叉树
一、树的基本概念
　　 1、子结点与叶子结点
　　 2、一个结点所拥有的后件个数称为该结点的度。
　　 3、树的最大层次称为树的深度。
　　 4、以某结点的一个子结点为根构成的树称为该结点的一棵子树。
二、二叉树及其基本性质
　　 1、二叉树：具有以下两个特点
　　 （1）非空二叉树只有一个根结点。
　　 （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
　　 2、满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
　　 3、完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
　　 4、性质
　　 （1）在二叉树的第K层上，最多有2k-1(k>=1)个结点。
　　 （2）深度为m的二叉树最多有2m-1个结点。
　　 （3）在任意一棵二叉树中，度为0的结点总是比度为2的结点多一个。
　　 （4）具在n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取log2n的整数部分。
　　 （5）具有n个结点的完全二叉树的深度为[log2n]+1。
　　 （6）设完全二叉树共有n个结点，如果从根结点开始，按层序（第一层自左到右）用自然数给结点进行编号，则对于编号为k的结点有以下结论：
　　　　　 若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)。
　　　　　 若2k<=n，则编号为k的结点的左子结点编号为2k，否则该结点无左子结点。
　　　　　 若2k+1<=n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。
三、二叉树的遍历
　　 1、前序遍历
　　　　 若二叉树为空，则结束返回。
　　　　 否则：
　　　　 （1）访问根结点。
　　　　 （2）前序遍历左子树。