Estrunctura de Datos y Algoritmos I

De Computacion

Un aspecto muy importante en el desarrollo de aplicaciones es conocer las estructuras de datos utilizadas y adicionalmente optimizar los recursos del computador tales como memoria, esto se logra con una adecuada utilización de dichas estructuras. El aprendizaje de las estructuras de datos así como también de los algoritmos es realmente importante ya que por una parte los programas manipulan datos y por otro lado estas soluciones tienen una secuencia ordenada de pasos para obtener el resultado; como se podrá dar cuenta los datos necesitan de un soporte para que sean almacenados esto lo dan las estructuras de datos y por otra parte la lógica de la solución esta dada por el algoritmo a seguir.

El desarrollo del curso se realiza en base a los siguientes capítulos los cuales se describen en forma breve a continuación: En el primer capitulo “Estructuras de datos Simples y compuestas” en este capitulo se expone una visión general de las estructuras de datos fundamentales, igualmente se presenta una clasificación de los tipos de datos, esto es fundamental puesto que representa la base para obtener una panorámica de los datos que estudiaremos en los capítulos siguientes

El segundo capitulo denominado “Estructuras Lineales Estáticas: Arreglos” estudiaremos las características fundamentales de estas estructuras igualmente se estudian los algoritmos necesarios para manipular los datos de los arreglos.

El tercer capitulo denominado “Estructuras Dinámicas: Apuntadores” es la base para estudiar las listas enlazadas, si bien es cierto las estructuras de datos dinámicas pueden resultar complicadas de entender y aplicarlas en la resolución de problemas, este resultara sencillo si se entiende claramente l naturaleza de los punteros.

El segundo bimestre se inicia con el cuarto capitulo “Listas enlazadas” es muy importante entender los algoritmos de manipulación de estas estructuras puesto que las mismas se utilizan frecuentemente en aplicaciones mas avanzadas.

En el capitulo 5 se estudian las pilas y colas las cuales son una extensión de las listas enlazadas, de hecho pertenecen a este tipo de estructuras pero con algunas restricciones de tipo funcional tal como lo veremos mas adelante

Finalmente en el capitulo sexto “Estructuras no lineales: Árboles” se estudia los árboles binarios, pues dichas estructuras son muy importantes en los ciclos posteriores de nuestra carrera.

Objetivos Generales

Conocer las estructuras de datos empleados en el desarrollo de aplicaciones, tanto fundamentales como compuestas.
Estudiar y aplicar los algoritmos que manipulan las estructuras de datos compuestas tales como arreglos, Listas, Pilas, Colas, Árboles binarios
Aplicar los conceptos relacionados con estructuras de datos en la solución de problemas de carácter general.

Bibliografía

Libro básico

AGUILAR LUIS JOYANES, Zahonero Martínez Ignacio, Algoritmos y Estructuras de Datos. Una perspectiva en C, McGraw-Hill, Madrid-España, 2004.

Este es un libro en el cual se exponen todos los conceptos que estudiaremos en este curso, adicionalmente el libro dispone de una serie de ejercicios al final de cada capitulo para que el estudiante seleccione algunos de estos y los desarrolle igualmente los conceptos expuestos en este libro se ven reforzados con aplicaciones en lenguaje C.

Bibliografía complementaria:

JOYANES AGUILAR , LUIS, Programación en C, Metodología, estructura de datos y objetos, McGraw-Hill, Madrid-España,2001.

Este libro proporciona el fundamento conceptual para la comprensión y aprendizaje de los fundamentos de la Programación en C, utilizando las diferentes estructuras de datos, a través de ejemplos y ejercicios resueltos.

ROMAN MARTINEZ, ELDA QUIROGA, Estructuras de Datos, Referencia práctica con orientación a objetos, México, Thomson, 2002

Este libro es mucho más teórico que el libro básico, el mismo que no esta orientado a ningún lenguaje específico, todos los ejercicios se encuentran expuestos mediante Pseudocodigo. Sitios de Internet

http://www.elrincondelc.com/cursoc/cursoc.html

http://linuxupc.upc.es/~pep/Punteros.html

http://www.pablin.com.ar/computer/cursos/c3/index.htm

Desarrollo del Aprendizaje

Capitulo1: ESTRUCTURAS DE DATOS SIMPLES Y COMPUESTOS

Datos Generales:

Texto Base	AGUILAR LUIS JOYANES, Zahonero Martínez Ignacio, Algoritmos y Estructuras de Datos. Una perspectiva en C, McGraw-Hill, Madrid-España, 2004.
Capítulo	1. Estructuras de datos Simples y Compuestas
Páginas	1.1; 1.2; 4.1; 4.2; 4.3
Horas de estudio empleadas para el desarrollo del contenido	6 horas

Introducción:

Bueno ya estamos listos para empezar con el desarrollo del aprendizaje de esta asignatura, nuevamente quiero desearles éxitos en el desarrollo de la misma. En primer lugar comentemos algo sobre los sistemas computacionales, como ustedes saben, estos efectúan una serie de tareas, cálculos o procesos y generan resultados, pero lo mas importante es que esas tareas se efectúan en base a los “datos” esa es precisamente la razón de ser de esta asignatura, estudiar las Estructuras de Datos, Tipos de Datos y principalmente los algoritmos utilizados para manipular esa información; en este primer capitulo vamos a estudiar algunos conceptos básicos, los tipos de datos fundamentales o primitivos, haremos una clasificación sobre los tipos de datos, el estudio de estos contenidos es muy importante puesto que es la base para entender las estructuras de datos en los siguientes capítulos.

Objetivos:

Estudiar y comprender la importancia de las estructuras de datos en el desarrollo de programas.
Conocer la clasificación de los tipos de datos y su aplicabilidad en diferentes entornos de aplicaciones.

Conceptos Claves:

Algoritmo.- Es un conjunto de pasos o tareas sistemáticamente definidas que cumplen con un objetivo especifico.
Tipos de datos simples.- Es una estructura en la cual se almacena un solo valor el mismo puede ser entero, real o booleano.
Tipos de datos compuestos.- Es una estructura que agrupa varios datos los cuales pueden ser simples o igualmente complejos

Esquema de Estudio:

A continuación se detallan los temas que se deben desarrollar, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que cada estudiante estima que necesita tutoría y realizar anotaciones personales

Tema a revisar	Descripción del Contenido a revisar	Actividades Recomendadas
1.1 Tipos de datos	Se presenta una visión general de los tipos de datos	Se recomienda leer y entender los conceptos expuestos en la guía y en el libro
1.2 Tipos de datos primitivos	Se exponen los tipos de datos primitivos así como la cantidad de bytes que necesitan para almacenarse en memoria	Se recomienda analizar los conceptos expuestos sobre overflow, este análisis permitirá comprender como se almacenan los datos primitivos en memoria, igualmente se debe ejecutar el programa propuesto para corroborar lo expuesto.
1.3 Tipos de Datos compuestos	Se presenta una visión global de estos tipos de datos: Arreglos, Cadenas y Registros	Revisar los contenidos teóricos expuestos en el libro sobre registros, los arreglos serán tratados ampliamente en el segundo capitulo

1.1. Tipos de datos

Es evidente que todo software o programa que desarrollemos, por mas pequeño que sea necesita una definición y posterior uso de información, pero en primer lugar debemos entender claramente cuales son los tipos de datos existentes, esto nos ayudara mucho para construir programas robustos, fiables y sobre todo que se utilice los recursos estrictamente necesarios. Desde un punto de vista muy general los tipos de datos se pueden clasificar en dos grandes grupos:

Tipos de datos Primitivos

Tipos de datos Compuestos

Con toda seguridad los datos primitivos ya los han utilizado en las asignaturas de programación (lenguaje de alto nivel), pues un programa por más pequeño que sea utilizada definiciones de datos simples, en todo caso haremos una revisión de este tema.

Pensemos que esta asignatura no esta orientada únicamente a explicar o enseñar las estructuras de datos existentes, el alumno debe tener criterios para seleccionar una u otra estructura dependiendo de la naturaleza del problema, un programa se puede desarrollar de varias formas, pero lo importante es una solución optima, definitivamente no es lo mismo resolver un problema mediante arreglos o mediante punteros, se debe utilizar la mejor opción es decir aquella que preste ventajas en cuanto a optimización de recursos, tiempos de respuesta, facilidades de implementación y adicionalmente que se pueda desarrollar las operaciones o funcionalidades que requiere la solución.

En la sección 1.2 del libro se exponen criterios relacionados con la necesidad de una buena definición de estructuras de datos.

1.2. Tipos de Datos Primitivos

Los Datos Primitivos son la base de cualquier estructura, en definitiva no se pueden descomponer, son únicos, puntuales, pues al declarar una variable de este tipo se tiene un solo dato o valor almacenado en dicha variable, obviamente durante el transcurso del programa ese dato puede cambiar; los siguientes son ejemplos de datos de tipo primitivo:

a = 30

x = 29.67

c = ‘w’

u = true

Que tal, sencillo no, la información que se almacena en este tipo de datos puede ser numérica, caracteres o de tipo lógica; en función de esto revisemos una nueva clasificación de estos datos primitivos:

Enteros (3; 100; 27; etc.)

Reales (3.76; 3.1416; 2.71828182; 10.0002; etc.)

Carácter (‘a’; ‘+’; ‘$’; ‘6’; ‘?’; ‘S’; etc.)

Lógico (true; false)

NOTA

Antes de revisar y analizar con mayor detalle estos tipos de datos, es importante puntualizar que el lenguaje que utilizaremos como base para probar nuestros algoritmos es el lenguaje “C” (no C++), por lo tanto las explicaciones que se impartan en esta guía estarán orientadas a este lenguaje. Otro aspecto importante es que los tipos de datos pueden diferir de una maquina a otra, dependiendo de la arquitectura de la misma y del compilador que se este utilizando por lo tanto recomiendo probar los programas que desarrollaremos aquí en sus respectivas computadoras.

Enteros.

Los datos numéricos son los mas fáciles de entender tal como se menciona en la Pág. 5 del libro y mas aun si estos son enteros pero es importante conocer aspectos sobre overflow, underflow, rango de valores, etc. Los datos de tipo entero no tienen parte decimal.

Reales. Las variables declaradas de este tipo pueden almacenar números reales, es decir números con parte decimal, la capacidad de almacenamiento de estas variables igualmente depende del compilador.

Carácter.

Este tipo de dato permite almacenar un elemento del conjunto de caracteres ASCII.

Lógicos.

También llamados lógicos y pueden tomar uno de los siguientes valores: “True”, “False”.

En algunas partes del libro se mencionan los términos “overflow” y “underflow” a continuación se presenta una explicación sobre este comportamiento de las variables. Empecemos comentando que en el lenguaje “C” existe la función “sizeof” misma que devuelve el tamaño en bytes que requiere una variable o en general un tipo de dato para almacenarse en memoria; aplicando esta función a un dato de tipo “short int” (por ejemplo) podemos observar que devuelve el valor de 2, es decir en variables de este tipo se pueden almacenar únicamente valores que no excedan a 2 bytes, ahora bien recordemos que 1 byte es equivalente a 8 bits, es decir:

1 byte = 11111111 2 bytes = 1111111111111111

2 bytes son equivalentes a 16 bits, en base a esto se podría decir que el valor máximo que se puede almacenar en 16 bits es: 65535, puesto que:

1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
32768	16384	8192	4096	2048	1024	512	256	128	64	32	16	8	4	2	1

Ahora bien se supone que en una variable de tipo “short int” se podría almacenar como máximo el valor antes indicado, pero recordemos que esta variable no es de tipo “unsigned” (que quiere decir: sin signo o solo valores positivos) ósea que el numero 65535 debe ser repartido entre valores positivos y negativos:

65535 / 2 = 32767,5 lo cual equivale a 32767 ya que el tipo de dato del ejemplo es int

En conclusión en una variable de tipo “short int” se pueden almacenar:

Positivos: desde 1 hasta 32767 Negativos: desde -1 hasta -32768

Puesto que 32767 + 32768 = 65535 que es el numero máximo que se puede almacenar.

Una vez entendido esto vamos a explicar el concepto de “overflow” y “underflow” para lo cual vamos a disponer los números anteriormente mencionados de la siguiente forma:

Como se podrá dar cuenta los valores admisibles para el tipo “short int” los he dispuesto de forma similar a la distribución de los números en un reloj, en el cual el menor valor posible esta en la parte superior-central, desde ese punto van creciendo de forma ascendente hasta el ultimo (32767) mismo que regresa prácticamente al mismo lugar del punto de partida.

En consecuencia se produce “overflow” cuando asignamos un valor superior a 32767 (para el caso de una variable de tipo “short int”), por ejemplo si se asigna el valor 32770 (es decir 3 mas de lo aceptable) a una variable de este tipo y luego se quiere presentar o aplicar ese valor en otro proceso, veremos que el valor que se ha asignado es: -32766; esto se explica puesto que para los 3 valores adicionales o en exceso se tomo en cuenta los números que están después del valor máximo, tal como lo indica la figura.

