集合
什么是数据结构与算法？
- 数据结构就是在计算机中，存储和组织数据的方式。
+ 常见的数据结构： <img src="http://vamknight.com/%E5%B8%B8%E8%A7%81%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.png"> <!--more--> - 算法（Algorithm）的定义：
- 算法就是解决问题的方法/步骤，数据结构的实现离不开算法。
- 一个有限指令集，每条指令的描述不依赖于语言
- 接受一些输入（有些情况不需要输入）
- 产生输出
- 一定在有限步骤之后终止
- 算法就是解决问题的方法/步骤，数据结构的实现离不开算法。
集合
集合通常是由一组无序的，不能重复的元素构成。可以看成是一种特殊的数组，特殊之处在于里
面的元素没有顺序就意味着不能通过下标值进行访问，不能重复意味着相同的对象在同一个集合中只能存
在一份。集合都有哪些常见的操作方法呢？
add(value)：向集合添加一个新的项。
remove(value)：从集合移除一个值。
has(value)：如果值在集合中，返回 true，否则返回 false。
clear()：移除集合中的所有项。
size()：返回集合所包含元素的数量。与数组的 length 属性类似。
values()：返回一个包含集合中所有值的数组。
集合之间都有哪些操作呢？
- 并集：对于两个给定的集合，返回一个包含两个集合中所有元素的新集合。
- 交集：对于两个给定的集合，返回一个包含两个集合中公有元素的新集合。
- 差集：对于两个给定的集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的新集合。
- 子集：验证一个给定集合是否是另一个集合的子集。
- 集合封装的完整代码：
1 | // 封装集合的构造函数 |
队列（Queue）
队列是一种受限的线性表，先进先出（FIFO First In First Out）。
- 它只允许在表的前端（front）进行删除操作
- 在表的后端（rear）进行插入操作
常见应用场景： + 队列主要用在和时间有关的地方，特别是操作系统中，队列是实现多任务的重要机制。 + 消息机制可以通过队列来实现，进程调度也是使用队列来实现。
队列有哪些常见的操作呢？
- enqueue(element): 向队列尾部添加一个（或多个）新的项。
- dequeue(): 移除队列的第一项，并返回被移除的元素。
- front(): 返回队列中第一个元素，队列不做任何改动。
- isEmpty(): 如果队列中不包含任何元素，返回 true，否则返回 false。
- size(): 返回队列包含的元素个数，与数组 length 类似。
- toString(): 将队列中的内容，转成字符串形式。
队列常见操作的封装：
1 | //封装队列 |
- 面试题： 击鼓传花
1 | //面试题: 击鼓传花 |
- 封装优先队列
1 | //封装优先级队列 |
链表
什么是链表？ + 链表的元素在内存中不必是连续的空间，链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。
相对于数组，链表都有哪些优势？
- 内存空间不是比是连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理。
- 链表不必在创建时就确定大小, 并且大小可以无限的延伸下去。
- 链表在插入和删除数据时, 时间复杂度可以达到 O(1). 相对数组效率高很多。
相对于数组，链表都有哪些缺点？ + 链表访问任何一个位置的元素时, 都需要从头开始访问.(无法跳过第一个元素访问任何一个元素)。 + 无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的问题。
链表的数据结构：
链表有哪些常见操作？ + append(element)：向列表尾部添加一个新的项
+ insert(position, element)：向列表的特定位置插入一个新的项。 + update(position, element): 修改某一个位置上的元素。 + remove(element)：从列表中移除一项。 + indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。 // 链表中的属性 this.length = 0 this.head = null // 链表尾部追加元素方法 LinkedList.prototype.append = function (element) { // 1.根据新元素创建节点 var newNode = new Node(element) // 2.判断原来链表是否为空 if (this.head === null) { / + removeAt(position)：从列表的特定位置移除一项。this.next = null
}
/ 链表尾空
this.head = newNode
} else { // 链表不为空
// 2.1.定义变量, 保存当前找到的节点
var current = this.head
while (current.next) {
current = current.next
}// 2.2.找到最后一项, 将其next赋值为node current.next = newNode } // 3.链表长度增加1 this.length++ } // 链表的toString方法 LinkedList.prototype.toString = function () { // 1.定义两个变量 var current = this.head var listString = "" // 2.循环获取链表中所有的元素 while (current) { listString += "," + current.element current = current.next } // 3.返回最终结果 return listString.slice(1) } // 根据下标删除元素 LinkedList.prototype.insert = function (position, element) { // 1.检测越界问题: 越界插入失败 if (position < 0 || position > this.length) return false // 2.定义变量, 保存信息 var newNode = new Node(element) var current = this.head var previous = null index = 0 // 3.判断是否列表是否在第一个位置插入 if (position == 0) { newNode.next = current this.head = newNode } else { while (index++ < position) { previous = current current = current.next } newNode.next = current previous.next = newNode } // 4.length+1 this.length++ return true } //update方法 LinkedList.prototype.update = function (position, newData) { if (position < 0 || position >= this.length) return null var current = this.head var index = 0 while (index++ < position) { current = current.next } current.data = newData return true } // 根据位置移除节点 LinkedList.prototype.removeAt = function (position) { // 1.检测越界问题: 越界移除失败, 返回null if (position < 0 || position >= this.length) return null // 2.定义变量, 保存信息 var current = this.head var previous = null var index = 0 // 3.判断是否是移除第一项 if (position === 0) { this.head = current.next } else { while (index++ < position) { previous = current current = current.next } previous.next = current.next } // 4.length-1 this.length-- // 5.返回移除的数据 return current.element } // 根据元素获取链表中的位置 LinkedList.prototype.indexOf = function (element) { // 1.定义变量, 保存信息 var current = this.head index = 0 // 2.找到元素所在的位置 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.来到这个位置, 说明没有找到, 则返回-1 return -1 } // 根据元素删除信息 LinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index) } // 判断链表是否为空 LinkedList.prototype.isEmpty = function () { return this.length == 0 } // 获取链表的长度 LinkedList.prototype.size = function () { return this.length } // 获取第一个节点 LinkedList.prototype.getFirst = function () { return this.head.element }}
1 | - 以上操作的都是单向链表，下面来认识一下双向链表。 |
// 创建双向链表的构造函数
function DoublyLinkedList() {
// 创建节点构造函数
function Node(element) {
this.element = element
this.next = null
this.prev = null // 新添加的
}
// 定义属性
this.length = 0
this.head = null
this.tail = null // 新添加的
// 定义相关操作方法
// 在尾部追加数据
DoublyLinkedList.prototype.append = function (element) {
// 1.根据元素创建节点
var newNode = new Node(element)
// 2.判断列表是否为空列表
if (this.head == null) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
}
// 3.length+1
this.length++
}
// 在任意位置插入数据
DoublyLinkedList.prototype.insert = function (position, element) {
// 1.判断越界的问题
if (position < 0 || position > this.length) return false
// 2.创建新的节点
var newNode = new Node(element)
// 3.判断插入的位置
if (position === 0) { // 在第一个位置插入数据
// 判断链表是否为空
if (this.head == null) {
this.head = newNode
this.tail = newNode
} else {
this.head.prev = newNode
newNode.next = this.head
this.head = newNode
}
} else if (position === this.length) { // 插入到最后的情况
// 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
this.tail.next = newNode
newNode.prev = this.tail
this.tail = newNode
} else { // 在中间位置插入数据
// 定义属性
var index = 0
var current = this.head
var previous = null
// 查找正确的位置
while (index++ < position) {
previous = current
current = current.next
}
// 交换节点的指向顺序
newNode.next = current
newNode.prev = previous
current.prev = newNode
previous.next = newNode
}
// 4.length+1
this.length++
return true
}
// 根据位置删除对应的元素
DoublyLinkedList.prototype.removeAt = function (position) {
// 1.判断越界的问题
if (position < 0 || position >= this.length) return null
// 2.判断移除的位置
var current = this.head
if (position === 0) {
if (this.length == 1) {
this.head = null
this.tail = null
} else {
this.head = this.head.next
this.head.prev = null
}
} else if (position === this.length -1) {
current = this.tail
this.tail = this.tail.prev
this.tail.next = null
} else {
var index = 0
var previous = null
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
// 3.length-1
this.length--
return current.element
}
// 根据元素获取在链表中的位置
DoublyLinkedList.prototype.indexOf = function (element) {
// 1.定义变量保存信息
var current = this.head
var index = 0
// 2.查找正确的信息
while (current) {
if (current.element === element) {
return index
}
index++
current = current.next
}
// 3.来到这个位置, 说明没有找到, 则返回-1
return -1
}
// 根据元素删除
DoublyLinkedList.prototype.remove = function (element) {
var index = this.indexOf(element)
return this.removeAt(index)
}
// 判断是否为空
DoublyLinkedList.prototype.isEmpty = function () {
return this.length === 0
}
// 获取链表长度
DoublyLinkedList.prototype.size = function () {
return this.length
}
// 获取第一个元素
DoublyLinkedList.prototype.getHead = function () {
return this.head.element
}
// 获取最后一个元素
DoublyLinkedList.prototype.getTail = function () {
return this.tail.element
}
// 遍历方法的实现
// 正向遍历的方法
DoublyLinkedList.prototype.forwardString = function () {
var current = this.head
var forwardStr = ""
while (current) {
forwardStr += "," + current.element
current = current.next
}
return forwardStr.slice(1)
}
// 反向遍历的方法
DoublyLinkedList.prototype.reverseString = function () {
var current = this.tail
var reverseStr = ""
while (current) {
reverseStr += "," + current.element
current = current.prev
}
return reverseStr.slice(1)
}
// 实现toString方法
DoublyLinkedList.prototype.toString = function () {
return this.forwardString()
}
}
1 |
栈
我们知道数组是一种线性结构，可以在数组的任意位置插入或删除数据。但有些时候，我们为了实现某种功能，必须对这种 任意性 加以限制，而我们的栈和队列就是比较常见的 受限的线性结构。
栈是一种先进后出或**后进先出(LIFO Last In First Out)**的数据结构，栈内的元素只能通过列表的一端访问，这一端称为栈顶，因为
数据只能在栈顶添加或删除，所以只要数据的保存满足“先进后出或后进先出”的原理，都优先考虑使用栈。栈的结构示意图：
栈常见有哪些操作？
- push（element）：添加一个新元素到栈顶位置。
- pop（）：移除栈顶的元素，同时返回被移除的元素。
- peek（）：返回栈顶的元素，不对栈做任何修改。
- isEmpty（）：如果栈里没有任何元素返回 true，否则返回 false。
- size（）：返回栈里的元素个数，类似数组中的 length。
- toString（）：将栈结构的内容以字符形式返回。
- 栈常见操作的封装：
1 | function Stack() { |
1 | //函数十进制转为二进制 |
数据结构与算法
五大算法
贪心算法
分治算法
动态规划
回溯法
分支限界法
冒泡排序
1 | function bubleSort(arr) { |
选择排序
1 | function selectSort(arr) { |
插入排序
1 | function insertSort(arr) { |
快速排序
1 | function quickSort(arr) { |
1 | //创建列表类 |
完整代码
1 | // 封装ArrayList |
哈希表
1 | // 创建HashTable构造函数 |