Programmi C/C++ - prof.Claudio Maccherani

Programmi C / C++ - prof. Claudio Maccherani - Perugia - 2008
Gestione Archivio SEQUENZIALE con INDICE
(con gestione Dizionario/Indice 'casareccia', fatta direttamente da programma)

In un archivio sequenziale con indice (o index sequential) si accede al record fornendo il valore di una chiave alfanumerica. È anche possibile l’accesso sequenziale, secondo l’ordinamento della chiave (prima, seguente, ultima, precedente). La chiave viene gestita in una struttura a parte, detta Indice o Dizionario, che contiene le chiavi logicamente ordinate e i puntatori ai record dell’Archivio Dati. Esistono vari metodi di gestione del file Indice/Dizionario: Indice Statico a uno o più livelli, come l’ISAM (Indexed Sequential Acces Method) della IBM; Indice Dinamico basato su strutture B-Tree, estensioni dell’ABR (Albero Binario di Ricerca), quali B-Albero, B*-Albero, B+_Albero.

Il presente programma realizza una versione semplificata e 'casareccia' di organizzazione Sequenziale con Indice, utilizzando due archivi ad accesso diretto (random), uno per l'Archivio Dati e uno per il Dizionario (oltre ad un file di appoggio con i numeri totali di record attivi). Il Dizionario viene mantenuto fisicamente ordinato - ordine crescente - sul valore della chiave. Per la ricerca delle chiavi nel Dizionario si utilizza la Ricerca Binaria.

FileIndexSeq.exe

[ per eseguire il programma creare una cartella in locale e copiarcelo ]

L'archivio Dati "FileIndexSeq.dat" contiene 'studenti' con record così strutturati:

+------+------+-------+--------+---------+-------+-------+-------+

+------+------+-------+--------+---------+-------+-------+-------+

(dove 'flag'=1-record occupato, 0-record libero)

Il Dizionario o Indice "FileIndexSeq.diz" contiene le chiavi ordinate in ordine crescente e i puntatori all'archivio dati:

+------+-----+

| key | pun |

+------+-----+

Il file "FileIndexSeq.tot", sequenziale, contiene il numero totale di record del file dati [TotDat] ed il numero di record del dizionario [TotDiz].

Nel Dizionario - "diz" - le chiavi vengono reperite utilizzando la RICERCA BINARIA.

// Registrazione nuova chiave "key" nel record "r" del dizionario.

// metodo 'lento': la chiave si memorizza in fondo e poi il dizionario viene riordinato.

strcpy(diz.key,key); diz.pun = pun; TotDiz++;

rr = fseek(fd,sizeof(recdiz) * TotDiz,SEEK_SET);

fwrite(&diz,sizeof(recdiz),1,fd);

// ordinamento dizionario (con Bubble Sort)

bool scambio; recdiz diz1,diz2; int r1,po1,r2,po2;

do { scambio = false;

for (int i = 1; i < TotDiz; i++ ) {

po1 = sizeof(recdiz) * i; r1 = fseek(fd,po1,SEEK_SET);

fread(&diz1,sizeof(recdiz),1,fd); // lettura record i

po2 = sizeof(recdiz) * (i+1); r2 = fseek(fd,po2,SEEK_SET);

fread(&diz2,sizeof(recdiz),1,fd); // lettura record i+1

if (strcmp(diz1.key,diz2.key) > 0)

{ r1 = fseek(fd,po1,SEEK_SET); fwrite(&diz2,sizeof(recdiz),1,fd);

r2 = fseek(fd,po2,SEEK_SET); fwrite(&diz1,sizeof(recdiz),1,fd);

scambio = true; } } }

while (scambio == true);

// metodo 'veloce': si ricerca il posto con la ricerca binaria, si spostano i record successivi di una posizione in basso, si memorizza. Il programma usa questo, qui non riportato (qualcosa dovete fare anche voi).

// Ricerca di una chiave "key" nel dizionario con Ricerca Binaria ricorsiva.

int RicBin(char key[31],int i1,int i2,char flag) {

int r,rr,pos;

if (i1 > i2) return 0; // chiave non trovata

r = (i1+i2)/2;

pos = sizeof(recdiz) * r; rr = fseek(fd,pos,SEEK_SET);

fread(&diz,sizeof(recdiz),1,fd); // lettura record r

if (strcmp(diz.key,key) == 0) // trovato

return r;

if (strcmp(diz.key,key) > 0) // maggiore

RicBin(key,i1,r-1,flag);

else // minore

RicBin(key,r+1,i2,flag); }

// Cancellazione di una chiave: si cerca la chiave, la si cancella, si ricompatta il dizionario (spostando in alto di 1 posizione i record successivi a quello cancellato).