Javascript--数据结构

1. 数组 let arr = [1, 2, 3, 4, 5,...]
   1.2. 矩阵（二维或多维数组）let arrs = [[1,2,3,4], [2,2,3,4],...]
2. 栈（LIFO）：遵循“后进先出”原则，主要是 追加元素、选择元素、删除元素等方法（后入先出）
   3.1 实现一个栈
   function Stack() {
   let items = []
   this.push = function(v) {
   return items.push(v) // 往后添加元素，返回新的长度
   }
   this.pop = function() {
   return items.pop() // 删除最后一个元素，返回被删除的元素
   }
   this.clear = function() {
   items = [] // 清空栈
   }
   this.isEmpty = function() {
   return items.length === 0 // 判断是否为空栈，返回true 或 false
   }
   this.size = function() {
   return items.length // 返回栈元素个数
   }
   // 现在，为我们的类实现一些额外的辅助方法。如果想知道栈里最后添加的元素是什么，可以 用peek方法。这个方法将返回栈顶(装瓶子原理)的元素：
   this.peek = function () {
   return items[items.length - 1]
   }
   // 我们来实现一个辅 助方法，叫print。它会把栈里的元素都输出到控制台：
   this.print = function () {
   console.log(items.toString())
   }
   }
   使用实现的栈
   let stack = new Stack()
   console.log(stack.isEmpty()) // 开始为空栈，我们要根据需要手动往里添加

// 往栈里添加一些元素
stack.push(1)
stack.push(2)
stack.push(3)

// 根据栈使用规则（后入先出）原则，我们来取元素
console.log(stack.peek()) // 返回栈顶元素及3

// 再添加一个元素，并使用它
stack.push(4)
stack.peek() // 返回的就是4，及栈顶最后一个元素
stack.size() // 查看元素个数，结果为 4
stack.isEmpty() // 查看是否为空数据 false
stack.pop() // 删除栈顶元素（最后一个元素）
stack.size() // 元素个数为 3
stack.print() // 打印出 1,2,3

实例：
我们主要使用十进制。但在计算科学中，二进制非常重要，因为计算机里的所 有内容都是用二进制数字表示的（0和1）。没有十进制和二进制相互转化的能力，与计算机交流 就很困难。

要把十进制转化成二进制，我们可以将该十进制数字和2整除（二进制是满二进一），直到结 果是0为止。举个例子，把十进制的数字10转化成二进制的数字，过程大概是这样：

image.png

十进制转二进制
function divideBy2(decNumber) {

var remStack = new Stack(), rem, binaryString = '';

while (decNumber > 0) { // 数字大于0
rem = Math.floor(decNumber % 2); // 取模 （余数）
remStack.push(rem); // 把余数放入栈
decNumber = Math.floor(decNumber / 2); //赋值新的结果值，继续循环与2取模, 且除2下去直到decNumber小于等于0停止
}
while (!remStack.isEmpty()) { //转换完后，取余数拼接起来就是对应的进展码数
binaryString += remStack.pop().toString();
console.log(binaryString)
}
return binaryString;
}

3. 队列 -- 先入先出
   实现封装一个队列类
   function Queue () {
   var items = []
   this.enqueue = function (ele) {
   return items.push(ele)
   }
   this.dequeue = function () {
   return items.shift() // 删除并返回第一个元素 （先进先出）
   }
   this.front = function () { //返回队列第一个元素
   return items[0]
   }
   this.isEmpty = function () {
   return items.length === 0
   }
   this.size = function () {
   return items.length
   }
   this.print = function () {
   console.log(items.toString())
   }
   }

var queue = new Queue () // 创建一个队列实例

// 添加元素
queue.enqueure('张三')
queue.enqueure('李四')
queue.enqueure('赵五')

queue.print() // 张三、李四、赵五
queue.size() // 3
console.log(queue.isEmpty()) // false
queue.deueue() // 移除第一个元素
queue.deueue() // 再次移除目前队列里的第一个元素
queue.print() // 赵五

// 优先队列
设置元素优先级，然后在正确的位置添加元素

function PriorityQueue () {
var items = []
function QueueElement (element, priority) {
this.element = element
this.priority = priority
}

// 添加元素
this.enqueue = function (element, priority) {
var queueElement = new QueueElement(element, priority) // 设置元素优先级

  // 检测队里是否为空
 if (this.isEmpty())
  items.push(queueElement)  // 为空时，直接追加元素
}

this.isEmpty = function () {
return items.length === 0
}
// .... 其它方法与Queue 类方法实现相同
}
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.print();

