Другими словами, сущность задачи (проблемы) и метода ее решения мы описываем (очевидно, на каком-то языке, а это уже и есть формализованная запись!) на уровне данных в программе, а ее поведение — действиями над данными. <...> Структура книги В этой книге описываются абстрактные типы данных— матрицы, списки, стек, очередь, двоичные деревья, множества, очереди с приоритетом, сбалансированные деревья. <...> Таблица 1.1 Имя Адрес начального элемента (физический адрес первого элемента массива) Индекс начального элемента Индекс конечного элемента Типэлемента Длинаэлемента V address(V[i]) i k Integer w(=2) Адрес элемента V с индексом j вычисляется по следующей формуле: address(V[j]) a address(V[i]) + (j–i)*w. <...> Тогда адрес элемента V[13,5] при отображении по строкам равен Integer)—а он обязательно создается—в этом случае может иметь вид, представленный в табл. <...> Procedure MatrixSumm(n:Integer; Const A:TInt; ka,la:Integer; Const B:TInt; kb,lb:Integer; Var C:TInt; kc,lc:Integer; IsSumm:Boolean); Var i,j:Integer; Begin For i:=1 To n Do For j:=1 To n Do If IsSumm Then Else C[kc+i,lc+j]:=A[ka+i,la+j]+B[kb+i,lb+j] C[kc+i,lc+j]:=A[ka+i,la+j]-B[kb+i,lb+j]; End; Вслучаекогдаnне является степенью числа 2, обрабатываемая матрица вкладывается в матрицу, порядок которой равен наименьшей степени числа 2, большей n.Эта операция увеличивает порядок матрицы не более чем вдвое, а константу в оценке времени работы — не более чем в семь раз. <...> Матрицы При реализации этого способа в основной процедуре определяется наименьшая степень двойки, большая n,иосуществляется вызов рекурсивной процедуры MatrixMult: Procedure Solve; Var m:Integer; Begin m:=1; While m<n <...>
Абстрактные_типы_данных_(1).pdf
УДК 519.85(023)
ББК 22.18
О-52
С е р и я о с н о в а н а в 2008 г.
Окулов С. М.
О-52
Абстрактные типы данных / С. М. Окулов.—
4-е изд., электрон.—М. : Лаборатория знаний, 2024.—
253 с.—(Развитие интеллекта школьников).—Систем.
требования: Adobe Reader XI ; экран 10".—Загл.
с титул. экрана.—Текст : электронный.
ISBN 978-5-93208-673-5
Абстракция, абстрагирование—одна из составляющих
мыслительного процесса творческой личности. Для развития
этого компонента мышления в процессе обучения информатике
есть дополнительные возможности, так как знание
абстрактных типов данных, умение оперировать ими—необходимый
элемент профессиональной культуры специалиста,
связанного с разработкой программных комплексов.
Для школьников, преподавателей информатики и студентов
младших курсов университетов. Книга может быть
использована при проведении факультативных занятий и при
углубленном изучении информатики.
УДК 519.85(023)
ББК 22.18
Деривативное издание на основе печатного аналога: Абстрактные
типы данных / С. М. Окулов.—М. : БИНОМ.
Лаборатория знаний, 2009.—250 с. : ил.—(Развитие интеллекта
школьников).—ISBN 978-5-94774-869-7.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-93208-673-5
© Лаборатория знаний, 2015
Стр.3
Оглавление
Предисловие ........................................... 5
Введение ............................................. 12
Глава 1. Матрицы ....................................... 15
1.1. Основные понятия ............................. 15
1.2. Операции над матрицами ....................... 18
1.3. Элементарные преобразования матриц ........... 27
Глава 2. Списки ......................................... 36
2.1. Основные понятия о ссылочном типе данных
(указателях) .................................. 36
2.2. Линейный список.............................. 39
2.3. Реализация линейного списка с использованием
массивов ..................................... 47
2.4. Двусвязные списки ............................ 51
Глава 3. Стек ............................................ 58
3.1. Основные понятия ............................. 58
3.2. Реализация стека через линейный список......... 59
3.3. Реализация стека с использованием массива ...... 60
3.4. Постфиксная, префиксная и инфикснаяформы
записи выражений............................. 66
3.5. Стек и рекурсивные процедуры .................. 73
Глава 4. Очередь......................................... 84
4.1. Определение и реализация очереди
с использованием списков ...................... 84
4.2. Реализация очереди с помощью массива .......... 86
Глава 5. Деревья......................................... 94
5.1. Основные понятия ............................. 94
5.2. Двоичные деревья поиска ....................... 96
5.3. Способы описания деревьев .................... 105
5.4. Оптимальные двоичные деревья поиска ......... 115
Стр.4
4
Оглавление
Глава 6. Множества .................................... 125
6.1. Основные понятия ............................ 125
6.2. Стандартные способы реализации множества .... 127
6.3. Объединение непересекающихся множеств ...... 129
6.4. Использование древовидных структур данных
в задаче объединения непересекающихся
множеств.................................... 134
6.5. Словари и хеширование ....................... 141
Глава 7. Очереди с приоритетами....................... 150
7.1. Двоичная куча и пирамидальная сортировка..... 150
7.2. Очередь с приоритетом на базе двоичной кучи .... 161
7.3. Биномиальная куча ........................... 165
Глава 8. Сбалансированные деревья. . .................. 178
8.1. АВЛ-деревья ................................. 178
8.2.«2–3»-деревья ................................ 189
8.3. Б-деревья .................................... 207
8.4. Красно-черные деревья ........................ 225
Стр.5