Ingeniero

Taller listas

Algoritmos y estructuras de datos I

En cada caso realice el algoritmo, recuerde que no es necesario codificarlo en ningún lenguaje, basta con escribirlo en seudocódigo.

1. Dada una lista simplemente ligada, escriba un algoritmo que calcule el promedio de los números que se encuentran en las posiciones impares, es decir en la posición 1, 3, 5…

2. Se tiene una lista doblemente ligada y la dirección de un nodo interno, cuente el número de nodos que hay a la izquierda y el número de nodos que hay a la derecha del nodo dado.

3. En una lista circular, dada la dirección de cualquiera de sus nodos; calcule el promedio de la lista e identifique el menor número de la lista.

Solución

1)

Inicio

Contador← 1

sumar← 0

P← primero

Mientras P <> null hacer

Si (“contador mod 2 <> 0”)

Leer INFO(P)

Suma ← suma+ INFO(P)

Contador ← contador +1

Fin si

P← SIG(P)

Fin mientras

Promedio ← suma/contador

Escribir (“promedio”)

fin

2)

Inicio

posicion ←P

int←encontrado

P← primero

encontrado← 0

contador←0

contador←1

mientras ((p <> null) && (no. Encontrado))

Si (P→ elemento =x)

encontrado ←1

Sino P= P→ siguiente

Fin Si

mientras (p <>null)

p= p→ siguiente

contador← contador 2+1

Fin mientras

Escribir (“ nodos a la izquierda: “contador 1”, y nodos a la derecha: , “contador 2”)

Fin proceso

3)

Inicio

Contador ← 1

suma← 0

P ← PRIMERO

Leer (INFO (P))

Info (P) ← menor

Si (ptr <>null)

Cabeza ← ptr → adelante

Hacer

Si (cabeza → x = busca)

K← k+1

Fin si

Leer INFO (P)

suma←+INFO (p):

Si (INFO (P) < menor)

menor← INFO (P)

Fin si

cabeza← cabeza → adelante

Mientras (cabeza <> ptr→ adelante)

Sino

Escribir 8” no esta el elemento en la lista”)

Fin si

promedio← suma/ contador

Escribir (“promedio”)

Escribir (“menor”)

Fin proceso

...