El efecto de “underflow” es exactamente lo contrario es decir cuando se trata de asignar valores inferiores al mínimo permitido. En el siguiente programa se muestran las situaciones de desbordamiento (overflow y underflow).

Ejercicio 1.1: Escribir un programa que demuestre los casos de desbordamiento que se pueden presentar en una variable de tipo “short int”.

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: desbordamiento.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11	#include <string.h>
12	short int x;
13
14	void main( ) {
15	printf(“La cantidad de bytes necesarios para un dato de tipo short int es: %d \n\n”,sizeof(x));
16
17
18	x = 32767;
19	p align="left"> printf(“El valor asignado fue 32767, y el valor cargado es: %d \n”, x);</p>
20
21	x = 32770;
22	printf(“El tamaño del arreglo cadena1 es: %d\n\n”,
23	printf(“El valor asignado fue 32770, y el valor cargado es: %d (overflow)\n”, x);
24	printf(“El tamaño de la cadena de texto es: %d\n\n”,
25	x = -32771;
26	printf(“El valor asignado fue -32771, y el valor cargado es: %d (underflow)\n”, x);
27	printf(“El resultado de la concatenacion es: %s\n\n”,
28
29	system(“PAUSE”);
30	}
31

Resultados

Analisis

Línea 15-16	En estas líneas se presenta la cantidad de bytes que utiliza una variable de tipo short int
Línea 22-28	En estas líneas se asigna un valor determinado a la variable “x” y posteriormente se presenta el valor almacenado, se podrá dar cuenta que el valor presentado es diferente al asignado, esto ocurre por efectos del desbordamiento explicado anteriormente

1.3. Tipos de datos Compuestos

Es muy importante que el tema anterior (Tipos de datos primitivos) este bien claro para continuar el estudio de este nuevo tema.

Bien, conforme avanzamos en el estudio de las estructuras de datos y en general cuando se aprende a desarrollar programas en cualquier lenguaje, cada vez se tienen nuevas necesidades, las aplicaciones se vuelven mas exigentes y se hace imprescindible el uso de nuevas tecnologías de programación, estructuras de datos; mismas que no necesariamente son mas complejas pero deben satisfacer las nuevas características. Las estructuras de datos compuestas son una extensión de los datos primitivos y los más representativos son los arreglos y los registros. Arreglos.

Imaginemos que para un problema puntual se necesita almacenar los ingresos mensuales de un determinado negocio, o guardar las notas de los estudiantes de un curso, o grabar la temperatura en cada hora del día que registra un determinado proceso, etc. bueno si hablamos de problemas que se pueden resolver mediante el uso de un ordenador las necesidades van a ser cada ves mayores y diversas; analicemos los ejemplos planteados anteriormente, si utilizamos las estructuras de datos que hemos estudiado hasta ahora, naturalmente se deberían declarar tantas variables como se necesite para resolver el problema es decir: 12, la cantidad de alumnos que tenga el curso o 24 variables para el caso de la temperatura. Este tipo de aplicaciones se pueden resolver de forma mas eficiente si utilizamos alguna estructura que nos permita almacenar varios datos o valores en una sola variable, dicha estructura se denomina arreglo el mismo que es una colección de datos y a cada uno de los cuales se accede por medio de un índice que indica la posición del dato en la estructura, en los capítulos posteriores profundizaremos el estudio de los arreglos.

450	632	741	526	525	652	842	632	758	632	896	955
0	1	2	3	4	5	6	7	8	9	10	11

Cadenas.

Una cadena o string en una secuencia de caracteres (letras o caracteres especiales), en el lenguaje “C” las cadenas en realidad son arreglos de caracteres por lo cual esta estructura es en realidad un tipo de arreglo, un ejemplo de cadena puede ser:

Registros.

En las secciones 4.1, 4.2, 4.3 del libro básico se expone los conceptos importantes relacionados con estructuras (en lenguaje “C” a los registros también se los cono ce con el nombre de “estructura”), los registros no son complicados de comprender y mucho menos de implementar, desde un punto de vista global se los puede ver como una sola variable que agrupa a varios datos o variables de tipo primitivo como se vera mas adelante.

En estos se puede almacenar información de diferente tipo, por ejemplo almacenar la información de un empleado: nombres, apellidos, fecha de nacimiento, numero de años de servicio, si esta activo o no; como se podrá dar cuenta la información puede ser de tipo cadena, numérica o booleana es decir de tipo lógico; para lo cual seria imposible resolverlo mediante arreglos ya que estos almacenan varios datos efectivamente pero del mismo tipo lo cual no es útil en este contexto, bueno volviendo a nuestro ejemplo en este tipo de aplicaciones es ideal utilizar registros, pues se define una estructura con los tipos de datos que quiero utilizar y luego simplemente se declaran variables de ese tipo de estructura.

Registro empleado

{

Apellidos

Nombres

Cedula

Edad

Cargo

Categoría

Sueldo_Basico

N_cuenta

Activo

}

En el ejemplo anterior se ha definido una estructura (empleado) la cual es básicamente un tipo de dato, en el interior de la misma se han definido otras variables mismas que son simplemente datos de tipo primitivo: enteros, reales, etc. A estos elementos se les llama miembros o campos tal como se menciona en el libro, es importante indicar que los miembros de una estructura pueden ser igualmente otros tipos de datos compuestas como arreglos o inclusive otras estructuras, de hecho en la definición anterior se tiene definidos algunos campos que son arreglos de caracteres por ejemplo: “Apellidos” y “Nombres”.

Ahora puntualicemos algunas cosas que de hecho ya están en el libro pero simplemente las voy a recalcar. En la sección 4.1.2 (Pág. 90) se muestran dos ejemplos de cómo se pueden definir y declarar variables de registro, el registro denominado “coleccionesCD” no es una variable de registro es una definición y posteriormente se declaran variables del tipo antes mencionado lo cual se lo puede hacer en una o dos líneas tal como se menciona.

En las secciones posteriores de este capitulo también se presenta como inicializar (inicializar significa darle valores) un registro al momento de su declaración, en este sentido vale comentar que la información que se inicializa en el registro debe estar en el mismo orden en que están definidos sus miembros. Igualmente se puede aplicar el operador “sizeof” en los registros en este caso el valor resultante es la sumatoria del tamaño de cada miembro.

En este capitulo también se presenta la forma de acceso a las estructuras las cuales se pueden hacer de dos formas, nosotros en este capitulo utilizaremos únicamente aquella que utiliza el operador punto “.”, el otro operador lo utilizaremos posteriormente cuando estudiemos los punteros como estructuras de datos dinámicas.

1.4. Clasificación de las Estructuras de Datos

Para comprender mejor los contenidos que se imparten en esta asignatura, creo que es conveniente tener una visión global de las Estructuras de datos, para lo cual se presenta una clasificación. Empecemos comentando que existen algunos parámetros que se debe tomar en cuenta al momento de clasificar las estructuras de datos, estos parámetros entre otros son los siguientes: casillas de memoria que utilizan para su almacenamiento, dinamismo, lineabilidad y no lineabilidad, etc. de acuerdo ha esto se ha desarrollado la siguiente clasificación:

Por otra parte las estructuras también pueden clasificarse por su lineabilidad y no lineabilidad:

La principal característica de los datos simples es que ocupan solo una casilla de memoria, por lo tanto una variable simple hace referencia a un único valor a la vez; mientras que los datos estructurados se caracterizan por el hecho de que con un nombre (identificador de variable) se hace referencia a un grupo de casillas de memoria.

==Capitulo2: ESTRUCTURAS DE DATOS LINEALES ESTÁTICAS: ARREGLOS==

Datos Generales:

Texto Base	A GUILAR LUIS JOYAOYANES, Zahonero Martínez Ignacio, Algoritmos y Estructuras de Datos. Una perspectiva en C, McGraw-Hill, Madrid-España, 2004.
Capítulo	2. Estructuras de datos lineales estáticas: Arreglos
Secciones	3.1; 3.2; 3.3; 3.4; 6.1; 6.2; 6.3; 6.4; 6.5; 6.6; 6.7; 6.8; 6.10
Horas de estudio empleadas para el desarrollo del contenido	7 horas

Introducción:

En el primer capitulo estudiamos los Tipos de Datos en general, como recordara se dio una explicación preliminar de los Datos Compuestos, particularmente de los arreglos, en este capitulo se profundiza su estudio, revisaremos los algoritmos que manipulan la información en esta estructura de datos; como ustedes sabrán las materias orientadas a la resolución de problemas mediante el uso del ordenador son eminentemente practicas y nuestra materia no es la excepción, por lo tanto es indispensable que el estudiante paralelamente al desarrollo del curso haga la mayor cantidad de ejercicios, mismos que se pueden encontrar al final de cada capitulo del libro o inclusive se puede obtener de cualquier libro de programación o igualmente en Internet existe una gran cantidad de problemas planteados.

Objetivos:

Estudiar los arreglos como estructuras de datos conjuntamente con los algoritmos que manipulan los datos de esta estructura.
Aplicar los conceptos de Arreglo en el desarrollo de aplicaciones que utilizan esta estructura de datos.
Solucionar problemas computacionales mediante el uso de arreglos de dos dimensiones o matrices.
Estudiar las estructuras de datos compuestas concretamente arreglos.
Aplicar los algoritmos de manipulación de String y Arreglos en el desarrollo de aplicaciones
Aplicar los conocimientos adquiridos de matrices en el desarrollo de aplicaciones

Conceptos Claves:

Arreglo. Estructura de datos compuesta que almacena datos de forma consecutiva y a los cuales se puede acceder a través de un índice.
Índice.- Es un numero consecutivo que corresponde a cada casillero del arreglo, en lenguaje C este comienza desde 0.
Matriz.- Es una arreglo de dos dimensiones, es decir tiene dos índices, uno para las filas y el otro para las columnas.
Operaciones sobre los arreglos.- Son las operaciones que se pueden efectuar para manipular la información en un arreglo

Esquema de Estudio:

Tema a revisar	Descripción del Contenido a revisar	Actividades Recomendadas
2.1 Arreglos	Representan los conceptos relacionados con esta estructura	Lectura y comprensión de dichos conceptos
2.2 Cadenas de texto	Se presenta una explicación sobre esta estructura de datos	Se recomienda codificar y ejecutar el programa planteado en la guía didáctica y adicionalmente efectuar modificaciones al mismo
2.3.1 Operaciones con arreglos desordenados	Se presentan y explican mediante programas las principales operaciones que se efectúan en arreglos desordenados	El estudiante debe comprender la lógica de los programas planteados
2.3.2 Operaciones con arreglos ordenados	Se presentan y explican mediante programas las principales operaciones que se efectúan en arreglos ordenados	El estudiante debe comprender la lógica de los programas planteados, adicionalmente desarrollar los programas para Búsqueda, Modificación y eliminación en arreglos ordenados
2.4 Arreglos de dos dimensiones	Se presenta el marco teórico relacionado con esta estructura de datos	Se recomienda desarrollar el programa de la guía y adicionalmente desarrollar otros programas relacionados con matrices

2.5. Arreglos. El uso de arreglos en nuestras aplicaciones nos brinda mayores posibilidades para obtener soluciones muy potentes, esto se hace evidente principalmente en aplicaciones científicas en donde la aplicación de modelos matemáticos es determinante, por ejemplo en Ingeniería Civil se utilizan estas estructuras para resolver problemas con operaciones de matrices.

El estudio de este tema en la presente guía esta dividida principalmente en dos partes. En la primera parte que corresponde al capitulo 3 del libro en las secciones antes indicadas se estudian los fundamentos relacionados con la estructura de arreglo, se estudian aspectos tales como declaración de un arreglo, almacenamiento de un arreglo en memoria, tamaño, inicialización, etc. un aspecto muy importante en esta primera parte es el estudio de las cadenas de caracteres mismas que son arreglos de caracteres tal como ya se ha mencionado anteriormente, este tema es de suma importancia puesto que en la mayoría de programas se trabaja con datos de este tipo, igualmente se debe tener muy en cuenta la sección 3.4 en la cual se estudian los arreglos multidimensionales y concretamente los de dos dimensiones.

Bien, revisemos algunas características principales de un arreglo o vector el cual se define como una colección finita, homogénea y ordenada de elementos. Finita: Todo arreglo tiene un límite, debe determinarse cuál será el número máximo de elementos que podrán formar parte del arreglo.

Homogénea: Todos los elementos de un arreglo son del mismo tipo, todos son enteros, reales, booleanos, etc., pero nunca una combinación de distintos tipos.

Ordenada: Se puede determinar cuál es el primer elemento, el segundo, el tercero y el enésimo elemento.

En general cuando se declaran variables de tipo Array, estamos haciendo referencia a un gran conjunto de datos como por ejemplo: las edades de los alumnos en un curso, la cantidad de unidades vendidas cada día del mes, etc. Otro aspecto importante de mencionar en los arreglos es que se distinguen dos partes: los componentes o datos y los índices.

Los componentes son los elementos que forman el arreglo, es decir los valores que se almacenan en cada una de las casillas. Los índices especifican cuántos elementos tendrá el arreglo y además son el medio para acceder a la información de los componentes.

El arreglo de la Figura 2.1 tiene 6 elementos pero como se podrá dar cuenta el índice del último elemento es 5, esto se debe obviamente a que en el lenguaje “C” los arreglos se indexan desde 0. La anterior fue una representación grafica de los arreglos, a continuación repasaremos algunos puntos importantes relacionados con la implementación de estas estructuras en una aplicación en lenguaje “C”.

Declaración de un array

tipo nombreArray[numeroDeElementos];

Por ejemplo la siguiente instrucción crea un arreglo de 10 elementos de tipo entero:

int numeros[10];

Inicialización de un array

Existen dos maneras de inicializar los datos en un arreglo, la primera y menos práctica consiste en asignar datos a cada elemento del arreglo:

numeros[0] = 52;

numeros[1] = 45;

numeros[2] = 87;

La segunda consiste en asignar todos los valores a los elementos del arreglo al momento de su declaración, así por ejemplo:

int numeros[6] = {34, 76, 21, 84, 76, 98};

Cuando inicializamos un arreglo de esta manera no es necesario especificar el tamaño del mismo:

int numeros[] = {34, 76, 21, 84, 76, 98};

A continuación se presenta un programa en el cual se usa arreglos.

Ejercicio 2.1: Escribir un programa que invierta n números enteros de un arreglo.

Código:

Análisis:

Dado un arreglo de n elementos:

5	47	32	58	94	61	14	34

Invertir dichos elementos

37	14	61	94	58	32	47	5

Línea 2-8:	Estas líneas corresponden a la documentación del programa, es recomendable poner en el encabezado de cada programa alguna información relevante sobre el mismo
Línea 12:	Declaración del arreglo de enteros, máximo de 20 elementos.
Línea 17:	Se obtiene la cantidad de elementos que tendrá el arreglo.
Línea 18-21	En este proceso repetitivo se leen los valores de cada elemento del arreglo
Línea 23-28	Este proceso repetitivo se ejecuta hasta la mitad de elementos, el propósito es invertir los elementos de la primera mitad con los de la segunda mitad.

2.6. Cadenas de texto en C

Las cadenas de caracteres son de significativa importancia en cualquier lenguaje ya que estas nos permiten trabajar con información alfabética como nombres de personas, direcciones, etc. En el primer capitulo estudiamos los datos simples y particularmente los datos de tipo char, recordemos que un dato de tipo char puede ser una letra, un numero o un carácter especial; en el lenguaje C las cadenas de texto son simplemente arreglos de datos de tipo Char, mientras que en otros lenguajes como por ejemplo en Java existe el dato de tipo string explícitamente; como mencionaba anteriormente en C las cadenas de texto son arreglos de caracteres mismos que tienen una característica muy importante que es: los arreglos que son cadenas de texto deben terminar con un carácter nulo, es decir si un arreglo de caracteres no tiene dicho carácter este arreglo no será interpretado como string y por lo tanto no es posible aplicarle al mismo las funciones de manipulación de strings. En el lenguaje C existe la librería “string.h” misma que dispone de funciones para manipular la información de tipo string, se recomienda que el estudiante investigue las funciones que dispone la librería antes mencionada y realice ejercicios aplicando las mismas

Ejercicio 2.2: Escribir un programa que utilice funciones de la librería “string.h” para manipular cadenas de texto.

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: string.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11	#include <string.h>
12
13	char cadena0[100];
14
15	char cadena1[ ] = “Universidad”;
16	char cadena3[ ] = “ tecnica de “;
17	char* cadena4;
18	int i;
19
20	main( ) {
21	printf(“El contenido de la cadena1 es: %s\n\n”, cadena1);
22	printf(“El tamaño del arreglo cadena1 es: %d\n\n”,
23	sizeof(cadena1));
24	printf(“El tamaño de la cadena de texto es: %d\n\n”,
25	strlen(cadena1));
26	strcat(cadena1, cadena2);
27	printf(“El resultado de la concatenacion es: %s\n\n”,
28	cadena1);
29	cadena4 = strpbrk(cadena1, “L”);
30	strncpy(cadena0,cadena1,11);
31	strcat(cadena0, cadena3);
32	strcat(cadena0, cadena4);
33	for (i=0; i<strlen(cadena0); i++) {
34	cadena0[i] = toupper(cadena0[i]);
35	}
36	printf(“%s\n\n”,cadena0);
37	}

Resultados

Analisis Por ejemplo los datos almacenados en la variable cadena1 serian los siguientes:

U	n	i	v	e	r	s	i	f	d	a	d	\0

Línea 11:	En esta línea se ha incluido la librería necesaria para trabajar con funciones de tipo string
Línea 13-16	En estas líneas se declaran los arreglos de tipo char para almacenar las cadenas de texto
Línea 17:	En C una cadena también puede ser declarada como un puntero a char, en este caso las funciones de manipulación de string interpretan a un dato de este tipo hasta encontrar en primer carácter nulo.
Línea 22-25	En la primera línea se determina cuantos elementos tiene la estructura desde el punto de vista de un arreglo, como se podrá dar cuenta el valor retornado es 12, es decir uno mas del total de letras que tiene la cadena, esto se debe a que en el arreglo se toma en cuenta el carácter nulo que existe al final de todo string. En la segunda línea se utiliza las funciones de string, por lo tanto estas funciones no toman en cuenta el dato nulo como parte de una cadena de caracteres.
Línea 26-36	La función strcat se utiliza para concatenar cadenas, la función strpbrk divide un string en base a un carácter determinado, retorna el string que esta después de dicho carácter.

2.7. Operaciones con Arreglos

Bien una vez que hemos estudiado los aspectos fundamentales de los arreglos vamos a revisar algunos algoritmos para manipular los datos de estas estructuras, es importante que ponga especial atención a estos algoritmos ya que los mismos son la base para desarrollar y resolver aplicaciones específicas.

Adicionalmente a las operaciones de lectura y asignación de datos que ya se estudiaron en el ejercicio 2.1 existen otras operaciones fundamentales, estas son: Inserción, Modificación, Eliminación, Ordenación, Búsqueda. La lógica para resolver las operaciones citadas anteriormente puede cambiar dependiendo de que si el arreglo en cuestión esta o no ordenado, en función de esto estudiaremos las operaciones con arreglos desde dos perspectivas.

2.7.1 Operaciones con arreglos desordenados

Estudiaremos en primera instancia los arreglos desordenados, pues estos representan mayores ventajas puesto que son más fáciles de comprender lo cual es muy importante para comprender mejor los algoritmos para trabajar con esta estructura.

Inserción (Arreglos desordenados).

La inserción de nuevos elementos en un arreglo desordenado generalmente se lo hace al final del mismo, pero dependiendo de las características del problema esta inserción puede realizarse al inicio del mismo, también se puede pedir que la inserción se realice en una posición especifica para lo cual se debe verificar que el arreglo este lleno hasta dicha posición, o también es posible que la inserción deba realizarse antes o después de un elemento que tiene un valor especifico para lo cual igualmente se debe verificar que dicho elemento exista en el arreglo; en definitiva creo que las posibilidades son muchas y todo depende de la naturaleza del problema; una buena practica para entender mejor estos algoritmos puede ser que el estudiante desarrolle programas que satisfagan las posibilidades de inserción citadas anteriormente y otras mas que pueda imaginar. A continuación desarrollaremos el programa para insertar elementos al final de un arreglo.

Ejercicio 2.4: Escribir un programa que inserte un elemento al final de un arreglo desordenado Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: insertaDesordenado.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	int arreglo[ ] = {24, 18, 26, 51, 47};
13	int i, n, elemento;;
14
15	main( ) {
16	n = sizeof(arreglo)/sizeof(int);
17	printf(“Los elementos del arreglo son: \n”);
18	for(i=0; i<n; i++) {
19	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
20	}
21	printf(“\nIngrese un valor: “);
22	scanf(“%d”,&elemento);
23	insertaDesordenado();;
24	printf(“\nLos nuevos elementos del arreglo son: \n”);
25	for(i=0; i<n; i++) {
26	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
27	}
28	system(“PAUSE”);
29	}
30
31	void insertaDesordenado( ) {
32	arreglo[n] = elemento;
33	n = n + 1;
34	};

Resultado:

Análisis:

Línea 22-33	El método “insertaDesordenado” inserta el valor correspondiente al final del arreglo e incrementa el tamaño del mismo.
( … )	Es importante destacar el uso de variables globales en este programa, como se podrá dar cuenta no utilizamos parámetros en la llamada al procedimiento “insertaDesordenado”, los cambios se efectúan directamente en las variables globales.

Búsqueda (Arreglos desordenados). Antes de estudiar los algoritmos de “Modificación” y de “Eliminación” revisemos como realizar búsquedas de elementos en arreglos desordenados, es evidente que para modificar el valor de un elemento o para eliminarlo, primero es necesario buscarlo. Los algoritmos de búsqueda básicamente pueden ser de dos tipos:

Búsqueda secuencial
Búsqueda binaria (solo en arreglos ordenados)

En esta sección implementaremos la primera lógica (Búsqueda secuencial) para dejar la búsqueda binaria cuando estudiemos los arreglos ordenados. Si bien es cierto la búsqueda secuencial es la mas sencilla de comprender e implementar pero resulta ineficiente cuando se tiene gran cantidad de datos por el tiempo que necesita para realizar una operación de búsqueda; en la pagina 194 se muestra un análisis de rendimiento de estos algoritmos.

Ejercicio 2.3: Escribir un programa que busque un dato en un arreglo por el método secuencial.

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: busquedaSecuencial.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	int arreglo[ ] = { 24, 18, 26, 51, 47, 92, 14, 36, 52, 487, 523, 64, 78, 146 };
13	int i, n, indice, elemento;
14
15
16	&main( ) {
17	n = sizeof(arreglo)/sizeof(int);
18	printf(“Los elementos del arreglo son: \n”);
19	for(i=0; i<n; i++) {
20	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
21	}
22	printf(“\n\nIngrese un valor: “);
23	scanf(“%d”,&elemento);
24	indice = busquedaSecuencial(arreglo, n, elemento);
25	if (indice == -1)
26	printf(“\nEl numero %d no pertenece al arreglo\n\n”, elemento);
27	}
28	else
29	printf(“\nEl numero %d se encuentra en la posicion %d \n\n”, elemento, indice);
30
31
32	& system(“PAUSE”);
33	}
34
35	int busquedaSecuencial(int a[], int numElementos, int valor) {
36	int x = -1;
37	for(i=0; i<numElementos; i++) {
38	if (a[i] == valor) {
39	x = i;
40	i = numElementos;
41	}
42	}
43	return x;
44	}
45

Análisis:

Línea 12-13	Cuando se declara el arreglo, también se inicializan los valores en el mismo, esto se lo hace para dar mayores facilidades para probar el programa y no estar ingresando la información para cada corrida.
Línea 17	En “n” se obtiene el número total de elementos, esto se lo hace dividiendo el número total de bytes del arreglo para la cantidad de bytes que almacenan los datos de tipo int (puesto que el arreglo es de tipo int).
Línea 24	El método “busquedaSecuencial” recibe como parámetros: el arreglo, la cantidad de elementos, y el valor a buscar
Línea 25-30	Si el numero buscado no pertenece al arreglo el método devuelve el valor -1
Línea 38-43	Este proceso repetitivo busca secuencialmente el valor, si no existe una coincidencia entre el valor buscado y cada elemento, se retorna el valor inicializado en “x” que es -1

Modificación (Arreglos desordenados).

Modificar un elemento significa reemplazar el valor existente por un nuevo dato, este proceso consiste inicialmente en buscar el elemento, para lo cual se puede utilizar la función de búsqueda (busquedaSecuencial) previamente desarrollada. Tal como se comento en la inserción de elementos las posibilidades pueden ser varias por ejemplo en el caso de la modificación se pude requerir modificar el elemento que se encuentre en un índice determinado, es decir modificar en función del índice y no de un valor concreto.

Ejercicio 2.5: Escribir un programa que modifique el valor de un elemento dado.

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: modificaDesordenado.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	iint arreglo[] = {24, 18, 26, 51, 47, 92};
13	iint n, i, indice, elementoAnterior, elementoNuevo;
14
15	main( ) {
16	n = sizeof(arreglo)/sizeof(int);
17	printf(“Los elementos del arreglo son: \n”);
18	for(i=0; i<n; i++) {
19	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
20	}
21	printf(“\nIngrese un elemento para reemplazar: “);
22	scanf(“%d”,&elementoAnterior);
23	indice = busquedaSecuencial(arreglo, n, elementoAnterior);
24	if (indice == -1)
25	printf(“\nEl numero %d no pertenece al arreglo\n\n”,
26
27	else {
28	printf(“\nIngrese el nuevo elemento: “);
29	& scanf(“%d”,&elementoNuevo);
30	& arreglo[indice] = elementoNuevo ;
31	& printf(“\nLos nuevos elementos del arreglo son: \n”);
32	& for(i=0; i<n; i++) {
33	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
34	nbsp; nbsp; }
35	nbsp; }
36	system("PAUSE");
37	}

Línea 23	En este programa se utiliza el método de “busquedaSecuencial” para determinar si es posible modificar el elemento dado
Línea 28-37	Si la operación de búsqueda es exitosa se procede a obtener el nuevo valor y se asigna al índice del elemento encontrado.

Eliminación (Arreglos desordenados). El proceso de eliminación igualmente necesita del proceso de búsqueda, inicialmente consiste en buscar el dato a eliminar y posteriormente mover el numero que esta a la derecha para ocupar el espacio del numero que se elimino, este proceso se repite para todos los elementos del arreglo que se encuentran a la derecha del elemento eliminado, finalmente se debe tener en cuenta la actualización de la variable que contiene el numero de elementos que quedan en el arreglo.

Ejercicio 2.6: Escribir un programa que elimine un elemento de un arreglo dado.

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: eliminaDesordenado.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	iint arreglo[] = {24, 18, 26, 51, 47, 92};
13	int n, i, indice, elemento;
14
15	main( ) {
16	n = sizeof(arreglo)/sizeof(int);
17	printf(“Los elementos del arreglo son: \n”);
18	for(i=0; i<n; i++) {
19	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
20	}
21	printf(“\nIngrese un elemento para eliminar: “);
22	scanf(“%d”,&elemento);
23	indice = busquedaSecuencial(arreglo, n, elemento);
24	if (indice == -1)
25	printf(“\nEl numero %d no pertenece al arreglo\n\n”, elemento);
26
27	else {
28	eliminaDesordenado();
29	& printf(“\nLos elementos del arreglo son: \n”);
30	& for(i=0; i<n; i++)
31	& printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
32	& }
33	system(“PAUSE”);
34	}
35	nbsp;
36	&void eliminaDesordenado( ) {
37	int j;
38	for(j=indice; j<n; j++) {
39	arreglo[j] = arreglo[j+1];
40	}
41	n = n-1;
37	}

Resultado:

Análisis:

Línea 28-32	Si la operación de búsqueda del elemento a eliminar es exitosa, se ejecuta el método de eliminación
Línea 38-41	La eliminación consiste en mover los elementos una posición a la izquierda a partir del índice del elemento encontrado y posteriormente disminuir el tamaño del arreglo..

1.3.1. Operaciones con arreglos ordenados

Una vez estudiadas las operaciones que se pueden realizar en arreglos desordenados estudiaremos los arreglos ordenados, para lo cual primero se debe tener en cuanta los algoritmos de ordenación.

Ordenación. Ordenar un arreglo significa disponer los elementos de forma ascendente o descendente es decir colocar los elementos de menor valor al inicio y los de mayor valor al final o viceversa.

Tal como dice el libro en la página 167 existen algunos métodos de ordenación los cuales son muy importantes revisarlos y sobre todo entender cual es la lógica que utiliza cada método. Se recomienda que el estudiante se centre principalmente en el estudio de los siguientes métodos:

Ordenación por intercambio
Ordenación por selección
Ordenación por inserción
Ordenación por burbuja
Ordenación SHELL
Ordenación rápida (ó QUICKSORT)

El último método utiliza recursividad como metodología de programación.

Ejercicio 2.2: Escribir un programa que ordene los elemento de un arreglo por el método de “Inserción”

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: ordenacionPorInsercion.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	int arreglo[] = {24, 18, 26, 51, 47, 92};
13	int i, j, n, aux;
14
15	main( ) {
16	printf(“Ingrese la cantidad de numeros del arreglo: “);
17	scanf(“%d”, &n);
18	for(i=0; i<n; i++) {
19	printf(“Elemento [%d]: “, i);
20	scanf(“%d”, &arreglo[i]);
21	}
22
23	for(i=1; i<n; i++) {
24	j = i;
25	& aux = arreglo[i];
26	while(j>0 && aux<arreglo[j-1]) {
27	arreglo[j] = arreglo[j-1];
28	j=j-1;
29	& }
30	& arreglo[j] = aux;
31	& }
32	& }
33	printf(“\n\nLos elementos ordenados del arreglo son: \n”);
34	for(i=0; i<n; i++) {
35	nbsp; printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
36	}
37	system(“PAUSE”);
38	}
39

Resultado:

Análisis:

( … )	El análisis correspondiente a este programa esta en la pagina 173 del libro, favor revisarlo para obtener una mejor comprensión del mismo.

Inserción (Arreglos ordenados). La inserción de nuevos elementos en un arreglo ordenado debe realizarse exactamente en el lugar que le corresponde de acuerdo al orden del mismo, a diferencia de los arreglos desordenados en el cual se podía hacer al inicio, final o en cualquier posición.

Ejercicio 2.7: Escribir un programa que inserte un elemento de un arreglo ordenado.

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: insertaOrdenado.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	int arreglo[] = {24, 18, 26, 51, 47, 92};
13	int n, i, elemento;
14
15	main( ) {
16	n = sizeof(arreglo)/sizeof(int);
17	printf(“Los elementos del arreglo son: \n”);
18	for(i=0; i<n; i++) {
19	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
20	}
21	printf(“\nIngrese un elemento para insertar: “);
22	scanf(“%d”, &elemento);
23	insertaOrdenado(arreglo, n, elemento);
24	printf(“\nLos elementos del arreglo son: \n”);
25	& for(i=0; i<n; i++) {
26	printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
27	}
28	system(“PAUSE”);
29	}
30	&
31	&void insertaOrdenado( ) {
32	int j,pos = 0;
33	while((arreglo[pos] < elemento) && (pos < n))
34	pos = pos + 1;
35	n = n + 1;
36	for(j=n; j>pos; j--)
37	arreglo[j] = arreglo[j-1];
38	}
39	}

Resultado:

Análisis:

Línea 33-34	Para insertar un elemento en un arreglo ordenado primero se debe encontrar la posición correcta (“pos”).
Línea 36-37	Luego se mueven los elemento una posición a la derecha a partir del índice (“pos”) respectivo
Línea 38	Finalmente se inserta el elemento en la posición correspondiente

Búsqueda (Arreglos ordenados) Anteriormente habíamos comentado que existen dos algoritmos de búsqueda el secuencial (que ya lo implementamos anteriormente) y la búsqueda binaria la misma que se aplica en arreglos ordenados, esta ultima tiene una gran ventaja en cuanto al tiempo que necesita para buscar un elemento en la lista o arreglo, este tiempo es muy corto puesto que utiliza la ventaja de tener ordenado el arreglo y no tiene que recorrer todo el arreglo desde el principio para encontrar un elemento; la codificación de este algoritmo conjuntamente con su análisis se encuentra implementado en las paginas 190-194 del libro por lo tanto se recomienda que el estudiante lo revise y entienda para que el mismo sea aplicado en otras aplicaciones.

Modificación (Arreglos ordenados). La modificación de elementos en un arreglo ordenado debe tratársela con mucha atención ya que puede ocurrir que al modificar un elemento se pierda el orden preestablecido; en este caso se recomienda aplicar el algoritmo para eliminar el elemento que se quiere modificar y posteriormente aplicar el algoritmo para insertar el nuevo valor (insertaOrdenado) de esta manera se obtendrá un arreglo igualmente ordenado y aplicada la modificación respectiva.

Eliminación (Arreglos ordenados). La eliminación de elementos en arreglos ordenados es igual que la implementada anteriormente para arreglos desordenados, puesto que en la eliminación el orden del mismo no importa; la única diferencia puede residir en el método de búsqueda utilizado en la eliminación, anteriormente en el caso de los arreglos desordenados utilizamos el algoritmo de búsqueda secuencial (busquedaSecuencial), pero en el caso que estamos estudiando (arreglos ordenados) se puede implementar la búsqueda binaria misma que representa mayores ventajas para los arreglos ordenados tal como se ha comentado anteriormente.

2.8. Arreglos de dos dimensiones

Luego de revisar los arreglos de una dimensión con las operaciones que se puede aplicar sobre estos ya podemos estudiar los arreglos de dos dimensiones o matrices, la lógica de los programas que se aplican a las matrices no difiere en mucho con las estudiadas previamente, en este caso se debe tener en cuenta que se aumenta un índice mas y en consecuencia para recorrer la matriz se utilizan dos procesos repetitivos.

Los arreglos bidimensionales también conocidos como tablas o matrices requieren de dos índices para acceder a sus elementos, el primer índice hace referencia a las filas y el segundo hace referencia a las

Declaración de una matriz

tipo nombreMatriz[numeroDeFilas][numeroDeColumnas];

Por ejemplo la siguiente instrucción crea una matriz de Filas y 10 Columnas de tipo entero:

int numeros[10][10];

Inicialización de datos en una matriz

Existen dos maneras de inicializar los datos en un arreglo, la primera y menos práctica consiste en asignar datos a cada elemento del arreglo:

numeros[0][0] = 52;

numeros[0][1] = 45;

numeros[0][2] = 87;

....

La segunda consiste en asignar todos los valores a los elementos de la matriz al momento de su declaración, así por ejemplo:

int numeros[5][5] = {

{25,45,78,62,14},

{35,41,87,52,19},

{65,48,73,21,49},

{21,85,94,13,25},

{25,36,17,54,93} };

Cuando se desarrollan aplicaciones con matrices es importante rescatar el hecho que para el ingreso de datos se necesitan dos estructuras repetitivas, una para las filas y otra para las columnas.

A continuación se presenta un programa en el cual se utiliza un arreglo de dos dimensiones como estructura de datos, así mismo se recomienda que el estudiante desarrolle programas para manipular los datos en este tipo de estructuras como por ejemplo: eliminar, modificar, insertar, buscar elementos.

Ejercicio 2.8: Escribir un programa que lea los elementos de una matriz y posteriormente encuentre lo siguiente:

* El elemento mayor con su índice.

* El elemento menor con su índice.

* La sumatoria de los elementos que están sobre la diagonal secundaria.

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: ordenacionPorInsercion.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	int arreglo[] = {24, 18, 26, 51, 47, 92};
13	int i, j, n, aux;
14
15	main( ) {
16	printf(“Ingrese la cantidad de numeros del arreglo: “);
17	scanf(“%d”, &n);
18	for(i=0; i<n; i++) {
19	printf(“Elemento [%d]: “, i);
20	scanf(“%d”, &arreglo[i]);
21	}
22
23	for(i=1; i<n; i++) {
24	j = i;
25	& aux = arreglo[i];
26	while(j>0 && aux<arreglo[j-1]) {
27	arreglo[j] = arreglo[j-1];
28	j=j-1;
29	& }
30	& arreglo[j] = aux;
31	& }
32	& }
33	printf(“\n\nLos elementos ordenados del arreglo son: \n”);
34	for(i=0; i<n; i++) {
35	nbsp; printf(“Elemento [%d]: %d\n”, i, arreglo[i]);
36	}
37	system(“PAUSE”);
38	}
39

