注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Leo

笑:胸怀,傲:实力,才能笑傲江湖。

 
 
 

日志

 
 

数据结构和算法  

2017-06-15 22:03:10|  分类: 技术管理 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、表、栈、队列
1、表:最基本的链表,单向双向链表,环形链表等,最基本的数据结构,在很多STL容器中,都是以链表来实现的。
2、栈:是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶。对于栈的操作,有push入栈和pop出栈,插入和删除操作。栈是后进先出,和STL中的stack栈类似。
3、队列:像栈一样,队列也是表。在队列的一端删除,另外一段插入,也就是先进先出,比较常用。可以用链表实现,也可以用循环数组实现。

二、树
1、树的实现:一种方法是在每一个节点除数据外还要有一些指针,是的该节点的每一个儿子都有一个指针指向它。然而由于每个节点的儿子数是变化的且事先并不知道,因此无法实现预先设定个数,否则会很浪费空间。简单的方法就是每个节点的所有儿子都放在树节点的链表中。
2、每次插入和删除,都是调用malloc申请空间,使用之后可以free释放掉,用多少申请多少。
3、AVL树:带有平衡条件的二叉查找树,这个平衡条件必须要容易保持,而且它必须保证树的深度是O(logN),最简答的想法就是要求左右子树具有相同的高度。

三、散列
1、散列是一种用于以常数平均时间执行的插入、删除和查找的技术;
2、理想的散列表数据结构只不过是一个包含有关键字的具有固定大小的数组;
3、每个关键字被映射到从0到TableSize-1的这个范围之中的某一个数,并且被放到合适的单元中;
4、我们需要寻找一个散列函数,该函数要在单元之间均匀地分配关键字;
Index Hash(const char *Key, int TableSize) { 
unsigned int HashVal = 0; 
while (*Key != '\0') {
HashVal = (HashVal << 5) + *Key++; 
}
 return HashVal % TableSize; 
}//算法书中讲的一个较好的散列函数;
5、分离链接法:解决冲突的一种方法叫做分离链接法,将散列到同一个值的所有元素保留到一个链表中;缺点是需要指针,因为需要给新的节点分配空间,所有导致速度会减慢。
6、方法二:开放定址法。如果关键值产生了冲突,那就要尝试寻找另外的单元,直到找出空的单元为止。因为所有的节点都需要放在表中,因此需要散列表更大一些。有:线性探测法,平方探测法,双散列,再散列。

四、优先队列(堆)
1、有一些优先的工作,要先处理,这个时候,就要按照优先级来处理,来排序。书中讲到用到二叉堆,用二叉树来排序和处理。这里不多说,到二叉树再说。

五、排序
1、插入法排序:P和P+1元素进行比较,然后交换位置;
2、希尔排序:通过比较相距一定间隔的元素来工作,各趟比较所用的距离随着算法的进行而减小,知道只比较相邻元素的最后一趟排序为止;
3、堆排序:树的排序处理;
4、归并排序:算法基本操作是合并两个已经排好序的表,因为表已经排好序,所以若将输出放到第三个表中时则算法可以通过对输入数据一趟排序来完成;
5、快速排序:实在实践中最快的已知的排序算法,它平均运行时间哦日O(NlogN)。主要是由于非常精炼和高度优化的内部循环,最坏性能为O(N的2次方),稍加努力可改变这个情况。
(1)、如果S集合中元素时0或者1,则返回;
(2)、取S中任一元素v,作为枢纽元(pivot);
(3)、将S - {v}(S中其余元素)分成两个不想交的集合:S1 = {x 属于 S - {v} | x<= v} 和S2 = {x 属于S - {v} | X >= v};
(4)、返回{quicksort(S1) 后,继续v,继而quicksort(S2)}。
枢纽元的选择:一般做法是使用左端、右端、中心位置的三个元素,大小在中间的值作为枢纽元。
6、大型结构的排序:交换2个结构可能是非常昂贵的操作,实际的解法是让输入的数组包含指向结构的指针,通常是交换指针指向的关键字,并在必要是交换指针来进行排序。
7、桶式排序:
8、外部排序:

六、不相交集的ADT
七、图论算法
八、跳跃表
  评论这张
 
阅读(31)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017