IDZ DO
IDZ DO
PRZYKŁADOWY ROZDZIAŁ
PRZYKŁADOWY ROZDZIAŁ
Język C. Wska niki.
SPIS TRE CI
SPIS TRE CI
Vademecum profesjonalisty
KATALOG KSIĄŻEK
KATALOG KSIĄŻEK
Autor: Kenneth A. Reek
Tłumaczenie: Paweł Gonera
KATALOG ONLINE
KATALOG ONLINE
ISBN: 83-7361-198-3
Tytuł oryginału: Pointers on C
ZAMÓW DRUKOWANY KATALOG
ZAMÓW DRUKOWANY KATALOG
Format: B5, stron: 544
Przykłady na ftp: 55 kB
TWÓJ KOSZYK
TWÓJ KOSZYK
Książka  Język C. Wska niki. Vademecum profesjonalisty przeznaczona jest dla
DODAJ DO KOSZYKA
DODAJ DO KOSZYKA
zaawansowanych studentów i profesjonalistów, zapewniając obszerne ródło informacji
dla tych, którzy potrzebują dogłębnego omówienia języka C. Dokładne wyja nienie
podstaw oraz przegląd zaawansowanych funkcji pozwala programistom skorzystać
CENNIK I INFORMACJE
CENNIK I INFORMACJE
z siły wska ników w języku C. Dokładny opis idiomów programowych oraz gruntowna
dyskusja zaawansowanych tematów powoduje, że książka jest nieocenionym
ZAMÓW INFORMACJE
ZAMÓW INFORMACJE
podręcznikiem i informatorem dla studentów i zawodowych programistów.
O NOWO CIACH
O NOWO CIACH
" Zawiera wszystko, co jest niezbędne do dogłębnego poznania języka C
ZAMÓW CENNIK " Dokładnie opisuje wska niki, ich składnię, techniki efektywnego użycia
ZAMÓW CENNIK
oraz często stosowane idiomy programistyczne, w których występują wska niki
" Porównuje różne metody implementacji często stosowanych abstrakcyjnych
typów danych
CZYTELNIA
CZYTELNIA
" Zawiera wskazówki na temat efektywno ci, przeno no ci i zagadnień inżynierii
FRAGMENTY KSIĄŻEK ONLINE
FRAGMENTY KSIĄŻEK ONLINE
programowania, jak również ostrzeżenia o często popełnianych błędach
" Oferuje prosty, konwersacyjny styl, jasno opisujący trudne tematy, zawiera wiele
ilustracji i diagramów pomagających z wizualizacji skomplikowanych zagadnień
" Opisuje wszystkie funkcje z biblioteki standardowej C.
O Autorze: Kenneth A. Reek jest Profesorem informatyki w Rochester Institute of
Technology i do wiadczonym programistą, który pracował w wielu firmach jako
konsultant. Książka ta powstała po dziewięciu latach prowadzenia seminariów
z programowania w C. Profesor Reek prowadził zajęcia na podstawowym i rednim
poziomie z systemów operacyjnych, telekomunikacji, sieci komputerowych, analizy
algorytmów i systemów przełączających.
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl



1.1. Wstąp ..............................................................................................................................19
1.1.1. Odstąpy i komentarze ............................................................................................22
1.1.2. Dyrektywy preprocesora........................................................................................23
1.1.3. Funkcja main .........................................................................................................24
1.1.4. Funkcja czytaj_zakresy_kolumn ...........................................................................27
1.1.5. Funkcja przeksztalc ...............................................................................................32
1.2. Inne możliwości..............................................................................................................35
1.3. Kompilacja......................................................................................................................35
1.4. Podsumowanie ................................................................................................................35
1.5. Podsumowanie ostrzeżeń................................................................................................36
1.6. Podsumowanie wskazówek ............................................................................................36
1.7. Pytania ............................................................................................................................37
1.8. Ćwiczenia........................................................................................................................37

2.1. Środowiska......................................................................................................................39
2.1.1. Translacja...............................................................................................................39
2.1.2. Wykonanie.............................................................................................................41
2.2. Zasady leksykalne...........................................................................................................42
2.2.1. Znaki......................................................................................................................42
2.2.2. Komentarze............................................................................................................44
2.2.3. Dowolna postać kodu z
ródłowego ........................................................................44
2.2.4. Identyfikatory ........................................................................................................45
2.2.5. Postać programu ....................................................................................................45
2.3. Styl programowania........................................................................................................46
2.4. Podsumowanie ................................................................................................................47
2.5. Podsumowanie ostrzeżeń................................................................................................48
2.6. Podsumowanie wskazówek ............................................................................................48
2.7. Pytania ............................................................................................................................48
2.8. Ćwiczenia........................................................................................................................50
n
3.1. Podstawowe typy danych................................................................................................51
3.1.1. Rodzina liczb całkowitych.....................................................................................51
3.1.2. Typy zmiennoprzecinkowe....................................................................................55
3.1.3. Wskaz
niki ..............................................................................................................56
3.2. Podstawowe deklaracje...................................................................................................58
3.2.1. Inicjalizacja............................................................................................................59
3.2.2. Deklarowanie prostych tablic ................................................................................59
6 Język C. Wskaz
niki. Vademecum profesjonalisty
3.2.3. Deklaracja wskaz
ników.........................................................................................60
3.2.4. Niejawne deklaracje ..............................................................................................61
3.3. Typedef ...........................................................................................................................61
3.4. Stałe ................................................................................................................................62
3.5. Zasiąg..............................................................................................................................63
3.5.1. Zasiąg ograniczony do bloku.................................................................................64
3.5.2. Zasiąg ograniczony do pliku..................................................................................65
3.5.3. Zasiąg ograniczony do prototypu ..........................................................................65
3.5.4. Zasiąg ograniczony do funkcji ..............................................................................65
3.6. Sposób konsolidacji ........................................................................................................66
3.7. Klasa zapisu ....................................................................................................................67
3.7.1. Inicjalizacja............................................................................................................69
3.8. Słowo kluczowe static ....................................................................................................69
3.9. Przykład zasiągu, rodzaju łączenia i klas zapisu...............................................................70
3.10. Podsumowanie ..............................................................................................................72
3.11. Podsumowanie ostrzeżeń..............................................................................................72
3.12. Podsumowanie wskazówek ..........................................................................................73
3.13. Pytania ..........................................................................................................................73
In u
4.1. Instrukcja pusta ...............................................................................................................77
4.2. Instrukcja wyrażenia .......................................................................................................77
4.3. Instrukcja bloku ..............................................................................................................78
4.4. Instrukcja if .....................................................................................................................79
4.5. Instrukcja while...............................................................................................................80
4.5.1. Instrukcje break i continue ....................................................................................80
4.5.2. Działanie pątli while..............................................................................................81
4.6. Instrukcja for...................................................................................................................82
4.6.1. Wykonanie pątli for...............................................................................................82
4.7. Instrukcja do ...................................................................................................................83
4.8. Instrukcja switch .............................................................................................................84
4.8.1. Instrukcja break w switch......................................................................................85
4.8.2. Wartości domyślne ................................................................................................86
4.8.3. Wykonanie instrukcji switch .................................................................................86
4.9. Instrukcja goto ................................................................................................................87
4.10. Podsumowanie ..............................................................................................................89
4.11. Podsumowanie ostrzeżeń..............................................................................................90
4.12. Podsumowanie wskazówek ..........................................................................................90
4.13. Pytania ..........................................................................................................................90
4.14. Ćwiczenia......................................................................................................................92
n
5.1. Operatory ........................................................................................................................95
5.1.1. Arytmetyka ............................................................................................................95
5.1.2. Przesuniącia...........................................................................................................95
5.1.3. Operatory bitowe ...................................................................................................97
5.1.4. Przypisania.............................................................................................................98
5.1.5. Operatory jednoargumentowe .............................................................................101
5.1.6. Operatory relacyjne .............................................................................................103
5.1.7. Operatory logiczne ..............................................................................................104
5.1.8. Operator warunkowy ...........................................................................................105
5.1.9. Operator przecinka ..............................................................................................105
5.1.10. Indeks, wywołanie funkcji i element struktury .................................................107
5.2. Wartości logiczne .........................................................................................................108
5.3. L-wartości i R-wartości ................................................................................................109
Spis treści 7
5.4. Obliczanie wyrażeń.......................................................................................................110
5.4.1. Niejawna konwersja typów .................................................................................110
5.4.2. Konwersje arytmetyczne .....................................................................................111
5.4.3. Właściwości operatorów......................................................................................112
5.4.4. Priorytety i kolejność wykonywania ...................................................................114
5.5. Podsumowanie ..............................................................................................................116
5.6. Podsumowanie ostrzeżeń..............................................................................................118
5.7. Podsumowanie wskazówek ..........................................................................................118
5.8. Pytania ..........................................................................................................................118
5.9. Ćwiczenia......................................................................................................................121
n
6.1. Pamiąć i adresy .............................................................................................................123
6.1.1. Adresy i zawartość...............................................................................................124
6.2. Wartości i ich typy........................................................................................................124
6.3. Zawartość zmiennej wskaz
nikowej ..............................................................................126
6.4. Operator dereferencji ....................................................................................................126
6.5. Niezainicjowane i nieprawidłowe wskaz
niki ...............................................................128
6.6. Wskaz
nik NULL...........................................................................................................129
6.7. Wskaz
niki, dereferencja i L-wartości ...........................................................................130
6.8. Wskaz
niki, dereferencja i zmienne...............................................................................131
6.9. Stałe wskaz
nikowe........................................................................................................131
6.10. Wskaz
niki do wskaz
ników .........................................................................................132
6.11. Operacje na wskaz
nikach............................................................................................133
6.12. Przykłady ....................................................................................................................138
6.13. Arytmetyka wskaz
ników ............................................................................................141
6.13.1. Operacje arytmetyczne ......................................................................................142
6.13.2. Operacje relacyjne .............................................................................................145
6.14. Podsumowanie ............................................................................................................146
6.15. Podsumowanie ostrzeżeń............................................................................................147
6.16. Podsumowanie wskazówek ........................................................................................147
6.17. Pytania ........................................................................................................................148
6.18. Ćwiczenia....................................................................................................................150
un
7.1. Definicja funkcji ...........................................................................................................153
7.1.1. Instrukcja return...................................................................................................154
7.2. Deklaracje funkcji.........................................................................................................155
7.2.1. Prototypy .............................................................................................................155
7.2.2. Domyślne założenia dla funkcji ..........................................................................158
7.3. Argumenty funkcji........................................................................................................158
7.4. ATD i czarne skrzynki..................................................................................................162
7.5. Rekurencja ....................................................................................................................164
7.5.1. Śledzenie funkcji rekurencyjnych .......................................................................166
7.5.2. Rekurencja a iteracja ...........................................................................................169
7.6. Zmienna lista argumentów............................................................................................172
7.6.1. Makra stdarg........................................................................................................173
7.6.2. Ograniczenia zmiennej listy argumentów ...........................................................174
7.7. Podsumowanie ..............................................................................................................175
7.8. Podsumowanie ostrzeżeń..............................................................................................176
7.9. Podsumowanie wskazówek ..........................................................................................176
7.10. Pytania ........................................................................................................................177
7.11. Ćwiczenia....................................................................................................................178
8Język C. Wskaz
niki. Vademecum profesjonalisty

