estructuras autoreferenciadasestructuras autoreferenciadas •una estructura no puede referenciarse...

Estructuras autoreferenciadas


• Estructuras que contienen campos que son punteros a la misma estructura

• Aquí el miembro sgt apunta a una estructura de tipo Nodo, de allí el nombre de este tipo de estructura typedef struct Nodo

{

int Dato;

struct Nodo *sgt;

}TNodo;


• El campo Dato puede contener información representada como un tipo de dato primitivo o representada con un arreglo o, más comúnmente una estructura

typedef struct Automovil{ char patente[8];// 3 letras 3 nros y un guion char vin[18];/* 17 digitos y letras para nro.grabado en el motor*/ char* marca; char* modelo; int potencia; // en alguna unidad, por ej. HP DIN char* color; }Auto; typedef struct Nodo{ Auto *a; struct Nodo* next;/*puntero al siguiente nodo que contiene un auto*/ } nodo


• Una estructura no puede referenciarse a si misma es decir, tener una estructura del mismo tipo como miembro, puesto que esto daría lugar a una recursión infinita

• Pero si puede tener un campo que sea un puntero a la misma estructura (dirección de una variable del tipo de la estructura que contiene este campo)

Estructuras autoreferenciadas • El campo sgt se conoce como enlace o

vínculo, ya que sirve para vincular una estructura de tipo struct Nodo con otra estructura del mismo tipo

• Las estructuras autoreferenciadas pueden ser enlazadas juntas para formar estructuras de datos útiles y flexibles tales como son las listas, colas, pilas, árboles, tablas, grafos, diccionarios, entre otras


• Estas estructuras de datos almacenan un conjunto de objetos del mismo tipo, relacionados entre sí mediante punteros contenidos en ellos mismos, de forma que,

• basta conocer la raíz de un árbol o el principio de una lista (normalmente terminadas en un puntero NULL, usado como centinela), para poder acceder a todo el conjunto

Listas enlazadas

• Colección lineal de nodos autoreferenciados • Conectados por punteros enlazados • Acceso mediante un puntero al nodo inicial de la

lista • Los nodos siguientes se acceden mediante el

campo de puntero de enlace del nodo en curso (acceso secuencial, aunque los datos almacenados en la misma, no se encuentran en espacios consecutivos de memoria)

• El puntero de enlace del último nodo se asigna a NULL para indicar final de la lista

Listas enlazadas

• Eliminar o (insertar) un elemento que está al medio en una lista enlazada es muy simple y eficiente, consiste simplemente en reasignar los punteros del siguiente y del anterior elemento de los elementos que están entre el elemento a ser eliminado.

• No hay necesidad de grandes cantidades de memoria contigua, ni de definir un tamaño inicial

• Eliminar un elemento que está al medio en un array es costoso pues consiste en remover el elemento y desplazar todos los elementos siguientes a él, un lugar hacia atrás.

• Necesita información extra (el enlace o vínculo) con respecto a un array de estructuras

Listas enlazadas

Listas enlazadas

• El nodo autoreferenciado es el componente clave de una lista enlazada

• El nodo es una estructura de datos compuesta por:

• Dato: Representa al dato de interés

• sgt: Puntero al siguiente nodo

Operaciones más comunes

• Crear la lista • Insertar un elemento en la lista en determinada

posición • Eliminar un elemento de la lista o toda la lista • Buscar y recuperar un elemento en la lista • Recorrer la lista e imprimirla • Ordenar la lista según algún criterio • Insertar un elemento en forma ordenada • Preguntar si la lista está vacía • Obtener la cantidad de elementos de la lista, etc.

Lista simplemente enlazada

• Es la más básica y puede definirse como la secuencia de 0 (lista vacía) o más elementos de un determinado tipo.

• Los elementos quedan ordenados linealmente por su posición en la secuencia.

• Se requiere sólo un enlace entre un elemento y su sucesor • Los elementos de un arreglo ocupan posiciones contiguas o

adyacentes en la memoria. • En las listas debe asumirse que el espacio de un nodo no es

contiguo con otro; por esta razón, no basta incrementar en uno el puntero a un nodo, para obtener la dirección de inicio del nodo siguiente

Nodo

• El nodo es el componente clave de una lista enlazada (LE)

• Suponiendo que nuestros datos almacenados en la LE son enteros, crearemos el tipo de dato Tnodo mediante la siguiente estructura typedef struct Nodo

{

int dato;

struct Nodo *sgt;

}TNodo;

Operaciones sobre LE

• Para implementar operaciones sobre la LE debemos estructurar adecuadamente la misma. Una lista enlazada solamente necesita conocer la referencia del primer nodo, por lo que su estructura puede definirse simplemente como sigue: typedef struct LE

{

TNodo *inicio;

}TLE;

Recordar de punteros…

• En C el paso de argumentos es siempre por valor, aún cuando se pasa como argumento un puntero, por lo cual es posible modificar el valor de la variable a la que apunta un puntero

• Si se desea modificar el puntero original y no su copia, debe pasarse como puntero a puntero. En el siguiente ejemplo se pasa a la función allocateArray un argumento que es un puntero a un array de enteros (en este ejemplo un puntero inicialmente con valor NULL); la función asigna memoria dinámicamente para dicho array y lo inicializa. A través de este argumento la función retornará la dirección de comienzo de la memoria asignada dinámicamente e inicializada

Recordar de punteros… #include <stdio.h>

#include <stdlib.h>//necesaria para malloc

void allocateArray(int **arr, int size, int value) {

int i;

*arr = (int*)malloc(size * sizeof(int));

if(*arr != NULL) {

for(i=0; i<size; i++) {

*(*arr+i) = value;

}}}

void main(){

int *vector = NULL;

int i;

allocateArray(&vector,5,45);

//paso la dirección de un puntero a entero

//puesto que el argumento es un puntero a puntero a entero

for(i=0; i<5; i++) {

printf("%d\n", vector[i]);//ya no es NULL }

free(vector);}


• en donde TLE es nuestro tipo de datos creado que representa un lista enlazada.

• Para facilitar la implementación de las operaciones creamos dos funciones,

• una para crear un nuevo nodo y,

• la otra para crear una lista enlazada, estas funciones se definen a continuación:


TNodo *crearNodo(int x) { TNodo *nodo=(TNodo*)malloc(sizeof(TNodo)); nodo->dato=x; nodo->sgt=NULL; return nodo; } TLE *crearLista() { TLE *lista=(TLE*)malloc(sizeof(TLE)); lista->inicio=NULL; return lista; }

Insertar un nuevo elemento

• Por defecto los nuevos elementos se insertarán al final. Así, la operación de inserción simplemente sigue los siguientes pasos:

• Crear nuevo nodo

• Si la lista está vacía, el nuevo nodo es el primero

• En otro caso, ir hasta el final de lista avanzando de nodo en nodo, y hacer que el puntero sgt del último nodo apunte al nodo nuevo.

• Para avanzar de nodo en nodo se utiliza un puntero auxiliar que empieza con el nodo inicial de la lista y avanza mediante el puntero sgt de cada nodo.


void insertar(TLE *lista, int x)

{//al crear un nodo sgt es NULL

TNodo *nodo=crearNodo(x);

TNodo *p=NULL;//auxiliar

if(lista->inicio==NULL) {//lista vacia

lista->inicio=nodo;}

else{

p=lista->inicio;

while(p->sgt!=NULL){

p=p->sgt;}

p->sgt=nodo;}

}

Imprimir elementos de LE

• En este caso los pasos son:

• Obtener el primer nodo de la lista.

• Se utiliza un puntero p (auxiliar) a un nodo que empieza en el primer nodo

• Mientras no se llegue al final de la lista (p diferente de NULL)

– Mostrar el dato de p

– Avanzar p (p = p-> sgt)


void reportar(TLE lista)

{//no se modifica la lista

TNodo *p=NULL;//auxiliar

p=lista.inicio;

while(p!=NULL){

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

p=p->sgt;

}

}


• Usando un argumento puntero void reportar(TLE* lista) { TNodo *p=NULL;//auxiliar p=lista->inicio; while(p!=NULL){ printf("%d \n",p->dato); p=p->sgt; } }

Aplicando operaciones

int main()

{

TLE *l=crearLista();

insertar(l,1);

insertar(l,2);

insertar(l,3);

reportar(*l);

return 0;

}

Eliminar elemento de LE

• Supongamos que lo que queremos hacer es eliminar el nodo de la lista que contiene un cierto dato.

• La idea simplemente es encontrar el nodo correspondiente q – Esto también sirve para modificar algún campo del

nodo, por ejemplo • y, hacer que el nodo anterior a q apunte al siguiente de q.

• Con esto la lista deja de tener acceso a q. • Finalmente, liberamos el espacio que ocupaba q

usando la función free.

Eliminar elemento de LE

Eliminar elemento de LE void eliminar(TLE *lista, int dato){

TNodo *p=lista->inicio;//auxiliar, apunta al principio de la LE

TNodo *ant=NULL;//auxiliar

int encontrado=0;

while((p!=NULL)&&(!encontrado)){

if(p->dato==dato){

encontrado=1;}

else{

ant=p;

p=p->sgt; } //muevo p

}//recorrió toda la lista, si lo encuentra p no es NULL

if(p!=NULL){//si lo encontró

if (ant==NULL){//si quiero eliminar el primero

lista->inicio=(lista->inicio)->sgt;}

else{//no es el primero

ant->sgt=p->sgt;}

free(p);

}//fin if

}

Aplicando operaciones

int main() { TLE *l=crearLista(); insertar(l,5); insertar(l,1); insertar(l,3); insertar(l,4); reportar(*l); eliminar(l,3); reportar(*l); return 0; }

Ordenar en forma ascendente void ordenar(TLE* lista){//burbuja

TNodo *siguiente=NULL;//auxiliar

int temp;

TNodo *actual=lista->inicio;//auxiliar

if(actual!=NULL){//si lista no es vacia

while(actual->sgt != NULL){//no es el último

siguiente=actual->sgt;

while(siguiente!=NULL){//si los siguientes de actual no tienen sgt=NULL

if(actual->dato > siguiente->dato){//intercambio

temp=siguiente->dato;

siguiente->dato=actual->dato;

actual->dato=temp;

}

siguiente=siguiente->sgt;

}

actual=actual->sgt;//actualizo actual y su siguiente

siguiente=actual->sgt;

}

}//fin if lista no vacia

}

Listas enlazadas

• Constituyen la base para implementar otras estructuras dinámicas tales como colas, pilas, árboles, etc.

estructuras autoreferenciadasestructuras autoreferenciadas •una estructura no puede referenciarse...

Documents