5. Redactaţi un program C care implementează operatorii de inserţie, suprimare şi
căutare într-o tabelă utilizînd tehnica dispersiei deschise.
6. Redactaţi un program C care implementează operatorii de inserţie şi căutare într-o
tabelă utilizînd tehnica dispersiei închise. Ce măsuri trebuiesc luate pentru a realiza
şi implementarea operatorului de suprimare. Implementaţi şi o astfel de variantă
Răspunsuri la întrebare
//5.
#include <stdlib.h>
#define MARIME 256
struct Nod {
int valoare;
int cheie;
Nod *urmatorul = (Nod*) NULL;
};
struct List {
Nod *nod = (Nod*) NULL;
};
struct Harta {
List *liste[MARIME];
} h;
void initializare(){
for(int i = 0; i < MARIME; i++){
h.liste[i] = (List*) malloc(sizeof(List));
h.liste[i]->nod = NULL;
}
}
void inserare(int cheie, int valoare){
int c = cheie / MARIME, cm = cheie % MARIME;
if(h.liste[cm]->nod == NULL){
h.liste[cm]->nod = (Nod*) malloc(sizeof(Nod));
h.liste[cm]->nod->cheie = cheie;
h.liste[cm]->nod->valoare = valoare;
h.liste[cm]->nod->urmatorul = NULL;
}else{
Nod* u,p;
for(u = h.liste[cm]->nod->urmatorul,p = h.liste[cm].nod; u != NULL; p = u, u = u->urmatorul);
p->urmatorul = (Nod*) malloc(sizeof(Nod));
p->urmatorul->cheie = cheie;
p->urmatorul->valoare = valoare;
p->urmatorul->urmatorul = NULL;
}
}
void suprimare(int cheie){
int cm = cheie % MARIME;
Nod *u, *p;
for(u = h.liste[cm]->nod, p = u; u != NULL && u->cheie != cheie; p = u, u = u->urmatorul);
if(u == NULL)return;
p->urmatorul = u->urmatorul;
free(u);
}
int cautare(int cheie){
int cm = cheie % MARIME;
Nod* u;
for(u = h.liste[cm].nod; u != NULL && u->cheie != cheie; u = u->urmatorul);
if(u == NULL)return -1;
else return u->valoare;
}
// 6.
#include <stdlib.h>
#define MARIME 256
struct Nod {
int valoare;
int cheie;
};
struct Harta {
Nod *noduri[MARIME];
} h;
void inserare(int cheie, int valoare){
int cm = cheie % MARIME;
if(h.noduri[cm] == NULL){
h.noduri[cm] = (Nod*)malloc(sizeof(Nod));
h.noduri[cm]->cheie = cheie;
h.noduri[cm]->valoare = valoare;
}else{
int i;
for(i = cm+1; i < MARIME && h.noduri[i] != NULL; i++);
if(i == MARIME){
for(i = 0; i < cm && h.noduri[i] != NULL; i++);
if(i == cm) return; /// fara spatiu, abandoneaza inserarea
else {
h.noduri[i] = (Nod*)malloc(sizeof(Nod));
h.noduri[i]->cheie = cheie;
h.noduri[i]->valoare = valoare;
}
}
else{
h.noduri[i] = (Nod*)malloc(sizeof(Nod));
h.noduri[i]->cheie = cheie;
h.noduri[i]->valoare = valoare;
}
}
}
void suprimare(int cheie){
int cm = cheie % MARIME;
if(h.noduri[cm]->cheie = cheie){
free(h.noduri[cm]);
h.noduri[cm] = NULL;
}else{
int i;
for(i = cm+1; i < MARIME && ((h.noduri[i] != NULL && h.noduri[i]->cheie != cheie) || h.noduri[i] == NULL); i++);
if(i == MARIME){
for(i = 0; i < cm && ((h.noduri[i] != NULL && h.noduri[i]->cheie != cheie) || h.noduri[i] == NULL); i++);
if(i == cm) return; // Elementul nu exista
else{
free(h.noduri[i]);
h.noduri[i] = NULL;
}
}else{
free(h.noduri[i]);
h.noduri[i] = NULL;
}
}
}
int cautare(int cheie){
int cm = cheie % MARIME;
if(h.noduri[cm]->cheie = cheie){
return h.noduri[cm]->valoare;
}else{
int i;
for(i = cm+1; i < MARIME && ((h.noduri[i] != NULL && h.noduri[i]->cheie != cheie) || h.noduri[i] == NULL); i++);
if(i == MARIME){
for(i = 0; i < cm && ((h.noduri[i] != NULL && h.noduri[i]->cheie != cheie) || h.noduri[i] == NULL); i++);
if(i == cm) return -1; // Elementul nu exista
else{
return h.noduri[i]->valorea;
}
}else{
return h.noduri[i]->valoare;
}
}
}