Чем стек отличается от структуры данных линейный список

Основные структуры данных. Матчасть. Азы

Все чаще замечаю, что современным самоучкам очень не хватает матчасти. Все знают языки, но мало основы, такие как типы данных или алгоритмы. Немного про типы данных.

Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.

40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.

В статье так же будут вопросы, которое вы можете услышать на интервью.

Что такое структура данных?

Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.

Какие бывают?

Линейные, элементы образуют последовательность или линейный список, обход узлов линеен. Примеры: Массивы. Связанный список, стеки и очереди.

Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.

Основные структуры данных.

1. Массивы
2. Стеки
3. Очереди
4. Связанные списки
5. Графы
6. Деревья
7. Префиксные деревья
8. Хэш таблицы

Массивы

Массив — это самая простая и широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.

Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

Каждому элементу данных присваивается положительное числовое значение (индекс), который соответствует позиции элемента в массиве. Большинство языков определяют начальный индекс массива как 0.

Бывают

Одномерные, как показано выше.
Многомерные, массивы внутри массивов.

Основные операции

• Insert-вставляет элемент по заданному индексу
• Get-возвращает элемент по заданному индексу
• Delete-удаление элемента по заданному индексу
• Size-получить общее количество элементов в массиве

Вопросы

• Найти второй минимальный элемент массива
• Первые неповторяющиеся целые числа в массиве
• Объединить два отсортированных массива
• Изменение порядка положительных и отрицательных значений в массиве

Стеки

Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Это не массивы. Это очередь. Придумал Алан Тюринг.

Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.

Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.

Основные операции

• Push-вставляет элемент сверху
• Pop-возвращает верхний элемент после удаления из стека
• isEmpty-возвращает true, если стек пуст
• Top-возвращает верхний элемент без удаления из стека

Вопросы

• Реализовать очередь с помощью стека
• Сортировка значений в стеке
• Реализация двух стеков в массиве
• Реверс строки с помощью стека

Очереди

Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.

Пример очереди – очередь людей. Последний занял последним и будешь, а первый первым ее и покинет.

Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым

Основные операции

• Enqueue—) — вставляет элемент в конец очереди
• Dequeue () — удаляет элемент из начала очереди
• isEmpty () — возвращает значение true, если очередь пуста
• Top () — возвращает первый элемент очереди

Вопросы

• Реализовать cтек с помощью очереди
• Реверс первых N элементов очереди
• Генерация двоичных чисел от 1 до N с помощью очереди

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

Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.

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

Бывают

Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.

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

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

Самое частое, линейный однонаправленный список. Пример – файловая система.

Основные операции

• InsertAtEnd — Вставка заданного элемента в конец списка
• InsertAtHead — Вставка элемента в начало списка
• Delete — удаляет заданный элемент из списка
• DeleteAtHead — удаляет первый элемент списка
• Search — возвращает заданный элемент из списка
• isEmpty — возвращает True, если связанный список пуст

Вопросы

• Реверс связанного списка
• Определение цикла в связанном списке
• Возврат N элемента из конца в связанном списке
• Удаление дубликатов из связанного списка

Графы

Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).

Бывают

Ориентированный, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
Смешанные

Встречаются в таких формах как

• Матрица смежности
• Список смежности

Общие алгоритмы обхода графа

• Поиск в ширину – обход по уровням
• Поиск в глубину – обход по вершинам

Вопросы

• Реализовать поиск по ширине и глубине
• Проверить является ли граф деревом или нет
• Посчитать количество ребер в графе
• Найти кратчайший путь между двумя вершинами

Деревья

Дерево-это иерархическая структура данных, состоящая из узлов (вершин) и ребер (дуг). Деревья по сути связанные графы без циклов.

Древовидные структуры везде и всюду. Дерево скилов в играх знают все.

• N дерево
• Сбалансированное дерево
• Бинарное дерево
• Дерево Бинарного Поиска
• AVL дерево
• 2-3-4 деревья

«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs

Три способа обхода дерева

• В прямом порядке (сверху вниз) — префиксная форма.
• В симметричном порядке (слева направо) — инфиксная форма.
• В обратном порядке (снизу вверх) — постфиксная форма.