8.1. Tablice jednowymiarowe..............................................................................................179
8.1.1. Nazwy tablic........................................................................................................179
8.1.2. Indeksy.................................................................................................................180
8.1.3. Wskaz
niki kontra indeksy ...................................................................................183
8.1.4. Efektywność wskaz
ników ...................................................................................184
8.1.5. Tablice i wskaz
niki..............................................................................................190
8.1.6. Nazwy tablic i argumenty funkcji .......................................................................190
8.1.7. Deklarowanie parametrów tablicowych ..............................................................192
8.1.8. Inicjalizacja..........................................................................................................192
8.1.9. Niekompletne inicjalizacje ..................................................................................193
8.1.10. Automatyczne określanie wielkości tablicy ......................................................194
8.1.11. Inicjalizacja tablicy znaków ..............................................................................194
8.2. Tablice wielowymiarowe..............................................................................................194
8.2.1. Kolejność zapisu..................................................................................................195
8.2.2. Nazwy tablic........................................................................................................196
8.2.3. Indeksy.................................................................................................................197
8.2.4. Wskaz
niki na tablice............................................................................................199
8.2.5. Tablice wielowymiarowe jako argumenty funkcji ..............................................200
8.2.6. Inicjalizacja..........................................................................................................201
8.2.7. Automatyczne określanie wielkości tablic ..........................................................204
8.3. Tablice wskaz
ników .....................................................................................................204
8.4. Podsumowanie ..............................................................................................................207
8.5. Podsumowanie ostrzeżeń..............................................................................................208
8.6. Podsumowanie wskazówek ..........................................................................................209
8.7. Pytania ..........................................................................................................................209
8.8. Ćwiczenia......................................................................................................................213
n
9.1. Ciągi znaków  podstawy ...........................................................................................219
9.2. Długość ciągu ...............................................................................................................219
9.3. Nieograniczone funkcje operujące na ciągach................................................................221
9.3.1. Kopiowanie ciągów .............................................................................................221
9.3.2. A
ączenie ciągów ..................................................................................................222
9.3.3. Wartość zwracana przez funkcją .........................................................................222
9.3.4. Porównywanie ciągów.........................................................................................223
9.4. Funkcje operujące na ciągach o ograniczonej długości..................................................223
9.5. Proste wyszukiwanie w ciągach ...................................................................................224
9.5.1. Wyszukiwanie znaków........................................................................................225
9.5.2. Wyszukiwanie dowolnego z kilku znaków .........................................................225
9.5.3. Wyszukiwanie podciągu......................................................................................225
9.6. Zaawansowane wyszukiwanie ciągów .........................................................................227
9.6.1. Wyszukiwanie przedrostków w ciągu .................................................................227
9.6.2. Wyszukiwanie tokenów.......................................................................................227
9.7. Komunikaty dotyczące błądów.....................................................................................229
9.8. Operacje na znakach .....................................................................................................229
9.8.1. Klasyfikacja znaków............................................................................................229
9.8.2. Transformacje znaków ........................................................................................230
9.9. Operacje na pamiąci......................................................................................................230
9.10. Podsumowanie ............................................................................................................232
9.11. Podsumowanie ostrzeżeń............................................................................................233
9.12. Podsumowanie wskazówek ........................................................................................233
9.13. Pytania ........................................................................................................................234
9.14. Ćwiczenia....................................................................................................................234
Spis treści 9
u u un
10.1. Podstawy struktur .......................................................................................................241
10.1.1. Deklaracje struktur ............................................................................................242
10.1.2. Składniki struktury ............................................................................................243
10.1.3. Bezpośredni dostąp do składników ...................................................................244
10.1.4. Pośredni dostąp do składników .........................................................................244
10.1.5. Struktury odwołujące sią do samych siebie.......................................................245
10.1.6. Niekompletne deklaracje ...................................................................................246
10.1.7. Inicjalizacja struktur ..........................................................................................246
10.2. Struktury, wskaz
niki i składniki .................................................................................247
10.2.1. Odwołanie poprzez wskaz
nik............................................................................248
10.2.2. Odwoływanie sią do struktury...........................................................................248
10.2.3. Odwoływanie sią do składników struktury .......................................................249
10.2.4. Odwoływanie sią do zagnieżdżonej struktury ...................................................251
10.2.5. Odwoływanie sią do składnika wskaz
nikowego ...............................................251
10.3. Sposób zapisu struktur ................................................................................................253
10.4. Struktury jako argumenty funkcji ...............................................................................254
10.5. Pola bitowe .................................................................................................................257
10.6. Unie.............................................................................................................................260
10.6.1. Rekordy z wariantami........................................................................................261
10.6.2. Inicjalizacja unii ................................................................................................262
10.7. Podsumowanie ............................................................................................................263
10.8. Podsumowanie ostrzeżeń............................................................................................264
10.9. Podsumowanie wskazówek ........................................................................................264
10.10. Pytania ......................................................................................................................264
10.11. Ćwiczenia..................................................................................................................267
n n n
11.1. Dlaczego korzystamy z dynamicznego przydzielania pamiąci ..................................271
11.2. Funkcje malloc i free ..................................................................................................271
11.3. Funkcje calloc i realloc ...............................................................................................273
11.4. Wykorzystanie dynamicznie przydzielanej pamiąci...................................................273
11.5. Cząste błądy pamiąci dynamicznej.............................................................................274
11.5.1. Wycieki pamiąci................................................................................................277
11.6. Przykłady przydzielania pamiąci ................................................................................277
11.7. Podsumowanie ............................................................................................................283
11.8. Podsumowanie ostrzeżeń............................................................................................283
11.9. Podsumowanie wskazówek ........................................................................................283
11.10. Pytania ......................................................................................................................284
11.11. Ćwiczenia..................................................................................................................285
n u u n
12.1. Listy ............................................................................................................................287
12.2. Lista jednokierunkowa................................................................................................287
12.2.1. Wstawianie wązłów do listy jednokierunkowej ................................................288
12.2.2. Inne operacje na listach .....................................................................................297
12.3. Lista dwukierunkowa..................................................................................................298
12.3.1. Wstawianie do listy dwukierunkowej................................................................298
12.3.2. Inne operacje na listach .....................................................................................306
12.4. Podsumowanie ............................................................................................................307
12.5. Podsumowanie ostrzeżeń............................................................................................307
12.6. Podsumowanie wskazówek ........................................................................................308
12.7. Pytania ........................................................................................................................308
12.8. Ćwiczenia....................................................................................................................308
10 Język C. Wskaz
niki. Vademecum profesjonalisty
n n n n n
13.1. Wiącej o wskaz
nikach do wskaz
ników ......................................................................311
13.2. Deklaracje zaawansowane ..........................................................................................313
13.3. Wskaz
niki do funkcji ..................................................................................................315
13.3.1. Funkcje wywołania zwrotnego..........................................................................316
13.3.2. Tablice skoków..................................................................................................319
13.4. Argumenty wiersza poleceń........................................................................................321
13.4.1. Przekazywanie argumentów wiersza poleceń ...................................................321
13.4.2. Przetwarzanie argumentów wiersza poleceń.....................................................323
13.5. Literały ciągów znaków..............................................................................................326
13.6. Podsumowanie ............................................................................................................328
13.7. Podsumowanie ostrzeżeń............................................................................................329
13.8. Podsumowanie wskazówek ........................................................................................329
13.9. Pytania ........................................................................................................................330
13.10. Ćwiczenia..................................................................................................................333

