Listas en C

Programación en C. Listas enlazadas. Ordenar. Sumar. Mostrar

  • Enviado por: Felix
  • Idioma: castellano
  • País: España España
  • 12 páginas

publicidad

INTRODUCCION

En esta práctica vamos a trabajar con listas. Vamos a crear una lista con una estructura que tiene dos números el coeficiente y el exponente de cada elemento de un polinomio, cada elemento del polinomio va a ser un nodo de la lista, para enlazar la lista vamos a utilizar un puntero que apunte al siguiente nodo de la lista, siendo NULL el último apuntador de la lista para diferenciarlo de los demás y para que el ordenador sepa que es el último nodo.

El programa nos va ha permitir:

  • Entrar un polinomio con los elementos desordenados y después ordenarlos, de esta forma siempre quedará la lista ordenada del elemento con mayor exponente al de menor exponente.

  • También nos va a permitir sumar el polinomio introducido con otro polinomio que introduciremos en ese momento y guardar la suma de los dos en un tercer polinomio.

  • Hacer la derivada del polinomio introducido en el primer apartado. Y guardar la derivada en un segundo polinomio.

  • Nos tendrá evaluar el primer polinomio en un punto que deseemos.

  • Por ultimo nos tendrá que permitir visualizar el polinomio introducido en el primer apartado.

Para realizar las funciones utilizaremos tres archivos “*.C”. En uno pondremos el menú “polinomi.C” en otro implementaremos las funciones necesarias para el manejo de los nodos “poli.C” y en el último pondremos las funciones para trabajar con la lista “lista.C”.

Aparte crearemos dos librerías “*.h” en donde pondremos la estructura a utilizar, y las cabeceras de las funciones de “poli.C” y “lista.C”, que se llamaran respectivamente “poli.H” y “lista.H”.

EXPLICACIÓN DEL PROGRAMA.

“POLINOMI.C”

Las variables principales en el control del programa sirven para: OP que será la opción que deseamos realizar. OPCION que la utilizaremos como control del WHILE y CREADA que será la que nos diga si hemos creado la primera lista.

En este archivo crearemos el menú que veremos al ejecutar e programa, este menú irá saliendo mientras que no demos a la opción “6” que será la de salir del programa. Si ponemos una opción incorrecta nos sacará un mensaje por pantalla y volverá a escribir el menú.

Mientras que no creemos la primera lista las opciones de la “2-5” nos funcionarán y nos sacarán un mensaje por pantalla diciendo que no hay una lista introducida. Para crear la lista lo haremos a través de la opción “1” que llamará a una función que nos crea la lista.

La opción “2” nos creara una segunda lista y después creara la tercera lista que será la de la suma de las dos anteriores, por ultimo nos sacará por pantalla las tres listas y liberará la memoria de las dos últimas.

En la opción “3” nos creará una segunda lista que será la derivada de la primera, sacra las dos listas por pantalla y liberará de la memoria la segunda lista.

La opción “4” evaluará la lista en un punto que deseemos.

Por ultimo la opción “5” nos mostrará por pantalla el polinomio que hemos insertado en la opción “1”.

Cuando terminamos el programa liberamos la memoria de las listas, aunque solo haría falta liberar la memoria de la primera lista, liberamos todas por si hubiese algún error.

“POLI.C”

Este archivo va a servir para manejar los nodos de cada lista. Esta dividida en funciones que explicaremos seguidamente.

Nodo *escribir_poli(void)

Esta función es la principal al crear la lista, en ella las variables serán: C será el coeficiente leído por teclado. E será el exponente leído por teclado PRIMERO será para saber si hay algún nodo que ya hubiésemos leído antes. *AUX será el apuntador auxiliar al nodo donde pondremos los datos que leemos de teclado antes de colocarlo en su lugar en la lista y *P será el apuntador al principio de la lista.

El procedimiento que ejecuta la función será de pedir los términos del polinomio, y mientras que C y E no sean 0 y 0 que vaya leyendo C y E. Dentro de WHILE lo que haremos será reservar memoria para *AUX, cambiar el coeficiente y el exponente por los puestos por teclado. Si son diferentes de 0 que mire si son los primeros que hay que poner en la lista a través de la variable PRIMERO, y si es así llama a la función crear_primero que nos devolverá la dirección del primer nodo de la lista.

En el caso contrario mirará si el exponente del nodo AUX es mayor que el del primer nodo de la lista y lo insertará el primero devolviéndonos el apuntador nuevo al primer nodo de la lista. Si es menor buscará el sitio donde debe colocar el nodo para colocarlo a través de la función buscar_siguiente.

