Autor Tema: Estructuras de Datos Dinámicas - La Pila  (Leído 10742 veces)

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado mxgxw

  • Global Moderator
  • Trade Count: (1)
  • The Communiter-
  • *
  • Thank You
  • -Given: 27
  • -Receive: 651
  • Mensajes: 5662
  • Starlet - 999cc
    • mxgxw
Estructuras de Datos Dinámicas - La Pila
« : enero 08, 2012, 10:17:50 pm »
La Pila

Una de las estructuras de datos dinámicas más utilizadas es la Pila (stack), esta estructura de datos es del tipo Last In First Out (LIFO: Último que entra, primero que sale).

En este corto tutorial intentaré explicarles varios conceptos: Asignación de Memoria Dinámica, Relación entre Arreglos y Punteros, Estructuras y Listas Anidadas. Así que espero que esten familiarizados aunque sea un poco con estos conceptos.

Al final tendremos una implementación bastante sencilla de una Pila que puede ser utilizada o adaptada para almacenar diferentes tipos de datos.

Decidí escribir este pequeño tutorial en C ya que en lenguajes de más alto nivel aunque es más fácil entender la parte abstracta muchas veces no queda claro que es lo que sucede "tras bambalinas" al momento de asignar y utilizar la memoria en la computadora. (Además que casi no hay POSTS en C/C++)

Una vez dicho esto: ¡¡Comencemos!!

La memoria dinámica

Cuando comenzamos a programar en C, se nos enseña a utilizar diferentes tipos de datos según la información que vamos a guardar en nuestro programa. Cuando queremos guardar conjuntos de datos nos enseñan a utilizar los arreglos. Los arreglos nos permiten guardar en memoria un conjunto de datos del mismo tipo.

El problema de los arreglos es que son estáticos, es decir, una vez hemos declarado su tamaño no podemos modificarlo, al menos no sin correr el riesgo de generar un error de acceso en la memoria.

Para solventar este problema existen en las librerías estándar de C dos funciones sumamente útiles, estas son malloc y free.

"malloc" se encarga de reservar un espacio de memoria del tamaño en bytes que le especifiquemos.

"free" por el contrario se encarga de liberar la memoria que hemos asignado haciendo uso de malloc.

Por ejemplo, si quisieramos reservar espacio en memoria para un arreglo 4 bytes podríamos hacer lo siguiente:

Código: [Seleccionar]
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
  // Inicializamos el arreglo
  int *array_int = (int*)malloc(sizeof(int)*4);

  array_int[0] = 1;
  array_int[1] = 2;
  array_int[2] = 3;
  array_int[3] = 4;

  printf("Pos 0: %i\n",array_int[0]);
  printf("Pos 1: %i\n",array_int[1]);
  printf("Pos 2: %i\n",array_int[2]);
  printf("Pos 3: %i\n",array_int[3]);

  // Liberamos el arreglo
  free(array_int);
  return 0;
}

Output:
Código: [Seleccionar]
[root@localhost sf_Development]# ./array
Pos 0: 1
Pos 1: 2
Pos 2: 3
Pos 3: 4

Pro tip: sizeof es una función del lenguaje C que nos permite saber el tamaño en Bytes de un tipo de dato especifico.

Justo en este punto es donde las cosas se ponen interesantes: ¿Cómo es que declaré un puntero y lo accedo luego como un arreglo?

La respuesta es simple: los arreglos son en realidad "punteros disfrazados", la notación de los arreglos nos permite acceder a las direcciones de memoria del puntero sin tener que estar calculando las direcciones de memoria para cada uno de los elementos.

¿Como tendríamos que acceder a cada uno de los items si no existiera la notación del arreglo?

Pues deberíamos hacerlo de la siguiente manera:

