*********************************************
            ---算法与数据机结构---

数据结构：由于计算机技术的发展，需要处理的对象不再是纯粹的数值，还有像字符，表，图像等具有一定结构的数据，需要用好的算法来处理这些数据。

我们把现实中大量而又复杂的问题以特定的数据类型的特定的存储结构保存到主存储器中，以及在此基础上为实现某个功能而执行的相应操作（查找排序），这个相应的操作也叫算法。

数据结构 = 个体 +个体的关系
算法 =对存储数据的操作

基础知识：
1.数据结构：（即数据元素之间的关系）
线性表：一对一
  顺序表示：数组
  链式表示：链表

操作受限的线性表：
  栈：先进后出
     线性栈（数组）
     链式栈（链表）
  队列：先进先出
      线性队列
      链表队列

 数据约束为字符集，操作对象通常以串的整体。（类似线性表）
  串：
 
非线性表：
   树：一对多
     二叉树

   图：多对多

数据在计算机中的存储方式：
顺序存储 ：内存分配连续的内存地址 。
链式存储：一个个不连续地址的节点通过指针连起来。

衡量算法的标准：
时间复杂度：T(n)=O(f(n))
空间复杂度：S(n)=O(f(n))
难易程度
健壮性

树：
专业定义：
  1.有且只有一个称为根的结点
  2.有若干个互不相交的子树，这些子树本身也是一棵树
通俗定义：
　１.树是由结点和边组成
　２.每个结点只有一个父节点但可以有多个子节点
　３.但有一个结点例外，该结点没有父节点，次结点称为根节点。　　

专业术语：结点　　父节点　子节点　子孙　　堂兄弟
深度：从根节点到最底层节点的层数称之为深度，根节点是第一层
叶子节点：没有子节点的节点
非终端节点：实际就是非叶子节点
度：字节点的个数

分类：
１.一般树：任意一个节点的个数都不受限制
２.二叉树：任意一个节点的子节点个数最多两个，且子节点位置不可更改（有序）
　　　　　　分类：１.一般二叉树
　　　　　　　　　２.满二叉树：在不增加层数的前提下，无法再多添加一个节点的二叉树。
　　　　　　　　　３.完全二叉树：如果只是删除了满二叉树最底层最右边连续若干个节点。
３.森林：ｎ个互不相交的树的集合。

树的存储：
　　　二叉树的存储：
　　　　　　连续存储－－数组（完全二叉树）
   优点：查找某个节点的父节点和子节点方便
　   缺点：耗用内存空间过大

　　　　　　链式存储－－链表

 一般树的存储
  双亲表示法：求父节点方便（数组）
  孩子表示法：求子节点方便（数组加链表）
  带双亲的孩子表示法：求父节点和子节点都很方便
  二叉树表示法：左指针域指向它的第一个孩子　（二叉链表）
    　右指针域指向它的下一个兄弟
    　把一个普通树转换成一个没有右子树的二叉树
  
 森林的存储
  把森林转换为二叉树，几个根节点为兄弟
  左第一个孩子，右下一个兄弟。

二叉树的操作
 遍历：
  先序遍历：根－>左 -> 右
  中序遍历：左－>根 -> 右
  后序遍历：左- >右－> 根
 
  已知两种遍历序列求原始二叉树　（必须知道中序）
  先序和中序：
  中序和后序：
树的应用：
 树是数据库中数据组织的一种重要形式
 树是操作系统子父进程的关系
 面向对象语言中类的继承关系
 赫夫曼树

---查找---
静态查找表：

顺序查找
从线性表的一端开始，顺序扫描，依次扫描的节点关键字与给定值K相比较，如果相等则查找成功，如果不相等则继续查找下一个结点，如果扫描结束仍没有找到关键字等于K的结点，则查找失败。
平均查找长度：ASL=1/2(n+1)  (如果算上查找不成功，则ASL=3/4(n+1))
优点：算法简单，适应面广，对表没什么要求。
缺点：查找长度较大，特别是n很大时，找找效率较低。

