archivi sequenziali

Materie:Appunti
Categoria:Informatica

Voto:

2 (2)
Download:88
Data:09.03.2006
Numero di pagine:2
Formato di file:.doc (Microsoft Word)
Download   Anteprima
archivi-sequenziali_1.zip (Dimensione: 4 Kb)
trucheck.it_archivi-sequenziali.doc     23.5 Kb
readme.txt     59 Bytes


Testo

ARCHIVI SEQUENZIALI:
Gli archivi sequenziali possono essere ordinati o non ordinati rispetto ad una chiave di riferimento.
Gli archivi sequenziali vengono di solito utilizzati per archivi costituiti da pochi record, poiche' per archivi di grandi dimensioni il tempo di ricerca diventa eccessivamente lungo.
Ipotizziamo di avere un archivio costituito da N record.
DEF. RECORD LOGICO: si definisce record logico la struttura di riferimento di uno specifico archivio, cioe' il formato in byte del tracciato record.
DEF.RECORD FISICO: si definisce record fisico la quantita' di memoria di massa trasferibile in memoria centrale con una sola operazione di lettura/scrittura (tale record fisico puo' contenere uno o piu' record logici). Un record fisico viene anche indicato con il termine pagina o blocco logico. Di solito una pagina e' dell'ordine di 2k Byte o di 4k Byte.
TEMPI DI COMPUTAZIONE DEGLI ARCHIVI SEQUENZIALI:
Il tempo di computazione o ordine di computazione si indica con O(N) e rappresenta il numero di confronti fra la chiave di riferimento (variabile di appoggio) e il valore della chiave dell'archivio.
Variabile appoggio FILE-DATI
1
2
3
N
IPOTESI:
- Consideriamo un archivio con N Record
- Consideriamo il RECORD FISICO corrispondente al RECORD LOGICO e sviluppiamo la seguente
tabella:
TABELLA DI RICERCA CON O SENZA SUCCESSO PER GLI ARCHIVI SEQUENZIALI:
TIPI DI ARCHIVI
RICERCA OTTIMA
RICERCA MEDIA
RICERCA PEGGIORE
RICERCA SENZA SUCCESSO
Archivi Sequenziali non ordinati
O(1)
O((N+1)/2)
O(N)
O(N+1)
Archivi sequenziali ordinati
O(1)
O(Log(N)/2)
O(Log(N))
O(Log(N)+1)
NOTA:
- Con Log(N) si intende logaritmo in base 2.
- Per gli archivi ordinati si effettua la ricerca binaria o dicotomica.
ok

Esempio