Estructuras de Datos y Algoritmos (EDA)

Están disponibles en este enlace los ejercicios sobre los que trabajaremos en las clases del 18 y del 21 de octubre.

Haz clic en el cuadro negro de arriba para que empiece…

Directamente desde la Universidad de Stanford. Recomendable además leer el documento sobre “punteros y memoria” de la misma Universidad.

Un registro, en programación, es un tipo de dato estructurado formado por la unión de varios elementos bajo una misma estructura. Estos elementos pueden ser, o bien datos elementales (entero, real, carácter,…), o bien otras estructuras de datos. A cada uno de esos elementos se le llama campo.

Un registro se diferencia de un vector en que éste es una colección de datos iguales, es decir, todos del mismo tipo, mientras que en una estructura los elementos que la componen, aunque podrían serlo, no tiene porque ser del mismo tipo. (Wikipedia)

En el caso del lenguaje Java, el equivalente a los campos de un registro son los atributos o campos de los objetos de una clase.

En la notación algorítmica utilizada en clase, un tipo registro se declara así:

  tipo fecha = registro 
                 elDía:día;
                 elMes:mes;
                 elAño:natural
               freg
 

Se declaran variables así:

  variable aniversario:fecha 
 

Y se utilizan así:

  principio
    aniversario.elDía:=1;
    aniversario.elMes:=oct; {el tipo mes se ha definido por enumeración, como 
                             mes=(ene,feb,mar,abr,may,jun,jul,ago,sep,oct,nov,dic)}
    aniversario.elAño:=2011;
    ...
    aniversario.elDía:=aniversario.elDía+1;
    ...

Se ha publicado en la sección de material adicional una colección de enunciados de ejercicios de diseño e implementación de TAD’s arborescentes y otros ejercicios sobre árboles extraídos de la bibliografía.

Se ha publicado en la sección de material adicional una colección de enunciados de ejercicios sobre TAD’s lineales.

Texto extraído de Wikipedia:

In computer science, a tagged union, also called a variant, variant record, discriminated union, or disjoint union, is a data structure used to hold a value that could take on several different, but fixed types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which one is in use. It can be thought of as a type which has several “cases,” each of which should be handled correctly when that type is manipulated. Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.
Tagged unions are most important in functional languages such as ML and Haskell, where they are called datatypes (see algebraic data type) and the compiler is able to verify that all cases of a tagged union are always handled, avoiding many types of errors. They can, however, be constructed in nearly any language, and are much safer than untagged unions, often simply called unions, which are similar but do not explicitly keep track of which member of the union is currently in use.

La sintaxis en Ada puede verse aquí.

Haz clic en el cuadro negro de arriba para que empiece…

Directamente desde la Universidad de Stanford.

Se ha publicado en la sección de material adicional una colección de enunciados de ejercicios sobre especificación algebraica.

Se debe escribir la especificación algebraica del TAD genérico “multiconjunto de elementos” que aparece en el enunciado de la práctica 1, con las operaciones: vacío, poner, esVacío, quitar, pertenece, frecuencia, unión, cardinal, diferencia y esSubconjunto, indicando además a qué clase pertenece cada operación (generadora/modificadora/observadora).