Capítulo 1 Listas abiertas

1.1 Definición

La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo siguiente vale NULL.

En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista.

Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía.

El nodo típico para construir listas tiene esta forma:

struct nodo {
   int dato;
   struct nodo *siguiente;
};

En el ejemplo, cada elemento de la lista sólo contiene un dato de tipo entero, pero en la práctica no hay límite en cuanto a la complejidad de los datos a almacenar.

1.2 Declaraciones de tipos para manejar listas en C

Normalmente se definen varios tipos que facilitan el manejo de las listas, en C, la declaración de tipos puede tener una forma parecida a esta:

typedef struct _nodo {
   int dato;
   struct _nodo *siguiente;
} tipoNodo;
 
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;

tipoNodo es el tipo para declarar nodos, evidentemente.

pNodo es el tipo para declarar punteros a un nodo.

Lista es el tipo para declarar listas, como puede verse, un puntero a un nodo y una lista son la misma cosa. En realidad, cualquier puntero a un nodo es una lista, cuyo primer elemento es el nodo apuntado.

Lista enlazada
Lista enlazada

Es muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, ya que si no existe ninguna copia de ese valor, y se pierde, será imposible acceder al nodo y no podremos liberar el espacio de memoria que ocupa.

Comentarios de los usuarios (3)

Iván
2012-06-20 22:21:06

Bueno quiero hacer un aporte de listas circulares pero estático, es algo que yo hice espero que a más de alguien le sirva el Algoritmo (si alguien desea modificar estos programas es libre de modificarlos siempre y cuando al utilizarlo aporten su idea y funcione de una mejor manera)

y si tiene algunos fallos, *si le pongo un pop en medio de los push() pues tiende a descontrolarse un poco....*

Bueno espero a que se mejore y así se perfeccione

//////////////////////////////////////////////////

//Listas circulares Estáticas Cola

//////////////////////////////////////////////////

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int vector [4];

unsigned int s=0;

unsigned int m=0;

void iniciar ()

{

unsigned int i;

for (i=0; i<4; i++)

{

vector[i]=0;

}

s=0;

m=0;

}

void mostrar()

{

unsigned int j;

cout<<"=====Mostrando datos==========="<<endl;

for (j=0; j<4; j++)

{

cout<<"\t\t"<<vector[j]<<endl;

}

cout<<"==============================="<<endl;

}

void Push (int dato)

{

if ((m>3)&&(vector[0]!=0))

{

cout<<"lista llena"<<endl;

}

else

{

if (m>3)

{

m=0;

}

else

{

vector[m]=dato;

cout<<"\t#dato insertado ["<<vector[m]<<"]"<<endl;

m++;

}

}

}

void Pop ()

{

if ((s==m)&&(vector[0]==0))

{

cout<<"cola vacia \n";

iniciar();

}

else

{

if(vector[s]!=0)

{

cout<<"sacando datos["<<vector[s]<<"]"<<endl;

vector[s]=0;

s++;

}

else

{

cout<<"casilla vacia"<<endl;

}

}

}

int main()

{

iniciar();

Pop();

Push(7);

Push(9);

Push(4);

Push(6);

Push(3);

mostrar ();

Pop();

Pop();

Pop();

Pop();

Pop();

Pop();

iniciar ();

Push(9);

Push(10);

Push(11);

Push(12);

mostrar ();

Pop();

Pop();

Pop();

Pop();

Pop();

return 0;

}

///////////////////////////////////////////////////////

///////////////////////////////////////////////////

//////////////////////////////////////////////////////////

/////////////////////////////////////////////////////

//Listas circulares estáticas Pila

////////////////////////////////////////////////////

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

int vector[4];

unsigned int t=3;

unsigned int s=0;

void iniciar ()

{

unsigned int i;

for (i=0; i<4;i++)

{

vector[i]=0;

}

t=3;

s=0;

}

void Push(int dato)

{

if ((vector[0]!=0)&&(s>3))

{

cout<<"lista llena"<<endl;

}

else

{

vector[s]=dato;

cout<<"\t\tdato insertado ["<<vector[s]<<"]\n";

s++;

}

}

void Pop()

{

if((t!=s)&&(vector[0]==0))

{

cout<<"Lista vacia"<<endl;

iniciar ();

}

else

{

if (vector[t]==0)

{

cout<<"casilla vacia";

iniciar ();

}

cout<<"====================================="<<endl;

cout<<"sacando dato ["<<vector[t]<<"]"<<endl;

cout<<"====================================="<<endl;

vector[t]=0;

t--;

}

}

int main()

{

cout<<"|*==============================*|\n";

cout<<"|*=Listas circulares estáticas==*|\n";

cout<<"|*==============Pila============*|\n\n";

iniciar ();

Push(7);

Push(4);

Push(9);

Push(5);

Push(14);

Pop();

Pop();

Pop();

Pop();

Pop();

Pop();

Push(1);

Push(6);

Push(9);

Push(15);

//mostrar();

return 0;

}

Liz
2012-06-25 23:19:04

hola, alguien podria ayudarme con estructuras ligadas? es que tengo que resolver lo siguiente pero no tengo idea de como hacerlo! me urge.

1. Observar la figura y contestar las siguientes preguntas

http://www.infinitumpage.mx/GESLAVA/img/estrucLigada2.gif

(aqui esta el enlace para poder ver la imagen, gracias!)

a) (1 puntos) Escribir el código en lenguajes C que la represente.

b) (1 puntos) Apartir del inciso a), escribir el código en lenguajes C para insertar únicamente el 15

c) (1 puntos) Apartir del inciso a), escribir el código en lenguajes C para insertar únicamente la 'G'

d) (1 puntos) Escribir el código en lenguajes C para almacenar cada elementos que conforma a la estructura del inciso en un archivo de nombre dado por el usuario.

Alvaro J
2012-12-05 05:54:20

Saludos.

No me queda claro por qué se utiliza el caracter "\" en la declaración..

struct nodo \{

int dato;

struct nodo *siguiente;

};

¿cuál es su utilidad?

Muchas gracias.