gui a lab list as

UNIVERSIDAD DE EL SALVADOR EISI

PROGRAMACION II (SISTEMAS) CICLO I/2009 1

UNIVERSIDAD DE EL SALVADOR FACULTAD DE INGENIERIA Y ARQUITECTURA ESCUELA DE INGENIERIA DE SISTEMAS INFORMATICOS PROGRAMACION II ( SISTEMAS )

GUIA DE LABORATORIO No. 7

LISTAS , LISTAS DOBLEMENTE ENLAZADAS Y LISTAS CIRCULARES

Tema: LISTAS Objetivo: Que el estudiante a través de la práctica aprenda el funcionamiento y la utilización de las estructuras de tipo lista implementada con arreglo y con memoria dinámica. EJEMPLOS DE LISTAS

1. Digite, compile y ejecute el siguiente programa. /*aplicacion demostrativa de implementacion de listas enlazadas con la utilizacion de un arreglo de nodos vacios */ #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <string.h> #include <iostream.h> #define NumNode 10 #define TRUE 1 #define FALSE 0 struct nodetype { char info[30]; int next; }; int getnode(struct nodetype *,int*); void insafter(int*, char*, struct nodetype *, int* ); void freenode(int p,struct nodetype *,int*); void imprimir_lista(int,struct nodetype *); int ultimo_lista(int, struct nodetype *); int isempty(int); int previo_lista(int,struct nodetype *, char *, int *); char * delafter( int, struct nodetype *, int *); char * remover( int *, struct nodetype *, int * ); char * leer_valor(void); void main(void) { struct nodetype node[NumNode];