Código: [Seleccionar]
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
  int *array_int = malloc(sizeof(int)*4);
  *(array_int) = 1;
  *(array_int+1) = 2;
  *(array_int+2) = 3;
  *(array_int+3) = 4;

  int *int_ptr = array_int; // Primera direccion en memoria
  printf("Pos 0: %i\n",*int_ptr);

  int_ptr = array_int + 1; // segunda direccion en memoria
  printf("Pos 1: %i\n",*int_ptr);

  int_ptr = array_int + 2; // tercera direccion en memoria
  printf("Pos 2: %i\n",*int_ptr);

  int_ptr = array_int + 3; // cuarta direccion en memoria
  printf("Pos 3: %i\n",*int_ptr);

  free(array_int);
  return 0;
}

Output:
Código: [Seleccionar]
[root@localhost sf_Development]# ./array
Pos 0: 1
Pos 1: 2
Pos 2: 3
Pos 3: 4

Nótese como utilizamos el "*" para acceder al contenido del puntero. Ojo con el uso de free, cuando declaramos las variables el compilador se encarga de agregar el código para liberar la memoria de las variables declaradas, sin embargo cuando utilizamos punteros y "malloc" DEBEMOS de utilizar siempre "free" ya que en este caso el compilador no generará el código para liberar la memoria. Muchos de los "memory leaks" son generados por algún programador descuidado que olvidó utilizar algún "free".

Las Estructuras

C es un lenguaje de "bajo nivel", esto significa que nos permite interactuar directamente con la memoria. Una de las características más interesantes y que precede al "concepto" de las "clases" en la POO son las famosas "estructuras".

Una estructura es un tipo especial de datos en C, que nos permite agrupar diferentes tipos de datos diferentes en un solo elemento.

Las estructuras se utilizan generalmente cuando queremos guardar datos asociados de diferente tipo. Un ejemplo práctico es cuando queremos definir una cordenada en el plano (x,y):

Código: [Seleccionar]
struct Coordenada {
  int x;
  int y;
}

Si quisieramos crear una coordenada podríamos hacerlo de la siguiente manera:


Código: [Seleccionar]
struct Coordenada primera;
primera.x = 4;
primera.y = 4;

O bien de una manera más abreviada:
Código: [Seleccionar]
struct Coordenada primera = {4,4};
Podemos crear estructuras de manera dinámica con malloc, en este caso el código sería similar al siguiente:

Código: [Seleccionar]
#include <stdlib.h>

struct Coordenada {
  int x;
  int y;
};

int main(int argc,char *argv[]) {

  struct Coordenada* primera = (struct Coordenada*)malloc(sizeof(struct Coordenada));

  primera->x = 4;
  primera->y = 4;

  free(primera);

  return 0;
}

Pueden observar como utilizamos "->" en vez de "." para acceder a los datos de la estructura en puntero.

Las Listas

Una lista es una estructura dinámica de datos que nos permite almacenar una cantidad indefinida de datos, cada uno de los elementos de la lista se une al siguiente como en una pequeña cadena.

Una forma más sencilla de entender las listas es imaginarlas como "cadenas", donde cada dato es un eslabón dentro de la misma.

Podemos clasificar las cadenas en base como estan anidados sus eslabones entre sí, la forma en que estén anidados los eslabones determinará como la lista puede ser recorrida.

Una lista con anidación sencilla es la que cada item (o eslabón) tiene un puntero al siguiente item:

[dato 1]->[dato 2]->[dato 3]->[dato 4]

Una lista doblemente anidada es la que cada item tiene un puntero hacia el item siguiente, pero también tiene un puntero al item anterior:

[dato 1]<->[dato 2]<->[dato 3]<->[dato 4]

Pueden observar como en una lista simplemente anidada solo podemos recorrer los datos en una sola dirección, en cambio en una lista doblemente anidada podemos recorrer la lista en cualquier dirección.

El eslabón de la cadena

Vamos a hacer uso de una estructura que va a representar el eslabón de nuestra cadena, para nuestro caso vamos a hacer una lista doblemente anidada ya que posiblemente luego querramos recorrer la lista en cualquier dirección.

Código: [Seleccionar]
struct Item {
  struct Item *prevPtr;
  int data;
  struct Item *nextPtr;
};