第一个被添加的元素是优先级为2的John。因为此前队列为空，所以它是队列中唯一的元素。 接下来，添加了优先级为1的Jack。由于Jack的优先级高于John，它就成了队列中的第一个元 素。然后，添加了优先级也为1的Camila。Camila的优先级和Jack相同，所以它会被插入到Jack 之后（因为Jack先被插入队列；Camila的优先级高于John，所以它会被插入到John之前。

我们在这里实现的优先队列称为最小优先队列，因为优先级的值较小的元素被放置在队列最 前面（1代表更高的优先级）。最大优先队列则与之相反，把优先级的值较大的元素放置在队列最 前面。

// 循环队列。 即一个需求任务，需要不断的循环遍历元素排列，不断的一次遍历完删除第一个元素. 模拟的击鼓传花游戏
function hotPotato (nameList, num) {
var queue = new Queue()

// 把名字添加队列
for (var i=0; i<nameList.length; i++) {
queue.enqueue(nameList[i]) // 把人员名单添加到队列
}

var eliminated = '';

// 当队列还有元素（人），代表没淘汰完呢，继续遍历游戏规则
while (queue.size() > 1) {

// 遍历找到指定元素num，遍历完下一个就是指定元素, 注意这里的循环只负责排列元素， 遍历完，排到的第一个元素就是要淘汰的元素，故此利用队列的"先入先出"原则，来使用队列，既队列的第一个元素不断被移除
for (var i=0; i<num; i++) {
  queue.enqueue(queue.dequeue()) // 没找到指定元素，往后排
}
// 删除元素
let eliminated = queue.dequeue()  // 遍历完一轮，移除第一个元素
queue.print()

}
return queue.dequeue() // 最后一个被移除的元素
}
var names = ['meng','xu','zhang','guo','jiang']
console.log(hotPotato(names, 8))

4. 链表
   链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成

   
   image.png

相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然 而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何 位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到 所需的元素。
实现封装链表类
function linkedList() {

// 节点元素
var Node = function (element) {
this.element = element
this.next = null
}
var length = 0
var head = null

this.append = function(element) {
var node = new Node(element),
current

// 空列表时直接赋值head
if (head === null) {
  head = node
} else {  // 非空列表时
  current = head

  // 循环列表，直到找到最好一项循环遍历完，及最后一个元素的node.next 为null就停止
  while(current.next) {
    current = current.next
  }

  current.next = node  // 找到最好一项，next 指向node进行连接
}
length ++  // 追加元素，长度要增加

}

this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head,
previous,
index = 0

  // 如果是移除第一项，
  if (position === 0) {
    head = current.next
  } else {

    // 虚幻遍历完，定为项所在
    while (index ++ < position) {
      previous = current
      current = current.next
    }
    // 断开连接current,直接连接到current.next项
    previous.next = current.next
  }
  length --   // 元素减完，length需要减
  return current.element  // 返回被移除的元素
} else {
  return null  // 如果是不存在的position 则返回null
}

}

// 插入元素
this.insert = function(position, element) {
// 检查边界
if (position >= 0 && position <= length) {
var node = new Node(element),
current = head,
previous,
index = 0

  if (position === 0) {
    node.next = current
    head = node
  } else {
    while (index++ < position) {
      previous = current
      current = current.next
    }
    node.next = current
    previous.next = node
  }
  length ++ // 更新列表长度
  return true
} else {
  return false
}

}

this.toString = function() {
var current = head,
string = ''

while (current) {
  string += current.element
  current = current.next
}
return string

}

this.indexOf = function(element) {
var current = head,
index = -1

while (current) {
  index ++
  if (element === current.element) {
    return index
  }
  current = current.next
}
return -1

}

this.remove = function(element) {
var index = this.indexOf(element)
return this.removeAt(index)
}

this.isEmpty = function() {
return length === 0
}
this.size = function() {
return length
}
this.getHead = function() {
return head
}
}
var list = new linkedList()

list.append(10)
list.append(11)
list.insert(2, 12)
list.insert(3, 13)
// list.removeAt(1)
list.remove(12)
console.log(list.toString())
console.log(list.indexOf(12))

4.1 双向链表
。双向链表和普通链表的区别在于，在链表中， 一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素， 另一个链向前一个元素，如下图所示：

image.png