int avail=0; /*inicializacion de lista de nodos disponible avail a 0 */ int i, r, enc, paises=-1, herramientas=-1, alumnos=-1; char pais[30]; char herra[30]; char alum[30]; int salir=FALSE,opcion; /*inicializacion del arreglo de nodos */ for (i=0; i<NumNode-1; i++) { strcpy(node[i].info," "); node[i].next=i+1; } strcpy(node[NumNode-1].info," "); node[NumNode-1].next = -1; /*Menu de opciones*/ while (!salir) { clrscr(); printf("ARREGLO CON 3 LISTAS\n"); printf("1. agregar pais\n"); printf("2. agregar herramienta\n"); printf("3. agregar nombre\n"); printf("4. imprimir listas\n"); printf("5. imprimir VECTOR\n"); printf("6. borrar pais\n"); printf("7. Salir\n\n"); printf("Digite opci¢n:"); scanf("%d",&opcion); if (opcion == 1) { strcpy(pais, leer_valor()); insafter(&paises,pais,node,&avail); } if (opcion == 2) { strcpy(herra, leer_valor()); insafter(&herramientas, herra,node,&avail); } if (opcion == 3) { strcpy(alum, leer_valor()); insafter(&alumnos,alum,node,&avail); } if (opcion == 4) { printf("\n\nPaises...\n\n"); imprimir_lista(paises,node); printf("Herramientas...\n\n"); imprimir_lista(herramientas,node); printf("Nombres...\n\n"); imprimir_lista(alumnos,node); getch(); }



if (opcion == 5) { for (i=0;i<NumNode;i++) { printf("Node[%d] = %s %d\n",i,node[i].info,node[i].next); } printf("\n\ninicio de lista PAISES: %d\n",paises); printf("inicio de lista HERRAMIENTAS: %d\n",herramientas); printf("inicio de lista ALUMNOS: %d\n",alumnos); getch(); } if (opcion == 6) { if ( ! ( isempty(paises) ) ) { imprimir_lista(paises, node); printf("Digite nombre de pais a borrar\n"); fflush(stdin); gets(pais); r = previo_lista(paises, node, pais, &enc); if ( enc ) { if ( r != -1 && enc) { strcpy(pais, delafter(r, node, &avail)); printf("El elemento borrado de la lista paises es: %s\n", pais); cout << pais; getch(); } else { if ( paises != -1 && enc) { strcpy(pais, remover(&paises, node, &avail)); printf("El elemento borrado de la lista paises es: %s\n", pais); getch(); } } } else { printf("Revise la lista de paises mostrada. Ese pais no esta en la lista.\n"); getch(); } } /* fin de proceso si pila no esta vacia */ else { printf("La lista esta vacia. No hay elementos a borrar.\n"); getch(); } } if (opcion == 7) { salir = TRUE; }



} } /*Recupera el siguiente nodo disponible, y asigna el siguiente node disponible*/ int getnode(struct nodetype * node, int *avail) { int nodo; nodo = *avail; *avail=node[*avail].next; return nodo; } /*Inserta un nodo al final de una lista*/ void insafter( int *lista, char x[30], struct nodetype * node,int* avail) { int nodo, ultimo; if (*avail == -1) { printf("Fallo la inserci¢n, vector lleno\n"); getch(); return; } nodo = getnode(node,avail); strcpy(node[nodo].info, x); if (!isempty(*lista)) // si la lista no esta vac¡a { ultimo = ultimo_lista(*lista,node); node[ultimo].next = nodo; node[nodo].next=-1; } else // si la lista esta vac¡a { *lista = nodo; node[nodo].next = -1; } } void freenode(int posicion, struct nodetype * node, int * avail) { node[posicion].next = *avail; strcpy( node[posicion].info, " "); *avail = posicion; } /*Recorre una lista, e imprime cada valor*/ void imprimir_lista(int lista,struct nodetype * node) { int i; i = lista; while ( i != -1 ) { printf("---> %s",node[i].info); printf("\n"); i = node[i].next; } printf("\n\n"); } /*Devuelve la posici¢n del ultimo nodo en una lista*/ int ultimo_lista(int lista,struct nodetype * node) {



int i,next; i=lista; while (node[i].next != -1) { i = node[i].next; } return i; } /*Determina si una lista esta vacia*/ int isempty(int lista) { if (lista == -1) return TRUE; else return FALSE; } /*Devuelve una cadena de caracteres leida*/ char *leer_valor() { char valor[30]; printf("\n\nDigite valor:"); fflush(stdin); gets(valor); return valor; } /* Elimina un nodo despues del nodo apuntado por p en la lista */ char * delafter( int p, struct nodetype * node, int * avail ) { int q; char b[30]; if ( ( p == -1 ) || ( node[p].next == -1 ) ) { printf( " Fallo eliminacion. \n" ); return " "; } q = node[p].next; strcpy( b, node[q].info ); node[p].next = node[q].next; freenode ( q, node, avail ); return b; } /*Devuelve la posici¢n del nodo previo al buscado en una lista. La variable encon devuelve cierto si fue encontrado y falso si no.*/ int previo_lista(int lista,struct nodetype * node, char *valor, int *encon) { int i,prev=-1; i =lista; *encon = FALSE; if ( ! (isempty(lista))) { while ( ! *encon && i != -1 ) { if (strcmp(node[i].info,valor) == 0 ) {



*encon = TRUE; return prev; } prev = i; i = node[i].next; } } return prev; } /* Elimina un nodo al frente de la lista */ char * remover( int *p, struct nodetype * node, int * avail ) { char b[30]; int q; if (*p == -1 ) { printf( " Fallo eliminacion. \n" ); return " "; } q = *p; *p = node[q].next; strcpy( b, node[q].info); freenode ( q, node, avail ); return b; }

2. Modifique el programa anterior para que se pueda eliminar el último

elemento en las listas. 3. Digite los diferentes archivos ( .c, .h, .txt ), haga un proyecto, compílelo y

ejecútelo. El problema a solucionar es: Una empresa de reparto de propaganda contrata a sus trabajadores por días. Cada trabajador puede trabajar varios días continuados o alternos. Los datos de los repartidores se almacenan en una lista simplemente enlazada. El programa a desarrollar contempla los siguientes puntos:

• Crear una estructura de cola para recoger en ella el número de la seguridad social de cada repartidor y la entidad anunciada en la propaganda para un único día de trabajo.

• Actualizar la lista citada anteriormente (que ya existe con contenido) a partir de los datos de la cola.

