标签归档:数据结构

图—最短路径 Dijkstra, SPFA, Floyd

最短路径一看到最,职业病一般的就会想到用动态规划来做。。。至少事实证明的确存在动态规划的解法,但就像上一篇文章中分析的那样,这是一个具有最优子结构的问题,所以我们可以用优雅的贪心算法来解决。

这里我们用来做测试的图如下图所示,还是相当给力了

最短路径

最短路径要解决的实际问题,其实通过名字[……]阅读全文

图—最小生成树 Prime 和 Kruskal 算法

图的最小生成树的算法,这个问题要解决的问题场景很简单,要给几个地方修建铁路把它们连接起来。

如下图,黑色加粗的边表示是最小生成树的边。
最小生成树

如果最理想的情况,可以假设我们知道任意一点到其他点的距离,也就是边的权重,整个图应该是连通的,那我们开始修路吧
其实这里有一个变形,我们在教科书中[……]阅读全文

数据结构复习—图

图我觉的是数据结构中的最高境界了,其实想想,链表是图,所以栈,队列,字符串 都可以理解为图;树是图,所以各种树,森林,堆等数据结构都可以理解为图。。。。生活中的各种物品,事情,关系,工程项目中的工作,计划,代码 非常非常多的东西都能理解为图,所以可以看到图这种数据结构是多么的普遍而具有通用性。[……]阅读全文

数据结构复习要点—树

发表这一系列的博客,不是为了初级入门者的教学,而是将要点难点尽可能的列出来,方便快速复习,之前的链表和字符串貌似扯的有点多,这次力求简短。

  • 类型很多:二叉树,完全二叉树,搜索二叉树,Huffman树,AVL 平衡树,红黑树,Trie树,B树
  • 二叉树:能用数组表示一颗完全二叉树,一颗二

[……]阅读全文

数据结构复习要点–前言,链表,字符串

所谓万变不离其宗,数据结构的基础是很多复杂大的算法以及大的工程的基础,有了基础才能跑的快,这篇文章就是按照常用的数据结构里的点,来建立一些简要描述帮助大家能够快速抓到重点,应该会持续更新的。

其实感觉数据结构是一门非常基础的编程基础,编程的目标是要告诉计算机,应该如何认知这个世界并且进行操作。

[……]阅读全文