14.1. Symbole predefiniowane ............................................................................................337
14.2. #define ........................................................................................................................337
14.2.1. Makra.................................................................................................................339
14.2.2. Podstawianie za pomocą #define.......................................................................340
14.2.3. Makra kontra funkcje.........................................................................................341
14.2.4. Argumenty makr z efektami ubocznymi ...........................................................342
14.2.5. Konwencje nazewnictwa ...................................................................................343
14.2.6. #undef ................................................................................................................344
14.2.7. Definicje z wiersza poleceń...............................................................................345
14.3. Kompilacja warunkowa ..............................................................................................345
14.3.1. #if defined..........................................................................................................347
14.3.2. Dyrektywy zagnieżdżone ..................................................................................347
14.4. Dołączanie plików ......................................................................................................348
14.4.1. Dołączanie biblioteczne.....................................................................................349
14.4.2. Dołączanie lokalne ............................................................................................349
14.4.3. Zagnieżdżone dołączanie plików.......................................................................350
14.5. Inne dyrektywy ...........................................................................................................351
14.6. Podsumowanie ............................................................................................................352
14.7. Podsumowanie ostrzeżeń............................................................................................353
14.8. Podsumowanie wskazówek ........................................................................................354
14.9. Pytania ........................................................................................................................354
14.10. Ćwiczenia..................................................................................................................356
un
15.1. Raportowanie błądów .................................................................................................357
15.2. Przerywanie działania .................................................................................................358
15.3. Standardowa biblioteka wejścia-wyjścia ....................................................................358
15.4. Założenia wejścia-wyjścia ANSI................................................................................359
15.4.1 Strumienie...........................................................................................................359
15.4.2. Struktury FILE...................................................................................................361
15.4.3. Standardowe stałe wejścia-wyjścia ...................................................................361
15.5. Przegląd strumieniowego wejścia-wyjścia .................................................................362
15.6. Otwieranie strumieni...................................................................................................363
15.7. Zamykanie strumieni ..................................................................................................365
15.8. Znakowe wejście-wyjście ...........................................................................................366
15.8.1. Makra znakowego wejścia-wyjścia...................................................................367
15.8.2. Wycofywanie operacji znakowego wejścia-wyjścia .........................................368
15.9. Niesformatowane wierszowe wejście-wyjście ...........................................................369
Spis treści 11
15.10. Formatowane wierszowe wejście-wyjście................................................................371
15.10.1. Rodzina scanf ..................................................................................................371
15.10.2. Kody formatujące funkcji scanf ......................................................................371
15.10.3. Rodzina printf..................................................................................................376
15.10.4. Kody formatujące printf ..................................................................................376
15.11. Binarne wejście-wyjście ...........................................................................................380
15.12. Funkcje wyszukujące i opróżniające bufory.............................................................381
15.13. Zmiana buforowania .................................................................................................384
15.14. Funkcje obsługi błądów strumienia ..........................................................................385
15.15. Pliki tymczasowe ......................................................................................................385
15.16. Funkcje do manipulacji plikami ...............................................................................386
15.17. Podsumowanie ..........................................................................................................386
15.18. Podsumowanie ostrzeżeń..........................................................................................388
15.19. Podsumowanie wskazówek ......................................................................................389
15.20. Pytania ......................................................................................................................389
15.21. Ćwiczenia..................................................................................................................390
n
16.1. Funkcje typu całkowitego...........................................................................................395
16.1.1. Arytmetyka .......................................................................................395
16.1.2. Liczby losowe ..................................................................................396
16.1.3. Konwersja ciągów znaków ..............................................................397
16.2. Funkcje zmiennoprzecinkowe ....................................................................................398
16.2.1. Trygonometria ...................................................................................399
16.2.2. Funkcje hiperboliczne .......................................................................399
16.2.3. Funkcje logarytmiczne i wykładnicze ...............................................399
16.2.4. Reprezentacja zmiennoprzecinkowa .................................................400
16.2.5. Potągowanie ......................................................................................400
16.2.6. Podłoga, sufit, wartość bezwzglądna i reszta ....................................400
16.2.7. Konwersja ciągów znaków ..............................................................401
16.3. Funkcje daty i czasu....................................................................................................401
16.3.1. Czas procesora ...................................................................................401
16.3.2. Data i godzina ....................................................................................402
16.4. Skoki nielokalne ......................................................................................405
16.4.1. Przykład.............................................................................................................406
16.4.2. Kiedy używać nielokalnych skoków .................................................................408
16.5. Sygnały .......................................................................................................................408
16.5.1. Nazwy sygnałów .............................................................................408
16.5.2. Przetwarzanie sygnałów ..................................................................410
16.5.3. Obsługa sygnałów..............................................................................................411
16.6. Drukowanie list zmiennych argumentów .................................................413
16.7. Środowisko wykonania...............................................................................................413
16.7.1. Przerwanie działania ........................................................................413
16.7.2. Asercje .............................................................................................414
16.7.3. Środowisko .......................................................................................415
16.7.4. Wykonywanie poleceń systemowych ..............................................415
16.8. Sortowanie i wyszukiwanie .......................................................................415
16.9. Ustawienia miądzynarodowe......................................................................................418
16.9.1. Formatowanie numeryczne i monetarne .........................................419
16.9.2. Ciągi znaków i ustawienia regionalne .............................................421
16.9.3. Efekty zmiany ustawień regionalnych...............................................................422
16.10. Podsumowanie ..........................................................................................................422
16.11. Podsumowanie ostrzeżeń..........................................................................................424
16.12. Podsumowanie wskazówek ......................................................................................424
16.13. Pytania ......................................................................................................................425
16.14. Ćwiczenia..................................................................................................................426
12 Język C. Wskaz
niki. Vademecum profesjonalisty
n n h n h
17.1. Przydział pamiąci........................................................................................................429
17.2. Stosy............................................................................................................................430
17.2.1. Interfejs stosu.....................................................................................................430
17.2.2. Implementacja stosu ..........................................................................................430
17.3. Kolejki ........................................................................................................................438
17.3.1. Interfejs kolejki..................................................................................................439
17.3.2. Implementacja kolejki .......................................................................................440
17.4. Drzewa ........................................................................................................................444
17.4.1. Wstawianie wartości do uporządkowanego drzewa binarnego............................445
17.4.2. Usuwanie wartości z uporządkowanego drzewa binarnego ..............................445
17.4.3. Wyszukiwanie wartości w uporządkowanym drzewie binarnym ........................446
17.4.4. Przeglądanie drzewa..........................................................................................446
17.4.5. Interfejs uporządkowanego drzewa binarnego ..................................................448
17.4.6. Implementacja uporządkowanego drzewa binarnego........................................448
17.5. Usprawnienia implementacji ......................................................................................455
17.5.1. Utworzenie wiącej niż jednego stosu ................................................................455
17.5.2. Wykorzystywanie wiącej niż jednego typu.......................................................456
17.5.3. Konflikty nazw ..................................................................................................457
17.5.4. Standardowe biblioteki ATD.............................................................................457
17.6. Podsumowanie ............................................................................................................460
17.7. Podsumowanie ostrzeżeń............................................................................................461
17.8. Podsumowanie wskazówek ........................................................................................461
17.9. Pytania ........................................................................................................................462
17.10. Ćwiczenia..................................................................................................................463
n n
18.1. Określanie cech środowiska wykonania .....................................................................465
18.1.1. Program testowy................................................................................................465
18.1.2 Zmienne statyczne i inicjalizacja........................................................................468
18.1.3. Ramka stosu.......................................................................................................469
18.1.4. Zmienne register................................................................................................470
18.1.5. Długość identyfikatorów zewnątrznych ............................................................471
18.1.6. Określanie układu ramki stosu ..........................................................................472
18.1.7. Efekty uboczne wyrażeń....................................................................................477
18.2. Współpraca z kodem asemblera .................................................................................478
18.3. Efektywność działania ................................................................................................479
18.3.1. Poprawianie wydajności....................................................................................480
18.4. Podsumowanie ............................................................................................................482
18.5. Podsumowanie ostrzeżeń............................................................................................482
18.6. Podsumowanie wskazówek ........................................................................................483
18.7. Pytania ........................................................................................................................483
18.8. Ćwiczenia....................................................................................................................483
A n n


