Scrieți un program care citește un n de la tastatură și creează un vector (cu dimensiunea n) de numere întregi generate aleator și îl sortează ulterior folosind funcția de bibliotecă void qsort din stdlib.h:

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) )

base este adresa primului element din vector
num este numărul de elemente din vector
size este dimensiunea unui element
comparator este funcția ce compară 2 elemente din vector

Implementați o funcție de comparare în care să apelați qsort cu parametrii corespunzători.
Rezolvare:

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

#define MAX_VALUE 200

int cmp(const void * a, const void *b)
{
    return (*(int*)a - *(int*)b);
}

int main(void)
{
    int N, i;
    int *v;
    printf("Introduceti dimensiunea vectorului:\n");
    scanf("%d", &N);

    v = calloc(N, sizeof(int));
    if (!v) printf("Nu am putut aloca memorie pentru v!\n");

    srand(time(NULL));
    for (i = 0; i < N; ++i)
        v[i] = (rand() % MAX_VALUE)+1;

    for (i = 0; i < N; ++i)
        printf("%d ", *(v+i));
    printf("\n");

    qsort(v, N, sizeof(int), cmp);

    for (i = 0; i < N; ++i)
        printf("%d ", *(v+i));
    printf("\n");

    free(v);
    return 0;
}

Problema 2.

Completați programul de la problema 1 astfel încât să se afișeze poziția pe care apare un întreg x citit de la tastatură în vectorul sortat. Veți folosi funcția void *bsearch din stdlib.h:

void *bsearch ( const void * key, void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) )

key este adresa cheii căutate
base este adresa primului element din vector
num este numărul de elemente din vector
size este dimensiunea unui element
comparator este funcția ce compară 2 elemente din vector

Funcția întoarce un pointer către elementul din vector corespunzător cheii căutate sau NULL dacă nu a fost găsit un astfel de element.

Problema 3.

Se consideră următoarele definiții:

typedef struct entry {
    void * key;
    void * value;
} entry;

typedef struct map {
    entry ** elem; // vectorul de elemente; este alocat si realocat dinamic
    int n_elem; // numarul de elemente din vector
    int cap; // capacitatea vectorului
} map;

Definiți următoarele funcții:

void init(map *m, int cap); alocă inițial memorie pentru cap elemente de tip entry*
void add(map *m, entry *e); adaugă la vectorul de elemente din m noua intrare (pointerul primit) și eventual realocă pe m->elem
void print(map *m, void ( *printEntry) ( entry * ) ); afișează pe m folosind funcția pentru afișarea unui entry primită ca parametru
void sort(map *m, int ( * fc ) ( const void *, const void * ) ) sortează elementele din m folosind funcția primită ca parametru și funcția de bibliotecă qsort. Observație: fc va trebui să compare între ele 2 structuri entry
void del(map *m, void *k, int ( * fc2 ) ( const void *, const void * )); șterge prima apariție cu cheia k în m. Atenție! Nu veți compara pointerii pentru a testa dacă 2 elemente sunt egale, ci veți folosi funcția primită ca parametru, ce se consideră că întoarce 0 pentru elemente egale. Observație: fc2 va trebui să compare între ele 2 chei (void *).
void *find(map *m, void *k, int ( * fc2 ) ( const void *, const void * )); funcție ce întoarce valoarea asociată unei chei. Observație: fc2 va trebui să compare între ele 2 chei (void *).

Pentru a testa funcțiile definite vom face următoarea particularizare: vrem să reținem definițiile asociate unor cuvinte. Va trebui să implementați funcțiile:

int compareEntry( const void *, const void *); ce compară între ele 2 structuri entry ținând cont de faptul că în acest caz particular cheie vor fi char *. Funcția de comparare nu trebuie să țină cont și de valorile asociate.
int compareKey( const void *, const void *); compară 2 chei (în cazul de față, 2 șiruri de caractere. Funcția va apela strcmp.
void printEntry( const entry *); afișează cheia și valoarea asociată pe cazul particular când sunt șiruri de caractere.

În programul principal, afișați un meniu ce va permite următoarele operații la apăsarea respectivelor taste:

1. Afisare dictionar sortat.
2. Cauta cuvant in dictionar. // se va afisa cuvantul + definitia sau un mesaj corespunzator daca nu a fost gasit
3. Adauga cuvant in dictionar. // se va citi de la tastatura cuvantul si definitia
4. Sterge cuvant din dictionar. // se va citi de la tastatura cuvantul ce se doreste sters
0. Iesire din program.

Aveți grijă să alocați memorie pentru fiecare cuvânt și pentru fiecare definiție și să o eliberați atunci când nu mai este nevoie (de ex. la ștergerea unui cuvânt). Puteți să le citiți inițial într-un buffer alocat static și să folosiți funcția strdup.

Laborator 11

Programare generică

În acest laborator veţi învăţa să:

Problema 1 - Problemă rezolvată.

Problema 2.

Problema 3.