Diseño de algoritmos“Listas Enlazadas”

Claudio Gutiérrez-Soto.

Ejemplovoid ajustar(registro *pt)

{

pt->nombre=“José”;

pt->no_cuenta=9999;

pt->tipo_cuenta=‘R’;

pt->saldo=99.99;

return;

}

#include<stdio.h>typedef struct{

char *nombre;

int no_cuenta;

char tipo_cuenta;

float saldo;

}registro;

void ajustar(registro *pt);

main(){

registro cliente={“Lázaro”,3333,’A’,33.33};

ajustar(&cliente);

}

Estructuras Autorreferenciadas

A veces es deseable incluir dentro de una estructura un miembro que sea un puntero a este tipo de estructura. En términos generales esto puede ser expresado como:

struct marca{

Miembro 1;

Miembro 2;

………

struct marca *nombre;

};

Estructuras Autorreferenciadas

La estructura no tiene un tamaño predefinido por lo que en general es más óptimo en cuanto a espacio. Además es simple de manipular por los punteros.

Estructuras Autorreferenciadas

La idea básica de una estructura de datos enlazada es que cada componente dentro de la estructura incluye un puntero indicando donde está el siguiente componente.

Estructuras Autorreferenciadas

También existen otras estructuras autorreferenciadas como los árboles. Los cuales pueden ser binarios (2 nodos) o n-arios.

Estructuras Autorreferenciadas

En el caso de una lista enlazada, la estructura principal puede ser vista como sigue:

struct Lista{ miembro 1; miembro 2; …. struct Lista *sgte; };

Estructuras Autorreferenciadas

Para el caso de una lista que almacena números enteros, su respectiva estructura sería:

struct Lista{ int dato; struct Lista *sgte; };

Estructuras Autorreferenciadas

Para el caso de un árbol binario que almacena números enteros, su respectiva estructura sería:

struct arbol{ int dato; struct arbol *izq; struct arbol *der; };

Estructuras Autorreferenciadas

Para el caso de un árbol N-ario que almacena números enteros, su respectiva estructura sería:

#define N 5

struct arbol{

int dato;

struct arbol *Hijos[N];

};

Estructuras Autorreferenciadas

Para todas estas estructuras, hay que definir las funciones de inserción, eliminación y otros.

Ejemplo de una Lista Enlazadainclude<stdio.h>#include<stdlib.h>#define NULL 0struct Lista{ int dato; struct Lista *sgte;};typedef struct Lista Lista;typedef Lista *Enlace;Enlace Head=NULL;Enlace insertar(Enlace nodo,int dato);void imprimir(Enlace nodo);main(){ int n,i,dato; printf("Ingrese cuantos elementos desea agregar\n"); scanf("%d",&n); for(i=0;i<n;i++) { printf("Ingresando el elemento %d\n",i+1); scanf("%d",&dato); Head=insertar(Head,dato); } imprimir(Head);}

Enlace insertar(Enlace nodo,int dato){

if(nodo==NULL)

{ nodo=(Enlace)malloc(sizeof(Lista));

nodo->dato=dato;

nodo->sgte=NULL;

}

else nodo->sgte=insertar(nodo->sgte,dato);

return(nodo);

}

void imprimir(Enlace nodo)

{

if(nodo!=NULL)

{ printf(" dato-> %d \n",nodo->dato);

imprimir(nodo->sgte);

}

else printf("Null");

}

¿Preguntas?