Tracy JS 小笔记 - 数据结构 栈，队列，链表，字典，集合，哈希表(散列表)
巫马星雨
数据结构栈
- 后进先出(兜儿)，栈应该有如下方法：
- 入栈 push() 添加栈顶元素
- 出栈 pop() 移除栈顶元素
- 获取栈顶元素 peek()
- 是否为空 isEmpty()
- 清空栈 clear()
- 栈元素个数 size()
-
js 实现栈结构 -- 封装数组 var Stack = function(){ var items = []; //这个变量需要是一个私有的，外部看不到的，这样才是一个栈，不要写成 this.item = []; 否则容易被别人串改 this.push = function(ele){ items.push(ele); } this.pop = function(){ return items.pop(); } this.peek = function(){ return items[items.length - 1]; } this.isEmpty = function(){ return items.length == 0; } this.clear = function(){ items = []; } this.size = function(){ return items.length; } } var s = new Stack(); s.push("0"); 10 进制转换成 n 进制, 用的是余数法： function tenToN(number, n){ var yushu; var s = new Stack(); //我们用的是栈的思想，先进后出 var resault = ""; while(number > 0){ yushu = number % n; s.push(yushu); number = Math.floor(number / n); } while(!s.isEmpty()){ resault += s.pop(); } return resault; } - 栈作用： 在编程语言的编译器和内存中保存变量、方法调用
- 函数调用的时候，是在内存栈里入栈
函数真正执行的时候，是在内存栈里出栈
(Tips: 所以说递归如果没有出口，是不停入栈而不出栈，会导致栈溢出)
队列
- 先进先出，队列应该有如下方法
- 入列 enqueue()
- 出列 dequeue()
- 查看列头 front()
-
使用数组实现队列结构 function Queue(){ var items = []; this.enqueue = function(ele){ items.push(ele); } this.dequeue = function(){ return items.shift(); } this.front = function(){ return items[0]; } this.isEmpty = function(){ return items.length == 0; } this.clear = function(){ items = []; } this.size = function(){ return items.length; } this.getItem = function(){return items;} } //击鼓传花游戏,花每传三次，花在谁手上就把谁踢出去 function flowerTurn(items, number){ var q = new Queue(); for(var item in items){q.enqueue(items[item]);} while(q.size() > 1){ for (var i = 1; i < number - 1; i ++){ q.enqueue(q.dequeue()); //相当于要一个无线循环队列，当 队列头 出列后 直接入列 到队尾 } console.log("淘汰的玩家是：" + q.dequeue()); } console.log("最后的胜利者是：" + q.dequeue()); } //参与人员 var names = ["a", "b", "c", "d", "e", "f"]; //游戏规则 var number = 3; flowerTurn(names, number); - 队列的应用： 下载文件， 上传文件，打印文件
- 优先队列
//飞机 高级会员 优先登机 //优先级 //小明 3 //小黑 5 function PriorityQueue(){ var items = []; //辅助类 var QueueItem = function(element, priority) { this.element = element; this.priority = priority; } //只有入列不一样，其他方法和正常队列都是一样的 this.enqueue = function(element, priority){ var queueItem = new QueueItem(element, priority); //比较优先级 var added = false; for (var i = 0; i < items.length; i++){ if(priority > items[i].priority) { //新加入的成员优先级比当前 item 优先级高，则插入到当前元素的前面去 items.splice(i, 0, queueItem); //数组方法 splice(被切割的元素位置，切割掉多少个元素，想要添加的元素...) added = true; //插入成功 break; } } if(!added){items.push(queueItem);} //没有插入成功证明优先级最低，直接入列到队尾 } this.getItems = function(){console.log(items);} } var p = new PriorityQueue(); p.enqueue("小明",1); p.enqueue("小黑",5); p.enqueue("小蓝",3); p.getItems();
链表
- 每个元素都有下个元素的位置
火车 ： 每一列(note) 不仅要携带自己的乘客(item)，还要与下一节火车相连(next)。
链表包括以下属性和方法- 链表头 head
- 链表尾 (链表尾的标志是 current.next == null;)
- node 链表元素
- element (自己的属性)
- next (链接下一个节点)
- append() 链表尾部添加元素
- insert() 链表某个位置插入元素
- removeAt() 移除链表中任意位置元素
- indexof() 获取元素第一次出现的位置
- isEmpty(); size();
-
链表 var LinkList = function(){ //链表头 var head = null; //链表长度， 由于链表不是数组实现的，所以要自己记录长度 var length = 0; //链表元素类 var Node = function(element){ this.element = element; this.next = null; } //链表尾部添加元素 this.append = function(element){ var node = new Node(element); if(head == null){ //当链表中没有元素的时候 head = node; }else{ //当链表中有元素的时候 var current = head; while(current.next){ //遍历链表到尾部 既：current.next == null current = current.next; } current.next = node; //while 循环完毕后，把元素添加到链表尾部 } length ++; } this.getHead = function(){ return head; } //链表某个位置插入元素 this.insert = function(position, element){ if (position == 0){//在表头添加 var node = new Node(element); var current = head; head = node; head.next = current; length ++; }else if (position > -1 && position < length){ //越界问题 var node = new Node(element); //在链表中插入元素 var index = 0; var current = head; var previous = null; //上一个元素 while (index < position) { previous = current; current = current.next; index ++; } previous.next = node; node.next = current; length ++; } } //移除链表中任意位置元素 this.removeAt = function(position){ if(position > -1 && position < length) {//判断越界 if(position == 0){ //移除表头 head = head.next; }else{ var current = head; var index = 0; var previous = null; while (index < position) { previous = current; current = current.next; index ++; } previous.next = current.next; } length --; } } //获取元素第一次出现的位置, 这里我们就对String 类型的 indexof 的方法有了更深了理解 this.indexof = function(element){ var current = head; var index = 0; while(current){ if(element === current.element) {return index;} index ++; current = current.next; } return -1; } this.remove = function(element){ var index = this.indexof(element); while(index != -1){ this.removeAt(index); index = this.indexof(element); } } this.isEmpty = function(){ return length == 0; } this.size = function(){ return length; } }
集合 Set
- 集合是一个数学概念 如 A = {1,2,3}
它很像 js 里的对象 - 集合的特点
- 无重复性， 集合不能有重合的元素
- 空集
- 子集
- 集合方法
- has(value); 是否存在
- remove(value);
- add(value);
- 集合间操作
- union 并集
- intersection 交集
- difference 差集 : A 中要排除 B 的元素
-
集合代码实现 var Set2 = function(){ var items = {}; this.has = function(value){ return items.hasOwnProperty(value); } this.remove = function(value){ if(this.has(value)){ delete items[value]; return true; } return false; } this.add = function(value){ if(!this.has(value)){ items[value] = value; return value; } return false; } this.getItems = function(){ return items; } this.clear = function(){ items = {}; } this.size = function(){ //兼容性好的传统方法 var length = 0; for(var item in items) { //for in 循环，专门遍历对象属性的 if (items.hasOwnProperty(item)){length ++;} //过滤继承的属性，值遍历自己的属性 } return length; //这个是 es6 的方法,除了 IE 老版本外，都能兼容 //return Object.keys(items).length; } //得到集合里的值并以数组形式返回 this.value = function(){ var arr = []; for(var item in items) { //for in 循环，专门遍历对象属性的 if (items.hasOwnProperty(item)){ arr.push(item); } } return arr; } //并集 this.union = function(otherSet){ var resultSet = new Set2(); //1.把自己的值提取出来 var arr = this.value(); for(var i = 0; i < arr.length; i++){ resultSet.add(arr[i]); } //2.把传来过的值提取出来 arr = otherSet.value(); for(var i = 0; i < arr.length; i++){ resultSet.add(arr[i]); } return resultSet; } //交集 this.intersection = function(otherSet){ var resultSet = new Set2(); //1.把自己的值提取出来，然后判断 B 里是否有这个元素 var arr = this.value(); for(var i = 0; i < arr.length; i++){ if (otherSet.has(arr[i])) resultSet.add(arr[i]); } return resultSet; } //差集 this.different = function(otherSet){ var resultSet = new Set2(); //1.把自己的值提取出来，然后判断 B 里是否有这个元素 var arr = this.value(); for(var i = 0; i < arr.length; i++){ if (!otherSet.has(arr[i])) resultSet.add(arr[i]); } return resultSet; } } //由于集合是不能重复的，所以我们用对象来实现 value 和 key 相等，键值相等来实现 var a = new Set2(); a.add(1); a.add(2); var b = new Set2(); b.add(2); b.add(3); var c = a.union(b); //交集 - 为何我们的集合用 Set2 而不用 Set 呢？
因为 es6 给我们提供了以下两种内置数据结构 ： Set 集合; WeakSet 弱集合
Set 和 WeakSet 最大区别 ： 强引用和弱引用var obj = {name: "Tracy"}; var s = new Set(); s.add(obj); obj = null; //此时 s 里仍然保留了 obj 的值, s 会一直指向 obj var obj2 = {name: "Tracy"}; var ws = new WeakSet(); ws.add(obj2); obj2 = null; //此时 ws 里就已经找不到 obj2 的值了- Set 集合的方法
- new Set([1,2,3]); 创建对象的时候可以直接初始化元素
- add
- clear
- delete
- forEach 遍历方法
var s = new Set(); s.add(1);
s.forEach(function(key,value, set){}); - entire 获得迭代器
var interator = s.entire(); interator.next().value;
interator.next().value;
每次调用都不断返回下一项 - has
- size
- value() 获取全部值
//并集 var a = new Set([1, 2, 3]); var b = new Set([4, 3, 2]); var union = new Set([...a, ...b]); // {1, 2, 3, 4} //交集 var a = new Set([1, 2, 3]); var b = new Set([4, 3, 2]); var intersect = new Set([...a].filter(x => b.has(x))); // {2, 3} var intersect = new Set([...a].filter(function(x){ return b.has(x); // filter 也是es6 里针对数组的一个方法，结果为 true 的时候 数组的值会被保留 }); // 差集 var a = new Set([1, 2, 3]); var b = new Set([4, 3, 2]); var difference = new Set([...a].filter(x => !b.has(x))); // {1} - WeakSet 集合的方法
- add, 注意这里传的参数必须是对象， 因此 s.add(1); 会报错， 必须是 s.add({"name":"Tracy"});
- delete
- has
- Set 集合的方法
字典(Dictionary)
- 字典是一种类似集合的数据结构，只不过集合是键值相等而已(key = value)
Set{1:1, 2: 2}
Dictionary{"name": "Tracy", "age" : 16}
字典的 key 不能重复，value 可以相同 - 字典的方法
- 添加键值对 set(key, value)
- 通过键值移除元素 delete(key)
- 检查键 has(key)
- 由键获取值 get(key)
-
var Dictionary = function(){ var items = {}; this.has = function(key){ return items.hasOwnProperty(key); //方法 2 return key in items; } this.set = function(key, value){ items[key] = value; } this.delete = function(key){ if (this.has(key)) { delete items[key]; return true; } return false; } this.get = function(key){ return items[key]; } this.getItems = function(){ return items; } //获取全部键名 es6 this.keys = function(){ return Object.keys(items); } }
散列表(哈希表 HashTable) 和 散列算法
-
名称/键 散列函数 散列值 散列表 Jobs
Bob
Adam74+111+98+115
66+111+98
85+100+97+109398
275
371[275] bob@qq.com
[...]
[371] Adma@163.com
[...]
[398] jobs@qq.com - 散列表和其他数据结构
其他数据结构: 获取值的时候需要遍历元素
散列表： 可以快速定位元素，效率高
我的个人理解，哈希表就是把一个原来对象的存储，标变成了一个数组的存储。
对象在调用或者删除的时候需要从头遍历一遍
[{name : "tracy", email : "tracy@qq.com"}, {name : "bob", email : "bob1@qq.com"}]
而变成了数组，就是将 name 通过一定方式转换成数字，变成了数组的 key,然后 email 变成了数组的
value var items = [,,...,"tracy@qq.com",...,"bob1@qq.com"]; - 散列表方法
- 添加 put
- 删除
- 索引
-
var HashTable = function(){ var items = []; //散列函数1：冲突相对比较 this.loseloseHashCode = function(key){ //通过ASCII码转换生成key var hash = 0 for (var i = 0; i< key.length; i++) { hash += key[i].charCodeAt(); //计算key的ASCII码 } return hash%37; //loseloseHashCode方法计算关键码的公式，即 ASCII码取余37 } //更好的散列函数2，就不用分离链接和线性探查法了，它就是从根源上解决了原先算法的重复的问题 var djb2HashCode = function(key) { var hash = 5831; for(var i = 0; i < key.length; i++) { hash = hash * 33 + key.charCodeAt(i); } return hash % 1013; } // 新增元素 this.put = function(key,value){ var position = this.loseloseHashCode(key); // 元素在散列表里的地址 items[position] = value; } //移除元素 this.remove = function(key){ items[this.loseloseHashCode(key)] = undefined; } //获取元素 this.get = function(key){ return items[this.loseloseHashCode(key)]; } this.getItems = function(){ return items; } } var ht = new HashTable(); ht.put("tracy", "123@qq.com"); ht.put("bob", "bob@qq.com"); ht.getItems(); //上面散列函数有一个缺陷，也就是计算出来的关键码 hash 有可能会相同，以至于在存储过程中会产生冲突。下面介绍两个改善的方法，可以更好的避免此类问题的发生。分离链接法//分离链接法，当两个名字的值的 assic code 相等的时候，会被覆盖，那么我们就在值相等的时候，存储到一个链表里 //它的缺点就是牺牲了快速定位，回到了线性查找来遍历数据 var HashTable_L = function(){ var table = []; //散列函数1：冲突相对比较 this.loseloseHashCode = function(key){ //通过ASCII码转换生成key var hash = 0 for (var i = 0; i< key.length; i++) { hash += key[i].charCodeAt(); //计算key的ASCII码 } return hash%37; //loseloseHashCode方法计算关键码的公式，即 ASCII码取余37 } var Node = function(key, value){ this.key = key; this.value = value; } // 新增元素 this.put = function(key,value){ var position = this.loseloseHashCode(key); // 元素在散列表里的地址 var node = new Node(key,value); if(!table[position]){ var l = new LinkList(); //链表的结构之前写过, 没有值新建链表 table[position] = l; } table[position].append(node); } //移除元素 this.remove = function(key){ var position = this.loseloseHashCode(key); if(table[position]){ //链表线性查找 var current = table[position].getHead(); while(current){ if (current.element.key == key){ table[position].remove(current.element); //如果我们删除了之后这个链表没有东西了，那么我们就释放链表 变成 undefined 来优化程序; if (table[position].isEmpty()) { table[position] = undefined; } return true; } current = current.next; } } return false; } //获取元素 this.get = function(key){ var position = this.loseloseHashCode(key); if(table[position]){ //链表线性查找 var current = table[position].getHead(); while(current){ if (current.element.key == key){ return current.element.value; } current = current.next; } } return undefined; } this.getTable = function(){ return table; } } var ht2 = new HashTable_L(); ht2.put("Ana", "Ana@qq.com"); ht2.put("Donnie", "Donnie@qq.com"); ht2.getTable()[13].getHead(); ht2.get("Ana");线性探查法var HashTable_X = function(){ var table = []; //散列函数1：冲突相对比较 this.loseloseHashCode = function(key){ //通过ASCII码转换生成key var hash = 0 for (var i = 0; i< key.length; i++) { hash += key[i].charCodeAt(); //计算key的ASCII码 } return hash%37; //loseloseHashCode方法计算关键码的公式，即 ASCII码取余37 } var Node = function(key, value){ this.key = key; this.value = value; } // 新增元素,这回不创建列表了，而是看到位置被占了就往下找其他空位， 如我的座位号是13，我发现有人了，我就继续去14，15 查找 this.put = function(key,value){ var position = this.loseloseHashCode(key); // 元素在散列表里的地址 if(table[position] == undefined){ table[position] = new Node(key,value); }else{ //这个位置被占据了 var index = position + 1; while(table[index] != undefined){index++;} table[index] = new Node(key,value); } } //移除元素 this.remove = function(key){ var position = this.loseloseHashCode(key); if(table[position]){ } return false; } //获取元素 this.get = function(key){ var position = this.loseloseHashCode(key); if(table[position]){ } return undefined; } }
类似资料：