Fundamentos-De-programacion Ordenamientos y Vectores

5/12/2018 Fundamentos-De-programacion Ordenamientos y Vectores - slidepdf.com

http://slidepdf.com/reader/full/fundamentos-de-programacion-ordenamientos-y-vectores

INSTRUCCIONES DE REPETICION

Las instrucciones de repetición son necesarias cuando en unalgoritmo hay que realizar una o muchas tareas varias veces, lasinstrucciones de repetición básicas son: el MIENTRAS y el PARA,

cada una de las cuales tiene su propia representación y su propiamanera de controlar el número de veces que se repetirá el ciclo(instrucciones internas ). estas características hacen que unainstrucción de repetición sea mas adecuado que la otra en unasituación particular.

ESTRUCTURA MIENTRAS( while)

La estructura repetitiva mientras es aquella en que las instruccionesinternas (bucle )se ejecutan mientras se cumple una determinada

condición. La estructura es la siguiente:

y Inicio y Instrucción 1 y mientras expresión_lógica haga y .......Instrucción 11 y .......Instrucción 12 y .......Instrucción 13 y f in mientras

y Instrucción n y « y f in del programa

Cuando se ejecuta la instrucción mientras. La primera cosa quesucede es que se evalúa la condición (una expresión lógica). Si laexpresión es f alsa, ninguna acción del bucle( parte interna) seejecuta y el programa continua en la siguiente instrucción al bucle.Si la expresión es verdadera, entonces se ejecuta el cuerpo del

bucle. Después de lo cual se evalúa de nuevo la expresión booleana.Este proceso se repite una y otra vez mientras la expresión lógica(condición) sea verdadera. Dentro del cuerpo del bucle debe existir una instrucción que modif ique la expresión de tal manera que enalgún momento haga que su valor sea f also. Es decir que garanticela terminación del ciclo.



Para controlar el número de repeticiones del ciclo se puede hacer de dos maneras:

1. utilizando una variable contador .

2. utilizando una variable centinela.

problemas propuestos

ESTRUCTURA DE REPETICIÓN PARA (FOR)

Permite que un grupo de instrucciones se repita cero o mas veces,dependiendo del valor que resulte al evaluar una expresión de tipológico.

La estructura es la siguiente:

Para expresión_inicio, expresión_lógica, expresion_incremento.......Instruccion1.......Instruccion2......Instruccion3......Instruccion4«

Fin paraInstrucción n«

la expresión_inicio establece la condición inicial para la variable decontrol evaluada en la expresión lógica.

La expresion_incremento modif ica la variable de control.La expresión_lógica es una expresión f ormado con la variable decontrol, y que sirve para controlar el número de iteraciones del ciclo

el cual termina cuando su valor sea f also.

ejemplo 1 ejemplo 6

ejemplo 2 ejemplo 7

ejemplo 3 ejemplo 8



ejemplo 4 ejemplo 9

ejemplo 5 ejemplo 10


SUBALGORITMOS

cuando un algoritmo crece demasiado, se hace necesario dividirloen subalgoritmos o módulos, llamados f unciones o procedimientos.Esta división nos permite:

1. hacer mas entendible los algoritmos.

2. la detección y corrección de problemas se hace mas simple, pues los problemas están mas localizados, no es necesarioanalizar todo el algoritmo, sólo el módulo que esta f allando.

3. permite que los subalgoritmos se especialicen en resolver una tarea específ ica, sin importarles como f uncionan losdemás módulos. esto f acilita que varias personas puedanrealizar un algoritmo, cada uno de ellos realiza unsubalgoritmo específ ico.

4. si se han construido subalgoritmos, estos se puedenutilizar( llamar) las veces que se necesite. esto es lareutilización de los subalgoritmos, para que resolver un

problema que ya había sido resuelto, sólo se llama a lasolución.

FUNCIÓNES:

Una f unción es un subalgoritmo que toma uno o más valoresllamados argumentos y produce un valor llamado resultado (valor de la f unción para los argumentos dados).

DECLARACION DE FUNCIÓNES:

La declaración de una f unción requiere una serie de pasos que ladef inen. Una f unción tiene una construcción similar a losalgoritmos.



La descripción de la f unción será:

