Guia

COMPUTACION Y PROGRAMACION

5 ESTRUCTURAS DE DATOS
5.1 INTRODUCCION Uno de los elementos fundamentales del desarrollo de la solución a un problema es la abstracción que se debe hacer sobre las estructuras de datos que mejor se adaptan a la representación de dicho problema. Es más, la decisión sobre las estructuras de datos a utilizar puede ser estratégicamente relevante, al punto de lograr nosólo una buena solución sino incluso de lograr una.

Mundo Real

0 12

1 23

n

3 n

1 2 m

Prob lema a Modelar

Estructuras de Datos Disp onib les

Existe algunas estructuras de datos básicas, fundamentalmente aquellas basadas en las listas y aquellas basadas en los árboles. Para determinar cuál estructura es más conveniente para un determinado problema es necesario determinarcuáles son las operaciones más típicas sobre cada estructura de datos, es así como, para las listas, las operaciones más típicas son la búsqueda y el ordenamiento, en el caso de los árboles, los principales procesos son los de creación y caminamiento (recorrido) de un árbol. 5.1 LA ESTRUCTURA DE DATOS ARREGLO (ARRAY). Una variable con estructura de arreglo es una 'colección de variables componentesdel mismo tipo', con la característica de que cada variable (componente) individual de un arreglo es denotable explícitamente y directamente accesible, y que el número de sus componentes se fija cuando el arreglo es definido, y permanece inalterable durante la ejecución del programa. 5.1.1 Búsqueda en un arreglo La búsqueda de un componente del arreglo se puede definir como: dado un arreglo concomponentes A[1], ... , A[n]; y un valor x, buscar en el arreglo por algún componente A[k] que tenga almacenado el valor x. Si ese componente existe, usar una variable booleana q para almacenar el valor true y una variable i para almacenar el valor del índice k, si no es así, fijar el valor de q en false.

Javier Vidal Valenzuela

45

COMPUTACION Y PROGRAMACION

program busqueda1; constn=10; type arreglo=array[1..n] of integer; var a : arreglo; k, datoBuscado : integer; procedure leeArreglo (var a : arreglo); var i : integer; begin for i:=1 to n do read(a[i]); end; function buscaElemento (x : integer; a : arreglo):integer; var i : integer; q : boolean; begin i := 0; q := false; repeat i := i+1; q := (a[i] = x); until (q or (i = n)); if (q) then buscaElemento := i elsebuscaElemento := -1; end; begin leeArreglo(a); write ('Ingrese dato a buscar:'); read (datoBuscado); k := buscaElemento(datoBuscado, a); if (k -1) then write (datoBuscado,' encontrado en posici¢n ',k) else write (datoBuscado,' no fue encontrado'); end. La condición de término de este programa es la unión lógica de las condiciones q e i = n. Una técnica común para acelerar el algoritmo es simplificar lacondición compuesta es: i) Extender el arreglo A en un elemento. ii) Al nuevo (último) componente se le asigna el valor x que actuará como un centinela para el fin de la búsqueda. program busqueda2; const n=10; type arreglo=array[1..n+1] of integer; var a : arreglo; k, datoBuscado : integer; procedure leeArreglo (var a : arreglo); ... end; function buscaElemento (x : integer; a : arreglo) : integer;var i : integer; begin

Javier Vidal Valenzuela

46

COMPUTACION Y PROGRAMACION

i := 0; a[n+1] := x; repeat i := i+1; until (a[i]=x ); buscaElemento := i end; begin leeArreglo(a); write ("Ingrese dato a buscar:"); read (datoBuscado); k := buscaElemento(datoBuscado, a); if (k x; por razones análogas, una búsqueda posterior deberá restringirse al

subarreglo izquierdo. Esta estrategia debúsqueda se conoce como Búsqueda Binaria. program busqueda3; const n=10; type arreglo=array[0..n-1] of integer; var a: arreglo; procedure leeArreglo (var a:arreglo); ... function busquedaBinaria (x:integer;a:arreglo):integer; var i, j, k:integer;

Javier Vidal Valenzuela

47

COMPUTACION Y PROGRAMACION

begin i:=0; j:=n-1; k:=(i+j) div 2; while (a[k] x and i x) then j := k - 1 else i...