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 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 | /* 6x02-Lista_enlazadas_desordenadas 01/02/2012 Repite el ejercicio anterior usando una lista (no ordenada), que implemente una operación de ordenarLista. Se almacenarán los números desordenados en la lista y luego se aplicará la operación implementada. */ // Estructuras de datos: struct SORTEO { int numero; // Numero de boleto int cuantia; // Importe del premio }; struct NODO { struct SORTEO elemento; // Información contenida en cada nodo de la lista. struct NODO *puntero; // Puntero al siguiente nodo de la lista. }; // Constantes: #define NUMEROS 10 // Librerias: #include <stdio.h> #include <stdlib.h> #include <time.h> //#include "listas.h" // FUNCION QUE INSERTA NODOS AL FINAL DE LA LISTA: void listaInsertAlFinal( struct NODO **lista, struct SORTEO *cupon ) { /* Precondición: Se ha de recibir un puntero de tipo struct NODO al primer nodo de la lista. Este podrá valer NULL la primera vez o la dirección de memoria que corresponda. El puntero además es un "doble puntero" ya que es necesario poder modificarlo. También se ha de recibir un puntero a una estructura de tipo SORTEO con la información a insertar en la lista. Poscondición: Se inserta la información contenida en "cupon" en un Nodo nuevo perteneciente a "lista", la inserción se realiza siempre al final de la lista. */ struct NODO *temp = (struct NODO *)malloc(sizeof(struct NODO)); // Se define un puntero temporal de tipo NODO que apunta a la memoria solicitada al sistema. struct NODO *anterior = NULL; // Se crea otro puntero de tipo NODO, este apuntando a NULL struct NODO *siguiente = *lista; // Y un tercer puntero de tipo NODO que apunta al primer nodo de la lista. // En la primera inserción "lista" no apuntara a nada, por lo que se inserta el primer nodo y se hace que "lista" apunte a él. if( *lista == NULL ) { temp->elemento = *cupon; temp->puntero = NULL; *lista = temp; } // Cuando la lista ya tenga un elemento... else { // Se recorren todos los Nodos de la lista hasta llegar al final. while( siguiente != NULL ) { anterior = siguiente; siguiente = siguiente->puntero; }; // Se agrega el nuevo Nodo al final de la lista. if( siguiente == NULL ) { temp->elemento = *cupon; // Se guarda la estructura de datos (cupon) en la estructura del nuevo Nodo. temp->puntero = NULL; // Como la inserción es al final de la lista el puntero del Nodo no a puntara a ningún otro Nodo. anterior->puntero = temp; // Se modifica el puntero del Nodo anterior para que apunte al nuevo Nodo. }; }; }; // FUNCION QUE ORDENA LOS NODOS DE UNA LISTA DE FORMA ASCENDENTE: void listaOrdenarAscendente( struct NODO **lista ) { /* Precondición: Se ha de recibir un puntero de tipo struct NODO al primer nodo de la lista. Este podrá valer NULL la primera vez o la dirección de memoria que corresponda. Poscondición: La función se encarga de ordenar de forma ascendente cada Nodo de la lista según el numero de cupón que contengan dichos nodos. El método usado para ordenar los nodos es mediante el método de la burbuja, de modo que se necesitan dos bucles, el segundo se encarga de ordenar el nodoA y el nodoB en la primera iteración, después el nodoB y el nodoC en la segunda iteración, luego el nodoC y el nodoD, etc. de modo que se van arrastrando los números pequeños hacia el principio de la lista, una vez recorrida entera el segundo bucle se encarga de recorrerla de nuevo, así tantas veces como nodos tiene la lista. Finalmente la lista queda ordenada completamente. Esquema gráfico: http://goo.gl/I54uV */ struct NODO *p_nodoAnt2_nodoAnt1 = NULL; // Es(sera) el puntero del puntero que apunta al nodoA (es necesario para modificar el puntero que apunta a A) struct NODO *p_nodoAnt1_nodoA = *lista; // Es el puntero que apunta al nodoA struct NODO *p_nodoA_nodoB = p_nodoAnt1_nodoA->puntero; // Es el puntero del nodoA y apunta al nodoB struct NODO *p_nodoB_sig = p_nodoA_nodoB->puntero; // Es el puntero del nodoB que apunta al siguiente nodo. struct NODO *temporal = NULL; // Puntero temporal de intercambio. struct NODO *iteracion = *lista; // Es el puntero que va avanzando en la lista en cada iteración del primer bucle, es necesario para saber cuando detener el bucle. int salirBucle1; // Variables "booleanas" para indicar cuando se ha de salir de los bucles. int salirBucle2; // Si la lista contiene Nodos se ordenan: if( *lista != NULL ) { salirBucle1 = 0; // La lista se ha de recorrer tantas veces como Nodos tenga: while( !salirBucle1 ) { // Si "iteracion" es NULL se cambia el estado de "salirBucle1" para salir del primer bucle una vez se haya hecho una ultima vez el bucle 2. // En caso contrario iteración avanza un nodo de la lista. if( iteracion == NULL ) salirBucle1 = 1; else iteracion = iteracion->puntero; salirBucle2 = 0; // Cada vez que se recorre la lista se ordenan dos Nodos: while( !salirBucle2 ) { // Si se va a ordenar el primer Nodo con el segundo... if( p_nodoAnt1_nodoA == *lista ) { // Si el NodoA es mayor que el nodoB, se cambian de orden: if( p_nodoAnt1_nodoA->elemento.numero > p_nodoA_nodoB->elemento.numero ) { // Se intercambia el NodoA con el NodoB: *lista = p_nodoA_nodoB; temporal = p_nodoB_sig; p_nodoA_nodoB->puntero = p_nodoAnt1_nodoA; p_nodoAnt1_nodoA->puntero = temporal; // Se actualizan los punteros para que cada uno apunte segun su nombre correspondiente: p_nodoAnt1_nodoA = *lista; p_nodoA_nodoB = p_nodoAnt1_nodoA->puntero; p_nodoB_sig = p_nodoA_nodoB->puntero; }; } // Si se van a ordenar nodos intermedios de la lista... else if( p_nodoB_sig != NULL ) { if( p_nodoAnt1_nodoA->elemento.numero > p_nodoA_nodoB->elemento.numero ) { // Se intercambian los punteros: p_nodoAnt2_nodoAnt1->puntero = p_nodoA_nodoB; temporal = p_nodoB_sig; p_nodoA_nodoB->puntero = p_nodoAnt1_nodoA; p_nodoAnt1_nodoA->puntero = temporal; // Se actualizan los punteros para que cada uno apunte segun su nombre correspondiente: p_nodoAnt1_nodoA = p_nodoAnt2_nodoAnt1->puntero; p_nodoA_nodoB = p_nodoAnt1_nodoA->puntero; p_nodoB_sig = p_nodoA_nodoB->puntero; }; } // Si se va a ordenar el penultimo y ultimo nodo... else if( p_nodoB_sig == NULL ) { if( p_nodoAnt1_nodoA->elemento.numero > p_nodoA_nodoB->elemento.numero ) { // Se intercambian los punteros: p_nodoAnt2_nodoAnt1->puntero = p_nodoA_nodoB; p_nodoA_nodoB->puntero = p_nodoAnt1_nodoA; p_nodoAnt1_nodoA->puntero = NULL; // Se actualizan los punteros para que cada uno apunte segun su nombre correspondiente: p_nodoAnt1_nodoA = p_nodoAnt2_nodoAnt1->puntero; p_nodoA_nodoB = p_nodoAnt1_nodoA->puntero; p_nodoB_sig = NULL; } // Ya se han ordenado los dos últimos Nodos y ahora se para el bucle2: salirBucle2 = 1; }; // Mientras el nodoB siga apuntando a otro nodo, se modifican todos los punteros para que apunten al siguiente nodo: if( p_nodoB_sig != NULL ) { p_nodoAnt2_nodoAnt1 = p_nodoAnt1_nodoA; p_nodoAnt1_nodoA = p_nodoAnt1_nodoA->puntero; p_nodoA_nodoB = p_nodoA_nodoB->puntero; p_nodoB_sig = p_nodoB_sig->puntero; }; }; // Fin primer bucle // Al parar el segundo bucle hay que resetear los punteros al valor original. p_nodoAnt2_nodoAnt1 = NULL; p_nodoAnt1_nodoA = *lista; p_nodoA_nodoB = p_nodoAnt1_nodoA->puntero; p_nodoB_sig = p_nodoA_nodoB->puntero; }; // Fin segundo bucle };// Fin del if }; // fin de la funcion // FUNCION QUE LIBERA LA MEMORIA USADA POR UNA LISTA: void listaLiberaRam( struct NODO **lista ) { /* Precondición: Se ha de recibir un puntero de tipo struct NODO al primer nodo de la lista. Poscondición: Se borran todos los nodos de esa lista hasta llegar a NULL. */ struct NODO *actual, *siguiente; actual = *lista; while(actual != NULL) { siguiente = actual->puntero; free(actual); actual = siguiente; }; *lista = NULL; }; // Función que genera números aleatorios con sus premios aleatorios respectivos y los guarda en "fichero.dat": void generaDat() { /* Poscondición: La función se encarga de generar estructuras con números aleatorios que son guardados en un fichero secuencial. El numero de estructuras a guardar viene dado por la constante NUMEROS. */ FILE *ficheroBin = fopen( "sorteo.dat", "w" ); struct SORTEO cupon; int i; srand((unsigned int)time(NULL)); for( i=0; i < NUMEROS; i++ ) { cupon.numero = rand()%100000; cupon.cuantia = rand()%1000; fwrite( &cupon, sizeof(struct SORTEO), 1, ficheroBin ); }; fclose( ficheroBin ); }; // Funciona que pasa el contenido de "fichero.dat" a "fichero.txt": void mostrarDat() { /* Poscondición: Se pasa todo el contenido del fichero secuencial a un fichero de texto. */ FILE *ficheroBin = fopen( "sorteo.dat", "r" ); FILE *ficheroText; struct SORTEO cupon; if( ficheroBin == NULL ) printf( "Genere rimero el fichero \"sorteo.dat\"\n" ); else { ficheroText = fopen( "sorteo.txt", "w" ); fread( &cupon, sizeof(struct SORTEO), 1, ficheroBin ); while( !feof(ficheroBin) ) { fprintf( ficheroText, "%i\t%i\n", cupon.numero, cupon.cuantia ); fread( &cupon, sizeof(struct SORTEO), 1, ficheroBin ); }; fclose( ficheroBin ); fclose( ficheroText ); }; }; main() { struct NODO *lista = NULL; struct NODO *temp; struct SORTEO cupon; FILE *fichOriginal, *fichOrdenDat, *fichOrdenTxt; char opcion; printf( "Eliga una opcion:\n" ); printf( "1. Ordenar el fichero \"sorteo.dat\" mediante listas\n" ); printf( "2. Generar \"sorteo.dat\"\n" ); printf( "3. Pasar fichero \"sorteo.dat\" a \"sorteo.txt\"\n" ); do{ scanf( "%c", &opcion ); } while( opcion < '1' || opcion > '3' ); if( opcion == '2' ) generaDat(); else if( opcion == '3' ) mostrarDat(); else if( opcion == '1' ) { fichOriginal = fopen("sorteo.dat", "r"); // Se comprueba que el fichero secuencial con el que se ha de trabajar exista: if( fichOriginal == NULL ) printf( "Necesita el fichero \"sorteo.dat\", generelo primero\n" ); else { // Se recorre cada estructura del fichero secuencial y se inserta en una estructura de datos dinamica de tipo lista: fread( &cupon, sizeof(struct SORTEO), 1, fichOriginal ); while( !feof(fichOriginal) ) { listaInsertAlFinal( &lista, &cupon ); // Se crea un nuevo nodo para el estruct leido y se inserta en la lista. fread( &cupon, sizeof(struct SORTEO), 1, fichOriginal ); // Se lee la siguiente estructura de datos a guardar en la lista. }; fclose(fichOriginal); // Se ordena la lista: listaOrdenarAscendente( &lista ); // Se imprime el contenido de la lista en unos ficheros: fichOrdenDat = fopen("sorteoOrdenado.dat", "w"); fichOrdenTxt = fopen("sorteoOrdenado.txt", "w"); temp = lista; while( temp != NULL ) { fwrite( &temp, sizeof(struct SORTEO), 1, fichOrdenDat ); fprintf( fichOrdenTxt, "%i\t%i\n", temp->elemento.numero, temp->elemento.cuantia ); temp = temp->puntero; }; fclose(fichOrdenDat); fclose(fichOrdenTxt); // Ya se ha finalizado el programa, pero antes de terminar del todo hay que liberar toda la memoria RAM usada: listaLiberaRam( &lista ); }; }; printf( " Operación finalizada.\n" ); }; |
6×02: Lista desordenada
