data-structures учебник
Начало работы с структурами данных

замечания

Введение в структуры данных

Структура данных - это способ организации и хранения информации.

Пусть «Привет, мир!» string - информация, которую нам нужно организовать и сохранить в байт-адресуемой памяти.

Для каждого символа ASCII требуется 7 бит памяти. Большинство систем резервируют 8 бит (1 байт) для каждого символа, поэтому каждый символ в «Привет, Мир!» хранится в единичной единичной единице памяти один за другим, последовательно.

Нам нужна единственная ссылка на нашу строку, хотя она охватывает несколько адресов памяти, поэтому мы используем адрес первого символа в строке «H». Доступ к любому другому символу можно получить по адресу «H» + индекс этого символа с использованием нуль-индексированных символов.

Мы хотим напечатать нашу строку «Hello, World!». Мы знаем его адрес в памяти, который мы предоставляем функции печати, но как известно функции печати, чтобы остановить печать последовательных мест памяти? Один общий подход - добавить нулевой символ «\ 0» в строку. Когда функция печати встречает нулевой символ, она знает, что она достигла конца строки.

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

Массив: простая структура данных

Структура данных массива используется для хранения похожих объектов (или значений данных) в непрерывном блоке памяти. Структура данных массива имеет фиксированный размер, который определяет количество значений данных, которые могут быть сохранены в нем.

Массив: путь C ++

В языке программирования C ++ мы можем объявить статический массив следующим образом

int arrayName[100];

Здесь мы объявили массив с именем «arrayName», который может хранить до 100 значений, все из которых имеют один и тот же тип, который является целым числом.

Теперь мы обсудим некоторые преимущества и недостатки этой структуры данных

1. Мы можем получить доступ к значениям данных, хранящимся в массиве в постоянном времени, то есть временной сложностью является O (1) . Поэтому, если мы хотим получить доступ к значению данных, хранящемуся на i-й позиции, нам не нужно начинать с начальной позиции и двигаться до i-й позиции, но мы можем сразу перейти в i-ю позицию, тем самым экономя вычислительное время.
2. Вставка элемента в середине массива не является эффективной задачей. Предположим, мы хотим добавить новый элемент в массив в i-й позиции, тогда нам нужно перенести весь элемент в (i-я) и (i + 1-я) позицию, чтобы создать пространство для нового элемента. Пример: 1 4 2 0 - массив с 4 элементами, теперь мы хотим вставить 3 на 2-ю позицию, тогда нам нужно переместить 4,2 и 0 на одну позицию, чтобы создать пространство для 3.

  1 3 4 2 0

3. Подобно вставке элемента, удаление элемента из i-й позиции в массиве также неэффективно, так как нам нужно переместить все элементы перед удаленным элементом на 1 блок, чтобы заполнить свободное пространство, созданное удаленным элемент.

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

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