Enginyeria en Informàtica (3371)

Estructures de Dades i de la Informació I(12413) 

Tema 1:Tipus abstracte de dades (TAD)

Definició.
Exemples.

Tema 2: Llistes

Implementació mitjançant arrays.
Implementació mitjançant llistes enllaçades. 
Llistes doblement enllaçades.
Llistes lliures.
Comparació.

Tema 3: Piles

Implementació mitjançant taules ( arrays).
Implementació mitjançant llistes enllaçades.

Tema 4: Cues

Implementació mitjançant taules ( arrays).
Implementació mitjançant llistes enllaçades.
Circular.

Tema 5: Arbres

Definicions.
Recorreguts (preordre-postordre).
Implementació mitjançant taules ( arrays).
Implementació mitjançant punters.
Arbre de cerca binària.
Monticles ( heaps) i cues de prioritat.
Arbres AVL.
Arbres B.
Codificació Huffman.

Tema 6: Grafs

Definicions.
Implementació.
Recorreguts.
Cerca.
Camins mínims.
Cost mínim.
Prim.
Kruskal.

Tema 7: Hashing

Conceptes.
Implementacions de funcions hash.
Taules hash.
Col·lisions.
Hashing doble.  

Tema 8: Fitxers

Seqüencials.
D'accés aleatori.
Cerca en fitxers.
Índexs.

Bibliografia

AHO, A.V. i d’altres. Data Structures and Algorithms. Addison-Wesley, 1983.
AMSBURY, W. Data Structures, from arrays to priority queues. Wadsworth, 1985.
CORMEN, LEISERSON, RIVEST: Introduction to Algorithms. MIT Press, 1990.
FLAMIG, B. Practical Data Structures in C++. Wiley and Sons, 1993.
FRAKES, B.; BAEZA-YATES, R. Information Retrieval: Data Structures and Algorithms. Prentice Hall, 1992.
HOROWITZ, E.; SAHNI, S. Fundamentals of Data Structures. Computer Science Press, 1983.
KORSH, J.; GARRET, L. Data Structures, Algorythms and Program Style Using C. PWS Kent Publishing, 1988
MORET, SHAPIRO: Algorithms from P to NP. Benjamin Cummings, 1991.
PLUM, T. Reliable Data Structures in C. Plum Hall, 1985
WEISS, M. Data Structures and Algorithm Analysis in C. Benjamin Cummings, 1993.
WIRTH, N. Algorithms + Data Structures = Programs. Prentice Hall, 1980.