数据结构浅谈

港控/mmm° 2022-06-17 08:36 227阅读 0赞

*时间：2017年4月21日15:47:46*

[《我的博客地图》][Link 1]

[数据结构][Link 2]是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。[\[百度百科\]][Link 3]

数据结构分为八类：数组-array、队列-queue、堆-heap、栈-stack、链表-linked list、树-tree、图-graph、散列表-hash。

数据结构是人为定义的一种模型，看不见摸不着但可以用概念清晰形容出来，即编程思想；对象和面向对象编程的思想尤为重要，只可意会不可言传，听不懂没关系，可以通过经年累月的摸索和总结去深刻认知。

运用js中一切皆对象的思想，可以很方便的去构造出各种复杂的数据类型对象。所有的数据结构都可以被实现为对象。JavaScript 提供了多种方式来创建和使用对象。这里通过如下方式创建：定义包含属性和方法声明的构造函数， 并在构造函数后紧跟方法的定义。

1、数组

2、栈

栈，stack，存储五种（undefined、null、boolean、number、string）基本数据类型的 值，这些 值 占用的内存空间固定（数据大小确定），由系统自动分配自动释放。（可以直接访问数据）

栈，是一种高效的数据结构， 因为数据只能在栈顶添加或删除， 所以这样的操作很快；是一种特殊的列表， 栈内的元素只能通过列表的一端访问， 这一端称为栈顶；一摞盘子是现实世界中常见的栈的例子；栈具有后入先出的特点， 所以任何不在栈顶的元素都无法访问；为了得到栈底的元素， 必须先拿掉上面的元素。

属性:  
top  栈数组的第一个空位置  
empty 栈内是否含有元素,用 length 属性也可以达到同样的目的  
    方法:  
push() 元素入栈，  
pop() 元素出栈,(也可以访问栈顶的元素，但是调用该方法后，栈顶元素被删除)  
peek() 预览栈顶元素,只返回栈顶元素，不删除它。  
length() 返回栈内元素的个数(top应该是等于数组的length的,所以用top属性也可)  
clear() 清除栈内所有元素

栈类的构造函数  
function Stack() \{  
    this.dataStore = \[\]; //底层数据结构是数组  
    this.top = 0; //top应该是等于数组的length的  
    this.push = push;  
    this.pop = pop;  
    this.peek = peek;  
    this.length = length;  
    this.clear = clear;  
\}

将push() pop() peek() length() clear方法重写就可以得到栈类；

3、队列

4、链表

5、树

6、图

7、堆

堆，heap，存储引用类型（object、array、function）的 值，这些 值 占用的内存空间不定（数据大小不确定），由系统动态分配且不会释放。（引用类型的地址指针存储在 栈 中，当我们访问引用类型的值时，首先从栈中获得该对象的地址指针，然后再从堆内存中取得所需的数据。）

8、散列表

散列表，Hash Table，也叫哈希表，是根据关键码值（key value）而直接进行访问的数据结构

[Link 1]: https://blog.csdn.net/wanshaobo888/article/details/79179440
[Link 2]: http://baike.baidu.com/link?url=CA-L9X9G17rTqOrQQ9lunsaK6kku8Kg2qPdhz6AcMTnDYq2Geeia0xH_ottUGC6aQxN4GIyGRG06kB6oPvIoU4UUsD0sZopEBxGZomtOYxS9S9P7y0HiIFLJnIQeTknp#2
[Link 3]: http://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450