数据结构的那些事(一)

482 阅读4分钟

前端早已不是当年的切图仔了。想要升职加薪,进军大厂,在前端的路上走的更远,你不得不了解一下数据结构。

常用的数据结构有:数组,列表,栈,队列,链表,字典,散列表,树,图。

我们会在接下来一个一个的介绍,并且实现它们!

1.数组:最常见也是用的最多的数据结构就是数组了。它通过索引来实现元素的任意存储。

大多数语言都有数组,值得一提的是,JavaScript中的数组是一种特殊的对象,因此索引在内部会被转换成字符串类型,所以效率会有所折扣。

因为数组大家了解的比较多,在这里只提下数组的迭代器方法:

不生成新数组的迭代器方法:

forEach():接收一个函数作为参数,对数组中每个元素使用该函数
every():接收一个返回值为布尔值的函数,遍历数组,对于所有函数返回true,该方法返回true
some():接收一个返回值为布尔值的函数,遍历数组,只要有一个函数返回true,该方法返回true
reduce():使用接收的函数操作数组,最后返回一个结果

生成新数组的迭代器方法

map()
filter()

2.列表:适用于保存元素不多,不需要在一个很长的序列中查找元素,或对其排序。

列表是一组有序的数据,每个列表中的数据项称为元素。 首先我们来设计一下这个列表应该具有哪些属性和方法:

function List() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = []; // 初始化一个空数组来保存列表元素
    this.clear = clear;
    this.find = find;
    this.toString = toString;
    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.currPos = currPos;
    this.moveTo = moveTo;
    this.getElement = getElement;
    this.length = length;
    this.contains = contains;
}

当我们设计好一个列表类后,接下来开始实现里面的方法:

//append
function append(e){
    this.dataStore[this.listSize++] = e;
}
//remove方法要求我们首先要找到删除的元素,我们需要一个辅助方法find()
function find(e){
    for(let i = 0; i<this.dataStore.length; ++i){
        if(this.dataStore[i] === e){
            return i
        }
    }
    return -1
}
function remove(e){
    let findCode = this.find(e);
    if(indCode > -1){
        this.dataStore.splice(findCode, 1);
        --this.listSize;
        return true;
    }
    return false;
}
//insert 向列表中插入一个元素
function insert(e, where){
    let insetPos = this.find(where);
    if(insertPos > -1){
        this.datastore.splice(insertPos+1, 0 , e);
        ++this.listSize;
        return true;
    }
    return false;
}
//length
function length(){
    return this.listSize;
}
//清空列表中的元素
function clear(){
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = this.pos = 0;
}
//cotains判断给定值是否在列表中
function coatains(e){
    for(let i = 0; i<this.dataStore.length; ++i ){
        if(this.dataStore[i] === e){
            return true;
        }
    }
    return false;
}

最后,我们还需要一组方法来遍历列表

function front() {
    this.pos = 0;
}
function end() {
    this.pos = this.listSize-1;
}
function prev() {
    if (this.pos > 0) {
        --this.pos;
    }
}
function next() {
    if (this.pos < this.listSize-1) {
        ++this.pos;
    }
}
function currPos() {
    return this.pos;
}
function moveTo(position) {
    this.pos = position;
}
function getElement() {
    return this.dataStore[this.pos];
}

到这里,我们就自己实现了一个列表类。有自己的属性,可以增删改查,可以遍历。

3.栈:栈是和列表类似的一种数据结构,但是它遵循后进先出的规则

因为数据只能在栈顶添加或删除,所以这样的操作很快,而且容易实现。 对栈的两种主要操作是将一个元素压入栈和讲一个元素弹出栈,另一个常用操作是访问栈顶元素。 一样的,在实现之前,我们先来设计一下栈应该具有的属性和方法:

function Stack() {
    this.dataStore = [];//存储
    this.top = 0;//栈顶
    this.push = push;//入栈操作
    this.pop = pop;//出栈操作
    this.peek = peek;//获取栈顶元素
}

接下来我们来实现这些方法:

function push(e){
    this.dataStore[this.top++] = e;
}

function pop(){
    return this.dataStore(--this.top);
}

function peek(){
    return this.dataStore[this.top - 1];
}

有时候需要知道栈内存储元素个数,可以定义一个length方法:

function length(){
    return this.top
}

清空栈也很简单:

function clear(){
    this.top = 0;
}
适合使用栈的场景:

(1)数制间的相互转换

eg:将数字转换为二进制和八进制
function changeBase(num, base){
    let s = new Stack();
    do{
        s.push(num % base);
        num = Math.floor(num /= base);
    }while(num > 0)
    let convert = "";
    while(s.length() > 0){
        convert += s.pop();
    }
    return convert;
}

(2)回文:回文指从前往后写和从后往前写都是一样的结构。使用栈可以轻松地判断一个字符串是否是回文。

字符串完整压入栈内后,通过持续弹出栈中的每个字母就可以得到一个新的字符串,该字符串刚好与原来的字符串顺序相反。我们只需要比较这连个字符串是否一样即可判断是不是回文。

(3)用栈来模拟递归

function fact(n){
    let s = new Stack();
    while(n > 1){
        s.push(n--);
    }
    let product = 1;
    while(s.length() > 0){
        product *= s.pop();
    }
    return product;
}

避免一篇博客过长,我会将数据结构分成几篇来写,喜欢的帮忙点个赞,给博主一点动力~~