Resultado:

Análisis:

( … )	El análisis correspondiente a este programa esta en la pagina 173 del libro, favor revisarlo para obtener una mejor comprensión del mismo.

Ejercicio 2.7: Escribir un programa que inserte un elemento de un arreglo ordenado.

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: Matriz.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	int numeros[10][10];
13	int i,j,n,iMayor,jMayor,iMenor,jMenor,ds,mayor,menor,s;
14
15	main( ) {
16	printf(“Ingrese la dimension de la matriz: “);
17	scanf(“%d”, &n);
18	for(i=0; i<n; i++) {
19	for(j=0; j<n; j++) {
20	printf(“Elemento [%d][%d]: “,i,j);
21	scanf(“%d”, &numeros[i][j]);
22	}
23	}
24	mayor = numeros[0][0];
25	menor = numeros[0][0];
26	for(i=0; i<n; i++) {
27	for(j=0; j<n; j++) {
28	if (numeros[i][j] > mayor) {
29	mayor = numeros[i][j];
30	iMayor = i;
31	jMayor = j;
32	}
33	if (numeros[i][j] < menor) {
34	menor = numeros[i][j];
35	iMenor = i;
36	jMenor = j;
37	}
38	}
39	}
40	ds = n;
41	s = 0;
42	for(i=0; i<n; i++) {
43	ds = ds-1;
44	for(j=0; j<ds; j++) {
45	s = s + numeros[i][j];
46	}
47	&nbsp ;};
48	printf(“\n\nElemento mayor es: %d y se encuentra en [%d][%d]”, mayor, iMayor, jMayor);
49	s = 0;
50	printf(“\n\nElemento menor es: %d y se encuentra en [%d][%d]”, menor, iMenor, jMenor);
51	printf(“\n\nLa sumatoria es : %d\n\n”, s);
52	system(“PAUSE”);
53	}

