Структуры данных. Двунаправленный список.

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Назначение структур: повышении эффективности и производительности программ. Структуры относятся к типам значений, и поэтому ими можно оперировать непосредственно, а не по ссылке. Следовательно, для работы со структурой вообще не требуется переменная ссылочного типа, а это означает в ряде случаев существенную экономию оперативной памяти.

Список – это последовательность элементов a1, а2,…,аn (n больше 0) одного типа. Количество элементов n называется длиной списка. Если n = 0, то это пустой список. Элементы списка линейно упорядочены в соответствии с их позицией в списке.

Если каждый элемент списка содержит две ссылки (одну на следующий элемент в списке, а вторую на предыдущий), то такой список называется

двунаправленным.

Двунаправленный список

Prev

Data

Next

Prev

Data

Next

class ListItem<T>

{

public ListItem<T> Previous {get; set}

public T Data {get; set;}

public ListItem<T> Next {get; set;}

}

private ListItem<T> first; (current, last)

Операции

Проверка на пустоту, добавление в начало или конец,

Добавление в начало списка

current = new ListItem<T>();

current.Data = value;

current.Next = first;

first Previous = current;

first = current;

Структуры данных. Хеш-таблица.

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Назначение структур: повышении эффективности и производительности программ. Структуры относятся к типам значений, и поэтому ими можно оперировать непосредственно, а не по ссылке. Следовательно, для работы со структурой вообще не требуется переменная ссылочного типа, а это означает в ряде случаев существенную экономию оперативной памяти.

Плюсы: произвольный доступ, добавление и удаление элементов

Минусы: память, последовательный доступ

Хеширование (хэш-функция)

Преобразование входного набора данных, произвольных данных в выходные значения, фиксированные длины.

Хеш, хэш-код – результат хеширования.

Использование:

• Проверка целостности данных (контрольные суммы)
• Проверка паролей
• Быстрый поиск данных по ключу
• Базы данных
• Ассоциативные массивы

Контрольные суммы

22 15

15 22

Приемник

Магнитная буря

Скачок напряжения

Среда передачи