Apropament a les estructures de dades des del programari lliure

Abstract

La informàtica, o, més precisament, els programes, gestionen informació, una gran quantitat d’informació. Aquesta informació s’ha d’emmagatzemar a la memòria de l’ordinador o en mitjans d’emmagatzemament persistents (com ara un disc) de manera que s’hi pugui accedir tan eficientment com sigui possible. Les estructures de dades miren de resoldre aquest problema. Osigui, cerquen com estructurar la informació de manera que l’accés a ella sigui eficient. D’aquesta manera, podem pensar en una estructura de dades com una col.lecció de dades emmagatzemades amb una certa gràcia en un mitjà (típicament, la memòria de l’ordinador o el disc) de manera que sigui senzill d’accedir-hi. Però com accedim a una estructura de dades? Doncs, depenent de què signifiquin i per a què volem fer servir les dades d’aquella estructura. Si l’estructura representa la cua d’una pastisseria, en tot moment necessitarem accedir al primer de la cua i necessitarem afegir els nous clients al final de la cua. Si representa un diccionari (una col.lecció de paraules amb la seva definició, sinònims i exemples d’ús), no ens interessa per a res saber quina paraula és la primera. En canvi, voldrem trobar ràpidament tota la informació associada a una paraula determinada. Si l’estructura representa una xarxa de carreteres, la informació que li demanarem serà: quines són les ciutats veïnes de Lleida a la xarxa de carreteres? Veiem, doncs, que apareixen diferents estructures de dades segons l’ús que vulguem fer d’aquelles dades. En aquest llibre estudiarem algunes d’aquestes estructures de dades: les llistes (i les seves parentes, les cues i les piles), els arbres i les taules. Totes aquestes estructures de dades viuran a la memòria principal. Pràcticament no direm res de les estructures de dades en memòria persistent (fitxers i bases de dades). Aquest material serveix de base per a l’assignatura d’Estructures de Dades impartida al tercer quadrimestre del grau en Enginyeria Informàtica que s’ofereix a l’Escola Politècnica Superior de la Universitat de Lleida.