Menu Home

Бесплатная техническая библиотека для любителей и профессионалов Бесплатная техническая библиотека


Информатика и информационные технологии. Древовидные структуры данных (конспект лекций)

Конспекты лекций, шпаргалки

Справочник / Конспекты лекций, шпаргалки

Комментарии к статье Комментарии к статье

Оглавление (развернуть)

ЛЕКЦИЯ № 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К дисплей со сверхшироким цветовым охватом

▪ Данные можно хранить в пыли

▪ Новый рекорд скорости для электрокаров

▪ Лодочный реактивный двигатель на забортной воде

▪ Почему после холодной воды болит голова

Лента новостей науки и техники, новинок электроники

 

Интересные материалы Бесплатной технической библиотеки:

▪ раздел сайта Электропитание. Подборка статей

▪ статья Не плакать, не смеяться, не ненавидеть, но понимать. Крылатое выражение

▪ статья Что такое археология? Подробный ответ

▪ статья Расположение звезд в средней полосе северного полушария. Советы туристу

▪ статья Регулятор температуры. Энциклопедия радиоэлектроники и электротехники

▪ статья Случайные статьи. Большая подборка

Оставьте свой комментарий к этой статье:

Имя:


E-mail (не обязательно):


Комментарий:





Главная страница | Библиотека | Статьи | Карта сайта | Отзывы о сайте

www.diagram.com.ua

www.diagram.com.ua
2000-2026