雅乐网

计算机技术、学习成长

计算机

堆和堆排序

堆和堆排序

数据结构中的堆和程序语言中的堆的意义并不相同,这里的堆是一种数据结构。二叉堆可以分为最大堆和最小堆,这里介绍最大堆。在最大堆中,结点的值满足堆的性质:除了根节点外,所有结点都不会比它的父节点大。 可以看到,逻辑上的堆是二叉树,但堆的物理结构

数据库结构升级要注意

数据库结构升级要注意

比如我使用sqlite3数据库,用户安装应用时会创建db,用来存储一些个人的数据。 某一天我想给数据库增加一个表或者某张表增加列。 那么新的程序就要考虑:用户覆盖安装,全新安装的情况。 创建数据库就要if not exist Db1 cre

向量叉积和应用:判断点是否在三角形内部

向量叉积和应用:判断点是否在三角形内部

本文是学堂在线计算几何课程 凸包一章的部分学习笔记。如果要求编程判断一个点是否在三角形(三个点)内部。 可以看出,如果点在三角形的内部,沿着三边走一圈,这个点相对于行进路径始终保持相同方向(图中一直在左边); 如果点在三角形的外部,沿着三条

用两个栈模拟队列,快速获得队列的最大值

用两个栈模拟队列,快速获得队列的最大值

队列是一种常用的数据结构。如果按照常规的想法,要获得队列中的最大值,必须遍历队列中的所有元素,时间复杂度为O(n)。怎么降低这个时间呢?求最大元素很容易想到堆。如果建立一个辅助的最大堆(里面存放队列中元素的指针以及值),入队或者出队的时候,

使用主定理求解递归式

使用主定理求解递归式

算法导论中的4.5节介绍了一个用于求解递归式的主定理,可以用来求解部分形如下面形式的递归式: ,其中a>=1 , b >1 ,其中a>=1 , b >1 描述的算法 把规模为n的问题分为a个子问题,每个子问题规模是n

详解快速排序

详解快速排序

快速排序通常是在实际应用中排序的最好算法,虽然在最坏情况下它的时间复杂度是O(n^2),但是在平均情况下,它的时间复杂度是O(nlogn),并且它的常数因子非常小,因此效率极高。 下面的描述中对数组a中的[lo,hi)进行排序。([lo,h

linux添加字符设备驱动程序

linux添加字符设备驱动程序

要求: 掌握添加设备驱动程序的方法 内容 采用模块方法,添加一个新的字符设备的驱动程序,实现打开/关闭、读/写等基本操作 编写一个应用程序,测试添加的驱动程序 如果打开设备失败,应该用root身份来运行。下面的示例全部是root用户的身份。

ubuntu编译内核并添加系统调用(3.12版本)

ubuntu编译内核并添加系统调用(3.12版本)

本文是ubuntu13.10 32位环境下面添加系统调用并编译内核的过程。只针对3.12内核版本,对于其他版本的内核可能修改方式不同。 环境是virtualbox下面的ubuntu13.10 32bit ,雅乐网发现硬盘文件vdi分配20G

最大子列和问题

最大子列和问题

给定K个整数组成的序列{ N1, N2, …, NK },“连续子列”被定义为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素

数组中找两个数字之和为指定值

数组中找两个数字之和为指定值

快速找出一个数组中的两个数字,让这两个数字之和等于一个给定的值. 数组a[n] ,要找出两个数字 和为x O(n^2)的算法 很容易我们可以写出这么一个粗暴的算法,那就是两两比较,看有没有符合要求的