Esta función retornará al programa del menú el apuntador al primer nodo de la lista.

Nodo *derivar_funcion(nodo *p1)

Esta función es para devolver el apuntador del principio de la segunda lista que será la de la función derivada de la primera lista, para ello le hemos pasado el apuntador a la primera lista. Las variables utilizadas aparte de *P1 son *P2, *AUX y PRIMERO que tienen la misma función que *P, *AUX y PRIMERA que hemos utilizado en la función anterior.

La forma de ejecución de esta función es igual que en la anterior, con la diferencia de que los valores del coeficiente y del exponente ahora serán dados por la lista P1 y el WHILE no terminará mientras que no encuentre que el apuntador apunta a NULL que será cuando la lista se haya terminado.

En esta función no hace falta la función insertar_primero, ya que la lista P1 ya viene ordenada. Cuando el exponente de la lista P1 sea 0, no pondremos nada en AUX ya que la derivada de un polinomio de grado 0 es 0, y no hará falta colocarlo en la lista.

Nodo *sumar_poli(nodo *p1,nodo *p2)

En esta función pasamos la dos listas P1 y P2 que serán las que debamos sumar, como en las demás funciones utilizaremos unas variables con la misma función que en las otras que serán *AUX, *P3 y PRIMERO. Aparte vamos a utilizar *NULO que será un nodo que tendrá el exponente y el coeficiente 0 y el apuntador a un nodo apuntará a ella misma. Este nodo lo utilizaremos para que las comparaciones de después funcionen correctamente como explicaremos al final.

La forma de ejecución de esta función será ir comparando los exponentes de los nodos a los que apunta P1 y P2 si son diferentes cogerá el nodo de mayor exponente lo copiará en AUX y después pasará al siguiente nodo de la lista del que tenia mayor exponente. En el caso de que los dos exponentes sean iguales copiará el exponente de uno de los nodos en AUX y hará la suma de los coeficientes de los dos nodos y la pondrá en AUX, por ultimo pasará a los siguientes nodos de las dos listas.

Para crear la lista se hará de la misma forma que en derivar_funcion y retornará el apuntador al primer nodo de la lista al programa principal.

Por la forma de ir incrementado y comparando las dos listas llegaría un momento en que una de las dos listas se acabase antes de terminar la otra, para que esto no nos dé problemas cuando las listas P1 y P2 lleguen al final, hacemos que sus apuntadores apunten al nodo NULO que como tiene exponente y coeficiente 0 mientras que la lista que no haya acabado y siga teniendo nodos los seguirá pasando a AUX y en el caso de que los dos nodos tengan exponente cero no modificara al coeficiente al hacer la suma de los dos. Así que cuando las dos listas hayan terminado *P1 y *P2 apuntaran al nodo NULO y saldrán del WHILE . Al principio de la función le habremos reservado memoria a NULO y al salir de la función liberaremos la memoria de NULO.

Float evaluar_nodo(nodo *p, float punto)

En esta función le pasamos el nodo *P que será el nodo a evaluar y PUNTO que será el punto donde queremos evaluarla. Las variables utilizadas serán :I será para controlar el FOR que nos calcula el cuadrado de PUNTO y RESNODO que será el resultado del nodo evaluado en ese punto.

El funcionamiento de la función será de calcular el PUNTO elevado al exponente del nodo, después multiplicarlo por el coeficiente. Y por último devolverá a la función evaluar_lista el resultado de la evaluación del nodo “RESNODO”.

“LISTA.C”

Este archivo va a servir para manejar la lista. Esta dividida también en funciones que explicaremos seguidamente.

void insertar_nodo(nodo *p, nodo *aux)

Esta función inserta un nodo en cualquier punto de la lista, mientras que no sea el primero. La forma de hacerlo por pasos queda mas claro en el siguiente dibujo.

Nodo *crear_primero(nodo *aux)

Esta función sirve para crear la lista cuando todavía no existe. Devuelve el apuntador al primer nodo de la lista y le pone el apuntador al siguiente nodo a NULL, ya que al ser el primero no tiene que haber más nodos.

Nodo *insertar_primero(nodo *p, nodo *aux)

Esta función es como crear primero pero cuando la lista ya existe la utilidad de esta función es para cuando estamos ordenado la lista al crearla a través de la función crear_lista. Tiene que devolver el nuevo apuntador al primer nodo de la lista.

Void mostrar_polinomio(nodo *p)

Esta función va recorriendo la lista y escribiendo la ecuación que hemos creado anteriormente. Dependiendo de sí es el ultimo elemento de la lista, o de sí el exponente es 0 va escribiendo por pantalla las diferentes opciones.

Void evaluar_lista (nodo *p)

