首页 > 代码库 > 《数据结构与算法-Javascript描述》
《数据结构与算法-Javascript描述》
今年的上半年，项目原因大部分时间在写js，这期间把easyui，echarts，bootstrap都用了点皮毛，写的多了，自然也多了些感觉，不过仅局限于运用层面，于是决定再系统的看些javascript方面的书，强化运用能力，便有了这本~来自于国内知名公司前端工程师翻译自国外的书，见名知意用Javascript角度来讲数据结构和算法，一方面可以把javascript的基础知识加强，一方面加深数据结构以及算法的理解和应用。
全书篇幅不长，第一章简明扼要对javascript做了简单的介绍，基本语法、运算符、流程控制方面的基础知识，中间按章节依次对常用数据结构进行讲解。javascript除提供原生态的数组外，其他数据结构都需要自己实现，没有高级语言c#，java来的这么方便。常用数据结构分别是列表，栈，队列，链表，字典，散列，集合，二叉树，图，最后三章是算法相关，分别是排序算法、检索算法、以及两个高级算法，动态规划和贪心算法。
本书循序渐进，层层深入，从最基础的列表开始，到栈、队列，链表、hashtable、set、tree等的实现结合代码通俗易懂的呈现出来， 并结合一些实例加强对数据结构的理解。
在看完数据结构部分章节后，并动手将书中的示例敲了一遍加深印象，与此同时还有额外的收获，对js中的this关键字有了更进一步的理解。重温了一遍数据结构在js中的实现，特别是hashtable章节，对散列过程中的碰撞做了很详细的说明，如何避免碰撞的产生和提升性能方面都给出了解决方案，为今后编写高质量代码和优化代码提供了一定的借鉴作用。
列表
<!doctype html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="Generator" content="EditPlus®"> <meta name="Author" content=""> <meta name="Keywords" content=""> <meta name="Description" content=""> <title>Javascript-List</title> </head> <body> <script type="text/javascript"> function List(){ this.listSize=0; this.pos=0; this.dataStore=[]; this.clear=clear; this.find=find; this.toString=toString; this.insert=insert; this.append=append; this.remove=remove; this.front=front; this.end=end; this.prev=prev; this.next=next; this.length=length; this.currPos=currPos; this.moveTo=moveTo; this.contains=contains; this.getElement=getElement; } function append(element){ this.dataStore[this.listSize++]=element; } function find(element){ for(var i=0;i<this.dataStore.length;i++){ if(this.dataStore[i]==element){ return i; } } return -1; } function remove(element){ var foundAt=this.find(element); if(foundAt>-1){ this.dataStore.splice(foundAt,1); --this.listSize; return true; } return false; } function length(){ return this.listSize; } function toString(){ return this.dataStore; } function clear(){ delete this.dataStore; this.dataStore=[]; this.listSize=this.pos=0; } function insert(element,after){ var insertPos=this.find(after); if(insertPos>-1){ this.dataStore.splice(insertPos+1,0,element); ++this.listSize; return true; } return false; } function front(){ this.pos=0; } function end(){ this.pos=this.listSize-1; } function prev(){ if(this.pos>0){ --this.pos; } } function next(){ if(this.pos<this.listSize-1){ ++this.pos; } } function currPos(){ return this.pos; } function contains(element){ for(var i=0;i<this.dataStore.length;i++){ if(this.dataStore[i]==element){ return true; } } return false; } function getElement(){ return this.dataStore[this.pos]; } var names=new List(); names.append("123"); names.append("456"); names.append(1); names.append("789"); console.log(names.toString()); names.front(); names.next(); names.next(); console.log(names.getElement()); </script> </body></html>
栈
<!doctype html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="Generator" content="EditPlus®"> <meta name="Author" content=""> <meta name="Keywords" content=""> <meta name="Description" content=""> <title>Javascript-Stack</title> </head> <body> <script type="text/javascript"> function Stack(){ this.dataStore=[]; this.top=0; this.push=push; this.pop=pop; this.peek=peek; this.length=length; } function push(element){ this.dataStore[this.top++]=element; } function pop(){ return this.dataStore[--this.top]; } function peek(){ return this.dataStore[this.top-1]; } function length(){ return this.top; } function clear(){ this.top=0; } var s=new Stack(); s.push("1"); s.push("2"); console.log(s.length()); console.log(s.pop()); console.log(s.length()); s.push("3"); console.log(s.length()); console.log(s.peek()); s.pop(); console.log(s.peek()); function isPalindrome(word){ var s=new Stack(); for(var i=0;i<word.length;i++){ s.push(word[i]); } var rword=""; while(s.length()>0){ rword+=s.pop(); } if(word==rword){ return true; }else{ return false; } } var word="hello"; console.log(word +" is palindrome : "+isPalindrome(word)); word="level"; console.log(word +" is palindrome : "+isPalindrome(word)); word="racecar"; console.log(word +" is palindrome : "+isPalindrome(word)); </script> </body></html>
队列
<!doctype html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="Generator" content="EditPlus®"> <meta name="Author" content=""> <meta name="Keywords" content=""> <meta name="Description" content=""> <title>Javascript-Queue</title> </head> <body> <script type="text/javascript"> function Queue(){ this.dataStore=[]; this.enqueue=enqueue; this.dequeue=dequeue; this.front=front; this.back=back; this.toString=toString; this.empty=empty; } function enqueue(element){ this.dataStore.push(element); } function dequeue(){ return this.dataStore.shift(); } function front(){ return this.dataStore[0]; } function back(){ return this.dataStore[this.dataStore.length-1]; } function toString(){ var reStr=""; for(var i=0;i<this.dataStore.length;i++){ reStr+=this.dataStore[i]+"\n"; } return reStr; } function empty(){ if(this.dataStore.length==0){ return true; }else{ return false; } } var q=new Queue(); q.enqueue("1"); q.enqueue("2"); q.enqueue("3"); console.log(q.toString()); q.dequeue(); console.log(q.toString()); console.log("front:"+q.front()); console.log("back:"+q.back()); </script> </body></html>
链表
<!doctype html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="Generator" content="EditPlus®"> <meta name="Author" content=""> <meta name="Keywords" content=""> <meta name="Description" content=""> <title>javascript-linkList</title> </head> <body> <script type="text/javascript"> function Node(element){ this.element=element; this.next=null; } function LList(){ this.head=new Node("head"); this.find=find; this.insert=insert; this.remove=remove; this.display=display; this.findPrevious=findPrevious; } function find(item){ var currNode=this.head; while(currNode.element!=item){ currNode=currNode.next; } return currNode; } function insert(newElement,item){ var newNode=new Node(newElement); var current=this.find(item); newNode.next=current.next; current.next=newNode; } function display(){ var currNode=this.head; while(!(currNode.next==null)){ console.log(currNode.next.element); currNode=currNode.next; } } function findPrevious(item){ var currNode=this.head; while(!(currNode.next==null)&& (currNode.next.element!=item)){ currNode=currNode.next; } return currNode; } function remove(item){ var preNode=this.findPrevious(item); if(!(preNode.next==null)){ preNode.next=preNode.next.next; } } var cities=new LList(); cities.insert("beijing","head"); cities.insert("shanghai","beijing"); cities.insert("shenzhen","shanghai"); cities.display(); cities.remove("shanghai"); cities.display(); </script> </body></html>
Hashtable
<!doctype html><html lang="en"> <head> <meta charset="UTF-8"> <meta name="Generator" content="EditPlus®"> <meta name="Author" content=""> <meta name="Keywords" content=""> <meta name="Description" content=""> <title>javascript-hashtable</title> </head> <body> <script type="text/javascript"> function Hashtable(){ this.table=new Array(137); this.simpleHash=simpleHash; this.betterHash=betterHash; this.showStorage=showStorage; this.put=put; } function put(data){ //var pos=this.simpleHash(data); var pos=this.betterHash(data); this.table[pos]=data; } function simpleHash(data){ var total=0; for(var i=0;i<data.length;i++){ total+=data.charCodeAt(i); } //console.log(data+":"+total); return total%this.table.length; } function showStorage(){ var n=0; for(var i=0;i<this.table.length;i++){ if(this.table[i]!=undefined){ console.log(i+": "+this.table[i]); } } } function betterHash(data){ const H=37; var total=0; for(var i=0;i<data.length;i++){ total+=H*total+data.charCodeAt(i); } total=total%this.table.length; //console.log(total); if(total<0){ total+=this.table.length-1; } return parseInt(total); } var someNames = ["David", "Jennifer", "Donnie", "Raymond","Cynthia", "Mike", "Clayton", "Danny", "Jonathan"]; var hTable = new Hashtable(); for (var i = 0; i < someNames.length; ++i) { //console.log(someNames[i]+":"+someNames[i].charCodeAt(i)); hTable.put(someNames[i]); } hTable.showStorage(); </script> </body></html>
集合
<!doctype html><html lang="en"><head> <meta charset="UTF-8"> <meta name="Generator" content="EditPlus®"> <meta name="Author" content=""> <meta name="Keywords" content=""> <meta name="Description" content=""> <title>javascript-set</title></head><body> <script type="text/javascript"> function Set() { this.dataStore = []; this.add = add; this.remove = remove; this.size=size; this.union=union; this.intersect=intersect; this.subset = subset; this.contains = contains; this.difference=difference; this.show = show; } function add(data) { if (this.dataStore.indexOf(data) < 0) { this.dataStore.push(data); return true; } else { return false; } } function remove(data) { var pos = this.dataStore.indexOf(data); if (pos > -1) { this.dataStore.splice(pos, 1); return true; } else { return false; } } function show() { return this.dataStore; } function contains(data) { if (this.dataStore.indexOf(data) > -1) { return true; } else { return false; } } function union(set) { var tempSet = new Set(); for (var i = 0; i < this.dataStore.length; i++) { tempSet.add(this.dataStore[i]); } for (var i = 0; i < set.dataStore.length; i++) { if (!tempSet.contains(set.dataStore[i])) { tempSet.dataStore.push(set.dataStore[i]); } } return tempSet; } function intersect(set) { var tempSet = new Set(); for (var i = 0; i < this.dataStore.length; i++) { if (set.contains(this.dataStore[i])) { tempSet.add(this.dataStore[i]); } } return tempSet; } function size() { return this.dataStore.length; } function subset(set) { if (this.size() > set.size()) { return false; } else { for (var i = 0; i < this.dataStore.length ; i++) { if (!set.contains(this.dataStore[i])) { return false; } } return true; } } function difference(set) { var tempSet = new Set(); for (var i = 0; i < this.dataStore.length; ++i) { if (!set.contains(this.dataStore[i])) { tempSet.add(this.dataStore[i]); } } return tempSet; } //basic //var names = new Set(); //names.add("David"); //names.add("Jennifer"); //names.add("Cynthia"); //union var cis = new Set(); //cis.add("Mike"); //cis.add("Clayton"); //cis.add("Jennifer"); //cis.add("Raymond"); //var dmp = new Set(); //dmp.add("Raymond"); //dmp.add("Cynthia"); //dmp.add("Jonathan"); //var it = new Set(); //it = cis.union(dmp); //console.log(it.show()); //intersect //var cis = new Set(); //cis.add("Mike"); //cis.add("Clayton"); //cis.add("Jennifer"); //cis.add("Raymond"); //var dmp = new Set(); //dmp.add("Raymond"); //dmp.add("Cynthia"); //dmp.add("Bryan"); //var inter = cis.intersect(dmp); //console.log(inter.show()); // 显示 Raymond //console.log(names.show()); //names.remove("David"); //console.log(names.show()); //subset //var it = new Set(); //it.add("Cynthia"); //it.add("Clayton"); //it.add("Jennifer"); //it.add("Danny"); //it.add("Jonathan"); //it.add("Terrill"); //it.add("Raymond"); //it.add("Mike"); //var dmp = new Set(); //dmp.add("Cynthia"); //dmp.add("Raymond"); //dmp.add("Jonathan"); //if (dmp.subset(it)) { // console.log("DMP is a subset of IT."); //} else { // console.log("DMP is not a subset of IT."); //} //differencce var cis = new Set(); var it = new Set(); cis.add("Clayton"); cis.add("Jennifer"); cis.add("Danny"); it.add("Bryan"); it.add("Clayton"); it.add("Jennifer"); var diff = new Set(); diff = cis.difference(it); console.log("[" + cis.show() + "] difference [" + it.show()+ "] -> [" + diff.show() + "]"); </script></body></html>
《数据结构与算法-Javascript描述》
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。