Rozdział 12.
n u u
n
A
ącząc ze sobą wskaz
niki i struktury, można tworzyć bardzo efektywne struktury danych.
W rozdziale tym przyjrzymy sią kilku technikom wykorzystania struktur i wskaz
ników.
Wiele czasu poświącimy strukturze nazywanej listą  nie tylko dlatego, że jest bardzo
użyteczna, ale również dlatego, że wiele z technik wykorzystywanych do manipulowania
listą można również stosować do innych struktur danych.

Jeżeli nie jesteś zaznajomiony z pojąciem listy, nakreślą krótkie wprowadzenie. Lista to
zbiór niezależnych struktur (cząsto nazywanych węzłami), zawierających dane. Poszcze-
gólne wązły na liście są połączone ze sobą za pomocą połączeń lub wskaz
ników. Program
odwołuje sią do wązłów listy podążając za wskaz
nikami. Zwykle wązły są tworzone
dynamicznie, choć czasami można spotkać sią z listą skonstruowaną z elementów tablicy
wązłów. Nawet w takim przypadku program przegląda listą podążając za wskaz
nikami.
n un
Na liście jednokierunkowej każdy wązeł zawiera wskaz
nik do nastąpnego wązła listy.
Pole wskaz
nikowe w ostatnim elemencie zawiera wartość , wskazując, że na liście
nie ma już wiącej wązłów. Aby pamiątać, w którym miejscu lista sią zaczyna, wykorzy-
stywany jest wskaz
nik nazywany korzeniem lub głową listy. Wskaz
nik korzenia wska-
zuje na pierwszy element listy. Zwróć uwagą, że korzeń nie zawiera żadnych danych.
Poniżej przedstawiono diagram listy jednokierunkowej.
288 Język C. Wskaz
niki. Vademecum profesjonalisty
Wązły z tego przykładu są strukturami utworzonymi na podstawie nastąpujących deklaracji.




W każdym z wązłów zapisywana jest jedna dana  liczba . Przedstawiona lista zawiera
trzy wązły. Jeżeli zaczniemy od korzenia i za wskaz
nikiem podążymy do pierwszego wązła,
możemy uzyskać dostąp do danych zapisanych w tym wąz
le. Podążając za wskaz
nikiem,
przechodzimy z pierwszego wązła do drugiego i uzyskujemy dostąp do jego danych. Na
koniec nastąpny wskaz
nik przenosi nas do ostatniego wązła. Wartość zero została wyko-
rzystana do pokazania wskaz
nika ; oznacza on, że na liście nie ma już wiącej wązłów.
Na diagramie wązły zostały umieszczone obok siebie w celu pokazania logicznego
uporządkowania zapewnianego przez połączenia. W rzeczywistości wązły mogą być roz-
siane po całej pamiąci. Dla programu przetwarzającego taką listą nie ma żadnej różnicy,
czy wązły sąsiadują ze sobą czy nie, ponieważ program zawsze korzysta z połączeń, aby
przejść z jednego wązła do drugiego.
Lista jednokierunkowa może być przeglądana od początku do końca dziąki podążaniu
za wskaz
nikami, ale nie można jej przeglądać wstecz. Inaczej mówiąc, gdy program
dojdzie do ostatniego wązła listy, jedyną możliwością cofniącia sią jest wykorzystanie
wskaz
nika korzenia. Oczywiście program może zapamiątać wskaz
nik do bieżącego wązła
przed przejściem do nastąpnego wązła, może nawet zapamiątywać wskaz
niki wskazujące
na kilka kolejnych wązłów. Jednak lista jest strukturą dynamiczną i może zwiąkszyć sią
do kilkuset lub kilku tysiący wązłów  nierealne jest wiąc zapamiątywanie wskaz
ników
do wszystkich poprzednich wązłów w liście.
Wązły przedstawionej listy są połączone w taki sposób, że wartości w wązłach są uporząd-
kowane w kolejności rosnącej. Takie uporządkowanie jest ważne w przypadku niektórych
aplikacji, na przykład dla porządkowania spotkań wzglądem czasu. Możliwe jest również
tworzenie listy nieuporządkowanej, jeżeli aplikacja nie wymaga uporządkowania.
n n un
W jaki sposób należy wstawiać nowy wązeł do uporządkowanej listy jednokierunkowej?
Załóżmy, że mamy nową wartość  12  i musimy wstawić ją do przedstawionej po-
wyżej listy. Pod wzglądem koncepcyjnnym zadanie jest proste: zaczynamy od początku
listy i podążamy za wskaz
nikami, aż znajdziemy pierwszy wązeł o wartości wiąkszej
niż 12. Wstawiamy wówczas nową wartość do listy przed znalezionym wązłem.
W praktyce algorytm jest bardziej interesujący. Przeglądamy listą i zatrzymujemy sią,
gdy osiągniemy wązeł z wartością 15  pierwszy, który jest wiąkszy od 12. Wiemy, że
nowa wartość musi być dodana do listy bezpośrednio przed tym wązłem, ale przed reali-
zacją tej operacji zmienione musi zostać pole wskaz
nikowe poprzedniego wązła; tym-
czasem my nie możemy sią cofnąć. Rozwiązaniem jest zapamiątywanie wskaz
nika do
poprzedniego wązła.
Teraz możemy zaprojektować funkcją wstawiającą wązeł do uporządkowanej listy jedno-
kierunkowej. W listingu 12.1 przedstawiamy pierwsze podejście do tego problemu.
Rozdział 12. Wykorzystanie struktur i wskaz
ników 289
n Wstawianie węzła do uporządkowanej listy jednokierunkowej  pierwsza próba (wstaw1.c)






































Funkcją tą wywołujemy w nastąpujący sposób:

Prześledz
my kod, aby sprawdzić, czy wartość 12 jest prawidłowo wstawiana do listy.
Na początek funkcja jest wywoływana z wartością zmiennej , która jest wskaz
ni-
kiem na pierwszy wązeł listy. Poniżej przedstawiono stan listy na początku wykonywania
funkcji:
290 Język C. Wskaz
niki. Vademecum profesjonalisty
Diagram ten nie zawiera zmiennej , ponieważ funkcja nie może sią do niej odwo-
ływać. Kopia jej wartości jest przekazana do funkcji jako parametr , ale funkcja nie
może odwoływać sią do . Teraz jest równe 5, czyli mniej niż 12
 wykonywane jest wiąc ciało pątli, w którym przesuwane są nasze wskaz
niki.
W chwili obecnej jest równe 10, wiąc ciało pątli jest wykonywane kolejny
raz, co daje nastąpujący wynik:
Teraz jest wiąksze od 12, wiąc pątla jest przerywana.
W tym momencie ważny staje sią wskaz
nik , ponieważ wskazuje na wązeł, który
musi zostać zmieniony, aby możliwe było dodanie nowej wartości. Na początek należy
jednak utworzyć nowy wązeł i zapisać w nim wartość. Nastąpny diagram pokazuje stan
listy po skopiowaniu wartości do nowego wązła.
Rozdział 12. Wykorzystanie struktur i wskaz
ników 291
Włączenie nowego wązła do listy wymaga wykonania dwóch kroków. Pierwszym jest:

co powoduje, że nowy wązeł wskazuje na wązeł bądący nastąpnym wązłem na liście 
pierwszym, którego wartość jest wiąksza niż 12. Po tej operacji lista wygląda nastąpująco:
Drugim krokiem jest zmiana wskaz
nika w poprzednim wąz
le  ostatnim o wartości
mniejszej niż 12  tak, aby wskazywał na nowy wązeł. Operacja ta jest wykonywana
przez instrukcją:

Wynikiem wykonania tego kroku jest:
292 Język C. Wskaz
niki. Vademecum profesjonalisty
Funkcja kończy sią, pozostawiając listą w nastąpującym stanie:
Rozpoczynając od wskaz
nika i podążając za wskaz
nikami, możemy sprawdzić,
że nowy wązeł został prawidłowo wstawiony.
u n un
Niestety funkcja wstawiająca jest nieprawidłowa. Spróbuj wstawić do listy wartość 20,
a zobaczysz, na czym polega problem; pętla przejdzie poza koniec listy i wykona
dereferencję wskaz
nika . Aby rozwiązać ten problem, musimy przed obliczeniem
sprawdzać, czy wskaz
nik jest różny od .

Nastąpny problem jest poważniejszy. Prześledz
zachowanie funkcji podczas wstawiania
do listy wartości 3. Co sią dzieje?
Aby wstawić element na początek listy, funkcja musi zmienić wskaz
nik . Funkcja
jednak nie może odwoływać sią do wartości . Najprostszym sposobem naprawienia
tego problemu jest zmiana zmiennej na zmienną globalną, dziąki czemu funkcja
wstawiająca mogłaby ją modyfikować. Niestety podejście to jest najgorszym sposobem
rozwiązania tego problemu, ponieważ funkcja mogłaby być używana tylko dla jednej listy.
Lepszym rozwiązaniem jest przekazywanie wskaz
nika do jako argumentu. Funkcja
mogłaby wykonywać dereferencją zarówno w celu pobrania wartości (wskaz
nika
do pierwszego elementu listy), jak i zapisywania nowej wartość wskaz
nika. Jaki powinien
być typ takiego parametru? Zmienna jest wskaz
nikiem na , wiąc parametr
powinien mieć typ : wskaz
nik do wskaz
nika na . Funkcja zamieszczona
w listingu 12.2 zawiera te modyfikacje. Funkcją tą należy wywoływać w nastąpujący
sposób:

n Wstawianie węzła do uporządkowanej listy jednokierunkowej  druga próba (wstaw2.c)




Rozdział 12. Wykorzystanie struktur i wskaz
ników 293











































Ta druga wersja zawiera kilka dodatkowych instrukcji:

Instrukcja ta jest niezbądna, ponieważ póz
niej możemy sprawdzić, czy nowa wartość
powinna być pierwszym wązłem na liście.

294 Język C. Wskaz
niki. Vademecum profesjonalisty
Wykorzystano tu dereferencją na argumencie bądącym wskaz
nikiem do korzenia, dziąki
czemu pobraliśmy wartość wskaz
nika  wskaz
nika do pierwszego wązła listy.
Na koniec funkcji dodane zostały instrukcje:




Sprawdzają one, czy nowa wartość powinna być włączona na początku listy. Jeżeli tak, za
pomocą dereferencji modyfikujemy wskaz
nik tak, aby pokazywał nowy wązeł.
Funkcja działa prawidłowo i w wielu jązykach programowania jest najlepszym możli-
wym rozwiązaniem. Jednak w C możemy zapisać ją jeszcze lepiej, ponieważ jązyk ten
posiada możliwość odczytu adresu (wskaz
nika) istniejącego obiektu.
un
Może sią wydawać, że wstawianie wązła na początku listy musi być specjalnym przypad-
kiem. Wskaz
nik, który musi być zmieniony w celu wstawienia pierwszego wązła, jest
wskaz
nikiem korzenia. Dla pozostałych wązłów korygowanym wskaz
nikiem jest pole
łączące z poprzedniego wązła. Te pozornie różne operacje są w rzeczywistości tym samym.
Kluczem do wyeliminowania tego specjalnego przypadku jest fakt, że każdy wązeł listy
posiada wskaz
nik, który na niego wskazuje. Dla pierwszego wązła jest to wskaz
nik ,
a dla pozostałych wązłów  pole łączące z poprzedniego wązła. Najważniejsze jest, że
istnieje wskaz
nik wskazujący na wązeł. To, czy wskaz
nik jest zapisany w wąz
le czy nie,
jest nieistotne.
Spójrzmy jeszcze raz na listą, aby wyjaśnić ten wniosek. Mamy tutaj pierwszy wązeł
i odpowiadający mu wskaz
nik.
Jeżeli nowa wartość jest wstawiana przed pierwszym wązłem, musi być zmieniony
odpowiedni wskaz
nik.
Tutaj mamy drugi wązeł i jego wskaz
nik.
Rozdział 12. Wykorzystanie struktur i wskaz
ników 295
Jeżeli nowa wartość jest wstawiana przed drugim wązłem, to ten wskaz
nik musi być
zmieniony. Zwróć uwagą, że zajmujemy sią tylko wskaz
nikami; zawartość wązła jest
w tym momencie nieistotna. Ten sam wzór powtarza sią dla każdego wązła listy.
Teraz spójrzmy na zmienioną funkcją, gdy rozpoczyna ona działanie. Poniżej przedsta-
wiono wszystkie zmienne bezpośrednio po pierwszym przypisaniu.
Mamy wskaz
nik do bieżącego wązła i wskaz
nik do połączenia wskazującego na bieżący
wązeł. Nie potrzebujemy niczego wiącej! Jeżeli wartość w bieżącym wąz
le jest wiąksza
niż nowa wartość, wskaz
nik wskazuje nam na pole połączeniowe, które musi
zostać zmienione, aby możliwe było włączenie nowego wązła do listy. Jeżeli wstawienie
w dowolne inne miejsce listy może być zrealizowane tak samo, specjalny przypadek znika.
Kluczem jest pokazana wcześniej relacja wskaz
nik-wązeł.
Przesuwając sią do nastąpnego wązła, zapamiątujemy  zamiast wskaz
nika na poprzedni
węzeł  wskaz
nik na połączenie, które wskazuje na nastąpny wązeł. Najłatwiej nary-
sować to na diagramie:
Zwróć uwagą, że nie wskazuje na wązeł, lecz na pole łączące w wąz
le. Ma
to kluczowe znaczenie dla uproszczenia funkcji wstawiającej, ale zależy od możliwości
uzyskania adresu pola łączącego z bieżącego wązła. W jązyku C operacja taka jest bardzo
prosta  realizuje ją wyrażenie . W listingu 12.3 zamieszczona została
ostateczna wersja naszej funkcji wstawiającej. Parametr jest teraz nazwany
, ponieważ wskazuje teraz na wiele różnych połączeń, nie tylko na korzeń.
Nie potrzebujemy już zmiennej , ponieważ nasz wskaz
nik na połączenie pozwala
na zlokalizowanie pola łączącego, wymagającego zmodyfikowania. Specjalny przypadek
na końcu funkcji już nie wystąpuje, ponieważ zawsze mamy wskaz
nik do pola połącze-
niowego, które należy zmodyfikować  zmieniamy wskaz
nik korzenia w identyczny
sposób, co pole łączące w wąz
le. Na koniec wreszcie dodana została deklaracja
dla zmiennej wskaz
nikowej, co powinno poprawić efektywność wynikowego kodu.
296 Język C. Wskaz
niki. Vademecum profesjonalisty
n Wstawianie węzła do uporządkowanej listy jednokierunkowej  wersja ostateczna (wstaw3.c)





































W pątli w tej końcowej wersji zastosowana została sztuczka z wbudowanym
przypisaniem do zmiennej . Poniżej przedstawiamy realizującą to samo zadanie,
choć nieco dłuższą pątlą.