La información de la lista es la siguiente: Número de seguridad social, nombre y total de días trabajados. Si el trabajador no está incluido en la lista debe añadirse a la misma de tal manera que siga ordenada.

La implementación en lenguaje C se hará mediante un proyecto constituido por:



1. Dos archivos de cabecera denominados COLADIM..H, y LISTALIN.H los cuales contendrán las definiciones de las estructuras y los prototipos de las operaciones.

2. Un archivo de implementación denominado COLADIM.C y LISTALIN.C los cuales contendrán las definiciones de las funciones que soportarán las operaciones

3. Un archivo de aplicación denominado PROPAGA.C, el cual contiene la lógica. 4. Un archivo de datos denominado GENERAL.TXT, en formato texto el cual

contendrá los datos con los que funcionará la aplicación. 5. Un archivo de proyecto denominado APLISTA.PRJ, el cual integrará los archivos

de implementación COLADIM.C, LISTALIN.C y el programa de aplicación PROPAGA.C.

ARCHIVO COLADIM.H /*Implementacion de cola lineal con memoria dinámic a */ #define CIERTO 1 #define FALSO 0 #define NULO 0 typedef struct{ char SeguroSocial[10]; char Entidad[40]; }TipoDato; struct Nodoq{ TipoDato Info; struct Nodoq * Sgte; }; typedef struct Nodoq * Ptrnodoq; typedef struct{ Ptrnodoq Frente, Final; }TipoCola; void freenode(Ptrnodoq); Ptrnodoq getnode(void); void LimpiarCola(TipoCola *); int ColaVacia(TipoCola ); void Quitar(TipoDato *, TipoCola *); void Poner(TipoDato , TipoCola *); ARCHIVO COLADIM.C /* COLAS.C */ #include "a:coladim.h" #include <conio.h> #include <stdio.h> void freenode(Ptrnodoq p) { free(p); } Ptrnodoq getnode(void) { Ptrnodoq p;



p=(Ptrnodoq)malloc(sizeof(struct Nodoq)); return(p); } void LimpiarCola(TipoCola * pq) { pq->Frente=NULO; pq->Final=NULO; } int ColaVacia(TipoCola q) { return((q.Frente == NULO)? CIERTO: FALSO); } void Poner(TipoDato x , TipoCola * pq) { Ptrnodoq T; T=getnode(); T->Info=x; T->Sgte=NULO; if (ColaVacia(*pq)) pq->Frente=T; else (pq->Final)->Sgte=T; pq->Final=T; } void Quitar(TipoDato * px, TipoCola * pq ) { Ptrnodoq A; if (!ColaVacia(*pq)) { *px=(pq->Frente)->Info; A=pq->Frente; pq->Frente=(pq->Frente)->Sgte; if (pq->Frente==NULO) pq->Final=NULO; freenode(A); } }

ARCHIVO LISTALIN.H /*Implementacion de una lista enlazada lineal orden ada */ #define CIERTO 1 #define FALSO 0 #define NULO 0 typedef struct{ char ISSS[10]; char Nombre[41]; int DiasTrabajados; }TipoInfo; struct Nodo{ TipoInfo Info; struct Nodo * Sgte; }; typedef struct Nodo * ApuntaNodo; void LimpiarLista(ApuntaNodo *); int ListaVacia(ApuntaNodo);



ApuntaNodo PostInsert(TipoInfo, ApuntaNodo ); void InserOrden(TipoInfo , ApuntaNodo *); void Suprimir(TipoInfo * , ApuntaNodo *);

