PILAS:
Las pilas son otro tipo de estructura de datos lineales, las
cuales presentan restricciones en cuanto a la posición en la cual pueden
realizarse las inserciones y las extracciones de elementos.
Una pila es una lista de elementos en la que se pueden insertar y
eliminar elementos sólo por uno de los extremos. Como consecuencia, los
elementos de una pila serán eliminados en orden inverso al que se insertaron.
Es decir, el último elemento que se metió a la pila será el primero en salir de
ella.
En la vida cotidiana existen muchos ejemplos de pilas, una pila de
platos en una alacena, una pila de latas en un supermercado, una pila de
papeles sobre un escritorio, etc.
Una pila es un tipo especial de lista abierta en la que sólo se
pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas
operaciones se conocen como "push" y "pop", respectivamente
"empujar" y "tirar". Además, las escrituras de datos
siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo
leído.
Estas características implican un comportamiento de lista LIFO
(Last In First Out), el último en entrar es el primero en salir.
El símil del que deriva el nombre de la estructura es una pila de
platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo
pueden tomarse del mismo extremo.
Representaciones
Representación Gráfica ( Graphic Representation )
top
.
. DATA LINK
. +-------------+ <------ add
...........>| | * |
+----------|--+ ------> delete
V
+-------------+
| | * |
+----------|--+
V
+-------------+ +---+
| | * | P | | Variable con el tope de la pila
+----------|--+ +---+
V
.
.
.
.
|
V
+-------------+
| | 0 |
+-------------+
Observar que las
operaciones de agregar o eliminar un elemento a la pila, siempre se hacen sobre
el nodo que está al tope y es referenciado por la variable que representa la
pila.
EJEMPLOS:
C:
- #include <stdio.h>
- #include <conio.h>
- #include <stdlib.h>
- #include <string.h>
-
- struct agenda
- {
- char nombre[50];
- char telefono[25];
- char mail[50];
- };
-
- struct nodo
- {
- struct agenda dato;
- struct nodo *proximo;
- };
-
- struct nodo *nuevonodo();
- int colavacia(struct nodo *);
- struct nodo *creacola(struct nodo
*, struct agenda);
- void mostrar(struct nodo *);
-
- void main()
- {
- struct nodo *pri=NULL,
*ult=NULL;
- struct agenda x;
- printf("Ingrese nombre: ");
- gets(x.nombre);
- while(strcmpi(x.nombre,"fin"))
- {
- printf("Ingrese telefono: ");
- gets(x.telefono);
- printf("Ingrese mail: ");
- gets(x.mail);
- ult=creacola(ult,x);
- if(pri==NULL) pri=ult; //
Si es la 1º pasada pongo en pri el valor del primer nodo
- printf("Ingrese nombre: ");
- gets(x.nombre);
- }
- if(colavacia(pri)==1) { printf("No se ingresaron registros"); getch(); }
- else mostrar(pri);
- }
-
- struct nodo *nuevonodo()
- {
- struct nodo *p;
- p=(struct nodo
*)malloc(sizeof(struct nodo));
- if(p==NULL)
- {
- printf("Memoria RAM Llena");
- getch();
- exit(0);
- }
- return p;
- }
-
- struct nodo *creacola(struct nodo
*ult, struct agenda x)
- {
- struct nodo *p;
- p=nuevonodo();
- (*p).dato=x;
- (*p).proximo=NULL;
- if(ult!=NULL) (*ult).proximo=p; // Si hay
nodo anterior en prox pongo la direccion del nodo actual
- return p;
- }
-
- int colavacia(struct nodo *pri)
- {
- if(pri==NULL) return 1;
- else return 0;
- }
-
- void mostrar(struct nodo *pri)
- {
- struct nodo *aux;
- while(pri!=NULL)
- {
- printf("Nombre: %s - Telefono: %s - Mail:
%s \n",pri->dato.nombre,pri->dato.telefono,pri->dato.mail);
- aux=pri;
- pri=(*pri).proximo;
- free(aux);
- }
- getch();
- }
Colas:
Una cola es una colección de elementos homogéneos
(almacenados en dicha estructura), en la misma se pueden insertar elementos por
uno de los extremos, llamado frente, y retirar los mismos por el otro
extremo, denominado final.
Es importante aclarar que, tanto el frente como el final de la
cola, son los únicos indicados para retirar e insertar elementos,
respectivamente. Esto nos indica que no podemos acceder directamente a
cualquier elemento de la cola, sino solo al primero, o sea el que está o se
encuentra en el frente, y no se pueden insertar elementos en cualquier posición
sino solo por el final, así el elemento insertado queda como último.
Por esta razón la cola es denominada una estructura F.I.F.O.,
o simplemente una lista F.I.F.O., esto representa el acrónimo de las
palabras inglesas “first in, first out” (primero en entrar, primero en salir).
Gráficamente podemos representarla como: La cola fue recién creada y esta
vacía. (Frente y final apuntan FINAL FRENTE a nil).
Las colas se utilizan en sistemas informáticos, transportes y
operaciones de investigación (entre
otros), dónde los objetos, personas o eventos son tomados como datos que se
almacenan y se guardan mediante colas para su posterior procesamiento. Este
tipo de estructura de datos abstracta se implementa en lenguajes
orientados a objetos mediante clases, en forma de listas enlazadas.
Usos concretos de la cola
La particularidad de una estructura de datos de cola es el hecho de que
sólo podemos acceder al primer y al último elemento de la estructura. Así
mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden
añadir por el final de la cola.
Operaciones Básicas
- Crear: se
crea la cola vacía.
- Encolar
(añadir, entrar, insertar): se añade un elemento a la cola. Se añade al
final de esta.
- Desencolar
(sacar, salir, eliminar): se elimina el elemento frontal de la cola, es
decir, el primer elemento que entró.
- Frente
(consultar, front): se devuelve el elemento frontal de la cola, es decir,
el primer elemento que entró.
EJEMPLO:
C:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
struct agenda
{
char nombre[50];
char telefono[25];
char mail[50];
};
struct nodo
{
struct agenda
dato;
struct nodo
*proximo;
};
struct nodo *nuevonodo();
int colavacia(struct nodo *);
struct nodo
*creacola(struct nodo *, struct agenda);
void mostrar(struct nodo *);
void main()
{
struct nodo
*pri=NULL, *ult=NULL;
struct agenda
x;
gets(x.nombre);
while(strcmpi(x.nombre,"fin"))
{
gets(x.telefono);
gets(x.mail);
ult=creacola(ult,x);
if(pri==NULL) pri=ult; // Si es la 1º pasada pongo en pri
el valor del primer nodo
gets(x.nombre);
}
else mostrar(pri);
}
struct nodo *nuevonodo()
{
struct nodo *p;
p=(struct nodo
*)malloc(sizeof(struct nodo));
if(p==NULL)
{
getch();
exit(0);
}
return p;
}
struct nodo
*creacola(struct nodo *ult, struct agenda x)
{
struct nodo *p;
p=nuevonodo();
(*p).dato=x;
(*p).proximo=NULL;
if(ult!=NULL) (*ult).proximo=p; // Si
hay nodo anterior en prox pongo la direccion del nodo actual
return p;
}
int colavacia(struct nodo *pri)
{
if(pri==NULL) return 1;
else return 0;
}
void mostrar(struct nodo
*pri)
{
struct nodo *aux;
while(pri!=NULL)
{
printf("Nombre:
%s - Telefono: %s - Mail: %s \n",pri->dato.nombre,pri->dato.telefono,pri->dato.mail);
aux=pri;
pri=(*pri).proximo;
free(aux);
}
getch();
}
LISTA
Una lista enlazada es una de las estructuras
de datos fundamentales, y puede ser usada para implementar otras
estructuras de datos. Consiste en una secuencia de nodos,
en los que se guardan campos de
datos arbitrarios y una o dos referencias,
enlaces o punteros (punteros)
al nodo anterior o posterior. El principal beneficio de las listas enlazadas
respecto a los vectores convencionales
es que el orden de los elementos enlazados puede ser diferente al orden de
almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido
de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de
dato autoreferenciado porque contienen un puntero o enlace (en
inglés link, del mismo significado) a otro dato del mismo tipo. Las listas
enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la
lista en tiempo constante (suponiendo que dicho punto está previamente
identificado o localizado), pero no permiten un acceso aleatorio.
Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas
Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente
Circulares.
Las listas enlazadas pueden ser
implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos
ya construidas, junto con operaciones para acceder a las listas enlazadas.
Lenguajes imperativos u orientados a
objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas
enlazadas.
Una lista es una estructura de datos secuencial.
Lista densa: la propia estructura determina cuál es el siguiente elemento
de la lista. Ejemplo: un array.
Lista enlazada: la posición del siguiente elemento de la estructura la
determina el elemento actual.
Una lista es una secuencia de elementos llamados nodos. Cada nodo esta
formado por un campo de datos y 1 o más campos de enlace que apunta(n) al
siguiente nodo. Todo nodo tiene un predecesor y antecesor excepto el primero y
el último.
La lectura de una lista se realiza secuencialmente pero su posición física
en memoria solo depende del método para implementarla. Si por ejemplo usamos
punteros –que es la técnica más adecuada– podemos almacenar los componentes de
la lista en posiciones dispersas de memoria, aunque ante el usuario continuara
apareciendo como una estructura secuencial.
Se llaman operaciones simples las que afectan a un solo dato y complejas
las que afectan a varios. Las operaciones complejas pueden realizarse
repitiendo las simples.
Es necesario almacenar al menos la posición de memoria del primer elemento.
Además es dinámica, es decir, su tamaño cambia durante la ejecución del
programa. Una lista enlazada se puede definir recursivamente de la siguiente
manera:
a) una lista enlazada es una estructura vacía o
b) un elemento de información y un enlace hacia una
lista (un nodo).
c) Gráficamente se suele representar así:
Una lista puede cambiar de tamaño, pero su ventaja fundamental es que son
flexibles a la hora de reorganizar sus elementos; a cambio se ha de pagar una
mayor lentitud a la hora de acceder a cualquier elemento.
Implementación con variables
Referencias
Se debe definir una clase que
implemente la lista.
Ejemplo: en código…
public class nodo {
private Object elemento;
private nodo siguiente;
public nodo() {
this(null,null);
}
public
nodo(Object e, nodo n){
elemento=e;
siguiente=n;
}
Object
getElemento(){
return elemento;
} nodo getSiguiente(){
return siguiente;
}
void
setElemento(Object nuevoelemento){
elemento=nuevoelemento;
}
void setSiguiente(nodo nuevosiguiente){
siguiente=nuevosiguiente;
}
}
Un programa que acceda a la lista.
public class agrega {
public static void main(String [] args){
nodo
p,q;
p
= new nodo("uno",null);
q
= new nodo();
q.setElemento("dos");
q.setSiguiente(p);
p
= q;
q
= new nodo();
q.setElemento("tres");
q.setSiguiente(p);
p
= q;
while (q!=null){
System.out.println(q.getElemento());
System.out.println(q.toString());
q=q.getSiguiente(); }
} }
ARBOLES:
los arboles representan las
estructuras no lineales y dinámicas de datos mas importantes en computación las
estructuras de datos se dividen en estáticas y dinámicas:
ESTATICAS
-Arreglos
-Registros
-Conjuntos
DINAMICAS
-Listas
-Arboles
Un árbol es una estructura jerárquica aplicada a una construcción de elementos llamados nodos y uno de los cuales es conocido como raíz, además se crea una relación o parentesco entre nodos, dando lugar a términos como padre, hijos, hermanos, antecesor, sucesor, ancestro, etc...
Existen 4 formas de representar un árbol
-Grafo
-Diagrama de venn
-Anidacion de paréntesis
-Notación identada
ESTATICAS
-Arreglos
-Registros
-Conjuntos
DINAMICAS
-Listas
-Arboles
Un árbol es una estructura jerárquica aplicada a una construcción de elementos llamados nodos y uno de los cuales es conocido como raíz, además se crea una relación o parentesco entre nodos, dando lugar a términos como padre, hijos, hermanos, antecesor, sucesor, ancestro, etc...
Existen 4 formas de representar un árbol
-Grafo
-Diagrama de venn
-Anidacion de paréntesis
-Notación identada
Arboles y
Características
Los árboles son estructuras de datos no lineales.
Cada elemento conocido con el nombre de NODO
Un árbol se define como una colección de nodos donde cada uno además de
almacenar información, guarda las direcciones de sus sucesores.
Se conoce la dirección de uno de los nodos, llamado raíz y a
partir de el se tiene acceso a todos los otros miembros de la estructura.
Grafos, anidación de paréntesis y diagramas de venn.
Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre,
son aquellos que se encuentran en el mismo nivel
Padre: Es aquel que tiene hijos y también puede tener o no
antecesores.
Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es
decir si tienen el mismo padre.
Raíz: Es el nodo principal de un árbol y no tiene
antecesores.
Hoja o terminal: Son aquellos nodos que no tienen hijos o también los
nodos finales de un árbol.
Interior: Se dice que un nodo es interior si no es raíz ni hoja.
Nivel de un nodo: Se dice que el nivel de un nodo es el numero de arcos
que deben ser recorridos, partiendo de la raíz para llegar hasta el.
Altura del árbol: Se dice que la altura de un árbol es el máximo de los
niveles considerando todos sus nodos.
Grado de un nodo: se dice que el
grado de un nodo es el número de hijos que tiene dicho nodo.
GRAFOS:
Un grafo en el ámbito de
las ciencias de la computación es
una estructura
de datos, en concreto un tipo
abstracto de datos (TAD), que consiste en un conjunto de nodos (también
llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre
los nodos. El concepto de grafo TAD
desciende directamente del concepto matemático de grafo.
Informalmente se define como G =
(V, E), siendo los elementos de V los vértices, y los elementos de E, las
aristas (edges en inglés). Formalmente, un grafo,
G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y
E es un conjunto que
consta de dos elementos de V.
Formas de representación
Existen diferentes implementaciones
del tipo grafo: con una matriz
de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no
acotadas).
§ Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo
del grafo, siendo los elementos de la matriz la relación entre los mismos,
tomando los valores de 1 si existe la arista y 0 en caso contrario.
§ Lista de
adyacencias: se asocia a
cada nodo del grafo una lista que contenga todos aquellos nodos que sean
adyacentes a él.
un grafo es un conjunto de
objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se
representa gráficamente como un conjunto de puntos (vértices o nodos) unidos
por líneas (aristas).
Desde un punto de vista práctico,
los grafos permiten estudiar las interrelaciones entre unidades que interactúan
unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices
representan terminalesy las aristas representan conexiones (las cuales, a su vez, pueden
ser cables o conexiones inalámbricas).
Prácticamente cualquier problema
puede representarse mediante un grafo, y su estudio trasciende a las diversas
áreas de las ciencias
exactas y las ciencias sociales.
EXCELENTE DOCUMENTO ME AYUDO MUCHO...GRACIAS
ResponderEliminar