Algoritmos de lista

ALGORITMOS DE LISTA
OSCAR ANDRES SANCHEZ OVIEDO
UNIVERSIDAD DE CUNDINAMARCA
EXTENSION CHIA
COMPUTACION GRAFICA
V SEMESTRE
18 de septiembre de 2008
INTRODUCCION
El ordenamiento es una labor común que realizamos continuamente. ¿Pero te has preguntado qué es ordenar? ¿No? Es que es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar essimplemente colocar información de una manera especial basándonos en un criterio de ordenamiento.
En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Aquí voya mostrarte algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.
ALGORITMO
Definición:
Una lista es una estructura de datos secuencial.
Una manera de clasificarlas es por la forma de acceder al siguiente elemento:
lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array.
- lista enlazada:la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.
Una lista enlazada se puede definir recursivamente de la siguiente manera:
una lista enlazada es una estructura vacía o
un elemento deinformación y un enlace hacia una lista (un nodo). Gráficamente se suele representar así:
{draw:frame}
Como se ha dicho anteriormente, pueden cambiar de tamaño, pero su ventaja fundamental es que son flexibles a la hora de reorganizar sus elementos; a cambio se ha de pagar una mayor lentitud a la hora de acceder a cualquier elemento.
En la lista de la figura anterior se puede observarque hay dos elementos de información, x e y. Supongamos que queremos añadir un nuevo nodo, con la información p, al comienzo de la lista. Para hacerlo basta con crear ese nodo, introducir la información p, y hacer un enlace hacia el siguiente nodo, que en este caso contiene la información x.
¿Qué ocurre si quisiéramos hacer lo mismo sobre un array?. En ese caso sería necesario desplazar todos loselementos de información "hacia la derecha", para poder introducir el nuevo elemento, una operación muy engorrosa.


ALGORITMO DE PRIORIDAD
En los algoritmos de planificación existen los siguientes algoritmos:
Algoritmo FIFO
- Algoritmo SJF
Algortimo Round Robin
- y támbien está el algoritmo de Prioridad de el cual hemos realizado un Algoritmo y sus corridas quepresentamos a continuación, lo realizamos en Netbeens: Los procesos tienen prioridades asignadas, y el planificador escogerá aquel proceso con mayor prioridad.
Cuando un proceso debe ser seleccionado, el planificador por prioridades seleccionará aquel proceso que tenga mayor prioridad. Si hay más de un proceso entonces se deberá seguir alguna política de selección.
Un problema quepresenta un esquema de planificación por prioridades puro es que los procesos con la prioridad más baja pueden sufrir de inanición o bloqueo indefinido. Un proceso que está listo para correr pero espera porque siempre hay procesos con prioridad más alta.
Para evitar este problema, se puede ir incrementando gradualmente la prioridad de los procesos.
SJF es un caso especial de planificación porPrioridad, donde la prioridad es el inverso del valor estimado del próximo ciclo de CPU (a menor ciclo, mayor prioridad).
Los resultados del Algoritmo son los siguientes:


TDA LISTA
Una lista se define como una serie de N elementos E1, E2, ..., EN, ordenados de manera consecutiva, es decir, el elemento Ek (que se denomina elemento k-ésimo) es previo al elemento Ek+1. Si la lista...