ARCHIVO LISTALIN.C /* LISTALIN.C */ #include "a:listalin.h" #include <conio.h> #include <stdio.h> void LimpiarLista(ApuntaNodo * pl) { *pl=NULO; } int ListaVacia(ApuntaNodo l) { return((l == NULO)? CIERTO: FALSO); } ApuntaNodo PostInsert(TipoInfo x, ApuntaNodo l) { ApuntaNodo T; T=NULO; if (!ListaVacia(l)){ while ((strcmp(x.ISSS, l->Info.ISSS)>=0) && (l- >Sgte!= NULO)){ T=l; l=l->Sgte; } if (strcmp(x.ISSS,l->Info.ISSS)>=0) T=l; } return(T); } void InserOrden(TipoInfo x , ApuntaNodo * pl) { ApuntaNodo A,N; N=(ApuntaNodo) malloc (sizeof(struct Nodo)); N->Info=x; N->Sgte=NULO; if (ListaVacia(*pl)) *pl=N; else{ A=PostInsert(x,*pl); if (A==NULO){ N->Sgte=*pl; *pl=N; } else{ N->Sgte=A->Sgte; A->Sgte=N; } } } void Suprimir(TipoInfo * px, ApuntaNodo *pl) { ApuntaNodo A;



if (! ListaVacia(*pl)){ A=*pl; *px=A->Info; *pl=A->Sgte; free(A); } }

ARCHIVO PROPAGA.C /*Nombre:PROPAGA*/ #include <conio.h> #include <stdio.h> #include <string.h> #include <ctype.h> #include "a:coladim.h" #include "a:listalin.h" main() { /* Variable */ TipoCola DatosDiarios; ApuntaNodo DatosGenerales, Aux; TipoDato DatoCola; TipoInfo DatoLista; FILE * arch; /* Inicializaciones */ LimpiarLista(&DatosGenerales); LimpiarCola(&DatosDiarios); arch=fopen("a:General.txt","r"); /*Creaci¢n de la lista*/ while (!feof(arch)) { fscanf(arch, "%s \n", DatoLista.ISSS); fscanf(arch, "%s \n", DatoLista.Nombre); fscanf(arch, "%d \n", &DatoLista.DiasTrabajad os); InserOrden(DatoLista,&DatosGenerales); } fclose(arch); /* Registro de datos diarios */ clrscr(); printf("\nDigite -1 en Numero de Seguro Social pa ra terminar\n"); printf("Numero de Seguro Social:"); fflush(stdin); scanf("%s",DatoCola.SeguroSocial); while (strcmp(DatoCola.SeguroSocial,"-1")) { fflush(stdin); printf("Entidad:"); scanf("%s",DatoCola.Entidad); Poner(DatoCola,&DatosDiarios); printf("\nDigite -1 en Numero de Seguro Social para terminar\n"); printf("Numero de Seguro Social:"); scanf("%s",DatoCola.SeguroSocial); } /* Actualizar Lista */ while (!ColaVacia(DatosDiarios)) {



Quitar(&DatoCola,&DatosDiarios); /*Busqueda de empleado*/ Aux=DatosGenerales; while((strcmp(Aux->Info.ISSS,DatoCola.SeguroSocial )<0) && (Aux->Sgte != NULO) ) Aux=Aux->Sgte; /*Actualiza o Agrega*/ if (!strcmp(Aux->Info.ISSS,DatoCola.SeguroSocial)) Aux->Info.DiasTrabajados++; else {strcpy(DatoLista.ISSS,DatoCola.SeguroSocial); DatoLista.DiasTrabajados=1; clrscr(); printf("\nAgregando un Nuevo Empleado\n"); printf("Numero Seguro Social:%s\n",DatoLista.IS SS); printf("Nombre:"); scanf("%s",DatoLista.Nombre); InserOrden(DatoLista,&DatosGenerales); } } /*Mostrar el contenido de la Lista*/ clrscr(); printf("\nListado General de Empleados\n"); Aux=DatosGenerales; while(Aux!=NULO){ printf("Numero Seguro Social:%s\n",Aux->Info.ISSS) ; printf("Nombre:%s\n",Aux->Info.Nombre); printf("Dias Trabajados:%d\n\n",Aux->Info.DiasTrab ajados); Aux=Aux->Sgte; } printf("<ENTER> para continuar.....\n\n"); getch(); /*Actualizando Archivos de texto*/ arch=fopen("a:General.txt","w"); printf("Guardando en Archivo"); while(!ListaVacia(DatosGenerales)){ Suprimir(&DatoLista,&DatosGenerales); fprintf(arch,"%s\n",DatoLista.ISSS); fprintf(arch,"%s\n",DatoLista.Nombre); fprintf(arch,"%d\n",DatoLista.DiasTrabajados); } fclose(arch); return(0); }/* main */