En esta función nos pide el punto donde queremos evaluar y va llamando a la función evaluar_nodo para cada nodo de la función guardando los resultados en la variable RES y cuando ya ha evaluado todos los nodos escribe por pantalla el resultado, la variable RES la hemos definido como un real para poder evaluarla en cualquier punto.

Void buscar_siguiente(nodo *p, nodo *aux)

Esta función la utilizamos cuando queremos insertar un nodo que no sea el primero para buscar el lugar de la lista en el que tiene que ir, lo único que se hace es ir recorriendo la lista y comparando el exponente de P y de AUX para saber donde colocarla. Si llega al final de la lista coloca AUX en el ultimo lugar de la lista P.

Para insertar el nodo en la lista se llama a la función insertar_nodo y le debemos pasar el apuntador al nodo anterior al que tenga un exponente menor que el de AUX, por eso utilizamos la variable SIGUIENTE, que será el nodo que queremos ver si es menor que AUX.

PROGRAMA PRINCIPAL

POLI.H

struct nod{ /*Definicion de la estructura*/

int coef;

int expo;

struct nod *sig;

};

typedef struct nod nodo;

float evaluar_nodo(nodo *p,float punto);

nodo *escribir_poli(void);

nodo *derivar_funcion(nodo *p1);

nodo *sumar_poli (nodo *p1,nodo *p2);

void buscar_siguiente(nodo *p,nodo *aux);

LISTA.H

# include <stdio.h>

void evaluar_lista (nodo *p);

void insertar_nodo(nodo *p,nodo *aux);

nodo *insertar_primero(nodo *p,nodo *aux);

void mostrar_polinomio (nodo *p);

nodo *crear_primero(nodo *aux);

void buscar_siguiente(nodo *p,nodo *aux);

nodo *reservar_nodo(void);

POLINOMI.C

#include <stdio.h>

#include "poli.h"

main () /*Programa principal donde esta el menu y

la opcion a realizar*/

{ nodo *p1,*p2,*p3;

int op,opcion,creada;

creada=0; /*variable para saber si hemos credo alguna lista*/

opcion=0; /*variable para salir del menu principal*/

while (opcion!=1){

printf ("\n Menu principal:\n");

printf (" 1 - Crear polinomio \n");

printf (" 2 - Suma de polinomios \n");

printf (" 3 - Derivar polinomios\n");

printf (" 4 - Evaluacion del polinomio \n");

printf (" 5 - Mostrar polinomio \n");

printf (" 6 - terminar \n");

printf ("\n INTRODUCE ELECCION:");

scanf ("%d",&op);

switch (op){

case 1 : p1=escribir_poli(); /*funcion para crear lista*/

creada=1;break;

case 2 : if (creada==0) printf("\n La lista no esta creada");

else{

p2=escribir_poli(); /*creamos la lista p2*/

p3=sumar_poli(p1,p2); /*creamos la lista p3 que es la suma*/

mostrar_polinomio(p1); /*a partir de la funcion sumar_poli*/

mostrar_polinomio(p2); /*por ultimo mostramos las tres listas*/

mostrar_polinomio(p3);

free (p2,p3);}

break;

case 3 : if (creada==0) printf("\n La lista no esta creada");

else {

p2=derivar_funcion(p1); /*funcion que nos crea p2 a traves de*/

mostrar_polinomio(p1); /*la derivada de p1. Por ultimo */

mostrar_polinomio(p2); /*mostramos p1 y p2*/

free (p2);}

break;

case 4 : if (creada==0) printf("\n La lista no esta creada");

else evaluar_lista(p1);

break;

case 5 : if (creada==1) mostrar_polinomio(p1);

else printf("\n La lista no esta creada");

break; /*si hemos creado la lista p1 podemos verla*/

case 6 : opcion=1;break; /*opcion de salida para ello ponemos opcion=1*/

default : printf ("\n opcion incorrecta!"); }} /*si no hemos puesto ninguna*/

/*opcion sale el mensaje*/

/*y volvemos a empezar*/

free(p1,p2,p3); /*liberamos la memoria de las listas*/

return(0);}

POLI.C

# include <stdio.h>

# include "poli.h"

nodo *escribir_poli(void) /*funcion que devuelve el apuntador al primer nodo de

la lista*/

