UNIDAD III. ESTRUCTURAS DE DATOS (LINEALES Y NO LINEALES)

UNIDAD III. ESTRUCTURAS DE DATOS (LINEALES Y NO LINEALES)

ARBOLES

GRAFOS

UNIDAD IV. RECURSIVIDAD

UNIDAD V APUNTADORES

UNIDAD III ESTRUCTURAS DE DATOS (LINEALES Y NO LINEALES)

Actividad 1

DEFINICIÓN DE UNA ESTRUCTURA DE DATOS PILA

Definición 1

Colección de datos. Es una estructura de datos que permite almacenar datos del mismo tipo, en la cual en un extremo se puede insertar y eliminar elementos, llamado la parte superior de la pila o cima. A este tipo de estructura de datos se le conoce como LIFO (primero en entrar, último en salir).

70705" RKNCU

Definición 2

Una pila (stack) es una estructura lineal a cuyos datos sólo se puede acceder por un solo extremo, denominado  tope o  cima (top). En esta estructura sólo se pueden efectuar dos operaciones: añadir y eliminar un elemento, acciones que se conocen por meter (push), y sacar (pop). Si se meten varios elementos en la pila y después se sacan de ésta, el último elemento en entrar será el primero en salir. Por esta razón se dice que la pila es una estructura en la que el último en entrar es el primero en salir, en inglés, LIFO (last in first out).

Definición 3

Una pila es un tipo especial  de lista en la que todas las  inserciones y borrados tienen lugar en un extremo denominado  tope. A las pilas se les llama también “listas LIFO” (last in first out) o  listas “último en entrar, primero en salir”.

LA ESTRUCTURA DE UNA PILA

 

CÓMO FUNCIONA UNA PILA

Una pila es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. Sólo es

posible un modo de acceso a esta estructura: a través de la cabeza de la pila. De este modo podemos

añadir un elemento a

la cabeza de la pila o

extraer un elemento de la cabeza de la pila. Debido a que las operaciones de extracción e inserción

se realizan por el mismo extremo, el último elemento en ser añadido será el primero en ser extraído; por ello a estas

estructuras se las conoce con el nombre de
LIFO (last-in, first-out; último en entrar, primero en salir).

APLICACIONES DE LAS PILAS

IMPLEMENTACION ALGORITMICA DE UNA PLIA

#include <stdlib.h>
#include <stdio.h>

