Рубрики
Uncategorized

Основа реализации структуры данных

Автор оригинала: David Wong.

Вступление

статистика данных

Пример: при ежедневной обработке данных часто необходимо проводить базовый статистический анализ группы данных, включая следующие операции: среднее значение, максимум, минимум, медиана, стандартное отклонение, дисперсия и т.д. Такого рода статистика может встречаться в различных ситуациях, таких как статистика успеваемости учащихся, статистика расходов домашних хозяйств, статистика ВВП и т.д., Все из которых включают в себя статистику такого рода данных.

Это не очень хороший метод для написания программы для каждого конкретного приложения, и программа имеет большое сходство. Метод обработки структуры данных исходит из этих конкретных приложений Абстрактные общие методы организации и работы с данными А затем используют определенный язык программирования Реализуют соответствующее хранение и эксплуатацию данных

Абстракция данных

  • Имя типа: набор статистических данных
  • Набор объектов данных: n элементов {x 1 , x 2 , … , x N }Наборы
  • Набор операций:
  1. Тип элемента среднее значение (s, n): среднее значение N элементов в S
  2. Тип элемента max (s, n): найдите максимальное значение n элементов в S
  3. Тип элемента main (s, n): найдите минимальное значение n элементов в S
  4. Среда типа элемента (s, n): найдите медиану из n элементов в S

хранение данных

Основной режим хранения организации данных в основном реализуется массивом и связанным списком, включая очень сложную структуру данных, такую как график и дерево, которые также реализуются массивом и связанным списком

  • Если выполняемая операция является не базовой статистикой, а операцией набора, необходимо определить, принадлежат ли элементы набору, выполнить операцию объединения и пересечения на множестве, вставить элементы в набор и т.д. Хотя эти операции могут быть реализованы в простом массиве, но эффективность не высока. Используя древовидную организацию, можно легче реализовать описанные выше операции набора.
  • Если в дополнение к основным статистическим операциям вам необходимо динамически поддерживать коллекцию, то есть часто добавлять/удалять элементы в коллекцию, какого размера должен быть массив для сохранения этих элементов? Это слишком большая пустая трата пространства, слишком маленькая для использования. Возможно, для сохранения данных более целесообразно использовать связанный список, но у связанного списка также есть недостатки. Связанный список должен записывать адреса последующих узлов. По сравнению с хранилищем массива, связанному списку требуется больше места для хранения, а реализация программы сложнее, чем в массиве.

Реализация структуры данных для хранения тесно связана с требуемыми операциями, Нет лучшего способа хранения, только наиболее подходящий способ хранения 。

Осуществление операции

  • После определения режима хранения данных другая проблема, связанная со структурой данных, заключается в том, как реализовать связанные операции. Реализация этих операций требует использования другой функции, предоставляемой языком программирования, а именно Функции проектирования процесса 。
  • В любом языке программирования высокого уровня предусмотрена базовая инструкция управления потоком, то есть инструкция управления ветвями и инструкция управления циклом. Структура управления ветвями, структура управления циклом и структура выполнения последовательности естественных операторов программы являются базовой структурой для реализации любого потока алгоритмов.
  • В программе мы можем спроектировать базовую функцию программы как функцию, которая, с одной стороны, снижает сложность разработки программы, а с другой стороны, улучшает возможность повторного использования разработки программы. Рекурсия-очень важный метод разработки алгоритма структуры данных.

Вопросы и ответы на PHP-интервью https://github.com/collinlet/php-интервью-добро пожаловать, начните следовать~~ В сочетании с фактическим интервью на PHP, обобщите свои собственные проблемы и проблемы, с которыми сталкиваются другие пользователи в Интернете, и постарайтесь дать краткие и точные ответы, включая сеть, структуру и алгоритм данных, PHP, веб, mysql, redis, Linux, безопасность, режим проектирования, архитектуру, интервью и т. Д

Основа для хранения структуры данных