Rozdział 12. Wykorzystanie struktur i wskaz
ników 297
Na początku wskaz
nik ustawiany jest na pierwszy wązeł na liście. Instrukcja
sprawdza, czy osiągnąliśmy koniec pątli. Jeżeli nie, sprawdza, czy jesteśmy w odpowied-
nim miejscu do wstawienia wązła. Jeżeli nie, wykonywane jest ciało pątli, w którym
wskaz
nik jest tak zmieniany, aby wskazywał na pole łączące w bieżącym
wąz
le, a wskaz
nik jest przesuwany do nastąpnego wązła.
Fakt, że ostatnia instrukcja w ciele pątli jest identyczna z instrukcją umieszczoną przed
pątlą, pozwala  uprościć program poprzez wbudowanie w wyrażenie przypisania
do wskaz
nika . W wyniku usuniącia nadmiarowego przypisania otrzymujemy bardziej
złożoną, ale i bardziej zwartą pątlą.
Wyeliminowanie specjalnego przypadku uprościło tę funkcję. Wystąpiły tu dwa
czynniki umożliwiające tę modyfikację. Pierwszym jest nasza zdolność do prawidłowej
interpretacji problemu. Jeżeli nie zidentyfikujemy wspólnych cech w pozornie różnych
operacjach, będziemy zmuszeni tworzyć dodatkowy kod dla specjalnych przypadków.
Często wiedza ta jest zdobywana po dłuższym czasie pracy z takimi strukturami
i po ich dogłębnym poznaniu. Drugim czynnikiem jest to, że język C zapewnia właściwe
narzędzia, pozwalające wykorzystać te wspólne cechy.
Ulepszona funkcja korzysta z zawartych w jązyku C możliwości odczytywania adresu
istniejącego obiektu. Podobnie jak wiele funkcji C, możliwość ta jest jednocześnie potążna
i niebezpieczna. W jązykach Modula i Pascal nie ma operatora  adres czegoś , wiąc jedyne
wskaz
niki, jakie w nich wystąpują, to wskaz
niki uzyskane poprzez dynamiczny przydział
pamiąci. Niemożliwe jest uzyskanie wskaz
nika do zwykłej zmiennej lub nawet do pola
dynamicznie utworzonej struktury. Niedozwolona jest arytmetyka wskaz
ników, nie ma
również sensu rzutowanie wskaz
ników jednego typu na inne. Ograniczenia te są wprowa-
dzone w celu zabezpieczenia przed popełnianiem przez programistów takich błądów, jak
indeksowanie poza obszarem tablicy czy generowanie wskaz
ników niewłaściwego typu.
W języku C występuje o wiele mniej ograniczeń dotyczących operacji na wskaz
nikach
 dzięki temu mogliśmy usprawnić naszą funkcję. Z drugiej strony programista C
musi o wiele bardziej uważać, aby uniknąć pomyłek przy stosowaniu wskaz
ników.
Filozofię języka Pascal dotyczącą stosowania wskaz
ników można podsumować
zdaniem:  Możesz się skaleczyć siekierą, więc jej nie dostaniesz . Filozofia C to raczej:
 Oto siekiera. Masz tu też inne rodzaje siekier. Powodzenia! . Dysponując takimi
narzędziami, programista C może łatwiej popaść w kłopoty niż programista Pascala.
Dobry programista C może jednak tworzyć mniejsze, efektywniejsze i łatwiejsze
do utrzymania programy niż jego koledzy korzystający z Moduli czy Pascala. Z tego
powodu język C jest tak popularny w branży i dlatego doświadczeni programiści C są
tak poszukiwani.
Inn n h
Aby lista jednokierunkowa była naprawdą użyteczna, niezbądne jest wykorzystywa-
nie wiąkszej liczby operacji, na przykład wyszukiwania i usuwania. Jednak algorytmy
tych operacji są proste i łatwe do zaimplementowania z wykorzystaniem technik poka-
zanych w funkcji wstawiającej. Napisanie tych funkcji pozostawiam Czytelnikowi jako
ćwiczenie.
298 Język C. Wskaz
niki. Vademecum profesjonalisty
u un
Alternatywą dla listy jednokierunkowej jest lista dwukierunkowa. W przypadku tej listy
każdy wązeł ma dwa wskaz
niki  jeden wskazuje na nastąpny wązeł listy, a drugi na
poprzedni wązeł. Wskaz
nik do poprzedniego wązła pozwala na przeglądanie listy w dowol-
nym kierunku. Na poniższym diagramie przedstawiono listą dwukierunkową.
Deklaracja typu wązła jest nastąpująca:





Korzeń ma teraz dwa wskaz
niki: jeden wskazuje na pierwszy wązeł listy, drugi natomiast
na ostatni. Te dwa wskaz
niki pozwalają nam na przeglądanie listy z dowolnego jej końca.
Możemy zadeklarować dwa wskaz
niki korzenia jako osobne zmienne, ale musielibyśmy
przekazywać oba te wskaz
niki do funkcji wstawiającej. Wygodniej jest zadeklarować
cały wązeł jako korzeń i nie wykorzystywać pól wartości. W naszym przykładzie technika
ta powoduje niepotrzebne zającie pamiąci tylko na jedną liczbą . Osobne wskaz
niki
mogą być lepsze w przypadku list zawierających duże pola wartości. Można również
wykorzystać pole wartości wązła korzenia do przechowywania danych o liście, na przy-
kład informacji o ilości wązłów w liście.
Pole wązła korzenia wskazuje na pierwszy wązeł na liście, natomiast pole
wskazuje na ostatni wązeł. Jeżeli lista jest pusta, oba te wskaz
niki przyjmują wartość .
Pole pierwszego wązła listy oraz pole ostatniego wązła również mają wartość
. Na liście uporządkowanej wązły są łączone w rosnącym porządku pól .
n u un
Tym razem zaprojektujemy funkcją wstawiającą wartość do uporządkowanej listy dwu-
kierunkowej. Funkcja wymaga dwóch argumentów: wskaz
nika do
wązła korzenia oraz wartości całkowitej.
Rozdział 12. Wykorzystanie struktur i wskaz
ników 299
Zaprojektowana wcześniej funkcja wstawiająca wązeł do listy pojedynczej pozwala na
wstawianie duplikatów do listy. W niektórych aplikacjach prawidłowym działaniem jest
niedodawanie duplikatów. Funkcja wstawi nową wartość tylko wtedy,
gdy nie ma jej jeszcze na liście.
Funkcją tą zaprojektujemy w sposób bardziej zdyscyplinowany. W czasie wstawiania
wartości do listy mogą wystąpić cztery przypadki:
Wartość bądzie musiała być wstawiona w środek listy.
Wartość bądzie musiała być wstawiona na początek listy.
Wartość bądzie musiała być wstawiona na koniec listy.
Wartość bądzie musiała być wstawiona zarówno na początek, jak i na koniec listy
(czyli wstawienie do pustej listy).
W każdym z przypadków zmodyfikowane bądą musiały być cztery wskaz
niki.
W przypadkach (1) i (2) pole nowego wązła musi wskazywać na nastąpny
wązeł listy, natomiast pole nastąpnego wązła musi wskazywać na nowy wązeł.
W przypadkach (3) i (4) pole nowego wązła musi mieć wartość ,
a pole wązła korzenia musi wskazywać na nowy wązeł.
W przypadkach (1) i (3) pole nowego wązła musi wskazywać na poprzedni
wązeł listy, a pole poprzedniego wązła musi wskazywać na nowy wązeł.
W przypadkach (2) i (4) pole nowego wązła musi mieć wartość , a pole
wązła korzenia musi wskazywać na nowy wązeł.
Jeżeli ten opis wydaje sią niejasny, pomóc powinna prosta implementacja przedstawiona
w listingu 12.4.
n Prosta funkcja wstawiająca węzeł do listy dwukierunkowej (dwu_wstaw1.c)



















300 Język C. Wskaz
niki. Vademecum profesjonalisty





















































