Tablouri de pointeri, pointeri pe pointeri

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 ?