TDA Lista de enteros I

TDA Lista de enteros I

Vamos a comenzar ésta serie de artículos desarrollando una lista de enteros en c. Esta estructura lineal tendrá la particularidad de tener tres punteros en la cabecera apuntando al inicio de la lista, al centro de la lista y al final de la lista.

Esta es la estructura de datos lineal más genérica que la pila y la cola que vimos en la serie de artículos anterior.

En nuestro caso particular,  la inserción de elementos se podrá hacer bien por el inicio de la lista, por el final o por ina posición intermedia que determinará el usuario.

lista lista_nueva ( )

precondicion: haya memoria para el nuevo objeto.
postcondicion: devuelve una lista nueva vacía.

int lista_vacia ( )

precondicion: la lista debe existir.
postcondicion: devuelve un valor distinto de cero si la lista no contiene ningún valor y cero en caso contrario.

void lista_mete ( lista c, struct l_enteros e, int donde )

precondicion: la lista debe de existir y debe de haber memoria para el nuevo elemento
postcondicion: añade un elemento nuevo a la lista con la condición de que si d>0 lo añadirá en la cabecera, si d<0, lo añadirá al final de la lista, y si d=0 lo añadirá detrás del elemento marcado. Si se introduce por elemento marcado y no hay ningún elemento den la lista, se asume que se insertará en la cabecera de la lista.


void lista_saca ( lista c, struct l_enteros *e, int donde )

precondicion: la lista debe existir y no estar vacía
modifica: *e
postcondicion: si donde<0 se elimina el primer elemento de la lista, si donde>0 se elimina  el último y si donde=0, entonces se eliminará el elemento marcado. Libera el elemento de memoria que se ha sacado siendo antes devuelto en *e.


void lista_dest ( lista *c )

precondicion: la lista debe existir.
modifica: *c.
postcondicion: libera la memoria asignada a la lista e inicializa el puntero *c=NULL.


lista lista_copyseg ( lista c, int ini, int fin )

precondicion: debe existir memoria para la nueva lista y la lista que se va a copiar debe de existir.
postcondicion: devuelve una copia de la lista que se pasa como argumento pero desde el número de elemento ini hasta el número de elemento fin ( esto es un subconjunto de la lista que se pasa como argumento ).


lista lista_copy ( lista c )

precondicion: debe haber memoria para la nueva lista y la lista que se le pasa como argumento debe existir.
postcondicion: devuelve una copia de la lista que se le pasa como argumento.


lista lista_corta ( lista c, int posicion )

precondicion: debe de haber memoria para la nueva lista y la lista que se le pasa como argumento debe existir. Posicion debe ser un indice dentro del rango de los elementos de la lista.
postcondicion: divide la lista en dos mitades. La lista devuelta comenzará en el indice posición.


lista lista_contat ( lista *c, lista *d )

precondicion: las dos listas que se le pasan como argumento deben existir.
modifica: *c y *d
postcondicion: devuelve una lista que resulta ser la concatenación de las listas que se le pasan como argumento.


lista lista_merge ( lista *c, lista *d )

modifica: *c y *d
postcondicion: devuelve una lista que es el resultado de aplicar el algoritmo merge entre las dos listas. A la salida *d=NULL. El valor devuelto coincide con *c. Esta función no chequea la existencia de ninguna de las listas.


void lista_mergesort ( lista *c )

modifica: *c
postcondicion: ordena la lista que se le pasa como argumento. No chequea la existencia de la lista ni realiza ningún control de memoria para las operaciones intermedias.


void lista_look ( lista c, struct l_enteros *e )

precondicion: la lista que se le pasa como argumento debe de existir.
modifica: *e
postcondicion: devuelve en *c el elemento marcado.


void l_next ( lista c )

precondicion:  la lista debe de existir y tambien debe de haber un nodo marcado
postcondicion: devuelve en *c el valor del elemento marcado.


int l_tama ( lista c )

precondicion:  la lista debe de existir
postcondicion: devuelve el número de nodos de la lista


int l_posi ( lista c )

precondicion: la lista debe de existir
postcondicion: devuelve la posición del nodo marcado


void l_marc ( lista c, int indice )

precondicion: la lista debe de exisitr y el valor deindice debe de estar dentro del rango de la lista
postcondicion: marca el nodo que ocupa la posición indice en la lista


int l_marcado ( lista c, int indice )

precondicion: la lista deve de existir.
postcondicion: devuelve distinto de cero si el elemento marcado ocupa la posición indice.

int l_find ( lista c, struct l_enteros *e )

precondicion: la lista debe de estar creada.
postcondicion: devuelve la posición del elemento *e en la lista. En caso de no existir, simplemente devuelve 0;

Para terminar éste artículo, voy a dejar el código fuente del archivo .h de nuestra estructura de datos.

#ifndef LISTA_ENTEROS
#define LISTA_ENTEROS


#define L_DER 1;
#define L_IZQ -1;
#define L_MED 0;

struct l_enteros {
	int x;
};

typedef struct l_dir *lista;

lista lista_nueva ( );
int lista_vacia ( );
void lista_mete ( lista c, struct l_enteros e, int donde );
void lista_saca ( lista c, struct l_enteros *e, int donde );
void lista_dest ( lista *c );
lista lista_copyseg ( lista c, int ini, int fin );
lista lista_copy ( lista c );
lista lista_corta ( lista c, int posicion );
lista lista_contat ( lista *c, lista *d );
lista lista_merge (  lista *c, lista *d );
void lista_mergesort ( lista *c );
void lista_look ( lista c,  struct l_enteros *e );
void l_next ( lista c );
int l_tama ( lista c );
int l_posi ( lista c );
void l_marc ( lista c, int indice );
int l_marcado ( lista c, int indice );
int l_find ( lista c, struct l_enteros *e );


#endif

Dejo abierta la sección de contactos para que me dejéis vuestras opiniones y aportaciones de código.

No Comments

Post a Comment