• BUSQUEDA:

Estos métodos son requeridos para poder realizar las siguientes operaciones en las estructuras de datos formadas por archivos y tablas:

• Agregar elementos

• Borrar elementos

• Consultar elementos :

  • modificación de un elemento existente (escritura)

  • obtención de los datos de un elemento existente (lectura)

  • revisión de la existencia de un elemento (verificación)
    

La operación de búsqueda sobre una estructura de datos es aquella que permite localizar un nodo en particular si es que éste existe.

Búsqueda por Transformación de Llaves:<;br>
Esta técnica conocida como hash está basada en la idea de calcular una dirección en forma directa a partir de la llave de un nodo. Con este método se tiene tiempo de búsqueda independiente del número de nodos en la estructura y su eficiencia es proporcional al tiempo utilizado para llevar a cabo la transformación.

Existen muchas funciones de transformación, pero las cuatro funciones siguientes son importantes porque pueden usarse sin que se conozca previamente la distribución inicial de los nodos y utilizan las llaves o parte de las mismas, independientemente de si son numéricas o alfabéticas:

• COLAS:

Una cola es una estructura de almacenamiento, donde la podemos considerar como una lista de elementos, en la que éstos van a ser insertados por un extremo y serán extraídos por otro.

La cola lineal es un tipo de almacenamiento creado por el usuario que trabaja bajo la técnica FIFO (primero en entrar primero en salir).

Las operaciones que podemos realizar en una cola son las de inicialización(o creacion), inserción y extracción.

Operaciones:

1. INSERCIÓN ( INSERT(q,x) ): Adiciona un elemento x en la parte posterior de la cola q. Esta operación siempre se puede realizar puesto que no existe límite en cuanto el numero de elementos que puede contener una cola.

2. EXTRACCION ( x := REMOVE(q) ): La cual retira el elemento del frente de la cola q y coloca en x su contenido. Esta operación se puede aplicar unicamente si la cola no esta vacía, es decir no existe forma de remover un elemento de una cola que no contiene elementos.

• LISTAS:

Una LISTA es una estructura de datos dinamica. El numero de nodos en una lista puede variar dramaticamente a medida que los elementos son insertados o removidos. La naturaleza dinamica de una lista contrasta con la estructura estatica de un arreglo cuyo tamaño es constante.

Una Lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada uno contiene datos y un enlace o liga.

