js优先队列和链表

js优先队列和链表

//封装优先级队列 function PriorityQueue(){ function QueueElement(element,priority){ this.element=element this.priority=priority } //封装属性 this.items=[] //实现插入方法 PriorityQueue.prototype.enqueue=function(element,priority){ // 1.创建PriorityQueue对象 var queueElement=new QueueElement(element,priority) //2.判断队列是否为空 if(this.items.length===0){ this.items.push(queueElement) }else{ var added=false for(var i=0;i

链表的相关方法：

单链表 //分装链表类    function LinkedList(){

//内部的类：节点类 function Node(data){ this.data=data this.next=null } //属性 this.head=null this.length=0 //1.追加方法 LinkedList.prototype.append=function(data){ //1.创建新的节点 var newNode=new Node(data) //判断是否添加的是第一个节点 if(this.length===0){ //是第一个节点 this.head=newNode }else{ //找到最后一个节点 var current=this.head while(current.next){ current=current.next } //最后节点的 next指向新的节点 current.next=newNode } //3.lenght +1 this.length+=1 } //2.toString方法 LinkedList.prototype.toString=function(){ //1.定义变量 var current=this.head var listString="" //2.循环获取一个个节点 while(current){ listString+=current.data+ " " current=current.next } return listString } //3.insert方法 LinkedList.prototype.insert=function(position,data){ //1.对 position进行越界判读 if(position<0||position>this.length) return false //2.根据 data 创建newNode var newNode=new Node(data) //3.判断插入的位置是否是第一个 if(position===0){ newNode.next=this.head this.head=newNode }else{ var index=0 var current=this.head var previous=null while(index++=this.length) return null //2.获取对应的数据 var current=this.head var index=0 while(index++

//5.indexOf LinkedList.prototype.indexOf=function(data){ //1.定义变量 var current=this.head var index=0 //2.开始查找 while(current){ if(current.data===data){ return index } current=current.next index+=1 } //3.找到最后没有找到，返回-1 return -1 } //6.update方法 LinkedList.prototype.updated=function(position,newData){ //1.越界判断 if(position<0||position>=this.length) return false //2.查找正确的节点 var current=this.head var index=0 while(index++=this.length) return null //2.判断是否删除的是第一个节点 var current=this.head if(position===0){ this.head=this.head.next }else{ var index=0 var previous=null while(index++

双线链表封装：

function DoublyLinkedList(){ //内部类 function Node(data){ this.data=data this.prev=null this.next=null } //属性 this.head=null this.tail=null this.length=0 //常见的操作 //1.append方法 DoublyLinkedList.prototype.append=function(data){ //1.根据 data 创建节点 var newNode=new Node(data) //2.判断添加的是否是第一个节点 if(this.length===0){ this.head=newNode this.tail=newNode }else{ newNode.prev=this.tail this.tail.next=newNode this.tail=newNode } //3.length+1 this.length+=1 } //2.将链表转成字符串形式 //2.1 toString方法 DoublyLinkedList.prototype.toString=function(){ return this.backwardString() } //2.2forwardString 方法 DoublyLinkedList.prototype.forwardString=function(){ //1.定义变量 var current=this.tail var resultString="" //2.依次向前遍历，获取每一个节点 while(current){ resultString+=current.data+" " current=current.prev } return resultString } //2.3backwardString 方法 DoublyLinkedList.prototype.backwardString=function(){ //1.定义变量 var current=this.head var resultString="" //2.依次向后遍历，获取每一个节点 while(current){ resultString+=current.data+" " current=current.next } return resultString } //3.insert 方法 DoublyLinkedList.prototype.insert=function(position,data){ //1.越界判断 if(position<0||position>this.length) return false //2.根据 data 创建新的方法 var newNode=new Node(data) //3.判断原来的列表是否为空 if(this.length===0){ this.head=newNode this.tail=newNode }else{ if(position===0){ //3.1判断 position是否为空 this.head.prev=newNode newNode.next=this.head this.head=newNode }else if(position===this.length){ //3.2position===this.length newNode.prev=this.tail this.tail.next=newNode this.tail=newNode }else{ //3.3其他情况 var current=this.head var index=0 while(index++ < position){ current=current.next } //4.修改指针 newNode.next=current newNode.prev=current.prev current.prev.next=newNode current.prev=newNode } } //4.length+1 this.length+=1 return true } //4.get 方法 DoublyLinkedList.prototype.get=function(position){ //1.越界判断 if(position<0||position>this.length) return null //2.获取元素 var current=this.head var index=0 while(index++=this.length) return false //2.寻找正确的节点 var current=this.head var index=0 while(index++=this.length) return null //2.判断列表中是否只有一个节点 var current=this.head if(this.length===1){ this.head=null this.tail=null }else{ //判断是否删除的是第一个节点 if(position===0){ this.head.next.prev=null this.head=this.head.next }else if(position===this.length-1){//最后节点 current=this.tail this.tail.prev.next=null this.tail=this.tail.prev }else{ var index=0 while(index++

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。