一、栈
javascript实现栈的数据结构(借助javascript数组原生的方法即可)
//使用javascript来实现栈的数据结构 var Stack={ //不需要外界传参进行初始化,完全可以定义为一个属性 items:[], push:function(item){ this.items.push(item); }, pop:function(){ return this.items.pop(); }, peek:function(){ ]; }, isEmpty:function(){ ; }, size:function(){ return this.items.length; }, clear:function(){ this.items=[]; }, print:function(){ console.log(this.items.toString()); } };
栈
javascript栈的应用案例(十进制和其他进制的转换)
//基于栈的数据结构实现进制转换,比如将十进制转换为2进制 function baseConvert(number,base){ var result=Object.create(Stack), rem, baseString='', digits='0123456789ABCDEF', decNumber=number; ){ rem=Math.floor(decNumber%base); result.push(rem); decNumber=Math.floor(decNumber/base); } while(!result.isEmpty()){ baseString+=digits[result.pop()]; } return baseString; } console.log(baseConvert(,));//输出11000011111111001 console.log(baseConvert(,));//输出303771 console.log(baseConvert(,));//输出187F9
进制转换
二、队列
javascript实现队列的数据结构
//实现队列 var Queue={ item:[], enqueue:function(item){ this.items.push(item); }, dequeue:function(){ return this.items.shift(); }, isEmpty:function(){ ; }, front:function(){ ]; }, clear:function(){ this.items=[]; }, size:function(){ return this.items.length; } };
队列
三、链表
单项链表
感觉在javascript中实现单项链表意义不大,因为单项链表的优势在于插入和删除,可是javascript的splice方法就可以实现了呀
//单链表的实现 //感觉在javascript中实现单链表没有什么用 //因为单链表的有事在于插入,删除元素的时间复杂度为O(1),可以javascript中利用数组,调用数组的splice方法,就可以实现这一目的 var Node={ init:function(element){ this.element=element; this.next=null; }, }; var LinkedList={ length:, head:null,//指向队列的头结点 //尾部插入元素 append:function(element){ var node=Object.create(Node), current; node.init(element); if(!this.head){ this.head=node; }else{ current=this.head; while(current.next){ current=current.next; } current.next=node; } this.length++; return true; }, //在任意一个位置插入一个元素 insert:function(position,element){ ||position>=this.length){ return false; } var node=Object.create(Node), current=this.head, previous=this.head, index=; node.init(element); ){ node.next=this.head; this.head=node; }else{ while(index<position){ index++; previous=current; current=current.next; } node.next=current; previous.next=node; } this.length++; return true; }, //从链表中移除元素 removeAt:function(position){ var current=this.head, previous, index=; ||position>=this.length){ return false; } ){ this.head=this.head.next; }else{ while(index<position){ index++; previous=current; current=current.next; } previous.next=current.next; } this.length--; return true; }, //接收一个元素的值,如果在列表中找到它,就返回元素位置,否则返回-1 indexOf:function(element){ var current=this.head, index=; while(current){ if(current.element==element){ return index; }else{ index++; current=current.next; } } ; }, isEmpty:function(){ ; }, size:function(){ return this.length; }, //将LinkedList对象转换为一个字符串 toString:function(){ var current=this.head, baseStr=''; while(current){ baseStr+=current.element+','; current=current.next; } return baseStr; }, print:function(){ console.log(this.toString()); } };
单项链表实现
此外还有双向链表,双向循环链表。这里不多做讨论、
四、集合
//实现集合这种数据结构 //基本思路是基于javascript对象结构的键值来实现,当然也可以基于数组 var Set={ init:function(){ this.items=Object.create(null); }, has:function(item){ return item in this.items; }, add:function(item){ if(!this.has(item)){ this.items[item]=item; return true; } return false; }, remove:function(item){ if(this.has(item)){ delete this.items[item]; return true; } return false; }, clear:function(){ this.items={}; }, size:function(){ return Object.keys(this.items).length; }, values:function(){ return Object.keys(this.items); }, //求并集 union:function(otherSet){ var result=Object.create(Set), key; result.init(); for(key in this.items){ result.add(key); } for(key in otherSet.items){ result.add(key); } return result; }, //求交集 intersection:function(otherSet){ var result=Object.create(Set),key; result.init(); for(key in this.items){ if(otherSet.has(key)){ result.add(key); } } return result; }, };
集合