ARCHIVO ORIGINAL GENERAL.TXT 098765432 Luis 1 123456787 Mario 1 123456789 Silvia



5 987654321 Marta 4

CORRIDA DEL PROGRAMA Listado General de Empleados Numero Seguro Social: 098765432 Nombre: Luis Dias Trabajados: 1 Numero Seguro Social: 123456787 Nombre: Mario Dias Trabajados: 1 Numero Seguro Social: 123456789 Nombre: Silvia Dias Trabajados: 6 Numero Seguro Social: 567891234 Nombre: Guadalupe Dias Trabajados: 1 Numero Seguro Social: 987654321 Nombre: Marta Dias Trabajados: 4 ARCHIVO FINAL GENERAL.TXT 098765432 Luis 1 123456787 Mario 1 123456789 Silvia 6 567891234 Guadalupe 1 987654321 Marta 4

EJERCICIOS DE LISTAS

1. Escriba una función para ejecutar cada una de las siguientes operaciones, utilizar memoria dinámica:

a. Concatenar dos listas. b. Invertir una lista, de manera que el último elemento se convierta en el

primero y así sucesivamente. c. Suprimir el enésimo elemento de una lista. d. Combinar dos listas ordenadas en una sola lista ordenada.



e. Suprimir cada segundo elemento de una lista. f. Colocar los elementos de una lista en orden creciente. g. Retornar la cantidad de elementos en una lista.

Hacer un programa principal que ofrezca todas estas opciones, además de las operaciones básicas de una lista.

2. Realizar el ejercicio anterior pero implementarlo usando memoria estática

(arreglo). 3. Escriba funciones para realizar cada una de las operaciones del ejercicio 4,

suponiendo que cada lista contiene un nodo de encabezado que incluye el número de elementos en la lista. Hacer un programa para probar la funcionalidad de las funciones.

Tema: LISTAS DOBLEMENTE ENLAZADAS Objetivo: Que el estudiante a través de la práctica aprenda el funcionamiento y la utilización de la estructura lista doblemente enlazada.

1. Digite, compile y ejecute el siguiente programa. /* El siguiente programa ofrece diferentes opciones, a través de un menú, de operaciones con listas doblemente enlazadas: insertar un nodo, buscar, borrar nodo, imprimir ascendente, imprimir descendente. */ #include <stdlib.h> #include <stdio.h> #include <conio.h> #define ASCENDENTE 1 #define DESCENDENTE 0 #define TRUE 1 #define FALSE 0 typedef struct _nodo { int valor; struct _nodo *siguiente; struct _nodo *anterior; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Lista; /* Funciones con listas: */ void Insertar(Lista *l, int v); void Borrar(Lista *l, int v); pNodo getnodo(void); void BorrarLista(Lista *); void MostrarLista(Lista l, int orden);



pNodo buscar_nodo( Lista, int, int *); void menu(void); void main(void) { Lista lista = NULL; pNodo p; int opcion, v, enc, cont=TRUE; clrscr(); while ( cont ) { menu(); printf("Digite una opcion:\n "); scanf("%d", &opcion); switch(opcion) { case 1: /*Insertar un elemento a la lista doblemente enlazada */ printf("Digite el valor a insertar en la lista: \n"); scanf("%d", &v); Insertar(&lista, v); break; case 2: /* Borrar un elemento de la lista doblemente enlazada*/ MostrarLista(lista, ASCENDENTE); printf("Digite el valor a borrar de la lista: \n"); scanf("%d", &v); Borrar(&lista, v); break; case 3: /* Buscar un elemento en la lista doblemente enlazada */ printf("Digite el valor a buscar en la lista. \n"); scanf("%d", &v); buscar_nodo(lista, v, &enc); if (enc) printf("El valor si existe en la lista.\n"); else printf("El valor no esta en la lista.\n"); break; case 4: /*Imprimir la lista en forma ASCENDENTE */ MostrarLista(lista, ASCENDENTE); break; case 5: /*Imprimir la lista en forma DESCENDENTE */ MostrarLista(lista, DESCENDENTE); break; case 6: cont = FALSE; } /* fin del switch */ } /*fin del while */ /* Liberar toda la memoria utilizada */ BorrarLista(&lista); getch(); }



