lunes, 22 de noviembre de 2010

.: Listas Vinculadas :.

:: Listas Enlazadas y sus Procesos ::



Materia. Lenguajes de Programación
Hora. M1 - M3 (Martes)

Aquí me dedicaré a comentar algo sobre el trabajo o las acciones realizadas con el proyecto de listas que use el semestre pasado ya modificado.
Primero comentaremos las variables presentes es la estructura de la lista:
  • ID. Funciona como la matricula del alumno.
  • Name. Es el nombre del alumno.
  • Facu. Almacena el nombre de la facultad del alumno.
  • Carr. Contiene el nombre de la carrera que cursa el alumno.
  • Sem. Variable que contiene el semestre que cursa el alumno en ese momento.
Definición de la Estructura.
Obviamente, primero se define lo que es la estructura de tipo NODO para hacer referencia a cada nodo presente en la lista.
#define TAM 80
typedef struct nodo {
  int ID,Sem;
  char Name[TAM];
  char Facu[TAM];
  char Carr[TAM];

  struct nodo *next; ---->> Punto para enlace al nodo anterior
  struct nodo *prev; ---->> Punto para enlace al nodo siguiente
} NODO;
Ingreso de Registros Nuevos: Nodos Nuevos
Para este proceso, que es el principal, tenemos la función CrearNodo donde usamos un puntero Q que se posiciona en la parte inicial de la lista.