{nodo *aux,*p; /*nodo auxiliar para poner los datos del teclado*/

int c,e,primero;

primero=1; /*variable para saber si es el primer nodo que escribimos*/

printf("\nEscribir terminos del polinomio deseado:\n");

do{

aux = (nodo *)malloc(sizeof(nodo)); /*reservamos memoria a aux*/

if (aux==NULL) {

printf("\nNo haymemoria");

e=0;

c=0;}

else{ scanf("%d%d",&c,&e); /*ponemos lo leido en c y e y despues*/

aux->coef=c; /*lo pasamos al nodo aux*/

aux->expo=e;

if (c!=0 || e!=0) /*si c=0 y e=0 no crea nodo en la lista*/

{if (primero==1){ /*en el caso de sea el primer nodo a insertar*/

p=crear_primero(aux); /*funcion que devuelve el apuntador al*/

primero=0;} /*primer nodo de la lista*/

else { if (p->expo<aux->expo) p=insertar_primero(p,aux);

/*si el expo del nodo a insertar es mayor que el primero

de la lista debemos insertarlo el primero en la lista

y nos debera devolver el apuntador a ese nodo que ahora sera

el primero*/

else {if (p->sig==NULL) insertar_nodo(p,aux);

else buscar_siguiente(p,aux);}

/*si no buscaremos el lugar de la lista donde insertarlo*/

}}}

}while (c!=0 || e!=0); /*condicion de salida de escribir poli*/

return (p); /* devolvemos el apuntador al primer nodo de la lista*/

}

nodo *derivar_funcion(nodo *p1) /*funcion de derivar que devuelve

el apuntador al primer nodo de la funcion derivada*/

{nodo *aux,*p2;

int primero=0;

do{ aux=(nodo *)malloc(sizeof(nodo));

if (aux==NULL) {

printf("\n %d No hay memoria",primero);

p1=NULL;}

else{

if (p1->expo!=0){ /*los valores de aux seran haciendo la derivada*/

aux->coef=p1->expo * p1->coef;

aux->expo=(p1->expo)-1;

if (primero==0){ /*si es el priemero nos devolvera el apuntador*/

p2=crear_primero(aux); /*a ese primer nodo*/

primero=primero++;}

else buscar_siguiente(p2,aux); /*si no insertamos detras del ultimo*/

p1=p1->sig;

} }

}while (p1!=NULL && p1->expo!=0);

return(p2); /*devolvemos el apuntador al primer nodo de la lista*/

}

nodo *sumar_poli (nodo *p1,nodo *p2)

{nodo *aux, *nulo, *p3;

int primero=0;

nulo=(nodo *)malloc(sizeof(nodo));

if (nulo==NULL) printf("\n NO HAY MEMORIA");

else{

nulo->expo=0; /*hemos creado este nodo para cuando acaben la lista p1 o p2*/

nulo->coef=0; /*hacer la comparacion entre las dos listas y que funcione*/

nulo->sig=nulo; /*este nodo apuntara a el mismo*/

do{aux=(nodo *)malloc(sizeof(nodo));

if (aux==NULL) printf("\n No hay memoria");

else{

if (p1->expo > p2->expo){ /*a partir de aqui comparamos cual de los*/

aux->coef=p1->coef; /*dos exponentes es mas grande y dependiendo*/

aux->expo=p1->expo; /*del caso aux tomara valores*/

if (p1->sig!=NULL) p1=p1->sig; /*este caso es para que coga solo p1*/

else p1=nulo;}

else {if(p1->expo < p2->expo){ /*este caso es para que coga p2*/

aux->coef=p2->coef;

aux->expo=p2->expo;

if (p2->sig!=NULL) p2=p2->sig;

else p2=nulo;}

else {aux->coef=p1->coef+p2->coef; /*este caso es cuando p1=p2*/

aux->expo=p1->expo;

if (p1->sig!=NULL) p1=p1->sig;

else p1=nulo;

if (p2->sig!=NULL) p2=p2->sig;

else p2=nulo;}}}

if (primero==0){ /*a partir de aqui ya con aux con su valor */

p3=crear_primero(aux); /*colocamos aux en la lista p3*/

primero=1;}

else buscar_siguiente(p3,aux);

}while (p1!=p2); /*mientras que las dos listas no esten apuntando al nulo*/

free (nulo);} /*liberamos el espacio reservado al nodo nulo*/

return(p3);} /*devolvemos el apuntador al primer nodo de p3*/

float evaluar_nodo(nodo *p,float punto)

{int i; /*con esta funcion devolvemos el valor del nodo*/

float resnodo,in; /*evaluado en punto*/

i=1; resnodo=0;in=punto;

if (p->expo>1)

{for (i=1;i!=p->expo;i++) /*Aquí elevamos el punto al valor del expo*/

in=in*punto;

resnodo=p->coef*in;}

else {if (p->expo==1)

resnodo=p->coef*punto;

else resnodo=p->coef;}

return (resnodo);}

LISTA.C