void Insertar(Lista *lista, int v) { pNodo nuevo, actual; /* pedir un nodo nuevo */ nuevo = getnodo(); nuevo->valor = v; /* Colocamos actual en la primera posición de la lista */ actual = *lista; if(actual) while(actual->anterior) actual = actual->anterior; /* Si la lista está vacía o el primer miembro es mayor que el nuevo*/ if(!actual || actual->valor > v) { /* Añadimos la lista a continuación del nuevo nodo */ nuevo->siguiente = actual; nuevo->anterior = NULL; if(actual) actual->anterior = nuevo; if(!*lista) *lista = nuevo; } else { /* Avanzamos hasta el último elemento o hasta que el siguiente tenga un valor mayor que v */ while(actual->siguiente && actual->siguiente->valor <= v) actual = actual->siguiente; /* Insertamos el nuevo nodo después del nodo anterior */ nuevo->siguiente = actual->siguiente; actual->siguiente = nuevo; nuevo->anterior = actual; if(nuevo->siguiente) nuevo->siguiente->anterior = nuevo; } } void Borrar(Lista *lista, int v) { pNodo nodo; /* Buscar el nodo de valor v */ nodo = *lista; while(nodo && nodo->valor < v) nodo = nodo->siguiente; while(nodo && nodo->valor > v) nodo = nodo->anterior; /* El valor v no está en la lista */ if(!nodo || nodo->valor != v) return; /* Borrar el nodo */ /* Si lista apunta al nodo que queremos borrar, apuntar a otro */ if(nodo == *lista) if(nodo->anterior) *lista = nodo->anterior; else *lista = nodo->siguiente;



if(nodo->anterior) /* no es el primer elemento */ nodo->anterior->siguiente = nodo->siguiente; if(nodo->siguiente) /* no es el último nodo */ nodo->siguiente->anterior = nodo->anterior; free(nodo); } void BorrarLista(Lista *lista) { pNodo nodo, actual; actual = *lista; while(actual->anterior) actual = actual->anterior; while(actual) { nodo = actual; actual = actual->siguiente; free(nodo); } *lista = NULL; } void MostrarLista(Lista lista, int orden) { pNodo nodo = lista; if(!lista) printf("Lista vacía"); nodo = lista; if(orden == ASCENDENTE) { while(nodo->anterior) nodo = nodo->anterior; printf("Orden ascendente: "); while(nodo) { printf("%d -> ", nodo->valor); nodo = nodo->siguiente; } } else { while(nodo->siguiente) nodo = nodo->siguiente; printf("Orden descendente: "); while(nodo) { printf("%d -> ", nodo->valor); nodo = nodo->anterior; } } printf("\n"); } pNodo getnodo(void) {



pNodo nuevo; /* Crear un nodo nuevo */ nuevo = (pNodo)malloc(sizeof(tipoNodo)); return nuevo; } pNodo buscar_nodo( Lista lista, int v, int *enc ) { pNodo nodo; /* Buscar el nodo de valor v */ nodo = lista; while(nodo && nodo->valor < v) nodo = nodo->siguiente; while(nodo && nodo->valor > v) nodo = nodo->anterior; /* El valor v no está en la lista */ if(!nodo || nodo->valor != v) *enc = FALSE; /* devolver a través de enc si v fue encontrado en la lista */ else *enc = TRUE ; /* devolver el apuntador al nodo */ return nodo; } void menu(void) { printf("\n------------------------------------------------\n"); printf("----------------- M E N U ----------------------\n"); printf("------------------------------------------------\n"); printf("1. Introducir un elemento en la lista.\n"); printf("2. Borrar un elemento de la lista.\n"); printf("3. Buscar un elemento en la lista.\n"); printf("4. Imprimir la lista en forma ASCENDENTE\n"); printf("5. Imprimir la lista en forma DESCENDENTE\n"); printf("6. Salir. \n"); } 2. Modificar el programa anterior para que implemen te un nodo de

