ЛК5

1. 5. Структуры данных

5. СТРУКТУРЫ ДАННЫХ
Массивы. Работа с массивами. Строки. Работа со строками.
Структуры данных различного типа. Основные возможности работы с динамической памятью. Примеры
вычислительных алгоритмов.
Задачи поиска и сортировки.

2. 5.1. Массивы. Строки

5.1. МАССИВЫ. СТРОКИ
Массив — упорядоченная структура данных, которая связывает значения и
ключи.
Массив (array) создают языковой конструкцией array(). В качестве аргументов она
принимает любое количество разделённых запятыми пар ключ => значение.
array(
key
=> value,
key2 => value2,
key3 => value3,
...
)

3.

PHP поддерживает короткий синтаксис массива, который заменяет языковую
конструкцию array() выражением [].
$array = [
"key1" => "value1",
"key2" => "value2",
"key3" => "value3"
];
Запятая после последнего элемента массива необязательна и её можно
опустить.
Ключ массива (key) разрешено указывать либо как целочисленное значение (int),
либо как строку (string). Значение массива (value) может принадлежать любому
типу данных.

4.

Дополнительно произойдут следующие преобразования ключа key:
Строки (string), содержащие целое число (int) (исключая случаи, когда перед
числом указывают знак +), будут преобразованы в целое число (int). Например,
ключ со значением «8» сохранится со значением 8. При этом, значение «08» не
преобразуется, так как оно — не корректное десятичное целое.
Числа с плавающей точкой (float) также преобразуются в целочисленные
значения (int) — дробная часть будет отброшена. Например, ключ со значением
8.6 будет сохранится со значением 8.
Логический тип (bool) также преобразовывается в целочисленный тип (int).
Например, ключ со значением true сохранится со значением 1, а ключ со
значением false сохранится со значением 0.
Тип null преобразуется в пустую строку. Например, ключ со значением null
сохранится со значением "".
Массивы (array) и объекты (object) нельзя указывать как ключи. Это
сгенерирует предупреждение: Недопустимый тип смещения (Illegal offset type).

5.

Пример. Смешанные целочисленные (int) и строковые (string) ключи:
Код
<?php
$array = array(
"one" => "two",
"two" => "one",
100
=> -100,
-100 => 100,
);
var_dump($array);
?>
Результат выполнения
array(4) {
["one"]=>
string(3) "two"
["two"]=>
string(3) "one"
[100]=>
int(-100)
[-100]=>
int(100)
}

6.

Пример. Индексные массивы без ключа:
Код
<?php
$array = array("one", "two",
"hallo", "world");
var_dump($array);
?>
Результат выполнения
array(4) {
[0]=>
string(3) "one"
[1]=>
string(3) "two"
[2]=>
string(5) "hallo"
[3]=>
string(5) "world"
}

7.

Доступ к элементам массива разрешено получать, используя синтакс array[key].
Пример. Доступ к элементам массива:
Код
Результат
выполнения
$array = array(
string(3) "two"
"one" => "two",
int(24)
42
=> 24,
string(3) "one"
"multi" => array(
"dimensional" => array(
"array" => "one"
)
)
);
var_dump($array["one"]);
var_dump($array[42]);
var_dump($array["multi"]["dimensional"]["array"]);

8.

Попытка получить доступ к неопределённому ключу массива аналогична
обращению к любой другой неопределённой переменной: будет выдано
сообщение об ошибке уровня E_WARNING (ошибки уровня E_NOTICE до PHP
8.0.0), а результатом будет значение null.
Пример. Создание и модификация с применением синтаксиса квадратных
скобок:
<?php
$arr = array(5 => 1, 12 => 2);
$arr[] = 56;
// В этом месте скрипта это
// то же самое, что и $arr[13] = 56;
$arr["x"] = 42; // Это добавляет в массив новый
// элемент с ключом «x»
unset($arr[5]); // Это удаляет элемент из массива
unset($arr);
// Это удаляет весь массив
?>

9.

Массивы разрешено деструктурировать языковыми конструкциями [] (начиная с
PHP 7.1.0) или list(). Эти языковые конструкции разрешено использовать для
деструктуризации массива на отдельные переменные:
<?php
$source_array = ['one', 'two', 'three'];
[$one, $two, $three] = $source_array;
echo $one;
// выведет «one»
echo $two;
// выведет «two»
echo $three; // выведет «three»
?>
* Деструктуризацию массива также выполняют в конструкции foreach для
деструктуризации многомерного массива во время итерации по массиву.

10.

Функции для работы с массивами :
array_fill — Заполняет массив значениями
array_find — Возвращает первый элемент, который удовлетворяет
callback-функции
array_flip — Меняет местами ключи с их значениями в массиве
array_key_exists — Проверяет, существует ли в массиве ключ / индекс
array_map — Применяет callback-функцию к элементам массивов
array_pad — Дополняет массив значением до заданной длины
array_pop — Извлекает последний элемент массива
array_product — Вычисляет произведение значений массива
array_push — Добавляет один или несколько элементов в конец массива
array_rand — Выбирает один или несколько случайных ключей из массива
array_shift — Извлекает первый элемент массива
array_slice — Выбирает срез массива
array_sum — Вычисляет сумму значений массива

