Estructuras en C++

TRABAJO EXTRA CLASE DE

PROGRAMACIÓNII TRIMESTRE

Kimberly Mora Chaves 11-2

Estructuras de Datos 1

S


A

S

IntroducciónIntroducciónIntroducciónIntroducciónEn este trabajo se presentaran varios conceptos relacionados con las estructuras de datos en C++ con el propósito de ampliar los conocimientos, hacia éstos; poner a prueba nuestra creatividad, imaginación entre otras.


Se realiza con motivo de ser clasificado como trabajo extra clase.

Como objetivo del trabajo tenemos: desarrollar la investigación y la descripción de cada uno de los temas, estableciendo la fundamentación teórica de dichos conceptos de manera interactiva e interesante.

SA


SA

ÍndiceÍndiceÍndiceÍndicePunteros o apuntadores 6Listas enlazadas simples 8Colas 10Pilas 12Listas doblemente enlazadas 14Estructuras circulares 16Recursividad 18Recursividad versus iteración 21Árboles binarios 23Grafos 30Archivos secuenciales 32Archivos directos 34Estructura de registro/registro de datos 36Modo de operación de los archivos 38Ejemplos de archivos 40Conclusión 42Bibliografía 44


S

A


SA

Punteros o apuntadoresPunteros o apuntadoresPunteros o apuntadoresPunteros o apuntadores

Variable que direcciona o apunta a un dato que esté almacenado en un lugar de la memoria del computador.


ConceptoConcepto

Caracter íst iCaracter íst icascas Dicha variable no guarda directamente el dato, sino más bien lo que almacena es una

dirección de la memoria del computador done está almacenado dicho dato. Permiten simular llamadas por referencia dentro de una función o procedimiento. Permiten crear y manipular estructuras de datos de manera dinámica. Se inicializa con la palabra NULL.

EjemplosEj emplos

void main(){ double v1=2.5, v2=3.5, v3; double *ptrv1, *ptrv2; ptrv1=&v1; *ptrv1=2*v1; ptrv2=&v2; v3=3*(*ptrv2-*ptrv1); cout<<v3; getch();}

int dato;Int *punterodato;*punterodato=NULL;

10

SA


SA

Listas enlazadas simplesListas enlazadas simplesListas enlazadas simplesListas enlazadas simples


Estructuras dinámicas que están compuestas por un conjunto de estructuras llamados nodos, que están enlazados uno con el otro por medio de un campo de tipo puntero.

ConceptoConcepto

Caracter í st iCaracter í st icascas Estructura lineal.

Cada nodo tendrá solamente un apuntador. El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista). Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el

puntero siguiente permite el desplazamiento hacia el próximo elemento. El desplazamiento se hace en una sola dirección, del primer al último elemento, o del

último al primero. Pero solo una.

Ej emplosEj emplosstruct lista{ int dato; struct lista *siguiente;};

struct lista{ float nota1,nota2,nota; double promedio; struct lista *siguiente;};

SA


SA

Colas Colas Colas Colas


Es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro.

ConceptoConcepto

Caracter íst iCaracter íst icascas Estructura FIFO (del inglés First In First Out), debido a que el primer elemento en

entrar será también el primero en salir. Se utilizan en sistemas informáticos, transportes y operaciones de investigación.

Ej emplosEj emplos

SA


SA

Pilas Pilas Pilas Pilas


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".

ConceptoConcepto

Caracter íst iCaracter íst icascas Estructura lista LIFO (Last In First Out), el último en entrar es el primero en salir.

EjemplosEj emplos

SA


SA

Listas doblemente Listas doblemente enlazadas enlazadas

Listas doblemente Listas doblemente enlazadas enlazadas


Estructuras dinámicas que están compuestas por un conjunto de estructuras llamados nodos, que están enlazados uno con el otro por medio de dos campos de tipo puntero.

ConceptoConcepto

Caracter íst iCaracter íst icascas

Ej emplosEj emplos

Estructura lineal. Cada nodo tendrá dos apuntadores. Anterior y siguiente. El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista). El puntero anterior del primer elemento debe también apuntar hacia NULL(el inicio de

la lista),

struct lista{ int dato; struct lista *siguiente, *anterior;};

SA


SA

Estructuras circulares Estructuras circulares Estructuras circulares Estructuras circulares


Una lista circular es una lista lineal en la que el último nodo a punta al primero.

ConceptoConcepto

Caracter í st iCaracter í st icascas

Ej emplosEj emplos

Cada nodo siempre tiene uno anterior y uno siguiente.

En algunas listas circulares se añade un nodo especial de cabecera.

