Programarea Calculatoarelor: Laborator 10

Pointeri şi alocare dinamică

Scrieţi o funcţie care ia ca parametri un tablou de adrese de caracter (fiecare indicând un şir valid) şi returnează, alocat dinamic, un şir de caractere care e concatenarea celor date, separate prin spaţii.

Pentru a clarifica folosirea unui tablou de adrese, scriem întâi următoarea funcţie care tipăreşte tabloul dat:

void afiseaza(char *tab[], int num) // sau: char **tab
{
  for (int i = 0; i < num; ++i)
    printf("la adresa %p se afla sirul %s\n", tab[i], tab[i]);
}

Pentru a rezolva problema propusă, parcurgem întâi tabloul şi însumăm lungimile şirurilor pentru a afla care va fi dimensiunea şirului concatenat. E preferabil să facem alocarea dinamică o singură dată, cunoscând dimensiunea totală a memoriei necesare (chiar cu costul parcurgerii preliminare a şirurilor) decât să repetăm pentru fiecare şir efortul de creştere cu realloc a zonei de memorie alocate.

char *concat(char *tab[], int num) // sau: char **tab
{
  size_t len = num;	// dimensiunea zonei de alocat
  // pe langa siruri e nevoie de num-1 spatii + un caracter '\0'
  for (int i = 0; i < num; ++i)
    len += strlen(tab[i]);	// calculeaza lungimea totala
  char *p = malloc(len), *end = p;
  if (p) {	// alocare cu succes
    for (int i = 0; i < num; ++i) {
      char *s = tab[i];
      while (*s) *end++ = *s++); // copiaza sirul tab[i] pana la '\0'
      *end++ = ' ';              // pune spatiu şi avansează
    }
    end[-1] = '\0';	// pune '\0' in loc de spatiu dupa ultimul cuvant
  }
  return p;
}

Copierea din tab[i] se putea face şi cu funcţia strcpy, dar în acest caz, şirul era parcurs de două ori: o dată la copiere, şi încă o dată pentru a-i calcula lungimea (necesară pentru plasarea spaţiului). Ciclul s-ar fi scris:

strcpy(end, tab[i]);
end += strlen(tab[i]);
*end++ = ' ';

int main(int argc, char *argv[])
{
  char *p = concat(argv, argc);
  if (p) {
    printf("%s\n", p);
    free(p);
  }
  return 0;
}

Funcţia trebuie să returneze adresa unui tablou cu elemente adrese de caracter (char *), deci rezultatul e de tipul char **. Similar cu problema anterioară, efectuăm întâi o parcurgere în care numărăm cuvintele din şir (primul ciclu for).

char **splitwords(char *s)
{
  while (isspace(*s)) ++s;	// sare peste spaţiile iniţiale
  int nw = 0;	// numarul de cuvinte
  for (char *p = s; *p; ++nw) {	// fiecare ciclu numara un cuvant
    while (!isspace(*++p) && *p);  // sare peste cuvânt
    while (isspace(*p)) ++p;	   // sare peste spaţii
  }
  char **t = malloc((nw + 1) * sizeof(char *));	 // un element in plus
  if (t) {
    char **t1 = t;	// intrarea curentă în tablou
    while (*s) {	
      *t1++ = s;	// memorează începutul cuvântului
      while (!isspace(*++s) && *s);  // sare peste cuvânt
      if (*s == '\0') break;   // s-a terminat tot şirul
      *s = '\0';	// marcheaza sfârşitul cuvântului
      while (isspace(*++s));	// sare peste eventuale alte spaţii
    }
    *t1 = NULL;	// marchează sfârşitul tabloului
  }
  return t; 
}

După ce a numărat cuvintele (nw), funcţia alocă un tablou de nw+1 elemente char * unde vor fi memorate adresele de început ale cuvintelor din şir. Tabloul este parcurs cu un pointer t1 care indică elementul curent; la fiecare iteraţie, la adresa indicată de acesta (adică în elementul curent) se trece adresa de început al cuvântului. Parcurgerea şirului este similară cu cea făcută prima dată; cu deosebire că primul spaţiu de după un cuvânt e transformat în caracterul '\0' pentru a indica sfârşitul cuvântului, şi apoi se sare peste eventualele spaţii suplimentare.

