【前端数据结构】基本数据结构及特点
什么是数据结构
数据元素相互之间存在的一种和多种特定的关系集合 包括二个部分组成逻辑结构，存储结构。
逻辑结构
简单的来说 逻辑结构就是数据之间的关系,逻辑结构大概统一的可以分成两种 一种是线性结构，非线性结构 。
线性结构
是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
常用的线性结构有: 栈，队列，链表，线性表。
非线性结构
各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。
常见的线性结构有 二维数组，树(二叉树等)等。
存储结构
逻辑结构指的是数据间的关系，而存储结构是逻辑结构用计算机语言的实现。 常见的存储结构有顺序存储、链式存储、索引存储以及散列存储（哈希表）。
时间复杂度
一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。
把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度。
没有循环语句，记作O(1)，也称为常数阶。
只有一重循环，则算法的基本操作的执行频度与问题规模n呈线性增大关系，记作O（n），也叫线性阶。
常用的还有平方阶O（n2）、立方阶O（n3）、对数阶O(log2n)等。 常见的时间复杂度有：
O(1)< O(log2n)< O（n）< O（n2）< O（ n3 ）< O（ 2n ）顺序表
把线性表的结点按逻辑顺序一次存放在一组地址连续的存储单元中。
可以直接通过下标获取到数据，查询快。
插入和删除时要移动后续元素，还要考虑扩容问题，插入慢。
function List() { // 列表的元素个数
this.listSize = 0; // 列表的当前位置 是第几个
this.pos = 0; // 初始化一个空数组来保存列表元素
this.dataStore = [];
} List.prototype = (function () { return {
clear: clear,
find: find,
toString: toString,
insert: insert,
append: append,
remove: remove,
front: front,
end: end,
prev: prev,
next: next,
hasNext: hasNext,
hasPrev: hasPrev,
length: length,
currPos: currPos,
moveTo: moveTo,
getElement: getElement
};
/**
* 给列表最后添加元素的时候，列表元素个数+1
* @param element
*/
function append(element) { this.listSize++; this.dataSource.push(element);
} /**
* @param element
* @returns {number} 如果找到，返回位置，否则-1
*/
function find(element) { for (var i = 0; i < this.dataSource.length; i++) { if (this.dataSource[i] === element) { return i;
}
} return -1;
} /**
* 删除元素成功，元素个数-1
* @param element
* @returns {boolean}
*/
function remove(element) { var removeIndex = this.find(element); if (removeIndex !== -1) { this.dataSource.splice(removeIndex, 1); this.listSize--; return true;
} return false;
} /**
* 插入某个元素
* @param element 要插入的元素
* @param afterElement 列表中的元素之后
* @returns {boolean}
*/
function insert(element, afterElement) { var insertIndex = this.find(afterElement); if (insertIndex !== -1) { this.dataSource.splice(insertIndex + 1, 0, element); this.listSize++; return true;
} return false;
} }());链表
用一组任意存储的单元来存储线性表的数据元素。
一个对象存储着本身的值和下一个元素的地址。
需要遍历才能查询到元素，查询慢。
插入元素只需断开连接重新赋值，插入快。
function LinkList(){ function node(element){ this.value = element; this.next = null;
} let length = 0; let head = null;
} LinkList.prototype = { append:function(element){ var node = new node(element); var temp = this.head; if(this.head){ //遍历找到链表的终点
while(temp.next){
temp = temp.next;
}
temp.next = node;
}else{ this.head = node;
} this.length++;
}, insert:function(element,index){ if(index <= this.length && index>0){ var node = new node(element); var currentIndex = 0; var currentNode = this.head; var preNode = null; if (currentIndex === 0) {
node.next = currentNode; this.head = node; return;
} while(currentIndex<index){
preNode = currentNode;
currentNode = currentNode.next;
currentIndex++;
}
preNode.next = node;
node.next = currentNode; this.length++;
}
}
}链表翻转
reverse: function (node) {
//把初始链表头当做基准点，移动下一个元素到头部，直到下一个元素为空
var currentNode = node.next; node.next = node.next.next;
currentNode.next = this.head;
this.head = currentNode;
if(node.next){
this.reverse(node);
}
}z栈
先进后出
进栈：push (在尾部插入元素)
出栈：pop（在尾部删除元素并返回此元素）
队列
先进先出
进队列：unshift（在头部插入元素）
出队列：pop(在尾部删除元素并返回)
哈希表
哈希的基本原理是将给定的键值转换为偏移地址来检索记录。
键转换为地址是通过一种关系（公式）来完成的，这就是哈希（散列）函数。
虽然哈希表是一种有效的搜索技术，但是它还有些缺点。两个不同的关键字，由于哈希函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该哈希函数的同义词(Synonym)。
好的哈希函数的选择有两条标准：
1)简单并且能够快速计算
2)能够在址空间中获取键的均匀人分布
除余法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m
解决hash冲突：链表法
链表法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。
具体的关键字列表为（19,14,23,01,68,20,84,27,55,11,10,79），则哈希函数为H（key）=key MOD 13。则采用除留余数法和链地址法后得到的预想结果应该为：
哈希造表完成后，进行查找时，首先是根据哈希函数找到关键字的位置链，然后在该链中进行搜索，如果存在和关键字值相同的值，则查找成功，否则若到链表尾部仍未找到，则该关键字不存在。
插入元素：直接按地址插入到链表末尾。
综合了链表和数组的优点，查询插入都很快。
构造hash表
function linklist(){
...
}
funtion hashtable{ length 0
data []
}腾讯云开发者