tipo de dato: nombre_ f inción (lista de parámetros)

<acciones>

devolver( expresión )f in f unción

1. tipo de dato: indica de que tipo de dato es la inf ormación quedevuelve la f unción.

2. dos puntos ' : ' 3. nombre de la f unción : debe ser un identif icador válido y

unico que se utiliza para llamar a la f unción. 4. argumentos de dicha f unción. Es una lista de declaraciones

de variables se paradas por dos puntos(' : ') donde seespecif ican los datos que requiere la f unción para trabajar.

5. Acciones o cuerpo de la f unción: son las dif erentes tareasque realiza la f unción.

6. devolver( expresión ): se indica que dato es el que devolverála f uncion al subalgoritmo que lo llamó.

7. f in f uncion: para indicar donde termina la f unción.

INVOCACION DE LAS FUNCIÓNES:

Una f unción puede ser llamada de la siguiente manera:

nombre_ f inción ( lista de parámetros actuales)

la lista de parámetros actuales debe corresponder en tipo y cantidad

con la lista de parámetros (f ormal) def inidos en la f unción.Una llamada a la f unción implica los siguientes pasos:· a cada parámetro f ormal se le asigna el valor real de sucorrespondiente parámetro actual.· Se ejecuta el cuerpo de acciones de la f unción· Se devuelve el valor de la f unción al nombre de la f unción y seretorna al punto de llamada.



ejemplo 1 ejemplo 6

ejemplo 2 ejemplo 7

ejemplo 3 ejemplo 8

ejemplo 4 ejemplo 9



PROCEDIMIENTOS

Un procedimiento es un subalgoritmo que toma uno o más valoresllamados argumentos, con los cuales ejecuta tareas específ icas.

DECLARACION DE PROCEDIMIENTOS:

La declaración de un procedimiento requiere una serie de pasos quela def inen. Un procedimiento tiene una construcción similar a losalgoritmos, por consiguiente constará de una cabecera quecomenzará con nombre del procedimiento y entre paréntesis unalista de argumentos del procedimiento. A continuación irá el cuerpodel procedimiento, que será una serie de acciones o instruccionesque conf orman el cuerpo del procedimiento.

La descripción del procedimiento será:

nombre_procedimiento (lista de argumentos)

<acciones>

f in procedimiento

1. nombre del procedimiento : debe ser un identif icador válido y unico que se utiliza para identif icar al procedimiento.

2. lista de argumentos. Es una lista de declaraciones devariables se paradas por dos puntos(' : ') donde se especif icanlos datos que requiere el procedimiento para trabajar.



3. Acciones o cuerpo del procedimiento: son las dif erentestareas que realiza el procedimiento.

4. f in procedimiento: para indicar donde termina el procedimiento.

INVOCACION DE LOS PROCEDIMIENTOS:

Un procedimiento puede ser llamada de la siguiente manera:

nombre_procedimiento ( lista de parámetros actuales)

la lista de parámetros actuales debe corresponder en tipo y cantidadcon la lista de parámetros (f ormal) def inidos en la f unción.Una llamada a un procedimiento implica los siguientes pasos:· a cada parámetro f ormal se le asigna el valor real de sucorrespondiente parámetro actual.· Se ejecuta el cuerpo de acciones del procedimiento.· Se regresa a la instrucción siguiente del punto de llamada.

ejemplo 1 ejemplo 6

ejemplo 2 ejemplo 7

ejemplo 3 ejemplo 8

ejemplo 4 ejemplo 9



REGRESAR

LAS TORRES DE HANOI



Hanoi es uno de las aplicaciones clásicas para enseñar recursion.una f unción o procedimiento es recursivo si en su def inición sellama a si mismo.

las torres de hanoi, consiste en un juego que consta de tres torres y

N discos de dif erente tamaño. el juego consiste en pasar todos losdiscos que están inicialmente en una torre (ordenados de mayor amenor de abajo hacia arriba) llamada origen y pasarlos a una torrellamada destino, siguiendo las siguientes reglas:

1. sólo se puede trasladar un disco a la vez.

2. nunca puede haber en una torre un disco de mayor tamaño, sobre otro disco de menor tamaño.

ESTRUCTURAS DE DATOS

ARREGLOS:

Un arreglo es una colección de datos del mismo tipo, que se almacenan en posiciones consecutivas de memoria y reciben un nombre común. Para ref erirse aun determinado elemento de un arreglo se deberá utilizar el nombre del arregloacompañado de un índice el cual especif ica la posición relativa en que se

encuentra el elemento.Los arreglos pueden ser:unidimensionales (vectores).Bidimensionales (matrices, tablas).Multidimensionales(tres dimensiones o más).

ARRAY UNIDIMENSIONALES O VECTORESLos pasos para la utilización de un vector son;1 Declarar el vector: consiste en establecer el nombre, el tamaño y el tipo de losdatos que se van a almacenar en el arreglo ejemplo:

hay que dif erenciar dos términos :tamaño del vector (T): es el numero máximo de elementos que puede contener elvector.

Numero de elementos(N): que indica cuantos elementos hay almacenados en elarreglo en determinado momento. Nota N<=T.

T = 10;



Real: notas[T]

2 Llenar el vector con los datos: Se puede hacer en el momento de la declaraciónasignando al vector los valores que necesitamos almacenar. Ejemplo.real : notas[10] = {2.3 , 3.5 , 4.2 , 3.3 , 3.0 , 4.9 , 4.2 , 3.0 , 2.0 , 1.5 };

ó recorriendo el arreglo así:

para i = 1 hasta N.......leer( notas[i] )f in del para

3 manipular la inf ormación guardada en el vector. Para esto es necesario recorrer dicha estructura y se puede hacer de la siguiente manera.

para i = 1 hasta N......mostrar ( notas[i] )f in del para

las operaciones que se pueden realizar con los arreglos son las siguientes:- lectura (llenar el vector)- escritura (mostrar el vector)- asignación (dar valor a una posición específ ica)- actualización (inserción , eliminación, modif icación )- ordenación . (burbuja, inserción directa, selección directa, selle y quicksort).

- búsqueda. (secuencial , binaria, hash( por claves) ). ARRAY BIDMENSIONALES (MATRICES)

Consiste en un vector de vectores y es por lo tanto un conjunto de elementos delmismo tipo en el que el orden de los componentes es signif icativo y en el quenecesitan especif icarse dos subíndices para poder identif icar cada elemento de lamatriz.Los pasos para la utilización de una matriz son;1. declarar la matriz: consiste en establecer el nombre, el tamaño y el tipo de los

datos que se van a almacenar en la matriz ejemplo: N = 3;M = 4;Real: matriz[N][M]

2. llenar la matriz con los datos: se puede hacer en el momento de la declaraciónasignando a la matriz los valores que necesitamos almacenar. Ejemplo.real: notas[][ ] = { {2.3 , 3.5 , 4.2 },{ 3.3 , 3.0 , 4.9} ,{ 4.2 , 3.0 , 2.0 } }



ó recorriendo el arreglo así:

para f = 1 hasta 3 , 1........para c = 1 hasta 4 , 1

..................leer( matriz[f ][c] )

........f in del paraf in del para

3. manipular la inf ormación guardada en la matriz. Para esto es necesario recorrer dicha estructura y se puede hacer de la siguiente manera.

para f = 1 hasta 3 ,1......para c = 1 hasta 4, 1..............mostrar ( matriz[f ][c] )......f in del paraf in del para

REGISTROS

Un registro es un dato estructurado, donde cada uno de sus componentes sedenomina campo. Los campos de un registro pueden ser todos de dif erentes tipos.Por lo tanto también podrán ser registros o arreglos. Cada campo se identif ica por

un nombre único (el identif icador del campo):

DEFINICION DE REGISTROPara def inir un registro se hará de la siguiente manera:

REGISTRO:id_registro....tipo1:id_campo1....tipo2:id_campo2....tipo3:id_campo3

« f in de la def inición

para acceder a un campo determinado de un registro se hará de la siguientemanera:



id_registro.id_capo

ejemplo1, problemas propuestos

VECTORES DE REGISTROS

También se puede manejar un vector de registros. Recuerde que el vector debecontener datos del mismo tipo (en este caso todos los datos son del tipo registro).

DEFINICION: para def inir un vector de registros proceda de la siguiente manera:Vector[ 5] : id_registro

Donde id_registro es el identif icador que se le dio al registro.

MATRIZ DE REGISTROS

También se puede manejar una matriz de registros. Recuerde que la matriz debecontener datos del mismo tipo (en este caso todos los datos son del tipo registro).

DEFINICION: para def inir una matrizr de registros proceda de la siguientemanera:id_registro:MaT[N][M]

Donde id_registro es el identif icador que se le dio al registro. N es el número def ilas de la matiriz y M es el número de columnas de la matriz.

LISTAS ENLAZADAS

Una lista enlazada o encadenada es un conjunto de elementos en los que cada

elemento contiene la posición (o dirección ) del siguiente elemento de la lista.Cada elemento de la lista debe tener al menos dos campos: un campo quecontiene el valor del elemento y un campo( enlace, link) que contiene la posicióndel siguiente elemento, es decir su conexión, enlace o encadenamiento. Loselementos de una lista son enlazados por medio de los campo enlaces.Las listas enlazadas se conf orman por nodos, como el que se muestra acontinuación.



Los componentes de los nodos se llaman campos. Un nodo tiene al menos uncampo dato o valor y un enlace o liga (dirección o puntero) con el siguientecampo.El ultimo nodo de la lista enlazada tiene como liga un NULL, indicando que lalista termina en ese nodo.

El enlace o puntero es una variable cuyo valor es la dirección o posición de otravariable. En las listas enlazadas no es necesario que los elementos de la lista seanalmacenados en posiciones f ísicas adyacentes, ya que el puntero indica donde se

encuentra el siguiente elemento de la lista .

Las listas enlazadas son estructuras dinámicas, queriendo decir esto que puedencrecer o encogerse durante la ejecución de un programa, utilizando así sólo lamemoria que requiere.

Una lista enlazada se def ine por:· El tipo de sus elementos o nodos· Campo de inf ormación (datos)· Campo enlace o liga (puntero)· Un puntero de cabecera que permite acceder al primer elemento de la lista,

utilizaremos la variable llamada punta.· Un medio para determinar el ultimo elemento de la lista: liga = null.

Para acceder al campo dato de un registro p utilizaremos la siguiente notaciónk = p.datoasignará a la variable k el valor que hay en p.datosi la punta = null quiere decir que la lista esta vacía.Para pedir un nodo p



pcrea_nodo() para liberar un nodo de la memoria se hará de la siguiente manera:libere(p)Para manipular y sacar inf ormación de la lista es necesario recorrerla y se hace dela siguiente manera:

Las operaciones básicas para el manejo de listas enlazadas son:· Insertar al principio de la lista un dato dado· mostrar el promedio de los datos de la lista· decir si un dato dado se encuentra o no en la lista.· Eliminar un dato dado de la lista

LISTAS SIMPLEMENTE LIGADAS CIRCULARES

Las listas simplemente enlazadas no permiten a partir de un elemento dadoacceder directamente a cualquiera de los que le preceden. En lugar de almacenar un puntero null en el campo liga del ultimo nodo de la lista, se hace que el ultimoelemento apunte al primero (punta) o principio de la lista.



Las listas circulares presentan las siguientes ventajas respecto a las listassimplemente enlazadas.

y Dado un nodo se puede recorrer la lista completa.y Las operaciones de concatenación y división de las listas son más ef icaces

con listas circulares.

Entre los inconvenientes esta que se pueden presenta ciclos inf initos en losalgoritmos.

Para manipular y sacar inf ormación de la lista es necesario recorrerla y se puedehacer de la siguiente manera:

LISTAS SIMPLEMENTE LIGADAS CIRCULAR CON REGISTRO CABEZA

La representación gráf ica de esta lista es la siguiente:



El primer nodo o registro de esta lista se llama registro cabeza. El campo de lainf ormación del registro cabeza no se utiliza, lo que se señala con el sombreadode dicho campo.

Una lista simplemente ligada con registro cabeza vacía se representa de la

siguiente manera:

El registro cabeza se utiliza para f acilitar las operaciones de recorrer la lista,insertar un registro, borrar un registro etc.


LISTAS SIMPLEMENTE LIGADAS CIRCULAR CON REGISTRO CABEZA

La representación gráf ica de esta lista es la siguiente:



