Навигация

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаKlein S.T. Basic concepts in data structures. - Cambridge; New York: Cambridge university press, 2016. - xii, 220 p.: ill., tab. - Ind.: p.217-220. - ISBN 978-1-107-16127-6
Шифр: (И/З 973.2-К53) 02 (ВМИ)

 

Место хранения: 02 | Отделение ГПНТБ СО РАН | Новосибирск

Оглавление / Contents
 
   List of Background Concepts ................................. ix
   Preface ..................................................... xi

1  Why Data Structures? A Motivating Example .................... 1
   1.1  Boyer and Moore's Algorithm ............................. 3
   1.2  The Bad-Character Heuristic ............................. 4
   1.3  The Good-Suffix Heuristic ............................... 7
   Exercises ................................................... 12
2  Linear Lists ................................................ 14
   2.1  Managing Data Storage .................................. 14
   2.2  Queues ................................................. 16
   2.3  Stacks ................................................. 21
   2.4  Other Linear Lists ..................................... 28
   Exercises ................................................... 31
3  Graplis ..................................................... 33
   3.1  Extending the Relationships between Records ............ 33
   3.2  Graph Representations .................................. 38
   3.3  Graph Exploration ...................................... 40
   3.4  The Usefulness of Graphs ............................... 41
   Exercises ................................................... 47
4  Trees ....................................................... 50
   4.1  Allowing Multiple Successors ........................... 50
   4.2  General versus Binary Trees ............................ 52
   4.3  Binary Trees: Properties and Examples .................. 55
   4.4  Binary Search Trees .................................... 58
   Exercises ................................................... 64
5  AVL Trees ................................................... 65
   5.1  Bounding the Depth of Trees ............................ 65
   5.2  Depth of AVL Trees ..................................... 66
   5.3  Insertions into AVL Trees .............................. 71
   5.4  Deletions from AVL Trees ............................... 77
   5.5  Alternatives ........................................... 80
   Exercises ................................................... 80
6  B-Trees ..................................................... 83
   6.1  Higher-Order Search Trees .............................. 83
   6.2  Definition of B-Trees .................................. 85
   6.3  Insertion into B-Trees ................................. 86
   6.4  Deletions from B-Trees ................................. 90
   6.5  Variants ............................................... 92
   Exercises ................................................... 99
7  Heaps ...................................................... 101
   7.1  Priority Queues ....................................... 101
   7.2  Definition and Updates ................................ 102
   7.3  Array Implementation of Heaps ......................... 105
   7.4  Construction of Heaps ................................. 106
   7.5  Heapsort .............................................. 110
   Exercises .................................................. 112
8  Sets ....................................................... 114
   8.1  Representing a Set by a Bitmap ........................ 114
   8.2  Union-Find ............................................ 117
   Exercises .................................................. 125
9  Hash Tables ................................................ 127
   9.1  Calculating instead of Comparing ...................... 127
   9.2  Hash Functions ........................................ 129
   9.3  Handling Collisions ................................... 134
   9.4  Analysis of Uniform Hashing ........................... 140
   9.5  Deletions from Hash Tables ............................ 147
   9.6  Concluding Remarks .................................... 148
   Exercises .................................................. 150
10 Sorting .................................................... 152
   10.1 A Sequence of Sorting Algorithms ...................... 152
   10.2 Lower Bound on the Worst Case ......................... 156
   10.3 Lower Bound on the Average ............................ 160
   10.4 Quicksort ............................................. 166
   10.5 Finding the kth Largest Element ....................... 170
   Exercises .................................................. 177
11 Codes ...................................................... 178
   11.1 Representing the Data ................................. 178
   11.2 Compression Codes ..................................... 179
   11.3 Universal Codes ....................................... 189
   11.4 Error Correcting Codes ................................ 194
   11.5 Cryptographic Codes ................................... 199
   Exercises .................................................. 202
Appendix  Solutions to Selected Exercises ..................... 205
   Index ...................................................... 217


Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
 

[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск]
  Пожелания и письма: branch@gpntbsib.ru
© 1997-2024 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Mon Mar 4 17:23:28 2019. Размер: 7,361 bytes.
Посещение N 1055 c 05.03.2019