Limbaje de programare: Laborator 7

Tablouri. Şiruri de caractere

Exerciţii pregătitoare

Un tipar des folosit e traversarea unui tablou calculând un rezultat din toate elementele, de exemplu suma:

double sumtab(double a[], unsigned len)
{
  double sum = 0;
  for (unsigned i = 0; i < len; ++i)
    sum += a[i];
  return sum;
}

Un alt tipar este căutarea în tablou după un element care îndeplineşte o condiţie:

int findneg(int a[], unsigned len)
{
  for (unsigned i = 0; i < len; ++i)
    if (a[i] < 0) return i;
  return -1;
}

Un alt tipar este cel de filtrare sau prelucrare selectivă doar a elementelor care satisfac o condiţie. Următorul exemplu copiazădintr-un tablou în altul doar anumite elemente (cele negative).

#include <stdio.h>

unsigned selectodd(int src[], int dest[], unsigned len)
{
  unsigned si, di;
  for (si = di = 0; si < len; ++si)
    if (src[si] % 2) dest[di++] = src[si];
  return di;
}

#define LEN 10

int main(void)
{
  int a[LEN] = {1, 4, 5, 6, -5, 7, 10, 9, 9, -5}, b[LEN];
  unsigned lenb = selectodd(a, b, LEN);	// returneaza nr. elem. copiate
  for (unsigned i = 0; i < lenb; ++i)
    printf("%d ", b[i]);
  return 0;
}

Pentru funcţiile care lucrează cu şiruri de caractere nu trebuie transmisă şi dimensiunea lor, dacă se respectă convenţia că un şir se termină cu caracterul '\0'.

#include <ctype.h>
#include <stdio.h>
void dotCaps(char s[])
{
  for (unsigned i = 0; s[i]; ++i)
    if (s[i] == '.') s[i+1] = toupper(s[i+1]);
}
int main(void)
{
  char sir[] = "citius.altius...fortius.";
  dotCaps(sir);
  printf("%s\n", sir);
}

Probleme propuse

1. Implementaţi câteva funcţii simple pentru lucru cu şiruri de caractere:
   • funcţia standard strlen care returnează lungimea unui şir: size_t strlen(const char *s)
     size_t e un tip întreg fără semn folosit pentru dimensiuni (tipul returnat de operatorul sizeof). Specificatorul const precizează că obiectul respectiv (şirul s) nu e modificat.
     Parcurgeţi şirul în ciclu cu un indice până când întâlneşte caracterul de sfârşit '\0' şi returnează valoarea indicelui (numărul caracterelor parcurse).
   • o funcţie int strindex(const char *s, char c) care returnează primul indice la care se află caracterul c în şirul s, sau -1 când caracterul nu e găsit.
     Tiparul e acelaşi ca la funcţia de căutare în tablou din exerciţiile de mai sus.
   • funcţia char *strchr(const char *s, int c) care la fel cu cea de mai sus caută un caracter (reprezentat de întregul c) într-un şir, dar returnează adresa caracterului găsit, sau NULL dacă acesta nu există în şir
   • variantele strrindex şi strrchr ale funcţiilor de mai sus, care găsesc ultima apariţie a caracterului în şir
2. Scrieţi o funcţie care ia ca parametru un şir şi returnează numărul de cuvinte din şir (cuvintele sunt şiruri care nu conţin spaţii albe).
3. Scrieţi o funcţie care ia ca parametru un şir şi returnează şirul modificat astfel încât fiecare cuvânt începe cu literă mică, în afară de primul cuvânt şi următorul cuvăt care începe după un punct care nu e în interiorul unui cuvânt.
   Variantă: ca mai sus, dar toate celelalte cuvinte sunt scrise integral cu litere mici, în afară de cele care erau formate doar din majuscule.
4. Scrieţi o funcţie care ia ca parametru un şir de caractere şi îl modifică înlocuind orice spaţii albe consecutive cu un singur spaţiu.
5. Scrieţi o funcţie care ia ca parametru un şir de caractere şi returnează valoarea numărului aflat în porţiunea iniţială a şirului.
   Funcţia acceptă ca şirul să conţină un număr arbitrar de spaţii albe iniţiale, opţional semnul (+ sau -), şi apoi cifre în baza 10. Conversia se opreşte la întâlnirea primului caracter necorespunzător. Dacă până în acel punct nu s-a întâlnit un număr valid, funcţia returnează zero.
   Observaţie: O astfel de funcţie standard există: int atoi(const char *s) şi e declarată în stdlib.h.
   Funcţia va construi numărul similar cu cele de citire de numere întregi (readnat, readint) scrise anterior, cu deosebirea că numărul e conţinut în şir. Funcţia nu va citi pe rând caractere de la intrare, ci va avansa cu indicele în şir.
   Variantă: scrieţi o funcţie care se comportă similar, dar acceptă un şir reprezentând un număr într-o bază arbitrară (între 2 şi 36), dată ca al doilea parametru. Cifrele cu valori începând de la 10 sunt reprezentate prin litere mari sau mici.
6. Scrieţi o funcţie care ia ca parametri un tablou cu coeficienţii (reali) ai unui polinom, gradul lui, şi o valoare x şi returnează valoarea în punctul x a polinomului.
7. Scrieţi o funcţie simplă de sortare a unui tablou (de întregi sau reali).
   Scrieţi întâi o funcţie care returnează indicele elementului maxim din tablou. Interschimbaţi maximul cu ultimul element, a[len-1] (dacă maximul nu e deja chiar pe această poziţie). Acum ultimul element e cel bun în ordinea de sortare, şi repetaţi sortarea pentru tabloul de la a[0] la a[len-2].
8. Fiind dat un număr prim p şi un număr 1 < a < p afişaţi toate numerele din intervalul (1, p) care nu pot fi scrise sub forma a^k(mod p).
   Indicaţie: calculaţi valorile a^k(mod p), k ≥ 1 până cănd apare valoarea 1 (şirul e periodic). Folosiţi un tablou cu indici resturile modulo p (0 până la p-1), iniţializat cu 0, în care treceţi 1 când întâlniţi restul respectiv.
9. Scrieţi o funcţie care afişează rezultatul împărţirii a două numere naturale m/n, incluzând perioada (dacă există) între paranteze. Exemplu: 5/28 = 0.17(857142)
   Indicaţie: perioada începe când la împărţirea lui m cu n apare un rest care a mai fost întâlnit. Procedaţi ca la problema anterioară.
10. Scrieţi o funcţie care realizează adunarea/înmulţirea/împărţirea a două polinoame, date prin tabloul cu coeficienţi şi gradul lor.