Apuntes segundo parcial 14/11/2006 (Organización del Computador II)

Listas

Estructura de una lista

Sean las funciones

• procesar1 (nodo **p)
• procesar2 (nodo *p)

La primera permite agregar un nodo al principio, la segunda no. La primera da acceso al tipo lista, que contiene el puntero al 1er elemento.

Un nodo aislado no es una lista, debe existir el puntero al primer elemento. Si se toma el puntero a siguiente de un nodo, y ese nodo, entonces sí se tiene una lista.

Cuando se quiere pasar una lista por parametro, se pasa el puntero al puntero al primer nodo. O sea, si se tiene una estructura del tipo Lista->Nodo->Nodo..., entonces se pasa *Lista.

En procesar1, se sabe que el puntero recibido es distinto de null, porque se esta recibiendo el tipo lista. En procesar2, en cambio, si la lista es vacia, el puntero recibido es null. Asi, si se trabaja con doble referenciacion, se sabe que el 1er puntero nunca es nulo.

Funcion procesar recursiva:

procesar(p)
{
	Nodo* n = *p;
	f(& n->dato);
	procesar(& n->prox);
}

En assembler

procesar:
  
  push ebp
  mov ebp, esp
  
  mov eax, [ebp+8]
  mov ecx, [eax]
  
  push ecx
  call f
  add esp, 4
  
  lea ecx, [ecx+8]
  push ecx
  call procesar

Ojo: No se recorren las listas de forma recursiva, se utilizan ciclos. El ejemplo anterior es justamente eso, solo un ejemplo. La idea es no confundir si un registro apunta a un nodo a la direccion a la que apunta un nodo.

Cuando un registro tiene un puntero al nodo, para modificar una direccion se tiene que acceder a esa posicion mas el offset. Si tiene puntero al puntero, se accede directamente para modificar el puntero.

Ejemplo, para agregar un nodo. Se tiene en eax el puntero al puntero al nodo, en ebx se calcula el puntero al nodo, en ecx el puntero al nodo nuevo.

mov ebx, [eax]
ecx = malloc(size)
mov [ecx + offset], ebx
mov [eax], ecx

Si se quiere eliminar un nodo, tal que se tiene el puntero al puntero en eax, y el puntero al nodo en ebx.

mov ecx, [ebx + offset]
mov [eax], ecx
free(ebx)

Lo complicado en estos ejercicios es mantener los invariantes, es decir, que cosa esta apuntando a donde en todo momento; tanto luego de avanzar como de eliminar un nodo. Se debe agregar una linea mas al codigo anterior.

mov ecx, [ebx + offset]
mov [eax], ecx
free(ebx)
mov ebx, ecx

Ejercicios del parcial

Ejercicio de FPU

Se tiene una lista, cada nodo tiene 3 miembros: x, y, z. Se reciben 3 parametros: w, a, b. Se pide evaluar para cada nodo una expresion en punto flotante, del estilo (w^x + y^(log z))^b...

La primera parte del ejercicio consiste en dejar la parte precalculada de la operacion en la pila FPU. Luego se procesa elemento a elemento, aprovechando lo ya precalculado. Se toma como invariante de ciclo que en cada iteracion esten los mismos valores precalculados en los mismos lugares de la pila.

El resultado se pedira guardarlo en alguna posicion de memoria. A algun resultado intermedio se le pedira una comparacion (en FPU).

Es recomendable graficar la pila, de la forma mas prolija posible. Ante un error puede servir para mas benevolencia en la correccion.

En este ejercicio se evalua:

• Que la cuenta de la FPU este bien
• Que haya un solo load desde memoria por dato, tanto para los parametros como para los miembros del nodo
• El guardado en memoria
• La comparacion

Ejercicio de listas

Cosas que se pueden querer hacer con la lista:

• Recorrer la lista
• Crear una lista nueva, vacia o a partir de otra/s, reutilizando nodos
• Eliminar algunos nodos
• Agregar algunos nodos

Ejemplo 1

Se tiene una funcion complicada sobre los x[i]. Se pide:

1. x[i+1] - x[i] > E, entonces agregar un nodo intermedio con el valor del promedio
2. x[i+1] < x[i], entonces eliminar x[i+1], el nodo desordenado
3. f(x[i]) indefinida, entonces agrega el nodo a una nueva lista

Ejemplo 2: Quicksort

Se tiene el metodo separar tal que

input

una lista

output

1er elemento, lista con mayores, lista con menores

Luego se concatena separar(menores) + 1er elemento + separar(mayores)

Se efectua recursivamente el proceso hasta llegar a listas de uno o dos elementos, cuando se tiene todo ordenado.

Ejercicio de MMX

Entra en el parcial, pero no hay ningun ejercicio de este tema seguramente (guiño, guiño).