Алгоритмы и структуры данных в JS — Список (List)

внешний интерфейс алгоритм JavaScript модульный тест

предисловие

У фронтенда редко есть возможность соприкоснуться с алгоритмами, и большинство из них работают интерактивно, поэтому многих фронтендеров будет придерживаться такая мысль: я фронтенд, зачем мне изучать структуры данных и алгоритмы? Я могу справиться с работой и без структур данных и алгоритмов.
На самом деле алгоритм - это широкое понятие. Любой код, который мы обычно пишем, может стать алгоритмом. Это точное и полное описание решения проблемы и четкая инструкция по решению ряда проблем. Он представляет собой использование систематических Методы описывают механизм стратегии решения проблемы.
С быстрым развитием Интернета фронтенд-инженеры уже не могут справиться с несколькими операциями селектора, ссылками и событиями.Все более и более сложные продукты и базовые библиотеки требуют надежных структур данных и алгоритмов для управления, поэтому я думаю, что фронтенд-инженеры следует также обратить внимание на алгоритмы и структуры данных, которые очень помогают в их карьерном росте.
Конечно, изучение алгоритмов — это не однодневная вещь, это процесс, который вы должны исследовать, практиковать и подводить итоги самостоятельно.Здесь я просто реализую некоторые общие алгоритмы и структуры данных в JavaScript, что играет роль привлечения других .

Список (Список)

Список — это обычная структура данных в компьютерах. В повседневной жизни списками могут стать списки покупок, список дел и т. д. Это набор упорядоченных данных, и элементы данных в каждом списке называютсяэлемент. В javascript элементы в списке могут иметь любой тип данных. Нет ограничений на количество элементов, которые могут быть сохранены в списке (при фактическом использовании он будет ограничен памятью программы).
В списке будут некоторые общие свойства или методы, такие как количество элементов в списке, текущая позиция в списке, добавление элемента в конец списка, удаление элемента из списка, очистка списка и ряд операций.
Затем мы абстрагируем определение типа данных списка и реализуем его с помощью массива в JS.

列表的数据类型定义
Определение типа данных списка

Класс списка

/*定义List类*/
 function List () {
    this.listSize = 0;   //初始化元素个数为0
    this.pos = 0;        //初始化位置为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.contains = contains; //判断给定值是否在列表中
}

Тогда давайте реализуем эти методы.

Сначала мы должны иметь возможность добавлять элементы, поэтому давайте сначала напишем метод добавления.

append: добавить элемент в список

//该方法给列表的最后一个位置添加一个新的元素，待插入成功后，更新列表中的元素个数

function append ( element ) {
    this.dataStore[this.listSize++] = element;
}

Итак, мы можем добавить элементы в список, а затем давайте посмотрим на метод find

найти: найти элемент в списке

//该方法通过循环查找给定元素是否在列表中，如果存在返回元素的位置，否则返回 -1

function find(element){
    for( var i = 0 ; i < this.dataStore.length ; i ++ ){
            if( this.dataStore[i] == element ){
                return i;
            }
        }
    return -1;
}

Элементы могут быть вставлены, затем их необходимо удалить, мы используем метод удаления для удаления элемента

удалить: удалить элемент из списка

//该方法通过使用find()方法返回元素的位置对 dataStore 数组进行截取，如果删除成功，返回 true , 并将 listSize 的值减1，更新列表长度，否则返回 false

function remove ( element ) {
    var foundAt = this.find(element);
    if( foundAt > -1 ){
        this.dataStore.splice( foundAt , 1 );
        --this.listSize;
        return true;
    }
    return false;
}

Когда я хочу узнать, сколько элементов в моем списке, мне нужно построить метод длины,

длина: возвращает общее количество элементов в списке

//该方法直接将 listSize 返回即可

function length(){
    return this.listSize;
}

Было бы неплохо, если бы я мог отображать свои элементы списка, это может быть там, давайте посмотрим на метод toString,

toString: отображает элементы списка

//该方法直接返回了列表数组，显示出当前列表内容

function toString(){
    return this.dataStore;
}

Теперь, когда в нашем списке есть несколько основных функций, давайте попробуем.

//构造列表对象
var fruits = new List();
//添加三个元素
fruits.append('Apple');
fruits.append('Grape');
fruits.append('Banana');

//打印列表
console.log( fruits.toString() )      // ["Apple", "Grape", "Banana"]
//查看列表长度
console.log( fruits.length() )        // 3
//查找 Banana 的位置
console.log( fruits.find('Banana') )  // 2
//删除 Grape 
fruits.remove('Grape');
console.log( fruits.toString() )      // ["Apple", "Banana"]

Если мы удаляем элемент Виноград, мы также хотим вернуть его в исходное положение, тогда нам нужно вызвать метод вставки