NODO *CrearNodo(NODO *Q, NODO *list){
  NODO *P, *R;
  int x;
Ya para este paso, habíamos asignado al primer ID de la lista el valor de cero (0) con el propósito de usarlo como base para la organización de la lista.
Nosotros tenemos el conocimiento de que los elementos en una lista enlazada se van agregando como se van creando. En el caso de este proyecto no es asi, pues es ahí donde entra el valor cero del primer nodo de la lista.
Al querer crear un nodo nuevo e ingresar el ID de esa nodo, nos topamos después con la siguiente instrucción:
while (x > Q->ID) {
         if (Q->next != NULL) {
            Q = Q->next;
         } else if (Q->next == NULL) {
             break;
         }
}
La cual va a estar operando mientras el ID nuevo que se ingresa sea mayor al último ID presente en la lista enlazada.
La manera en que ira iterando este WHILE es con la ayuda del IF-ELSE, pues éste me dice que si el siguiente elemento es diferente de un valor NULO, se pasará al valor del ID del siguiente nodo y cuando llegue el momento en que el siguiente nodo sea un valor NULO o que el ID nuevo que ingresamos ya no sea mayor al ID que se está tomando de base, el WHILE se va a quebrar o invalidar.
Todo este rollo es sólo para posicionarnos en la parte donde vamos a crear el nodo en la lista enlazada.
Ahora bien, para ya formalizar la creación de nuestro nodo y capturar todas las variables, tenemos el siguiente IF-ELSE:
if (x > Q->ID) {
    P = (NODO*)malloc(sizeof(NODO));  ---->> Reserva de memoria
    P->ID = x;
        
    captura(P); ---->> Función para la captura de la información
        
    P->next = NULL;
    P->prev = Q;
    Q->next = P;
    Q = P;
    } else {
      P = (NODO*)malloc(sizeof(NODO));              
      R = Q;
      Q = Q->prev;
      P->ID = x;
          
      captura(P);
           
      P->prev = Q;
      P->next = R;
      R->prev = P;
      Q->next = P;
      Q = P;
    }
Aquí ya definimos oficialmente como va a quedar lo que es la posición completa del nodo que se va a crear: lectura de información, la reserva de memoria para ese nodo, la lectura de todas las variables y las secciones destinadas para apuntar al nodo anterior y el siguiente.
Propósito del orden de la lista.
El propósito para que hayamos ordenado nuestra lista enlazada era para el uso apropiado de lo que era la función Búsqueda, Modificación de Registros, Eliminación de Nodos.
Todo parte desde la búsqueda, para la cual tenemos las siguientes instrucciones:
while (dato != 0) {
     if ((Q->ID > dato) || (Q->next == NULL) && (Q->ID < dato)) {
          return NULL;
     } else if (Q->ID == dato) {
           
          imprime(Q); --->> Función para imprimir el registro
                 
          switch (proceso) {
               case 1: {       //FUNCION DE BUSQUEDA
                        return;
                }
               case 2: {       //FUNCION DE MODIFICAR
                        modify(Q, dato);
                        return;
                }
                case 3: {       //FUNCION PARA ELIMINAR
                         Borrar(Q, dato);     
                         return;
                }
          }
     } else if (dato != Q->ID) {
          Q = Q->next;
     }
}
Primeramente comento que ya desde la función main se le envio a esta función lo que es el valor de ID que estamos tratando de localizar en la lista enlazada.
Tenemos la primer condición donde si el ID que se está analizando es mayor al dato buscado o si es dicha condición junto con el hecho de que el siguiente nodo es un valor NULO, regresará un valor falso, el cual sirve de base para decir que el elemento que se busca no existe.
De lo contrario, si no pasa lo antes mencionado, solo nos pasamos al siguiente nodo para seguir comparando.
Una vez que el ID  que buscamos sea el mismo que el ID del nodo donde nos ubicamos en ese instante, se imprimen los datos correspondientes y luego ya el programa sabrá si es una buscado, eliminación o modificación.
¿Y el programa como sabrá que hacer en este paso?
En lo que es la función main estamos usando un switch para cada acción que podemos realizar con la lista. Dependiendo del proceso que hayamos elegido desde main, también se envía a nuestra función que realiza las búsquedas  en la lista, una especia de dato predefinido que te indica que tipo proceso elegir.
Función Búsqueda
No tiene gracia. Su dato predefinido para realizar esta acción es el 1, por lo que al imprimir el registro localizado, sólo nos regresamos a main y no pasa nada más.
Función Modificar
Tenemos la siguiente función para esta acción:
NODO *modify(NODO *Q, int modify) {
int op;
  
     printf("\n\t1. Nombre");
     printf("\n\t2. Facultad");
     printf("\n\t3. Carrera");
     printf("\n\t4. Semestre");
     printf("\n\n\tModificar---> ");
     scanf("%d", &op);
      
     switch(op){
        case 1:{
             lectura("Nombre Nuevo: ", Q->Name); --->> Función de
                                                       captura
              break;
       }
        case 2:{
             lectura("\nFacultad Nueva: ", Q->Facu);
              break;
        }
        case 3:{
             lectura("\nCarrera Nueva: ", Q->Carr);
              break;
        }
        case 4:{
              printf("\nSemestre Nuevo: ");
              scanf(" %d", &(Q->Sem));
              break;
        }
        default:{
              printf("\nEdicion NO Autorizada.\n");
              break;
        }
     }

return;
}
Aquí lo principal es mandar desde nuestra función selectiva de procesos la dirección de memoria y el ID del nodo que hemos localizado para poder modificarlo; es nada más de sobre escribir el dato o la variable que deseemos utilizando la dirección de memoria ya ubicada.
Función Eliminar
Al igual que en la función de modificar, desde la función selectiva de procesos mandamos la dirección de memoria y el ID del registro o nodo localizado a la función para depurar los nodos:
void Borrar(NODO *Q, int borrar) {
   char answer;
   NODO *ant, *aux;
  
   printf("\n\nEliminar Registro [Y/N]: ");
   scanf("%s", &answer);
               
   if (answer == 'Y' || answer == 'y') {
              aux = Q;
              ant = Q->prev;
                          
              if (aux->next == NULL) {
                     ant->next = NULL;
                                         
                     free(aux); --->> Liberar espacio en memoria
                                      de aux
                                        
                     printf("\n\n----->> Registro eliminado\n");
                    
                     return;
              } else {
                     ant->next = aux->next;
                     Q = Q->next;
                     Q->prev = ant;
                                 
                     free(aux);
                                 
                     printf("\n\n----->> Registro eliminado\n");
                    
                     return;
              }
   } else {
              printf("\n\n----->> Registro NO eliminado\n");
             
              return;
   }
}
Aquí es donde se me hizo más interesante.
Nosotros tenemos dos casos: cuando el nodo a eliminar está al final de la lista o en una parte media.
Para ambos casos necesitamos dos punteros de tipo NODO: ant y aux.
En el caso de que el nodo a eliminar se encuentre al final de la lista tenemos las operaciones:
aux = Q; ------------------->>> Paso 1
ant = Q->prev; ------------->>> Paso 2
                          
if (aux->next == NULL) { --->>> Elemento a eliminar es el último
ant->next = NULL; ---->>> Paso 3
                                    
              free(aux); -->>> Paso 4
}
De manera gráfica sería lo siguiente:
Paso 1:
Paso 2:
Paso 3:
Paso 4:
En el caso de que el nodo a eliminar se encuentra en la parte media sería con los siguientes pasos:
aux = Q; ---------------------------->>> Paso 1
ant = Q->prev; ---------------------->>> Paso 2
Agregamos la parte del else del if
ant->next = aux->next; -------------->>> Paso 3
Q = Q->next; ------------------------>>> Paso 4
Q->prev = ant; ---------------------->>> Paso 5
                                 
free(aux); -------------------------->>> Paso 6
En dibujito sería:
Paso 1:
Paso 2:
Paso 3:
Paso 4:
Paso 5:
Paso 6:
A grandes rasgos esos son los procesos que realiza este programa.
Saludos a todos.

1 comentario: