Una estructura de datos es: un cojunto de elementos ordenados y sistematizados.
estructura de control nos permite tomar decisiones tipo boleano (verdadero o falso) (if, if then, if then else, case, switch) estructuras iterativas tambien llamadas en iteración (repetición) while for: son los arreglos Do while: punteros son: variables tipos flotantes dentro de un vector busqueda acendente y decendente
Estructura de control.- un conjunto de parametro o relgas para el ordaneamiento de datosNos pèrmiten tomar decisiones boleanos (verdaderas o falso ):-- if-- ifthen-- ifelse
Son if aninadados:-- case-- swithEstructuras iteractivas (repeticion)Son aciones repetitivas que se vuelven a repetir en ejecucionWhileFordowhilePunteros son variables que se mueven dentro de un vector o indices.
Actividad de la clase.-
ejercicio 1.- declarar una matris 3 * 3 que corra de manera horizontal
ejercicio 2.- declarar una matris de 2*2 Multiplicar una matris x 2
ejercicio 3.- Hacer un arreglo y ver en que posición este un dato de 3*3 en la posición 2,1
Algoritmo ejercicio 1
int a [1.3]; int x,y
for x=1 hasta y=3
for y=1 hasta y=3
a[x.y]= a[x.y]= mas 1;
imprimir a [x,y]
Algoritmo del ejercicio 2
int a [1.3]; int x,y
for x=1 hasta y=3
for y=1 hasta y=3a[x.y]=
a[x.y]= mas 1;
imprimir a [x,y] + 2
Algorito del ejercicio 3
int A [1.3] [1.3]
int b [1.3] [1.3]
for x=1 hasta x=3
for y=1 hasta y=3
a [w.y] = a[w.y] mas 1
imprimir x,y
viernes, 7 de noviembre de 2008
Definición de Métodos de Ordenación
Las estructuras de datos son utilizadas para almacenar información, para poder recuperarla de manera eficiente es deseable que esté ordenada. Existen varios métodos para ordenar la información, los cuales tienen como finalidad organizar los datos en un orden creciente o decreciente mediante una regla prefijada (numérica, alfabética, etc.). Atendiendo al tipo de elemento que se quiera ordenar la ordenación puede ser:
- Ordenación interna: Los datos se encuentran en memoria (ya sean arreglos, listas, etc.), y son de acceso aleatorio o directo (se puede acceder a un determinado campo sin pasar por los anteriores).
- Ordenación externa: Los datos están en un dispositivo de almacenamiento externo (archivos), y su ordenación es más lenta que la interna.
Métodos de Búsqueda ( secuencial, binaria, indexado, hashing)
Búsqueda Secuencial:
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.
Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. Y así poder encontrar el dato requerido.
Búsqueda Binaria:
La búsqueda binaria es el método, donde si el arreglo o vector esta bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.
El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Este método se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los pre – requisitos para la búsqueda binaria son:
La lista debe estar ordenada, en un orden especifico de acuerdo al valor de la clave.
Debe conocerse el número de elementos.
Si el conjunto de elementos es grande, el tiempo de búsqueda se puede reducir utilizando el siguiente algoritmo de tipo divide y vencerás:
1.-Se divide el elemento en dos partes.
2.-Se determina la parte que debe contener la clave buscada.
3.-Se repite el proceso en esa parte.
Búsqueda Indexada:
En este modo de organización, al fichero le acompaña un fichero de índice que tiene la función de permitir el acceso directo a los registros del fichero de datos.El índice se puede organizar de diversas formas, las más típicas son: secuencial, multinivel y árbol.A través del índice podremos procesar un fichero de forma secuencial o de forma directa según la clave de indexación, y esto independientemente de como esté organizado el fichero por sí mismo.El índice debe estar organizado en función de alguno de los campos de los registros de datos. Se pueden tener tantos índices como se quiera variando la clave (o campo) que se emplee. El índice está formado por registros (entradas) que contienen:
Clave de organización.
Puntero(s) al fichero de datos, en concreto al registro que corresponda.
Búsqueda Hashing:
En este método se requiere que los elementos estén ordenados.
El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento.
La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el 1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres, para utilizar mejor el espacio se utilizan funciones mas complejas.
La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar.
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.
Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. Y así poder encontrar el dato requerido.
Búsqueda Binaria:
La búsqueda binaria es el método, donde si el arreglo o vector esta bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante.
El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo. Si el elemento buscado es mayor se procede a hacer búsqueda binaria en el subarray superior, si el elemento buscado es menor que el contenido de la casilla central, se debe cambiar el segmento a considerar al segmento que está a la izquierda de tal sitio central.
Este método se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los pre – requisitos para la búsqueda binaria son:
La lista debe estar ordenada, en un orden especifico de acuerdo al valor de la clave.
Debe conocerse el número de elementos.
Si el conjunto de elementos es grande, el tiempo de búsqueda se puede reducir utilizando el siguiente algoritmo de tipo divide y vencerás:
1.-Se divide el elemento en dos partes.
2.-Se determina la parte que debe contener la clave buscada.
3.-Se repite el proceso en esa parte.
Búsqueda Indexada:
En este modo de organización, al fichero le acompaña un fichero de índice que tiene la función de permitir el acceso directo a los registros del fichero de datos.El índice se puede organizar de diversas formas, las más típicas son: secuencial, multinivel y árbol.A través del índice podremos procesar un fichero de forma secuencial o de forma directa según la clave de indexación, y esto independientemente de como esté organizado el fichero por sí mismo.El índice debe estar organizado en función de alguno de los campos de los registros de datos. Se pueden tener tantos índices como se quiera variando la clave (o campo) que se emplee. El índice está formado por registros (entradas) que contienen:
Clave de organización.
Puntero(s) al fichero de datos, en concreto al registro que corresponda.
Búsqueda Hashing:
En este método se requiere que los elementos estén ordenados.
El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento.
La principal forma de transformar el elemento es asignarlo directamente, es decir al 0 le corresponde el índice 0, al 1 el 1, y así sucesivamente pero cuando los elementos son muy grandes se desperdicia mucho espacio ya que necesitamos arreglo grandes para almacenarlos y estos quedan con muchos espacios libres, para utilizar mejor el espacio se utilizan funciones mas complejas.
La función de hash ideal debería ser biyectiva, esto es, que a cada elemento le corresponda un índice, y que a cada índice le corresponda un elemento, pero no siempre es fácil encontrar esa función, e incluso a veces es inútil, ya que puedes no saber el número de elementos a almacenar.
Suscribirse a:
Entradas (Atom)