El primer nodo o registro de esta lista se llama registro cabeza. El campo de lainf ormación del registro cabeza no se utiliza, lo que se señala con el sombreadode dicho campo.

Una lista simplemente ligada con registro cabeza vacía se representa de lasiguiente manera:

El registro cabeza se utiliza para f acilitar las operaciones de recorrer la lista,insertar un registro, borrar un registro etc.




PILAS REPRESENTADAS COMO VECTOR

En la representación de las pilas en arreglos se manejan las siguientes variables:Pila, TOPE y máximo.Pila : nombre del vector que sirve para representar la estructura.tope: posición en el vector que indica donde esta el ultimo elemento de la

pila.Máximo: tamaño del vector o máximo número de elementos de la pila.

Los Estados de una pila son:

y pila llena y pila con algunos elementos y pila vacia

la representación gráf ica el la siguiente:

PILAS REPRESENTADAS COMO LISTAS LIGADAS



En la representación de las pilas como listas simplemente ligadas. llamaremos ala punta de la lista como pila y las operaciones de apilar y desapilar se realizarande la siguiente manera:

y apilar : se debe insertar el elemento al inicio de la lista. y desapilar : se extrae el elemento que esta al inicio de la lista.

regresar

COLAS

Una cola es una lista de elementos en la cual las operaciones de inserción seef ectúan en un extremo llamado ULTIMO y las operaciones de borrado seef ectúan en el otro extremo llamado PRIMERO ( las colas también reciben elnombre de estructuras FIFO primero en entrar primero en salir).

las operaciones que se realizan en una cola son las siguientes:

encolar : es insertar un elemento en la cola , recuerde que se hace por elextremo llamado ultimo.

desencolar: es extraer un elemento de la cola, recuerde que se hace por elextremo llamado primero.

Un ejemplo clásico de una cola es la que hacen las personas esperando ser atendidos en una ventanilla.

Una cola se puede representar con un vector, con un vector circular o con unalista.

COLAS REPRESENTADAS COMO VECTOR

En la representación de las colas en arreglos se manejan las siguientes variables:COLA, ULTIMO, PRIMERO y MAXIMO.

COLA : nombre del vector que sirve para representar la estructura.ULTIMO: posición en el vector que indica donde esta el ultimo elemento de lacola.



PRIMERO: posición en el vector que indica donde esta el primer elemento de lacola.MAXIMO: tamaño del vector o máximo número de elementos de la COLA.

los dif erentes estados de una cola se muestran a continuación:

ejemplo, regresar

COLAS REPRESENTADAS COMO VECTOR CIRCULAR

Para hacer un uso más ef iciente de la memoria disponible se trata a la cola (elvector que la representa ) como una estructura circular.

En la representación de las colas en arreglos se manejan las siguientes variables:COLA, ULTIMO, PRIMERO y MAXIMO.

COLA : nombre del vector que sirve para representar la estructura.ULTIMO: posición en el vector que indica donde esta el ultimo elemento de lacola.PRIMERO: posición en el vector que indica donde esta el primer elemento de lacola.MAXIMO: tamaño del vector o máximo número de elementos de la COLA.

los dif erentes estados de una cola se muestran a continuación:



ejemplo, regresar

COLAS REPRESENTADAS COMO LISTASSIMPLEMENTE LIGADAS

para manejar la estructura cola como una lista simplemente ligada, se def ine unalista cuya dirección del primer nodo se guarda en una variable tipo punterollamada cola y la dirección del último nodo se guardará en una variable de tipo

puntero llamada ultimo. Las operaciones de encolar y desencolar se realizarán dela siguiente manera:

para encolar un dato se actualiza la liga del último nodo, agregando de estamanera el nuevo dato al f inal de la lista.

para desencolar un dato se extrae el dato al principio de la lista.

BURBUJA1

Es el metodo mas utilizado por los estudiantes principiantesde computación, por su f ácil comprensión y programación. pero es probablemente el método mas inef iciente.La idea básica de este algoritmo consiste en comparar paresde elementos adyacentes e intercambiarlos entre sí hasta quetodos se encuentren ordenados. se realizan ( N-1 ) pasadas,transportando en cada una de las mismas el menor o mayor elemento (según sea el caso) a su posición ideal.



