ЛЕКЦИЯ № 8. Абстрактные структуры данных

1. Абстрактные структуры данных

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

Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими. К ним относятся стеки, очереди, списки, деревья и др.

Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

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

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

1) добавление элемента к списку;

2) удаление элемента из списка с заданным ключом;

3) поиск элемента с заданным значением ключевого поля;

4) сортировка элементов списка;

5) деление списка на два и более списков;

6) объединение двух и более списков в один;

7) другие операции.

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

2. Стеки

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO(Last-In, First-Out) - "Поступивший последним, обслуживается первым".

Обычно над стеками выполняется три операции:

1) начальное формирование стека (запись первой компоненты);

2) добавление компоненты в стек;

3) выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две переменные типа "указатель", первая из которых определяет вершину стека, а вторая - вспомогательная.

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

Program STACK;

end.

3. Очереди

Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) - "Поступивший первым, обслуживается первым".

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

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

Program QUEUE;

end.

Автор: Цветкова А.В.

<< Назад: Абстрактные структуры данных (Абстрактные структуры данных. Стеки. Очереди)

>> Вперед: Графы (Понятие графа. Способы представления графа. Представление графа списком инцидентности. Алгоритм обхода графа в глубину. Представление графа списком списков. Алгоритм обхода графа в ширину)

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

▪ Общая и клиническая иммунология. Конспект лекций

▪ Стратегический менеджмент. Конспект лекций

▪ История медицины. Шпаргалка

Смотрите другие статьи раздела Конспекты лекций, шпаргалки.

Читайте и пишите полезные комментарии к этой статье.

<< Назад

Последние новости науки и техники, новинки электроники:

Рыжий ген и ускоренная эволюция 30.04.2026

Вопрос о том, как и насколько быстро меняется человеческий вид, давно занимает биологов и генетиков. Долгое время считалось, что эволюционные процессы происходят крайне медленно, однако новые данные заставляют пересматривать эти представления. Особенно интересные результаты связаны с изменением частоты редких генетических признаков, включая рыжий цвет волос. Рыжеволосость сегодня остается редкой чертой: ее носители составляют менее 2 процентов мирового населения. Однако анализ древней и современной ДНК показывает, что ген, связанный с этим признаком, за последние примерно 10 тысяч лет стал заметно более распространенным, особенно среди популяций Европы. Более того, вместе с ним исследователи фиксируют и другие изменения в генетическом профиле человека, затрагивающие внешность и физиологические особенности. Среди сопутствующих тенденций, выявленных в генетических данных, отмечается увеличение частоты светлой кожи, снижение вероятности мужского облысения, а также некоторые физиолог ...>>

Нейтринный лазер 30.04.2026

Нейтринный лазер - это гипотетическое устройство, способное управлять потоками одних из самых трудноуловимых частиц во Вселенной. Такая разработка открывает новые горизонты в изучении фундаментальных законов природы и может изменить представления о космосе. Идею нового типа излучателя представили физики из Massachusetts Institute of Technology, предложив лазер, который вместо света генерирует поток нейтрино. Эти частицы, почти не взаимодействующие с материей, настолько слабо проявляют себя, что их часто называют "частицами-призраками". Тем не менее они пронизывают все вокруг: по оценкам, триллионы нейтрино ежесекундно проходят через человеческое тело, не оставляя следа. Несмотря на их колоссальную распространенность во Вселенной, нейтрино остаются одними из наименее изученных частиц. Их крайне сложно регистрировать, а еще сложнее контролировать, поэтому традиционно их получают в крупных установках вроде ядерных реакторов или ускорителей частиц. Такие комплексы требуют огромных за ...>>

Мороженое не такое вредное, как принято считать 29.04.2026

В питании часто встречаются продукты, которые одновременно вызывают удовольствие и сомнения с точки зрения здоровья. К таким относится и мороженое: оно воспринимается как типичный десерт с высоким содержанием сахара и жиров, однако современные научные данные постепенно усложняют это привычное представление. Долгое время считалось, что мороженое не может быть частью рационального питания, однако исследования последних лет показывают более неоднозначную картину. Ученые подчеркивают, что влияние этого продукта на организм зависит не только от его сладости или калорийности, но и от состава, качества ингредиентов и общего образа жизни человека. Одни из наиболее масштабных данных были получены в рамках долгосрочных наблюдений в США, включавших проекты Nurses Health Study, Nurses Health Study II и Health Professionals Follow-Up Study. В этих исследованиях на протяжении 20-40 лет наблюдали примерно 190 тысяч взрослых участников, регулярно собирая данные об их питании, физической активнос ...>>

Случайная новость из Архива Новые твердотельные реле International Rectifier 16.06.2007 По отношению к аналогам и предшественникам семейство PVN012A обладает вдвое меньшим сопротивлением по переменному току в открытом состоянии (Rdd(on)) и на 37,5% более высокой нагрузочной способностью на переменном токе при 100% скважности. Новая серия реле также нормирована на максимальный импульсный (перегрузочный) ток. Благодаря низкому сопротивлению канала и высокой нагрузочной способности по току в сочетании с компактным корпусом реле PVN012A превосходят возможности традиционных электромеханических реле. Они занимают меньшую площадь, нормированы на высокое напряжение изоляции между входом и выходом, имеют стабильное сопротивление в открытом состоянии в течение всего срока эксплуатации, высокую чувствительность и высокую надежность, свободны от дребезга контактов. Новые реле нормированы на напряжение 20 В, сопротивление в открытом состоянии 50 мОм на переменном и 15 мОм на постоянном токе. Нагрузочная способность по току составляет 4 А на переменном и 6 А на постоянном токе. Испытательное напряжение при проверке изоляции между входом и выходом равно 4000 В. Новые реле выпускаются в бессвинцовых 6-выводных DIPи SOIC-корпусах и на ленте.

Другие интересные новости:

▪ Мобильник помогает ориентироваться в городе

▪ Архив Википедии спрячут на поверхности Луны

▪ За пристрастие к кофе отвечают гены

▪ Кабина для общения с голограммой собеседника

▪ Планшетофон Newman K2S с восьмиядерным процессором MediaTek MT6592

Лента новостей науки и техники, новинок электроники

Интересные материалы Бесплатной технической библиотеки:

▪ раздел сайта Микроконтроллеры. Подборка статей

▪ статья Мещанское счастье. Крылатое выражение

▪ статья Что называется бизнесом? Подробный ответ

▪ статья Мотор для летательного аппарата. Личный транспорт

▪ статья Светодиодное устройство Снежинка. Энциклопедия радиоэлектроники и электротехники

▪ статья Источник питания с автоматическим зарядным устройством. Энциклопедия радиоэлектроники и электротехники

[an error occurred while processing this directive] Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2026