Интерфейсные структуры данных и алгоритмы, которые вы должны знать

внешний интерфейс алгоритм программист

Когда дело доходит до структур данных и алгоритмов, я чувствую, что это должно быть знанием, которое нужно освоить серверной части, для фронтенда ему нужно только писать страницы, связывать события и отправлять данные на серверную часть. . Структуры данных и алгоритмы не нужны. Некоторый поиск данных можно выполнить с помощью простого цикла for, и он может быть улучшен только на несколько миллисекунд, но его можно игнорировать. Если предположить, что узел используется для фоновой разработки, Несколько миллисекунд, сэкономленных запросом, но не миллисекунды, сэкономленные десятками миллионов запросов, структура данных является обязательным знанием для старших программистов.

Добро пожаловать в гостисчастливый мусорщик, передовая платформа для сводки знаний и обмена ими, развивайтесь и развивайтесь вместе со всеми! 🙏🙏🙏

Сначала рассмотрим тип данных js.

  • Базовые типы (стек стека): Number, String, Boolean, Null и Undefined, Symbol (новое в es6); базовые типы данных распределяются по значению доступа от старшего к младшему, максимальная память стека 8 МБ, (превышает переполнение стека) , Строка: это специальная память стека (переменный размер, выделенный старше), которая выделяется программистом
  • Ссылочный тип (heap heap): Объект, Массив, Функция, Данные; данные ссылочного типа, хранящиеся в памяти стека, на самом деле являются ссылочным адресом (указателем) объекта в куче памяти, выделенным на высокий уровень, система автоматически выделяет
1. Различия в распределении пространства стека:
  • Стек (операционная система): автоматически выделяется и освобождается операционной системой для хранения значений параметров функций, значений локальных переменных и т. д. Его работа аналогична стеку в структуре данных;
  • Куча (операционная система): обычно выделяется и освобождается программистом. Если программист не освобождает ее, она может быть освобождена ОС в конце программы. Метод выделения аналогичен связанному списку.
Во-вторых, разница между режимом кэширования стека:
  • В стеке используется кеш первого уровня, они обычно находятся в памяти при вызове и освобождаются сразу после вызова;
  • Куча хранится в кеше второго уровня, а жизненный цикл определяется алгоритмом сборки мусора виртуальной машины (не один раз потерянный объект может быть переработан). Так что скорость вызова этих объектов относительно низкая.
В-третьих, разница между структурами данных кучи и стека:
  • Куча (структура данных): Куча может рассматриваться как дерево, например: сортировка кучи;
  • Стек (структура данных): структура данных по принципу «первым поступил — последним вышел».

структура данных

Структура данных относится к набору элементов данных, которые имеют одно или несколько отношений друг с другом и отношения между элементами данных в наборе; наиболее важным критерием для настройки основных операций структуры данных является реализация приложения программа и взаимосвязь между элементами данных Независимость от структуры хранения (структура данных = хранение данных + алгоритм)

Классификация структуры данных

  • Логическая структура: отражать логическую связь между данными;

  • Структура хранения: представление структур данных в компьютере;

Логическая структура:
   集合:结构中的数据元素除了同属于一种类型外，别无其它关系。(无逻辑关系)
   线性结构 :数据元素之间一对一的关系(线性表)
   树形结构 :数据元素之间一对多的关系(非线性)
   图状结构或网状结构: 结构中的数据元素之间存在多对多的关系(非线性)
Структура хранения:
  顺序存储数据结构
  链式存储数据结构
  索引存储数据结构
  散列存储数据结构

Линейная структура:

  • Очередь: также линейный список с ограниченной операцией. Он позволяет вставлять только на одном конце таблицы и удалять на другом. Конец, допускающий удаление, называется началом очереди, а конец, допускающий вставку, называется задним. Первым пришел-первым вышел.
  • Стек: это линейная таблица, которая ограничивает операции вставки и удаления на одном конце таблицы.Обычно конец вставки и удаления называется вершиной стека (Top), а другой конец — низом стека ( Нижний). Первый вышел последним. Когда top=-1, стек пуст.Top=0 может указывать только на то, что в стеке есть только один элемент, и значение top должно автоматически увеличиваться, когда элемент помещается в стек.
  • Строка: это конечная последовательность из нуля или более символов. Строка нулевой длины называется пустой строкой (Empty String), которая не содержит никаких символов. Обычно строка, состоящая только из одного или нескольких пробелов, называется пустой строкой (Blank String).Примечание: разница между пустой строкой и пустой строкой, например, " " и "" представляют пустую строку длиной 1 и пустая строка длины 0 соответственно string.

нелинейная структура

  • Дерево: нелинейная структура. Дерево является рекурсивной структурой, и понятие дерева используется в определении дерева.
  • Порядковый номер: между дочерними узлами существует отношение порядка
  • Неупорядоченное дерево: нет отношения порядка между дочерними узлами
  • Бинарное дерево: нелинейная структура. Дерево является рекурсивной структурой, и понятие дерева используется в определении дерева.
Обход бинарного дерева

Так что каждый узел посещается один и только один раз. Нерекурсивные реализации обхода используют стеки.

  • 先序遍历DLR：根节点->左子树->右子树(广度遍历)

  • 中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序(广度遍历)

  • 后续遍历LRD：左子树->右子树->根节点。需要栈的支持。(广度遍历)

  • 层次遍历：用一维数组存储二叉树时,总是以层次遍历的顺序存储结点。层次遍历应该借助队列。(深度遍历)

Память: очень длинный одномерный массив;

алгоритм

Особенности алгоритма:

Конечность, Детерминизм, Выполнимость, Вход, Выход

Меры дизайна алгоритма:

Корректность, Удобочитаемость, Надежность, Временная сложность, Пространственная сложность

Классификация алгоритмов

Основной алгоритм (должен быть)

Пузырьковая сортировка

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

быстрая сортировка

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

function partition(items, left, right) {
    var pivot = items[Math.floor((right + left) / 2)],
        i = left,
        j = right;
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right);
        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }
        if (index < right) {
            quickSort(items, index, right);
        }
    }
    return items;
}

var items = [3,8,7,2,9,4,10]
var result = quickSort(items, 0, items.length - 1);

Сортировка вставками

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

сортировка выбором

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

временная и пространственная сложность

  • В пузырьковой сортировке, сортировке вставками, сортировке выбором, быстрой сортировке в худшем случае временная сложность быстрой сортировки составляет O (n2), сортировка вставками O (n2), сортировка выбором O (n2), пузырьковая сортировка O (n2)

Добро пожаловать в гостисчастливый мусорщикУзнайте больше о передовых знаниях!

Категории