Adam Drozdek Donald L. Simon

STRUKTURY DANYCH
W JĘZYKU
C

Bognie i Lei,
naszym żonom i przyjaciółkom

z angielskiego przełożył Adam Malinowski
Instytut Informatyki Uniwersytetu Warszawskiego

Wydawnictwa
Naukowo-Techniczne
Warszawa

Dane o oryginale
Data Structures In C
Adam Drozdek, Donald L. Simon
Duquesne University

COPYRIGHT © 1995 by PWS Publishing Company,
A Diyjsion of International Thomson Publishing Inc.

ALL RIGHTS RESERVED. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, or any Information storage and retrieval system, without permission, in writing, from the Publisher.

Redaktor: Ewa Zdanowicz
Opracowanie techniczne: Ewa Eckhardt
Przygotowanie do druku : Marta Jęczeń, Anna Szeląg
Projekt okładki i stron tytułowych: Ewa Bohusz-Rubaszewska

Copyright © for the Polish edition
by Wydawnictwa Naukowo-Techniczne
Warszawa 1996

Utwór w całości ani we fragmentach nie może być powielany ani rozpowszechniany za pomocą urządzeń elektronicznych, mechanicznych, kopiujących, nagrywających i innych bez pisemnej zgody posiadacza praw autorskich.

Adres poczty elektronicznej: [e-mail]
Ali Rights Reserved Printed in Poland
ISBN-83-204-1981-6


Spis treści

Przedmowa do polskiego wydania 11
Przedmowa 13

1. Projektowanie programu w języku C 17
1.1. Projektowanie zstępujące 17
1.2. Projektowanie wstępujące: maszyny wirtualne 19
1.3. Projektowanie do wielokrotnego użytku: oddzielna kompilacja 20
1.4. Abstrakcyjne typy danych 22
1.5. Ćwiczenia 33

2. Projektowanie algorytmu 35
2.1. Algorytmy zachłanne 35
2.2. Algorytmy oparte na strategii "dziel i zwyciężaj" 36
2.3. Algorytmy oparte na programowaniu dynamicznym 38
2.4. Algorytmy z powrotami 41
2.5. Ćwiczenia 45

3. Poprawność programu 47
3.1. Wprowadzenie 47
3.2. Warunki wstępne i końcowe 47
3.3. Niezmienniki pętli 50
3.3.1. Dowodzenie niezmienników 52
3.3.2. Najczęstsze niezmienniki pętli 55
3.3.3. Przetwarzanie tablic 58
3.4. Problem stopu 59
3.5. Przykład: wyszukiwanie binarne 60
3.6. Uwagi końcowe 63
#6

4. Analiza złożoności 66
4.1. Złożoność obliczeniowa i asymptotyczna 66
4.2. Notacja "wielkie O" 67
4.3. Własności notacji "wielkie O" 70
4.4. Notacje Q i 0 71
4.5. Możliwe problemy 72
4.6. Przykłady rzędów złożoności 73
4.7. Znajdowanie złożoności asymptotycznej: przykłady 75
4.8. Ćwiczenia 77

5. Dynamiczne przydzielanie pamięci 79
5.1. Listy 79
5.1.1. Listy dwukierunkowe 86
5.1.2. Listy cykliczne 87
5.2. Tablice rzadkie 89
5.3. Przykład: zarządzanie biblioteką 93
5.4. Ćwiczenia 101
5.5. Zadania programistyczne 101

6. Stosy i kolejki 103
6.1. Stosy 103
6.2. Kolejki 110
6.3. Kolejki priorytetowe 115
6.4. Przykład: płatek śniegu von Kocha 116
6.5. Ćwiczenia 121
6.6. Zadania programistyczne 122

7. Rekursja 125
7.1. Definicje rekurencyjne 125
7.2. Wywołania funkcji i realizacja rekursji 128
7.3. "Anatomia" wywołania rekurencyjnego 130
7.4. Rekursja końcowa 134
7.5. Rekursja niekońcowa 136
7.6. Rekursja pośrednia 140
7.7. Rekursja zagnieżdżona 143
7.8. Nadużywanie rekursji 143
7.9. Metoda powrotów 147
7.10. Uwagi końcowe 154
7.11. Przykład: interpretator 155
7.12. Ćwiczenia 163
7.13. Zadania programistyczne 165
#7

8. Drzewa binarne 168
8.1. Drzewa, drzewa binarne i drzewa poszukiwań binarnych 168
8.2. Realizacja drzew binarnych 168
8.3. Wyszukiwanie w drzewie poszukiwań binarnych 173
8.4. Przechodzenie drzewa 177
8.4.1. Przechodzenie wszerz 178
8.4.2. Przechodzenie w głąb 178
8.4.3. Przechodzenie w głąb bez użycia stosu 186
8.5. Wstawianie 192
8.6. Usuwanie 198
8.6.1. Pierwsze rozwiÄ…zanie 199
8.6.2. Drugie rozwiÄ…zanie 202
8.7. Równoważenie drzewa 204
8.7.1. Algorytm DSW 208
8.7.2. Drzewa A VL 211
8.8. SamokorygujÄ…ce siÄ™ drzewa 216
8.8.1. SamoorganizujÄ…ce siÄ™ drzewa 217
8.8.2. Rozchylanie 218
8.9. Kopce 221
8.10. Notacja polska i drzewa wyrażeń 226
8.10.1. Operacje na drzewach wyrażeń 228
8.11. Przykład: obliczanie częstości występowania słów 231
8.12. Ćwiczenia 236
8.13. Zadania programistyczne 239

9. Drzewa wyższych rzędów 245
9.1. Rodzina B-drzew 246
9.1.1. B-drzewa 247
9.1.2. B^*-drzewa 258
9.1.3. B^+-drzewa 260
9.1.4. Prefiksowe B^+-drzewa 262
9.1.5. Drzewa bitowe 264
9.1.6. R-drzewa 267
9.1.7. 2-4 drzewa 270
9.2. Drzewa trie 279
9.3. Uwagi końcowe 288
9.4. Przykład: sprawdzanie pisowni 289
9.5. Ćwiczenia 297
9.6. Zadania programistyczne 299

10. Grafy 304
10.1. Reprezentacja grafów 305
10.2. Przechodzenie grafu 306
#8
10.3. Spójność/dwuspójność 310
10.4. Grafy z wagami 315
10.4.1. Najkrótsze ścieżki 316
10.4.2. Minimalne drzewo rozpinajÄ…ce 319
10.5. Grafy skierowane 326
10.5.1. Przechodzenie grafu skierowanego 328
10.5.2. Najkrótsze ścieżki 333
10.6. Przykład: układanie harmonogramu zajęć 334
10.7. Ćwiczenia 346
10.8. Zadania programistyczne 347

11. Sortowanie 349
11.1. Elementarne algorytmy sortowania 351
11.1.1. Sortowanie przez wstawianie 351
11.1.2. Sortowanie przez wybieranie 356
11.1.3. Sortowanie bÄ…belkowe 358
11.2. Drzewa decyzyjne 364
11.3. Efektywne algorytmy sortowania 367
11.3.1. Sortowanie metodÄ… Shella 367
11.3.2. Sortowanie przez kopcowanie 372
11.3.3. Sortowanie szybkie 379
11.3.4. Sortowanie przez scalanie 388
11.3.5. Sortowanie pozycyjne 391
11.4. Uwagi końcowe 397
11.5. Przykład: dodawanie wielomianów 399
11.6. Ćwiczenia 406
11.7. Zadania programistyczne 408

12. Mieszanie 412
12.1. Funkcje mieszajÄ…ce 413
12.1.1. Dzielenie 413
12.1.2. Składanie 414
12.1.3. Funkcja "środek kwadratu" 414
12.1.4. Wycinanie 415
12.1.5. Zamiana podstawy 415
12.2. RozwiÄ…zywanie problemu kolizji 415
12.2.1. Adresowanie otwarte 416
12.2.2. Metoda łańcuchowa 422
12.2.3. Adresowanie kubełkowe 425
12.3. Usuwanie 426
12.4. Doskonałe funkcje mieszające 427
12.4.1. Metoda Cichelliego 428
12.4.2. Algorytm FHCD 431
#9
12.5. Funkcje mieszające dla plików rozszerzalnych 434
12.5.1. Mieszanie przedłużalne 434
12.5.2. Mieszanie liniowe 437
12.6. Przykład: mieszanie z użyciem kubełków 440
12.7. Ćwiczenia 447
12.8. Zadania programistyczne 448

13. Kompresja danych 451
13.1. Wymagania dotyczÄ…ce kompresji danych 451
13.2. Metoda Huffmana 453
13.2.1. Adaptacyjne kody Huffmana 463
13.3. Metoda Shannona-Fano 467
13.4. Kodowanie długości serii 469
13.5. Metoda Ziva-Lempela 471
13.6. Przykład: metoda Huffmana z kodowaniem długości serii 474
13.7. Ćwiczenia 483
13.8. Zadania programistyczne 485

14. Zarządzanie pamięcią 487
14.1. Metody dopasowywania sekwencyjnego 488
14.2. Metody niesekwencyjne 490
14.2.1. Systemy par 492
14.3. Odśmiecanie 500
14.3.1. Metoda "zaznacz-i-usuń" 501
14.3.2. Metody kopiowania 509
14.3.3. Odśmiecanie krokowe 510
14.4. Uwagi końcowe 519
14.5. Przykład: odśmiecanie "w miejscu" 520
14.6. Ćwiczenia 525
14.7. Zadania programistyczne 527

