Este es un ejemplo de insertar un nodo a una lista en forma ordenada pero en la parte de la funcion insertarNodo (en la parte de "else" no veo como cambia el *cab para que se haya ingresado el NODO)
El codigo si funciona pero esa parte es la que no entiendo ,supongo que esta parte de :
neo->sgte = p->sgte;
p->sgte = neo;
"Pero esto como afectaria *cab ???"
Si alguien tiene alguna idea se lo agradecería ;)
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
using namespace std;
typedef int TD;
struct NODO {
TD valor;
NODO *sgte;
};
void crearLista(NODO **cab);
void insertarNodo(NODO **cab, int dato);
void mostrarLista(NODO *cab);
int listaVacia(NODO *cab);
int main()
{
NODO *A;
crearLista(&A);
insertarNodo(&A, 20);
insertarNodo(&A, 30);
insertarNodo(&A, 5);
insertarNodo(&A, 80);
insertarNodo(&A, 34);
insertarNodo(&A, 10);
mostrarLista(A);
system("PAUSE");
return 0;
}
void crearLista(NODO **cab)
{
*cab=NULL;
}
//Inserta elmentos en forma ordenada
void insertarNodo(NODO **cab, int dato)
{
//NODO nuevo, anterior;
NODO *neo, *p;
neo = (NODO*)malloc(sizeof(NODO));
neo->valor = dato;
// Si la lista está vacía
if(listaVacia(*cab) || (*cab)->valor > dato) {
//Añadimos la lista a continuación del nuevo nodo
neo->sgte = *cab;
//Ahora, la lista tiene un nuevo nodo
*cab = neo;
}
else {
// Buscar la posicion adecuiada para el nuevo nodo
p = *cab;
// Busca la posicion adecuada para dato
while(p->sgte && p->sgte->valor <= dato){
p = p->sgte;
}
neo->sgte = p->sgte;
p->sgte = neo;
}
}
void mostrarLista(NODO *cab)
{
NODO *p = cab;
if(listaVacia(p))
printf("Lista vacía\n");
else {
while(p) {
printf("%d -> ", p->valor);
p = p->sgte;
}
printf("\n");
}
}
int listaVacia(NODO *cab)
{
return (cab == NULL);
}
Tienes que hacer una prueba de escritorio con un diagrama de listas, sino te será dificil entenderlo.
Bueno lo estoy haciendo en un papel algo asi
por ejemplo ya habiendo ingresado algunos valores
mi *cab tendria 10->13->
ahora al ingresar por ejemplo dato = 15 (pasaría esto)
entraría a la función insertarNodo dando a neo->dato = 15 ahora entraría en la parte de else porque no es vacía la lista)
ahora dando p = *cab;
"p" sería 10->13-> (entonces p->sgte sería 13-> && p->sgte->dato sería 13 )
ahora entrando al while (entraria al while ya que 13 es <= 15)
entonces p = p->sgte entonces p sería 13-> (y p->sgte sería NULL con esto ya no entra denuevo al while)
despues se hace: neo->sgte = p->sgte; (con esto neo->sgte = NULL)
y neo sería 15-> ya que neo->dato le dimos 15
despues se hace: p->sgte = neo; (con esto p->sgte = 15->)
con esto p sería 13->15-> y terminó
Pero donde cambia *cab ?? (se supone que eso hay que modificar !) (a menos que con el p estamos cambiando dentro del *cab )(no entiendo la verdad) :-\
Cita de: Franz1628 en 7 Julio 2011, 19:49 PM
Este es un ejemplo de insertar un nodo a una lista en forma ordenada pero en la parte de la funcion insertarNodo (en la parte de "else" no veo como cambia el *cab para que se haya ingresado el NODO)
El codigo si funciona pero esa parte es la que no entiendo ,supongo que esta parte de :
neo->sgte = p->sgte;
p->sgte = neo;
"Pero esto como afectaria *cab ???"
No lo afecta y ese es el punto.
En la función de inserción primero se revisa si el nuevo nodo debe colocarse como primero, si es así se utiliza "*cab" para modificar el puntero al primer nodo de la lista (la variable "A" de la función "main").
Si no debe insertarse como primero basta con actualizar los punteros "sig" del nodo que corresponda (alguno después del primero) y del nuevo nodo.
Un saludo
En C++ puedes usar *& en los parámetros de tus funciones, en vez de ** para pasar la referencia de un puntero.
Saludos.
p=*cab ; eso esta bien
Pero lo que no entiendo es que despues se le da a p = p->sgte y modificando el p se modifica el *cab (eso es muy extraño)
Bueno gracias a sus respuestas ya entendí lo que pasaba
que el *cab era tenias todos los datos y era que solo tenia un dato y un puntero a otro nodo :xD
Gracias ;-)