int main(void)
{
  char buf[81];
  if (fgets(buf, 81, stdin)) {
    char **t = splitwords(buf);
    if (t) {
      for (char **t1 = t; *t1; t1++)
	printf("la adresa %p cuvântul %s\n", *t1, *t1);
      free(t);
    }
  }
  return 0;
}

for (int i = 0; t[i]; ++i)
  printf("la adresa %p cuvântul %s\n", t[i], t[i]);

Exerciţiul 3 Crearea unui tablou care poate fi redimensionat
Scriem un program care citeşte în memorie un text de la intrare păna la sfârşitul intrării, şi îl memorează pe linii, alocând un tablou de adrese, câte una pentru fiecare linie.

Folosim pentru citirea unei linii funcţia prezentată la curs care alocă dinamic memorie pentru a citi o linie de text oricât de lungă şi returnează adresa unde a fost citită linia:

char *makeline(void)
{
  char *p = NULL, *p1;
  int c, i = 0, lim = -1;

  while ((c = getchar()) != EOF) {
    if (i >= lim)
      if (p1 = realloc(p, (lim += 16)+1)) p = p1;
      else break;
    p[i++] = c;
    if (c == '\n') break;
  }
  if (p) {
    p[i++] = '\0';
    return realloc(p, i);
  } else return NULL;
}

int i = 0, size = 10;	// 10 linii 
char *p, *tab[size];
while (p = makeline()) { // p e nenul, s-a citit o linie
  if (i >= size) break;	// tabloul e plin
  tab[i++] = p;	// stocheaza adresa
}

int main(void)
{
  int i = 0, size = 0;
  char *p, **tab = NULL, **t1;
  while (p = makeline()) { // p e nenul, s-a citit o linie
    if (i >= size) {
      if (!(t1 = realloc(tab, (size += 10)*sizeof(char *)))) break; // nu e loc
      tab = t1; // folosim adresa la care a fost realocat tabloul
    }
    tab[i++] = p;	// stocheaza adresa
  }
  if (tab) {		// s-a citit macar o linie
    tab = realloc(tab, (size = i) * sizeof(char *));	// realoca cat e nevoie
    for (i = 0; i < size; ++i) // foloseste tabloul
      printf("%s", tab[i]);
    for (i = 0; i < size; ++i) 
      free(tab[i]);	// elibereaza fiecare sir
    free(tab);	// elibereaza tabloul
  }  
  return 0;
}

Exerciţiul 4 Sortarea unor şiruri de caractere
Continuăm programul anterior efectuând şi o prelucrare asupra textului citit: afişăm liniile acestuia în ordine alfabetică (lexicografică) crescătoare (ca numele din cartea de telefon). Pentru aceasta folosim funcţia standard qsort. Aceasta are nevoie de o funcţie de comparaţie care primeşte adresele a două elemente de tablou. Întrucât elementele tabloului sunt ele însele adrese (char *), funcţia va avea parametri de tipul char ** :

int compstr(const char **ps1, const char **ps2)
{
  return strcmp(*ps1, *ps2);
}

typedef int (*compar_t)(const void *, const void *);

Pentru sortare, e suficient să mai adăugăm la programul anterior o linie înainte de tipărirea tabloului:

qsort(tab, size, sizeof(char *), (compar_t)compstr);

Spre comparaţie, dacă am fi lucrat cu tablouri bidimensionale de caractere, funcţia de comparare ar fi primit direct adresele şirurilor si nu mai era nevoie de o dereferenţiere suplimentară:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	4
#define LEN	10

typedef int (*compar_t)(const void *, const void *);

int comptab(const char *s1, const char *s2)
{
  return strcmp(s1, s2);
}

int main(void)
{
  char t[N][LEN] = { "primavara", "vara", "toamna", "iarna" };
  qsort(t, N, LEN, (compar_t)comptab);
  for (int i = 0; i < N; ++i)
    printf("%s\n", t[i]);
  return 0;
}

Exerciţii propuse:

• funcţii care realizează operaţii aritmetice (adunare, scădere, înmulţire ...) pe şiruri de caractere reprezentând întregi în baza 10, lucrănd cifră cu cifră, fără a converti valorile din şiruri la int (în felul acesta se poate lucra cu numere arbitrar de lungi)
• programe care citesc un text întreg de la intrare şi realizează diverse prelucrări (aliniază paragrafe, ordonează linii după lungime, şi apoi alfabetic, creează un indice de cuvinte, etc.)