常见数据结构_三种常见的数据结构

数据结构大致分为3类

1，线性结构 ： 元素之间是“一对一”的关系 ， 典型有： 数组，对列，栈，线性表
2，树形结构 ： 元素之间是”一对多“的关系 ， 典型有：树，堆
3，图形结构 ： 元素之间是”多对多“的挂安息，

常见的数据结构：

队列

队列是一种特殊的线性表，也就是 ”先进先出 “；义端进，另一端出。插入元素的一端称为对尾（进队），删除元素的一端称为队头（出队）

正向队列：后进前出
反向队列：前进后出
1
2

根据数组的 push()和shift()实现正向对列
unshift()和pop()实现反向队列

正向队列实现

function Queue( ){
	var items = [ ];
	this.entryQueue=function(element){     //插入元素   入队
		items.push(element);
	}；
	this.deleteQueue=function(){       //删除元素      出对
		return items.shift() ;
	}；
	this.isEmpty()=function{             //队列是否为空
		return items.length == 0;
	}；
	this.size()=function{         //队列长度
		return items.length;
	}；
	this.clear()=function{       //清空队列
		items = [ ];
	}；
	this.print=function(){      //打印队列
		console.log(items.toString())
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

栈

栈是一种 ”后进先出“ 的数据结构， 只允许在同一端插入和删除元素，这一端叫栈顶， 另外一端叫栈底

链表

链表储存了一个head指针（称为头节点），该指针存放了一个地址指向一个元素。链表的每个元素称为节点，每个节点包括两个部分： 1，数据部分：用户所需的实际数据 （该节点存放的数据） 2，地址部分：下一个节点的地址 。 因此head指向第一个元素，第一个元素指向第二个元素 ，，，，，直到最后一个元素，该元素不再指向其他元素，称为”表尾“。它的地址部分存放了一个null,表示空地址。

***向链表中插入一个节点***的效率很高，需要修改它前面的节点（前驱），让它指向新插入进来的节点，而新节点指向原来前驱节点指向的节点即可。

删除节点 让要删除的节点的前驱节点指向要删除节点的后继节点，要删除的节点指向null就可以了

设计基于对象的链表：

Node类表示节点

//节点
function Node(){
	this.data = data ;      //当前节点的数据
	this.next = null ;        //下一个节点地址
}
1
2
3
4
5

LinkedList提供插入节点，添加节点，显示链表的方法

function LList(){
	this.head = new Node('head');       //头节点
}
1
2
3

链表又分为单链表，静态链表，循环链表，双向链表
1

单向链表

就是很单一的向下传递。每个节点只记录下一个节点的信息。

双向链表

每个节点不仅存了下一个节点的指针，还存了前一个节点的指针。

使用js实现链表，首先得知道链表最基本 的包括 数据（data）, 前一个节点指针（preNode）,下一个节点指针（nextNode）

js实现链表

首先创建一个链表

function NodeList(data,pre,next){
	this.data = data;
	this.preNode = pre;
	if(this.preNode){
		pre.nextNode = this;
	}
	this.nextNode = next;
}
1
2
3
4
5
6
7
8

插入节点

//在某个节点的后面插入一个节点   this代表这个节点
NodeList.prototype.insertNode=function(node){
	if(this.nextNode && this.nextNode.preNode){
		this.nextNode.preNode = node;
	}
	node.preNode = this;
	this.nextNode = node;
}
1
2
3
4
5
6
7
8

删除某个节点

//this表示要删除的节点
NodeList.prototype.removeNode = function(){
	this.nextNode.preNode = this.preNode;
	this.preNode.nextNode = this.nexNode;
}
1
2
3
4
5

反序链表

反序链表指当前节点的前驱节点变为后继节点，后继节点变为前驱节点

js实现反序链表

NodeList.prototype.reverseNode = function(){
		var temp = null；
		function reverse(){
				if(!this.nextNode){      //如果某个节点的没有下一个节点，那么他就是最后一个节点，就把它变成第一个，即它没有前驱节点
					this.preNode = null;
					this.nextNode = temp;
					return this;
				}else{       //如果当前节点有下一个节点，那么它的前驱节点变成后继节点，后继节点变为前驱节点
             		this.preNode = this.nextNode;
           	  		this.nextNode = temp;
            	 	temp = this;
             		return reverse.call(this.preNode);
     	  		}
		}
		return reverse.call(this);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17