Переменная является основной единицей хранения данных, в то время как переменная имеет тип, такой как целое число, с плавающей запятой, символ, логическое значение

массив

Массив-это самый базовый тип построения, представляющий собой упорядоченный набор данных одного и того же типа

Указатель

Переменная указателя используется для хранения адреса переменной, к которой можно получить косвенный доступ с помощью указателя

структурная морфология

Тип структуры-это тип данных, который позволяет агрегировать некоторые компоненты данных в единое целое. Он может объединить различные типы данных с внутренними отношениями в единое целое, чтобы они могли быть связаны друг с другом. В то же время структура представляет собой набор переменных, и ее переменные элементы могут использоваться отдельно в соответствии с тем же методом работы, что и переменные типа элементов. Разница между структурой и массивом заключается в том, что все элементы массива должны быть одного типа, в то время как элементы структуры могут быть разных типов данных.

Struct structure name{
    Type name structure member name 1;
    Type name structure member name 2;
    ......
    Type name structure member name n;
};

Связанный список

Связанный список-это общая и важная базовая структура данных, а также важное средство реализации сложной структуры данных. Он не хранит данные в линейном порядке, а состоит из нескольких “узлов” одного и того же типа структуры, то есть каждый узел хранит адрес следующего узла. Использование структуры связанного списка может преодолеть недостатки данных, которые требуют предварительного знания размера данных, полного использования пространства компьютерной памяти и реализации гибкого динамического управления памятью. Однако связанный список теряет преимущество удобного случайного хранения массива, а накладные расходы на пространство связанного списка относительно велики из-за увеличения поля указателя узла.

Односторонний связанный список

Структура однонаправленного связанного списка

//One way list node
class node
{
    public $data;
    public $next;

    /**
     *@ param $P1 node data
     *@ param $P2 next node
     */
    public function __construct($p1, $p2)
    {
        $this->data = $p1;
        $this->next = $p2;
    }
}

Обычная работа с односторонним связанным списком

  • Создание связанного списка

При программировании со связанным списком часто бывает необходимо сначала создать связанный список. Процесс создания связанного списка на самом деле представляет собой процесс непрерывной вставки узлов в связанный список

class singleLinkList
{
    /**
     *@ param $n int number of nodes
     *@ return $head obj header node
     */
    public function create($n)
    {
        $head = new node(0, null);
        for ($i=$n; $i > 0; $i--) { 
            $newNode = new node($i, null);
            $newNode->next = $head->next;
            $head->next = $newNode;
        }
        return $head;
    }
}
  • Вставной Узел

Вставьте новый узел после узла P в заголовке одностороннего связанного списка: найдите правильную позицию P, подайте заявку на новый узел T и назначьте значение информации об узле T и, наконец, вставьте после p

  • Удалить Вершину

Удалите узел из заголовка одностороннего связанного списка: найдите узел P перед удаленным узлом и удалите узел после p

  • Обход однонаправленного связанного списка

Наиболее распространенным способом работы с однонаправленным связанным списком является проверка и обработка данных каждого узла в связанном списке по одному

Двусторонний связанный список

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

//Double linked list node
class node
{
    public $data;
    public $next;
    public $previous;

    /**
     *@ param $P1 node data
     *@ param $P2 next node
     *@ param $P3 previous node
     */
    public function __construct($p1, $p2, $p3)
    {
        $this->data = $p1;
        $this->next = $p2;
        $this->previous = $p3;
    }
}

Двусторонний круговой список

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

Основа управления технологическим процессом

В дополнение к выражению всех видов данных, язык программирования должен обеспечивать средство для выражения процесса обработки данных, а именно Процесс управления процедурой . Процесс управления программой реализуется серией операторов в программе.

Согласно точке зрения структурированного программирования, любая программа может реализовать программный модуль, объединив три основные структуры управления. Тремя основными структурами управления являются порядок 、 ветвь 、 цикл 。

Исходная ссылка основы реализации структуры данных: https://blog.maplemark.cn/2019/07/data реализация структуры foundation.html