数据结构JS版
Opened this issue · 0 comments
Lmagic16 commented
内容：栈、队列、链表、集合、字典、散列表、树
栈
- 通过类封装实现栈结构，不直接继承数组的原生方法的原因是，数组具有某些其他数据结构的方法，为了只让栈暴露栈的方法，还得编写将非栈的方法封闭的代码，多了冗余代码，且不是面向对象编程的合理表现。
//栈，方法包括入栈操作、出栈操作、返回栈顶元素、判断栈是否为空、清空栈、栈的长度
//这里栈实例对象的方法都可看作闭包函数，items可看作类的私有变量，只有类实例的方法来访问，而items也是栈内容的存储实体。
function Stack(){
var items = [];
this.push = function(ele){
items.push(ele);
};
this.pop = function(){
items.pop();
};
this.size = function(){
return items.length;
};
this.clear = function(){
items = [];
};
this.peek = function(){
return items[items.length-1];
}
this.isEmpty = function(){
return items.length > 0 ? false : true;
}
}
var stack = new Stack();
console.log(stack);
stack.push(2);
console.log(stack.size());
console.log(stack.isEmpty());
队列
- 基础实现
//队列，方法包括入队操作、出队操作、返回队首元素、判断队列是否为空、清空队列、队列的长度
function Queue(){
var items = [];
this.inqueue = function(ele){
items.push(ele);
};
this.outqueue = function(){
items.shift();
};
this.size = function(){
return items.length;
};
this.clear = function(){
items = [];
};
this.front = function(){
return items[0];
}
this.isEmpty = function(){
return items.length > 0 ? false : true;
}
}
- 优先级队列
考虑到队列中每个元素具有优先级，所以队列中的元素采用对象来实现，具有两个属性：元素的值和元素的优先级。
//优先级队列
function PriorityQueue(){
var items = [];
function QueueElement(element,priority){
this.element = element;
this.priority = priority;
}
this.inqueue = function(element,priority){
var queueElement = new QueueElement(element,priority);
if(this.isEmpty()){
items.push(queueElement);
}else{
for(var i=0;i<items.length;i++){
if(items[i].priority > priority){
items.splice(i,0,queueElement);
break;
}else if(i === (items.length-1)){
items.push(queueElement);
break; // 这里一定要break，不然会循环插入，导致堆溢出
}
}
}
};
this.outqueue = function(){
items.shift();
};
this.size = function(){
return items.length;
};
this.clear = function(){
items = [];
};
this.front = function(){
return items[0].element;
}
this.isEmpty = function(){
return items.length > 0 ? false : true;
}
this.get = function(){
return items;
}
}
- 循环队列/击鼓传花游戏
可以换个角度想：一排凳子，所有人循环去坐，击鼓之后，坐在第一个凳子（队头）上的人淘汰，即下面代码参考的思路。
//循环队列
//击鼓传花游戏，以固定循环次数来模拟每轮击鼓的固定时长，该游戏会一轮一轮迭代，每轮淘汰一人，直到只剩最后一人即为胜者
function hotPotato(namelist,num){
var queue = new Queue();
for(var i=0;i<namelist.length;i++){
queue.inqueue(namelist[i]);
}
while(queue.size() > 1){
for(i=0;i<num;i++){
var nowElement = queue.front();
queue.outqueue();
queue.inqueue(nowElement);
}
var deletElement = queue.front();
queue.outqueue();
console.log(deletElement+"在击鼓传花游戏中被淘汰");
}
return queue.front();
}
var list = ["hahah","askdjvzxv","uuuuu","aaaaa","bbbbbb","ccccc"];
var winner = hotPotato(list,5);
console.log("胜利者是："+winner);
链表
- 由于链表中每个元素都有指向下一个元素的指针，所以链表中每个元素利用对象来实现，对象具有两个属性：元素的值和指向下一个元素的指针；在指定位置插入或删除元素，都需要注意与前一个和后一个元素之间指针的关系；
//链表，元素在内存中非连续放置，方法包括链表尾部加入/删除元素，链表指定位置加入/删除元素，找出元素在链表中的索引，链表是否为空，链表的长度
function LinkedList(){
var head = null;//链表第一个元素的引用
var length = 0;//链表的长度，不然寻求size很麻烦
var end = null;//链表最后一个元素的引用，方便插入/删除元素
function Node(element){
this.element = element;
this.next = null;
}
//从链表尾部加入node元素
this.appendList = function(element){
var node = new Node(element);
if(head === null){
head = node;
}else{
end.next = node;
}
end = node;
length++;
};
//从链表指定位置加入node元素,0表示在链表头插入该元素
this.appendListAt = function(position,element){
var node = new Node(element);
if(position > 0){
var frontNode = this.findNodeAt(position);
var afterNode = frontNode.next;
frontNode.next = node;
node.next = afterNode;
length++;
}else if(position === 0){
node.next = head;
head = node;
length++;
}
};
//从链表尾部删除node元素
this.removeList = function(){
if(head !== null){
var findNode = this.findNodeAt(length-1);
end = findNode;
findNode.next = null;
length--;
}
};
//从链表指定位置删除node元素
this.removeListAt = function(position){
if(position > 1){ //永远检测用户输入
var frontNode = this.findNodeAt(position-1);
var afterNode = frontNode.next.next;
frontNode.next = afterNode;
length--;
}else if(position = 1){
head = head.next;
length--;
}
};
//链表的大小
this.size = function(){
return length;
};
this.isEmpty = function(){
return head === null ? true : false;
}
this.toString = function(){
var iterNode = head;
var outString = [];
outString.push(head.element);
for(var i=1;i<length;i++){
iterNode = iterNode.next;
outString.push(iterNode.element);
}
return outString;
}
//封装一个可共用的函数，找出指定位置的node元素
this.findNodeAt = function(position){
var iterNode = head;
while(position > 1){
iterNode = iterNode.next;
position--;
}
return iterNode;
}
}
集合
- 采用对象来实现集合，对象的属性存放元素值，因为对象中的属性无序，可以很好地模拟集合的特性
//集合，集合类的方法包括添加/删除元素，是否有某值，清除集合，集合大小
function Set(){
var items = {};
this.has = function(value){
return items.hasOwnProperty(value);
}
//向集合中添加元素
this.add = function(value){
if(!this.has(value)){
items[value] = value;
return true;
}
return false;
}
//删除集合中的元素
this.remove = function(value){
if(this.has(value)){
delete items[value]; // 删除元素的属性
}
return false;
}
this.size = function(){
return Object.keys(items).length;
}
this.clear = function(){
items = {};
}
this.values = function(){
return Object.keys(items); //返回对象自身中可枚举属性
}
//集合的交集，并集，差集，子集方法
//并集
this.union = function(setB){
var setAvalues = this.values();
var setUnion = new Set();
for(var i=0;i<setAvalues.length;i++){
setUnion.add(setAvalues[i]);
}
var setBvalues = setB.values();
for(var j=0;j<setBvalues.length;j++){
setUnion.add(setBvalues[j]);
}
return setUnion;
}
//交集
this.intersection = function(setB){
var setAvalues = this.values();
var intersectionSet = new Set();
var setBvalues = setB.values();
for(var i=0;i<setAvalues.length;i++){
if(setB.has(setAvalues[i])){
intersectionSet.add(setAvalues[i]);
}
}
return intersectionSet;
}
//差集
this.difference = function(setB){
var setAvalues = this.values();
var differenceSet = new Set();
var setBvalues = setB.values();
for(var i=0;i<setAvalues.length;i++){
if(!setB.has(setAvalues[i])){
differenceSet.add(setAvalues[i]);
}
}
return differenceSet;
}
//子集
this.isSubsetOf = function(setB){
var setAvalues = this.values();
var setBvalues = setB.values();
for(var i=0;i<setAvalues.length;i++){
if(!setB.has(setAvalues[i])){
return false;
}
}
return true;
}
}
字典
- 有集合的实现类似
//采用对象来实现字典，以key-value的形式存储，因为对象中的属性无序，字典的方法包括通过key来添加/删除元素，是否有某值，清除字典，字典大小
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 false;
}
//获取固定的值
this.get = function(key){
return this.has(key) ? items[key] : undefined;
}
this.size = function(){
return Object.keys(items).length;
}
this.clear = function(){
items = {};
}
this.keys = function(){
return Object.keys(items); //返回对象自身中可枚举属性
}
this.values = function(){
var res = [];
for(key in items){
if(items.hasOwnProperty(key)){
res.push(items[key]);
}
}
return res;
}
//获取整个字典对象
this.getItems = function(){
return items;
}
}
二叉搜索树
- 二叉搜索树中每个节点都有三个属性。值，左引用，右引用。
- 注意在实现时，拿到节点对象的引用，并不能对节点本身进行删除，最好删除节点的方法是将上一个节点的引用指向置为null，并将节点对象的引用置为null（释放内存，通知垃圾回收）
//二叉搜索树
function BinarySearchTree(){
var rootNode = null;
function TreeNode(key){
this.key = key;
this.left = null;
this.right = null;
}
//向树中插入新节点
this.insert = function(key){
var treeNode = new TreeNode(key);
if(rootNode === null){
rootNode = treeNode;
}else{
insertNode(rootNode,treeNode);
}
}
function insertNode(node,treeNode){
if(treeNode.key < node.key){
if(node.left === null){
node.left = treeNode;
}else{
insertNode(node.left,treeNode);
}
}else if(treeNode.key > node.key){
if(node.right === null){
node.right = treeNode;
}else{
insertNode(node.right,treeNode);
}
}
}
//先序遍历
this.preOrderTraverse = function(){
if(rootNode === null){
console.log("没有节点");
}else{
pretraverse(rootNode);
}
}
function pretraverse(node){
if(node !== null){
pretraverse(node.left);
console.log(node.key);
pretraverse(node.right);
}
}
//中序遍历
this.inOrderTraverse = function(){
if(rootNode === null){
console.log("没有节点");
}else{
intraverse(rootNode);
}
}
function intraverse(node){
if(node !== null){
console.log(node.key);
intraverse(node.left);
intraverse(node.right);
}
}
//后序遍历
this.posOrderTraverse = function(){
if(rootNode === null){
console.log("没有节点");
}else{
postraverse(rootNode);
}
}
function postraverse(node){
if(node !== null){
postraverse(node.left);
postraverse(node.right);
console.log(node.key);
}
}
//移除树中的节点
this.remove = function(key){
rootNode = removeNode(rootNode,key);
}
function removeNode(node,key){
if(node === null){
return null;
}
if(key < node.key){
node.left = removeNode(node.left,key);
return node; //与下面三个return node的功能都是保证removeNode的返回值为删除节点后树的根节点
}else if(key > node.key){
node.right = removeNode(node.right,key);
return node;
}else{
if(node !== null){ //考虑到被删除节点的三种情况
if((node.left === null) && (node.right === null)){
node = null;//这里只是为了垃圾回收node，下面作用都类似
return node;//这里才是删除的功能，这里的返回是为了让node.left = removeNode(node.left,key);中node.left=null;
}else if((node.left === null) && (node.right !== null)){
var temp = node.right;
node = null;
return temp;
}else if((node.left !== null) && (node.right === null)){
var temp = node.left;
node = null;
return temp;
}else if((node.left !== null) && (node.right !== null)){
var findNode = findMin(node.right);
node.key = findNode.key;
node.right = removeNode(node.right,findNode.key);
return node;
}
}
}
}
function findMin(node){
while(node.left !== null){
node = node.left;
}
return node;
}
//查找某个节点
this.search = function(key){
var node = rootNode;
while((node !== null) && (node.key !== key)){
if(key < node.key){
node = node.left;
}else if(key > node.key){
node = node.right;
}
}
return (node !== null) ? true : false;
}
//获取树中最小值
this.min = function(){
var node = rootNode;
while(node.left !== null){
node = node.left;
}
return node.key;
}
//获取树中最大值
this.max = function(){
var node = rootNode;
while(node.right !== null){
node = node.right;
}
return node.key;
}
this.getRootNodeKey = function(){
return rootNode.key;
}
}