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 potri-
vit 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 poin-
terii 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 */
else
printf("input prea mare pt sort \n");
}
#define MAXLEN 1000
readlines(lineptr, maxlines) /* citeste linii input */
char *lineptr[];
int maxlines;
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;
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;
*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: declaratii-
le 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;
}
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 progra-
mele 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 ?