typedef struct _nodo{ int dato; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Lista;

SA


SA

RecursividadRecursividadRecursividadRecursividad

No todas las funciones pueden llamarse a sí mismas, sino que deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a que el programa termine inadecuadamente.


Permite que una función pueda llamarse asimismo desde la misma función.

Se puede utilizar como una alternativa a la iteración.

Es una herramienta poderosa e importante en la resolución de problemas en programación.

Su uso permite a los programadores especificar las soluciones naturales, más lógicas, elegantes, sencillas, que serían, en caso contrario difícil de resolver.

Tampoco todos los lenguajes de programación permiten usar recursividad. C++ permite la recursividad.

SA

RecursividadRecursividadRecursividadRecursividad


/* Función recursiva para cálculo de factoriales */int factorial(int n){ if(n < 0) return 0; else if(n > 1) return n*factorial(n-1); /* Recursividad */ return 1; /* Condición de terminación, n == 1 */ }

/*Función recursiva para la Serie fibonacci*/#include<stdio.h> int fibonacci(int n) { if (n<2) return n; else return fibonacci(n-1) + fibonacci(n-2); } int main() { int num=0,res=0; printf("::NUMEROS DE FIBONACCI::\n"); printf("Introduce el numero de numeros: "); scanf("%i",&num); for(int i=0;i<=num-1;i++) { res = fibonacci(i); printf("%i ", res); } printf("\n"); return 0; }

S

A


SA

Recursividad versus Recursividad versus iteracióniteración

Recursividad versus Recursividad versus iteracióniteración

1- Ambas realizan una repetición:a)Solución iterativa repite el cuerpo del bucle.b)Solución recursiva repite las llamadas al método recursivo.


2- Ambas tienen una condición de terminación.a)Solución iterativa: termina cuando se incumple la condición de continuación del bucle.b)Solución recursiva: se termina cuando una llamada alcanza el caso base (inducción) desencadenando una secuencia de vuelta atrás.

3- Ambas se deben diseñar para converger a la solución (principio de convergencia, y que no se salten la condición de terminación).a)Solución iterativa: se llega a cumplir la condición de terminación (esto se debe garantizar).b)Solución recursiva: se debe garantizar que se llegue al caso base.

Toda solución recursiva puede encontrar Toda solución recursiva puede encontrar una solución iterativa equivalente, una solución iterativa equivalente, mientras que lo contrario no siempre es mientras que lo contrario no siempre es cierto.cierto.

SA


SA

Árboles binariosÁrboles binariosÁrboles binariosÁrboles binarios


Es el que cada elemento apunta como máximo a otros 2 elementos, comúnmente llamados hijo izquierdo y hijo derecho.

ConceptoConcepto


Un árbol binario de buque da o ABB, es un árbol binario en el cual para todo elemento, los elementos mayores a él, se ubican en su rama derecha, mientras que los elementos menores van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen elementos repetidos.

SA

Árboles binariosÁrboles binariosÁrboles binariosÁrboles binarios


EjemplosEj emplos

ABB crearNodo(int x){ ABB nuevoNodo = new(struct nodo); nuevoNodo->nro = x; nuevoNodo->izq = NULL; nuevoNodo->der = NULL; return nuevoNodo; }

void insertar(ABB &arbol, int x){ if(arbol==NULL) { arbol = crearNodo(x); } else if(x < arbol->nro) insertar(arbol->izq, x); else if(x > arbol->nro) insertar(arbol->der, x); }

S

A


S

A

EnOrdenEnOrdenEnOrdenEnOrden


Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho

ConceptoConcepto

Ej emplosEj emplos

void enOrden(ABB arbol) { if(arbol!=NULL) { enOrden(arbol->izq); cout << arbol->nro << " "; enOrden(arbol->der); } } S

A

PreOrdenPreOrdenPreOrdenPreOrden


Primero el padre, luego el hijo izquierdo y finalmente el hijo derecho.

ConceptoConcepto

Ej emplosEj emplos

void preOrden(ABB arbol) { if(arbol!=NULL) { cout << arbol->nro <<" "; preOrden(arbol->izq); preOrden(arbol->der); }} S

A

PostOrdenPostOrdenPostOrdenPostOrden


Primero hijo izquierdo, luego el hijo derecho y finalmente el padre.

ConceptoConcepto

Ej emplosEj emplos

void postOrden(ABB arbol){ if(arbol!=NULL) { postOrden(arbol->izq); postOrden(arbol->der); cout << arbol->nro << " "; }} S

A


SA

GrafosGrafosGrafosGrafos


ConceptoConcepto


Ej emplosEj emplos

SA

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.

Son objeto de estudio de la teoría de grafos.Típicamente, un grafo se representa gráficamente como un conjunto de puntos

V:={ 1,2,3,4,5,6}E:={ { 1,2} ,{ 1,5} ,{ 2,3} ,{ 2,5} ,{ 3,4} ,{ 4,5} ,{ 4,6} }El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.


