- Введение в информатику (Информатика. Информация. Представление и обработка информации. Системы счисления. Представление чисел в ЭВМ. Формализованное понятие алгоритма)
- Язык 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.
Автор: Цветкова А.В.
<< Назад: Абстрактные структуры данных (Абстрактные структуры данных. Стеки. Очереди)
>> Вперед: Графы (Понятие графа. Способы представления графа. Представление графа списком инцидентности. Алгоритм обхода графа в глубину. Представление графа списком списков. Алгоритм обхода графа в ширину)
Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:
▪ Макроэкономика. Шпаргалка
▪ Стратегический менеджмент. Конспект лекций
▪ Финансовое право. Шпаргалка
Смотрите другие статьи раздела Конспекты лекций, шпаргалки.
Читайте и пишите полезные комментарии к этой статье.
<< Назад
Последние новости науки и техники, новинки электроники:
Биокаталитический способ получения хиральных оксазолидинонов
14.10.2026
Химия все чаще обращается к биологическим молекулам, чтобы сделать синтез сложных веществ более точным и эффективным. Особенно важны такие технологии при создании соединений, у которых одинаковый химический состав может сопровождаться разным пространственным расположением атомов и, следовательно, различными свойствами. Исследователи из Калифорнийского технологического института и Университета Питтсбурга предложили новый биокаталитический подход, позволяющий получать хиральные оксазолидиноны непосредственно из простых неактивированных алкенов.
В основе предложенного метода лежит последовательность из двух реакций - азиридинирования и последующего расширения цикла. Этот каскад запускается с помощью гемопротеина, который выполняет функцию катализатора и позволяет направлять химическое превращение в нужную сторону. В результате из относительно простого исходного соединения формируется более сложная циклическая структура с заданной пространственной конфигурацией.
Особенно существенным ...>>
Клавиатура Gboard kurukuru version с вращающимися лентами
14.10.2026
Обычная клавиатура предполагает, что движется человек: пальцы перемещаются от одной неподвижной клавиши к другой, а расположение символов остается неизменным. Google Japan решила перевернуть этот привычный принцип и проверить, что произойдет, если заставить двигаться сам интерфейс. Так появился экспериментальный проект Gboard, в котором клавиши постоянно перемещаются и сами оказываются в зоне нажатия.
Необычная конструкция получила название Gboard "Курукуру-версия" (Gboard kurukuru version). Проект стал очередным ежегодным экспериментом японского подразделения Google, посвященным альтернативным способам взаимодействия человека с текстом. На этот раз идея не ограничилась компьютерной концепцией: специалисты создали полноценный физический прототип, способный работать в реальных условиях, а материалы для его самостоятельного изготовления сделали доступными для всех желающих.
Основу устройства образуют четыре замкнутые подвижные ленты, вращающиеся вокруг конструкции. На каждой из них ...>>
Легкий бег влияет на мозг и самоконтроль
13.10.2026
Физическая активность не обязательно должна быть интенсивной, чтобы на короткое время изменить состояние мозга. Новое исследование японских специалистов показывает, что даже непродолжительный бег с очень небольшой нагрузкой способен повлиять на настроение, внимание и способность контролировать собственные действия. Причем для этого, по данным эксперимента, может быть достаточно всего 10 минут.
Работу провели исследователи из Университета Цукубы с участием 24 здоровых молодых людей. Добровольцы выполняли два разных условия: в одном случае они спокойно сидели в течение 10 минут, а в другом такое же время проводили на беговой дорожке. Скорость во время пробежки составляла приблизительно от 3 до 6 км/ч, поэтому нагрузка оставалась сравнительно небольшой. Средняя частота сердечных сокращений участников при этом находилась в пределах 104-107 ударов в минуту.
После завершения физической активности добровольцы сообщали о большей бодрости и более приятном эмоциональном состоянии по сравне ...>>
| Случайная новость из Архива Нейрокомпьютерный интерфейс имплантирован человеку
30.07.2022
Нейрокомпьютерный интерфейс стал в Соединенных Штатах реальностью (хотя пока и ограниченной). В Synchron сообщают, что она стала первой в стране компанией, которой удалось имплантировать нейрокомпьютерный интерфейс человеку.
Врачи из нью-йоркского медицинского центра Mount Sinai West имплантировали устройство производства компании Stentrode в моторную кору пациента, согласившегося принять участие в организованном компанией Synchron эксперименте COMMAND. Его цель заключается в оценке полезности и безопасности нейрокомпьютерных интерфейсов для обеспечения людям, страдающим на сильный паралич, возможности управления устройством без использования рук.
В идеале технология Stentrode должна дать таким людям возможности самостоятельно отправлять электронные письма, текстовые сообщения и выполнять другие задачи в цифровой среде, которые воспринимаются здоровыми людьми как должное.
Хирурги установили имплант путем эндоваскулярной процедуры, позволяющей избежать серьезной операции на открытом мозге, введя его через яремную вену. Операция прошла "чрезвычайно хорошо", и, как сообщают Synchron, уже через 48 часов пациент смог вернуться домой. Эксперимент, продолжающийся в Австралии, также проходит хорошо: четыре пациента, которым год назад были установлены импланты, чувствуют себя нормально.
Понятно, что к тому моменту, когда врачи смогут предлагать установку нейрокомпьютерных интерфейсов от Synchron всем нуждающимся пациентам пройдет еще много времени.
В июле 2021 года компания получила от Управления по продовольствию и медикаментам США (FDA) разрешение на проведение операции по имплантации интерфейса людям в рамках экспериментальной программы COMMAND, которая действует и на момент написания этой новости.
Процедура, проведенная в США, стала значительным шагом вперед. Она позволит людям, страдающим параличом, вернуть возможность самостоятельного контроля за своей жизнью. Она также свидетельствует о победе компании Synchron в конкурентной борьбе - Илон Маск, к примеру, до сих пор не получил от FDA разрешения на использование имплантов, разработанных его компанией.
|
Другие интересные новости:
▪ Определение калорийности пищи по фотографии
▪ Создан гибрид мобильника и телевизора
▪ Электромобиль-трансформер Audi Activesphere
▪ Летающая 4G-вышка - дрон Flying COW
▪ Электрическая подводная лодка для туристов
Лента новостей науки и техники, новинок электроники
Интересные материалы Бесплатной технической библиотеки:
▪ раздел сайта Радиолюбительские расчеты. Подборка статей
▪ статья Бить челом. Крылатое выражение
▪ статья Как вначале использовали обнаруженную на Урале платину? Подробный ответ
▪ статья Защита от поражения электротоком
▪ статья Практические конструкции антенн DJ9BV на диапазон 144 МГц. Энциклопедия радиоэлектроники и электротехники
▪ статья Зажгите свечу. Секрет фокуса
Оставьте свой комментарий к этой статье:
Главная страница | Библиотека | Статьи | Карта сайта | Отзывы о сайте
www.diagram.com.ua
2000-2026
