一·基本数据结构与算法
算法基本概念
算法：解决问题的方法
程序：用某种语言来诠释算法，将算法写成代码。
算法基本特征：
1.可行性 2.确定性 3.有穷性 4.有足够的情报
算法的基本要素
1.算法种对数据对数据对象的运算和操作 2.算法的控制语句
算法设计的基本方法：
1.列举法 2.归纳法 3.递推法 4.减半递推法 5.递归法 6.回溯法
算法复杂度：
时间复杂度：是指执行算法所需要的计算工作量，是用算法所执行的基本运算次数来计算的，算法的工作量=f（n），n为问题的规模。分析算法的工作量：1）平均性态 2）最坏情况
空间复杂度：是指执行这个算法所需要的内存空间，算法执行所需要的存储空间包括：1）输入数据所占的存储空间 2）程序本身所占存储空间 3）算法执行过程中所需的额外空间
数据结构的定义
数据结构研究内容：1.逻辑结构 2.存储结构 3.对各种数据结构进行的运算
数据结构是指数据以及其关系
数据结构关系：1.线性结构 2.树状结构 3.网状结构 4.集合
数据逻辑结构
逻辑结构两个要素：1）数据元素的集合，通常记为D 2）D上的关系，反映了D种各数据元素之前的前后关系，通常记为R，即一个数据结构可表示为：B=(D,R)
数据的存储结构
数据在逻辑结构在计算机存储空间种存放方式
数据结构的图形中表示：根结点，终端结点（叶子结点），内部结点
线性结构与非线性结构：线性：一个非空的数据结构有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。非线性;不满足以上两个条件的数据结构就被成为非线性结构,主要为树状结构和图装结构。
线性表
线性表基本概念：线性表是最简单最常用的一种数据结构
存储结构：连续性，
插入与删除需要移动大量数据，效率低下，尤其是纯属表中数据较多的情况下尤为突出
栈与队列
栈：特殊的线性表，一端是封闭的（栈底），未封闭可以操作的一端（栈顶）。插入数据成为入栈，删除数据被成为出栈。入栈与出栈只能发生在栈顶。操作特定为先进后出
队列;插入数据应该是插入到对位，删除数据从队首删除。操作特点为先进先出
循环存储的循环队列：在实际应用中，比较有意义的一种形式，约定：front所指向的位置不作使用，必定为空。防止循环中出现队列为空于满队列之间无区别。
线性链表
（是否带头结点）
单链表
单向循环链表
双向链表
双向循环链表
运算：插入，删除。
| 类型 | 优点 | 缺点 |
|---|---|---|
| 顺序线性表 | 1.可随机存取表中任意结点 2.无需为表示结点间的逻辑关系额外增加存储空间 | 1.插入和删除的效率低2.存储空间不利于扩充3.不便于对存储空间的动态分配 |
| 链式线性表 | 1.在进行插入和删除是，只需改变指针，无需移动元素2.存储空间易于扩充并且方便空间动态分布 | 需要额外的空间开销，每个结点中需要以恶指针域来表示逻辑关系，存储密度必顺序表低 |
树状结构
二叉树的基本性质：
1）在二叉树的第K曾，最多有2^（k-1）个结点(k>=1)
2）深度为K的二叉树中，最多有2^k-1个结点
3）对任何一颗二叉树，度数为0的结点（叶子结点）总是比度为2的结点多一个
4）具有n个结点的二叉树，其深度至少为【log2n]+1,其中（log2n）表示log2n的整数部分
5）具有n个结点的完全二叉树的深度为（log2n）+1
6）设完全二叉树（）共有n个结点，如果从根结点开始，按层序用自然数进行编号，有以下结论：1.若i=1，则结点为根结点，它没有父结点，若i>1，则结点的父结点编号为i/2（取整），左子结点为2i，右子结点为2i+1
存储：链式存储
遍历：前序（根，左，右），中序（左，根，右），后序（左，右，根），按层（层次关系）
查找和排序
查找：顺序查找，二分法查找
一，顺序查找：顺序搜索：最理想情况下，比较次数为1，最坏情况为n，平均情况需要比较n/2次，所以查找算法的时间复杂程度为O（n）
二，二分法查找：折半查找，需要满座条件：1.用顺序存储结构，2.线性表是有序表
长度为n的有序线性表，在最坏情况下，二分查找需要比较log2n次
排序：交换类排序法，插入类排序法，选择类排序法
交换类排序法：
冒泡排序法：简单的交换类排序方法，通过相邻的两个数对比进行交换，长度为n的线性表排序，冒泡排序需要经过n/2便的从前往后的扫描和n/2便从后往前扫描
快速排序：冒泡排序的改进，平均时间的平均时间效率为O（log2n），最坏情况下时间效率为O(n2),所有排序算法中最快的一种。
插入类排序：
简单插入排序法：组织两个表，有序表和无序表，依次取出无序表中内容，插入到有序表中相应的位置，最好情况下，即为初始排序序列就是有序的情况，简单插入排序的比较次数n-1次，移动次数为0次，最坏ide情况下，即为初始排序是逆序，比较次序为n（n-1）/2次，移动次数是n（n-1）/2.平均比较次数和平均移动次数都约为n2/4，所有直接插入排序时间复杂程度为O（n^2）
希尔排序法：将整个无序序列分割成若干个小的子序列进行插入排序，最坏情况下，希尔排序所需要的比较次数为O(n1.5)
选择排序法：
简单选择排序：直接从目前的排序范围内找到最小的一个，放在第一个元素位置，其余以此类推。最坏情况下需要比较n（n-1）/2次
推排序法：对大量数据元素高效，需要比较次数为O（nlog2n）。
| 方法 | 平均时间 | 最坏情况 | 辅助存储 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(1) |
| 快速排序 | O(nlog2n) | O(n^2) | O(log2n) |
| 简单插入排序 | O(n^2) | O(n^2) | O(1) |
| 简单选择排序 | O(n^2) | O(n^2) | O(1) |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(1) |
上述没有包括希尔，以为其时间效率于所取的增量序列有关，最坏情况下，所需比较次数为O（n^1.5）