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.

[editar] 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.

[editar] 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

[editar] Desarrollo del Aprendizaje

[editar] Capitulo1: ESTRUCTURAS DE DATOS SIMPLES Y COMPUESTOS

[editar] 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

[editar] 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.

[editar] 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.

[editar] 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

[editar] 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.

[editar] Capitulo2: ESTRUCTURAS DE DATOS LINEALES ESTÁTICAS: ARREGLOS

[editar] 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

[editar] 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.

[editar] 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

[editar] 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

[editar] 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.

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: 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: %