Вопросы

• Найти высоту бинарного дерева
• Найти N наименьший элемент в двоичном дереве поиска
• Найти узлы на расстоянии N от корня
• Найти предков N узла в двоичном дереве

Trie ( префиксное деревое )

Разновидность дерева для строк, быстрый поиск. Словари. Т9.

Вот как такое дерево хранит слова «top», «thus» и «their».

Слова хранятся сверху вниз, зеленые цветные узлы «p», «s» и «r» указывают на конец «top», «thus « и «their» соответственно.

Вопросы

• Подсчитать общее количество слов
• Вывести все слова
• Сортировка элементов массива с префиксного дерева
• Создание словаря T9

Хэш таблицы

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

Объект хранится в виде пары «ключ-значение», а коллекция таких элементов называется «словарем». Каждый объект можно найти с помощью этого ключа.

По сути это массив, в котором ключ представлен в виде хеш-функции.

Эффективность хеширования зависит от

• Функции хеширования
• Размера хэш-таблицы
• Метода борьбы с коллизиями

Пример сопоставления хеша в массиве. Индекс этого массива вычисляется через хэш-функцию.

Вопросы

• Найти симметричные пары в массиве
• Найти, если массив является подмножеством другого массива
• Описать открытое хеширование

Список ресурсов

• medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
• www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1
• prog-cpp.ru/data-list
• habr.com/post/267855
• habr.com/post/273687
• habr.com/post/150732
• ruhighload.com/%D0%A7%D1%82%D0%BE+%D1%82%D0%B0%D0%BA%D0%BE%D0%B5+%D1%85%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B+%D0%B8+%D0%BA%D0%B0%D0%BA+%D0%BE%D0%BD%D0%B8+%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%B0%D1%8E%D1%82
• ru.wikipedia.org

Вместо заключения

Матчасть так же интересна, как и сами языки. Возможно, кто-то увидит знакомые ему базовые структуры и заинтересуется.

Спасибо, что прочли. Надеюсь не зря потратили время =)

PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.

• Программирование
• Алгоритмы

Информатика. 10 класс (Повышенный уровень)

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

Различные виды структур данных подходят для различных задач; некоторые из них имеют узкую специализацию, другие являются универсальными (пример 21.1).

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

Ни одна профессиональная программа сегодня не пишется без использования структур данных, поэтому многие из них содержатся в стандартных библиотеках современных языков программирования (например, STL для С++).

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

Структуры данных классифицируют по разным признакам. В примере 21.2 приведена классификация структур данных по организации взаимосвязей между элементами.

Пример 21.1. Примеры некоторых структур данных:

1. Массив (вектор в C++) — самая простая и широко используемая структура данных.

2. Запись (структура в С++) — совокупность элементов данных разного типа. Содержит постоянное количество элементов, которые называют полями.

3. Связный список (Linked List) представляет набор связанных узлов, каждый из которых хранит собственно данные и ссылку на следующий узел. В реальной жизни связный список можно представить в виде поезда, каждый вагон которого может содержать некоторый груз или пассажиров и при этом может быть связан с другим вагоном.

4. Граф — совокупность вершин (узлов) и связей между ними (ребер). В реальной жизни по такому принципу устроены социальные сети: узлы — это люди, а ребра — их отношения.

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

Пример 21.2. Классификация структур данных.

