1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
--| 16/03/2012 --| Implementa un módulo genérico con el TAD lista con acceso por posición. --| Es decir, se pretende que (entre otras operaciones precisas) se pueda acceder, modificar, insertar o borrar en cualquier posición de la lista, --| indicando con un número cuál es el elemento afectado. Lógicamente estas operaciones sólo están definidas para posiciones razonables --| (sólo puedo acceder, borrar o modificar posiciones existentes, y sólo insertar en posiciones de 1 a n+1). --| Desarrolla un programa de prueba de las operaciones. with ada.text_io, ada.integer_text_io, lista_dinamica; use ada.text_io, ada.integer_text_io; procedure ada8x07 is -- Se define el tipo de datos a almacenar en cada Nodo: type datos is record num:integer; end record; --Se instancia la libreria: package listaD is new lista_dinamica(datos); use listaD; l:ptLista; temp:datos; eleccion:natural; posicion:natural; --| SOLICITA UN NÚMERO NATURAL EN UN RANGO DADO PARA LOS MENUS: --| Precondición: Se han de recibir tres parámetros de tipo natural, el primero de "in/out", y los otros dos solo "in". --| Poscondición: Se solicita un numero natural comprendido entre un rango, si el rango no es valido se repite la operación recursivamente. procedure getEleccion( e:out natural; i,f:in natural ) is begin get(e); if e not in i..f then put(" Opción no valida, pruebe de nuevo: "); getEleccion(e, i, f); end if; end getEleccion; --| SOLICITA UN NÚMERO NATURAL EN UN RANGO DADO PARA LA POSICION DEL NODO: --| Precondición: Se ha de recibir un parámetro de tipo positive como salida. Y un parámetro de tipo carácter que puede valer 'w' para inserciones, 'r' para el resto de operaciones: --| Poscondición: De forma recursiva se solicita una posición de la pila hasta que seca correcta. procedure getPosicion( p:out natural; o:in character ) is begin get(p); if not esPosValida(l, p, o) then put(" Posición no valida, pruebe de nuevo: "); getPosicion(p, o); end if; end getPosicion; --| IMPRIME EL CONTENIDO DE LA LISTA JUNTO A SU POSICION: --| Precondición: Se ha de recibir un puntero de tipo ptLista como entrada y un entero con valor de 0 o -1 para imprimir una posición de mas o no. --| Poscondición: Se imprime el contenido de la lista. procedure imprimir(l:in ptLista; s:in integer) is pos:positive := 1; temp:datos; begin new_line; if not esVacia(l) then put_line(" Contenido actual de la lista: "); new_line; put(" Números: "); while esPosValida(l, pos, 'r') loop temp := leer(l, pos); put(temp.num, width=>3); put(", "); pos := pos + 1; end loop; new_line; put(" Posicion: "); for i in 1..pos+s loop put(i, width=>3); put(", "); end loop; new_line; end if; new_line; end imprimir; begin -- Primer menú: put_line("Menu:"); put_line(" 1. Inicializar lista"); put_line(" 0. Salir"); getEleccion(eleccion, 0, 1); if eleccion = 1 then inicializar(l); put_line("Lista inicializada."); while eleccion /= 0 loop -- Segundo menú: new_line;new_line; put_line("Menu:"); put_line(" 1. Insertar"); put_line(" 2. Extraer"); put_line(" 3. Imprimir"); put_line(" 4. Borrar"); put_line(" 0. Salir"); getEleccion(eleccion, 0, 4); case eleccion is -- Insertar: when 1 => imprimir(l, 0); put(" Qué número desea insertar: "); get(temp.num); put(" Dónde: "); getPosicion(posicion, 'w'); insertar(l, posicion, temp); -- Extraer: when 2 => if esVacia(l) then put_line(" La lista esta vacia."); else imprimir(l, -1); put(" Qué posición: "); getPosicion(posicion, 'r'); extraer(l, posicion, temp); put(" Número extraido: "); put(temp.num, width=>0); end if; -- Imprimir: when 3 => if esVacia(l) then put_line(" La lista esta vacia."); else imprimir(l, -1); end if; -- Borrar: when 4 => if esVacia(l) then put_line(" La lista esta vacia."); else imprimir(l, -1); put_line(" Qué posición desea borrar: "); getPosicion(posicion, 'r'); borrar(l, posicion); end if; -- Salir: when 0 => liberar(l); when others => null; end case; end loop; end if; end ada8x07; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
--| 16/03/2012 --| ESPECIFICACIÓN DE LA LISTA DINAMICA --| PRECONDICIÓN: --| En la instanciación de la librería en el programa principal se ha de enviar el tipo de dato a almacenar. --| Se ha de comprobar en las inserciones/lecturas/extracciones que haya nodos y/o existan mediante las funciones esVacia() y esPosValida() generic -- Parámetros recibidos de la instanciación de la librería: (private - limited private) type datos is private; package lista_dinamica is -- Se definen las cabeceras (como private - limited private) de los tipos de datos que emplearan las funciones, se terminan de definir en la zona private: type ptLista is limited private; -- Se definen las cabeceras de las funciones contenidas en el fichero de implementación: procedure inicializar( l:in out ptLista ); function esVacia( l:in ptLista ) return boolean; function esPosValida( l:in ptLista; p:in natural; o:in character ) return boolean; procedure insertar( l:in out ptLista; p:in positive; d:in datos ); function leer( l:in ptLista; p:in positive ) return datos; procedure extraer( l:in out ptLista; p:in positive; d:out datos ); procedure borrar( l:in out ptLista; p:in positive ); procedure liberar( l:in out ptLista ); -- Desde la zona privada, se detalla como son las variables declaradas previamente como privadas: private type nodo; type ptNodo is access nodo; type lista; type ptLista is access lista; type nodo is record elemento:datos; siguiente:ptNodo; end record; type lista is record nodos:natural; primero:ptNodo; end record; end lista_dinamica; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 |
--| 16/03/2012 --| IMPLEMENTACIÓN DE LA LISTA DINAMICA -- El siguiente paquete permite borrar la memoria dinámica. with unchecked_deallocation; -- Funciones del paquete: package body lista_dinamica is --| INICIALIZA LA LISTA: --| Precondición: Se ha de recibir un puntero(in/out) de tipo puntero lista. --| Poscondición: Se crea una nueva lista inicializada a cero y se hace que el puntero recibido apunte a ella. procedure inicializar( l:in out ptLista ) is begin l := new lista; l.nodos := 0; l.primero := null; end inicializar; --| INDICA SI LA LISTA ESTA VACIA: --| Precondición: Se ha de recibir un puntero(in) de tipo puntero lista. --| Poscondición: Devuelve true si la lista esta vacía o false en caso contrario. function esVacia( l:in ptLista ) return boolean is begin if l.nodos > 0 then return false; else return true; end if; end esVacia; --| INDICA SI LA POSICION INDICADA EXISTE EN LA PILA: --| Precondición: Se ha de recibir un puntero(in/out) de tipo puntero lista(in), y un numero positive. --| Poscondición: Devuelve true si la posición esta en el rango de nodos usados: 1..N+1, o false en caso contrario. function esPosValida( l:in ptLista; p:in natural; o:in character ) return boolean is suma:integer := 0; begin if o = 'w' then suma := 1; end if; if p in 1..l.nodos+suma then return true; else return false; end if; end esPosValida; --| INSERTA UN NUEVO NODO EN LA LISTA: --| Precondición: Se ha de recibir un puntero(in/out) de tipo puntero lista, un numero positive para indicar la posicion(in), y los datos a insertar(in). --| Poscondición: Inserta el nuevo Nodo en la posición indicada, desplazando al que estuviese en esa posición a la derecha. procedure insertar( l:in out ptLista; p:in positive; d:in datos ) is temp:ptNodo := new nodo; ant:ptNodo := l.primero; pos:positive := 1; begin temp.elemento := d; if p = 1 then if l.nodos = 0 then temp.siguiente := null; l.primero := temp; else temp.siguiente := l.primero; l.primero := temp; end if; else while pos < p-1 loop ant := ant.siguiente; pos := pos + 1; end loop; if p = l.nodos+1 then temp.siguiente := null; else temp.siguiente := ant.siguiente; end if; ant.siguiente := temp; end if; l.nodos := l.nodos + 1; end insertar; --| LEE LOS DATOS DE UN NODO DE LA LISTA: --| Precondición: Se ha de recibir un puntero(in/out) de tipo puntero lista, y un numero positive(in). La posición ha de ser valida, puede comprobarse mediante esPosValida() --| Poscondición: Devuelve la información de la posición indicada. function leer( l:in ptLista; p:in positive ) return datos is ant:ptNodo := l.primero; pos:positive := 1; begin while pos < p loop ant := ant.siguiente; pos := pos + 1; end loop; return ant.elemento; end leer; --| EXTREA LOS DATOS DE UN NODO DE LA LISTA: --| Precondición: Se ha de recibir un puntero(in/out) de tipo puntero lista, un numero positive para indicar la posicion(in), y los datos a extraer(out). La posición ha de ser valida, puede comprobarse mediante esPosValida() --| Poscondición: Extrae la información de la posición indicada. procedure extraer( l:in out ptLista; p:in positive; d:out datos ) is procedure liberar is new unchecked_deallocation(nodo,ptNodo); temp:ptNodo; ant:ptNodo := l.primero; pos:positive := 1; begin while pos < p-1 loop -- Revisar ant := ant.siguiente; pos := pos + 1; end loop; d := ant.siguiente.elemento; temp := ant.siguiente; ant.siguiente := ant.siguiente.siguiente; liberar(temp); l.nodos := l.nodos - 1; end extraer; --| BORRA UN NODO DE LA LISTA: --| Precondición: Se ha de recibir un puntero(in/out) de tipo ptLista y un numero positive(in) indicando el nodo a borrar. La posición ha de ser valida, puede comprobarse mediante esPosValida() --| Poscondición: Se elimina el Nodo indicado de la Pila. procedure borrar( l:in out ptLista; p:in positive ) is procedure liberar is new unchecked_deallocation(nodo,ptNodo); temp:ptNodo; ant:ptNodo := l.primero; pos:positive := 1; begin while pos < p-1 loop -- Revisar ant := ant.siguiente; pos := pos + 1; end loop; temp := ant.siguiente; ant.siguiente := ant.siguiente.siguiente; liberar(temp); l.nodos := l.nodos - 1; end borrar; --| LIBERA TODA LA MEMORIA EMPLADA POR LA PILA: --| Precondición: Se ha de recibir un puntero(in/out) de tipo puntero lista. --| Poscondición: Se borran todos los nodos recursivamente y al terminar se borra la pila. procedure liberar( l:in out ptLista ) is procedure liberar is new unchecked_deallocation(nodo,ptNodo); procedure liberar is new unchecked_deallocation(lista,ptLista); temp:ptNodo; begin if l.primero /= null then temp := l.primero; l.primero := l.primero.siguiente; liberar(l); liberar(temp); else liberar(l); end if; end liberar; end lista_dinamica; |