function doublyLinkedList () {
var Node = function(element) {
this.element = element,
this.prev = null
this.next = null
}

var head = null,
length = 0
tail = null

this.insert = function(position, element) {
var node = new Node(element),
current = head,
previous,
index = 0

// 检测边界
if (position >=0 && position <= length) {
  // 在第一个位置添加
  if (position === 0) {
    if(!head) {
      head = node
      tail = node
    } else {
      node.next = current
      current.prev = node
      head = node
    }
  } else if (position === length) {
    current = tail
    current.next = node
    node.prev = current
    tail = node // 最后一元素引用
  } else {
    while (index ++ < position) {
      previous = current
      current = current.next
    }
    node.next = current
    previous.next = node

    current.prev = node
    node.prev = previous
  }
  length ++
  return true
} else {
  return false
}

}

this.removeAt = function(position) {
// 检查越界值
if (position > -1 && position < length) {
var current = head
previous,
index = 0

  // 第一种情况是链表头时
  if (position === 0) {
    head = current.next

    // 如果链表只有一项
    if (length === 1) {
      tail = null  // 设置末尾
    } else{
      head.prev = null // 更新双向链表prev
    }
  } else if (position === length -1) { // position 是最后一项时

    current = tail
    tail = current.prev
    tail.next = null
  } else {
    while (index ++ < position) {
      previous = current  // 赋值要被移除元素的上一个节点
      current = current.next // 此时赋值current 为要被移除的元素 current.next 的节点要是要没移除的元素节点
    }

    // previous.next 链向 current.next节点， 被移除的元素的节点的下个节点的prev得链向previous
    previous.next = current.next // 上一个节点next，链向要被移除的元素的下个节点
    current.next.prev = previous // 要被移除的节点的下个节点的prev链向 previous 节点
  }

  length --  // 别忘了减length
  return current.element
} else {
  return null
}

}

// ... 其它方法与链表大致差不多
}
4.2 循环链表
循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链 表之间唯一的区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用null， 而是指向第一个元素（head），如下图所示。

image.png

双向循环链表有指向head元素的tail.next，和指向tail元素的head.prev。

image.png

链表相比数组最重要的优点，那 就是无需移动链表中的元素，就能轻松地添加和移除元素。
因此，当你需要添加和移除很多元素时，最好的选择就是链表，而非数组。

5. 集合
   目前的JavaScript实现是基于2011年6月发布的ECMAScript 5.1（现代浏览器均已支持），它包 括了我们在之前章节已经提到过的Array类的实现。ECMAScript 6（官方名称ECMAScript 2015， 2015年6月发布）包括了Set类的实现。

function Set() {
var items = {}

this.has = function(ele) {
// return ele in items
return items.hasOwnProperty(ele)
}
this.add = function(ele) {
if (!this.has(ele)) {
items[ele] = ele
return true
}
return false
}
this.remove = function(ele) {
if (this.has(ele)) {
delete items[ele]
return true
}
return false
}
this.clear = function(ele) {
items = {}
}
this.size = function() {
var count = 0
for (var key in items) {
if (items.hasOwnProperty(key))
++count
}
return count
}
this.values = function() {
// return Object.keys(items)
var keys = []

for (var key in items) {
  keys.push(key)
}
return keys

}

/首先需要创建一个新的集合，代表两个集合的并集。接下来，获取第一个集合（当 前的Set类实例）所有的值（values），遍历并全部添加到代表并集的集合中）。然后对 第二个集合做同样的事）。最后返回结果。/
// 并集
this.union = function(otherSet) {
var unionSet = new Set()

var values = otherSet.values()
for (var i=0; i<values.length; i++) {
  unionSet.add(values[i])
}

values = this.values()
for (var i=0; i<values.length; i++) {
  unionSet.add(values[i])
}
return unionSet // 返回新的集合

}

// 交集, 就是你有我也有的部分
this.intersection = function(otherSet) {
var intersectionSet = new Set()

var values = this.values()
for (var i=0; i<values.length; i++) {

  // 如果other集合里有当前集合的元素，则添加到新集合里
  if (otherSet.has(values[i])) {
    intersectionSet.add(values[i])
  }
}

return intersectionSet

}

// 差集，当前集合里有的，other没有的
this.difference = function(otherSet) {
var differenceSet = new Set()

var values = this.values()
for (var i=0; i<values.length;i++) {

  // 检查other里没有的，进行添加
  if (!otherSet.has(values(i))) {
    differenceSet.add(values[i])
  }
}
return differenceSet

}

// 子集，当前集合从属于other集合
this.subset = function(otherSet) {
if (this.size() > otherSet.size()) {
return false
} else {
var values = this.values()

  for (var i=0; i<values.length;i++) {

    // 即有一个不是other的元素，就不是子集
    if (!otherSet.has(values[i])) {
      return false
    }
  }
  return true
}

}
}

