- Введение в информатику (Информатика. Информация. Представление и обработка информации. Системы счисления. Представление чисел в ЭВМ. Формализованное понятие алгоритма)
- Язык 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.11.2025
Предсказание землетрясений остается одной из самых сложных задач геофизики. Несмотря на развитие сейсмологии, ученые все еще не могут точно определить момент начала разрушительного движения разломов. Недавние эксперименты американских исследователей открывают новые горизонты: впервые удалось наблюдать микроскопические изменения в контактной зоне разломов, которые предшествуют землетрясению.
Группа под руководством Сильвена Барбота обнаружила, что "реальная площадь контакта" - участки, где поверхности разлома действительно соприкасаются - изменяется за миллисекунды до высвобождения накопленной энергии. "Мы открыли окно в сердце механики землетрясений", - отмечает Барбот. Эти изменения позволяют фиксировать этапы зарождения сейсмического события еще до появления традиционных сейсмических волн.
Для наблюдений ученые использовали прозрачные акриловые материалы, через которые можно было отслеживать световые изменения в зоне контакта. В ходе искусственного моделирования примерно 30% ко ...>>
Музыка как естественный анальгетик
30.11.2025
Ученые все активнее исследуют немедикаментозные способы облегчения боли. Одним из перспективных направлений становится использование музыки, которая способна воздействовать на эмоциональное состояние и когнитивное восприятие боли. Новое исследование международной группы специалистов демонстрирует, что даже кратковременное прослушивание любимых композиций может значительно снижать болевые ощущения у пациентов с острой болью в спине.
В эксперименте участвовали пациенты, обратившиеся за помощью в отделение неотложной помощи с выраженной болью в спине. Им предлагалось на протяжении десяти минут слушать свои любимые музыкальные треки. Уже после этой короткой сессии врачи фиксировали заметное уменьшение интенсивности боли как в состоянии покоя, так и при движениях.
Авторы исследования подчеркивают, что музыка не устраняет саму причину боли. Тем не менее, она воздействует на эмоциональный фон пациента, снижает уровень тревожности и отвлекает внимание, что в сумме приводит к субъективном ...>>
Алкоголь может привести к слобоумию
29.11.2025
Проблема влияния алкоголя на стареющий мозг давно вызывает интерес как у врачей, так и у исследователей когнитивного старения. В последние годы стало очевидно, что границы "безопасного" употребления спиртного размываются, и новое крупное исследование, проведенное международной группой ученых, вновь указывает на это. Работы Оксфордского университета, выполненные совместно с исследователями из Йельского и Кембриджского университетов, показывают: даже небольшие дозы алкоголя способны ускорять когнитивный спад.
Команда проанализировала данные более чем 500 тысяч участников из британского биобанка и американской Программы миллионов ветеранов. Дополнительно был выполнен метаанализ сорока пяти исследований, в общей сложности включавших сведения о 2,4 миллиона человек. Такой масштаб позволил оценить не только прямую связь между употреблением спиртного и развитием деменции, но и влияние генетической предрасположенности.
Один из наиболее тревожных результатов касается людей с повышенным ге ...>>
| Случайная новость из Архива Пчелы-защитницы
06.10.2009
Энтомологи из университета Вюрцбурга (Германия) показали, что жужжание летающих пчел может отпугивать гусениц от поедания растений.
Под шатер из прозрачной полиэтиленовой пленки помещали растения сои и сладкого перца, по углам шатра ставили поилки с сахарным сиропом. На листья сажали гусениц малой совки. В тех случаях, когда в шатер запускали полсотни пчел, и они с жужжанием носились между поилками, гусеницы приостанавливали питание, сворачивались и падали с листьев.
Авторы эксперимента полагают, что вредители пугаются пчел, принимая их за ос, которые охотятся на гусениц. Тело гусеницы покрыто специальными волосками, воспринимающими звуковые колебания воздуха.
|
Другие интересные новости:
▪ Создано средство от диабета и ожирения
▪ Модуль памяти со сменой фазы
▪ Новая жизнь дирижаблей
▪ Батарейка размером с крупицу соли
▪ Акустика Стоунхенджа
Лента новостей науки и техники, новинок электроники
Интересные материалы Бесплатной технической библиотеки:
▪ раздел сайта Моделирование. Подборка статей
▪ статья Медицинские средства индивидуальной защиты. Основы безопасной жизнедеятельности
▪ статья Что такое слюда? Подробный ответ
▪ статья Куркума длинная. Легенды, выращивание, способы применения
▪ статья Автомобильные радиопередатчики. Энциклопедия радиоэлектроники и электротехники
▪ статья Необыкновенная ваза. Секрет фокуса
Оставьте свой комментарий к этой статье:
Главная страница | Библиотека | Статьи | Карта сайта | Отзывы о сайте
www.diagram.com.ua
2000-2025
