- Введение в информатику (Информатика. Информация. Представление и обработка информации. Системы счисления. Представление чисел в ЭВМ. Формализованное понятие алгоритма)
- Язык Pascal (Введение в язык Pascal. Стандартные процедуры и функции. Операторы языка Pascal)
- Процедуры и функции (Понятие вспомогательного алгоритма. Процедуры в Pascal. Функции в Pascal. Опережающие описания и подключение подпрограмм. Директива)
- Подпрограммы (Параметры подпрограмм. Типы параметров подпрограмм. Строковый тип в Pascal. Процедуры и функции для переменных строкового типа. Записи. Множества)
- Файлы (Файлы. Операции с файлами. Модули. Виды модулей)
- Динамическая память (Ссылочный тип данных. Динамическая память. Динамические переменные. Работа с динамической памятью. Нетипизированные указатели)
- Абстрактные структуры данных (Абстрактные структуры данных. Стеки. Очереди)
- Древовидные структуры данных (Древовидные структуры данных. Операции над деревьями. Примеры реализации операций)
- Графы (Понятие графа. Способы представления графа. Представление графа списком инцидентности. Алгоритм обхода графа в глубину. Представление графа списком списков. Алгоритм обхода графа в ширину)
- Объектный тип данных (Объектный тип в Pascal. Понятие объекта, его описание и использование. Наследование. Создание экземпляров объектов. Компоненты и область действия)
- Методы (Методы. Конструкторы и деструкторы. Деструкторы. Виртуальные методы. Поля данных объекта и формальные параметры метода)
- Совместимость типов объектов (Инкапсуляция. Расширяющиеся объекты. Совместимость типов объектов)
- Ассемблер (Об ассемблере. Программная модель микропроцессора. Пользовательские регистры. Регистры общего назначения. Сегментные регистры. Регистры состояния и управления)
- Регистры (Системные регистры микропроцессора. Регистры управления. Регистры системных адресов. Регистры отладки)
- Программы на Ассемблере (Структура программы на Ассемблере. Синтаксис Ассемблера. Операторы сравнения. Операторы и их приоритет. Упрощенные директивы определения сегмента. Идентификаторы, создаваемые директивой MODEL. Модели памяти. Модификаторы модели памяти)
- Структуры команд на Ассемблере (Структура машинной команды. Способы задания операндов команды. Способы адресации)
- Команды (Команды пересылки данных. Арифметические команды)
- Команды передачи управления (Логические команды. Таблица истинности для логического отрицания. Таблица истинности для логического включающего ИЛИ. Таблица истинности для логического И. Таблица истинности для логического исключающего ИЛИ. Значение аббревиатур в названии команды jcc. Перечень команд условного перехода для команды. Команды условного перехода и флаги)
ЛЕКЦИЯ № 8. Абстрактные структуры данных
1. Абстрактные структуры данных
Структурированные типы данных, такие как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы.
Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими. К ним относятся стеки, очереди, списки, деревья и др.
Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.
Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два поля: одно поле типа "указатель", а второе - для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью.
Если в указующей части содержится адрес одного элемента списка, то список называется однонаправленным (или односвязным). Если же он содержит две компоненты, то двусвязным. Над списками можно проводить различные операции, например:
1) добавление элемента к списку;
2) удаление элемента из списка с заданным ключом;
3) поиск элемента с заданным значением ключевого поля;
4) сортировка элементов списка;
5) деление списка на два и более списков;
6) объединение двух и более списков в один;
7) другие операции.
Однако, как правило, необходимости во всех операциях при решении различных задач не возникает. Поэтому в зависимости от основных операций, которые необходимо применить, существуют различные виды списков. Наиболее популярные из них - это стек и очередь.
2. Стеки
Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO(Last-In, First-Out) - "Поступивший последним, обслуживается первым".
Обычно над стеками выполняется три операции:
1) начальное формирование стека (запись первой компоненты);
2) добавление компоненты в стек;
3) выборка компоненты (удаление).
Для формирования стека и работы с ним необходимо иметь две переменные типа "указатель", первая из которых определяет вершину стека, а вторая - вспомогательная.
Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных - с клавиатуры, признак конца ввода - строка символов END.
Program STACK;
uses Crt;
type
Alfa = String[10];
PComp = ^Comp;
Comp = Record
sD : Alfa;
pNext : PComp
end;
var
pTop : PComp;
sC : Alfa;
Procedure CreateStack(var pTop : PComp; var sC : Alfa);
begin
New(pTop);
pTop^.pNext := NIL;
pTop^.sD := sC;
end;
Procedure AddComp(var pTop : PComp; var sC : Alfa);
var pAux : PComp;
begin
NEW(pAux);
pAux^.pNext := pTop;
pTop := pAux;
pTop^.sD := sC;
end;
Procedure DelComp(var pTop : PComp; var sC : ALFA);
begin
sC := pTop^.sD;
pTop := pTop^.pNext;
end;
begin
Clrscr;
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
CreateStack(pTop, sC);
repeat
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
AddComp(pTop, sC);
until sC = 'END';
writeln('****** ВЫВОД РЕЗУЛbТАТОВ ******');
repeat
DelComp(pTop, sC);
writeln(sC);
until pTop = NIL;
end.
3. Очереди
Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) - "Поступивший первым, обслуживается первым".
Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди, вторая - конец очереди, третья - вспомогательная.
Пример. Составить программу, которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных - с клавиатуры, признак конца ввода - строка символов END.
Program QUEUE;
uses Crt;
type
Alfa = String[10];
PComp = ^Comp;
Comp = record
sD : Alfa;
pNext : PComp;
end;
var
pBegin, pEnd : PComp;
sC : Alfa;
Procedure CreateQueue(var pBegin,pEnd:PComp; var sC:Alfa);
begin
New(pBegin);
pBegin^.pNext := NIL;
pBegin^.sD := sC;
pEnd := pBegin;
end;
Procedure AddQueue(var pEnd : PComp; var sC : Alfa);
var pAux : PComp;
begin
New(pAux);
pAux^.pNext := NIL;
pEnd^.pNext := pAux;
pEnd := pAux;
pEnd^.sD := sC;
end;
Procedure DelQueue(var pBegin : PComp; var sC : Alfa);
begin
sC := pBegin^.sD;
pBegin := pBegin^.pNext;
end;
begin
Clrscr;
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
CreateQueue(pBegin, pEnd, sC);
repeat
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
AddQueue(pEnd, sC);
until sC = 'END';
writeln(' ***** ВЫВОД РЕЗУЛbТАТОВ *****');
repeat
DelQueue(pBegin, sC);
writeln(sC);
until pBegin = NIL;
end.
Автор: Цветкова А.В.
<< Назад: Абстрактные структуры данных (Абстрактные структуры данных. Стеки. Очереди)
>> Вперед: Графы (Понятие графа. Способы представления графа. Представление графа списком инцидентности. Алгоритм обхода графа в глубину. Представление графа списком списков. Алгоритм обхода графа в ширину)
Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:
▪ Общая и клиническая иммунология. Шпаргалка
▪ Право социального обеспечения. Шпаргалка
▪ Экономическая география. Шпаргалка
Смотрите другие статьи раздела Конспекты лекций, шпаргалки.
Читайте и пишите полезные комментарии к этой статье.
<< Назад
Последние новости науки и техники, новинки электроники:
Хорошо управляемые луга могут компенсировать выбросы от скота
15.02.2026
Животноводство, особенно разведение крупного рогатого скота, часто обвиняют в значительном вкладе в глобальное потепление из-за мощного парникового газа - метана, который выделяется при пищеварении у жвачных животных. Это вызывает острые политические споры и призывы к сокращению потребления мяса. Однако ученые напоминают, что полная картина климатического воздействия отрасли не ограничивается только выбросами от животных: огромную роль играет окружающая экосистема - пастбища, почва и растительность, которые способны активно поглощать углекислый газ из атмосферы.
Исследователи из Университета Небраски-Линкольна решили глубже изучить этот баланс. Группа под руководством профессора Галена Эриксона сосредоточилась на том, как правильно организованные пастбища накапливают углерод в растениях и грунте благодаря естественным процессам, стимулируемым выпасом скота. Ученые подчеркивают, что при достаточном уровне осадков и грамотном управлении такие луга превращаются в мощные природные погло ...>>
NASA тестирует инновационную технологию крыла
15.02.2026
Коммерческая авиация ежегодно расходует колоссальные объемы керосина, что сказывается не только на бюджете авиакомпаний, но и на состоянии окружающей среды. В 2024 году глобальные затраты на авиационное топливо достигли 291 миллиарда долларов, и эта сумма продолжает расти. Чтобы справиться с этими вызовами, NASA активно работает над технологиями, способными заметно повысить аэродинамическую эффективность самолетов. Одним из самых перспективных направлений стало создание специальной конструкции крыла, которая максимизирует естественный ламинарный поток воздуха и минимизирует сопротивление.
В январе 2026 года специалисты NASA Armstrong Flight Research Center успешно провели важный этап наземных испытаний концепции Crossflow Attenuated Natural Laminar Flow (CATNLF). Для эксперимента под фюзеляж исследовательского самолета F-15B закрепили вертикально ориентированную масштабную модель высотой около 0,9 м (3 фута), напоминающую узкий киль. Такая компоновка позволила подвергнуть прототип р ...>>
Забота о внуках очень полезна для здоровья мозга
14.02.2026
Общение между поколениями приносит радость всей семье, но мало кто задумывается, насколько активно бабушки и дедушки, заботящиеся о внуках, поддерживают свою умственную форму. Регулярное взаимодействие с детьми стимулирует мозг пожилых людей, помогая сохранять память, скорость мышления и общую когнитивную активность.
Новые научные данные подтверждают, что такая добровольная помощь не только важна для общества, но и может замедлять возрастные изменения в мозге.
Исследователи из Тилбургского университета в Нидерландах провели анализ, чтобы понять, приносит ли уход за внуками реальную пользу здоровью пожилых людей. Ведущий автор работы Флавия Черечес отметила, что многие бабушки и дедушки регулярно присматривают за детьми, и оставался открытым вопрос, насколько это положительно сказывается на их собственном благополучии, особенно в плане когнитивных функций.
Ученые поставили цель выяснить, способен ли регулярный уход за внуками замедлить снижение памяти и других умственных способ ...>>
| Случайная новость из Архива Настраиваемые динамики JBL Studio 2 и JBL Arena
24.10.2015
Специально для требовательных меломанов компания Harman International Industries разработала акустические системы высокого уровня JBL Studio 2 и JBL Arena архитектурной серии. Новинки сочетают безупречный (по утверждению производителя) дизайн с лучшим качеством звучания в своем классе. Динамики предназначены для встраивания в стены или потолок и дополняют уже имеющиеся в ассортименте Harman другие модели семейств JBL Studio 2 и JBL Arena.
Благодаря технологии JBL High Definition Imaging (HDI) Waveguide динамики обеспечивают реалистичную звуковую сцену, которой можно наслаждаться в каждой точке комнаты. Для монтажа динамиков предлагаются крепления XL-2. При этом толщина стены может быть менее пяти сантиметров. Специальный зажим минимизирует вибрации, создаваемые при работе.
Модели Studio 2 включают высокочастотные динамики, выполненные из композитного алюминия, и басы PolyPlas. В зависимости от предпочтений пользователей и акустических особенностей помещения предусмотрена компенсация в пределах 3 дБ.
Стоимость новинок - от $175 до $350.
|
Другие интересные новости:
▪ Пузырьки против ураганов
▪ Видеокамеры JVC GZ-R550 и GZ-R440
▪ Лягушачий рай
▪ Любители орехов живут дольше
▪ Процессор Celeron 1019Y для в ультрабуков
Лента новостей науки и техники, новинок электроники
Интересные материалы Бесплатной технической библиотеки:
▪ раздел сайта Аудиотехника. Подборка статей
▪ статья Трактор. История изобретения и производства
▪ статья Какая империя в истории человечества была самой долгоживущей? Подробный ответ
▪ статья Сварка полиэтиленовых газопроводов. Типовая инструкция по охране труда
▪ статья Бытовая электроника. Звонки и аудио-имитаторы. Справочник
▪ статья Распределительные устройства и подстанции напряжением выше 1 кB. Открытые распределительные устройства. Энциклопедия радиоэлектроники и электротехники
Оставьте свой комментарий к этой статье:
Главная страница | Библиотека | Статьи | Карта сайта | Отзывы о сайте
www.diagram.com.ua
2000-2026