La Pila

Una pila es uno de las estructuras dinámicas más sencillas de realizar, en una pila el objetivo es ir agregando items al principio de la lista.

Este tipo de estructura es llamada usualmente una cola LIFO (de las siglas en ingles Last In, First Out en español último que entra, primero que sale).

Si fueran programadores encargados del desarrollo de Magic, utilizarían una cola LIFO para guardar su deck.

Usualmente a la función que agrega los items se le denomina "push" (de empujar).

La lógica de nuestra función push será la siguiente:

1-Vamos a revisar si se existe el primer eslabón
2-Si existe el primer eslabón lo creamos y definimos como NULL los punteros del eslabón.
3-Si ya existe el primer eslabón, entonces creamos un nuevo eslabón y asociamos los punteros.

En C y con la estructura de datos definida previamente, esto sería algo como lo siguiente:

Código: [Seleccionar]
struct Item* push(int data,struct Item* vector) {
  if(vector==NULL) { // Si no hay item definido
    vector = (struct Item*)malloc(sizeof(struct Item));
    vector->prevPtr = NULL;
    vector->data = data;
    vector->nextPtr = NULL;
  } else {
    // Creamos un nuevo eslabon al principio de la cadena
    vector->prevPtr = (struct Item*)malloc(sizeof(struct Item));
    // Establecemos el eslabon previo a NULL (no hay items antes)
    vector->prevPtr->prevPtr = NULL;
    // Asignamos el dato
    vector->prevPtr->data = data;
    // El puntero siguiente del nuevo eslabón es el eslabón actual
    vector->prevPtr->nextPtr = vector;
    // empujamos el principio de la lista hacia el nuevo item
    vector = vector->prevPtr;
  }
  return vector;
}

¿Cómo utilizamos esta nueva lista? La idea era hacerlo lo más simple posible, así que la función trabaja de la siguiente manera:

1-Si el argumento "vector" es NULL creará una nueva lista y nos devolvera el primer puntero de la misma.
2-Si el argumento "vector" es un puntero, esta función asumirá que este es el primer elemento de la pila, y agregará items antes de este.

OJO: Ustedes pueden pasar como argumento CUALQUIER item de la lista, obviamente si pasan un elemento intermedio está función no determinará si el eslabón está al inicio de la lista.

Ejercicio: Modifiquen la función PUSH para que al recibir cualquier puntero, se desplace automáticamente al inicio de la lista.


Agregar items a nuestra lista es relativamente fácil, en C sería algo como lo siguiente:

Código: [Seleccionar]
include <stdio.h>
#include <stdlib.h>

struct Item {
  struct Item *prevPtr;
  int data;
  struct Item *nextPtr;
};

struct Item* push(int data,struct Item* vector) {
  if(vector==NULL) {
    vector = (struct Item*)malloc(sizeof(struct Item));
    vector->prevPtr = NULL;
    vector->data = data;
    vector->nextPtr = NULL;
  } else {
    vector->prevPtr = (struct Item*)malloc(sizeof(struct Item));
    vector->prevPtr->prevPtr = NULL;
    vector->prevPtr->data = data;
    vector->prevPtr->nextPtr = vector;
    vector = vector->prevPtr;
  }
  return vector;
}

int main(int argc,char *argv[]) {
  printf("Hello World! ;)\n");

  struct Item* vector;

  vector = push(1,NULL); // Inicializa la pila
  vector = push(2,vector);
  vector = push(3,vector);
  vector = push(4,vector);
 
  return 0;
}

Hasta ahora todo parece ir de color de rosa, pero hay un pequeño problema ¿Como hacemos para sacar los datos de nuestra pila?

Usualmente utilizamos una función denominada "POP" o quitar, esta función simplemente extrae el primer eslabón de la cadena, devuelve el dato y elimina el eslabón.

Nuestra función pop sería similar a la siguiente:

Código: [Seleccionar]
struct Item* pop(int *data,struct Item* vector) {
   if(vector==NULL) {
     return NULL;
   } else {
     *data = vector->data;
     if(vector->nextPtr!=NULL) {
       vector->nextPtr->prevPtr = NULL;
     }
     struct Item* nextPtr = vector->nextPtr;
     free(vector);
     return nextPtr;
   }
}

Esta función trabaja de la siguiente manera:

1-Si el item enviado es NULL no se hace nada.
2-Si el item enviado no es NULL, extrae el dato y lo asigna al puntero "data".
3-Si existe el siguiente eslabón entonces elimina la referencia al eslabón actual.
4-Guarda la referencia al siguiente eslabón
5-Libera la memoria del eslabón actual
6-Devuelve la referencia al siguiente eslabón.

¿Cómo lo utilizamos?

Esta función devolverá NULL cuando el la lista ya no tenga más items por recorrer, por lo que un do-while nos será de mucha utilidad, el programa completo quedaría de la siguiente manera:

Código: [Seleccionar]
#include <stdio.h>
#include <stdlib.h>

struct Item {
  struct Item *prevPtr;
  int data;
  struct Item *nextPtr;
};

struct Item* push(int data,struct Item* vector) {
  if(vector==NULL) {
    vector = (struct Item*)malloc(sizeof(struct Item));
    vector->prevPtr = NULL;
    vector->data = data;
    vector->nextPtr = NULL;
  } else {
    vector->prevPtr = (struct Item*)malloc(sizeof(struct Item));
    vector->prevPtr->prevPtr = NULL;
    vector->prevPtr->data = data;
    vector->prevPtr->nextPtr = vector;
    vector = vector->prevPtr;
  }
  return vector;
}

struct Item* pop(int *data,struct Item* vector) {
   if(vector==NULL) {
     return NULL;
   } else {
     *data = vector->data;
     if(vector->nextPtr!=NULL) {
       vector->nextPtr->prevPtr = NULL;
     }
     struct Item* nextPtr = vector->nextPtr;
     free(vector);
     return nextPtr;
   }
}

int main(int argc,char *argv[]) {
  printf("Hello World!\n");

  struct Item* vector;

  vector = push(1,NULL); // Inicializa el vector
  vector = push(2,vector);
  vector = push(3,vector);
  vector = push(4,vector);

  int data;
  do {
    vector=pop(&data,vector);
    printf("Data %i\n",data);
  } while(vector!=NULL);
  return 0;
}
Output:

Código: [Seleccionar]
[root@localhost sf_Development]# gcc main.c -o main
[root@localhost sf_Development]# ./main
Hello World!
Data 4
Data 3
Data 2
Data 1


Noten que la salida del programa los items salen en orden inverso, es decir, "El primero que entra, es el último que sale".

Espero este pequeño tutorial les haya gustado, muchas veces nos enseñan todos estos conceptos por separado y es muy difícil entender su utilidad de manera individual, una vez agarramos todos estos pequeños componentes y los utilizamos es donde podemos comenzar a hacer cosas interesantes.
« Última Modificación: enero 08, 2012, 10:27:37 pm por mxgxw »


Desconectado dijonsv

  • Trade Count: (0)
  • Sv Member
  • ***
  • Thank You
  • -Given: 25
  • -Receive: 18
  • Mensajes: 185
  • Velocidad Pura
Re: Estructuras de Datos Dinámicas - La Pila
« Respuesta #1 : enero 08, 2012, 10:19:15 pm »
Excelente resumen.!   :thumbsup:
Follow members gave a thank to your post:

Desconectado salvadoresc

  • Global Moderator
  • Trade Count: (13)
  • The Communiter-
  • *
  • Thank You
  • -Given: 1461
  • -Receive: 779
  • Mensajes: 11644
  • Adobe Certified Expert en ACISEAPRENDE
    • Foro de Diseno - Pixeles al Desnudo
Re: Estructuras de Datos Dinámicas - La Pila
« Respuesta #2 : enero 08, 2012, 11:10:04 pm »
como era la frase para estos temas? lo que es no tener que hacer? tenes mucho tiempo libre? XD no me acuerdo...
Awaken my child, and embrace the glory that is your birthright. Know that I am the Overmind; the eternal will of the Swarm.