вставка: добавить элемент в позицию в списке

//该方法需要传入两个参数，第一个参数表示待插入的元素，第二个参数表示待插入元素的前一个元素，用于确定插入元素的位置，并调用 splice 方法更改列表数组，插入成功后更新 listSize 并返回 true ， 否则返回 false；
function insert( element , after ){
    var insertPos = this.find( after );
    if( insertPos > -1 ){
        this.dataStore.splice( insertPos + 1 , 0 , element );
        this.listSize ++;
        return true;
    }
    return false;
}

Теперь давайте поместим Виноград в исходное положение;

fruits.insert( 'Grape' , 'Apple' );
console.log( fruits.toString() )        // ["Apple", "Grape", "Banana"]

хорошо, теперь можно вставить Grape в исходное положение.

Если я съел все фрукты и теперь хочу очистить список, нам нужен четкий метод;

очистить: очистить список

//该方法使用 delete 操作符删除 dataStore 数组 ， 接着创建新的数组，并将其 listSize 和 pos 初始化设为 1 。

function clear(){
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = this.pos = 0;
}

Давайте попробуем.

fruits.clear();
console.log( fruits.toString() );      // []

Это сработало!

Выше мы видели, что в списке есть атрибут pos, указывающий на расположение текущего списка, далее мы будем что-то делать вокруг него, чтобы пользователи могли свободно манипулировать списком

спереди: переместить позицию списка на первую позицию

//该方法只要将 pos 置为 0 即可

function front(){
    this.pos = 0 ;
}

конец: переместить позицию списка в последнюю позицию

//同上，该方法只要将 pos 置为列表长度减 1 即可，因为数组下标从 0 开始嘛

function end(){
    this.pos = this.listSize - 1;
}

prev: переместить текущую позицию вперед на один

//只要将 pos 的位置减 1 即可，但要主要不能越界

function prev(){
    if( this.pos > 0 ){
        this.pos --;
    }else{
        console.log('您当前已在首位');
    }
}

следующий: переместить текущую позицию назад на одну позицию

//同理，只要将 pos 的位置加 1 即可，但要主要不能越界

function next(){
    if( this.pos < this.listSize - 1 ){
        ++this.pos;
    }else{
        console.log('您当前已在末尾');
    }
}

moveTo: переместить текущую позицию в указанную позицию

//直接改变 pos 的值即可，注意输入的合法性

function moveTo( position ){
    if( position < 0 || position > (this.listSize - 1) ){
        console.log('请输入正确的位置');
    }else{
        this.pos = position;
    }
}

Поскольку я могу изменить позицию своего списка по желанию, я должен знать, где находится моя текущая позиция, поэтому нам нужны два метода currPos и ​​getElement для возврата текущей позиции и элемента соответственно;

currPos: возвращает текущую позицию в списке

//只需将 pos 直接返回即可

function currPos(){
    return this.pos;
}

getElement: возвращает элемент в текущей позиции

//直接取对应的元素就好

function getElement(){
    return this.dataStore[this.pos];
}

Далее давайте проверим его: сначала ответ списка будет выглядеть до его опустошения, а затем мы добавим в него еще несколько элементов.

//再添加几个
fruits.append('Pear');
fruits.append('Orange');
fruits.append('Strawberry');
console.log( fruits.toString() );    // ["Apple", "Grape", "Banana", "Pear", "Orange", "Strawberry"]

//我们先看当前的位置和元素
console.log( fruits.currPos() );     // 0
console.log( fruits.getElement() );  // Apple

//我们尝试改变一下
fruits.moveTo( 2 );
fruits.next();
console.log( fruits.currPos() );     // 3
console.log( fruits.getElement() );  // Pear
fruits.end();
fruits.prev();
console.log( fruits.currPos() );     // 4
console.log( fruits.getElement() );  // Orange

Пока что мы в основном завершили все функции списка, и осталась последняя, ​​для определения есть ли данный элемент в списке, мы используем здесь метод contains

содержит: определяет, находится ли данное значение в списке

//我们直接利用利用 indexOf() 或者采用跟为高级的 ES6 中的 includes 方法来判断

//ES5
function contains( element ){
    if( this.dataStore.indexOf( element ) > -1 ) return true;
    else return false;
}

//ES6

function contains( element ){
    return this.dataStore.includes( element );
}

(ps: Студенты, не знакомые с ES6, также могут обратиться к другим сериям моих блогов.ES6 материал )

После написания теста,

console.log(fruits.contains('Banana'));         // true
console.log(fruits.contains('Watermelon'));     // false

Готово! Мы реализовали список с помощью javascript.Что касается того, как расширить его позже (например, создать круговой список), мы можем отклониться от нашего мышления, попрактиковаться в большей практической практике и пойти вместе!

Категории