Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

TDA - Listas Enlazadas Y Listas Dobles - Lenguaje C

No description
by

Gabriel Chaldu

on 16 September 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of TDA - Listas Enlazadas Y Listas Dobles - Lenguaje C

Estruturas de Datos Dinámicas
Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de
alguna manera para representar un comportamiento.
TDA - Listas Simples y Dobles
Definición de Listas
(simplemente enlazada)

Una lista enlazada es una estructura lineal conformada por nodos.
Estáticas:

su tamaño en memoria es fijo.
Ejemplo: arrays.
Dinámicas:

su tamaño en memoria es variable
.
Ejemplo: listas enlazadas con punteros,
ficheros, etc.
Listas Enlazadas -
Nodos
Cada uno de los elementos de la lista se llama
NODO
.
typedef
struct
{

char

nombre[20];

int

edad;

struct

nodo * siguiente
;
}
nodo
;
nodo *
inicLista
()
{
return NULL;
}
nodo *
cargarLista
(nodo *
lista
)
{
nodo * nuevoNodo;
char cont = 's';
while (cont=='s')
{
nodo *
nuevoDato()
{
int edad;
char nombre[20];
nodo *
nuevoNodo;
nodo *
agregarPpio
(nodo * lista, nodo * nuevoNodo)
{
nodo *
crearNodo
(char nombre[20], int edad)
{
AGREGAR NODOS A LA LISTA ENLAZADA
void
recorrerYmostrar
(nodo * lista)
{
nodo * seg = lista;
while (seg != NULL)
{

escribir
(seg);
seg= seg->siguiente;
}
}
void
escribir
(nodo * aux)
{
printf("nombre: %s \n", aux->nombre);
printf("edad: %d \n\n", aux->edad);
}
MOSTRAR NODOS LISTAS
int main()
{









}
Tipo de Dato Abstracto (TDA)
Es un tipo de dato definido por el programador
que se puede manipular de un modo similar a los tipos de datos definidos por el sistema.
La Pila
Una pila (stack o pushdown en inglés)
es una lista de elementos
de la cual sólo se puede extraer el último elemento insertado. La posición en donde se encuentra dicho elemento se denomina tope de la pila. También se conoce a las pilas como listas LIFO (LAST IN - FIRST OUT: el último que entra es el primero que sale).
Implementar librerias en C
2. Crear un NUEVO PROYECTO
malloc()
Asignación dinámica de memoria C
se refiere a la realización de la asignación de memoria dinámica
en tiempo de ejecución
a través de diferentes funciones de C como
malloc , realloc , calloc y free
.
int array[10];
Asignación de Memoria ESTÁTICA
int * array;
array = malloc(10 * sizeof(int));
Asignación de Memoria DINÁMICA
malloc()
TDA - Pila
void
inicpila
(Pila *p)
{
typedef struct
{
int * valores;
int postope;
}Pila;
void apilar(Pila *p, int dato)
{
p->valores[p->postope]=dato;
p->postope = p->postope + 1;
}
Asigno Memoria Dinámica
Prof. Gabriel Chaldu
Prof. Gustavo Sonvico

BORRAR un NODO de la lista buscándolo por el valor de un campo
Función que elimina un nodo de la lista:
nodo *
agregarEnOrden
(nodo * lista, nodo * nuevoNodo)
{

if(lista ==
NULL
)
{
lista = nuevoNodo;
}
else
{
if(nuevoNodo->dato < lista->dato)
lista = agregarPpio(lista, nuevoNodo);
else

{
nodo * ante = lista;
nodo * aux = lista;
while(aux != NULL && nuevoNodo->dato > aux->dato)
{
ante = aux;
aux = aux->siguiente;
}
ante->siguiente = nuevoNodo;
nuevoNodo->siguiente = aux;
}
}

}
Definición de Listas
(doblemente enlazada)
Es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.
ESTRUCTURA de Listas
(
doblemente
enlazada)
typedef struct
{
int dato;
Nodo2 * ste;
Nodo2 * ante;
} Nodo2;
Nodo2 * IniciLista()
{
return NULL;
}
Nodo2 * crearNodo(int dato)
{
Nodo2 * aux = (Nodo2*) malloc (sizeof(Nodo2)); aux->dato = dato;
aux->ante
=
NULL
;
aux->ste
=
NULL
;
return aux;
}

AGREGAR NODO
de Listas
(
doblemente
enlazada)
Nodo2 * agregarAlPio(Nodo2 * lista, Nodo2 * nuevoNodo)
{
nuevoNodo->ste = lista;
if(lista != NULL)
//Ingresa cuando carga el segundo
{
lista->ante = nuevoNodo;
}
return nuevoNodo;
}
AGREGAR ultimo
de Listas
(
doblemente
enlazada)
Nodo2 *
agregarAlFinal
(Nodo2 * lista, Nodo2 * nuevoNodo)
{
Nodo2 * ultimo = NULL;
if (lista == NULL)
{
lista = nuevoNodo;
}else{
ultimo =
buscarUltimo
(lista);
ultimo->ste = nuevoNodo;
nuevoNodo->ante = ultimo;
}
return lista;
}

Nodo2 *
buscarUltimo
(Nodo2 * lista)
{
Nodo2 * rta;
if (lista == NULL)
rta = NULL;
else
if (lista->ste == NULL)
rta = lista;
else
rta =
buscarUltimo
(
lista->ste
);

return rta;
}

Acercamiento al corte
AGREGAR en ORDEN
en Listas Dobles enlazadas
Nodo2 * insertarNodo(Nodo2 * lista, Nodo2 * nuevoNodo)
{
if (lista == NULL)
lista = nuevoNodo;
else
if (nuevoNodo->dato < lista->dato)
lista = agregarAlPrincipio(lista, nuevoNodo);
else{
Nodo2 * seg = lista->ste;
//Busco desde el 2º Nodo
Nodo2 * ante = lista;
while ( seg!= NULL && nuevoNodo->dato > seg->dato)
{
ante = seg;
seg = seg->ste;
}
ante->ste = nuevoNodo;
nuevoNodo->ante = ante;
nuevoNodo->ste = seg;
if( seg!= NULL)
seg->ante = nuevoNodo;
}
return lista;
}
Primer NODO
Cuando el NODO nuevo es EL MENOR
Ingresa solo para el primer nodo, cuando la lista esta vacia
Ingresa cuando el dato a ingresar es el menor de la Lista y por eso agrega al principio
MODIFICA EL INICIO DE LA LISTA
ante guardar el Nodo anterior a donde debo Insertar.

Hago todos los enlaces de NUEVO-ANTE y SEG.
Por ultimo SI seg es nulo quiere decir que el ultimo NODO que agregue era el mas grande de todos. Si seg es != NULL lo tengo que enganchar con el nuevo
MODIFICA EL INICIO DE LA LISTA
NO MODIFICA EL INICIO DE LA LISTA
El TDA

tiene:
Una identidad
Un comportamiento
, con el cual permite la interacción (comunicación) con el mismo.
Es
independiente del lenguaje en el que se quiera implementar;
PASCAL, C, C + +, C#, JAVA, etc.
Implementar librerías en C
1- CREAR ARCHIVOS .h y .c
Implementar librerias en C
3. Añadir los archivos .h y .c
Nuevo Archivo
Archivo
.h
Archivo
.c
Ingreso el nombre y ruta del archivo
Debo seleccionar la ruta
donde deseo guardar el
archivo
Añadir archivo
seleccionar archivo
Carpeta del proyecto
Asi queda el proyecto
Archivos añadidos desde la vista
de la IDE
include del .h
include .h
Las funciones
Defino la estructura
Defino el prototipado
de las funciones
Puntero
(int *)
malloc(50*sizeof(int));
p->valores =
p->postope = 0;
}
Puntero para arreglo dinámico
Índice del arreglo
dinámico
Incremento el indice
Conversión de datos
No tiene limite de elementos para almacenar.
Solo podemos acceder a sus elementos por el inicio de la lista.
El acceso al

primer

NODO
de la lista
se hace a través

de
una variable (con nombre) de tipo
puntero
.
El final de la lista se determina con
NULL
.
Cada
NODO
de la lista contiene campos con
información.
El acceso a cada NODO
de la lista se hace en forma secuencial,
a través del campo que contiene la dirección del siguiente.

Cada
NODO
nos proporciona la
dirección del siguiente
.
Datos
Dirección de memoria del NODO siguiente
nuevoNodo
=
nuevoDato()
;
lista
=
agregarPpio
(
lista
,
nuevoNodo
);
printf(
"desea continuar s/n: ");
fflush(stdin);

scanf("%c", &cont);
printf("\n");
}
return lista;
}
Variable de control
printf
("ingrese edad:");
fflush(stdin);

scanf("%d", &edad);
nuevoNodo
=
crearNodo
(
nombre
,
edad
);
return
nuevoNodo
;
}
Datos
Nodo de retorno
printf
("ingrese nombre: ");
fflush(stdin);
scanf("%s", &nombre);
nodo * aux =
(nodo*)
malloc
(sizeof(nodo));
aux->edad = edad;
strcpy(aux->nombre, nombre);
return
aux
;
}
Reservo memoria para el NODO
Asigno los parámetros
Retorno el NODO
if(lista == NULL)
{


}
else
{




}




}
Si esta vacia
Primer Nodo
lista = nuevoNodo;
nuevoNodo->siguiente = lista;
return lista;
Si NO esta Vacia
nuevoNodo es el nuevo inicio de la lista
Retorno el NUEVO INICIO DE LA LISTA
Retorno el puntero al inicio de la lista que es el ultimo nodo que cargue
Función
que inicializa
la lista
nodo* lista;
lista =
inicLista
();
lista =
cargarLista
(lista);
recorrerYmostrar
(lista);
DECLARO LA LISTA
INICIALIZO LA LISTA
Creo la lista y devuelvo el inicio
Muestro la lista
Busca el nodo por un valor de uno de sus campos.
Retorna un puntero al comienzo de la lista.
Enlaza el puntero anterior con el siguiente al eliminado
nodo *
borrarNodo
(char nombre[20], nodo * lista)
{
nodo * aux;
nodo * ante;
if( && )
{



}
else
{












}

}
Ej 1 Elimino el primer Nodo
nodo * aux = lista;
aux = lista;
while((aux != NULL) && (strcmp(nombre, aux->nombre)!=0 ))
{


}
ante = aux;
//adelanto una posición la variable ante.
aux = aux->siguiente;
//avanzo al siguiente nodo.
ante->siguiente = aux->siguiente;
free(aux);