Resultado:

Análisis:

Dada una matriz:

25	14	3	18
41	6	- 20	47
22	14	65	74
85	21	3	7

Encontrar el elemento de mayor valor, menor valor y la sumatoria de los que están sobre la diagonal secundaria.

Líneas 2-8:	Para cargar datos en una matriz es necesario dos procesos repetitivos (filas y columnas)
Línea 24-25	Se asume que el elemento de mayor y menor valor es el primer elemento.
Línea 26-39	Luego se recorre nuevamente toda la matriz y por cada elemento se va comparando si es mayor o menor que el dato almacenado en las variables respectivas, adicionalmente se registran los índices correspondientes.
Línea 40-47	Para la sumatoria se recorre nuevamente el arreglo, pero en este caso se utiliza una variable “ds”(diagonal secundaria) la misma que se va disminuyendo por cada fila para obtener así la diagonal secundaria.

Capitulo3: ESTRUCTURAS DINÁMINAS: APUNTADORES

Datos Generales:

Texto Base	A GUILAR LUIS JOYAOYANES, Zahonero Martínez Ignacio, Algoritmos y Estructuras de Datos. Una perspectiva en C, McGraw-Hill, Madrid-España, 2004.
Capítulo	3. Estructuras dinámicas: Apuntadores
Sección	Los temas estudiados en este capitulo deber ser ampliados para lo cual se presentan algunos links en Internet mismos que pueden ser revisados por el estudiante, adicionalmente en el libro básico existen algunas explicaciones en el apéndice B, en la sección B.20
Horas de estudio empleadas para el desarrollo del contenido	6 horas