haycoctelesamor.com

Desconectado mxgxw

  • Global Moderator
  • Trade Count: (1)
  • The Communiter-
  • *
  • Thank You
  • -Given: 27
  • -Receive: 651
  • Mensajes: 5662
  • Starlet - 999cc
    • mxgxw
Re: Estructuras de Datos Dinámicas - La Pila
« Respuesta #3 : enero 08, 2012, 11:17:15 pm »
como era la frase para estos temas? lo que es no tener que hacer? tenes mucho tiempo libre? XD no me acuerdo...

Esque instalé linux en una maquina virtual de la laptop (que por cierto corre mas rapido que en desktop) así que me dije a mi mismo:

¡¡Mi mismo!! ¿Por qué no programas algo en C? falsda ldfkjah dlfkajfdas


Desconectado Midnight

  • Trade Count: (0)
  • Sv Member
  • ***
  • Thank You
  • -Given: 9
  • -Receive: 5
  • Mensajes: 151
Re: Estructuras de Datos Dinámicas - La Pila
« Respuesta #4 : enero 08, 2012, 11:48:47 pm »
Tenia años pero años de no ver y de no usar c para programar algo,  :yahoo: realmente me recordaste muchas cosas que ya las tenia mas q olvidadas gracias por el minitutorial  :thumbsup:
Mi plan es vivir eternamente. Hasta ahora lo estoy cumpliendo perfectamente.

Experiencia es el nombre que damos a nuestras equivocaciones.

Desconectado Shinryu

  • Trade Count: (2)
  • The Communiter-
  • *
  • Thank You
  • -Given: 344
  • -Receive: 220
  • Mensajes: 1614
Re: Estructuras de Datos Dinámicas - La Pila
« Respuesta #5 : enero 08, 2012, 11:55:26 pm »
Esque instalé linux en una maquina virtual de la laptop (que por cierto corre mas rapido que en desktop) así que me dije a mi mismo:

¡¡Mi mismo!! ¿Por qué no programas algo en C? falsda ldfkjah dlfkajfdas

jajajajaja con eso del mi mismo me recordaste a cierto catedratico de cierta universidad  :rofl:

por cierto buen aporte.

Desconectado antonio

  • Sv Vampire Team ®
  • Trade Count: (0)
  • The Communiter-
  • ***
  • Thank You
  • -Given: 0
  • -Receive: 0
  • Mensajes: 1567
Re:Estructuras de Datos Dinámicas - La Pila
« Respuesta #6 : mayo 21, 2012, 12:21:30 pm »
y como crear una linked list por medio de de un for o while? digamos unos 100 nodos de memoria de una sola vez, sin que te de error?
Porque cortarlas verdes , si maduras caen solas

Desconectado Non Servium

  • Trade Count: (0)
  • Sv Member
  • ***
  • Thank You
  • -Given: 6
  • -Receive: 39
  • Mensajes: 426
  • Ilix Punx :)
Re:Estructuras de Datos Dinámicas - La Pila
« Respuesta #7 : mayo 21, 2012, 02:02:57 pm »
Gran post mxgxw!! Está interesante!  :thumbsup:

Solo quee vi q por ratos hablabas de pila y por ratos de listas ^^ la diferencia q aprendi de es q la pila, como decis, es tipo LIFO y la lista es independiente a ello, de hecho para las listas, existen varios tipos... por orden: Ascendente y descendente, por tipo: lineales y circulares y por enlaces: unidireccionales o bidireccionales, la combinación de todos esos criterios te hacen varios tipos pero diferente que una pila, la cuál la única relación que podrían tener es: Una pila puede ser considerada una lista de orden ascendente al tiempo de inserción de los elementos, unidireccional y lineal.

Y según leí, la pila no necesitaría un puntero que apunte a la dirección anterior, solo es necesaria la siguiente, algo asi:

