Lista en C++ (Resuelto)

[Franz1628]

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  

Código (cpp) [Seleccionar] Expandir


#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);
}



[leogtz]

Tienes que hacer una prueba de escritorio con un diagrama de listas, sino te será dificil entenderlo.

[Franz1628]

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)

[rir3760]

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

[Khronos14]

En C++ puedes usar *& en los parámetros de tus funciones, en vez de ** para pasar la referencia de un puntero.

Saludos.

[Franz1628]

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)

[Franz1628]

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 

Gracias