DODATEK A. Obliczenia przybliżone 532
A.1. Szereg harmoniczny 532
A.2. Oszacowanie funkcji lg(n!) 532
A.3. Średnia złożoność algorytmu auicksort 535
A.4. Średnia długość ścieżki w losowym drzewie binarnym 536

Skorowidz 538


Przedmowa do polskiego wydania

Jedną z podstawowych dziedzin informatyki jest dziedzina zajmująca się strukturami danych. Każdy informatyk musi mieć niezłe pojęcie o tej dziedzinie, by być w stanie zaprojektować jakiekolwiek oprogramowanie, następnie napisać program, przetestować go i uaktualnić zgodnie ze zmieniającymi się specyfikacjami. Język struktur danych jest językiem uniwersalnym. Używając tego narzędzia, ma się pewność, że komputer wykona zadanie w sposób jak najbardziej efektywny. Stąd też analiza struktur danych jest nierozerwalnie związana z analizą algorytmów.
Pisząc niniejszą książkę, postawiliśmy sobie dwa zadania. Po pierwsze, chodziło nam o to, żeby służyła jako wprowadzenie do dziedziny struktur danych, a pomyślana jako podręcznik była przydatna wykładowcom i studentom. Założyliśmy przy tym, że Czytelnik zna język C. Po drugie, pragnęliśmy przedstawić - do pewnego przynajmniej stopnia - aktualne dokonania w tej dziedzinie, przy czym opieraliśmy się na wynikach badań opublikowanych w pismach specjalistycznych. Umożliwi to Czytelnikowi zorientowanie się, jak szybko zachodzą zmiany w tej dziedzinie i być może zachęci do rozwijania pewnych aspektów struktur danych.
Jesteśmy niezmiernie zadowoleni, że książka ta zostaje udostępniona polskiemu Czytelnikowi, za co pragniemy bardzo podziękować Wydawnictwom Naukowo-Technicznym i Tłumaczowi. Jesteśmy również zainteresowani opinią Czytelników o książce, sposobie prezentacji materiału, programach itp. Będziemy wdzięczni za przesłanie nam tych opinii pod adresem [e-mail] lub [e-mail] (jeśli chodzi o pierwszy z tych adresów, opinie mogą być kierowane w języku polskim).
Pragniemy też wspomnieć, że do programów zawartych w tej książce można dotrzeć, używając polecenia gopher [e-mail] lub polecenia gopher:/[e-mail].

Adam Drozdek Donald Simon


Przedmowa

Język C został opracowany z myślą o tworzeniu systemów operacyjnych i zarządzaniu nimi. Szybko jednak znaleziono również inne jego zastosowania. W tej książce pokazujemy, że używanie języka C do nauki struktur danych ma wiele niezaprzeczalnych zalet, a dla uczestników zaawansowanego kursu struktur danych realizowanie zadań programistycznych w C nie wymaga większego wysiłku niż pisanie ich w Pascalu czy Moduli-2.
Swój sukces język C zawdzięcza sile wyrazu, elastyczności i efektywności. W miarę jak zyskuje on rosnącą popularność w zastosowaniach przemysłowych i akademickich jako znakomity język programowania, staje się również coraz bardziej przydatny do nauki struktur danych. Fakt powszechnego stosowania języka C w programowaniu systemów użytkowych i wspomniane powyżej zalety tego języka stanowią dobre uzasadnienie używania C do nauczania na kursie struktur danych i algorytmów.
Większość rozdziałów zawiera rozbudowane przykłady, które wybraliśmy z różnych dziedzin informatyki, takich jak grafika, interpretatory, obliczenia symboliczne czy przetwarzanie plików, aby uwidocznić szeroki zakres zastosowań omawianych tematów.
Krótkie i dłuższe przykłady napisane w języku C ilustrują praktyczne znaczenie struktur danych. Analiza teoretyczna jest jednak niemniej istotna. Z tego powodu prezentacja algorytmów jest połączona z analizą ich złożoności i poprawności.
Dużo uwagi poświęcamy omówieniu rekursji, ponieważ zrozumienie jej mechanizmu sprawia często kłopoty. Nasze doświadczenie wykazało, że najlepiej objaśniać rekursję, rozważając zmiany zachodzące na stosie programu podczas jego wykonywania. Niełatwo na przykład pojąć zadziwiająco krótką procedurę przechodzenia drzewa, jeśli nie będzie wyjaśnione, co dzieje się na stosie w czasie pracy wykonywanej przez system. Trzymanie się z dala od systemu i ograniczanie się do czysto teoretycznych aspektów przy omawianiu struktur danych i algorytmów nie musi być wcale dobrym pomysłem.
Warto wspomnieć o umieszczeniu w książce rozbudowanego przykładu z użyciem grafiki, fraktala zwanego płatkiem śniegu von Kocha. O ile nam wiadomo, żaden z dotychczas napisanych podręczników struktur danych nie zawiera przykładów
#14
z grafiki. Książka zawiera także obszerne rozdziały dotyczące kompresji danych i zarządzania pamięcią.
W rozdziałach 1-9 przedstawiamy wiele rozmaitych struktur danych i działających na nich algorytmów. Opis każdego algorytmu jest uzupełniony analizą jego efektywności i sugestiami możliwych-ulepszeń.

