- Введение в информатику (Информатика. Информация. Представление и обработка информации. Системы счисления. Представление чисел в ЭВМ. Формализованное понятие алгоритма)
- Язык 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.
Автор: Цветкова А.В.
<< Назад: Абстрактные структуры данных (Абстрактные структуры данных. Стеки. Очереди)
>> Вперед: Графы (Понятие графа. Способы представления графа. Представление графа списком инцидентности. Алгоритм обхода графа в глубину. Представление графа списком списков. Алгоритм обхода графа в ширину)
Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:
▪ Национальная экономика. Конспект лекций
▪ Трудовое право Российской Федерации. Шпаргалка
▪ Государственное и муниципальное управление. Шпаргалка
Смотрите другие статьи раздела Конспекты лекций, шпаргалки.
Читайте и пишите полезные комментарии к этой статье.
<< Назад
Последние новости науки и техники, новинки электроники:
Тающие айсберги создают новые оазисы жизни на дне океана
30.06.2026
Глобальное потепление активно меняет облик нашей планеты, и одним из наиболее заметных его проявлений становится ускоренное таяние ледников в полярных регионах. Этот процесс не только приводит к подъему уровня Мирового океана, но и вызывает цепную реакцию в морских экосистемах, порой создавая неожиданные и парадоксальные последствия. Массовое высвобождение айсбергов из Гренландии - яркий пример того, как климатические изменения перестраивают жизнь в самых глубоких и удаленных уголках океана.
Из-за повышения температуры количество айсбергов, откалывающихся от гренландских ледников, стремительно растет. Ученые проанализировали данные за последние 40 лет и установили, что с 2000 года поток ледяных глыб через пролив Фрама увеличился в четыре раза. Об этом сообщает Futurism со ссылкой на исследование специалистов из Технического университета Дании.
Такое беспрецедентное нашествие айсбергов представляет серьезную опасность для международного судоходства. Одновременно оно радикально тра ...>>
Робот-тьютор Optio, помошник школьника
30.06.2026
Икусственный интеллект и робототехника все активнее помогают учителям и ученикам, делая обучение более персонализированным и увлекательным. Гуманоидные роботы, способные взаимодействовать с людьми естественным образом, открывают новые возможности для школ, особенно в условиях нехватки педагогических кадров и растущего интереса к технологиям. Одна из таких инновационных инициатив стартовала в американском штате Нью-Йорк.
Компания Realbotix запустила своего помощника учителя на базе искусственного интеллекта под названием Optio в Центральном школьном округе Саламанки. Робот выступает в роли тьютора, предлагая персонализированное репетиторство, многоязычную помощь с домашними заданиями и круглосуточную академическую поддержку. По данным Interesting Engineering, проект направлен на повышение вовлеченности учащихся и внедрение передовых технологий в учебный процесс.
В рамках пилотной программы школы округа планируют интегрировать человекоподобных роботов в классы. Изначально Optio буд ...>>
Биопрепараты повышают питательную ценность органической гречихи
29.06.2026
В органическом земледелии особое внимание уделяется не только урожайности, но и качественному составу продукции. Потребители все чаще выбирают продукты с высоким содержанием полезных веществ и без следов химических веществ. Исследования показывают, что применение биологических препаратов может существенно улучшить минеральный состав зерновых культур, делая их более ценными с точки зрения питания.
В результате полевых экспериментов, проведенных в 2023-2025 годах, ученые установили, что использование биопрепаратов способствует активному накоплению макроэлементов, в частности фосфора и калия, в зерне органической гречихи. Об этом сообщила Леся Крупак из Белоцерковского национального аграрного университета в своей работе "Экологичность и производительность".
Наиболее заметный эффект наблюдался при применении гумата калия. В этом случае содержание калия в зерне увеличивалось на 19-21 процент по сравнению с контрольными участками. Такой результат свидетельствует об улучшении работы тра ...>>
| Случайная новость из Архива Микроконтроллеры TI Hercules RM57Lx и TMS570LCx
30.05.2014
Компания Texas Instruments (TI) расширила семейство компонентов SafeTI двумя сериями микроконтроллеров, построенных на двухъядерных 32-разрядных процессорах ARM Cortex-R5: Hercules RM57Lx и TMS570LCx.
К уникальным особенностям новых представителей платформы Hercules производитель относит наличие блоков вычислений с плавающей запятой, которые обеспечивают прирост вычислительной производительности на 50% по сравнению с любым другим из выпускаемых сейчас микроконтроллеров TI. Это позволяет заменить одним "геркулесом" несколько других микроконтроллеров или связку из микроконтроллера и FPGA.
К другим достоинствам новинок относится наибольший среди других представителей платформы Hercules объем встроенной флэш-памяти и ОЗУ. Говоря более конкретно, объем флэш-памяти программ достигает 4 МБ, а объем оперативной памяти - 512 КБ. Дополнительные 128 КБ флэш-памяти используются для эмуляции ЭСППЗУ.
Для облечения освоения новых микроконтроллеров они сделаны совместимыми на уровне выводов и на программном уровне с ранее выпущенными моделями Hercules. Микроконтроллеры TI Hercules RM57Lx и TMS570LCx предназначены для промышленной, медицинской и бортовой электроники, а также систем управления безопасностью на транспорте.
Цена Hercules RM57Lx - от $28,32 за штуку, Hercules TMS570LCx - от $32,15.
|
Другие интересные новости:
▪ 4К дисплей со сверхшироким цветовым охватом
▪ Данные можно хранить в пыли
▪ Новый рекорд скорости для электрокаров
▪ Лодочный реактивный двигатель на забортной воде
▪ Почему после холодной воды болит голова
Лента новостей науки и техники, новинок электроники
Интересные материалы Бесплатной технической библиотеки:
▪ раздел сайта Электропитание. Подборка статей
▪ статья Не плакать, не смеяться, не ненавидеть, но понимать. Крылатое выражение
▪ статья Что такое археология? Подробный ответ
▪ статья Расположение звезд в средней полосе северного полушария. Советы туристу
▪ статья Регулятор температуры. Энциклопедия радиоэлектроники и электротехники
▪ статья Случайные статьи. Большая подборка
Оставьте свой комментарий к этой статье:
Главная страница | Библиотека | Статьи | Карта сайта | Отзывы о сайте
www.diagram.com.ua
2000-2026