Introducción:

En el siguiente bimestre estudiaremos otro tipo de estructuras de datos mismas que presentan una gran ventaja en cuanto se refiere a la flexibilidad de uso, si bien es cierto el uso de arreglos nos ayuda mucho en el desarrollo de aplicaciones estos presentan la desventaja que se podría reservar mas memoria de la que se necesita o que en algún momento nos falte mas memoria de la reservada. Para el estudio de esas nuevas estructuras de programación es necesario conocer y entender el uso de punteros los cuales nos permiten reservar memoria durante la ejecución del programa, este tema debe estar completamente claro para iniciar el próximo bimestre con el estudio de las listas enlazadas.

Objetivos:

Estudiar y comprender el funcionamiento de las estructuras de datos dinámicas
Aplicar los conocimientos adquiridos sobre punteros en programas sencillos

Conceptos Claves:

Puntero. Es un tipo de dato simple, es decir almacena un solo valor de tipo hexadecimal, este valor corresponde a una direccion de memoria en la cual se encuentra un determinado dato el cual puede ser de tipo entero, real o una estructura completa (para el caso de las listas).
Dirección de memoria.- Es un valor hexadecimal que corresponde a una dirección física de memoria.
Operador & .- Este operador se utiliza para obtener la direccion de memoria en la cual se encuentra almacenada una variable determinada.
Operador * .- Dada una dirección de memoria este operado se utiliza para obtener el valor allí almacenado.

Esquema de Estudio:

Tema a revisar	Descripción del Contenido a revisar	Actividades Recomendadas	Planificación Personal del estudio (fecha)	¿Requiero Tutorial?	Anotaciones
* 3.1 Apuntadores 3.2 Estructuras de datos dinámicas	Se explican los conceptos relacionados con punteros, igualmente las estructuras de datos dinámicas que crecen dinámicamente mientras se ejecuta la aplicación.
3.3 Declaración de punteros	Se explica el uso del operador & y *, adicionalmente se expone un sencillo programa que usa punteros	Se recomienda codificar y ejecutar el programa que esta en la guía y adicionalmente incrementar mas variable para comprender el tema

3.1 Apuntadores

Hasta ahora, hemos estudiado los datos mediante estructuras estáticas, es decir, que ocupan un valor fijo en memoria en el momento de compilación. A continuación, estudiaremos estructuras de datos dinámicas las mismas que se crean dinámicamente en el momento de la ejecución del programa, esto se logra mediante el uso de punteros.

Un puntero es un tipo de dato simple que contiene la dirección de una variable o estructura en vez de un valor de dato.

Tengamos presente que los datos se almacenan en la memoria RAM en posiciones especificas, a las mismas que se acceden mediante valores hexadecimales.

Los punteros tienen dos propósitos principales:

* Hacer los programas más eficientes

* Construir estructuras muy complejas

3.2 Estructuras de Datos dinámicas

Las estructuras de datos dinámicas son una colección de elementos denominados nodos, en contraste a un arreglo que siempre contiene almacenamiento para un número fijo de elementos.

Los punteros (apuntadores) permiten la creación de estructuras de datos dinámicas las mismas que tienen la capacidad de variar en tamaño y ocupar tanta memoria como utilicen realmente.

Las variables que se crean y destruyen durante la ejecución se llaman variables dinámicas. Así, durante la ejecución de un programa, puede haber una posición de memoria específica asociada con una variable dinámica y posteriormente puede no existir ninguna posición de memoria asociada con ella.

Al contrario que las estructuras de datos estáticas, tales como arreglos cuyos tamaños y posiciones de memoria se fijan en tiempo de compilación, las estructuras de datos dinámicas se expanden o contraen a medida que se requiera durante la ejecución y cambia sus posiciones de memoria asociada.

Una variable tipo puntero contiene la dirección de la posición de otra variable.

3.3 Declaración de punteros

Es preciso diferenciar entre las dos entidades implicadas en el apuntamiento:

* La variable puntero (Quién hace el apuntamiento) y

* La variable apuntada (a quién se apunta)

Un tipo de dato puntero se especifica (en lenguaje C) utilizando el símbolo “*” seguido por un identificador de tipo. Su formato es:

tipoIdentificador

Es importante indicar que en otros lenguajes como por ejemplo Pascal se utiliza el signo de circunflejo “^” para declarar punteros.

En general, se pueden declarar variables puntero que apunten a cualquier tipo dato, incluso otros punteros.

A continuación se presenta un ejemplo de declaración y uso de punteros en “C”.

Ejercicio 4.1: Escribir un programa que presente el valor y la dirección en memoria de una variable en “C”:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: punteros.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	main( ) {
13	int numero;
14	int *punt
15	numero = 43;
16	punt = &numero;
17	printf( “\nValor de la variable numero: %i \n\n”, numero );
18
19	p align="left"> printf( “\nDireccion de la variable numero: %p \n\n”, punt);</p>
20
21	System("PAUSE");
22	}

Resultados

Analisis

Línea 13-14	Se declaran una variable de tipo “int” y otra de tipo puntero respectivamente.
Líneas 16	Se asigna la dirección de la variable número a la de tipo puntero “punt”.
Línea 17-19	Se presenta el valor de la variable y de su posición en memoria.
(.......)	Con este ejemplo debe quedar claro que las variables de tipo puntero apuntan a la dirección de otra variable, adicionalmente hemos visto el uso de otro operador: “&” el mismo que extrae la dirección en la que se encuentra una variable en memoria.

Capitulo4: Estructuras Dinámicas Lineales: Listas enlazadas

Datos Generales:

Texto Base	A GUILAR LUIS JOYAOYANES, Zahonero Martínez Ignacio, Algoritmos y Estructuras de Datos. Una perspectiva en C, McGraw-Hill, Madrid-España, 2004.
Capítulo	4. Listas enlazadas
Sección	9.1; 9.2; 9.4; 9.5; 9.6; 9.7; 9.8; 9.9; 9.10
Horas de estudio empleadas para el desarrollo del contenido	3 horas

Introducción:

Avanzando con nuestro estudio, en este capítulo estudiaremos las estructuras dinámicas, que son representadas con la utilización de punteros aplicados a la manipulación y procesamiento de listas enlazadas, pilas y colas. El estudio de este capítulo es de vital importancia, puesto que servirá de base para la solución de cualquier tipo de problema computacional aplicado a la realidad cotidiana, que amerite la utilización de este tipo de estructuras de datos. Revise en el libro básico los capítulos relacionados con el tema, y así mismo le recomiendo revisar y estudiar detenidamente cada uno de los ejemplos desarrollados

Objetivos:

Explicar las estructuras de listas enlazadas y desarrollar algoritmos de aplicación para cada una de las operaciones básicas que se realizan sobre las listas.
Desarrollar ejemplos de aplicación a través de algoritmos utilizando punteros aplicados a las listas enlazadas

Conceptos Claves:

Nodo. Es una estructura(registro) que como mínimo contiene dos campos uno para almacenar la información y otro para almacenar la dirección de memoria del siguiente nodo o estructura.
Lista enlazada.- Es una lista de nodos que se encuentran almacenados secuencialmente en lazados a través del campo tipo puntero.
Campo de enlace.- Es un campo del nodo de la lista enlazada que almacena la dirección de memoria del siguiente nodo.

Esquema de Estudio:

Tema a revisar	Descripción del Contenido a revisar	Actividades Recomendadas
4.1 Lista enlazadas 4.2 Clasificación de las listas enlazadas	Se presenta todo el marco teórico relacionado con las listas enlazadas y su clasificación
4.3 Operaciones con listas enlazadas	Se exponen los programas necesarios para manipular la información (nodos) de analista enlazada	Se recomienda que el estudiante analice los programas planteados y adicionalmente realice otros programas adicionales: insertar en nuevo nodo antes de un elemento dado, insertar elemento al inicio y fin de la lista, etc
4.5 Operaciones con listas doblemente en lazadas	Se exponen los programas para administrar los datos en esta estructura	Se recomienda que el estudiante igualmente analice estos programas y desarrolle los programas de la sección 4.3 utilizando las listas doblemente enlazadas

4.1 Listas enlazadas

Una vez estudiados los arreglos nos podremos dar cuenta de la grandes ventajas que ofrecen estos para el desarrollo de aplicaciones avanzadas, a pesar que estas estructuras presentan algunas desventajas; por ejemplo: el uso de arreglos obliga a reservar por adelantado el espacio de memoria que se desea utilizar, de modo que si se desea insertar un nuevo elemento que exceda el tamaño predefinido del array, no es posible realizar dicha operación sin que se produzca un error en tiempo de ejecución. Ello se debe a que los arrays hacen un uso ineficiente de la memoria, por otra parte se debe tener en cuenta que las necesidades de aplicaciones cada vez son mas exigentes las cuales requieren entre otras necesidades almacenar mas información y optimizar la memoria del equipo; es en este punto cuando se hace necesario la aplicación de nuevas estructuras, en este caso gracias a la asignación dinámica de memoria, se pueden implementar listas de modo que la memoria física utilizada se corresponda con el número de elementos de la estructura . Para ello se recurre a los punteros (apuntadores) que hacen un uso más eficiente de la memoria como ya se ha visto con anterioridad.

Una lista enlazada es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un “enlace” o “puntero”. La idea básica consiste en construir una lista cuyos elementos llamados nodos se componen de dos partes o campos: la primera parte o campo contiene la información y es, por consiguiente, un valor de un tipo genérico (denominado Datos, TipoElemento, Información, etc.) y la segunda parte o campo es un puntero (denominado enlace o siguiente) que apunta al siguiente elemento de la lista.

Gráficamente una lista puede ser representada por una caja (un rectángulo) con dos secciones en su interior. En la primera sección se escribe el elemento o valor del dato y en la segunda sección, el enlace o puntero mediante una flecha que sale de la caja y apunta al nodo siguiente, como se podrá dar cuenta para insertar un nuevo elemento simplemente es necesario crear un nuevo nodo con la nueva información y hacer los enlaces adecuado puesto que los nodos no deben quedar sueltos.

Una lista enlazada consta de un número de elementos y cada elemento tiene dos componentes (campos), un puntero al siguiente elemento de la lista y un valor, que puede ser de cualquier tipo.

4.2 Clasificación de las Listas Enlazadas

La estructura básica de una lista enlazada no cambia, es decir una lista enlazada tiene como mínimo un campo para el dato(información) y otro campo para realizar el enlace a otros nodos, la clasificación que se presenta a continuación esta orientada a brindar ventajas funcionales:

Listas simplemente enlazadas. Cada nodo (elemento) contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos (“adelante”).
Listas doblemente enlazadas. Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo (“Siguiente”) como en recorrido inverso (“Anterior”).
Lista circular simplemente enlazada. Una lista enlazada simplemente en la que el último elemento (cola) se enlaza al primer elemento (cabeza) e tal modo que la lista puede ser recorrida de modo circular (“en anillo”)

[[Imagen:<center>]]

Lista circular doblemente enlazada. Una lista doblemente enlazada en la que el último elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo circular (en anillo) tanto en dirección directa (“Siguiente”) como inversa (“Anterior”).