11.

Строка (string) — набор символов, в котором символ — то же, что и байт.
В PHP часто встречаются задачи на парсинг строк.
При парсинге строка или текст разбиваются на компоненты. Затем полученные
данные преобразуются в формат, подходящий для обработки и использования.
По сути, один формат данных превращается в другой, более читаемый.
В PHP со строками (string) работают два оператора. Первый — оператор
конкатенации («.»), который возвращает строку, которая представляет
соединение левого и правого аргумента. Второй — оператор присваивания с
конкатенацией («.=»), который присоединяет правый аргумент к левому.

12.

PHP позволяет обращаться к отдельным символам строки как к элементам
массива по числовому индексу:
$str = "Hello Tom";
echo $str[0];
// получим первый символ - H
$str[1] = "i";
// поменяем второй символ
echo "<br>" . $str . "<br>";
// Hillo Tom
Индексация символов, как и в массиве, начинается с нуля.

13.

Функции для работы со строками:
echo — Выводит строки
ltrim — Удаляет пробельные или другие символы в начале строки
print — Выводит строку
printf — Выводит отформатированную строку
rtrim — Удаляет пробельные или другие символы в конце строки
setlocale — Устанавливает региональные настройки
str_contains — Определяет, содержит ли строка заданную подстроку
str_split — Преобразовывает строку в массив
strtolower — Приводит строку к нижнему регистру
wordwrap — Переносит строку через заданное количество символов
strlen — Возвращает длину строки, то есть количество символов в ней
parse_str — Разбирает строку в переменные
* для некоторых требуется подключить специальное расширение mbstring.dll.

14. 5.2. Структуры данных различного типа. Основные возможности работы с динамической памятью

5.2. СТРУКТУРЫ ДАННЫХ РАЗЛИЧНОГО ТИПА. ОСНОВНЫЕ
ВОЗМОЖНОСТИ РАБОТЫ С ДИНАМИЧЕСКОЙ ПАМЯТЬЮ
В рамках программирования структуры данных представляют собой
специальные контейнеры. Они хранят информацию в определённом формате,
который придает структуре те или иные свойства. Именно эти качества отличают
одну структуру данных от другой. Кроме того, они определяют ее пригодность
для тех или иных сценариев применения.
Со структурой можно взаимодействовать разными способами: добавлять данные,
извлекать их и обрабатывать (изменять, анализировать, сортировать и т.д.).
Структуры отличаются тем, что любую единицу данных можно найти в
определённом месте. Чтобы определить это место, необходимо знать нюансы
конкретной структуры.

15.

Типы структур данных по составу:
Простые. Они не делятся на составные части, которые больше, чем биты. Для
простого типа четко определен размер и способ размещения структуры в
памяти устройства.
Сложные (интегрированные). Они включают в себя другие структуры, которые,
в свою очередь, могут быть простыми или сложными.
В зависимости от уровня изменчивости выделяют:
статические;
полустатические;
динамические.
Речь идёт об изменении числа элементов или связей между ними.

16.

В зависимости от признака упорядоченности элементов различают два типа
структур организации данных:
Нелинейные: деревья, графы, многосвязные списки.
Линейные. В зависимости от типа распределения компонентов в памяти
устройства они могут иметь последовательное распределение (строки,
векторы, массивы, стеки, очереди) и произвольное связное распределение
(односвязные и двусвязные списки).
При указании типа данных определяются следующие параметры:
размер памяти, который необходимо для определенной структуры;
способ размещения структуры в памяти; *
значения, которые могут применяться для этого типа данных;
поддерживаемые операции.

17.

Основные типы структур данных:
Массив.
Одномерные — простейшие линейные структуры.
Многомерные — вложенные структуры, которые состоят из других массивов.
Динамический массив.
Размер обычного массива указывается заранее. Благодаря этому человек сразу
понимает, какое количество индексов в него входит. Динамический массив
отличается тем, что его размер не предопределён, он может меняться.
Связанный список
Представляет собой набор элементов (узлов) в линейной
последовательной структуре. Узел — это простой объект, имеющий 2
свойства: переменные для хранения данных и адреса памяти следующего
узла в списке.

18.

Стек.
Стек представляет собой линейную структуру данных, которая формируется на
базе массивов или связанных списков. Стек работает по принципу LIFO (от Last-InFirst-Out — «первым на вход — последним на выход»). Проще говоря, первым
элементом, который покинет стек, станет тот, который последний в него войдёт.
Название «stack» переводится как «стопка». Дело в том, что данная структура
может быть визуализирована как стопка книг, лежащих на столе.

19.

