Tesis doctoral de Iñaki Varela Legarreta
Un array o matriz bidimensional tradicional es una estructura utilizada para el almacenamiento de informacion homogenea dispuesta en forma tabular, que garantiza el acceso inmediato a cada elemento de la misma en base a dos indices que referencian su posicion. Esta estructura presenta los problemas siguientes: su naturaleza estatica exige prefijar su dimensionamiento previamente a la incorporacion de los elementos; la definicion de las series de indices tiene restricciones que derivan en la infrautilizacion del espacio; se producen anomalias por accesos incorrectos con indices fuera de su rango; y el desperdicio de espacio en memoria originado, para matrices con un bajo porcentaje de ocupacion, junto con tiempos de respuesta elevados en procesos de recorrido. En este trabajo de investigacion se ha diseñado una nueva estructura: el array bidimensional dinamico (abd), que es un tipo abstracto de datos construido en base a punteros, lo que determina su caracter versatil. Esta estructura supera todos los inconvenientes del array estatico, permitiendo ademas su reajuste dinamico en tiempo de ejecucion en funcion de las actualizaciones de sus componentes. El mayor rendimiento se obtiene en matrices poco densas debido a la reduccion en el espacio de almacenamiento y en el tiempo de ejecucion de los procesos, al no existir posiciones reservadas inutilizadas. En primer lugar, se ha implementado el abd en base a listas enlazadas ortogonales, constituyendo una red de listas dobles con insercion al final entrelazadas para representar los elementos y listas simples para los indices. En las listas, la busqueda de un componente presenta un orden o(n), lo que significa que el tiempo es proporcional al numero de elementos procesados. Los tratamientos de busqueda intervienen en bastantes operaciones de manejo de la estructura, por lo que para mejorar su rendimiento se ha diseñado una segunda implementacion del abd utilizando arboles binarios de b
Datos académicos de la tesis doctoral «Diseño de un array bidimensional dinamico implementado mediante listas enlazadas y arboles avl.«
- Título de la tesis: Diseño de un array bidimensional dinamico implementado mediante listas enlazadas y arboles avl.
- Autor: Iñaki Varela Legarreta
- Universidad: Deusto
- Fecha de lectura de la tesis: 01/01/1995
Dirección y tribunal
- Director de la tesis
- Maximo Llaguno Ellacuria
- Tribunal
- Presidente del tribunal: Francisco Javier Zubillaga Zubimendi
- Juan Pazos Sierra (vocal)
- José Luis Maté Hernández (vocal)
- Juan Luis Gutierrez Gonzalez (vocal)