Por cada uno de estos cuatro tipos de estructuras de listas, se puede elegir una implementación basada en arrays o una implementación basada en punteros. Como ya se ha comentado estas implementaciones difieren en el modo en que asigna la memoria para los datos de los elementos, cómo se enlazan juntos los elementos y cómo se accede a dichos elementos. De forma más específica, las implementaciones pueden hacerse con cualquiera de éstas:

* Asignación fija, o estática, de memoria mediante array.

* Asignación dinámica de memoria mediante punteros.

Dado que la asignación fija de memoria mediante arrays es más ineficiente, utilizaremos en este capítulo la asignación de memoria mediante punteros. 4.3 Operaciones con Listas Enlazadas

En las Listas Enlazadas al igual que en los arreglos se aplican algunas operaciones que manipulan dicha información:

Crear la lista
Recorrido de la lista
Buscar elementos
Insertar elementos
Eliminar elementos
Modificar el valor de un elemento

En esta sección se presentan programas demostrativos que efectúan estas operaciones.

Creación. Lo primero que se debe hacer para trabajar con Listas es naturalmente crear o inicializar dicha estructura, tan como se ha mencionado anteriormente utilizaremos los punteros como estructuras de datos.

Ejercicio 4.2: Escribir un programa para crear una lista enlazada, los datos deben ser ingresados por teclado hasta que

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: creaLista.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	struct Elemento {
13	int informacion;
14	struct Elemento *Siguiente;
15	};
16	typedef struct Elemento Nodo;
17
18	main( ) {
19	Nodo *pCabeza = NULL;
20	Nodo *p = NULL;
21	Nodo *r = NULL;
22	int dato;
23
24	pCabeza = (Nodo*)malloc(sizeof(Nodo));
25	p = pCabeza;
26	do {
27	printf(“Ingrese la informacion del nodo: “);
28	scanf(“%d”, &dato);
29	if (dato != -1) {
30	r = (Nodo*)malloc(sizeof(Nodo));
31	r->informacion = dato;
32	r->Siguiente = NULL;
33	p->Siguiente = r;
34	p = r;
35	}
36	} while(dato != -1);
37	printf(“\n\n”)
38	presentar(pCabeza);
39	printf(“\n\n”);
40	system(“PAUSE”);
41	}
42
43	presentar(Nodo *cab){
44	Nodo *p = NULL;
45	Nodo *r = NULL;
46	p = cab;
47	do {
48	r = p->Siguiente;
49	printf(“%d, “, r->informacion);
50	p = p->Siguiente;
51	} while(p->Siguiente != NULL);
52	}

Resultados

Analisis

Línea 12-15	Definición del nodo que utilizaremos para las listas como una estructura, ya que este debe tener dos campos.
Línea 16	Definición de la estructura “Elemento” como un nuevo tipo de dato “Nodo”
Línea 19-21	Inicialización a nulo de los punteros
Línea 24	Crear el nodo o puntero para la cabeza de la lista
Línea 26-36	Ingresar la información a la lista, este proceso se repite hasta que el usuario ingrese un -1. En la línea 30 se crea cada nodo nuevo, posteriormente se le carga la información y se hace que el campo “Siguiente” no apunte a nada (Fin de la lista), adicionalmente es muy importante enlazar el campo “Siguiente”
Línea 47-51	Para presentar los datos de la lista simplemente se recorre la misma hasta que un elemento apunte a nulo, en este caso recordemos que el ultimo elemento no apuntara a nada, igualmente el método “presentar” recibe como parámetro el nodo de cabecera

Recorrido.

La operación de recorrido consiste en visitar cada uno de los nodos que forman la lista. La visita de un nodo puede definirse por medio de una operación muy simple, o por medio de operaciones tan complejas como desee.

Para recorrer todos los nodos de una lista se comienza con el primero. Tomando el valor del campo “Siguiente” de éste se avanza al segundo; a su vez, el campo “Siguiente” del segundo nos dará acceso al tercero, y así sucesivamente. En general la dirección de un nodo, excepto el primero, está dada por el campo “Siguiente” de su predecesor.

En el ejercicio anterior (4.2) para crear una lista, también se ha implementado un procedimiento para “Recorrido” de una lista (“presentar”).

Búsqueda. La operación de búsqueda de un elemento en una lista se realiza de modo secuencial. Se deben recorrer los nodos, tomando el campo “Siguiente” como puntero al siguiente nodo a visitar. Debido a esto puede decirse que esta operación está implícita en algunos de los casos de inserción y borrado.

En el caso del programa que se presenta a continuación el método de búsqueda devuelve un dato de tipo puntero al elemento buscado, si la operación de búsqueda ha sido exitosa, en caso contrario se devuelve un valor nulo (“NULL”).

Ejercicio 4.3: Escribir un programa que busque el nodo de un elemento dado en una Lista Encadenada:

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: buscaLista.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	struct Elemento {
13	int informacion;
14	struct Elemento *Siguiente;
15	};
16	typedef struct Elemento Nodo;
17
18	Nodo buscaLista(Nodo cab, int x);
19
20	main( ) {
21	Nodo *pCabeza = NULL;
22	iNodo *p = NULL;
23	Nodo *r = NULL;
24	pint dato;
25
26	pCabeza = (Nodo*)malloc(sizeof(Nodo));
27	p = pCabeza;
28	do {
29	printf(“Ingrese la informacion del nodo: “);
30	scanf(“%d”, &dato);
31	if (dato != -1) {
32	r = (Nodo*)malloc(sizeof(Nodo));
33	r->informacion = dato;
34	r->Siguiente = NULL;
35	p->Siguiente = r;
36	<palign="left"> p = r;</p>
37	&nbsp}
38	} while(dato != -1);
39	printf(“\n\n”);
40	presentar(pCabeza);
41	printf(“\n\n”);
42	Nodo *Indice;
43	printf(“Ingrese un dato para buscar en la lista:“);
44	scanf(“%d”, &dato);
45	Indice = buscaLista(pCabeza, dato);
46	if (Indice == NULL)
47	printf(“\nEl elemento NO existe en la lista.\n\n”);
48
49	else
50	printf(“\nEl elemento SI existe en la lista.\n\n”);
51	}
52	system(“PAUSE”);
53	}
54
55	Nodo buscaLista(Nodo cab, int x){
56	Nodo *p = NULL;
57	p = cab;
58	do {
59	p = p->Siguiente;
60	} while((p->Siguiente != NULL) && (p->informacion != x));
61
62	if (p->informacion == x)
63	return p;
64	else
65	return NULL;
65	}

Resultados

Analisis

Línea 45	El método “buscaLista” retorna un puntero al elemento encontrado
Línea 58-65	El método “buscaLista” consiste en recorrer la lista hasta encontrar el elemento buscado o hasta llegar al fin de la lista, si se tiene éxito en la búsqueda se devuelve un puntero a dicho elemento, en caso contrario se devuelve nulo.
( ..... )	En este programa por cuestiones de espacio se ha eliminado del código el método “presentar” mismo que es exactamente igual al implementado en programas anteriores, tener en cuenta esta observación para futuros programas.

Insertar.

La operación de inserción consiste en agregar un nuevo nodo a la lista. No se considera el caso de listas vacía, sino se supondrá que lista en la cual se va a insertar el nuevo nodo ya existe. Se pueden presentar tres casos en la operación de inserción:

* Insertar un nodo al inicio de la lista

*Insertar un nodo al final de la lista

* Insertar un nodo antes o después que un elemento indicado

El programa que se muestra a continuación corresponde a la inserción de un elemento después de un elemento determinado, se recomienda que el estudiante desarrolle los otros programas de inserción de elementos para obtener un mayor dominio de este tema.

Ejercicio 4.4: Escribir un programa que inserte un nodo, “después” de un elemento determinado:

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: insertaListaDespues.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	struct Elemento {
13	int informacion;
14	struct Elemento *Siguiente;
15	};
16	typedef struct Elemento Nodo;
17
18	Nodo insertaListaDespues(Nodo cab, int x, int nuevoElemento);
19
20
21	main( ) {
22	Nodo *pCabeza = NULL;
23	Nodo *p = NULL;
24	Nodo *r = NULL;
25	int dato;
26
27	pCabeza = (Nodo*)malloc(sizeof(Nodo));
28	p = pCabeza;
29	do {
30	printf(“Ingrese la informacion del nodo: “);
31	scanf(“%d”, &dato);
32	if (dato != -1) {
33	r = (Nodo*)malloc(sizeof(Nodo));
34	r->informacion = dato
35	r->Siguiente = NULL;
36	p->Siguiente = r;
37	p = r;
38	}
39	} while(dato != -1);
40	printf(“\n\n”);
41	presentar(pCabeza);
42	printf(“\n\n”);
43	Nodo *Indice;
44	int nodoActual, nodoNuevo;
45	Iprintf(“Ingrese la informacion del nodo EXISTENTE: “);
46
47	scanf(“%d”, &nodoActual);
48	printf(“Ingrese la informacion del nodo NUEVO: “);
49	scanf(“%d”, &nodoNuevo);
50	Indice = insertaListaDespues(pCabeza, nodoActual, nodoNuevo);
51
52	if (Indice == NULL)
53	printf(“\nEl elemento NO ha podido ser insertado.\n\n”);
54
55	else
56	printf(“\nEl elemento se inserto satisfactoriamente.\n\n”);
57
58	presentar(pCabeza);
59	printf(“\n\n”);
60	system(“PAUSE”);
61	}
62
63	Nodo insertaListaDespues(Nodo cab, int x, int nuevoElemento) {
64
65	Nodo *p = NULL;
66	Nodo *r = NULL;
67	p = cab;
68	do {
69	p = p->Siguiente;
70	} while((p->Siguiente != NULL) && (p->informacion != x));
71
72	if (p->informacion == x) {
73	r = (Nodo*)malloc(sizeof(Nodo));
74	r->informacion = nuevoElemento;
75	r->Siguiente = p->Siguiente;
76	rp->Siguiente = r;
77	return r;
78	}
79	else
80	return NULL;
81	}

Resultados

Analisis

Línea 68-71	En primer lugar se recorre la lista para encontrar el nodo de referencia para insertar.o
Línea 72-78	Si se encuentra el elemento de referencia se procede a la inserción. Se crea el nuevo nodo en la línea 73 y se hacen los enlaces correspondientes, finalmente en la línea 77 se retorna un puntero al elemento creado..

Eliminar.

Consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se puede presentar cuatro casos en esta operación.

* Eliminar el primer nodo.

* Eliminar el último nodo

* Eliminar un nodo con información X.

* Eliminar el nodo anterior o posterior al nodo con información X.

Igualmente se recomienda que el estudiante desarrolle las otras alternativas de eliminación.