//elimino el nodo
.
if(aux!=NULL)
{


}
lista = lista->siguiente;
free(aux);
(lista != NULL)
(strcmp(nombre, lista->nombre)==0 )
return lista;
Hay lista?
El nombre buscado es el primer nodo?
nodo *
borrarNodo
(char nombre[20], nodo * lista)
{
nodo * aux;
nodo * ante;
if( && )
{



}
else
{












}

}
Ej 2 Elimino
Otro Nodo
que no sea el Primero
nodo * aux = lista;
aux = lista;
while((aux != NULL) && (strcmp(nombre, aux->nombre)!=0 ))
{


}
ante = aux;
ante->siguiente = aux->siguiente;
if(aux!=NULL)
{


}
lista = lista->siguiente;
free(aux);
(lista != NULL)
(strcmp(nombre, lista->nombre)==0 )
return lista;
El nombre buscado es distinto del nodo?
//Asigno el inicio a la variable Auxiliar
//salteo el primer nodo a Eliminar
//elimino el primer nodo.
Nuevo Inicio
LLegue el Final?
retorno el NUEVO INICIO
aux = aux->siguiente;

Busco eliminar el NODO
"B"
ante = al nodo
ACTUAL
aux = al siguiente NODO
1º Iteración
En la 2º iteración AUX->nombre = "B" y salgo del Bucle.
OK
free(aux);
//elimino el nodo.
ante->sig
=
aux->sig
ante
aux
Retorno la puntero al inicio de la LISTA
nodo *
agregarEnOrden
(nodo * lista, nodo * nuevoNodo)
{

if(lista ==
NULL
)
{
lista = nuevoNodo;
}
else
{
if(nuevoNodo->dato < lista->dato)
lista = agregarPpio(lista, nuevoNodo);
else

{
nodo * ante = lista;
nodo * aux = lista;
while(aux != NULL && nuevoNodo->dato > aux->dato)
{
ante = aux;
aux = aux->siguiente;
}
ante->siguiente = nuevoNodo;
nuevoNodo->siguiente = aux;
}
}

return lista;
}
Ingresa solo para el primer nodo, cuando la lista esta vacia
Ingresa cuando el dato a ingresar es el menor de la Lista y por eso agrega al principio
MODIFICA EL INICIO DE LA LISTA
ante
guardar la dirección de memoria del
nodo anterior donde se debe insertar.
El siguiente al ante se enlaza con el aux siguiente.
NO SE MODIFICA EL INICIO DE LA LISTA
return lista;
aux->siguiente = NULL;
Direcc. de Memoria sig = Null
lista = nuevoNodo;
Engancho nuevo con la lista
Las listas doblemente enlazadas no necesitan
EL PUNTERO AL INICIO DE LA LISTA
, pueden recorrerse en ambos sentidos a partir de cualquier nodo.
Full transcript