Código: [Seleccionar]
typedef struct nodo {
    int valor,
    nodo * siguiente
};

typedef nodo * Pila;
♫ Condenados a perder la libertad! Por no acatar las leyes que les asignaron. ♪ ♫
Decididos, decididos a emprender! Un camino largo y duro por no ser esclavos ♫


Watch

Desconectado Jaru

  • Trade Count: (21)
  • The Communiter-
  • *
  • Thank You
  • -Given: 782
  • -Receive: 1555
  • Mensajes: 13248
  • -text
Re:Estructuras de Datos Dinámicas - La Pila
« Respuesta #8 : mayo 21, 2012, 02:19:47 pm »
en microcontroldores por lo limitado de la memoria y registros, se usa bastante la pila para almacenar datos de forma temporal
N/A

Desconectado mxgxw

  • Global Moderator
  • Trade Count: (1)
  • The Communiter-
  • *
  • Thank You
  • -Given: 27
  • -Receive: 651
  • Mensajes: 5662
  • Starlet - 999cc
    • mxgxw
Re:Estructuras de Datos Dinámicas - La Pila
« Respuesta #9 : mayo 23, 2012, 07:12:11 am »
Gran post mxgxw!! Está interesante!  :thumbsup:

Solo quee vi q por ratos hablabas de pila y por ratos de listas ^^ la diferencia q aprendi de es q la pila, como decis, es tipo LIFO y la lista es independiente a ello, de hecho para las listas, existen varios tipos... por orden: Ascendente y descendente, por tipo: lineales y circulares y por enlaces: unidireccionales o bidireccionales, la combinación de todos esos criterios te hacen varios tipos pero diferente que una pila, la cuál la única relación que podrían tener es: Una pila puede ser considerada una lista de orden ascendente al tiempo de inserción de los elementos, unidireccional y lineal.

Y según leí, la pila no necesitaría un puntero que apunte a la dirección anterior, solo es necesaria la siguiente, algo asi:

Código: [Seleccionar]
typedef struct nodo {
    int valor,
    nodo * siguiente
};

typedef nodo * Pila;

Sí, lo que pasa es que quería utilizar una estructura general que puego pudiera ser utilizada para otros tipos de listas. Mucha gente piensa que las listas circulares, anidadas, unidireccionales, etc, etc. Son cosas diferentes, sin embargo en el fondo todas son listas anidadas, la diferencia es la forma en que se accede a los elementos. Incluso podrías hacer una especie de "estructura 2-dimensional" con 4 punteros que apunten Norte-Sur-Este-Oeste, o incluso podrías ir mas lejos y hacer una estructura que te represente un vértice en un espacio tridimencional con 6 punteros representando las aristas.

Este tipo de estruturas que representan espacios N-Dimensionales te podrían servir para aplicarse en el diseño de redes neuronales solo por dar un ejemplo o para la representación de gráfos en memoria, que a su vez tiene sus aplicaciones en el cálculo de rutas, por dar otro ejemplo.

Hay que recordar que al final de cuentas el espacio de memoria es "lineal" y unidimensional, así que en mi opinión personal los diferentes tipos de listas simplemente representan el tipo de abstracción que se quiere realizar sobre este espacio de memoria lineal. Es decir jejeje por mucho que le metas vértices (punteros) a tu arista la memoria a la que apunta cada puntero siempre se va a guardar en el espacio de memoria lineal :)


Solo que OJO, como dice naruto, las pilas de hardware generalmente son parte del diseño de un microcontrolador y generalmente utilizan otros mecanismos diferentes a las listas para acceder a sus elementos.

Ahora, respecto a la pregunta que hace el otro comuno... En teoría malloc te va a permitir asignar memoria en tanto el sistema operativo le indique que hay memoria disponible. Que tanta memoria podas obtener va a depender de muchísimas cosas, incluyendo la memoria disponible, la fragmentación de la memoria (que tan dispersos estan los bloques asignados) y obviamente la cantidad de memoria que necesites.