SA

Archivos secuencialesArchivos secuencialesArchivos secuencialesArchivos secuenciales


Se componen de un conjunto de registros donde cada registro como tal es una línea de datos donde cada una

posee un inicio y un final.

ConceptoConcepto

Se maneja como documento de datos que siguen el orden a como están

escritos.

Son aquellos archivos que también se conocen como archivos planos.

Todos se almacenan por posiciones consecutivas.

SA


SA

Archivos secuencialesArchivos secuencialesArchivos secuencialesArchivos secuenciales


Se componen de un conjunto de registros de datos los cuales responden a una estructura de registro de una

entidad dada.

ConceptoConcepto

Identificación

123

SalarioNombre

100000000Pedro

Estructura del registro

Registro de datos

SA


SA

Estructura del registro y Estructura del registro y registro de datosregistro de datos

Estructura del registro y Estructura del registro y registro de datosregistro de datos


Identificación

123

SalarioNombre

100000000Pedro

Estructura del registro

Registro de datos

Conjunto de campos, características o atributos relacionados entre si, los cuales responden a una

entidad dada.

Conjunto de datos relacionados entre si, los cuales responden a una estructura de registro dada.

SA


SA

Modo de operaciónModo de operaciónModo de operaciónModo de operación


Modo de operación Descripción

r Abrir un archivo solo para lectura.

wCrear un archivo para escritura. Si ya existe se borra el contenido actual.

aAgregar, abrir o crear un archivo para escribir registros al final del mismo.

r+ Abrir y escribir en un archivo.

w+Crear un archivo para actualizar. Si ya existe se borra el contenido actual.

a+

Agregar, abrir o crear un archivo para actualizar, la escritura se efectuará al final del mismo

SA


SA

Archivos directos, Archivos directos, ejemplosejemplos

Archivos directos, Archivos directos, ejemplosejemplos


#include <iostream> #include <stdlib.h>

struct nodo{ int nro; struct nodo *izq, *der; }; typedef struct nodo *ABB; /* es un puntero de tipo nodo que hemos llamado ABB,*//*que ulitizaremos para mayor facilidad de creacion de variables */

ABB crearNodo(int x) { ABB nuevoNodo = new(struct nodo); nuevoNodo->nro = x; nuevoNodo->izq = NULL; nuevoNodo->der = NULL; return nuevoNodo; }

void insertar(ABB &arbol, int x){ i f (arbol==NULL) { arbol = crearNodo(x); } else if (x < arbol->nro) insertar(arbol->izq, x); else if(x > arbol->nro) insertar(arbol->der, x);}

void verArbol(ABB arbol, int n){ i f(arbol==NULL) return; verArbol(arbol->der, n+1); for(int i=0; i<n; i++) cout<<" "; cout<< arbol->nro <<endl; verArbol(arbol->izq, n+1);}

void main() { ABB arbol = NULL; // creado Arbol int n; // numero de nodos del arbol int x; // elemento a insertar en cada nodo cout << "\n\t\t ..[ ARBOL BINARIO DE BUSQUEDA ].. \n\n"; cout << " Numero de nodos del arbol: "; cin >> n; cout << endl; for(int i=0; i<n; i++) { cout << " Numero del nodo " << i+1 << ": "; cin >> x; insertar( arbol, x); } cout << "\n Mostrando ABB \n\n"; verArbol( arbol, 0); }

S

A


S

A

ConclusiónConclusiónConclusiónConclusiónEn la elaboración de este trabajo pude:


Aprendí nuevos conceptos, características y ejemplos de los temas.

Puse a prueba el uso de la creatividad en la elaboración del trabajo.

Reafirmar el significado de varios conceptos, que aunque ya conocía tenía que refrescarlos y saber más detalles sobre ellos.

SA


SA

BibliografíaBibliografíaBibliografíaBibliografía• Lenguaje de programación C, Introducción a la programación en C. Mario Gómez Moraga.• http://recursividadenc.blogspot.com/2012/03/recursividad-en-c.html• http://btocastro.blogspot.com/2011/07/recursividad-vs-iteracion.html• https://www.google.co.cr/imghp?hl=es&tab=ii• http://es.kioskea.net/faq/2842-la-lista-enlazada-simple• http://casicodigo.blogspot.com/2012/10/colas-en-c.html• http://www.conclase.net/c/edd/?cap=002• http://www.conclase.net/c/edd/?cap=004• http://casicodigo.blogspot.com/2012/11/arboles-binarios-de-busqueda-c.html• http://www.slideshare.net/luismy_martinez/archivo-secuencial• http://es.wikipedia.org/wiki/Grafo


A

Education

Estructuras en C++