请稍侯

栈应用 - 括号匹配

一、原理 很简单,遇到左括号用栈存起来,遇到右括号就从栈取出一个比较即可. 特殊情况: 在栈空的情况下遇到右括号肯定不匹配; 在括号扫描结束的情况下,栈不为空,肯定不匹配. 二、步骤 Step 1: 从左到右扫描括号字符串 Step 2: 左括号入栈 Step 3: 判断右括号与栈顶元素是否匹配 如果存储左括号的栈空或不匹配,返回false 如果匹配出栈,扫描下一个字符 Step 4: 扫描结束后,如果栈不为空,则肯定不匹配 三、实现 int BRA...

read more

栈应用 - 中缀表达式->后缀表达式

一、原理 二、步骤 Step 1: 从左向右开始扫描中缀表达式 Step 2: 如果是数字或字母,直接输出 或者 存取在其他地方 Step 3: 遇到运算符时, 3 IF 若为’(‘或栈空, 入栈; 若为’)’, 出栈直到’(‘为止; 若为其他, 比较运算符优先级, 如果栈非空并且tmpC<=栈顶元素,栈顶元素出栈; 比较下一个栈顶元素, 直到栈空或左括号; 最后将tmpC入栈. 三、实现 ...

read more

数据结构中的逻辑结构与物理结构

一、理解(重点) 比如数据结构中的树的存储 逻辑结构: 很形象啊,在你脑海里不就是一棵树吗? 物理结构: 这棵树在物理内存中可以用数组存储(顺序存储), 也可以在内存中用链表存储(链式存储); 二、课本原理 逻辑结构: 指数据元素之间的逻辑关系; 物理结构: 指数据结构在计算机中的表示(又称映像); 这里讲的不错,不妨看看 三、类型 (1)逻辑结构 1)集合结构 数据元素之间无序, 例如大圆圈里许多互不相...

read more

分治算法(Divide And Conquer Method)

重要性 要我说呢,这是算法中基础中的基础,但并不是不重要,相反,非常重要,而且有一定理解难度,至少对初学者,或者我来说,完全理解并灵活运用,绝非易事。 所以,这个分治法(Divide-And-Conquer-Method)得反复看.尤其是递归的时候,必须反思反思分治法. 一、基本思路 1.将问题的实例分为几个较小的实例,最好具有相等规模(事实上,一般说分为2个实例居多,并且注意是递归的分.); 2.对这些较小的实例求解(一般使用递归的方法, 但在问题规模足够小的时候也可以采用另一个算法(停止递归)); 3.如果有必要的话,合并这些较小问题的解,以得到原始问题...

read more

八种排序算法之7 归并排序(Merge Sort)

一、基本思想 归并排序依赖于递归合并操作, 即将一个数组递归分成两个子数组并分别进行排序,,然后将这两个有序数组排序. 二、基础: 合并两个有序列表 合并有序数列的效率 O(n) 步骤: 1.申请空间,使其大小为两个已经排序序列之和,然后将待排序数组复制到该数组中. 2.设定两个指针,最初位置分别为两个已经排序序列的起始位置 3.比较复制数组中两个指针所指向的元素,选择相对小的元素放入到原始待排序数组中,并移动指针到下一位置 4.重复步骤3直到某一指针达到序列尾. ...

read more

八种排序算法之6 堆排序(Heap Sort)

一、基本思想 先堆化,然后利用堆的性质排序. 最大堆: 根节点最大 最小堆: 根节点最小 二、基础: 堆(Heap) (1)二叉堆(一般简称堆)的定义 二叉堆是完全二叉树或者近似完全二叉树(只能有最后一个节点不完全) 二叉堆2个特性: a.父结点的键值总是大于或等于(最大堆)/小于或等于(最小堆)任何一个子结点的键值. b.每个节点节点的左子树和右子树都是一个二叉堆(最大堆/最小堆). 类型: 最大堆: 父结点的值总是大于或等于任何一个子结...

read more

八种排序算法之5 选择排序(Select Sort)

一、基本思想 选择排序和冒泡排序是差不多的一种排序. 和冒泡选择不一样的的是, 选择排序只有在确定了最小(或最大)的数据之后,才会发生交换. 二、基础 冒泡排序 三、解题方法 /** * array : 数组 * len : 数组长度 */ void SelectSort(int array[], int len) { // 当前的值最小的数组下标 int min_id; // 长度len的数组,排序len-1次交换就行了 // 每次只有最小的排到相对最前面 // i 刚好存放每次相对最小的数, 也就是要交换的数 ...

read more

八种排序算法之4 快速排序(Quick Sort)

一、基本思想 (挖坑填数 + 分治法(Divide and Conquer Method)) 1、先从数列中取出一个数作为基准数 2、分区过程,将比这个数大或者等于的数全放到它右边,小它的数全部放到它的左边 3、再对左右区间重复第二步,知道各区间只有一个数. 复杂度 时间复杂度 O(NlogN), 效率较高 二、基础: 分治法 分治法(Divide And Conquer Method) 待续: 独立一篇文章写写 写好了: 分治法 三、解题方法 (1)调整数组: 挖坑填数思想 /* 挖坑填数部分...

read more