基础数据结构

列表

列表式一种简单的数据结构，列表中元素数量不是很多，是一种有序的数据的结构（这里的有序不是指元素的大小顺序）
接下来，我们自己构建一个列表，自己维护列表的属性

function List() {
    this.listSize = 0; // 列表元素个数
    this.pos = 0; //列表当前位置
    this.dataSource = []; // 源数组
    this.clear = clear; // 列表清空
    this.find = find; // 查找
    this.toString = toString; // return字符串
    this.insert = insert; //插入元素
    this.append = append; // 添加元素
    this.remove = remove; //删除元素
    this.front = front; //当前位置移动到第一个元素
    this.end = end; // 当前位置移动到最后一个元素
    this.prev = prev; // 当前位置前移一位
    this.next = next; //当前位置后移一位
    this.length = length; // 元素数量
    this.currentPos = currentPos; // 返回列表当前位置
    this.moveTo = moveTo; //移动至指定位置
    this.getElement = getElement; // 显示当前元素
    this.contain = contain; // 是否包含
}
function append(element) {
    this.dataSource[this.listSize++] = element;
}
function clear() {
    this.dataSource = [];
    this.length = 0;
    this.listSize = 0;
}
function find(element) {
    for (let i in this.dataSource) {
        if (this.dataSource[i] === element) return i;
    }
    return -1;
}
function remove(element) {
    const index = this.find(element);
    if (index > -1) {
        this.dataSource.splice(index, 1);
        --this.listSize;
        return;
    } else {
        return false
    }
}
function length() {
    return this.listSize;
}
function toString() {
    return this.dataSource.toString();
}
function insert(element, index) {
    this.dataSource.splice(index, 0, element);
    ++this.listSize;
    return true;
}
function clear() {
    this.listSize = this.pos = 0;
    this.length = 0;
    delete this.dataSource;
}
function getElement() {
    return this.dataSource[this.pos]
}
function contain(element) {
    const index = this.find(element)
    return index > -1 ? true : false;
}
function prev() {
    if (this.pos > 0) this.pos--;
}
function next() {
    if (this.pos < this.listSize) this.pos++;
}
function currentPos() {
    return this.pos;
}
function moveTo(position) {
    this.pos = position;
}
function front() {
    this.pos = 0;
}
function end() {
    this.pos = this.listSize--;
}

栈

• 栈是一种特殊的列表
• 栈是一种高效的数据结构，因为栈只能在栈添加和删除，操作很快
• 栈被称为”先进后出“的数据结构

function Stack() {
    this.dataSource = []; //源数据
    this.pop = pop;  // 出栈
    this.push = push;  //进栈
    this.length = length; // 栈长度
    this.peek = peek; // 栈顶元素
    this.clear = clear; // 清空
}

function pop() {
    return this.dataSource.splice(0, 1);
}
function length() {
    return this.dataSource.length;
}
function push(element) {
   return  this.dataSource.splice(0, 0, element);
}
function clear() {
    delete this.dataSource;
}
function peek() {
    return this.dataSource[0]
}

队列

• 一种特殊的列表
• 先进先出
• 包含队首和队尾

function Queue() {
    this.enQueue = enQueue; //入队
    this.deQuue = deQuue; // 出队
    this.front = front; // 队首
    this.end = end; // 队尾
    this.isEmpty = isEmpty; //是否为空队列
    this.toString = toString; // 查看队列
    this.dataSource = []; // 源数据
}
function isEmpty() {
    return this.dataSource.length > 0 ? false : true;
}
function enQueue(element) {
    return this.dataSource.push(element);
}
function deQuue() {
    return this.dataSource.shift();
}
function front() {
    return this.dataSource[0]
}
function end() {
    if(this.isEmpty()) return;
    return this.dataSource[this.dataSource.length - 1]
}
function toString() {
    return this.dataSource;
}

链表

• 链表是一系列节点组成
• 每个节点的引用都指向它的后继（或前驱）
• 链表分为单向和双向链表
• 单向链表插入，需要将前面节点的后继，变成插入节点的前驱，插入节点的后继指向下一个节点
• 单向链表的删除，需要将删除节点的前驱指向删除节点的后继，并将删除节点的后继指向 null

  单向链表

function Node(element) {
    this.element = element;
    this.next=null;
}
function singleLinkedList(){
    this.head=new Node('head');
    this.find=find;
    this.insert=insert;
    this.display=display;
    this.remove=remove;
    this.findNext=findNext;
}
function find(item){
    const currentNode=this.head;
    while(currentNode.element!==item){
        currentNode=currentNode.next;
    }
    return currentNode;
}
function insert(newElement,item){
    const newNode=new Node(newElement);
    const currentNode=this.find(item);
    newNode.next=currentNode.next;
    currentNode.next=newNode;
}
function display(){
    const currentNode=this.head;
    while(currentNode.next!==null){
        console.log(currentNode.next)
    }
}
function findNext(item) {
    const currentNode = this.find(item);
    return currentNode.next;
}
function remove(item) {
    const deleteNode = this.find(item);
    deleteNode.next = null;
    deleteNode.prev = null;
    const prevNode = this.findPrev(item);
    prevNode.next = nextNode;
}