#include <stdio.h>

#include "poli.h"

#include "lista.h"

void insertar_nodo(nodo *p,nodo *aux)

{aux->sig=p->sig; /*funcion que inserta un nodo en lugar de lista*/

p->sig=aux;}

nodo *crear_primero(nodo *aux)

{nodo *p;

p=aux; /*funcion para crear el primer nodo de la lista*/

p->sig=NULL; /*esta condicion es para que el ultimo nodo sienpre*/

return (p);} /* apunte a NULL. devuelve el apuntador al primer nodo*/

nodo *insertar_primero(nodo *p,nodo *aux)

{aux->sig=p; /*para insertar un nodo al pricipio de la lista, es para*/

return (aux);} /*cuando ordenamos la lista en crearla*/

void mostrar_polinomio (nodo *p) /*esta funcion nos saca por pantalla el*/

{printf("\n"); /*polinomio*/

do{ if(p->expo==0){

printf("%d ",p->coef);

p=p->sig;}

else {printf("%dx%d",p->coef,p->expo);

if (p->sig!=NULL) printf("+");

p=p->sig;}

}while (p!=NULL);}

void evaluar_lista (nodo *p) /*esta funcion evalua la lista en un punto*/

{float res,in,punto;

res=0;

printf("\n Punto a evaluar:"); /*pedimos el punto a evaluar*/

scanf("%f",&punto);

do{

res=res+evaluar_nodo(p,punto); /*el resultado sera el resultado acumulado*/

p=p->sig; /*mas el resultado de evaluar el nodo*/

}while (p->sig!=NULL);

res=res+evaluar_nodo(p,punto); /*esto es para evaluar el ultimo nodo*/

printf("%f",res);}

void buscar_siguiente(nodo *p,nodo *aux) /*funcion para buscar donde tenemos*/

{nodo *siguiente; /*que insertar el siguiente nodo*/

int encontrado=0;

while (p->sig!=NULL && encontrado!=1){

siguiente=p->sig;

if (siguiente->expo<aux->expo)

encontrado=1;

else p=p->sig;}

insertar_nodo(p,aux);} /*una vez encontrado el lugar llamamos a insertar_nodo*/

JUEGO DE PRUEVAS


C:\TC\BIN>PROGRAMA1


Menu principal:

1 - Crear polinomio

2 - Suma de polinomios

3 - Derivar polinomios

4 - Evaluacion del polinomio

5 - Mostrar polinomio

6 - Terminar

INTRODUCE ELECCION: 3

La lista no esta creada

Menu principal: (...)

Para ahorrar espacio no copio

otra vez el menu que volveria a salir.

INTRODUCE ELECCION: 7

Opcion incorrecta!

Menu principal: (...)

INTRODUCE ELECCION: 1

Escribir terminos del polinomio deseado:

6 5 4 3 8 7 9 8 1 0 3 2 2 1 0 0

Menu principal: (...)

INTRODUCE ELECCION: 2

Escribir terminos del polinomio deseado:

8 8 3 3 4 4 2 2 5 5 0 0

9x8+8x7+6x5+4x3+3x2+2x1+1

8x8+5x5+4x4+3x3+2x2

17x8+8x7+11x5+4x4+7x3+5x2+2x1+1

Menu principal: (...)

INTRODUCE ELECCION: 3

9x8+8x7+6x5+4x3+3x2+2x1+1

72x7+56x6+30x4+12x2+6x1+2

Menu principal: (...)

INTRODUCE ELECCION: 4

Punto a evaluar: 1.5

437.160156

Menu principal: (...)

INTRODUCE ELECCION: 4

Punto a evaluar: 2

3569.00000

Menu principal: (...)

INTRODUCE ELECCION: 5

9x8+8x7+6x5+4x3+3x2+2x1+1

Menu principal: (...)

INTRODUCE ELECCION: 6

C:\TC\BIN>


CONCLUSIONES

El programa no he conseguido que funcionase en los ordenadores de la universidad, debido a que en casa he utilizado una versión diferente de Turbo C, con los archivos del programa incluyo el archivo ejecutable creado por mi versión de TC al hacer compilar y linkar el project. “PROGRAMA1.EXE”

PROGRAMACIÓN

PRÁCTICA 1

POLINOMIOS

3

2

1

p->sig

*aux

*p

4000

3000

3000

x

2000

4000

p->sig

*aux

*p

4000

3000

3000

x

2000

3000

p->sig

*aux

*p

4000

x

3000

x

2000

3000

Ahora devolvemos

*aux como el primer

nodo de la lista

2

1

*aux

*p

4000

2000

2000

x

*aux

*p

4000

x

2000

x