Структуры данных и алгоритмы (1021739), страница 101
Текст из файла (страница 101)
(1971). The Psychology of Computer Programming, VanNostrand, N. Y.116.Weiner, P. (1973). Linear pattern matching algorithms, Proc. IEEE FourteenthAnnual Symp. on Switching and Automata Theory, pp. 1-11.117.Wexelblat, R. L. (ed.) (1981). History of Programming Languages, AcademicPress, N. Y.118. Wiederhold, G.
(1982). Database Design, McGraw-Hill, New York.119. Williams, J. W. J. (1964). Algorithm 232: Heapsort, Comm. ACM 7:6, pp. 347-348.СПИСОК ЛИТЕРАТУРЫ373120. Wirth, N. (1973). Systematic Programming: An Introduction, Prentice-Hall,Englewood Cliffs, N. J. (Русский перевод: Вирт Н. Системное программирование:Введение. — М., "Мир", 1977.)121. Wirth, N. (1976). Algorithms + Data Structures = Programs, Prentice-Hall,Englewood Cliffs, N. J.
(Русский перевод: Вирт Н. Алгоритмы + структуры данных = программы. — М., "Мир", 1985.)122.Wulf, W. A., M. Shaw, P. Hilfinger, and L. Flon (1981). Fundamental Structuresof Computer Science, Addison-Wesley, Reading, Mass.123. Yao, A. C. (1975). An 0(|E| log log \V\) algorithm for finding minimum spanningtrees, Inf. Processing Letters 4:1, pp. 21-23.124.
Yao, A. C., and F. F. Yao (1976). The complexity of searching a random orderedtable, Proc. IEEE Seventeenth Annual Symp. on Foundations of Computer Science,pp. 173-177.125. Yourdon, E., and L. L. Constantine (1975). Structured Design, Yourdon, New York.374СПИСОК ЛИТЕРАТУРЫПредметный указательPrim, 204PRIORITYQUEUE, 124объявление, 128Algol, 18; 46Alphard, 36APL, 332; 360QQUEUE, 54; 122С, 18; 36CLU, 36RRussell, 36Deutsch — Schorr — Waite алгоритм, 338DICTIONARY, 105; 113diff, 167Dijkstra, 180Floyd, 183Fortran, 17; 28; 46sSET, 98; 101; 145; 154объявление, 102представление посредством деревадвоичного поиска, 139SETL, 332; 360SIMULA 67, 36Snobol, 332; 334; 360STACK, 50; 76КГТ1TREE, 75Trie, 146. См. Нагруженное деревоTRIENODE, 146операторы, 146определение, 147Kruskal, 206k-клика, 10k-связность, 212Lisp, 332; 333; 334; 360LIST, 12; 38; 78UUNIX, 30; 332MMAPPING, 59; 120; 172объявление, 120MESA, 36MFSET, 160; 174; 207быстрая реализация, 161объявления, 161реализация посредством деревьев, 164Morris, 357Pascal, 7; 54; 95; 110; 138; 204; 303; 315;331; 335; 345расширения, 30PL/1, 18; 26wWarshall, 186Абстрактный тип данных, 12; 14; 16; 37DICTIONARY, 105GRAPH, 15LIST, 12; 15; 38; 65MAPPING, 59; 60MFSET, 160PRIORITYQUEUE, 124QUEUE, 54SET, 15; 98STACK, 50TREE, 75TRIE, 146TRIENODE, 146для ориентированных графов, 178определение, 14; 16реализация, 16АВЛ-дерево, 173; 174Адресвозврата, 61; 338передачи, 356физический, 316Аккермана функция, 166Активационные записи, 61Алгоритмвнутренней сортировки, 220временная эффективность, 257Дейкстры, 180; 185;281Дейкстры, время выполнения, 183Дейкстры, обоснование, 181Дойча — Шорра — Уэйта, 338; 343жадный, 9; 280карманной сортировки, 240Крускала, 206; 281методы анализа, 257Морриса, 357нахождения максимальногопаросочетания, 216нахождения сильно связныхкомпонент, 195пирамидальной сортировки, 236поразрядной сортировки, 244Прима, 204пузырька, 221раскраски графа, 9случайной сортировки, 255сортировки вставками, 223сортировки посредством выбора, 224сортировки устойчивый, 254сортировки Шелла, 253Уоршелла, 186Флойда, 183Хаффмана, 85эффективность, 257Алгоритмы, 7формализация, 11чистки памяти, 336эвристические, 290Альфа-бета отсечение, 287Анализзакрытого хеширования, 116карманной сортировки, 241пирамидальной сортировки, 238поразрядной сортировки, 245потока данных, 98программ, 28псевдопрограмм, 28376рекурсивных программ, 258Асимптотические соотношения, 20АТД.
См. Абстрактный тип данныхАтом, 95;332Бит заполнения, 345Буфер, 304ВВ-дерево, 173поиск записей, 323удаление записей, 324Вектордвоичный, 101Вершинаграфа, 8ориетированного графа, 175стека, 50центральная, 187эксцентриситет, 187Вес дерева, 86Временная сложность, 19быстрой сортировки, 230методов сортировки, 225Временная эффективность, 257Время выполненияв наихудшем случае, 20в среднем, 20вычисление, 24измерение, 19оценка, 23программ, 19Время выполнения в среднембыстрой сортировки, 232Выделение памяти, 344Вызов процедур, 26Выраженияинфиксная форма, 74постфиксная (польская) форма, 74префиксная форма, 74Высота дерева, 70Вычислительные затраты, 7Глубинный остовный лес, 190; 209Граф, 8k-клика, 10k-связный, 212вершина, 8; 200глубинный остовный лес, 190; 209двудольный, 215ПРЕДМЕТНЫЙ УКАЗАТЕЛЬдвусвязный, 212задача раскраски, 8индуцированный подграф, 200матрица смежности, 202неориентированный, 200обход вершин, 209ориентированный.
См.Ориентированный графостовное дерево, 203остовное дерево минимальнойстоимости, 203полный, 218представления, 202дуть, 200ребро, 8; 200связная компонента, 200связный, 200списки смежности, 202точка сочленения, 212цикл, 201циклический, 201чередующейся цепи, 217дДвоичное дерево, 83Двоичный вектор, 101Дейкстры алгоритм, 180Дерево, 692-3. См. Дерево 2-3т-арное, 322АВЛ, 173В*-дерево, 328В-дерево, 322—330вес, 86выражений, 73высота, 70двоичного поиска, 322.
См. Дереводвоичного поискадвоичное, 83двоичное полное, 93двоичное, представление, 84двоичное, реализация, 90длина пути, 70игры, 283; 288метки узлов, 73нагруженное. См. Нагруженное деревонеупорядоченное, 70 'нулевое, 69определение, 69остовное, 203поиска внешнее, 322поиска разветвленное, 322помеченное, 73порядок узлов, 70представление посредством массива, 77ПРЕДМЕТНЫЙ УКАЗАТЕЛЬпредставление посредством списковсыновей, 78путь, 70решений,246сбалансированное, 150сбалансированное по высоте, 173свободное, 201способы обхода, 71упорядоченное, 70Хаффмана, 94частично упорядоченное, 125Дерево 2-3 (2-3 дерево), 150; 173; 272вставка элемента, 151операторы, 154тип данных узлов, 154удаление элемента, 153Дерево двоичного поиска, 138—150время выполнения операторов, 142определение, 138представление множеств, 139характеристическое свойство, 138эффективность, 144Динамическое программирование, 272;302Длина пути, 70Дойча — Шорра — Уэйта алгоритм, 338Дуги, 175дерева, 190обратные, 190поперечные, 190прямые, 190ЗадачаNP-полная, 9; 302коммивояжера, 282; 295конструирования кодов Хаффмана, 84наибольшей общейподпоследовательности, 167нахождения k-й порядковойстатистики, 250нахождения кратчайшего пути с однимисточником, 179нахождения максимальногопаросочетания, 215нахождения центра орграфа, 187о ранце, 61обхода доски шахматным конем, 283общая нахождения кратчайших путей,183разбиения на абзацы, 301размещения блоков, 298раскраски графа, 8сортировки, 20; 220триангуляции многоугольника, 275377умножения целых чисел, 269уплотнения памяти, 356эквивалентности, 160Запись, 17активационная, 61; 338закрепленная, 316ИИндексвторичный, 321плотный, 320разреженный, 319Инкапсуляция, 14; 29Исключение рекурсий, 62полное, 62ККаталана числа, 266Классы эквивалентности, 160Коды Хаффмана, 84Конечный автомат, 173Конкатенация списков, 240Кореньациклического орграфа, 198дерева, 69Крускала алгоритм, 206Курсор, 17Куча, 236; 331ЛЛексикографический порядок, 244Лес, 86глубинный остовный, 190; 209остовный, 190Лист дерева, 70мМатрицакратчайших путей, 188смежности, 176; 202Медиана, 250Методальфа-бета отсечения, 287близнецов, 351; 360близнецов k-ro порядка, 352близнецов с числами Фибоначчи, 352близнецов экспоненциального типа,351ветвей и границ, 288декомпозиции, 268; 271378линейный нахождения порядковыхстатистик, 251поиска в глубину, 188; 209поиска в ширину, 210последовательного сдвига регистра, 119сжатия путей, 165чередующихся цепей, 215Методыанализа алгоритмов, 257разработки алгоритмов, 268Минимальный эквивалентный орграф,199Многоканальное слияние, 309Множестваобъединение, 96пересечение, 96разность, 96слияние, 97Множество, 95атом, 95линейно упорядоченное, 95определение, 95представление посредством 2-3 дерева,157представление посредствомсбалансированного дерева, 150пустое, 96реализации, 101реализация посредством двоичноговектора, 101реализация посредством связанныхсписков, 102с операторами MERGE и FIND, 159универсальное, 101•шаблон, 96элемент, 95Мода, 255Морриса алгоритм, 357Мультисписки, 131нНагруженное дерево, 173представление узлов посредствомсписков, 148узлы, 146эффективность, 149Наибольшая общаяподпоследовательность, 167Наибольший общий делитель, 33НОП.
См. Наибольшая общаяподпоследовательностьНумерация глубинная, 191ПРЕДМЕТНЫЙ УКАЗАТЕЛЬоОбход неориентированного графа, 209Обход деревав обратном порядке, 71в порядке уровней, 93в прямом порядке, 71в симметричном (внутреннем)порядке, 71Объединение множеств, 96ОператорASSIGN, 59; 97; 120; 146COMPUTE, 59; 120CONCATENATE, 240CREATE!, 75DELETE, 38; 97; 140; 159; 236; 315DELETEMIN, 121; 140; 236; 309DEQUEUE, 54DIFFERENCE, 97EMPTY, 51; 54; 236ENQUEUE, 54EQUAL, 97FIND, 97; 159; 207FIRST, 15; 39; 178FRONT, 54GETNEW, 147INITIAL, 207INSERT, 15; 38; 97; 140; 154; 236; 309;315INTERSECTION, 97LABEL, 75LEFTMOST_CHILD, 75LOCATE, 38MAKENULL, 15; 38; 50; 54; 59; 75; 97;120; 147MAX, 97MEMBER, 97; 139MERGE, 97; 159; 207MIN, 97; 236MODIFY, 315NEXT, 15; 38; 178PARENT, 75POP, 50PREVIOUS, 38PRINTLIST, 39PUSH, 51RETRIEVE, 38; 315RIGHT_SIBLING, 75ROOT, 75SIZE, 15SPLIT, 167TOP, 50UNION, 15; 97VALUEOF, 146VERTEX, 178ПРЕДМЕТНЫЙ УКАЗАТЕЛЬОператоры2-3 дерева, 154АТД MFSET, 163дерева двоичного поиска, 139деревьев, 75для орграфов, 178множеств, 97отображений, 59; 120очередей, 53очереди с приоритетами, 124просмотра смежных вершин, 179работы с файлами, 315списков, 38стеков, 50узлов нагруженного дерева, 146; 147Организация выполнения процедур, 61Орграф.
См. Ориентированный графОриентированный граф, 175ациклический, 192ациклический, корень, 198вершина, 175длина пути, 175дуга, 175матрица смежности, 176минимальный эквивалентный, 199обратные дуги, 190обход, 188поиск в глубину, 188помеченный, 176поперечные дуги, 190проверка ацикличности, 193прямые дуги, 190путь, 175путь простой, 176редуцированный, 195сильная связность, 195сильно связная компонента, 195сильно связный, 195списки смежности, 177транзитивная редукция, 198центр, 187цикл, 176Остовное дерево, 203минимальной стоимости, 203Остовный лес, 190глубинный, 190Отношениелинейного порядка, 138многие-ко-многим, 129строгого включения, 193транзитивности, 95частичного порядка, 192эквивалентности, 159Отображениепустое, 59379реализация посредством хеширования,120Отображения, 58определение, 58реализация посредством массивов, 59реализация посредством списков, 60Очереди, 53реализация посредством указателей, 54реализация посредством циклическихмассивов, 55с двухсторонним доступом, 66Очередь с приоритетами, 121реализации, 123реализация посредством массива, 128реализация посредством частичноупорядоченных деревьев, 125пПамятьвнешняя, 303вторичная, 303динамическая, 332; 344оперативная, 303основная, 303управление блоками одинаковогоразмера, 335Паросочетание, 215максимальное, 215полное, 215Пересечение множеств, 96Подграф индуцированный, 200Поддерево, 69Поискв глубину, 209; 337; 340в мультисписке, 133в ширину, 210двоичный, 320интерполяционный, 329линейный, 319локальный, 294с возвратом, 283; 287Порядковые статистики, 250Правилопроизведений, 24сумм, 24Практика программирования, 28Преобразование Фурье, 302Прима алгоритм, 204Приоритет, 121Программаbfs, 210binsort, 241bubble, 24create, 91CREATE2, 82380dfs, 189; 337Dijkstra, 180EDIT, 51END, 40fact, 27findpivot, 228Floyd, 184greedy, 11heapsort, 238Huffman, 89INORDER, 72knapsack, 61Kruskal, 207LEFTMOST_CHILD, 79merge, 306; 348mergesort, 258move, 48mult, 270NPREORDER, 76nrdfs, 342partition, 230path, 186PREORDER, 72; 76Prim, 204propagate, 100PURGE, 39pushdown, 237quicksort, 230radixsort, 245rotate, 340same, 39search, 286select, 252Shellsort, 253spell, 145topsort, 194tuna, 106Warshall, 187выделения процессам машинноговремени, 123вычисления адреса передачи, 357вычисления вероятностей, 274вычисления транзитивного замыкания,187НОП, 169поиска в глубину, 189поиска с возвратом, 286форматирования текста, 33Программа-инструмент, 29Программыанализ, 28время выполнения, 19Псевдопрограммы, 28Псевдоязык, 7; 13; 28Путьв дереве, 70.I,ПРЕДМЕТНЫЙ УКАЗАТЕЛЬв ориентированном графе, 175особый, 180простой, 176; 200Разность множеств, 96Раскраска графа, 8Реализацияалгоритма быстрой сортировки, 235двоичных деревьев с помощьюуказателей, 90деревьев, 77операторов деревьев, 80операторов для орграфов, 179операторов множеств, 102; 103операторов отображений, 59; 121операторов очередей, 54операторов очереди с приоритетами,124; 128операторов словарей, 107; 110очередей, 54очередей с приоритетами, 123словарей, 107стеков, 52частично упорядоченных деревьев, посредством массивов, 127Ребродерева, 209графа, 8обратное, 209Рекуррентное соотношение, 26; 259метод подстановки, 261общее решение, 262однородное решение, 263оценка решения, 260решения, 259частное решение, 263Рекурсивные процедуры, 61исключение, 62Решениеглобально-оптимальное, 295локально-оптимальное, 281; 295оптимальное, 281Сборка мусора, 334Свойство ОДМС, 203Сжатие путей, 165Сильная связность, 195Символыстирающие, 51убийцы,51Слияние множеств, 97ПРЕДМЕТНЫЙ УКАЗАТЕЛЬСловари, 105реализация, 107реализация посредством закрытогохеширования, 113реализация посредством массива, 107реализация посредством открытогохеширования, 110Сортировка, 220алгоритм пузырька, 221быстрая, 227быстрая, вариант, 250внешняя, 220; 305; 330внутренняя, 220вставками, 223карманная, 239карманная двухэтапная, 243многофазная, 310; 330множеств с большими значениямиключей, 242пирамидальная, 236поразрядная, 244посредством выбора, 224слиянием, 305случайная, 255слянием многоканальная, 310слянием, ускорение, 308топологическая, 194; 328Шелла, 253Списки, 37дважды связные, 49однонаправленные, 43реализация, 40реализация посредством курсоров, 46реализация посредством массивов, 40реализация посредством указателей, 42связанные, 42; 102смежности, 177; 202сравнение реализаций, 45Стек, 50; 61; 66; 76вершина, 50реализация посредством массива, 52Степень узла, 93Стратегияпервый подходящий, 350самый подходящий, 350Структуры данных, 16двойные, 134сложных множеств, 129Суммирование по модулю 2, 119Схемас четырьмя буферами, 313с шестью входными буферами, 312Счетчикконтрольный, 336левых близнецов, 354размера блока, 344ссылок, 336Тип данных, 16Точка сочленения графа, 212Транзитивная редукция, 198Транзитивное замыкание, 186матрицы смежности, 186отношения частичного порядка, 193Треугольник Паскаля, 300Триангуляция, 275минимальная, 275УУзел дерева, 69высота, 70глубина, 70истинный потомок, 70истинный предок, 70лист, 70потомок, 70предок, 70родитель, 69степень, 93сыновья, 69Указатель, 17nil, 42Уоршелла алгоритм, 186Уплотнение памяти, 355Управление памятью, 331; 344ФФайл, 17индексированный, 319хешированный, 317Фибоначчи числа, 310; 352Фильтр, 29Флойда алгоритм, 183Фрагментация, 334; 345ФункцияАккермана, 166выигрыша, 285мультипликативная, 263приоритета, 121управляющая, 263Ханойские башни, 268Хаффмана коды, 84Хеширование, 108; 317закрытое (внутреннее), 109; 112закрытое, анализ, 116линейное, 112открытое (внешнее), 109повторное, 112разрешение коллизий, 112; 118; 136сегменты, 109таблица сегментов, 109хеш-значение, 109хеш-функция, 109; 118; 318эффективность, 114Хеш-таблица, 136; 144; 149реструктуризация, 120Хеш-функция, 109; 118; 318ЦЦентр орграфа, 187Цепь чередующаяся, 215Цикл, 176базовый, 218гамильтонов, 282Циклические массивы, 55Частично упорядоченное дерево, 144; 236ЧислаКаталана, 266Фибоначчи, 310; 352Чистка памяти, 334эЭвристические решения, 9Эксцентриситет вершины, 187Элемент опорный, 227Эффективность алгоритмов, 257ЯЯчейка, 16; 332382ПРЕДМЕТНЫЙ УКАЗАТЕЛЬАльфред В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