• • массив;
  • список;
  • связанный список;
  • стек;
  • очередь;
  • хэш-таблица.

  • Иерархические:

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

        Самые популярные структуры данных

        Что такое структура данных?
        Проще говоря, структура данных — это контейнер, в котором хранятся данные в определенной компоновке (формате, или способе организации их в памяти). Эта «компоновка» позволяет структуре данных быть эффективной в одних операциях и неэффективной в других. Ваша цель — понять структуры данных, чтобы вы могли выбрать структуру данных, наиболее оптимальную для рассматриваемой проблемы.

        Зачем нам нужны структуры данных?
        Поскольку структуры данных используются для хранения данных в организованном виде, и поскольку данные являются наиболее важным элементом компьютерной науки, истинная ценность структур данных очевидна.
        Независимо от того, какую проблему вы решаете, вам так или иначе приходится иметь дело с данными — будь то зарплата сотрудника, цены на акции, список покупок или даже простой телефонный справочник.
        Исходя из разных сценариев, данные должны храниться в определенном формате. У нас есть несколько структур данных, которые покрывают потребность хранить данные в разных форматах.

        • Arrays — массивы
        • Stacks — стеки
        • Queues — очереди
        • Linked Lists — связанные списки
        • Trees — деревья
        • Graphs — графы
        • Tries (они, по сути, деревья, но все же хорошо называть их отдельно). — очередности
        • Hash Tables — хэш таблицы

        Arrays — Массивы
        Массив — это самая простая и наиболее широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.
        Вот изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

        

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

        • Одномерные массивы (как показано выше) One-dimensional arrays
        • Многомерные массивы (массивы внутри массивов) Multi-dimensional arrays

        Основные операции над массивами
        Вставить (Insert) — вставляет элемент по указанному индексу
        Получить (Get) — возвращает элемент по указанному индексу
        Удалить (Delete) — удаляет элемент по указанному индексу
        Размер (Size) — получить общее количество элементов в массиве

        Для самостоятельного изучения:
        1. Найти второй минимальный элемент массива.
        2. Первые неповторяющиеся целые числа в массиве.
        3. Объединить два отсортированных массива.
        4. Переставить положительные и отрицательные значения в массиве.

        Stacks (Стеки)
        Мы все знакомы со знаменитой опцией Undo (Отмена), которая присутствует практически в каждом приложении. Когда-нибудь задумывались, как это работает? Суть механизма в том, что вы сохраняете предыдущие состояния вашей работы (которые ограничены определенным числом) в памяти в таком порядке, что последнее действие появляется первым. Это не может быть сделано только с помощью массивов. Вот где стек и пригодится!

        Реальным примером стека может быть стопка книг, расположенных в вертикальном порядке. Чтобы получить книгу, которая находится где-то посередине, вам нужно удалить все книги, помещенные поверх нее. Вот как работает метод LIFO (Last In First Out).
        Вот изображение стека, содержащего три элемента данных (1, 2 и 3), где 3 вверху и будет удалено первым:

        

        Основные операции со стеками:
        Протолкнуть (Push) — вставляет элемент сверху других.
        Вытащить (Pop) — возвращает верхний элемент после удаления из стека.
        Пустой? (IsEmpty) — возвращает истина (true), если стек пуст.
        Верхний (Top) — возвращает верхний элемент без удаления из стека.

        Для самостоятельного изучения:
        1. Оцените постфиксное выражение, используя стек.
        2. Сортировка значений в стеке.
        3. Проверьте сбалансированные скобки в выражении.

        Queues (Очереди)
        Подобно стеку, очередь — это еще одна линейная структура данных, в которой элементы хранятся последовательно. Единственное существенное различие между стеком и очередью состоит в том, что вместо использования метода LIFO в Queue реализован метод FIFO, который является сокращением от First in First Out.
        Прекрасный реальный пример очереди: ряд людей, ожидающих у билетной кассы. Если приходит новый человек, он присоединяется к линии с конца, а не с начала — и человек, стоящий впереди, первым получит билет и, следовательно, покинет линию.
        Вот изображение очереди, содержащей четыре элемента данных (1, 2, 3 и 4), где 1 находится вверху и будет удалено первым:

        

        Основные операции с очередью:
        Вочередить (Enqueue) — вставляет элемент в конец очереди.
        Выочередить (Dequeue) — удаляет элемент из начала очереди.
        Пустой? (IsEmpty) — возвращает истина (true), если очередь пуста.
        Верхний (Top) — возвращает первый элемент очереди.

        Для самостоятельного изучения:
        1. Реализация стека с использованием очереди.
        2. Обратные первые k элементы очереди.
        3. Генерация двоичных чисел от 1 до n с использованием очереди.

        Связанный список (Linked List)
        Связанный список — это еще одна важная линейная структура данных, которая на первый взгляд может выглядеть аналогично массивам, но отличается распределением памяти, внутренней структурой и тем, как выполняются основные операции вставки и удаления.

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

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

        Вот визуальное представление внутренней структуры связанного списка:

        

        • Односвязный список (однонаправленный)
        • Двусвязный список (двунаправленный)

        Основные операции над связанным списком
        ВставитьВКонец (InsertAtEnd) — вставляет элемент в конец связанного списка.
        ВставитьВНачало (InsertAtHead) — вставляет элемент в начало связанного списка.
        Удалить (Delete) — удаляет данный элемент из связанного списка.
        УдалитьВНачале (DeleteAtHead) — удаляет первый элемент связанного списка.
        Search (Поиск) — возвращает найденный элемент из связанного списка.
        Пустой? (IsEmpty) — возвращает истина (true), если связанный список пуст.

        Для самостоятельного изучения:
        1. Перевернуть связанный список (Обратить, реверсировать, отобразить задом наперёд).
        2. Определить цикл в связанном списке.
        3. Вернуть N-й узел с конца в связанном списке.
        4. Удалить дубликаты из связанного списка.

        Graphs (Графы)
        Графы — это набор узлов, которые связаны друг с другом в форме сети. Узлы также называются вершинами. Пара (x, y) называется ребром, что указывает на то, что вершина x связана с вершиной y. Ребро может содержать вес / стоимость, показывая, сколько затрат требуется для перехода от вершины x к y.

        

        • Undirected Graph
        • Directed Graph
        • Смежная (соседняя) матрица (Adjacency Matrix)
        • Смежный (соседний) список Adjacency List

        Ниже приведен пример смежного списка Adjacency List (ненаправленный граф).

        

        • Breadth First Search
        • Depth First Search

        Для самостоятельного изучения:
        1. Реализация Breadth and Depth First поиска
        2. Проверка если граф дерево или нет.
        3. Подсчет количества ребер в графе.
        4. Найти кратчайший путь между вершинами.

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

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

        Вот изображение простого дерева и основные термины, используемые в древовидной структуре данных:

        

        Имеются типы деревьев:

        • N-ое дерево
        • Сбалансированное дерево (Balanced Tree)
        • Бинарное дерево (Binary Tree)
        • Бинарное поисковое дерево (Binary Search Tree)
        • AVL дерево
        • Красно-черное дерево (Red Black Tree)
        • 2–3 дерево

        Из вышеперечисленного Бинарное дерево и Бинарное поисковое дерево являются наиболее часто используемыми деревьями.

        Для самостоятельного изучения:
        1. Найти высоту бинарного дерева.
        2. Найти k-е максимальное значение в двоичном поисковом дереве.
        3. Найти узлы на расстоянии «k» от корня.
        4. Найти предков данного узла в двоичном дереве.

        1. Facebook: Каждый пользователь представляет собой вершину, и два человека являются друзьями, когда имеется ребро между двумя вершинами. Так же и рекомендации в друзья — расчитываются на основаниитеории графов.

        2. Карты Google: Различные локации представлены вершинами и дороги представлены ребрами, теория графов используется для нахождения кратчайшего пути между двумя вершинами.

        3. Транспортные сети: в них вершины это пересечения дорог и рёбра — это дорожные сегменты между их пересечениями.

        4. Представление молекулярных структур где вершины это молекулы и рёбра — это связи между молекулами.

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

        7. Теория расширение кластера Майера функции летучести газа (Z) в термодинамике требует вычисления двух, трех, четырёх условий и так далее. Существует систематический способ сделать это комбинаторно с диаграммами, и это помогает узнать связность таких диаграмм. Знание теории графов может быть полезным, когда вы хотите суммировать подмножество этих диаграмм.

        8. Раскраска карты: знаменитая теорема о четырех цветах утверждает, что всегда можно правильно раскрасить регионы карты так, чтобы никаким двум смежным регионам не был назначен один и тот же цвет, используя не более четырех разных цветов. В этой модели регионы с цветами — это узлы, а смежность — ребра графа.

        9. Задача с тремя коттеджами — это хорошо известная математическая головоломка. Ее можно сформулировать так: Три коттеджа на плоскости (или сфере), каждый из которых должен быть подключен к газовым, водопроводным и электрическим компаниям. Задача решается при помощи графа на плоскости.

        10. Поиск центра графа: Для каждой вершины найдите длину кратчайшего пути к самой дальней вершине. Центром графа является вершина, для которой это значение минимально. Это важно для архитектурного планирования населенных пунктов, в которых больница, пожарная служба или отделение полиции должны быть расположены в так, чтобы самая дальняя точка была как можно ближе.

        Для любителей С#, как я, линк с примерами кода построения графов на C# тут. Для самых продвинутых библиотека с реализацией графов на C++ тут. Для фанатов AI и Skynet топать сюда.

        Очередности (Trie)
        Очередности, также известные как деревья с префиксами (Prefix Trees), представляют собой древовидную структуру данных, которая оказывается достаточно эффективной для решения проблем, связанных со строками. Они обеспечивают быстрый поиск и, в основном, используются для поиска слов в словаре, автоматического предложения в поисковой системе и даже для IP-маршрутизации.

        Вот иллюстрация того, как три слова «top», «thus», и «their» хранятся в Очередности:

        

        Слова хранятся сверху вниз, где зеленые узлы “p”, “s” и “r” указывают на конец “top”, “thus”, и “their” соответственно.

        Для самостоятельного изучения:
        1. Подсчитать общее количество слов в Очередности.
        2. Распечатать все слова, хранящиеся в Очередности.
        3. Сортировка элементов массива с использованием Очередности.
        4. Формируйте слова из словаря, используя Очередности.
        5. Создайте словарь T9.

        Практические примеры использования:
        1. Выбор из словаря или завершение при наборе слова.
        2. Поиск в контактах в телефоне или телефонном словаре.

        Hash Table (Хеш-таблица)
        Хеширование — это процесс, используемый для уникальной идентификации объектов и сохранения каждого объекта по некоторому предварительно рассчитанному уникальному индексу, называемому его «ключом». Таким образом, объект хранится в форме пары «ключ-значение», а коллекция таких элементов называется «словарь». Каждый объект может быть найден с помощью этого ключа.

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

        Хеш-таблицы обычно реализуются с использованием массивов.

        • Хэш-функция
        • Размер хеш-таблицы
        • Метод обработки столкновений

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

        

        Для самостоятельного изучения:
        1. Найти симметричные пары в массиве.
        2. Проследить полный путь путешествия.
        3. Найти, если массив является подмножеством другого массива.
        4. Проверьте, являются ли данные массивы непересекающимися.

        Ниже приведен пример кода использования хэш-таблицы в .Net

        static void Main(string[] args) < Hashtable ht = new Hashtable < < "001", "Zara Ali" >, < "002", "Abida Rehman" >, < "003", "Joe Holzner" >, < "004", "Mausam Benazir Nur" >, < "005", "M. Amlan" >, < "006", "M. Arif" >, < "007", "Ritesh Saikia" >>; if (ht.ContainsValue("Nuha Ali")) < Console.WriteLine("Эта персона уже в списке!"); >else < ht.Add("008", "Nuha Ali"); >// Получить коллекцию ключей. ICollection key = ht.Keys; foreach (string k in key) < Console.WriteLine(k + ": " + ht[k]); >Console.ReadKey(); > 

        1. Игра «Жизнь». В ней хэш — это набор координат каждой живой клетки.

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

        3. При имплементации структуры/алгоритма многонаправленного дерева (multiway tree) хэштаблицы могут использоваться для быстрого доступа к любому дочернему элементу внутреннего узла.

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

        5. Любой язык программирования нуждается в картировании имени переменной ее адресу в памяти. Фактически, в скриптовых языках как Javascript и Perl, поля могут быть добавлены в объекту динамически, это означает, что объекты сами по себе как хэш-карты.

        • Программирование
        • Анализ и проектирование систем
        • Хранение данных

        Теоретический материал: стеки, очереди, кольца (Паскаль)

        Стек. Отличия стека от списка. Основные операции со стеком

        Сейчас Вы познакомитесь с одной из разновидностей обычного линейного списка – стеком. Этот вид списка очень часто используется в программировании.

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

        Стек часто называют структурой LIFO (сокращение LIFO означает Last In – First Out, т.е. последним пришел – первым вышел). Это сокращение помогает запомнить механизм работы стека.

        Изобразим стек графически:

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

        Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.

        Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.

        Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.

        Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, «нижний» элемент.

        Таким образом, описать стек можно следующим образом:

        Если стек пуст, то значение указателя равно Nil.

        Рассмотрим возможные операции со стеком.

        Занесение элемента в стек

        Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.

        Процедура формирования стека будет иметь следующий вид:

        Procedure FormStack; Var Stack : EXST; Digit : integer; Procedure writeStack(Var u : EXST; Digit : integer); Var x : EXST; Begin new(x); x^.Data := Digit; x^.Next := u; u := x; End; Begin Stack := Nil; writeln(‘Введите элементы стека. Окончание ввода – 0’); read(Digit); while Digit <> 0 do begin writeStack(Stack, Digit); read(Digit); end; End;

        Извлечение элемента из стека

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

        Procedure readStack(Var u : EXST; Var i : integer); Var x : EXST; Begin i := u^.Data; x := u; u := u^.Next; dispose(x); End.

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

        Function FreeStack(u : EXST) : boolean;

        Задание. Описать функцию и закончить программу, для чего описать процедуру вывода значений элементов стека на экран (она аналогична выводу списка). Протестировать программу, дополнить комментарием.

        Примеры решения задач

        Пример 1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

        Program MordovskihK; Type EXST = ^ST; ST = record Data : char; Next : EXST; End; Var Stack : EXST; i : integer; f : text; Stroka : string; c : char; Procedure writeStack(Var u : EXST; Simvol : char); Var x : EXST; Begin new(x); x^.Data := Simvol; x^.Next := u; u := x; End; Procedure Print(Var u : EXST); Begin while u <> Nil do Begin write (u^.Data); u := u^.Next; End; End; Begin Stack := Nil; Assign(f, ‘c:\autoexec.bat’); Reset(f); while Not Eof(f) do Begin readln (f, Stroka); For i := 1 to Length(Stroka) do writeStack(Stack, Stroka[i]); Print(Stack); writeln; End; close(f); End.

        Пример 2. Написать программу, проверяющую своевременность закрытия скобок в строке символов.

        Для решения задачи определим стек, элементами которого являются символы:

        Type EXST = ^ST; ST = record Data : char; Next : EXST; End;

        Пусть факт наличия ошибки хранится в переменной логического типа f, то есть f=True, пока ошибка не найдена и f=False в противном случае. Тогда условие работы цикла будет выглядеть так:

        while (i<>Length(a)) and f do .

        Осталось выяснить, как определить, соответствует ли очередная закрывающая скобка скобке, находящейся в вершине стека. Можно заметить, что коды соответствующих друг другу скобок отличаются не более чем на 2, что можно проверить с помощью функции Ord(x)):

        < >123–125 [ ] 91–93 ( ) 40–41,

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

        if (Ord(a[i])–Ord(stack^.Data)) then . . .

        А теперь просмотрите полный текст программы:

        Program Skobki; Type EXST = ^ST; ST = record Data : char; Next : EXST; end; Var a : string; f : boolean; i : integer; Procedure writeStack(Var x1 : EXST; c : char); Var u : EXST; Begin new(u); u^.Data := c; u^.Next := x1; x1 := u; End; Procedure DelStack(Var x1 : EXST); Var u : EXST; Begin u := x1; x1 := x1^.Next; dispose(u); End; Procedure Solve(a : string); Var Stack : EXST; Begin Stack := Nil; i := 1; while (i <=Length(a)) and f do begin if (a[i]='(‘) or (a[i]=’ <') or (a[i]='[') then writeStack(Stack , a[i]) else if (a[i]=’)’) or (a[i]=’>’) or (a[i]=’]’) then if (Stack <> Nil) And (Ord(a[i]) — Ord(Stack ^.Data) then DelStack(Stack) else f := False; Inc(i); end; end; Begin writeln(‘Введите строку’); readln(a); f := True; if a<>» then begin Solve(a); if f then writeln(‘Все скобки расставлены верно’) else writeln(‘Скобка ‘,a[i-1],’ закрыта преждевременно’); end else writeln(‘Строка пуста’); readln; End.

        Задание. Разберите алгоритмы решения предложенных задач.

        Очередь. Основные операции над очередью

        Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала.

        Изобразим очередь графически:

        Итак, очередь – это вид связанного списка, в котором извлечение элементов происходит с начала списка, а добавление новых элементов – с конца. К этому виду списка, по определению, неприменима операция обхода элементов.

        Очередь является динамической структурой – с течением времени изменяется и колчество, и набор составляющих ее элементов.

        Опишем очередь на языке программирования:

        Type EXO = ^O; O = record Data : integer; Next : EXO; end;

        Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.

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

        Var BeginO, EndO : EXO;

        где BeginO – соответствует началу очереди и будет использоваться для удаления элемента из очереди, EndO – соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.

        Занесение элемента в очередь

        Занесение элемента в очередь реализуется как добавлению элемента в конец списка. Рассмотрите процедуру, описанную ниже.

        Procedure writeO(Var BeginO, EndO : EXO; c : integer); Var u : EXO; Begin new(u); u^.Data := c; u^.Next := Nil; if BeginO = Nil then BeginO := u else EndO^.Next := u; EndO := u; End;

        Задание. Создайте программу формирования очереди с использованием предложенной процедуры.

        Извлечение элемента из очереди

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

        Procedure readO(Var BeginO : EXO; Var c : integer); Var u : EXO; Function FreeO(x1 : EXO): boolean; Begin FreeO := (x1 = Nil); End; Begin if FreeO(BeginO) then writeln(‘Очередь пуста’) else begin c := BeginO^.Data; u := BeginO; BeginO := BeginO^.Next; dispose(u); end; End;

        Задание. Напишите программу, содержащую все необходимые процедуры и функции работы с очередью.

        Примеры решения задач

        Задание. Рассмотрите приведенные программы. Наберите их на компьютере, дополните комментарием и протестируйте. Имейте в виду, что уже рассмотренные выше подпрограммы в текстах задач пропущены.

        Пример 1. За один просмотр файла действительных чисел напечатать элементы файла в следующем порядке: сначала – все числа, меньшие а, затем – все числа из отрезка [а, b], и наконец – все остальные числа, сохраняя исходный порядок в каждой из этих трех групп чисел. Числа а и b задает пользователь.

        Program MordovskihK; Type EXO = ^O; O = record Data : real; Next : EXO; End; Var i, a, b : Real; Min, Vibr, Other, EndMin, EndVibr, EndOther : EXO; f : File of real; Stroka : string; Procedure writeO(Var BeginO, EndO : EXO; c : real); . . . Procedure Print(u : EXO); . . . Begin Min := Nil; Vibr := Nil; Other := Nil; EndMin := Nil; EndVibr := Nil; EndOther := Nil; writeln (‘Введите имя файла >’); readln(Stroka); writeln (‘Введите промежуток >’); readln(a, b); assign(f, Stroka); reset(f); while not Eof(f) do begin read(f, i); if i then writeO(Min, EndMin, i) else if (i>=a) and (i <=b) then writeO(Vibr, EndVibr, i) else writeO(Other, EndOther, i) end; close(f); writeln(‘Числа, меньшие ‘, а); Print(Min); writeln(‘Числа из промежутка [‘, а, ‘,’ , b, ‘]’); Print(Vibr); writeln(‘Числа, большие ‘, b); Print(Other); End.

        Пример 2. Из заданного текста перенести все цифры в конец каждой строки, сохранив их порядок.

        Program BaranovA; Type EXO = ^O; O = record Data : char; Next : EXO; End; Var O1, EndO1, O2, EndO2 : EXO; f1, f2 : text; Name, NewName, Stroka, NewStroka : string; Procedure writeO(Var BeginO, EndO : EXO; c : char); . . . Procedure readO(var u : EXO, var c: char); . . . Procedure ModifStr(St : string; var NewSt : string); Var i : integer; l : char; begin O1 := Nil; EndO1 := Nil; O2 := Nil; EndO2 := Nil; NewSt := »; for i := 1 to Length(St) do if St[i] in [‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘8’, ‘9’, ‘0’] then writeO(O2, EndO2, St[i]) else writeO(O1, EndO1, St[i]); while O1 <> Nil do begin readO(O1, l); NewSt := NewSt + l; end; while O2 <> Nil do begin readO(O2, l); NewSt := NewSt + l; end; End; Begin write(‘Введите имя исходного файла: ‘); readln(Name); write(‘Введите имя файла-результата: ‘); readln(NewName); assign(f1, Name); assign(f2, NewName); reset(f1); rewrite(f2); while not Eof(f1) do begin readln(f1, Stroka); ModifStr(Stroka, NewStroka); writeln(f2, NewStroka); end; close(f1); close(f2); End.

        Кольцо. Формирование кольца. Основные операции над кольцом

        Koльцо — это вид связанного списка, в котором указатель последнего элемента ссылается на первый элемент.

        Рассмотрите его графическое представление.

        К кольцу применим обход элементов, доступ возможен к любому элементу структуры.

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

        Опишем кольцо на языке программирования:

        Type TypeCircle = ^K; K = record Data : integer; Next : TypeCircle; End; Var Circle1 : TypeCircle;

        Формирование кольца

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

        Procedure FofmK(Var u : TypeCircle); Var x, y : TypeCircle; i, N, d : integer; Begin write(‘Введите количество звеньев кольца: ‘); readln(N); for i := 1 to N do begin new(x); write(‘Введите данные в звено: ‘); readln(d); x^.Data := d; if u=nil then u := x else y^.Next := x; y := x; end; x^.Next := u; End;

        Над кольцом определены три операции: занесение элемента в кольцо, извлечение элемента из кольца и обход кольца.

        Задание. Составьте программу, содержащую две процедуры: процедуру занесения элемента в кольцо и процедуру извлечения элемента из кольца по какому-либо условию. (Можно воспользоваться текстом предыдущей программы.)

        Обход кольца

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

        Рассмотрите процедуру обхода кольца.

        Procedure PrintК(u : TypeCircle); Var x : TypeCircle; Begin x := u; repeat write(x^.Data,’ ‘); x := x^.Next; until x = u; readln; End;

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

        Решение задач с применением динамической структуры кольцо

        Задание . Рассмотрите приведенную программу, наберите ее на компьютере, вставьте комментарий.

        Задача 1. N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая при этом круг. Определить порядок удаления ребят из круга.

        Program Schitalka; Type Children = ^Child; Child = record Name : string; Next : Children; end; Var Circle, p, Temp : Children; k, i, j, NumName : integer; text : string; Function NumSlov(Var S : string) : integer; Var i, d : integer; Begin d := 0; i := 1; while i begin while (S[i] = ‘ ‘) and (i Inc(i); while (S[i] <> ‘ ‘) and (i Inc(i); d := d+1; end; if S[Length(S)] = ‘ ‘ then d := d-1; NumSlov := d; End; Procedure AddName(Var Old, Young : Children); Begin Young^.Next := Old^.Next; Old^.Next := Young; End; Begin new(Circle); Circle^.Next := Circle; writeln(‘Считалка’); writeln(‘Введите текст считалки >’); readln(text); k := Numslov(text); writeln(‘Сколько человек в кругу? >’); readln(NumName); temp := Circle; for i:= 1 to NumName do begin write(‘Введите ‘,i,’-е имя:’); if i = 1 then readln(Circle^.name) else begin new(p); readln(p^.name); AddName(temp, p); temp:=p; end; end; temp := Circle; for i := 1 to NumName-1 do begin for j := 1 to k-1 do begin p := temp; temp := temp^.next; end; writeln(temp^.name, ‘- вышел’); p^.next:= temp.Next; dispose (temp); temp:=p^.Next; end; writeln(temp^.name, ‘- остался’); dispose (temp); end.