04/09/2008, 05:26
|
| | | Fecha de Ingreso: agosto-2008
Mensajes: 161
Antigüedad: 16 años, 4 meses Puntos: 0 | |
| Respuesta: Invertir lista circular
Códigos:
Código:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include "tabla.c"
typedef int Clave;
typedef double Valor;
int comparaClaves( void *c1, void *c2 ) {
return *(int *)c1 - *(int *)c2;
}
void imprimeClave( void *p ) {
printf( "clave: %d\n", *(int *)p );
}
void imprimeValor( void *p ) {
printf("\n%p ", p);
printf( " valor: %f\n", *(double *)p );
}
int main( ) {
Tabla tabla;
Clave clave;
Valor valor;
int i, j;
inicializa( &tabla, sizeof( Clave ), sizeof( Valor ), comparaClaves );
for( i = 1; i <= 5; i++ ) {
clave = i;
for( j = 1; j <= i; j++ ) {
valor = i + j / 100.0;
if( !inserta( &tabla, &clave, &valor ) ) {
printf( "No se pudo insertar\n" );
}
}
}
for( i = 9; i >= 1; i-- ) {
clave = i;
for( j = 1; j <= i; j++ ) {
valor = i + j / 10000.0;
if( !inserta( &tabla, &clave, &valor ) ) {
printf( "No se pudo insertar\n" );
}
}
}
printf( "claves: %d, valores: %d\n", (int)numClaves( &tabla ), (int)numValores( &tabla ) );
printf( "\nRecorrido:\n" );
ordenaValores(&tabla, comparaClaves);
recorrido( &tabla, imprimeClave, imprimeValor );
finaliza( &tabla );
return 0;
}
La otra:
Código:
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
typedef void (*funcionProcesa)(void *);
/* Compara dos valores. El resultado será menor, igual o mayor que 0
* si el primer elemento es menor, igual o mayor que el segundo */
typedef int (*funcionCompara)(void *,void *);
/*--------------ESTRUCTURAS---------------------*/
/* Nodos de la lista de valores asociados a un NodoClave, será enlazada y
* circular. El siguiente del último será el primero. */
typedef struct NodoValor{
void *valor;
struct NodoValor *siguiente;
} NodoValor;
/* Nodos de la Lista de claves. Será una lista doblemente enlazada ordenada
* por el valor de la clave */
typedef struct NodoClave {
void *clave;
NodoValor *ultimo; /* ultimo NodoValor con esta clave */
struct NodoClave *anterior; /* anterior NodoClave */
struct NodoClave *siguiente; /* siguiente NodoClave */
} NodoClave;
typedef struct {
size_t tamClave; /* tamaño de la clave */
size_t tamValor; /* tamaño de los valores */
size_t numClaves; /* numero de claves */
size_t numValores; /* numero de valores */
NodoClave *primero; /* primer nodo clave */
NodoClave *ultimo; /* último nodo clave */
funcionCompara comparaClaves; /* función para comparar las claves */
} Tabla;
/* Posiciones de la Tabla */
typedef struct {
NodoValor *valor;
NodoClave *clave;
Tabla *tabla;
} Posicion;
/* Creacion. Inicializamos la tabla. Se pasa como parametro el tamaño de cada clave,
* el tamaño de los valores y una funcion para comparar claves */
void inicializa(Tabla *tabla, size_t tamClave, size_t tamValor, funcionCompara fclaves){
tabla->tamClave=tamClave;
tabla->tamValor=tamValor;
tabla->numClaves=0;
tabla->numValores= 0;
tabla->primero=NULL;
tabla->ultimo=NULL;
tabla->comparaClaves=fclaves;
return;
}
bool inserta(Tabla *tabla, void *clave, void *valor){
bool insercionCorrecta=false;
NodoClave *claveAux, *claveAux2, *nuevaClave;
NodoValor *nuevoValor, *exValorUltimo;
claveAux= tabla->primero;
if (tabla->primero==NULL && tabla->ultimo==NULL){ /* tabla vacia. */
nuevaClave= (NodoClave *) malloc (sizeof (NodoClave));
nuevaClave->clave= (void *) malloc (tabla->tamClave);
nuevoValor= (NodoValor *)malloc(sizeof(NodoValor));
nuevoValor->valor= (void *)malloc (tabla->tamValor);
memcpy(nuevoValor->valor, valor, tabla->tamValor);
memcpy (nuevaClave->clave, clave, tabla->tamClave);
nuevaClave->ultimo=nuevoValor;
nuevoValor->siguiente=nuevoValor;
nuevaClave->anterior=NULL;
nuevaClave->siguiente=NULL;
tabla->primero=nuevaClave;
tabla->ultimo=nuevaClave;
tabla->numClaves++;
tabla->numValores++;
insercionCorrecta=true;
}
else{
while( claveAux!=NULL && tabla->comparaClaves(claveAux->clave, clave)!=0){
claveAux=claveAux->siguiente;
}
if(claveAux==NULL){ /* La clave no está */
if (tabla->comparaClaves(clave, tabla->primero->clave)<0 && tabla->primero->anterior==NULL){
/* la clave es < a la primera */
nuevaClave= (NodoClave *) malloc (sizeof (NodoClave));
nuevaClave->clave= (void *) malloc (tabla->tamClave);
nuevoValor= (NodoValor *)malloc(sizeof(NodoValor));
nuevoValor->valor= (void *)malloc (tabla->tamValor);
memcpy (nuevoValor->valor, valor, tabla->tamValor);
memcpy (nuevaClave->clave, clave, tabla->tamClave);
nuevaClave->ultimo=nuevoValor;
nuevoValor->siguiente=nuevoValor;
nuevaClave->anterior=NULL;
nuevaClave->siguiente=tabla->primero;
tabla->primero->anterior=nuevaClave;
tabla->primero= nuevaClave;
tabla->numClaves++;
tabla->numValores++;
insercionCorrecta=true;
}
else{
if (tabla->comparaClaves(clave, tabla->ultimo->clave)>0 && tabla->ultimo->siguiente==NULL){ /* la clave es > a la ultima */
nuevaClave= (NodoClave *) malloc (sizeof (NodoClave));
nuevaClave->clave= (void *) malloc (tabla->tamClave);
nuevoValor= (NodoValor *)malloc(sizeof(NodoValor));
nuevoValor->valor= (void *)malloc (tabla->tamValor);
memcpy(nuevoValor->valor, valor, tabla->tamValor);
memcpy (nuevaClave->clave, clave, tabla->tamClave);
nuevaClave->ultimo= nuevoValor;
nuevoValor->siguiente=nuevoValor;
nuevaClave->anterior=tabla->ultimo;
tabla->ultimo->siguiente=nuevaClave;
nuevaClave->siguiente=NULL;
tabla->ultimo= nuevaClave;
tabla->numClaves++;
tabla->numValores++;
insercionCorrecta=true;
}
else{
/* clave entre la primera y la ultima */
claveAux2=tabla->primero;
nuevaClave= (NodoClave *) malloc (sizeof (NodoClave));
nuevaClave->clave= (void *) malloc (tabla->tamClave);
nuevoValor= (NodoValor *)malloc(sizeof(NodoValor));
nuevoValor->valor= (void *)malloc (tabla->tamValor);
memcpy(nuevoValor->valor, valor, tabla->tamValor);
memcpy (nuevaClave->clave, clave, tabla->tamClave);
while(tabla->comparaClaves(claveAux2->clave, clave)<0){
claveAux2=claveAux2->siguiente;
}
nuevaClave->ultimo= nuevoValor;
nuevoValor->siguiente=nuevoValor;
nuevaClave->anterior= claveAux2->anterior;
nuevaClave->siguiente= claveAux2;
claveAux2->anterior->siguiente=nuevaClave;
claveAux2->anterior = nuevaClave;
tabla->numClaves++;
tabla->numValores++;
insercionCorrecta=true;
}
}
}
else{ /* la clave se encuentra en la tabla */
exValorUltimo=claveAux->ultimo;
nuevoValor= (NodoValor *)malloc(sizeof(NodoValor));
nuevoValor->valor= (void *)malloc (tabla->tamValor);
memcpy(nuevoValor->valor, valor, tabla->tamValor);
nuevoValor->siguiente=exValorUltimo->siguiente;
exValorUltimo->siguiente=nuevoValor;
claveAux->ultimo=nuevoValor;
tabla->numValores++;
insercionCorrecta=true;
}
}
return insercionCorrecta;
}
/* Se ordenan en orden ascendente los valores de las listas dentro de cada clave, no se cambian valores entre listas.
* Después de la ordenación cada clave tendrá asociados los mismos valores que tenÃ*a, pero estarán ordenados de menor a mayor*/
void ordenaValores(Tabla *tabla, funcionCompara fvalores){
NodoClave *claveAux;
NodoValor *valorAux, *valorAuxSig;
void *elemento;
int fin;
for(claveAux = tabla->primero ; claveAux->siguiente != NULL ; claveAux = claveAux->siguiente){
do {
fin=0;
valorAuxSig=valorAux->siguiente;
printf("Prueba");
for (valorAux=claveAux->ultimo; valorAux!=valorAuxSig; valorAux=valorAux->siguiente) {
if (fvalores (valorAux->valor, valorAuxSig->valor)<0) {
elemento=valorAux->valor; /* Uso fin como variable temporal*/
valorAux->valor=valorAuxSig->valor;
valorAuxSig->valor=elemento;
fin=1;
}
}
} while(fin==1);
}
}
/* Recorrido de la tabla. Se procesan las claves de modo ordenado. Para
* cada clave se llama a la funcion procesaClave y a continuacion se procesan
* sus valores asociados, del primero al ultimo, llamando a la funcion
* procesaValor */
void recorrido(Tabla *tabla, funcionProcesa procesaClave, funcionProcesa procesaValor){
NodoValor *valorAux;
NodoClave *claveAux;
claveAux = tabla->primero;
while(claveAux!=NULL){
procesaClave(claveAux->clave);
valorAux = claveAux->ultimo->siguiente;
while(claveAux->ultimo != valorAux){
procesaValor(valorAux->valor);
valorAux = valorAux->siguiente;
}
procesaValor(valorAux->valor);
claveAux = claveAux->siguiente;
}
return ;
}
/* Destruccion. Se liberan los recursos asociados a la Tabla. Todos los
* NodosClave y NodosValor */
void finaliza(Tabla *tabla){
NodoClave *claveAux;
NodoValor *valorAux;
claveAux = tabla->primero;
while(claveAux != NULL){
valorAux = claveAux->ultimo->siguiente;
while(claveAux->ultimo != valorAux){
free(valorAux->valor);
valorAux = valorAux->siguiente;
tabla->numValores--;
printf("Numero de valores de la tabla: %d\n",tabla->numValores);
}
tabla->numValores--;
free(valorAux->valor);
free(claveAux->clave);
free(claveAux);
tabla->numClaves--;
printf("Numero de claves de latabla: %d\n",tabla->numClaves);
claveAux = claveAux->siguiente;
}
return ;
}
Creo que he metido todo
Ayuda!!   |