encabezado en la lista doblemente enlazada, en el c ual debe estar el número de nodos de la lista.

EJERCICIOS DE LISTAS DOBLEMENTE ENLAZADAS

1. Una tienda de artículos deportivos desea almacenar en una lista doblemente enlazada, con un único elemento por producto, la siguiente información sobre las ventas realizadas: código del artículo, cantidad y precio. Desarrollar un programa que permita tanto la creación de la lista como su actualización al realizarse nuevas ventas o devoluciones de un determinado producto.



2. Escribir un programa que divide una lista doblemente enlazada determinada en

dos listas doblemente enlazadas independientes. El primer nodo de la lista principal es PRIMERO y la variable PARTIR es la dirección del nodo que se convierte en el primero de los nodos de la segunda lista doblemente enlazada resultante.

3. Dadas dos listas doblemente enlazadas, cuyos nodos frontales se indican con

los apuntadores LISTA1 y LISTA2, respectivamente, realizar un programa que una ambas listas. El nodo frontal de la lista nueva se indicará por LISTA3.

4. Hacer una función que cambie el campo INFO del n-ésimo nodo de una lista

doblemente enlazada por un valor dado de x. Probar la función en un programa. 5. Escriba un programa en C para convertir una cadena prefija a posfija, utilizando

una lista doblemente enlazada. 6. Escriba la rutina reduce en C y que acepte una cadena interfija y forme una

cadena interfija equivalente quitando todos los paréntesis superfluos, utilizando una lista doblemente enlazada.

7. Utilizar una lista doblemente enlazada para controlar una lista de pasajeros de

una línea aérea. El programa principal debe ser controlado por menú y permitir al usuario visualizar los datos de un pasajero determinado, insertar un nodo (siempre por el final), eliminar un pasajero de la lista. A la lista se accede por un puntero al primer nodo y otro al último.

8. Para representar un entero largo, de más de 30 dígitos, utilizar una lista circular

teniendo el campo dato de cada nodo un dígito del entero largo. Escribir un programa en el que se introduzcan dos enteros largos y se obtenga su suma.

9. Un vector disperso es aquel que tiene muchos elementos que son cero. Escribir

un programa que permita representar mediante listas doblemente enlazadas un vector disperso. Los nodos de la lista son los elementos de la lista distintos de cero; en cada nodo se representa el valor del elemento y el índice (posición del vector). El programa ha de realizar las operaciones: sumar dos vectores de igual dimensión, y hallar el producto escalar.



Tema: LISTAS CIRCULARES

Objetivo: Que el estudiante a través de la práctica aprenda el funcionamiento y la utilización de la estructura lista circulares. Digite, compile y ejecute el siguiente programa.

#include <stdio.h> #include <conio.h> #include <stdlib.h> /* Aplicacion de listas circulares con nodos de encabezado. El Hw solo permite enteros de una longitud maxima especifica. Suponga que queremos representar enteros positivos de longitud arbitraria y escribir una funcion que retorne la suma de esos dos enteros. Para agregar dos enteros, se recorren sus digitos de derecha a izquierda y se suman los digitos correspondientes y un posible acarreo de la suma de digitos anterior. */ // estructura de los nodos struct node { long int info; struct node *next; }; typedef struct node *NODEPTR; // el nodo de encabezado de la lista circular se distingue por un valor -1. NODEPTR addint ( NODEPTR , NODEPTR ); NODEPTR getnode ( void ); void insert ( NODEPTR *, long int ); void imprimir( NODEPTR ); void insafter (NODEPTR, long int ); void main ( void ) { long int a[10]={0}, a1, a2, a3, a4; int i,dig; NODEPTR r = NULL,lista = NULL, lis2=NULL; printf( "Este es un programa que puede representar enteros bastante largos. "); printf( "Se le pide digite el numero de 5 en 5 dígitos, seguidos de un <enter>"); printf(" Ejemplo: el numero a digitar es: 459763497210698463 \n"); printf("Digite: 459 <enter> 76349 <enter> 72106 <enter> 98463 <enter>\n"); printf("Capacidad maxima: 50 digitos \n"); printf("Cuantos grupos de 5 digitos o menos va a digitar: (maximo: 10) "); scanf("%d", &dig); printf("arreglo:"); for (i=0; i<10; i++) printf("%d", a[i]);