var set = new Set();

set.add(1); console.log(set.values()); //输出["1"] console.log(set.has(1)); //输出true console.log(set.size()); //输出1

set.add(2); console.log(set.values()); //输出["1", "2"] console.log(set.has(2)); //true console.log(set.size()); //2

set.remove(1); console.log(set.values()); //输出["2"]

set.remove(2); console.log(set.values()); //输出[]
var setA = new Set(); setA.add(1); setA.add(2);

var setB = new Set(); setB.add(1); setB.add(2); setB.add(3);

var setC = new Set(); setC.add(2); setC.add(3); setC.add(4);

console.log(setA.subset(setB)); console.log(setA.subset(setC));

5. 字典
   与Set类相似，ECMAScript 6同样包含了一个Map类的实现，即我们所说的字典。
   Set类很相似（但不同于存储[值，值]对的形式，我们将要存储的是[键，值]对）。
   function Dictionary () {
   var items = {}
   this.has = function(key) {
   return items.hasOwnProperty(key)
   }
   this.set = function(key, value) {
   if (!this.has(key)) {
   items[key] = value
   return true
   }
   return false
   }
   this.remove = function(key) {
   if (this.has(key)) {
   delete items[key]
   return true
   }
   return true
   }
   this.get = function(key) {
   return this.has(key) ? items[key] : undefined
   }
   this.clear = function() {
   items = {}
   }
   this.size = function() {
   var count = 0
   for (var k in items) {
   if (this.has(k)) {
   ++ count
   }
   }
   return count
   }
   this.keys = function() {
   return Object.keys(items)
   }
   this.values = function() {
   var values = []
   for (var k in items) {
   if (this.has(k)) {
   values.push(items[k])
   }
   }
   return values
   }
   this.getItems = function() {
   return items
   }
   }
   var dictionary = new Dictionary();
   dictionary.set('meng', 'meng@email.com');
   dictionary.set('xian', 'xian@email.com');
   dictionary.set('sheng', 'tyrion@email.com');

console.log(dictionary.has('sheng'));
console.log(dictionary.size());
console.log(dictionary.keys());
console.log(dictionary.values());
console.log(dictionary.get('xian'));

dictionary.remove('xian');

console.log(dictionary.keys());
console.log(dictionary.values());
console.log(dictionary.getItems());

6. 散列表
   function HashTable() {
   var table = []

// 散列函数1,会有索引冲突情况
var loseloseHashCode = function(key) {
var hash = 0

for (var i = 0; i<key.length;i++) {
  hash += key.charCodeAt(i)
}
return hash % 37

}
// 散列函数2，索引不会冲突
var djb2HashCode = function() {
var hash = 5381
for (var i=0; i<key.length;i++) {
hash += hash * 33 + key.charCodeAt(i)
}
return hash % 1013
}
this.put = function(key, value) {
var position = loseloseHashCode(key)
table[position] = value
}
this.remove = function(key) {
table[loseloseHashCode(key)] = undefined
}
this.get = function(key) {
return table[loseloseHashCode(key)]
}
}

var hash = new HashTable();
hash.put('meng', 'meng@email.com');
hash.put('xian', 'xian@email.com');
hash.put('sheng', 'sheng@email.com');

console.log(hash.get('xian'))
console.log(hash.get('meng'))
console.log(hash.get('sheng'))
hash.remove('meng')
console.log(hash.get('tong'))
console.log(hash.get('meng'))

解决散列表索引位置冲突

1. 分离链接
   分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的 最简单的方法，但是它在HashTable实例之外还需要额外的存储空间。
   为了实现一个使用了分离链接的HashTable实例，我们需要一个新的辅助类来表示将要加入
   LinkedList实例的元素。我们管它叫ValuePair类（在HashTable类内部定义）：

var ValuePair = function(key, value){
this.key = key;
this.value = value;
this.toString = function() { return '[' + this.key + ' - ' + this.value + ']'; }
};

(1) put方法

我们来实现第一个方法，put方法，代码如下：

this.put = function(key, value){
var position = loseloseHashCode(key);
if (table[position] == undefined) { //{1}
table[position] = new LinkedList();
}
table[position].append(new ValuePair(key, value)); //{2} };
在这个方法中，将验证要加入新元素的位置是否已经被占据（行{1}）。如果这个位置是第 一次被加入元素，我们会在这个位置上初始化一个LinkedList类的实例（你已经在第5章中学 习过）。然后，使用第5章中实现的append方法向LinkedList实例中添加一个ValuePair实例 （键和值）（行{2}）。