Rozdział 12. Wykorzystanie struktur i wskaz
ników 301
Funkcja rozpoczyna sią od przypisania wskaz
nikowi wskaz
nika na wązeł korzenia.
Wskaz
nik zawsze wskazuje na wązeł po ; wskaz
niki te bądą przesuwane razem
aż do znalezienia miejsca, w którym pomiądzy nie bądzie wstawiony nowy wązeł. Pątla
sprawdza wartości w wąz
le , określając, czy została osiągniąta odpowiednia pozycja.
Jeżeli na liście zostanie znaleziona nowa wartość, funkcja po prostu kończy swoje działa-
nie. W przeciwnym przypadku pątla kończy sią na końcu listy lub gdy osiągniąta zostanie
właściwa pozycja do wstawiania. W obu tych przypadkach nowy wązeł powinien być
wstawiony po wąz
le wskazywanym przez . Zwróć uwagą, że pamiąć przeznaczona
na nowy wązeł nie jest przydzielana do czasu, gdy zostanie sprawdzone, że wartość
powinna być dodana do listy.
Przydzielenie nowego wązła na początku może powodować potencjalny wyciek pamiąci
w przypadku znalezienia podwójnych wartości.
Przedstawione cztery przypadki są implementowane osobno. Prześledz
my pierwszy,
dodając do listy wartość 12. Poniższy diagram pokazuje stan naszych zmiennych bez-
pośrednio po przerwaniu pątli .
Teraz przydzielany jest pierwszy wązeł. Po wykonaniu instrukcji:


lista bądzie wyglądać nastąpująco:
302 Język C. Wskaz
niki. Vademecum profesjonalisty
Kolejne instrukcje


pozwalają zakończyć dodawanie nowej wartości do listy:
Przeanalizuj kod, aby sprawdzić, czy pozostałe przypadki działają prawidłowo.
n un
Spostrzegawczy programista zauważy wiele podobieństw w grupach instrukcji
umieszczonych w zagnieżdżonych instrukcjach , a dobry programista będzie
zaniepokojony tymi powtórzeniami. Spróbujmy więc wyeliminować te powtórzenia,
korzystając z dwóch technik. Pierwsza jest nazywana przebudową instrukcji
(ang. factoring) i została pokazana na następującym przykładzie:










Zwróć uwagą, że instrukcje oraz są wykonywane niezależnie od tego,
czy wyrażenie jest spełnione czy nie. Wykonanie przed nie wpłynie na
test , wiąc oba przypisania mogą zostać wyjąte z instrukcji , tworząc prostsze, ale
identycznie działające instrukcje:






Rozdział 12. Wykorzystanie struktur i wskaz
ników 303
Należy uważać, aby nie wyciągać przed instrukcji, które zmieniają wynik testu.
Na przykład we fragmencie:








instrukcja nie może być wyjęta przed test, ponieważ zmieniłaby wynik porównania.
Przebudowa najbardziej zagnieżdżonej instrukcji z listingu 12.4 daje w wyniku kod
zamieszczony w listingu 12.5. Porównaj ten kod z poprzednią funkcją i przekonaj sią,
że działa on identycznie.
n Przebudowa instrukcji funkcji wstawiającej węzeł do listy dwukierunkowej (dwu_wstaw2.c)

































304 Język C. Wskaz
niki. Vademecum profesjonalisty
Drugą techniką upraszczania najłatwiej pokazać na przykładzie:




Chcemy tutaj nadać zmiennej wartość lub wartość , jeżeli na nic
nie wskazuje. Ale spójrz na instrukcją:

Jeżeli ma wartość różną od ,  tak jak poprzednio  otrzymuje
kopią tej wartości. Ale jeżeli ma wartość , pole otrzymuje kopią wartości
ze zmiennej , co daje ten sam efekt, co przypisanie stałej . Wyrażenie
to wykonuje to samo zadanie i oczywiście jest prostsze.
Kluczem do zastosowania tej techniki w kodzie z listingu 12.5 jest zidentyfikowanie
instrukcji wykonujących te same zadania, chociaż wyglądają one inaczej, a nastąpnie
ich odpowiednie przepisanie. Jako pierwsze możemy zmienić pierwsze instrukcje przy-
padków (3) i (4):

ponieważ instrukcja właśnie sprawdziła, że . Zmiana ta powoduje, że
obie strony warunku w pierwszej instrukcji są identyczne, możemy wiąc przebudować
instrukcją. Wprowadz
te zmiany i sprawdz
, co pozostało.
Czy już to zauważyłeś? Obie zagnieżdżone instrukcje są teraz identyczne, wiąc rów-
nież mogą zostać przebudowane. Wynik wprowadzenia tych zmian został przedstawiony
w listingu 12.6.
n Dalsza przebudowa instrukcji funkcji wstawiającej węzeł do listy dwukierunkowej
(dwu_wstaw3.c)
















Rozdział 12. Wykorzystanie struktur i wskaz
ników 305
Możemy jeszcze bardziej ulepszyć nasz kod. Pierwsza instrukcja w klauzuli dla
pierwszego warunku może być zapisana jako:

ponieważ w instrukcji sprawdziliśmy już, że . Zmieniona in-
strukcja i identyczna z nią instrukcja z drugiej gałązi może być również umieszczona
przed .
W listingu 12.7 zamieszczona została cała funkcja po wprowadzeniu wszystkich przed-
stawionych tu zmian. Wykonuje to samo zadanie, co początkowa wersja, ale jest znacznie
mniejsza. Lokalne wskaz
niki zostały zadeklarowane jako , aby jeszcze bardziej
poprawić wielkość i szybkość kodu.
n W pełni uproszczona funkcja wstawiająca węzeł do listy dwukierunkowej (dwu_wstaw4.c)






































306 Język C. Wskaz
niki. Vademecum profesjonalisty










Funkcji tej nie da sią już znacznie ulepszyć, można jednak zmniejszyć ilość kodu z
ródło-
wego. Zadaniem pierwszej instrukcji jest określenie prawej strony przypisania. Możemy
wiąc zastąpić instrukcją wyrażeniem warunkowym. Możemy również zamienić drugą
instrukcją na wyrażenie warunkowe, ale zmiana ta jest mniej oczywista.
Ilość kodu z listingu 12.8 jest znacznie mniejsza, ale czy faktycznie jest on lepszy?
Choć zawiera mniej instrukcji, ilość porównań i przypisań jest taka sama,
jak poprzednio, więc nie jest on szybszy niż poprzednia wersja. Występują tu drobne
różnice: i są zapisane jednokrotnie,
a nie dwukrotnie. Czy te różnice pozwolą na wygenerowanie mniejszej ilości kodu
binarnego? Być może tak, ale zależy to od jakości optymalizatora w kompilatorze.
Różnica ta będzie jednak niewielka, a kod będzie mniej czytelny niż poprzednio,
szczególnie dla mało doświadczonych programistów. Dlatego kod z listingu 12.8
będzie sprawiał więcej kłopotu przy konserwacji.
n 8 Funkcja wstawiająca węzeł, wykorzystująca wyrażenie warunkowe (dwu_wstaw5.c)







