返回 登录
0

数据结构与算法(一)概念梳理篇

附上博客链接,希望能和大家一起学习交流
程序 = 数据结构 + 算法,至于我们平时用的语言,无论是C、C++、JAVA、Python、Golang等等,都肯定会用到各式各样的算法和数据结构,数组,链表,排序,搜索等等,可以说数据结构和算法就是程序的灵魂,同样的,也是程序员基本素养最直观的体现,只有拥有扎实的数据结构和算法知识,才能够成为一名合格的程序员。
写这个系列是因为觉得无论学哪门语言,数据结构和算法总是常伴左右,最近深深感觉到自己在这方面的欠缺,因为老是用一些已经封装好的库或者数据结构,算法用的也是少,感觉这是一块瓶颈,所以觉得提升这方面的知识是相当重要的,下面就是我总结的数据结构和算法知识拓扑图:

存储结构:线性表(简单点说就是数组)和链表 这两个是最基本的数据结构,代表着两种不同的存储数据的方式,数组就是说里面存的数据它们所占用的内存是连续的,而链表则是随机存储,关于这两者的例子太多太多,但说实话,那天我自己写一个链表的实现,也是痛苦得紧啊,所以一定要避免眼高手低,能用C语言手写一个链表,基本上这部分就差不多掌握了。

基础结构:队列和栈,这也是两种最常见的数据结构了,其特点也是很鲜明的,队列是先进先出,栈是先进后出,可别小看了这两者的特性,有时候很多问题,如果借助队列和栈可以说无论在逻辑上还是实际编程上都能降低不少难度。

排序算法:排序算法太多了,容我慢慢道来:
冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、计数排序、基数排序、桶排序、堆排序等等,基本能想到的目前就这么多了,其实在工作中这么多排序能用上的真不多,但是多掌握一个排序,也就多了一种选择,而我说的这些排序虽然都不难,但是上手写代码还是或多或少有一点小坑的,这些东西后面我会一一道来的。

搜索算法:顺序查找和二分查找,关于搜索,顺序查找没什么好说的,挨个遍历找我们想要的,可以说是性能最低,难度也是最低的,写代码也就是一个for循环的事儿,而二分查找则是针对有序数据的一种改进的搜索方法,如果你以为搜索就这么简单,那可就错了,我们说过,数据结构和算法是不分家的,那么为了实现二分搜索,我们就应该选择最适合其的数据结构,而这种结构就是二叉树。

树和二叉树:树也是一种很常见的数据结构,而二叉搜索树作为承载二分搜索的一种数据结构,最被大家所熟知,但实际上二叉树的性能有时候是很差的,比如说这颗二叉树不平衡,那么其搜索效率也是低的惊人,因此各种二叉树的兄弟衍生出来,比如说红黑树,伸展树,B+树,B-树等等,你可以暂时不知道他们是如何实现的,只需要知道他们都是为了让二叉树更像二叉树,也就是二叉平衡树!

图论:图也就一种常见的数据结构,关于图的算法有广度优先搜索和深度优先搜索,最短路径,最小生成树,其中最短路径有几种著名的解法,分别是Dijkstra算法,佛洛依德算法,A*算法,SPFA算法等等。

动态算法:比较为大家熟知的就是动态规划了,用于解决0/1背包问题等等需要最优解的问题。

数据挖掘十大算法:数据挖掘也是近几年非常火的一个名词,作为相对比之前提到的一些入门算法来说,数据挖掘的这十大算法可能略难一点,但是算法的难易并不能说明一个算法好坏,只能说要弄懂这种算法需要下更多的功夫。十大算法依次是:C4.5算法、K-Means算法、Support vector machines算法、The Apriori algorithm、最大期望(EM)算法、PageRank、AdaBoost算法、kNN: k-nearest neighbor classification、Naive Bayes算法、CART: 分类与回归树

其实吧,算法的难易度并不能作为衡量一个算法的最主要的标准,就好比说pagerank算法和快速排序,明显是前者更难一些,事实上pagerank算法成就了现在的谷歌,是谷歌搜索成功最主要的算法之一,而快速排序基本上有一些编程基础的人都会,但事实上快排是二十世纪最伟大的十大算法之一,所以说两者一样都是伟大的算法,我们学习形形色色的算法和数据结构并不是为了难而去学,说到底还是要解决实际问题,能够解决问题,或者能够优化问题的算法都是好的算法,而数据结构有时候更像是算法的一种承载体,二者之间紧密联系,构成了伟大的程序。

评论