首页

读【数据结构与算法】之高级算法

发表于2014年09月26日 分类: js 标签: js js数据结构与算法

高级算法,本部分只包含两个主题:动态规划和贪心算法。

动态规划有时会被认为是一种与递归相反的技术。动态规划是从底部开始解决问题,将所有小问题解决掉,然后合并成一个整体的解决方案。

贪心算法是一种寻找“优质解”为手段而达成的整体解决方案算法。这些优质的解决方案称为局部最优解,将有希望得到正确的最终解决方案,也称为全局最优解。

更多

读【数据结构与算法】之检索算法

发表于2014年09月15日 分类: js 标签: js js数据结构与算法

本文只包含数据检索的一个方面:如果在列表中查找特定的值。

在列表中查找数据有两种方式:顺序查找和二分查找。顺序查找适用于元素随机排列的列表;二分查找适用于元素已经排列的列表。二分查找效率高,但是必须在查找之前话费额外的时间将列表中元素排序。

更多

读【数据结构与算法】之排序算法

发表于2014年09月11日 分类: js 标签: js js数据结构与算法

本文介绍数据排序的基本算法和高级算法。这些算法都只依赖于数组来存储数据。

基本排序算法

基本排序算法的核心思想是指对一组数据按照一定的顺序重新排列。重新排列时用到的就是嵌套的for循环。其中外循环会遍历数组的每一项,内循环则用于比较元素。

冒泡排序

冒泡排序是最慢的排序算法之一,但也是一种最容易实现的排序算法。

之所以叫冒泡排序, 是因为使用这种算法排序时,数据值会像旗袍一样从数组的一端到另一端。这种算法会循环数组,然后多次循环,比较相邻的数据,当左侧值大于右侧值时将他们进行互换。

更多

读【数据结构与算法】之二叉树

发表于2014年09月11日 分类: js 标签: js js数据结构与算法

树是在计算机科学中经常用到的一种数据结构。树是非线性的数据结构,以分层的方式存储数据。在二叉树上进行查找非常快(在链表上查找就不是这样了),为二叉树添加或删除元素也非常快的(对数组添加或删除则不是这样)。

树由一组以边连接的节点组成。一棵树最上面的节点叫根节点,如果一个节点下面连接多个节点,那么该节点就称为父节点,他下面的节点称为子节点。没有任何子节点的节点称为叶子节点。沿着一组特定的边,可以从一个节点走到另外一个与他不直接连接的节点。从一个节点到另一个节点的这一组边称为路径。以某种特定顺序访问树中所有的节点称为树的遍历。

更多

读【数据结构与算法】之集合

发表于2014年09月10日 分类: js 标签: js js数据结构与算法

集合是一种包含不同元素的数据结构。集合中元素称为成员。集合的两个最重要的特性:

  • 首先,集合中的成员是无序的;

  • 其次,集合中不允许存在相同成员。

集合是由一组无序但彼此又有一定相关性的成员构成的,每一个成员在集合中只能出现一次。

更多

读【数据结构与算法】之散列

发表于2014年09月10日 分类: js 标签: js js数据结构与算法

散列是一种常用的数据存储技术,散列的数据可以快速的插入或者取用。散列使用的数据结构是散列表。在散列表上插入、删除和取用数据都很快,但是查找数据操作就慢了。

散列表是基于数组进行设计的,长度是预先定义好的,但是如果需要的话,也是可以增加的。元素根据该元素的键保存在数组的特定位置。使用散列表时,需要通过使用一个散列函数将键映射为一个数字,这个数字长度是从0到散列表长度。

更多

读【数据结构与算法】之队列

发表于2014年09月05日 分类: js 标签: js js数据结构与算法

基本实现

队列也是一种列表,他只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出,而栈是后入先出的。

队列主要有两种操作:向队列中插入新元素以及删除队列中元素。插入操作也叫入队,删除操作也叫出队。入队在队尾插入新元素,而出队则是删除队首的元素。

更多

读【数据结构与算法】之链表

发表于2014年09月05日 分类: js 标签: js js数据结构与算法

链表是由一组节点组成的集合。每一个节点都使用一个对象的引用指向他的下一个节点,指向另一个节点的引用就叫链。这样也就形成了链表。

实现链表需要两个类,一个是节点类Node,还有链表LinkedList类。

基本链表

最基本链表,也就是从头节点开始,一个链接着一个节点,直至最后一个,遍历的话只能从头开始到尾。

更多

读【数据结构与算法】之栈

发表于2014年09月05日 分类: js 标签: js js数据结构与算法

栈是一种特殊的列表,栈内元素只能通过栈的一端访问,这个端就叫栈顶。栈被称为一种后入先出的数据结构。

栈有三个主要的方法:pushpoppeek

实现一个栈,首先想到的存储数据是利用一个数组。

更多

读【数据结构与算法】之字典

发表于2014年09月05日 分类: js 标签: js js数据结构与算法

字典是一种以键-值形式存储数据的数据结构。

在JS中Object类就是以字典的形式设计的。所以在JS中实现字典是很容易的,且能够基于对象(非Object类)来封装出来字典。

字典类的基础是Array类,而不是Object类,但由于Array也是对象,所以上边所说基于对象是没错的。为什么是Array而不是Object呢,因为有好多场景需要有一个可以排序的字典,而在JS中是不能对对象的属性排序的。

更多