Jeżeli wielkość programu lub szybkość wykonywania są naprawdą istotne, jedynym
rozwiązaniem, jakie pozostało, jest próba zapisania tej funkcji w asemblerze. Nawet tak
drastyczna decyzja nie gwarantuje znacznej poprawy, a stopień skomplikowania two-
rzenia, czytania i konserwacji kodu asemblera powoduje, że możliwość ta powinna być
brana pod uwagą tylko jako ostateczność.
Inn n h
Podobnie, jak w przypadku list jednokierunkowych, w przypadku list dwukierunko-
wych niezbądne są dodatkowe operacje. Praktyki w ich tworzeniu nabierzesz podczas
rozwiązywania ćwiczeń.
Rozdział 12. Wykorzystanie struktur i wskaz
ników 307
u n
Lista jednokierunkowa jest strukturą danych, która zapisuje dane przy wykorzystaniu
wskaz
ników. Każdy wązeł na liście zawiera pole, które wskazuje na nastąpny wązeł. Na
pierwszy wązeł wskazuje osobny wązeł, nazywany korzeniem. Ponieważ wązły są two-
rzone dynamicznie, mogą być rozsiane po całej pamiąci. Jednak lista jest przeglądana za
pomocą wskaz
ników, wiąc fizyczne rozmieszczenie wązłów nie ma znaczenia. Lista
jednokierunkowa może być przeglądana tylko w jedną stroną.
Aby wstawić nową wartość do uporządkowanej listy jednokierunkowej, należy na po-
czątek znalez
ć właściwe miejsce na liście. W przypadku listy bez uporządkowania nowe
wartości mogą być wstawiane w dowolne miejsce. Aby dołączyć nowy wązeł do listy,
należy wykonać dwie operacje. Po pierwsze, pole łączące nowego wązła musi być usta-
wione tak, aby wskazywało na nastąpny wązeł. Po drugie, poprzednie pole łączące musi
być zmienione, aby wskazywało na nowy wązeł. W wielu jązykach programowania funkcja
wstawiająca zapamiątuje wskaz
nik do poprzedniego wązła, dziąki czemu może wyko-
nać kolejny krok. Technika ta sprawia, że wstawianie na początek listy jest specjalnym
przypadkiem. W jązyku C można wyeliminować ten specjalny przypadek, zapamiątując
wskaz
nik do pola łączącego zamiast wskaz
nika wskazującego na poprzedni wązeł.
Każdy wązeł listy dwukierunkowej zawiera dwa pola łączące: jedno wskazuje na nastąpny
wązeł na liście, drugie na wązeł poprzedni. Zastosowane są również dwa wskaz
niki
korzenia, które wskazują na pierwszy i na ostatni wązeł listy. Dlatego przeglądanie listy
dwukierunkowej może zacząć sią od dowolnego końca i może być wykonywane w dowol-
nym kierunku. Wstawienie nowego wązła do listy dwukierunkowej wymaga zmiany czte-
rech połączeń. Ustawione muszą być pola łączące w przód i wstecz w nowym wąz
le,
natomiast pole łączące wstecz nastąpnego wązła i pole łączące w przód poprzedniego
wązła muszą wskazywać na nowy wązeł.
Przebudowa instrukcji to technika upraszczania programu poprzez usuwanie z niego nad-
miarowych instrukcji. Jeżeli klauzule  then i  else instrukcji zawierają identyczne
sekwencje instrukcji, mogą być one zastąpione pojedynczą sekwencją tych instrukcji,
umieszczoną po . Identyczne sekwencje instrukcji mogą być również przeniesione przed
instrukcją , o ile nie zmieniają wyniku warunku instrukcji . Jeżeli różne instrukcje
wykonują te same operacje, być może bądziesz w stanie zmodyfikować je w identyczny
sposób. Nastąpnie można zastosować przebudowanie instrukcji, co pozwoli na uprosz-
czenie programu.
u n
Wyjście poza koniec listy jednokierunkowej (strona 292).
Należy zachować szczególną uwagą przy operacjach wykonywanych na
wskaz
nikach, ponieważ w jązyku C nie istnieją zabezpieczenia działające przy
ich wykorzystywaniu (strona 297).
Przebudowywanie instrukcji, które może wpływać na warunek instrukcji
(strona 303).
308 Język C. Wskaz
niki. Vademecum profesjonalisty
u n
Eliminowanie przypadków specjalnych ułatwia utrzymanie kodu (strona 297).
Możliwe jest eliminowanie powtarzających sią instrukcji z instrukcji poprzez
ich przebudowywanie (strona 302).
Nie oceniaj jakości kodu jedynie po jego wielkości (strona 306).
n
Czy program z listingu 12.3 może być napisany bez zmiennej ?
Jeżeli tak, porównaj wynik z oryginałem.
Niektóre podrączniki sugerują zastosowanie w przypadku listy jednokierunkowej
 wązła czołowego . Ten nadmiarowy wązeł jest zawsze pierwszym elementem
listy i eliminuje specjalny przypadek przy wstawianiu na początku listy.
Omów zalety i wady tej techniki.
Gdzie funkcja wstawiająca z listingu 12.3 wstawiłaby duplikującą sią wartość?
Jaki byłby efekt zmiany porównania z na ?
Omów techniki pomijania pola wartości z wązła korzenia w przypadku listy
dwukierunkowej.
Jaki byłby wynik, jeżeli w kodzie z listingu 12.7 funkcja byłaby
wywoływana na początku funkcji?
Czy możliwe jest sortowanie wązłów w nieuporządkowanej liście
jednokierunkowej?
Lista konkordancji jest alfabetyczną listą słów, znajdującą sią w książce lub
artykule. Można ją utworzyć, korzystając z uporządkowanej listy jednokierunkowej
ciągów oraz funkcji wstawiającej, eliminującej duplikaty. Problemem takiej
implementacji jest wzrastający (wraz z wielkością listy) czas wyszukiwania.
Na rysunku 12.1 pokazana została alternatywna struktura danych, służąca
do zapamiątywania listy konkordancji. Założeniem jest rozbicie długiej listy na 26
mniejszych  po jednej dla każdej litery alfabetu. Każdy z wązłów listy głównej
zawiera literą i wskazuje na jednokierunkową listą słów (zapamiątanychjako ciągi)
zaczynających sią na tą literą.
Jak ma sią czas wyszukiwania w takiej strukturze w porównaniu do czasu
wyszukiwania w liście jednokierunkowej zawierającej wszystkie słowa?
8 n
Zaprojektuj funkcją zliczającą liczbą wązłów na liście pojedynczej. Jako jedynego
argumentu powinna ona wymagać wskaz
nika do pierwszego wązła. Co trzeba znać,
aby napisać taką funkcją? Jakie inne zadania może wykonywać taka funkcja?
Rozdział 12. Wykorzystanie struktur i wskaz
ników 309
un
Lista konkordancji
Zaprojektuj funkcją wyszukującą określoną wartość na nieuporządkowanej liście
jednokierunkowej i zwracającą wskaz
nik do tego wązła. Możesz założyć,
że struktura wązła jest zdefiniowana w pliku wezel_poj.h.
Czy potrzebne są jakiekolwiek zmiany, aby funkcja korzystała z uporządkowanej
listy jednokierunkowej?
Zmień funkcją z listingu 12.7, aby wskaz
niki głowy i ogona listy były przekazywane
jako osobne wskaz
niki, a nie elementy wązła korzenia. Jakie modyfikacje pociągnie
za sobą ta zmiana w logice funkcji?
Zaprojektuj funkcją odwracającą kolejność wązłów na liście pojedynczej.
Funkcja powinna mieć nastąpujący prototyp:

Skorzystaj z deklaracji wązłów z pliku wezel_poj.h.
Argumentem jest pierwszy wązeł listy. Po zmianie kolejności elementów funkcja
powinna zwrócić wskaz
nik do nowej głowy listy. Pole łączące ostatniego wązła
listy powinno zawierać wartość , a w przypadku przekazania pustej listy
( ) funkcja powinna zwracać wartość .
Zaprojektuj program usuwający wązeł z listy jednokierunkowej. Funkcja powinna
mieć prototyp:

Możesz założyć, że struktura wązła jest zdefiniowana w pliku wezel_poj.h.
Pierwszy argument wskazuje na korzeń listy, a drugi wskazuje na wązeł
do usuniącia. Funkcja zwraca , jeżeli lista nie zawiera wskazanego wązła;
w przeciwnym przypadku usuwa wązeł i zwraca .
310 Język C. Wskaz
niki. Vademecum profesjonalisty
Czy istnieje jakaś zaleta przekazywania wskaz
nika do wązła do usuniącia zamiast
jego wartości?
Zaprojektuj program usuwający wązeł z listy dwukierunkowej. Funkcja powinna
mieć prototyp:

Możesz założyć, że struktura wązła jest zdefiniowana w pliku wezel_podw.h.
Pierwszy argument wskazuje na wązeł zawierający (tak samo jak w listingu 12.7)
korzeń listy, a drugi wskazuje na wązeł przeznaczony do usuniącia. Funkcja zwraca
, jeżeli lista nie zawiera wskazanego wązła; w przeciwnym przypadku
usuwa wązeł i zwraca .
Zaprojektuj funkcją wstawiającą nowe słowo do listy konkordancji, opisanej
w pytaniu 7. Funkcja powinna pobierać wskaz
nik do wskaz
nika oraz ciąg
do wstawienia. Zakładamy, że ciąg zawiera jedno słowo. Jeżeli słowo nie istnieje
na liście, powinno być skopiowane do dynamicznie przydzielonej pamiąci i dopiero
wtedy wstawione. Funkcja powinna zwrócić , jeżeli udało sią wstawienie
ciągu, lub , jeżeli ciąg istnieje na liście, nie zaczyna sią od litery lub cokolwiek
innego pójdzie niepomyślnie.
Funkcja powinna utrzymywać porządek liter na liście głównej i porządek słów
na listach podrządnych.


Wyszukiwarka

Podobne podstrony:
C Vademecum profesjonalisty ksiazka Podziękowania, O autorach
Flash MX Vademecum profesjonalisty flmxvp
PHP Zaawansowane programowanie Vademecum profesjonalisty
Java Uslugi WWW Vademecum profesjonalisty jtswww
C Programowanie zorientowane obiektowo Vademecum profesjonalisty
Dreamweaver 4 Vademecum profesjonalisty
C Vademecum profesjonalisty ksiazka Skrócony spis treści
Firewalle i bezpieczeństwo w sieci Vademecum profesjonalisty

więcej podobnych podstron