Un nodo es una secuencia de caracteres en memoria dividida en campos (de cualquier tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo de información si este existe.

Un apuntador es la dirección de memoria de un nodo. La lista enlazada o encadenada completa es accesada desde un puntero "externo"(no esta incluido dentro del nodo, en su lugar se puede accesar directamente al hacer referencia a una variable) de la lista que apunta hacia(contine la direccion de) el primer nodo en la lista.

El campo de dirección siguiente del ultimo nodo en la lista contiene un valor especial llamado NULO, el cual no es una direccion valida. Este PUNTERO NULO es utilizado para señalar el final de una lista.

La lista sin nodos se denomina LISTA VACIA o LISTA NULA. el valor del puntero externo de la lista es el puntero nulo. Por consiguiente una lista puede ser inicializada como lista vacia lediante la operacion list := nil.

Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:

1. INSERCION: Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:

• Insertar un nodo al inicio.
• Insertar un nodo antes o después de cierto nodo.
• Insertar un nodo al final.

2. BORRADO. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:

• Eliminar el primer nodo.
• Eliminar el último nodo.
• Eliminar un nodo con cierta información.
• Eliminar el nodo anterior o posterior al nodo cierta con información.

• PILAS:

Una PILA o STACK es una coleccion ordenada de elementos en la cula es un extremo se pueden insertar nuevos elementos y de la cual se pueden retirar otros, llamado la parte superior de la pila.

Las Pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a la posición en la cual pueden realizarse las inserciones y las extracciones de elementos.

Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.

Las operaciones basicasdentro de las Pilas son Push y Pop.

1. PUSH: �060;font size="3" face="CAC Futura Casual">Cuando se agrega un elemento a la lista este es empujado (pushed) dentro de la pila. Dadas una pila "s" y unelemento "i", la operación Push(s,i) se define como la acción de agregar el elemento "i" a la parte superior de la pila "s".

2. POP: Esta operacion retira el elemento superior y lo regresa como un valor de la funcion

• ORDENAMIENTO POR

BURBUJA:

El ordenamiento burbuja es quizá el método de ordenamiento de vectores más conocido por los programadores. Existen diferentes tipos de ordenamiento burbuja.

Este tipo de ordenamiento se basa fundamentalmente en un ordenamiento de tipo ascendente. Como su nombre lo indica, todo el ordenamiento es basado en una especie de inserción y el comportamiento interno del vector es como el de una burbuja. Se basa en dos apuntadores y en una variable auxiliar. En un inicio, un apuntador inicial 'x' empieza a recorrer el vector desde la posición inicial (en nuestro caso la llamaremos uno, pero para C++ será la posición cero) hasta la posición anterior a la final, y un apuntador 'y' que recorrerá el vector desde la posición  ' i +1 '  hasta la posición final, siendo esta un valor conocido anteriormente (N). Estos apuntadores recorrerán el vector e irán comparando los valores de la posición en que se encuentra cada uno y si el valor de la  posición  V[ i ]  es mayor que el de la posición V[ j ], intercambiarán sus valores utilizando la ayuda de la variable auxiliar (aux).
 

• ORDENAMIENTO POR

EMBUDO:

Es similar al de burbuja, pero las pasadas se alternan:

• Una para colocar la llave (o dato) menor:

1. De derecha a izquierda si los datos se acomodan de forma horizontal.
2. De abajo hacia arriba si los datos se acomodan de forma vertical.

• Otra para la llave mayor:

1. De izquierda a derecha si los datos se acomodan de forma horizontal.
2. De arriba hacia abajo si los datos se acomodan de forma vertical.

• ORDENAMIENTO POR

HEAP SORT:

• Un heap es un árbol binario completo al que pueden faltarle algunas de las hojas situadas más a la derecha en el último nivel.
• Este método se basa en la construcción de esta estructura llamada heap y en un recorrido de la misma llamado borrado del heap.
• En cualquier nodo del árbol, el dato es mayor que los que se encuentran en sus subárboles (nodos hijos).

• El algoritmo para borrar el heap consiste en remover el dato en la raíz e intercambiarlo con otro nodo, nivel por nivel, de abajo hacia arriba y de derecha a izquierda.
• Una vez construida la estructura del heap nunca cambia, sólo se acomodan todos los elementos de modo que el dato con el que se intercambia la raíz debe ser acomodado dentro del árbol considerando sólo los nodos activos.
• El número de comparaciones para la construcción del heap en el peor de los casos es de (n-1) 2d, donde d=|log n|-1.
• El algoritmo de borrado del heap realiza en el peor de los casos 2(n-1)d comparaciones.
• En forma general, el algoritmo tiene un promedio de comparaciones proporcional al n log2 n.
• El algoritmo heapsort utiliza memos memoria adicional de la que requiere el algoritmo de selección repetitiva.

• ORDENAMIENTO POR

INSERCION BINARIA:

El método de ordenamiento por inserción binaria es una mejora del ordenamiento por inserción directa. Para lograr esta mejora se recurre a una búsqueda binaria en lugar de una búsqueda secuencial para insertar un elemento en la parte izquierda del arreglo, que ya se encuentra ordenado. El resto del procedimiento es similar al de inserción directa, es decir, se repite este mismo procedimiento desde el segundo término hasta el último elemento.
 

• ORDENAMIENTO POR

MERGE:

El caso del MergeSort (Mezcla)une dos estructuras ordenadas para formar una sola ordenada correctamente.
Tiene la ventaja de que utiliza un tiempo proporcional a:
n log (n), su desventaja radica en que se requiere de un espacio extra para el procedimiento.

Este tipo de ordenamiento es útil cuando se tiene una estructura ordenada y los nuevos datos a añadir se almacenan en una estructura temporal para después agregarlos a la estructura original de manera que vuelva a quedar ordenada.

Procedimiento MergeSort
/*recibe el arreglo a ordenar un índice r que indica el límite inferior del arreglo a ordenar y un índice l que indica el límite superior*/
void mergesort(int a[], int l, int r)
{
   int i,j,k,m;
     if (r > l)
            {
                m = (r+l) /2;
                mergesort(a, l, m);
                mergesort(a, m+1, r);
                  for (i= m+1; i > l;i--)
                       b[i-1] = a[i-1];
                  for (j= m; j < r;j++)
                       b[r+m-j] = a[j+1];
                  for (k=l ; k<=r; k++)
                     a[k] = (b[i] } a="{a,s,o,r,t,i,n,g,e,x,a,m,p,l,e}"a,e,e,l,m,p,x}                                                    e,l,p} l,p,a,e,m,x, a,m, e,x, a,g,i,n,o,r,s,t,                                                    g,i,n,t, g,n, i,t, a,o,r,s,o,r, {a,s, b[j--]; :                                                    b[i++] ?>

• ORDENAMIENTO POR

PARES Y NONES:

• Primero se comparan los datos nones con su sucesor y se les intercambia si es necesario.
• Después se comparan los datos pares con su sucesor y se les intercambia si es necesario.
• Este proceso se repite hasta que en ambas pasadas no se encuentre un intercambio.

• ORDENAMIENTO POR

QUICK SORT:

El algoritmo quicksort es quizá el más eficiente de los algoritmos de ordenamiento, debido a que su complejidad es mínima y por lo tanto su tiempo de ejecución también es mínimo.

El ordenamiento quicsort está basado en el principio de guerra "DIVIDE Y VENCERÁS". Este procedimiento es en realidad muy sencillo y se desarrolla así:

La idea principal es dividir la lista en dos sub-listas y ordenarlas en forma independiente cada una. El proceso de partición es repetido hasta llegar a listas de tamaño 1 (que están ordenadas).

Lo central en este método es encontrar un método eficiente para particionar la lista en dos partes, tal que:

• Todos los elementos de una sub-lista deben ser menores que un elemento llamado pivote.
• Todos los elementos en la otra sub-lista deben ser mayores que el pivote.

• ORDENAMIENTO POR

RADIX SORT:

Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan.

Por ejemplo el número 235 se escribe 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades.

Reglas para ordenar.

• Empezar en el dígito más significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números.

• El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales).

Ventajas.

• El ordenamiento es razonablemente eficiente si el número de dígitos en las llaves no es demasiado grande.

• Si las máquinas tienen la ventaja de ordenar los dígitos (sobre todo si están en binario) lo ejecutarían con mucho mayor rapidez de lo que ejecutan una comparación de dos llaves completas.

• ORDENAMIENTO POR

SHELL:

Denominado así por su desarrollador Donald Shell (1959), ordena una estructura de una manera similar a la del Bubble Sort, sin embargo no ordena elementos adyacentes sino que utiliza una segmentación entre los datos. Esta segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor grande (pero menor al tamaño total de la estructura) y van disminuyendo hasta llegar al '1'. Una secuencia que se ha comprobado ser de las mejores es: ...1093, 364, 121, 40, 13, 4, 1. En contraste, una secuencia que es mala porque no produce un ordenamiento muy eficiente es ...64, 32, 16, 8, 4, 2, 1.