Curs 6 - Liste Înlănțuite, Dicționar, Stivă și Coadă în C

Acest curs introduce structurile de date dinamice, incluzând listele înlănțuite, dicționarele, stivele și cozile.

1. Liste Înlănțuite

Listele înlănțuite sunt structuri de date dinamice în care fiecare nod conține un element și un pointer către următorul nod.

a) Definirea unei Liste Înlănțuite

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

struct Nod {
    int valoare;
    struct Nod *urmator;
};

void afisare(struct Nod *cap) {
    while (cap != NULL) {
        printf("%d -> ", cap->valoare);
        cap = cap->urmator;
    }
    printf("NULL\n");
}

int main() {
    struct Nod *primul = malloc(sizeof(struct Nod));
    struct Nod *al_doilea = malloc(sizeof(struct Nod));
    struct Nod *al_treilea = malloc(sizeof(struct Nod));
    
    primul->valoare = 1; primul->urmator = al_doilea;
    al_doilea->valoare = 2; al_doilea->urmator = al_treilea;
    al_treilea->valoare = 3; al_treilea->urmator = NULL;
    
    afisare(primul);
    
    free(primul);
    free(al_doilea);
    free(al_treilea);
    
    return 0;
}

2. Dicționar în C

În C, dicționarele nu sunt disponibile nativ, dar putem implementa o structură bazată pe hashing.

a) Implementarea unui Dicționar Simplu cu Hashing

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

#define SIZE 10

struct Element {
    char cheie[50];
    int valoare;
    struct Element *urmator;
};

struct Element *tabela[SIZE] = {NULL};

int hash(char *cheie) {
    int suma = 0;
    for (int i = 0; cheie[i] != '\0'; i++) {
        suma += cheie[i];
    }
    return suma % SIZE;
}

void adauga(char *cheie, int valoare) {
    int index = hash(cheie);
    struct Element *nou = malloc(sizeof(struct Element));
    strcpy(nou->cheie, cheie);
    nou->valoare = valoare;
    nou->urmator = tabela[index];
    tabela[index] = nou;
}

int cauta(char *cheie) {
    int index = hash(cheie);
    struct Element *current = tabela[index];
    while (current) {
        if (strcmp(current->cheie, cheie) == 0)
            return current->valoare;
        current = current->urmator;
    }
    return -1;
}

int main() {
    adauga("cuvant1", 10);
    adauga("cuvant2", 20);
    printf("Valoarea pentru 'cuvant1': %d\n", cauta("cuvant1"));
    return 0;
}

3. Stivă

O stivă este o structură de date LIFO (Last In, First Out).

a) Implementarea unei Stive cu Liste Înlănțuite

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

struct Nod {
    int data;
    struct Nod *urmator;
};

struct Nod *varf = NULL;

void push(int x) {
    struct Nod *nou = malloc(sizeof(struct Nod));
    nou->data = x;
    nou->urmator = varf;
    varf = nou;
}

void pop() {
    if (varf == NULL) return;
    struct Nod *temp = varf;
    varf = varf->urmator;
    free(temp);
}

void afisare() {
    struct Nod *temp = varf;
    while (temp) {
        printf("%d\n", temp->data);
        temp = temp->urmator;
    }
}

int main() {
    push(10);
    push(20);
    push(30);
    afisare();
    pop();
    afisare();
    return 0;
}

4. Coada

O coadă este o structură de date FIFO (First In, First Out).

a) Implementarea unei Cozi cu Liste Înlănțuite

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

struct Nod {
    int data;
    struct Nod *urmator;
};

struct Nod *frunte = NULL, *spate = NULL;

void enqueue(int x) {
    struct Nod *nou = malloc(sizeof(struct Nod));
    nou->data = x;
    nou->urmator = NULL;
    if (spate == NULL) {
        frunte = spate = nou;
        return;
    }
    spate->urmator = nou;
    spate = nou;
}

void dequeue() {
    if (frunte == NULL) return;
    struct Nod *temp = frunte;
    frunte = frunte->urmator;
    free(temp);
    if (frunte == NULL) spate = NULL;
}

void afisare() {
    struct Nod *temp = frunte;
    while (temp) {
        printf("%d\n", temp->data);
        temp = temp->urmator;
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    afisare();
    dequeue();
    afisare();
    return 0;
}

Resurse suplimentare:

• Liste Înlănțuite - GeeksForGeeks
• Hash Table în C