Capitolul 5.8. Tablouri de pointeri, pointeri pe pointeri

Datorita faptului ca pointerii sint ei insisi variabile, este de asteptat ca ei sa fie utilizati in tablouri de pointeri. Deci, se pune problema de a ilustra prin scrierea unui program care sorteaza un set de linii de text in ordine alfabetica, o versiune a sortului utilitar UNIX.
In capitolul 3 am prezentat o functie sort shell care sorta un tablou de intregi. Vom utiliza acelasi algoritm cu exceptia faptului ca acum vom avea de-a face cu linii de text de lungimi diferite si care, spre deosebire de intregi, nu pot fi comparate sau deplasate printr-o singura operatie. Avem nevoie de o reprezentare a datelor care sa poata face eficient si potrivit regulilor in gestionarea linilor de text de lungime diferita.
Acum este momentul potrivit pt a introduce tabloul de pointeri.
Daca liniile de sortat sint memorate cap la cap intr-un lung sir de caractere (rezervat prin alloc, sazicem) atunci fiecare linie poate fi accesata printr-un pointer pe primul sau caracter.
Pointerii insisi pot fi memorati intr-un tablou. Doua linii pot fi comparate prin transmiterea pointerilor respectivi lui strcmp.Cind doua linii neordonate trebuiesc inversate se inverseaza pointerii lor in tabelul de pointeri, nu liniile insele. Acest mod de lucru elimina cuplul de probleme legate de gestionarea memoriei si, ceea ce este mai presus de orice, poate deplasa liniile reale.
Procesul de sortare consta din trei parti:

citirea tuturor liniilor la intrare
sortarea liniilor
tiparirea liniilor in ordine

Ca de obicei cel mai bine este sa impartim programul in functii care rezolva aceasta defalcare, cu o rutina principala care controleaza totul. Sa aminam pentru un moment pasul de sortare si sa ne concentram asupra structurii de date si a I/O. Rutina de inceput trebuie sa colecteze si sa salveze caracterele din fiecare linie si sa construiasca un tablou de pointeri pe linii. Va trebui, deasemenea sa se numere liniile la intrare, deoarece aceasta informstie este necesara pt sortare si tiparire. Deoarece functia de intrare poate opera doar cu un numar finit de linii-input, ea va returna o valoare, cum ar fi -1, in cazul in care se vor prezenta mai multe linii. Rutina de output trebuie doar sa tipareasca liniile in ordinea in care apar i tabloul de pointeri.

#define NULL 0
#define LINES 100 /* maximum de linii de sortat */
main() /* sortarea liniilor de intrare */
{
char *lineptr[LINES];/*pointeri pe linii de text*/
int nlines; /* nr liniilor libere */
if ((nlines = readlines(lineptr, LINES)) >= 0) {
sort(lineptr, nlines);
writelines(lineptr, nlines);
}
else
printf("input prea mare pt sort \n");
}
#define MAXLEN 1000
readlines(lineptr, maxlines) /* citeste linii input */
char *lineptr[];
int maxlines;
{
int len, nlines;
char *p, *alloc(), line[MAXLEN];
nlines = 0
while ((len = getline(line, MAXLEN)) > 0)
if (nlines >= maxlines)
return(-1);
else if ((p = alloc(len)) == NULL)
return(-1);
else {
line[len-1] = '\0'; /* zap newline */
strcpy(p, line);
lineptr[nlines++] = p;
}
return(nlines);
}

"newline" de la sfirsitul fiecarei linii este sters astfel incit nu va fi afectata ordinea in care sint sortate liniile.

writelines(lineptr, nlines) /* scrie linii la iesire */
char *lineptr[];
int nlines;
{
int i;
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}

Principala noutate este declarata pentru "lineptr":

char *lineptr[LINES];

spune ca lineptr este un tablou de elemente LINES, fiecare element fiind un pointer pechar. Adica, lineptr[i] este un pointer pe caractere iar *lineptr[i] acceseaza un caracter.
Daca lineptr este el insusi un tablou care este transmis lui writelines, el poate fi tratat ca un pointer in exact aceeasi maniera ca in exemplul nostru anterior, iar functia poate fi scrisa.

writelines(lineptr, nlines) /* scrie linii la iesire */
char *lineptr[];
int nlines;
{
while (--nlines >= 0)
printf("%s\n", *lineptr++);
}

*lineptr pointeaza initial pe prima linie, cu fiecare incrementare el avanseaza pe linia urmatoare pina cind nlines se epuizeaza.
Intrarea si iesirea fiind controlate, se poate duce la sortare. Sortul -shell din cap 3 va suferi modificari: declaratiile trebuie modificate iar operatia de grupare trebuie montata intr-o functie separata. Algoritmul de baza ramine acelasi ceea ce ne da o oarecare speranta ca totul va merge bine inca

short(v, n) /* sorteaza sirurile v[0]. . . v[n-1] */
char *v[]; /* in ordine crescatoare */
int n;
{
int gap, i, j;
char *temp;
for (gap = n/2); gap>0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0; j -= gap)
{
if (strcmp(v[j], v[j+gap]) <= 0)
break;
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}

Daca orice element individual din v(alias lineptr) este un pointer pe caractere, temp va fi si el astfel de pointer, asa incit cei doi pot fi copiati unul in altul.
Am scris un program care, in fc de cunostintele din acel moment a fost rapid pe cit posibil. Acest program poate fi facut mai rapid, de exemplu sa copieze liniile input direct intr-un tablou mentinut prin readlines in loc sa le copieze in line pt ca apoi sa le plaseze undeva prin alloc. Dar, pentru a facilita intelegerea programului sa intocmim mai intii o schema logica, si abia dupa aceea sa ne preocupam de eficienta sa.
Modalitatea de a face acest program mai eficeint nu vizeaza neaparat evitarea unei copii a liniilor input. Inlocuirea sortului shell prin ceva mai bun cum ar fi sortul Quicksort, este probabil mai mult decit a marca o simpla diferenta.
In capitolul 1 am semnalat acest lucru deoarece buclele while si for testeaza conditia finala inaintea executarii chiar si pt prima data a corpului buclei; ele ajuta la a ne asigura ca programele vor merge chiar si la limita, in particular fara input. Este edificator a umbla prin functiile programelor de sortare pt a verifica ce se intimpla daca nu exista deloc text de intrare.

Exercitiul 5.5. Rescrieti readlines pt a crea linii intr-un tablou umplut cu main, in loc de a apela pe alloc pt rezervarea de memorie, Cu cit este mai rapid acest program ?