| Ver tema anterior :: Ver siguiente tema | | Autor | Mensaje |
|---|
hongee
Registrado: 16 Nov 2013
Mensajes: 23
|  Publicado: 16/02/2014 9:34 am | | | Título: Borrar todos los valores menores al ultimo ingresado lista |
| Estimados,
Estoy realizando un programa que elimina todos los valores de una lista que sean menores al ultimo valor ingresados.
Ej: ingresamos 5,10,3,4. Deberia imprimir 5-10-4.
El programa me imprime 5-10-3.
| Código: |
#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable: 4996)
typedef struct snodo
{
int valor;
struct snodo *sig;
} tnodo;
typedef tnodo *tpuntero;
void imprimir (tpuntero cabeza);
void EliminarMenor (tpuntero *cabeza,int ultimo);
void insertarfinal(tpuntero *cabeza, int dato);// insertar al final
int main()
{
tpuntero cabeza;
int valor,ultimo;
cabeza=NULL;
printf ("Ingrese un numero (-1) para salir:");
scanf ("%d",&valor);
while (valor!=-1)
{
insertarfinal(&cabeza,valor);
ultimo=valor;
printf ("Ingrese un numero (-1) para salir:");
scanf ("%d",&valor);
}
printf ("\n");
printf ("Los valores ingresados son:\n");
imprimir (cabeza);
printf ("###Elemetos menores a %d eliminados\n",ultimo);
EliminarMenor(&cabeza,ultimo);
imprimir (cabeza);
system ("pause");
return 0;
}
void EliminarMenor(tpuntero *cabeza,int ultimo)
{
tpuntero ptr1, ptr2, men;
ptr1 = *cabeza;
/* Tomamos uno a uno los elementos */
while(ptr1 != NULL && ptr1->sig != NULL)
{
ptr2 = ptr1;
/* Comparamos los datos */
while(ptr2->sig != NULL)
{
/* Si hay menor lo borramos */
if(ptr1->valor < ultimo)
{
men = ptr2->sig;
ptr2->sig = ptr2->sig->sig;
free(men);
}
else
{
ptr2 = ptr2->sig;
}
}
ptr1 = ptr1->sig;
}
}
void imprimir (tpuntero cabeza)
{
while (cabeza!=NULL)
{
printf ("%d",cabeza->valor);
cabeza=cabeza->sig ;
printf ("\n");
}
}
void insertarfinal(tpuntero *cabeza, int dato)
{
tpuntero actual, anterior, nuevo;
actual = *cabeza;
anterior = NULL;
while(actual != NULL)
{
anterior = actual;
actual = actual->sig;
}
nuevo = (tpuntero)malloc(sizeof(tnodo));
nuevo->valor = dato;
nuevo->sig = actual;
if(anterior != NULL)
anterior->sig = nuevo;
else
*cabeza = nuevo;
}
|
Graciass
Saludos |
| | Volver arriba | |  | dehm
Registrado: 29 Abr 2011
Mensajes: 139
| | Publicado: 17/02/2014 6:33 am | | | Título: |
| No termino de entender el código que has puesto para borrar, pero parece algo complicado.
Supuestamente, sería suficiente con evaluar el valor del siguiente elemento de la lista al que apunta el puntero que usamos para recorrerlo.
Una opción es tener dos punteros, uno apuntando al nodo anterior al que contiene el valor y el otro al nodo que contiene el valor:
| Código: | tpuntero anterior, actual; |
Te mueves con el puntero anterior
Una vez que sepas que
| Código: | anterior->siguiente<valor |
posicionas actual apuntando al mismo lugar que el nodo que contiene el valor:
| Código: | actual=anterior->siguiente |
Ahora ya puedes "puentear" el nodo a borrar:
| Código: | anterior->siguiente=actual->siguiente |
y por último borrar el nodo que contiene ese valor:
Bueno, espero no haberme equivocado demasiado.
Saludos
_________________
Aprendiendo |
| | Volver arriba | | | hongee
Registrado: 16 Nov 2013
Mensajes: 23
| | Publicado: 17/02/2014 10:04 am | | | Título: |
| No logro entender lo que me quieres decir.
Te referis a hacer asi el codigo.
| Código: |
void EliminarMenor(tpuntero *cabeza,int ultimo)
{
tpuntero anterior, actual;
actual = *cabeza;
/* Tomamos uno a uno los elementos */
while(actual != NULL)
{
/* Si hay menor lo borramos */
if(actual->valor < ultimo)
{
anterior=actual;
actual=anterior->sig;
free(anterior);
}
else
{
actual = actual->sig;
}
}
*cabeza=actual;
}
|
|
| | Volver arriba | | | | dehm
Registrado: 29 Abr 2011
Mensajes: 139
| | Publicado: 17/02/2014 11:42 am | | | Título: |
| Hola:
La idea es usar dos punteros, uno que apuntará al nodo anterior al que queremos borrar y otro al propio nodo. Este último nos servirá para que cuando saquemos al nodo de la lista, no lo perdamos y podamos borrarlo, además de que nos da la información de dónde está el siguiente nodo, que necesita el anterior para enlazarlo.
Entonces, sería así:
| Código: | void EliminarMenor(tpuntero *cabeza,int ultimo)
{
tpuntero anterior, actual;
anterior = *cabeza; //uso anterior para ir recorriendo la lista
/* Tomamos uno a uno los elementos */
while(anterior->siguiente != NULL)
{
/* Si hay menor lo borramos */
if(anterior->siguiente < ultimo)
{
actual=anterior->siguiente //posiciono actual en el nodo que quiero borrar
anterior->siguiente=actual->siguiente;//enlazo el nodo anterior al que quiero borrar con el nodo siguiente al que quiero borrar. "Puenteo" el nodo que quiero borrar y ya lo tengo sacado de la lista
free(actual);//una vez fuera de la lista, lo elimino
}
anterior=anterior->siguiente//continuo avanzando en la lista
} |
Bueno, creo que esta sería la secuencia. No lo he probado, y a la vez que estoy escribiendo esto, me estoy dando cuenta de que creo que no evalúa el primer elemento, así que tendrías que considerar esto.
Saludos
_________________
Aprendiendo |
| | Volver arriba | | | hongee
Registrado: 16 Nov 2013
Mensajes: 23
| | Publicado: 17/02/2014 11:59 am | | | Título: |
| Hola, lo probé y no me funciono.
De todas maneras hay un error cuando estas en el IF, la condicion tiene que ser anterior->valor < ultimo, ya que tengo que comparar los valores.
saludos |
| | Volver arriba | | | dehm
Registrado: 29 Abr 2011
Mensajes: 139
| | Publicado: 17/02/2014 12:19 pm | | | Título: |
| Disculpa, ya que el código tenía errores (la cosa de no probarlo)
Te aclaro:
| Cita: | | De todas maneras hay un error cuando estas en el IF, la condicion tiene que ser anterior->valor < ultimo, ya que tengo que comparar los valores. |
La cosa es que me interesa buscar el valor desde el nodo anterior, no desde el propio nodo. Es sólo a efectos prácticos. Pero tienes razón, no estaba comparando el contenido del nodo, el valor 
El fallo que sí que tenía, es que estaba pasando el nodo al nodo siguiente independientemente de que ese nodo fuera borrado o no. Si el nodo se borraba, al pasar al nodo siguiente me estaba saltando el valor siguiente al nodo que quería borrar (vaya trabalenguas!!) y había nodos que no evaluaba.
Y por supuesto, seguía existiendo el problema del primer nodo, que no lo evaluaba.
Te pondo el código corregido, al final he copiado lo que tenías y he escrito bien lo que te puse antes:
| Código: | void EliminarMenor(tpuntero *cabeza,int ultimo) { tpuntero anterior, actual; anterior = *cabeza; //uso anterior para ir recorriendo la lista /* Tomamos uno a uno los elementos */ while(anterior->sig != NULL) { /* Si hay menor lo borramos */ if(anterior->sig->valor < ultimo) { actual=anterior->sig; //posiciono actual en el nodo que quiero borrar anterior->sig=actual->sig;//enlazo el nodo anterior al que quiero borrar con el nodo siguiente al que quiero borrar. "Puenteo" el nodo que quiero borrar y ya lo tengo sacado de la lista free(actual);//una vez fuera de la lista, lo elimino } else { anterior=anterior->sig;//continuo avanzando en la lista } } //tratamiento del primer elemento anterior=*cabeza; //posiciono de nuevo anterior al inicio de la lista if (anterior->valor<ultimo) { *cabeza=anterior->sig; free(anterior); } } |
_________________
Aprendiendo |
| | Volver arriba | | | | hongee
Registrado: 16 Nov 2013
Mensajes: 23
| | Publicado: 17/02/2014 12:38 pm | | | Título: |
| Ahí funciono  .
No hace falta que pidas disculpas por el error  .
Muchas Gracias dehn.
saludos |
| | Volver arriba | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 7516
Ubicación: Mexico
| | Publicado: 18/02/2014 6:47 pm | | | Título: |
| Para insertar al final de la lista el proceso lo puedes simplificar considerando directamente los dos casos (lista vacía y lista con al menos un nodo) con lo cual eliminas la variable "anterior":
| Código: | void insertarfinal(tpuntero *cabeza, int dato)
{
tpuntero nuevo;
nuevo = malloc(sizeof *nuevo);
nuevo->valor = dato;
nuevo->sig = NULL;
if (*cabeza == NULL)
*cabeza = nuevo;
else {
tpuntero p;
for (p = *cabeza; p->sig != NULL; p = p->sig)
;
p->sig = nuevo;
}
} |
Otra opción es utilizando el parámetro para realizar el recorrido (mas feo e ineficiente pero sin casos especiales):
| Código: | void insertarfinal(tpuntero *p, int dato)
{
tpuntero nuevo;
nuevo = malloc(sizeof *nuevo);
nuevo->valor = dato;
nuevo->sig = NULL;
while (*p != NULL)
p = &(*p)->sig;
*p = nuevo;
} |
Siguiendo la aproximación anterior se puede acortar la función que elimine los nodos con un valor menor al ultimo:
| Código: | void EliminarMenor(tpuntero *p, int max)
{
while (*p != NULL)
if ((*p)->valor < max){
tpuntero aux;
aux = *p;
*p = (*p)->sig;
free(aux);
}else
p = &(*p)->sig;
} |
Un saludo
_________________
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language |
| | Volver arriba | | | dehm
Registrado: 29 Abr 2011
Mensajes: 139
| | Publicado: 19/02/2014 2:25 am | | | Título: |
| Hola rir3760:
Muchas gracias por la aclaración y la explicación.
Hay una expresión que no entiendo:
¿Por qué no poner?
Saludos
_________________
Aprendiendo |
| | Volver arriba | | | | hongee
Registrado: 16 Nov 2013
Mensajes: 23
| | Publicado: 23/02/2014 9:22 am | | | Título: |
| Al igual que dehn, no me queda clara la expresion
Adapte el codigo con p=p->sig (en mi caso actual) pero me da error.
No entiendo como es que en siguiente no pone la dir del valor que sigue y sigue manteniendo los valores anteriores.
| Código: |
void EliminarMenor2(tpuntero *cabeza, int ultimo)
{
tpuntero actual,aux;
actual = *cabeza;
while ( actual != NULL)
{
if (actual->valor < ultimo)
{
aux = actual;
actual = actual->sig;
free(aux);
}else
actual = actual->sig;
}
*cabeza=actual;
}
|
Saludos |
| | Volver arriba | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 7516
Ubicación: Mexico
| | Publicado: 26/02/2014 7:37 am | | | Título: |
| | dehm escribió: | Hay una expresión que no entiendo:
¿Por qué no poner?
|
Porque los tipos son distintos: la variable "p" es de tipo "tpuntero *" mientras que la variable "cabeza" (de main) y los campos "sig" de cada nodo son de tipo "tpuntero".
----
Para explicarlo mejor la forma usual de procesar una lista:
| Código: | ---- ---- ----
| D | | D | | D |
primero-->| S |-->| S |-->| S |--> NULL
---- ---- ---- |
Es mediante un puntero que en cada iteración almacene la dirección del nodo en cuestión:
| Código: | Iteracion (1) (2) (3) (Salida)
p p p p
| | | |
| | | |
V V V |
---- ---- ---- |
| D | | D | | D | V
primero-->| S |-->| S |-->| S |--> NULL
---- ---- ----
D == Dato del nodo
S == campo "sig" apuntando al siguiente nodo o NULL si es el ultimo |
En la primera iteración el valor de "p" es la dirección del primer nodo, en la segunda la del segundo, ..., por ultimo toma el valor NULL y ello causa la salida del bucle.
El problema con esa aproximación es que no podemos afectar al nodo anterior porque este se proceso en la iteración anterior o bien es el caso especial de la variable "primero".
----
Una solución a esto es no utilizar un puntero a <nodo> sino un puntero a <puntero a nodo>, esta es:
| Código: | ---- ---- ----
| D | | D | | D |
primero-->| S |-->| S |-->| S |--> NULL
^ ^ ^ ^
| | | |
| | | |
p p p p
(1) (2) (3) (Salida)
D == Dato el nodo
S == campo "sig" apuntando al siguiente nodo o NULL si es el ultimo |
En la primera iteración el valor de "p" es la dirección de la variable "primero", al aplicar indireccion "*p" solo es otra forma de referirnos a la variable "primero".
Para la segunda iteración debemos obtener la dirección del campo "sig" del primer nodo, para ello utilizamos:
1) *p resulta en un puntero al nodo.
2) (*p)-> resulta en el nodo.
3) (*p)->sig resulta en el campo sig del nodo.
4) &(*p)->sig resulta en la dirección en memoria del campo sig del nodo en cuestión.
Hay que recordar que con la primera aproximación necesitábamos de una variable "anterior" y esta almacenaba la dirección en memoria del nodo anterior y lo único que hacíamos con ese nodo era modificar su campo "sig" teniendo en cuenta el caso especial del primer nodo (no tiene nodo anterior, en su lugar debemos modificar la variable "primero").
Si lo piensan un poco esta aproximación hace lo mismo pero enfocada solo en punteros (la variable "primero" y el campo "sig" de cada nodo). Como utilizamos punteros en lugar de "anterior->sig" utilizamos "*p".
----
| hongee escribió: | Adapte el codigo con p=p->sig (en mi caso actual) pero me da error.
No entiendo como es que en siguiente no pone la dir del valor que sigue y sigue manteniendo los valores anteriores.
| Código: | void EliminarMenor2(tpuntero *cabeza, int ultimo)
{
tpuntero actual,aux;
actual = *cabeza;
while ( actual != NULL)
{
if (actual->valor < ultimo)
{
aux = actual;
actual = actual->sig;
free(aux);
}else
actual = actual->sig;
}
*cabeza=actual;
} |
|
Esa función esta mal por dos razones: primero porque no reajusta el campo "sig" del nodo anterior y segundo porque el valor de la variable "actual" después del bucle siempre sera NULL (si no fuera así el bucle nunca terminaría).
Un saludo
_________________
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language |
| | Volver arriba | | | hongee
Registrado: 16 Nov 2013
Mensajes: 23
| | Publicado: 26/02/2014 1:20 pm | | | Título: |
| Muchas Gracias por la explicación, muy completa como siempre.
Antes que nada, no es que no quiero usar tu forma de resolver el problema, sino que estoy tratando de entender mis errores y de realizar el ejercicio con lo que me explicaron (no digo que este mal tu codigo, sino que para hacerlo asi se necesita un mayor aprendizaje quizas).
Muchas veces me has ayudado, y como se ve tu nivel es muy superior al mio y trato de bajar a mi nivel lo que indicas (lo cual es muy bueno ya que me permite ver otras opciones).
Tratando de entender el final de tu explicación sobre mi código hice lo siguiente.
| Código: |
void EliminarMenor3(tpuntero *cabeza, int ultimo)
{
tpuntero actual,aux,anterior;
actual = *cabeza;
anterior=NULL;
while ( actual != NULL)
{
if (actual->valor < ultimo)
{
aux = actual;
actual = actual->sig;
free(aux);
}else
{
if (anterior==NULL)// 1er nodo
{
anterior=actual;
actual = actual->sig;
}
else
{
aux=actual ;
actual = actual->sig;
anterior->sig=aux;
}
}
}
*cabeza=anterior;
}
|
De mas esta decir que no funciona. Cuando hago el debug, pierdo los valores del medio por ej si ingreso 1-5-6-3-4 anterior queda con 5-4 al final.
Ya no se mas que hacer.
dehm tu forma de hacerlo tmb es valida, pero como dije antes estoy tratando de entender mi error que ya se donde esta pero no me doy cuenta como solucionarlo.
Muchas Gracias |
| | Volver arriba | | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 7516
Ubicación: Mexico
| | Publicado: 28/02/2014 7:00 am | | | Título: |
| La función esta mal en varias partes.
* Si el nodo no cumple con la condición para ser eliminado no tienes porque distinguir entre primer nodo y algún otro, simplemente el anterior pasa a ser el actual y el actual el siguiente a este.
* Donde si debes distinguir es cuando se debe eliminar un nodo: el primero o alguno después de este.
* Si eliminas el primer nodo debes actualizar la variable "cabeza" de main, para ello utilizas "*cabeza" en la función EliminarMenor3.
Con los cambios la función termina así:
| Código: | void EliminarMenor3(tpuntero *cabeza, int ultimo)
{
tpuntero anterior;
tpuntero actual;
anterior = NULL;
actual = *cabeza;
while (actual != NULL)
if (actual->valor < ultimo){
if (anterior == NULL){
*cabeza = (*cabeza)->sig;
free(actual);
actual = *cabeza;
}else {
anterior->sig = actual->sig;
free(actual);
actual = anterior->sig;
}
}else {
anterior = actual;
actual = actual->sig;
}
} |
Te recomiendo, si tienes problemas para entender la función, que sigas con lápiz y papel (o mejor una pizarra) paso a paso los cambios que se deben hacer en una lista pequeña (unos cinco elementos).
Un saludo
_________________
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language |
| | Volver arriba | | | hongee
Registrado: 16 Nov 2013
Mensajes: 23
| | Publicado: 28/02/2014 1:02 pm | | | Título: |
| Muchas Gracias rir3760 como siempre excelente sus aclaraciones.
Entendí donde estaba el error en mi función.
Solo me queda una duda, haciendo el debug veo que cabeza se "actualiza" con anterior, en que momento le indico que haga referencia a anterior?
saludos |
| | Volver arriba | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 7516
Ubicación: Mexico
| | Publicado: 02/03/2014 7:17 am | | | Título: |
| | hongee escribió: | | Solo me queda una duda, haciendo el debug veo que cabeza se "actualiza" con anterior, en que momento le indico que haga referencia a anterior? |
En ninguno.
El puntero "*cabeza" solo se actualiza cuando se debe eliminar el primer nodo:
| Código: | while (actual != NULL)
if (actual->valor < ultimo){
if (anterior == NULL){
*cabeza = (*cabeza)->sig;
free(actual);
actual = *cabeza; |
Para visualizarlo mejor en ese momento el estado de la lista y los punteros es:
| Código: | *cabeza
|
|
V
---- ---- ----
| D | | D | | D |
| S |-->| S |-->| S |--> NULL
NULL ---- ---- ----
^ ^
| |
| |
anterior actual |
Aqui anterior es NULL mientras que *cabeza y primero apuntan al mismo nodo (el primero en la lista).
Una vez elimines todos los nodos al inicio de la lista que cumplen la condición (valor menor al ultimo) pasas a revisar los nodos en la segunda, tercera, etc. posición, ahí el estado de la lista es:
| Código: | *cabeza
|
|
V
---- ---- ----
| D | | D | | D |
| S |-->| S |-->| S |--> NULL
---- ---- ----
^ ^
| |
| |
anterior actual |
Como puedes ver si bien *cabeza y anterior apuntan al mismo nodo el primero ya no se toca (eso de ser necesario ya ocurrió en el paso anterior), solo se actualiza su campo "sig" en el caso de eliminar el segundo nodo.
Un saludo
_________________
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language |
| | Volver arriba | | | | |
| No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
|
|
| |
F.A.Q.
Conéctese para revisar sus mensajes