ANSI C 3

5 WSKAŹNIKI I TABLICE

możliwości są zawarte w funkcjach: getline (rozdz. 1 i 4), atoi, itoa i ich wariantach (rozdz. 2, 3 i 4), reverse (rozdz. 3) oraz w strindex i getop (rozdz. 4).

Tablice wskaźników; wskaźniki do wskaźników

Wskaźniki same są zmiennymi, można więc z nich budować tablice tak samo, jak z innych zmiennych. Dla ilusfracji napiszemy program ustawiający w porządku alfabetycznym zbiór wierszy tekstu. Będzie to okrojona wersja programu sort należącego do zestawu programów użytkowych systemu Unix.

W rozdziale 3 prezentowaliśmy funkcję porządkującą tablicę liczb całkowitych według metody Shell-sort, a w rozdz. 4 udoskonaliliśmy ją według metody szybkiego sortowania. Użyjemy tych samych algorytmów z tym, że teraz będziemy mieć do czynienia z wierszami tekstu. Wiersze są różnej długości i - w przeciwieństwie do liczb - nie można ich porównywać ani przesyłać za pomocą pojedynczej operacji. Potrzebujemy więc reprezentacji danych pozwalającej w sposób wygodny i efektywny obsługiwać wiersze tekstu o zmiennej długości.

Tu wkracza tablica wskaźników. Jeżeli przeznaczone do sortowania wiersze tekstu umieścić jeden za drugim w dużej tablicy znakowej, to każdy wiersz może być dostępny za pomocą wskaźnika do jego pierwszego znaku. Te wskaźniki można umieścić w innej tablicy. Wiersze porównuje się, przekazując ich wskaźniki funkcji strcmp. Gdy dwa nie uporządkowane wiersze należy zamienić miejscami, wówczas wystarczy w tablicy wskaźników zamienić miejscami ich wskaźniki, nie zaś same teksty.

Eliminuje to podwójny problem skomplikowanego zarządzania pamięcią oraz wysokich kosztów związanych z przesuwaniem samych wierszy tekstu.

Proces porządkowania przebiega w trzech etapach:

przeczytaj wszystkie wiersze z wejścia uporządkuj je

wypisz wiersze we właściwej kolejności

5.6 TABLICE WSKAŹNIKÓW; WSKAŹNIKI DO WSKAŹNIKÓW

Mi

powered by

iinp

Jak zwykle, najlepiej jest podzielić program na funkcje realizujące k wynikające z tego podziału, z główną funkcją sterującą działaniem pozostałych. Zostawimy na chwilę etap porządkowania i skoncentrujemy się nad zagadnieniem struktur danych oraz nad wejściem i wyjściem.

Zadaniem funkcji wejściowej jest zebranie i przechowanie wszystkich znaków z każdego wiersza, a także zbudowanie tablicy wskaźników do tych wierszy. Powinna ona także zliczyć wiersze, informacja ta będzie bowiem potrzebna przy ich porządkowaniu i wypisywaniu. Funkcja wejściowa może obsłużyć ograniczoną liczbę wierszy z wejścia. Jeśli więc jest ich zbyt dużo, może zwrócić niepoprawną ich liczbę, np. -1.

Funkcja wyjściowa służy jedynie do wypisania wierszy w kolejności, w jakiej występują w tablicy wskaźników.

#include <stdio.h>

#include <string.h>

#define MAXLINES 5000 /* maks. liczba wierszy do sortowania */ char *lineptr[MAXLINES]; /* wskaźniki do wierszy tekstu */

int readlines(char *lineptr[], int nlines); void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

I* uporządkuj wiersze wejściowe */ main()

{

int nlines; /* liczba wczytanych wierszy */

if ((nlines = readlines(lineptr, MAXLINES)) >= 0) { qsort(lineptr, 0, nlines—1); writelines(lineptr, nlines); return 0;

} else {

printf(”błąd: za dużo wierszy do sortowania\n”); return 1;

}

}

149