二分查找（有序表+顺序存储）
线性表中的节点按关键字排序，用给定值K与中间值比较，若相等则查找成功，不相等时，根据K与中间键值大小比较确定下一步查找那个子表，依次递归查找，知道查找结束。
平均查找长度：ASL=（n+1）/n(log2(n+1)-1)
当n较大时（n>50）：ASL=log2(n+1)-1 
优点：查找效率高
缺点：只适用于有序表，且限于顺序存储结构。（不能用于线性链表）

索引顺序表查找（分块查找）
将线性表分成若干块，每一块的存储顺序是任意的，但是块与块之间按关键字值大小有序排列，建立一个索引表，包括每块中最大关键字，和指针项指向每块的第一个记录位置。查找时，先用顺序查找或折半查找找到给定值所属的块，再在对应的块中顺序查找到键值相等的元素，没有则返回失败。
平均查找长度：ASL=L1+L2=1/2(n/s+s)+1
第一步用折半查找时，ASL=log2(n/s+1)+s/2
优点：比顺序查找快，比折半查找慢。
确定：需要每块关键字有序。

ELEM_TYPE  elem[]={{0,0},{3,6},{23,64},{32,66},{42,98},{86,11},{99,37}};
SSTable sst={elem,SZ(elem)};

/*顺序查找*/
int Search_Seq(SSTable _sst,KEY_TYPE _key)
{
 int i;
 _sst.pElem[0].key=_key; //保存“哨兵”
    for(i=_sst.length;!EQ((_sst.pElem[i].key),_key)&& i>=1;i--)
 {
  ;
 }
 return i;

}

/*折半查找*/
int Search_Bin(SSTable _sst,KEY_TYPE _key)
{
 _sst.pElem[0].key=_key; //保存“哨兵”
 int low=1,high=_sst.length,mid;
 while(low<=high)
 {
  mid=(low+high)/2;
  if(EQ(_sst.pElem[mid].key,_key))
  {
   return mid;
  }
  else if(LT(_key,_sst.pElem[mid].key))
  {
   high=mid-1;
  }
  else
  {
      low=mid+1;
  }
 }
 return -1;
 
}

动态查找表：
  二排序叉树
  平衡二叉树
  B-树，B+树

哈希表查找
哈希表：根据设定的哈希函数D=H(key)和处理冲突方法将一组关键字映像到一个有限的连续的存储地址区间上，并以关键字的像作为记录在表中的存储位置，这种表称为哈希表，映像过程称为哈希造表或散列，所得存储位置称为哈希地址或者散列地址。
有了哈希表，查找不需要关键字一一比较，只需要根据关键值转换为哈希存储地址就可以找到记录了。

构造哈希表方法：
1.直接定址法
2.数字分析法
3.平方取中法
4.折叠法
5.除留余数法：H(key)=key MOD p , p<=m   ,关键字与小于表长的一个数取余。
6.随机数法

处理冲突方法：
1.开放定址法：H=(H(key)+d) MOD m ; d为增量数列
  线性探测再散列：d=1,2,3...
  二次探测再散列：d=1,2,3的平方...
  随机探测再散列：d为随机数
2.链地址法：相同哈希地址的数据元素放在一个链表中。

哈希文件：用哈希函数法组织的文件，在物理地址上不是相邻的，只能用磁盘存储。并且只适用于定长记录文件和按记录随机查找的访问方式。

Linux中，用哈希表的方式组织进程。可通过find_task_by_pid()快速找到对应的进程。
#include <linux/sched.h>

---排序方法---
 插入排序：
1.直接插入排序：将记录一个个插入到前面已经排好的有序表中。
  比较 -> 后移 -> 插入
时间复杂度 O(n2)

2.折半插入排序:减少了比较的次数，移动次数不变
时间复杂度 O(n2)

3.2-路插入排序：减少了移动的次数
4.表插入排序：不移动记录
5.希尔排序：插入排序的改进

快速排序：交换
1.冒泡法
  交换法
2.快速排序：是对冒泡法的改进

 选择排序
1.简单选择排序
2.树形选择排序
3.堆排序

归并排序

基数排序

直接插入排序、冒泡排序、直接选择排序：  O(n2)
快速排序、归并排序、堆排序:            O(nlog2n)
从最好情况考虑，直接插入排序和冒泡排序时间复杂度最好:O(n)
从最坏情况考虑，快速排序的时间复杂度为：O(n2)