11.1 散列表(哈希表) 11.1.1 散列的基本思路 散列查找。 先讲一个例子: 比如说,C 语言编译的时候,C语言里有个规则就是变量名必须先定义(或声明)后再使用。当编译器碰到变量名的时候,它可能在两个位置,一个是在它定义(或声明)的地方,一个是在它使用的地方。当编译器碰到他使用的地方,它就要检查,该变量是否定义过,如果没有定义过,就会报错;如果定义过,还要知道这个变量是什么类型的,这种类型在这个语句环境里是不是可以用。这就涉及到一个变量管理的问题。 抽象一下,编译处理时,就是对变量名以及变量属性的管理: 插…

2017年7月11日 0条评论 0点热度 阅读全文

10.1 快速排序 在大多数的情况下,快速排序的表现都非常好。 10.1.1 算法概述 和归并排序一样,都是使用了分而治之的思想。 分而治之的例子: 伪代码描述: 10.1.2 选主元 取头、中、尾的中位数。 伪代码描述: C 语言实现:快速排序 直接调用库函数 /* 快速排序 - 直接调用库函数 */ #include <stdlib.h> /*---------------简单整数排序--------------------*/ int compare(const void *a, const vo…

2017年7月10日 0条评论 1点热度 阅读全文

9.1 简单排序(冒泡,插入) 9.1.1 概述 后面介绍的所有排序算法,都默认为这样的格式: 9.1.2 冒泡排序 思路:从上到下比较相邻的元素,每次和下面那个元素作比较并交换。一共要完成N次排序。 C 语言实现 void Bubble_Sort(ElementType A[],int N) { int p,i,flag; for(p=N-1;p>=0;p--) { flag=0; for(i=0;i<p;i++) //一趟冒泡 { if(A[i]>A[i+1]) { Swap(A[i],A[i…

2017年7月10日 0条评论 0点热度 阅读全文

8.1 最小生成树 8.1.1 什么是最小生成树 解决最小生成树有很多算法,但是归结起来都是贪心算法。 贪心算法: 什么是“贪”:每一步都要最好的 什么是“好”:权重最小的边 但是因为是最小生成树,所以这个贪心算法还需要约束: 只能用图里有的边 只能正好用掉 | V | - 1 条边 不能有回路 贪心算法由两个著名的算法:Prim 算法 和 Kruskal 算法。 8.1.2 Prim 算法 Prim 算法–选一个结点,让一棵小树“长大” (和之前 单源最短路径中的 Dijkstra算法很像)(针对的是点) 和 D…

2017年7月10日 0条评论 0点热度 阅读全文

7.1 最短路径问题 7.1.1 概述 图论里最少的步骤就是最短路径问题。 最短路径问题的抽象 在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径。 第一个顶点为源点,最后一个顶点为终点。 问题分类 单源最短路径问题:从某固定源点出发,求其到所有其他顶点的最短路径。 单源最短路径问题又分为两类: - (有向)无权图 - (有向)有权图 多源最短路径问题:求任意两顶点间的最短路径。 7.1.2 无权图的单源最短路 思路:按照递增(非递减)的顺序找出各个顶点的最短路。…

2017年7月10日 0条评论 0点热度 阅读全文

前言 请跟着上一讲http://blog.csdn.net/jurbo/article/details/52595821继续学习 3.1 树与树的表示 3.1.1 引子(顺序查找) 什么是树 客观世界中许多事物存在层次关系 人类社会家谱 社会组织结构 图书信息管理 分层次组织在管理上具有更高的效率! 数据管理的基本操作之一:查找 如何实现有效率的查找? 查找 查找:根据某个给定关键字K,从集合R中找出关键字与K相同的记录 静态查找:集合中记录是固定的(查字典) 没有插入和删除操作,只有查找 动态查找:集合中记录是动…

2016年9月21日 0条评论 0点热度 阅读全文

前言 请跟着上一讲http://blog.csdn.net/Jurbo/article/details/52593532继续学习 2.2 堆栈 2.2.1 什么是堆栈 计算机如何进行表达式求值? 【例】算术表达式5+6/2-3*4。正确理解: 5+6/2-3*4=5+3-3*4=8-3*4=8-12=-4 由两类对象构成的: 运算数,如2、3、4 运算符号,如+、- 、*、/ 不同运算符号优先级不一样 后缀表达式 中缀表达式:运算符号位于两个运算数之间。如:a+b*c-d/e 后缀表达式:运算符号位于两个运算数之后…

2016年9月20日 0条评论 0点热度 阅读全文