=> Rozdział 1 jest poświęcony metodom dobrego projektowania programu, w tym użyciu abstrakcyjnych typów danych.
=> Rozdział 2 zawiera omówienie różnych typów algorytmów w kontekście struktur danych.
=> Rozdział 3 dostarcza czytelnikowi aparatu matematycznego niezbędnego do poznawania struktur danych.
=> Rozdział 4 dotyczy notacji stosowanej przy szacowaniu złożoności algorytmów.
=> Rozdział 5 zawiera wprowadzenie do problematyki dynamicznego przydzielania pamięci i wykorzystania wskaźników.
=> Rozdział 6 jest poświęcony stosom i kolejkom oraz ich zastosowaniom.
=> Rozdział 7 zawiera szczegółowe omówienie różnych typów rekursji i dokładną analizę wywołania rekurencyjnego.
=> Rozdział 8 dotyczy drzew binarnych, ich implementacji, przechodzenia i wyszukiwania, a także drzew zrównoważonych.
=> Rozdział 9 umożliwia poznanie ogólniejszych drzew, takich jak drzewa Trie, 2-4 drzewa i B-drzewa.
=> Rozdział 10 jest poświęcony grafom.

W rozdziałach 11-14 ukazujemy rozmaite zastosowania struktur danych wprowadzonych we wcześniejszych rozdziałach. W każdym rozważanym problemie podkreślamy aspekt wykorzystania struktur danych.

=> Rozdział 11 zawiera szczegółową analizę sortowania, przy uwzględnieniu kilku elementarnych i nieelementarnych metod.
=> Rozdział 12 dotyczy jednej z najważniejszych dziedzin w zakresie wyszukiwania: mieszania. Przedstawione są tu rozmaite metody mieszania, przy czym główny nacisk jest położony na zastosowanie struktur danych.
=> Rozdział 13 jest poświęcony algorytmom i strukturom służącym do kompresji danych.
=> Rozdział 14 zawiera opis różnych metod i struktur danych służących do zarządzania pamięcią.
=> W dodatku A jest omówiona bardziej szczegółowo notacja "wielkie O".

Materiał przedstawiony w każdym rozdziale jest zilustrowany odpowiednimi rysunkami i tabelami. W wielu rozdziałach znajdują się rozbudowane przykłady, w których są wykorzystane elementy omawiane w tekście. Wszystkie przykłady zostały przetestowane z użyciem kompilatora gcc na stacji roboczej Sun IPX. Wyjątek stanowi
15
przykład płatka śniegu von Kocha, uruchomiony na komputerze PC za pomocą Turbo C. Na końcu rozdziałów są zamieszczone zadania o różnym stopniu trudności, czasami także zadania programistyczne. Ponadto w każdym rozdziale jest podany wykaz właściwej literatury.

Chcielibyśmy podziękować wielu osobom, które swoimi komentarzami i radami pomogły nam w ulepszeniu tej książki. Należą do nich: David Hemmendinger (Union College) i recenzenci
Richard J. Botting California State University
Patty Brayton Oklahoma City University
Ananda Gunawardena University of Houston
Janet Hartman United States Air F orce Academy
Sampath Kannon University of Arizona
Greg Leach Franklin University
Paul W. Ross Millersville University
Ali Salehnia University of South Dacota
Sharon Salveter Boston University
John B. Tappen University of Southern Colorado
Chcielibyśmy również podziękować naszym kolegom z Duauesne University, których zrozumienie i pomoc stworzyły atmosferę sprzyjającą pisaniu tej książki. Naszą wdzięczność zaskarbili sobie Patricia Adams, Sarah Lemałre (nasz redaktor) i Michael Sugarman, których nieoceniona pomoc i wsparcie umożliwiły nam doprowadzenie tej książki do jej obecnego stanu. Jednak odpowiedzialność za jej ostateczny kształt spoczywa na nas, będziemy więc wdzięczni Czytelnikom za wszelkie uwagi dotyczące niedociągnięć i braków.

Adam Drozdek Donald Simon