双向链表

function Node(element) {
    this.element = element;
    this.next = null; // 前驱
    this.prev = null; // 后继
}
function multipleLinkedList() {
    this.head = new Node('head');
    this.find = find;
    this.display = display;
    this.insert = insert;
    this.remove = remove;
    this.findNext = findNext;
    this.findPrev = findPrev;
}
function find(item) {
    let currentNode = this.head;
    while (item !== currentNode.element) {
        currentNode = currentNode.next;
    }
    return currentNode;
}
function insert(element, item) {
    const newNode = new Node(element);
    let currentNode = this.find(item);
    newNode.next = currentNode.next;
    newNode.prev = currentNode;
    currentNode.next = newNode;
}
function findPrev(item) {
    const currentNode = this.find(item);
    return currentNode.prev;
}
function findNext(item) {
    const currentNode = this.find(item);
    return currentNode.next;
}
function remove(item) {
    const deleteNode = this.find(item);
    deleteNode.next = null;
    deleteNode.prev = null;
    const prevNode = this.findPrev(item);
    const nextNode = this.findNext(item);
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
}

字典

字典就是一种键值对形式的数据结构

// 可以使用Map、Object、Array模拟，这里我们使用Array模拟
function Dictionary(){
    this.dataSource=[];
    this.add=add;
    this.remove=remove;
    this.find=find;
    this.clear=clear;
    this.count=count;
}
function add(key,value){
    return this.dataSource[key]=value;
}
function remove(key){
    return delete this.dataSource[key]
}
function find(key){
    return this.dataSource[key]
}
function clear(){
    this.dataSource=[];
}
function count(){
    return this.dataSource.length
}

散列

• 散列的数据结构可以快速插入、删除和取用数据
• 散列的数据结构查找效率低下
• 数组的长度最好是一个质数，所有的策略都是基于碰撞
• 一般碰撞的解决方法有”开链法“和”线性探测法“
  • 开链法：两个键相同，保存的位置一样，开辟第二个数组
  • 线性探测法：如果键存在，则寻找下一个位置

function HashTable(){
    this.table=new Array(137); // 质数
    this.get=get;
    this.simpleHash=simpleHash;
    this.put=put;
}
function simpleHash(data){
    let total=0;
    for(let i=0;i<data.length;i++){
        total+=data.charCodeAt(i);
    }
    return total % this.table.length;
}
function put(data){
    let position=this.simpleHash(data);
    this.table[position]=data;
}
function get(key){
    return this.table[key]
}

二叉树

• 二叉树是一种非线性结构，分层存储
• 二叉树查找比较快，无重复节点，子节点不超过两个
• 节点对应的值称为键
• 左节点比父节点小，右节点比父节点大

function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}
function Bst() {
    this.insert = insert;
    this.remove = remove;
    this.getMax = getMax;
    this.geiMin = geiMin;
    this.find = find;
    this.root = null;
}
function insert(data) {
    let node = new Node(data, null, null);
    if (this.root === null) {
        this.root = node;
    } else {
        let current = this.root;
        while (current === null) {
            if (data < current.data) {
                if (current.left) {
                    current = current.left;
                } else {
                    current.left = node;
                }
            } else {
                if (current.right) {
                    return current = current.right;
                } else {
                    return current.right = node;
                }
            }
        }
    }
}
function getMin() {
    let current = this.root;
    while (!(current === null)) {
        current = current.left;
    }
    return current.data;
}
function getMax() {
    let current = this.root;
    while (!(current === null)) {
        current = current.right;
    }
    return current.data;
}
function find(data) {
    let current = this.root;
    while (current !== null) {
        if (data === current.data) {
            return current;
        } else if (data < current.data) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return null;
}
function remove(data) {
    let delNode = this.find(data);
    if (delNode.right !== null) {
        let leftNode = delNode.left;
        delNode = delNode.right;
        delNode.left = leftNode;
    } else {
        delete delNode;
    }
}

树的遍历，先序遍历、中序遍历、后序遍历都是对根节点而言,皆属于深度优先。只有层序遍历是广度优先，从根节点一层一层遍历

• 先序遍历，从 root 开始
  
• 中序遍历，先左后 root,再右
  
• 后续遍历，先左后右再 root
  
• 层序遍历，根据深度依次遍历