数据结构和算法.doc

算法
算法是指对解题方案的准确而完整的描述。
程序的编制不可能优于算法的设计。
算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
算法设计的基本方法：列举法、归纳法、递推法、递归法、减半递推法、回溯法。
算法复杂度主要包括时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量（基本运算的执行次数），可以用平均性态和最坏情况复杂性两种方法进行分析。空间复杂度是指执行这个算法所需要的内存空间。
数据结构
数据元素：在数据处理领域中，每一个需要处理的对象。
数据对象：性质相同的数据元素的集合。
数据结构：相互关联的数据元素的集合。包括两方面的信息：表示数据元素的信息和表示各数据元素之间的前后件关系。
数据的逻辑结构：指反映数据元素之间逻辑关系的数据结构。有两个要素：一是数据元素的集合，记为D，二是D上的关系，记为R。一个数据结构可以表示成：B=（D,R）。
数据的存储结构：指数据的逻辑结构在计算机空间上的存放形式。
线性结构：非空的数据结构，满足有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。
线性表及其顺序存储结构
线性表的顺序存储结构的特点：所有元素所占的存储空间是连续的；各数据元素在存储空间中是按逻辑顺序依次存放的。
若长度为n的线性表采用顺序存储结构，删除第i个元素，需要依次向后移动n-i；插入则需要n-i+1。
栈和队列
栈是限定在一端进行插入与删除的线性表。（先进后出、后进先出）
队列是指允许在一端进行插入、而在另一端进行删除的线性表。（先进先出、后进后出）。
循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
队列空的条件是：s=0；队列满的条件是：s=1且front=rear。
线性链表
在链式存储方式中，结点由两部分组成：数据域和指针域。
线性表的链式存储结构的特点：所有元素所占的存储空间可以不连续的；各数据结点的存储方式中与数据元素之间的逻辑关系可以不一致，其由指针域来确定。
树和二叉树
在树结构中，一个结点所拥有的后件个数称为该结点的度。在树中，所有结点的最大度称为树的度。
树的最大层次称为树的深度。
二叉树的特点：非空二叉树只有一个根结点；每个结点最多有两棵子树，且分别称为该结点的左子树和右子树。
二叉树不是树的特殊情况。
二叉树的性质：在二叉树的第k层上，最多有2的k-1次方个结点；深度为m的二叉树最多有2的m次方-1个结点；在任意一棵二叉树中，度为0的结点总是比度为2的结点多一个；具有n个结点的二叉树，其深度为［㏒2n］+1(下取整)。
满二叉树：除了最后一层，每一结点的所有结点都有两个子结点的二叉树。满足1、2的性质。
完全二叉树：除最后一层外，每层的结点数都达到最大值的二叉树。
满二叉树是完全二叉树，但完全二叉树一般不是满二叉树。
前序遍历：根左右；中序遍历：左根右；后序遍历：左右根。
查找技术
二分法查找只适用于顺序存储的有序表。
对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较㏒2n次，而顺序查找则需要比较n次（无序的则需要n+1次）。
排序技术
在最坏情况下，冒泡排序法、简单插入排序法、简单选择排序法：需要比较次数为n(n-1)/2;快速排序法：需要比较的次数为n；希尔排序法：需要比较次数为O（n的1.5次方）；堆排序法：需要比较的次数为n㏒2n