- Введение в информатику (Информатика. Информация. Представление и обработка информации. Системы счисления. Представление чисел в ЭВМ. Формализованное понятие алгоритма)
- Язык 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.
Автор: Цветкова А.В.
<< Назад: Абстрактные структуры данных (Абстрактные структуры данных. Стеки. Очереди)
>> Вперед: Графы (Понятие графа. Способы представления графа. Представление графа списком инцидентности. Алгоритм обхода графа в глубину. Представление графа списком списков. Алгоритм обхода графа в ширину)
Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:
▪ Общая гигиена. Конспект лекций
▪ Уголовный процесс. Шпаргалка
▪ Экспериментальная психология. Конспект лекций
Смотрите другие статьи раздела Конспекты лекций, шпаргалки.
Читайте и пишите полезные комментарии к этой статье.
<< Назад
Последние новости науки и техники, новинки электроники:
Питомцы как стимулятор разума
06.10.2025
Помимо эмоциональной поддержки, домашние питомцы могут оказывать заметное воздействие на когнитивные процессы, особенно у пожилых людей. Новое масштабное исследование показало, что общение с кошками и собаками не просто улучшает настроение - оно действительно способствует замедлению возрастного снижения умственных способностей.
Работа проводилась в рамках проекта Survey of Health, Ageing and Retirement in Europe (SHARE), охватывающего период с 2004 по 2022 год. В исследовании приняли участие тысячи европейцев старше 50 лет. Анализ показал, что владельцы домашних животных демонстрируют более устойчивые когнитивные функции по сравнению с теми, кто не держит питомцев. Особенно выражен эффект оказался у владельцев кошек и собак.
Согласно данным ученых, владельцы собак дольше сохраняют хорошую память, в то время как хозяева кошек медленнее теряют способность к быстрому речевому взаимодействию. Исследователи связывают это с тем, что ежедневное взаимодействие с животными требует внимани ...>>
Мини-ПК ExpertCenter PN54-S1
06.10.2025
Компания ASUSTeK Computer презентовала новый мини-компьютер ASUS ExpertCenter PN54-S1. Устройство ориентировано на пользователей, которым важно сочетание производительности, энергоэффективности и универсальности - от офисных задач до мультимедийных проектов.
В основе ExpertCenter PN54-S1 лежит современная аппаратная платформа AMD Hawk Point, использующая архитектуру Zen 4. Это поколение чипов отличается улучшенным управлением энергопотреблением и повышенной вычислительной мощностью. Новинка доступна в конфигурациях с процессорами Ryzen 7260, Ryzen 5220 и Ryzen 5210, представленных AMD в начале 2025 года. Таким образом, устройство охватывает широкий диапазон задач - от базовых офисных до ресурсоемких вычислений.
Корпус мини-ПК выполнен из прочного алюминия и имеет размеры 130×130×34 мм, что делает его практически незаметным на рабочем столе или за монитором. Несмотря на компактность, внутренняя компоновка позволяет установить два модуля оперативной памяти SO-DIMM ...>>
Глазные капли, возвращающие молодость зрению
05.10.2025
С возрастом человеческий глаз постепенно теряет способность четко видеть на близком расстоянии - развивается пресбиопия, или возрастная дальнозоркость. Этот естественный процесс связан с утратой эластичности хрусталика и ослаблением цилиарной мышцы, отвечающей за фокусировку. Миллионы людей по всему миру сталкиваются с необходимостью носить очки для чтения или прибегают к хирургическим методам коррекции. Однако исследователи из Центра передовых исследований пресбиопии в Буэнос-Айресе представили решение, которое может стать удобной и неинвазивной альтернативой - специальные глазные капли, способные улучшать зрение на длительный срок.
Разработку возглавила Джованна Беноцци, директор Центра. По ее словам, цель исследования состояла в том, чтобы предоставить пациентам с пресбиопией эффективный и безопасный способ коррекции зрения без хирургического вмешательства. Новые капли, созданные на основе пилокарпина и диклофенака, показали убедительные результаты: уже через час после первого пр ...>>
| Случайная новость из Архива Угроза древнему городу инков
17.02.2002
После недавнего землетрясения силой 7,9 балла в Перу выяснилось, что стране угрожает новая страшная опасность. По данным ученых, древний город инков, Мачу-Пикчу, виртуозно возведенный индейцами на огромном горном карнизе, может в любую минуту сорваться в пропасть.
Ведущий перуанский археолог, доктор Фредерико Кауфманн, обвиняет власти страны в полном пренебрежении итогами исследований японских ученых, которые доказывают, что для спасения древнего города инков необходимы безотлагательные меры. Обнаружено, что склон горы, на который опирается город, уже через несколько лет может подвергнуться оползню и рухнуть вниз. Под городом замечены подвижки земной коры. Темпы начинающегося оползня нарастают очень быстро, и ученые оценивают возможную продолжительность существования города самое большее в 15 лет.
Инки были великими строителями, они так подгоняли громадные каменные глыбы одну к другой, что между ними невозможно было втиснуть лезвие бритвы. Но теперь в стенах появляются щели, и виной тому - сейсмологические процессы под городом.
|
Другие интересные новости:
▪ Медицинские причины религиозного радикализма
▪ Китайский аналог GPS
▪ Откуда взялись голубые глаза
▪ Виагра против малярии
▪ Пиво на основе экзотических дрожжей
Лента новостей науки и техники, новинок электроники
Интересные материалы Бесплатной технической библиотеки:
▪ раздел сайта Индикаторы, датчики, детекторы. Подборка статей
▪ статья Прядильная машина. История изобретения и производства
▪ статья Как появился гороскоп? Подробный ответ
▪ статья Работа на высоте. Типовая инструкция по охране труда
▪ статья Универсальный программатор UNIPROG. Энциклопедия радиоэлектроники и электротехники
▪ статья ЧМ Трансвертер 144/27 МГц. Энциклопедия радиоэлектроники и электротехники
Оставьте свой комментарий к этой статье:
Главная страница | Библиотека | Статьи | Карта сайта | Отзывы о сайте
www.diagram.com.ua
2000-2025