Para el ejemplo anterior si quisieras meter 100 elementos a la lista, un código como el siguiente te debería funcionar y no te debería generar errores:

Código: [Seleccionar]
struct Item* vector;

for(int i=0;i<100;i++) {
  vector = push(i,vector);
}

malloc devuelve Null si no puede asignar memoria, sería un buen ejercicio hacer un código que detecte cuando no se pueda asignar memoria y termine la ejecución del programa con agún error.
« Última Modificación: mayo 23, 2012, 07:18:37 am por mxgxw »


Desconectado Non Servium

  • Trade Count: (0)
  • Sv Member
  • ***
  • Thank You
  • -Given: 6
  • -Receive: 39
  • Mensajes: 426
  • Ilix Punx :)
Re:Estructuras de Datos Dinámicas - La Pila
« Respuesta #10 : mayo 23, 2012, 10:26:38 am »
Sí, lo que pasa es que quería utilizar una estructura general que puego pudiera ser utilizada para otros tipos de listas. Mucha gente piensa que las listas circulares, anidadas, unidireccionales, etc, etc. Son cosas diferentes, sin embargo en el fondo todas son listas anidadas, la diferencia es la forma en que se accede a los elementos. Incluso podrías hacer una especie de "estructura 2-dimensional" con 4 punteros que apunten Norte-Sur-Este-Oeste, o incluso podrías ir mas lejos y hacer una estructura que te represente un vértice en un espacio tridimencional con 6 punteros representando las aristas.

Este tipo de estruturas que representan espacios N-Dimensionales te podrían servir para aplicarse en el diseño de redes neuronales solo por dar un ejemplo o para la representación de gráfos en memoria, que a su vez tiene sus aplicaciones en el cálculo de rutas, por dar otro ejemplo.

Hay que recordar que al final de cuentas el espacio de memoria es "lineal" y unidimensional, así que en mi opinión personal los diferentes tipos de listas simplemente representan el tipo de abstracción que se quiere realizar sobre este espacio de memoria lineal. Es decir jejeje por mucho que le metas vértices (punteros) a tu arista la memoria a la que apunta cada puntero siempre se va a guardar en el espacio de memoria lineal :)

Si, buena explicación! Yo lo he entendido asi (no se si está bien) si dos pilas (sean p0 y p1) en este caso almacenando el mismo tipo (probemos "int") se crean y alimentan "paralelamente", los espacios de memoria son independientes, así por ejemplo:

Código: [Seleccionar]
push(p0, 3);
push(p1, 10);
push(p0, 6);
push(p0, 9);
push(p1, 20);
push(p0, 12);
push(p1, 30);
push(p1, 40);
reservarán diferente espacio de memoria (siempre lineal) a cada elemento... Al imprimir la dirección de memoria y su contenido, obtenemos:


Código: [Seleccionar]
printf("Direccion y Contenido de memoria para P0\n");
for (int i = 0; i < 4; i++)
{
    printf("Direccion:\t%d\tContenido:\t%d\n", p0+i, *(p0+i));
}
printf("\n\nEspacios y Contenido de memoria para P1\n");
for (int j = 0; j < 4; j++)
{
    printf("Direccion:\t%d\tContenido:\t%d\n", p1+j, *(p1+j));
}

Outputs:
Código: [Seleccionar]
Direccion y Contenido de memoria para P0
Direccion:    2538    Contenido:    3
Direccion:    2540    Contenido:    6
Direccion:    2542    Contenido:    9
Direccion:    2544    Contenido:    12

Direccion y Contenido de memoria para P1
Direccion:    6841    Contenido:    10
Direccion:    6843    Contenido:    20
Direccion:    6845    Contenido:    30
Direccion:    6847    Contenido:    40

Un post sobre árboles binarios me vendría de toque  ;) ya q esos son un poquito más complejos  :thumbsup:
♫ Condenados a perder la libertad! Por no acatar las leyes que les asignaron. ♪ ♫
Decididos, decididos a emprender! Un camino largo y duro por no ser esclavos ♫


Watch