printf("\n"); for ( i=0; i<dig; i++) { fflush(stdin); scanf("%D",&a[i]); } for ( i=0; i < dig; i++) insert(&lista, a[i]); imprimir(lista); printf("Probemos ahora la suma de dos listas: \n"); printf("Sumaremos a su numero, el numero: 45976349721069846354\n"); a1 = 45976; a2 = 34972; a3 = 10698; a4 = 46354; insert(&lis2, a1); insert(&lis2, a2); insert(&lis2, a3); insert(&lis2, a4); r= addint(lista, lis2); printf("La suma de los 2 numeros es: "); imprimir(r); printf("\n"); getch(); } NODEPTR getnode(void) { NODEPTR p; p = (NODEPTR) malloc ( sizeof ( struct node )); return p; } /* inserta un nodo al inicio de la lista circular */ void insert ( NODEPTR *pq, long int x) { NODEPTR p, aux; p = getnode(); p->info = x; if ( *pq == NULL ) { aux = getnode(); aux->info = -1; aux->next = p; *pq = aux; p->next = aux; } else { p->next = (*pq)->next; (*pq)->next = p; } /*fin del else */



} /*fin del insert */ NODEPTR addint ( NODEPTR p, NODEPTR q) { long int hunthou = 100000L; long int carry, number, total; NODEPTR s; /*establecer p y q para los nodos despues de los encabezados */ p = p->next; q = q->next; /*preparar un nodo de encabezado para la suma */ s = getnode(); s->info = -1; s->next = s; /*inicialmente no hay acarreo */ carry = 0; while ( p->info != -1 && q->info != -1 ) { /*sumar el campo info de los dos nodos y el acarreo previo */ total = p->info + q->info + carry; /*determinar los 5 digitos de orden inferior de la suma e insertarlos en la lista */ number = total % hunthou; insafter(s, number); /*avanzar los recorridos */ s = s->next; p = p->next; q = q->next; /*determinar si hay acarreo */ carry = total / hunthou; } /*fin de while */ /*en este punto pueden quedar nodos en una de las dos listas de ingreso*/ while (p->info != -1) { total = p->info + carry; number = total % hunthou; insafter(s, number); carry = total / hunthou; s = s->next; p = p->next; } /*fin de while */



while (q->info != -1) { total = q->info + carry; number = total % hunthou; insafter(s, number); carry = total / hunthou; s = s->next; q = q->next; } /*fin de while */ /*comprobar si hay un acarreo extra de los primeros cinco dígitos*/ if (carry == 1) { insafter(s, carry); s = s->next; } /*fin de if */ /* s apunta al ultimo nodo en la suma. s->next apunta al encabezado de la lista de suma. */ return ( s->next ); } /*fin de addint */ /*inserta un nodo después del nodo apuntado por p */ void insafter (NODEPTR p, long int x) { NODEPTR q; q = getnode(); if ( p == NULL ) { p=getnode(); p->info = -1; p->next = q; q->info = x; q->next = p; } else { q->info = x; q->next = p->next; p->next = q; } } /*fin de insafter */ void imprimir( NODEPTR L ) { NODEPTR L1; long int B[10]={0}; int i=0, k; if (L->info == -1) { L1=L->next; while ( L1->info != -1 )



{ B[i++]=L1->info; L1 = L1->next; } k=i-1; for ( ; k>=0; k--) printf("%d", B[k]); printf("\n"); } }

gui a lab list as

Documents