Ejercicio 4.5: Escribir un programa que elimine el nodo con información X:

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: eliminaLista.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	struct Elemento {
13	int informacion;
14	struct Elemento *Siguiente;
15	};
16	typedef struct Elemento Nodo;
17
18	Nodo eliminaLista(Nodo cab, int x);
19
20	main( ) {
21	Nodo *pCabeza = NULL;
22	Nodo *pCabeza = NULL;
23	Nodo *r = NULL;
24	Nodo int dato;
25
26	pCabeza = (Nodo*)malloc(sizeof(Nodo));
27	pp = pCabeza;
28	do {
29	printf(“Ingrese la informacion del nodo: “);
30	scanf(“%d”, &dato);
31	if (dato != -1) {
32	if (dato != -1) {
33	r = (Nodo*)malloc(sizeof(Nodo));
34	r->informacion = dato;
35	r->Siguiente = NULL
36	p->Siguiente = r;
37	p = r;
38	}
39	} while(dato != -1);
40	printf(“\n\n”);
41	presentar(pCabeza);
42	printf(“\n\n”);
43	Nodo *Indice;
44	int nodoEliminar;
45	printf(“Ingrese la informacion del nodo para ELIMINAR: “);
46	scanf(“%d”, &nodoEliminar);
47	Indice = eliminaLista(pCabeza, nodoEliminar);
48	if (Indice == NULL)
49	printf(“\nEl elemento NO ha podido ser eliminado.\n\n”);
50	else
51	printf(“\nEl elemento se elimino satisfactoriamente.\n\n”);
52	if (Indice == NULL)
53	printf(“\nEl elemento NO ha podido ser insertado.\n\n”);
54	presentar(pCabeza);
55	printf(“\n\n”);
56	system(“PAUSE”);
57	}
58
59	Nodo eliminaLista(Nodo cab, int x) {
60	Nodo *p = NULL;
61	Nodo *ant = NULL;
62	p = cab;
63	do {
64	ant = p;
65	p = p->Siguiente;
66	} while((p->Siguiente != NULL) && (p->informacion != x));
67
68	if (p->informacion == x) {
69	ant->Siguiente = p->Siguiente;
70	return p;
71	}
72	if (p->informacion == x) {
73	else
74	return NULL;
75	}

Resultados

Analisis

Línea 63-67	Igualmente primero se busca el elemento para eliminar
Línea 68-71	Posteriormente se cambian los enlaces, es decir se hace que el elemento anterior al buscado apunte al siguiente nodo, de esta manera queda eliminado el nodo, igualmente se retorna un puntero, para saber que la operación a tenido éxito.

Modificar.

La modificación consiste en cambiar únicamente el valor o el dato que se encuentra almacenado en un determinado nodo, con la modificación no cambian las direcciones de los apuntadores.

Ejercicio 4.6: Escribir un programa que modifique el valor de un nodo determinado:

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: modificaLista.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	struct Elemento {
13	int informacion;
14	struct Elemento *Siguiente;
15	};
16	typedef struct Elemento Nodo;
17
18	NNodo modificaLista(Nodo cab, int x, int nuevoElemento);
19
20	main( ) {
21	Nodo *pCabeza = NULL;
22	Nodo *p = NULL;
23	Nodo *r = NULL;
24	int dato;
25
26	pCabeza = (Nodo*)malloc(sizeof(Nodo));
27	p = pCabeza;
28	do {
29	printf(“Ingrese la informacion del nodo: “);
30	scanf(“%d”, &dato);
31	if (dato != -1) {
32	ir = (Nodo*)malloc(sizeof(Nodo));
33	r->informacion = dato;
34	r->Siguiente = NULL;
35	p->Siguiente = r;
36	p = r;
37	}
38	} while(dato != -1);
39	printf(“\n\n”);
40	presentar(pCabeza);
41	printf(“\n\n”)
42	Nodo *Indice;
43	int nodoActual, nodoNuevo;
44	printf(“Ingrese la informacion del nodo ACTUAL:
45	scanf(“%d”, &nodoActual);
46	printf(“Ingrese la informacion del nodo NUEVO: “);
47	scanf(“%d”, &nodoNuevo);
48	Indice = modificaLista(pCabeza, nodoActual, nodoNuevo);
49
50	if (Indice == NULL)
51	printf(“\nEl elemento NO ha podido ser modificado.\n\n”);
52
53	else
54	printf(“\nEl elemento se modifico
55	printf(“\n\n”);
56	satisfactoriamente.\n\n”);
57	presentar(pCabeza);
58	system(“PAUSE”);
59	N}
60
61	Nodo modificaLista(Nodo cab, int x, int nuevoElemento)Nodo {
62	Nodo *p = NULL;
63	Nodo *r = NULL;
64	p = cab;
65	do {
66	p = p->Siguiente;
67	} while((p->Siguiente != NULL) && (p->informacion != x));
68
69	if (p->informacion == x) {
70	p->informacion = nuevoElemento;
71	return p;
72	}
73	else
74	return NULL;
75	}

Resultados

Analisis

Línea 66-75	La modificación es mucho mas sencilla puesto que se busca el elemento para modificar y posteriormente se carga la información nueva en el campo de datos del nodo encontrado, igualmente siempre es importante retornar un puntero no nulo para conocer si la operación a tenido éxito.r

4.4 Listas Doblemente Enlazadas

Una lista doblemente ligada es una colección de nodos, en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (“ligaIzquierda”) y otro a su sucesor (“ligaDerecha”). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.

4.5 Operaciones con Listas Doblemente Enlazadas

Las operaciones que se pueden realizar en listas doblemente enlazadas son las mismas que estudiamos en las Listas Enlazadas. A continuación se presentan dos programas para manipular los datos de estas estructuras, adicionalmente se recomienda que el estudiante desarrolle los programas correspondientes a las otras operaciones.

Creación. Para la creación de una lista doblemente enlazada se debe crear un nodo con dos punteros, a continuación se presenta el programa para crear esta estructura, igualmente se presenta un método para presentar los elementos de la lista el mismo que recorre dicha estructura en ambos sentidos.

Ejercicio 4.7: Escribir un programa para crear los nodos en una Lista Doblemente Enlazada:

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: creaDobleLista.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	struct Elemento {
13	int informacion;
14	struct Elemento *Siguiente;
15	struct Elemento *Anterior;;
16	};
17	&typedef struct Elemento Nodo;
18
19	main( ) {
20	Nodo *pCabeza = NULL;
21	Nodo *p = NULL;
22	Nodo *r = NULL;
23	int dato;
24
25	pCabeza = (Nodo*)malloc(sizeof(Nodo));
26	p = pCabeza;
27	do {
28	printf(“Ingrese la informacion del nodo: “);
29	scanf(“%d”, &dato);
30	if (dato != -1) {
31	r = (Nodo*)malloc(sizeof(Nodo));
32	r->informacion = dato;
33	r->Siguiente = NULL;
34	r->Anterior = p;
35	p->Siguiente = r;
36	p = r;
37	}
38	} while(dato != -1);
39	printf(“\n\n”);
40	presentar(pCabeza);
41	printf(“\n\n”)
42	system(“PAUSE”);
43	}
44
45	presentar(Nodo *cab){
46	Nodo *p = NULL;
47	Nodo *r = NULL;
48	p = cab;
49	do {
50	r = p->Siguiente;
51	printf(“%d, “, r->informacion);
52	&nbsp p = p->Siguiente;
53	} while(p->Siguiente != NULL);
54	printf(“// “);
55	do {
56	r = p->Anterior;
57	presentar(pCabeza);
58	printf(“%d, “, r->informacion);
59	p = p->Anterior;
60	} while(p->Anterior != cab);
61	Nodo modificaLista(Nodo cab, int x, int nuevoElemento)Nodo {
62	}

Resultados

Analisis

Línea 31-36	El proceso de creación de una lista con doble enlace es muy similar al estudiando anteriormente, en este caso hay que tener en cuenta que cada nuevo nodo creado se debe enlazar al anterior y naturalmente el mismo debe ser también apuntado por el anterior
Línea 49-59	en ambos sentidos, para lo cual se tiene dos procesos repetitivos, el primero una el campo “Siguiente” y el segundo usa el campo “Anterior”.

Recorrido.

En el ejercicio anterior (“Creación”) se presenta un método denominado “presentar” el cual recorre la lista hacia delante y hacia atrás.

Insertar.

La inserción es una de las operaciones básicas en cualquier tipo de lista enlazada, misma que tiene algunas variantes: insertar elementos al inicio de la lista, al final, y antes y después de un nodo determinado.

Ejercicio 4.8: Escribir un programa para insertar elementos en una Lista Doblemente Enlazada, la inserción debe efectuarse antes de un nodo dado como referencia:

Código:

2	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
1
3	//	//
4	// Programa: insertaDobleListaAntes.c	//
5	// Autor: Guido Riofrio C.	//
6	// Fecha: 15-MAYO-2005	//
7	//	//
8	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	//
9
10	#include <stdio.h>
11
12	struct Elemento {
13	int informacion;
14	struct Elemento *Siguiente;
15	struct Elemento *Anterior;;
16	};
17	&typedef struct Elemento Nodo;
18
19	Nodo insertaDobleListaAntes(Nodo cab, int x, int nuevoElemento);
20
21
22	& main( ) {
23	Nodo *pCabeza = NULL;
24	Nodo *p = NULL;
25	Nodo *r = NULL;
26	int dato;
27
28	pCabeza = (Nodo*)malloc(sizeof(Nodo));
29	p = pCabeza;
30	do {
31	printf(“Ingrese la informacion del nodo: “);
32	scanf(“%d”, &dato);
33	if (dato != -1) {
34	r = (Nodo*)malloc(sizeof(Nodo));
35	r->informacion = dato;
36	r->Siguiente = NULL;
37	r->Anterior = p;
38	p->Siguiente = r;
39	p = r;
40	}
41	} while(dato != -1);
42	printf(“\n\n”);
43	presentar(pCabeza);
44	printf(“\n\n”);
45	Nodo *Indice;
46	int nodoActual, nodoNuevo;
47	printf(“Ingrese la informacion del nodo EXISTENTE: “);
48
49	scanf(“%d”, &nodoActual);
50	printf(“Ingrese la informacion del nodo NUEVO: “);
51	scanf(“%d”, &nodoNuevo);
52	Indice = insertaDobleListaAntes(pCabeza, nodoActual, nodoNuevo);
53	} while(p->Siguiente != NULL);
54	if (Indice == NULL)
55	printf(“\nEl elemento NO ha podido ser insertado.\n\n”);
56
57	else
58	pprintf(“\nEl elemento se inserto satisfactoriamente.\n\n”);
59
60	presentar(pCabeza);
61	printf(“\n\n”);
62	system(“PAUSE”);
61	}
62	system(“PAUSE”);
63	printf(“\n\n”);
64
65	Nodo insertaDobleListaAntes(Nodo cab, int x, int nuevoElemento) {
66
67	Nodo *p = NULL;
68	Nodo *r = NULL;
69	Nodo *ant = NULL;
70	p = cab;
71	do {
72	ant = p;
73	p = p->Siguiente;
74	} while((p->Siguiente != NULL) && (p->informacion != x));
75
76	if (p->informacion == x) {
77	r = (Nodo*)malloc(sizeof(Nodo));
78	r->informacion = nuevoElemento;
79	r->Siguiente = p;
80	r->Anterior = ant;
81	ant->Siguiente = r;
82	p->Anterior = r;
83	return r;
84	}
85	else
86	return NULL;
87	}

Resultados

Analisis

Línea 71-84	Para el algoritmo de inserción en una lista doblemente ligada, al igual que los anteriores programas, se busca el elemento de referencia, y posteriormente se inserta el elemento haciendo los respectivos enlaces al nodo anterior y posterior.

Capitulo 5 : PILAS Y COLAS

Datos Generales:

Texto Base	A GUILAR LUIS JOYAOYANES, Zahonero Martínez Ignacio, Algoritmos y Estructuras de Datos. Una perspectiva en C, McGraw-Hill, Madrid-España, 2004.
Capítulo	5. Pilas y Colas
Secciones	10.1; 10.3; 11.1; 11.4
Horas de estudio empleadas para el desarrollo del contenido	6 horas

Introducción:

Una vez que hemos estudiado las listas enlazadas y obviamente los punteros nos será fácil entender la estructura “Pila” y “Cola” en realidad estas estructuras son Listas enlazadas con algunas restricciones, si bien es cierto y como recordaremos en las listas se podían insertar o eliminar elementos en cualquier parte de la estructura: al inicio, intermedio o al final; en cambio en estas ultimas estructuras la inserción y eliminación se hace únicamente por el principio o fin, como se podrá dar cuenta las listas, pilas y colas no tienen diferencias desde el punto de vista estructural las únicas diferencias son de tipo funcional, por lo tanto algunas de los programas desarrollados en el capitulo de listas enlazadas son perfectamente aplicables a las “pilas” y “colas”. Por otra parte también se pueden utilizar arreglos para representar pilas y colas pero no es recomendable por las limitaciones que tienen los arreglos en cuanto al uso de memoria.

Objetivos:

Aplicar los conocimientos adquiridos en el estudio de listas enlazadas.
Desarrollar los algoritmos necesarios para manipular las estructuras de pilas y colas

Conceptos Claves:

Pila.-Es una estructura de datos que puede ser implementada mediante arreglos o mediante listas enlazadas, la cual tiene unas características en cuanto al ingreso y salida de datos (LIFO)
Cola.- Es una estructura de datos que puede ser implementada mediante arreglos o mediante listas enlazadas, la cual tiene unas características en cuanto al ingreso y salida de datos (FIFO)

Esquema de Estudio:

Tema a revisar	Descripción del Contenido a revisar	Actividades Recomendadas	Planificación Personal del estudio (fecha)	¿Requiero Tutorial?	Anotaciones
5.1 Pilas – 5.2 Colas	Se exponen los conceptos teóricos relacionados con pilas y colas
5.3 Operaciones con pilas y Colas	Las operación sobre pilas y colas son una extensión de las operaciones en listas enlazadas	El estudiante debe desarrollar los programas para insertar y eliminar elementos en la pilas y colas

5.4 Pilas. Concepto de Pila

Una pila es una colección ordenada de elementos a los que sólo se puede acceder por un único lugar o extremo de la pila. Los elementos de la pila se añaden o quitan (borran) de la misma sólo por su parte superior (cima) de la pila. Es el caso de una pila de platos, una pila de libros, etc.

Una pila es una estructura de datos de entradas ordenadas tales que sólo se pueden introducir y eliminar por un extremo, llamado cima.

Cuando se dice que la pila está ordenada, lo que se quiere decir es que hay un elemento al que se puede acceder primero (el que está encima de la pila), otro elemento al que se puede acceder en segundo lugar (justo el elemento que está debajo de la cima), un tercero, etc. No se requiere que las entradas se puedan comparar utilizando el operador “menor que” (<) y pueden ser de cualquier tipo.

Las entradas de la pila deben ser eliminadas en el orden inverso al que se situaron en la misma. Por ejemplo, se puede crear una pila de libros, situando primero un diccionario, encima de él una enciclopedia y encima de ambos una novela de modo que la pila tendrá la novela en la parte superior.

Cuando se quitan los libros de la pila, primero debe quitarse la novela, luego la enciclopedia y, por último, el diccionario. Debido a su propiedad específica “último en entrar, primero en salir” se conoce a las pilas como estructura de datos LIFO (last-in, first-out). Las operaciones usuales en la pila son Insertar y quitar. La operación Insertar (push) añade un elemento en la cima de la pila y la operación Quitar (pop) elimina o saca un elemento de la pila.

La operación Insertar (push) sitúa un elemento dato en la cima de la pila y Quitar (pop) elimina o quita el elemento de la pila.

La pila se puede implementar mediante arrays en cuyo caso su dimensión o longitud es fija, y mediante punteros o listas enlazadas en cuyo caso se utiliza memoria dinámica y no existe limitación en su tamaño.

Una pila puede estar vacía (no tiene elementos) o llena (en el caso de tener tamaño fijo, si no cabe más elementos en la pila). Si un programa intenta sacar un elemento de una pila vacía, se producirá un error debido a que esa operación es imposible; esta situación se denomina desbordamiento negativo (underflow). Por el contrario, si un programa intenta poner un elemento en una pila se produce un error llamado desbordamiento (overflow) o rebosamiento. Para evitar estas situaciones se diseña funciones, que comprueban si la pila está llena o vacía.

5.5 Colas

Una cola es una estructura de dato que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista. Un elemento se inserta en la cola (parte final) de la lista y se suprime o elimina por la frente (parte inicial, cabeza) de la lista. Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia.

Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se almacenan y, por consiguiente, una cola es una estructura de tipo FIFO (first-in/first-out, primero en entrar/primero en salir o bien primero en llegar/primero en ser servido). El servicio de atención a clientes en un almacén es un ejemplo típico de cola. La acción de gestión de memoria intermedia (buffering) de trabajos o tareas de impresora es un distribuidor de impresoras (spooler) es otro ejemplo típico de cola. Dado que la impresión es una tarea (un trabajo) que requiere más tiempo que el proceso de la transmisión real de los datos desde la computadora a la impresora, se organiza una cola de trabajos de modo que los trabajos se imprimen en el mismo orden en que se recibieron por la impresora. Este sistema tiene el gran inconveniente de que si su trabajo personal consta de una única página para imprimir y delante de su petición de impresión existe otra petición para imprimir un informe de 300 páginas, deberá esperar a la impresión de esas 300 páginas antes de que se imprima su página.

Desde el punto de vista de estructura de datos, una cola es similar a una pila, en donde los datos se almacenan de un modo lineal y el acceso a los datos sólo está permitido en los extremos de la cola.

100 UTPL La Universidad Católica de Loja MODALIDAD ABIERTA Y A DISTANCIA Guía Didáctica: Estructura de Datos y Algoritmos I

5.6 Operaciones con Pilas y Colas

Una vez que hemos estudiado las principales operaciones que se efectúan en las listas enlazadas estamos listos para aplicar dicha lógica a nuevas estructuras, en este caso las Pilas y Colas se pueden implementar mediante estructuras dinámicas (Listas Enlazadas) y las operaciones a efectuar son únicamente insertar o eliminar elementos al inicio o final de estas estructuras. Adicionalmente se debe mencionar que las Pilas y Colas también se pueden implementar mediante arreglos lo cual representa desventajas en cuanto a las limitaciones por ser estructuras estáticas, pero puede ser de gran utilidad la implementación mediante este tipo de estructuras en función de la simplicidad. Se recomienda que el estudiante desarrolle los programas para insertar y eliminar elementos en estas dos estructuras (Pilas y Colas) ya sea mediante Listas o Arreglos.

Capitulo 6 : ESTRUCTURAS DE DATOS NO LINEALES, ARBOLES

Datos Generales:

Texto Base	A GUILAR LUIS JOYAOYANES, Zahonero Martínez Ignacio, Algoritmos y Estructuras de Datos. Una perspectiva en C, McGraw-Hill, Madrid-España, 2004.
Capítulo	6. Estructuras de datos No Lineales, Árboles
Secciones	14.1; 14.2; 14.3; 14.4; 14.5; 14.6
Horas de estudio empleadas para el desarrollo del contenido	2 horas

Introducción:

En este capitulo estudiaremos los árboles como estructuras no lineales; específicamente nos centraremos en el estudio de los árboles binarios, mismos que tienen una gran importancia en el desarrollo de aplicaciones informáticas.

Objetivos:

Exponer las características de los árboles en general.
Explicar y aplicar los diferentes métodos de recorrer un árbol binario.
Explicar y aplicar la forma de construir un árbol binario de búsqueda.

Conceptos Claves:

Árbol. Es una estructura en la cual los datos se encuentran almacenados de forma jerárquica, no lineal
Árbol binario.- En un árbol binario cada nodo puede tener como máximo dos ramas descendientes o hijos.
Árbol binario de búsqueda.- En este tipo de árbol los elemntos se encuentran ordenados y para cada nodo los elementos mayores estan en el subárbol derecho y los menores en el izquierdo

Esquema de Estudio:

Tema a revisar	Descripción del Contenido a revisar	Actividades Recomendadas
6.1 Árboles 6.2 Terminología	Marco teórico sobre árboles así como los conceptos relacionados
6.6 Árboles binarios	Marco teórico sobre árboles binarios
6.7 Árboles de expresión	Se explican los conceptos relacionados con árboles de expresión así como el proceso para generarlos	El estudiante debe plantearse ecuaciones aritméticas para que las mismas sean expresadas mediante árboles de expresión
6.8 Recorridos en árboles binarios	Se exponen los algoritmos para realizar los diferentes tipos de recorridos	El estudiante debe graficar árboles binarios y realizar los recorridos planteados
6.9 Árboles binarios de búsqueda	Se exponen los conceptos relacionados con árboles binarios de búsqueda, así como también la forma de construirlos	Se recomienda que el estudiante se plantee listas de valores para posteriormente construir su árbol binario de búsqueda

6.9 Árboles

Un árbol implica una estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas. El árbol genealógico es el ejemplo típico más representativo del concepto de árbol general. Un árbol consta de un conjunto finito de elementos, denominados nodos y un conjunto finito de líneas dirigidas, denominadas ramas, que conectan los nodos. El número de ramas asociado con un nodo es el grado del nodo. Si un árbol no está vacío, entonces el primer nodo se llama raíz.

6.10 Terminología

Además de la raíz, existen muchos términos utilizados en la descripción de los atributos de un árbol. Tomado como base la Figura 6.1

Imagen:Terminología de arboles.JPG

Padres:	A, B, F
Hijos	B, E, F, C, D, G, H, I
Descendientes de A:	B, C, D
Ascendientes de C:	B, A
Hermanos:	{B, E, F}, {C, D}, {G, F, I}
Hojas:	C, D, E, G, H, I
Profundidad:	3 BCD, E, FGHI

6.11 Aplicaciones de los árboles

Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se puede utilizar para:

* Representar fórmulas matemáticas,

* Organizar adecuadamente la información,

* Registrar la historia de un campeonato de tenis,

* Construir un árbol genealógico,

* Análisis de circuitos eléctricos.

6.12 Representación de un árbol

Los árboles pueden representarse de varias maneras, aunque la forma más común es mediante grafos:

6.13 Árboles binarios

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener, cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Un árbol binario es una estructura recursiva, cada nodo es la raíz de su propio subárbol y tiene hijos, que son raíces de árboles llamados los subárboles derecho o izquierdo del nodo, respectivamente.

6.14 Árboles de expresión

Una de las aplicaciones mas importantes de los árboles binarios son los árboles de expresión, estos se utilizan para representar ecuaciones matemáticas, las características más importantes de esta representación es:

Los operándos (números o variables) de la expresión siempre serán las hojas del árbol.
Los operadores de la expresión están representados en los nodos internos o raíz.

En el libro existen algunos ejemplos de este tipo de representación, igualmente es muy importante recalcar que para aplicar el algoritmo de la página 431 del libro guía la expresión debe estar completamente agrupada entre paréntesis, de tal forma que la siguiente expresión:

a * c + e / g – ( b + d )

Debe estar agrupada de la siguiente forma:

( ( ( a * c ) + ( e / g ) ) – ( b + d ) )

Debe estar agrupada de la siguiente forma:

( ( ( a * c ) + ( e / g ) ) – ( b + d ) )

Una vez agrupada la expresión se deben seguir los pasos que indica el algoritmo, para lo cual se deben recorrer todos los elementos de la expresión, dichos pasos se presentan a continuación:

1. Cuando se encuentra el primer paréntesis izquierdo se crea el nodo raíz, a este nodo se le denomina nodo actual.

2. Cada vez que se encuentra un paréntesis izquierdo se debe crear un nodo vacío a la izquierda del nodo actual, si el nodo actual ya tiene creada la rama izquierda entonces se crea el nuevo nodo en la rama derecha, este ultimo nodo creado pasa a ser el nodo actual.

3. Cuando se encuentre un operando se debe crear un nuevo nodo no vacío, en este caso se le asigna el valor del operando, igualmente que el caso anterior, este nuevo nodo debe crearse a la izquierda del nodo actual, en caso contrario se crea a la derecha, y el mismo se hace nodo actual.

4. Cuando encontremos un operador se debe recorrer el árbol desde el nodo actual hacia la raíz hasta encontrar el primer nodo vacío y asignarle a este el valor del operador, de la misma forma este nodo encontrado se convierte en nodo actual.

Como se podrá dar cuenta el nodo actual cambia de valor o apuntamiento cada vez que se recorre los elementos de la expresión, es importante indicar que al encontrar un paréntesis derecha el algoritmo no realiza ninguna acción. El árbol de expresión para el ejemplo anterior es el siguiente:

6.15 Recorridos en árboles binarios

Recorrer significa visitar los nodos del árbol en forma sistemática. Un recorrido de un árbol binario, requiere que cada nodo del árbol sea procesado (visitado) una vez y sólo una en una secuencia determinada.

Existen tres formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva, éstas son:

Recorrido Preorden (NID)

* Visitar la raíz (N)

* Recorrer el subárbol izquierdo (I)

* Recorrer el subárbol derecho (D)

Recorrido Enorden(IND)

* Recorrer el subárbol izquierdo (I)

* Visitar la raíz (N)

* Recorrer el subárbol derecho (D)

Recorrido Postorden (IDN)

* Recorrer el subárbol izquierdo (I)

* Recorrer el subárbol derecho (D)

* Visitar la raíz (N)

Ejercicio 6.1: Realice los tres recorridos vistos anteriormente para el árbol mostrado en la siguiente figura:

a): Preorden : L, D, B, H, G, J, Q, X, T, S, W, Y b): Enorden : B, D, G, H, J, L, Q, S, T, W, X, Y c): Postorden : B, G, J, H, D, S, W, T, Y, X, Q, L

6.16 Árboles binarios de búsqueda

El árbol binario de búsqueda es una estructura sobre la cual se puede realizar eficientemente las operaciones de búsqueda, inserción y eliminación. Formalmente se define un árbol binario de búsqueda de la siguiente manera: «Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del subárbol izquierdo de T deben ser menores o iguales al valor del nodo T. De forma similar, todos los valores de los nodos del subárbol derecho de T deben ser mayores o iguales al valor del nodo T.

Un árbol binario de búsqueda se construye en base a una lista de números dados (claves), en el cual el primer número de dicha lista será la raíz del árbol, y los siguientes valores se ubican de acuerdo al criterio antes indicado.

Ejercicio 6.2: Construya un árbol binario de búsqueda para la siguiente lista de números: 65, 75, 30, 4, 41, 85.

Obtenido de "http://www.utpl.edu.ec/ecc/wiki/index.php/Estrunctura_de_Datos_y_Algoritmos_I"

Estrunctura de Datos y Algoritmos I

De Computacion

Tabla de contenidos

Objetivos Generales

Bibliografía

Desarrollo del Aprendizaje

Capitulo1: ESTRUCTURAS DE DATOS SIMPLES Y COMPUESTOS

Datos Generales:

Introducción:

Objetivos:

Conceptos Claves:

Esquema de Estudio:

Datos Generales:

Introducción:

Objetivos:

Conceptos Claves:

Esquema de Estudio:

Capitulo3: ESTRUCTURAS DINÁMINAS: APUNTADORES

Datos Generales:

Introducción:

Objetivos:

Conceptos Claves:

Esquema de Estudio:

Capitulo4: Estructuras Dinámicas Lineales: Listas enlazadas

Datos Generales:

Introducción:

Objetivos:

Conceptos Claves:

Esquema de Estudio:

Capitulo 5 : PILAS Y COLAS

Datos Generales:

Introducción:

Objetivos:

Conceptos Claves:

Esquema de Estudio:

Capitulo 6 : ESTRUCTURAS DE DATOS NO LINEALES, ARBOLES

Datos Generales:

Introducción:

Objetivos:

Conceptos Claves:

Esquema de Estudio:

Vistas

Herramientas personales

Navegación

Sitios UTPL

Sitios ECC

Buscar

Herramientas