常见数据结构

缺乏、安全感 2022-03-09 10:08 206阅读 0赞

# 数据结构大致分为3类 #

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

常见的数据结构：

# 队列 #

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

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

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

正向队列实现

# 栈 #

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

# 链表 #

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

\*\*\*向链表中插入一个节点\*\*\*的效率很高，需要修改它前面的节点（前驱），让它指向新插入进来的节点，而新节点指向原来前驱节点指向的节点即可。  
![在这里插入图片描述][20190321183430997.png]

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

设计基于对象的链表：

Node类表示节点

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

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

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

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

# 单向链表 #

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

# 双向链表 #

每个节点不仅存了下一个节点的指针，还存了前一个节点的指针。  
![在这里插入图片描述][2019032517543499.png]  
使用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;
    }

插入节点

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

删除某个节点

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

# 反序链表 #

反序链表指当前节点的前驱节点变为后继节点，后继节点变为前驱节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MjkzNw_size_16_color_FFFFFF_t_70]

# 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);
    }

[20190321182821973.png]: /images/20220309/0e32adb68c7644bc990ec352a254e90b.png
[20190321183430997.png]: /images/20220309/0a38362f476a43b4b9048e61043d17c2.png
[2019032517543499.png]: /images/20220309/2a099da7ed7c494786bf196e19ece02b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MjkzNw_size_16_color_FFFFFF_t_70]: /images/20220309/a2b0eac5979f40b980aadfe6e9da769d.png