• Author / Uploaded
• jda_177

• Categories
• Programación de computadoras
• Algoritmos y Estructuras de Datos
• Áreas de informática
• Ingeniería de software
• Informática

Citation preview

Algoritmos y estructuras de datos Operaciones sobre listas enlazadas Todas las operaciones que se resumen a continuación trabajan sobre una lista enlazada de valores enteros cuyos nodos tienen la siguiente estructura. type // definicion del puntero a nodo PNodo = ^Nodo; // definicion del nodo Nodo = record v:integer; sig:PNodo; end;

Agregar un elemento a la lista Agrega un nodo con un valor x al final de la lista direccionada por p. agregar var p:PNodo; x:integer new(nuevo) nuevo^.v  x nuevo^.sig  nil p = nil p  nuevo

aux  p aux^.sig nil aux  aux^.sig aux^.sig  nuevo

R Agrega un elemento al final de la lista enlazada

procedure agregar(var p:PNodo; x:integer); var aux,nuevo:PNodo; begin new(nuevo); nuevo^.v:=x; nuevo^.sig:=nil; if( p=nil ) then begin p:=nuevo; end else begin aux:=p; while(aux^.signil) do begin aux:=aux^.sig; end; aux^.sig:=nuevo; end; end;

Recorrer y mostrar el contenido de una lista enlazada Recorre la lista direccionada por p mostrando el valor v que contiene cada uno de sus nodos. mostrar p:PNodo aux  p auxnil aux^.v aux  aux^.sig

R Recorre la lista y muestra el valor contenido en cada nodo

procedure mostrar(p:PNodo); var aux:PNodo; begin aux:=p; while( auxnil ) do begin writeln(aux^.v); aux:=aux^.sig; end; end;

Liberar la memoria que insumen los nodos de una lista enlazada Libera la memoria insumida por cada uno de los nodos de la lista direccionada por p. liberar var p:PNodo pnil sig  p^.sig dispose(p) p  sig

R Recorre la lista y libera cada uno de sus nodos

procedure liberar(var p:PNodo); var sig:PNodo; begin while(pnil) do begin sig:=p^.sig; dispose(p); p:=sig; end; end;

Determinar si la lista contiene un determinado valor Recorre la lista direccionada por p para determinar si existe al menos un nodo cuyo valor v coincida con el valor de x. Retorna un puntero al nodo que contiene el valor buscado o nil si ningún nodo lo contiene. buscar: PNodo p:PNodo; x:integer aux  p auxnil and aux^.v x aux  aux^.sig buscar  aux

R Recorre la lista para determinar si contiene o no un valor determinado

function buscar(p:PNodo; x:integer):PNodo; var aux:PNodo; begin aux:=p; while( (auxnil) and (aux^.vx)) do begin aux:=aux^.sig; end; buscar:=aux; end;

Eliminar un valor de la lista Recorre la lista direccionada por p para buscar y eliminar el primer nodo que contenga un valor igual a x. Si no existe ningún nodo con ese valor entonces no hace nada. eliminar var p:PNodo; x:integer aux  p ant  nil auxnil and aux^.vx ant  aux aux  aux^.sig auxnil antnil ant^.sig  aux^.sig

p  aux^.sig

dispose(aux)

R Elimina el nodo que contiene un valor determinado

procedure eliminar(var p:PNodo;x:integer); var ant,aux:PNodo; begin aux:=p; ant:=nil; while( (auxnil) and (aux^.vx) ) do begin ant:=aux; aux:=aux^.sig;

end; if( auxnil ) then begin if( antnil ) then begin ant^.sig:=aux^.sig; end else begin p:=aux^.sig; end; dispose(aux); end; end;

Insertar un valor respetando el ordenamiento de la lista Inserta un nodo con valor x en la lista direccionada por p respetando el criterio de ordenamiento de la lista. En esta implementación se respeta el orden de precedencia de los números enteros. La función retorna un puntero al nodo recientemente insertado. insertarOrdenado:PNodo var p:PNodo; x:integer new(nuevo) nuevo^.v  x nuevo^.sig  nil aux  p ant  nil auxnil and aux^.v