Очередь.
Очередь относится к линейному типу структуры данных так же, как и стек.
Формируется она на основе массивов или связанных списков. Работает по
принципу FIFO (First-In-First-Out — «первым на вход — первым на выход»). Иначе
говоря, первым покинувшим очередь элементом будет тот, который первый в неё
вошёл.
Множество.
Во множестве данные не упорядочены и хранятся группой. При этом их нельзя
структурировать, а иногда даже сортировать.

20.

Карта (Map).
Внутри карт данные хранятся в паре «ключ/значение». Поэтому такие структуры
называют ассоциативными массивами или словарями. При этом каждый ключ
уникален, в отличие от значений.
Двоичное дерево поиска.
Представляет собой структуру, данные которой размещаются
в узлах. При этом у каждого узла могут быть один или несколько
дочерних и лишь один родитель. Существует несколько
разновидностей таких структур.
Префиксное дерево (бор, нагруженное дерево).
Каждый узел представляет собой префикс, с помощью которого можно найти
следующие узлы.

21.

Граф (Graph).
Граф представляет собой структуру данных, состоящую из нескольких узлов
(вершин), связанных между собой. Пару (x,y) называют ребром. Таким образом,
вершина x соединена с вершиной y. Ребро может определять вес/стоимость
(стоимость прохождения по пути между двумя вершинами).
Графы представляют собой более общие случаи деревьев, которые, в свою
очередь, нередко называют ациклическими графами.
Можно выделить две особенности, которые отличают одну структуру от другой:
В графе могут быть циклы (когда «ребенок» является «родителем» для того же
объекта).
Ребра могут нести смысловую нагрузку (необходимо сохранять их значения).

22.

В PHP память для всех переменных выделяется динамически и незаметно для
программиста. Каждый раз, когда вы что-то записываете в переменную - вы
увеличиваете потребление памяти.
* И обычно программист только это и делает - говорит PHP: дай, дай, ещё дай. График
потребления памяти всё время рос бы вверх, пока не достиг memory_limit и PHP не выдал бы Fatal
error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 54 bytes). Рос бы, если бы в
язык не было встроено несколько механизмов высвобождения этой памяти. И каждый из них
запускается в строго определённые моменты работы:
При выходе локальной переменной из области видимости
При достижении счётчика ссылок на переменную нуля
При работе сборщика мусора
В основе всех механизмов высвобождения памяти лежит один и тот же принцип:
переменная будет удалена, когда счётчик ссылок на значение, которое она хранит
станет равным нулю.

23.

Стандартная библиотека PHP (SPL)
SPL предоставляет набор стандартных структур данных. Они сгруппированы
здесь по своей базовой реализации, которая обычно определяет их общую
область применения.
Двусвязные списки
Двусвязный список (DLL) - это список узлов, связанных в обоих направлениях
друг с другом. Операции итератора, доступ к обоим концам, добавление или
удаление узлов стоимостью O(1), когда основная структура является DLL.
Следовательно, они обеспечивает хорошую реализацию для стеков и очередей.
SplDoublyLinkedList
SplStack
SplQueue

24.

Кучи
Кучи - это древовидные структуры, которые следуют свойствам кучи: каждый
узел больше или равен своим потомкам, при этом для сравнения используется
внедрённый метод сравнения, который является общим для всей кучи.
SplHeap
SplMaxHeap, SplMinHeap
SplPriorityQueue
Массивы
Массивы – структуры, которые хранят данные в непрерывном виде, доступные
через индексы.
SplFixedArray

25.

Карта
Карта - это структура данных, содержащая пары ключ-значение. Массивы PHP
можно рассматривать как карты, отображающие целые/строковые данные в их
значения. SPL предоставляет карту, отображающую объекты к данным. Эта карта
также может быть использована как множество объектов.
SplObjectStorage

26. 5.3. Задачи поиска и сортировки

5.3. ЗАДАЧИ ПОИСКА И СОРТИРОВКИ
Пузырьковая сортировка public function sort(array $data) {
$count_elements = count($data);
$iterations = $count_elements - 1;
for ($i=0; $i < $count_elements; $i++) {
$changes = false;
for ($j=0; $j < $iterations; $j++) {
if ($data[$j] > $data[($j + 1)]) {
$changes = true;
list($data[$j], $data[($j + 1)]) =
array($data[($j + 1)], $data[$j]); }
}
$iterations--;
if (!$changes) {
return $data; }
}
return $data; }

27.

Бинарный поиск:

28.

Бинарный поиск: public function search(int $element, array $data) {
}
$begin = 0;
$end = count($data) - 1;
$prev_begin = $begin;
$prev_end = $end;
while (true) {
$position = round(($begin + $end) / 2);
if (isset($data[$position])) {
if ($data[$position] == $element) {
return $position; }
if ($data[$position] > $element) {
$end = floor(($begin + $end) / 2);
} elseif ($data[$position] < $element) {
$begin = ceil(($begin + $end) / 2); }
}
if ($prev_begin == $begin && $prev_end == $end) {
return false; }
$prev_begin = $begin;
$prev_end = $end;
}