typedef struct _nodo \{
   int valor;
   struct _nodo *siguiente;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;

/* Funciones con pilas: */
void Push(Pila *l, int v);
int Pop(Pila *l);

int main() \{
   Pila pila = NULL;

   Push(&pila, 20);
   Push(&pila, 10);
   printf("%d, ", Pop(&pila));
   Push(&pila, 40);
   Push(&pila, 30);
   printf("%d, ", Pop(&pila));
   printf("%d, ", Pop(&pila));
   Push(&pila, 90);
   printf("%d, ", Pop(&pila));
   printf("%d\n", Pop(&pila));
   getchar();
   return 0;
}
void Push(Pila *pila, int v) \{
   pNodo nuevo;

   /* Crear un nodo nuevo */
   nuevo = (pNodo)malloc(sizeof(tipoNodo));
   nuevo->valor = v;
  
   /* Añadimos la pila a continuación del nuevo nodo */
   nuevo->siguiente = *pila;
   /* Ahora, el comienzo de nuestra pila es en nuevo nodo */
   *pila = nuevo;
}
int Pop(Pila *pila) \{
   pNodo nodo; /* variable auxiliar para manipular nodo */
   int v;      /* variable auxiliar para retorno */
  
   /* Nodo apunta al primer elemento de la pila */
   nodo = *pila;
   if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */
   /* Asignamos a pila toda la pila menos el primer elemento */
   *pila = nodo->siguiente;
   /* Guardamos el valor de retorno */
   v = nodo->valor;
   /* Borrar el nodo */
   free(nodo);
   return v;
}



IMPLEMENTACIÓN DE UNA PILA EN LENGUAJE C++

/* -------------------------------------------------- */
/* Implementación de una pila mediante lista enlazada */
/* ------ http://www.lawebdelprogramador.com -------- */
/* -------------------------------------------------- */
#include <stdio.h>
#include <stdlib.h>
/* declaracion de la pila*/
struct tipo_pila
{
 int clave;
 struct tipo_pila *sig;
};
/* Cabeceras de prototipos de funciones */
void crear_pila(struct tipo_pila **pila);
int es_vacia(struct tipo_pila *pila);
void apilar_pila(struct tipo_pila *pila, int elem);
void desapilar_pila(struct tipo_pila *pila, int *elem);
void crear_pila(struct tipo_pila **pila)
{
 *pila=(struct tipo_pila *) malloc(sizeof(struct tipo_pila));
 (*pila)->sig=NULL;
}
void apilar_pila(struct tipo_pila *pila, int elem)
{
 struct tipo_pila *nuevo;
 nuevo=(struct tipo_pila *) malloc(sizeof(struct tipo_pila));
 nuevo->clave=elem;
 nuevo->sig=pila->sig;
 pila->sig=nuevo;
}
void desapilar_pila(struct tipo_pila *pila, int *elem)
{
 struct tipo_pila *aux;
 aux=pila->sig;
 *elem=aux->clave;
 pila->sig=aux->sig;
 free(aux);
}
int es_vacia(struct tipo_pila *pila)
{
 return (pila->sig==NULL);
}
/* programa principal */
main(void)
{
 struct tipo_pila *pila;
 int elem;
 crear_pila(&pila);
 if (es_vacia(pila)) printf("\nPila vacia!");
 apilar_pila(pila, 1);
 desapilar_pila(pila, &elem);
}

UNIDAD II TIPOS DE DATOS ESTRUCTURADOS

//PROGRAMA 1//
#include <iostream.h>
#include <conio.h>
int main()
{
clrscr();
const int MAXTEMPS = 5;
int i, temp[MAXTEMPS];
for (i = 0; i < MAXTEMPS; i++)
{
cout << "introduzca una temperatura: ";
cin>> temp[i];
}
cout << endl;
for (i = 0; i < MAXTEMPS; i++)
cout << "la temperatura " << i <<" " << "es: " << temp[i] << endl;
getch();
return 0;
}

//PROGRAMA 2
#include <iostream.h>
#include <conio.h>
int main()
{
//clrscr();
const int MAXTEMPS = 5;
int i, temp[MAXTEMPS], total = 0;
for (i = 0; i < MAXTEMPS; i++)
{
cout << "introduzca una temperatura: ";
cin>> temp[i];
}
cout << "\nEl total de las temperaturas";
for (i = 0; i < MAXTEMPS; i++)
{
cout << " " << temp[i];
total = total + temp[i];
}
cout << " es " << total <<endl;
getch();
return 0;
}

//PROGRAMA 3
#include <iostream.h>
#include <conio.h>
int main()
{
//clrscr();
const int MAXELS = 5;
int i, max, nums[MAXELS] = {2, 18, 1, 27, 16};
max = nums[0];
for (i = 1; i < MAXELS; i++)
if (max < nums[i])
max = nums[i];
cout << "El maximo valor es : " << max << endl;
getch();
return 0;
}

//PROGRAMA 4
// Suma de dos vectores
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
 main()
{
//clrscr();
const int lim = 5;
int A[lim], B[lim], C[lim], i;
cout << "Dame los " << lim << " valores del arreglo A, "
<< "separados por espacios: ";
for (i = 0; i < lim; i++) cin >> A[i];
cout << "\nDame los " << lim << " valores del arreglo B, "
<< "separados por espacios: ";
for (i = 0; i < lim; i++) cin >> B[i];
cout << "\nLa suma es: " << endl;
for (i = 0; i<lim; i++)
{
C[i] = A[i] + B[i];
cout << C[i] << endl;
}
getch();5
}

//ROGRAMA 5
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <iomanip.h>
int main()
{
//clrscr();
const int NUMRENG = 3;
const int NUMCOL = 4;
int i,j;
int val[NUMRENG][NUMCOL] = {8, 16, 9, 52, 3, 15, 27, 6, 14,
25, 2, 10};
cout << "\nDespliegue del arreglo val por elemento explicito" <<endl
<< "\n" << setw(4) << val[0][0] << setw(4) << val[0][1]
<< setw(4) << val[0][2] << setw(4) << val[0][3]
<< "\n" << setw(4) << val[1][0] << setw(4) << val[1][1]
<< setw(4) << val[1][2] << setw(4) << val[1][3]
<< "\n" << setw(4) << val[2][0] << setw(4) << val[2][1]
<< setw(4) << val[2][2] << setw(4) << val[2][3];
cout << "\n\nDespliegue del arreglo val empleando ciclos for anidados" <<
endl;
for (i = 0; i < NUMRENG; i++)
{
cout << "\n";
for (j = 0; j < NUMCOL; j++)
cout << setw(4) << val[i][j];
}
cout << endl;
getch();
return 0;
}

//0PROGRAMA 6
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <iomanip.h>
int main()
{
//clrscr();
const int NUMRENG = 3;
const int NUMCOL = 4;
int i,j;
int val[NUMRENG][NUMCOL] = {8, 16, 9, 52, 3, 15, 27, 6, 14,
25, 2, 10};
//multiplicar cada elemento por 10 y desplegarlo
cout << "\nDesplegar los elementos multiplicados";
for (i = 0; i < NUMRENG; i++)
{
cout << endl;
for (j = 0; j < NUMCOL; j++)
{
val[i][j] = val[i][j] * 10;
cout << setw(5) << val[i][j];
}
}
cout << endl;
getch();
return 0;
}

UIDAD II TIPOS DE DATOS ESTRUCTURADOS

TAREA 1

UNIDAD I. CONCEPTOS BÁSICOS

UNIDAD I. CONCEPTOS BÁSICOS

UNIDAD I. CONCEPTOS BÁSICOS

 

TAREA1.

ESTRUCTURA DE DATOS

Una estructura de datos: es un conjunto de datos cuyas características se relacionan de una u otra manera, debido a la forma en que están organizados en forma de conjuntos o clases y los cuales hace más fácil acceder a ellos y de la misma forma resulta más eficiente la manipulación de dichos datos.

 

Definición 1

Las estructuras de datos nos han estado rodeando desde la era de la programación estructurada. Una definición de esa era: una estructura de datos es un conjunto de tipos, un tipo diseñado partiendo de ese conjunto de tipos, un conjunto de funciones, y un conjunto de axiomas. Esta definición implica que una estructura de datos es un tipo con implementación. En nuestra era de la programación orientada a objetos, tipo con implementación significa clase. Algunos ejemplos de estructuras de datos son los arrays, las listas enlazadas, las pilas y las colas.

 

Definición 2

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:

•          Alta, adicionar un nuevo valor a la estructura.

•          Baja, borrar un valor de la estructura.

•          Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).

Definición 3

 

Empecemos recordando que un dato de tipo simple, no está compuesto d otras estructuras, que no sean los bits, y que por tanto su representación sobre el ordenador es directa, sin embargo existen unas operaciones propias de cada tipo, que en cierta manera los caracterizan. Una  estructura de datos es, a grandes rasgos, una colección de datos (normalmente de tipo simple) que se caracterizan por su organización y las operaciones que se definen en ellos. Por tanto, una estructura de datos vendrá caracterizada tanto por unas ciertas relaciones entre los datos que la constituyen (p.e., el orden de las componentes de un vector de números reales), como por las operaciones posibles en ella. Esto supone que podamos expresar formalmente, mediante un conjunto de reglas, las relaciones y operaciones posibles (tales como insertar nuevos elementos o como eliminar los ya existentes). Por el momento y a falta de otros, pensemos en un vector de números, como el mejor ejemplo de una estructura de datos.