al f inal de las (N-1) pasadas los elementos del arreglo estaránordenados.

BURBUJA2

Es el metodo mas utilizado por los estudiantes principiantes de computación, por su f ácil comprensión y programación. pero es probablemente el método masinef iciente.La idea básica de este algoritmo consiste en comparar pares de elementosadyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. serealizan ( N-1 ) pasadas, transportando en cada una de las mismas el menor omayor elemento (según sea el caso) a su posición ideal.al f inal de las (N-1) pasadas los elementos del arreglo estarán ordenados.

BURBUJA CON SEÑAL

Este método es una modif icación del método de burbuja. La idea central de estealgoritmo consiste "en utilizar una marca o señal para indicar que no se ha producido ningúnintercambio en una pasada. "

Es decir, se comprueba si el arreglo está totalmente ordenado despues de cada pasada. "

terminando su ejecución en caso af

irmativo.

SACUDIDA

Es una optimización del método de intercambio directo. La idea basica de estealgoritmo consiste en mezclar las dos f ormas en que se puede realizar el métodode la burbuja.En este algoritmo cada pasada tiene dos etapas. En la primera etapa (de derecha aizquierda) se trasladan los elementos más pequeños hacia la parte izquierda delarreglo, almacenando en una variable la posición del ultimo elemento

intercambiado.En la segunda etapa(de izquierda a derecha) se trasladan los elementos másgrandes hacia la parte derecha del arreglo, almacenando en otra variable la

posición del ultimo elemento intercambiado. Las sucesivas pasadas trabajan conlos componentes del arreglo comprendidos entre las posiciones almacenadas enlas variables.El algoritmo termina cuando en una etapa no se producen intercambios o bien,



cuando el contenido de la variable que almacena el extremo izquierdo del arregloes mayor que el contenido del la variable que almacena el extremo derecho"

SELECCION

La idea básica de este algoritmo consiste en buscar el menor elemento del arregloy colocarlo en la primera posición.Luego se busca el segundo elemento más pequeño del arreglo y se coloca en lasegunda posisión. El proceso continúa hasta que todos los elementos del arreglohayan sido ordenados.

INSERCION

Es el metodo que generalmente utilizan los jugadores de cartas cuando ordenan

estas.La idea central de este algoritmo consiste en insertar un elemento al arreglo a lavez y ubicarlo el la posicion indicada.este proceso se repite desde el segundo hasta el n-esimo elemento. "

INSERCION BINARIA

El método de ordenación por inserción directa puede mejorarse f ácilmente.Para ello se recurre a una búsqueda binaria en lugar de una búsqueda secuencial

para isertar un elemento en la parte izquierda del arreglo, que ya se encuentra

ordenado. El proceso se repite desde el segundo hasta el n-esimo elemento. "

QUICKSORT

El metodo de ordenación quicksort es actualmente el más ef iciente y veloz de losmétodos de ordenación interna.La idea central de este algoritmo consiste en los siguiente :1. Se toma un elemento X de una posición cualquiera del arreglo2. Se trata de ubicar a X en la posicion correcta del arreglo, de tal f orma quetodos los elementos que se encuentren a su izquierda sean menores o iguales a Xy todos los elementos que se encuentren a su derecha sean mayores o iguales a X.3. se repiten los pasos anteriores pero ahora para los conjuntos de datos que seencuentran a la izquierda y a la derecha de la posición correcta de X en el arreglo.4. El proceso termina cuando todos los elementos se encuentran en su posicióncorcecta en el arreglo.

SHELL



En el metodo de ordenación por inserción directa cada elemento se compara paraus ubicación correcta en el arreglo con los elementos que se encuentran en la

parte izquierda del mismo.Si el elemento a insertar es más pequeño que el grupo de elementos que seencuentran a su izquierda, es necesario ef ectuar entonces varias comparaciones

antes de su ubicación.SHELL propone que las comparaciones entre elementos se ef ectúen con saltos demayor tamaño pero con incrementos decrecientes, así, los elementos quedaránordenados en el arreglo más rapidamente."

Fundamentos-De-programacion Ordenamientos y Vectores

Documents

Transcript of Fundamentos-De-programacion Ordenamientos y Vectores