Diapositiva PPT
2.2.2. Implementación mediante listas enlazadas.
- Miembro (x, A)
- Puesto la lista está ordenada, sólo es necesario buscar hasta encontrar x o un elemento mayor que x.
- En el caso medio necesitaremos buscar n/2 posiciones: O(n).
act:= Primero(A);
Mientras (act ? Nil) y (act ? x) hacer
Si (x=act) entonces devolver Verdad;
Sino act:= Siguiente(act, A);
Devolver Falso;
- Intersección (A, B, C)
- Buscar un elemento x de A en B: sólo hasta llegar a x o un elemento mayor.
- Si d es un elemento de A que precede inmediatamente a x, y se ha encontrado en B un elemento f tal que d ? f, para buscar x en B se puede empezar desde f.