Lista de listas en FreePascal

Aziwar #1 Jun '09 Inocente

Buenas! Alguien me puede decir como trabajar con una lista de lista en freepascal? insertar,buscar...etc

Se hacer arrays de listas pero no consigo hacer que funcione lista de listas.

Por ejemplo suponiendo la siguiente estructura:

TListaPtr = ^TLista;

TLista = record
	dato : integer;
	siguiente : TListaPtr;
	end;

TLista2Ptr = ^TLista2;

TLista2 = record
	lista : TLista;
	siguiente : TLista2Ptr;
	end;

Como pedir memoria para insertar nuevos elementos, etc. Es que siempre acabo teniendo runtime xD

B

[Borrado] #2 Jun '09

En pascal la memoria se reserva con un new() si no recuerdo mal.

Aziwar #3 Jun '09 Inocente

si y para borrarlo dispose, pero digo como hacer para por ejemplo simular una matriz con listas en vez de arrays

B

[Borrado] #4 Jun '09

A ver, no sé si te entiendo. Tú quieres hacer una lista de listas no? (Una multilista). Pues para eso lo que tienes que hacer es definir una lista cuyo contenido sea otra lista. Es que no entiendo la duda xD

Puni #5 Jun '09

De pascal no tengo ni idea, pero sin genericidad chungo, en cualquier lenguaje normal harias una lista de forma q los nodos ademas de un enlace al siguiente (y al anterior si es doblemente enlazada) contengan un tipo generico en el q en tiempo de ejecucion pudieras guardar un int, un float o en este caso una lista.

m0rG #6 Jun '09

Es lo que dice #5,una lista enlazada .Como supongo que será una práctica del primer año de la carrera no tienes que preocuparte del tipo de dato que guarda cada celda,sólo pensar como ir enlazando elementos,cómo acceder a ellos,cómo borrarlos etc...Una cosa que ayuda mucho (al menos a mí) es visualizar el problema con algún dibujo.Te dejo uno hecho en paint en 2 minutos de lo que podría ser una lista de listas enlazadas:

Empiezas por crear el tipo TListadeListas (o como lo llames) que no es más que una estructura con 2 punteros;uno a la primera lista y otro a la última (puedes hacer una versión más simple con un sólo puntero a la primera).TLista es una estructura que sólo tiene 3 punteros;uno a la siguiente lista (la última a nil) otro al primer elemento que guarda esa lista (TCelda) y otro al último(como antes puedes omitir este).Por último TCelda es una estructura con un puntero a la siguiente celda y lo que quieras guardar en ella (un int,una tabla,cualquier cosa).

Una vez pensado esto simplemente tienes que pensar las operaciones que se pueden hacer sobre este tinglado.Por ejemplo añadir una nueva lista al principio de la lista de listas.Tendrías que crear una función estilo:

añadirListaPrincipio(TListadeListas ^{listaDeListas})
{
TLista ^aux;
new(aux);
aux->siguiente=listaDeListas->prim; //El siguiente elemento a la nueva lista era el antiguo primero.
listaDeListas->prim=aux;
};

La sintaxis es una mezcla rara de C y Pascal así que no va a funcionar,tómala como si fuera pseudo-código xDD.Simplemente usas un puntero auxiliar para crear la nueva lista (y la inicializas por cierto) inicializando su puntero a la siguiente lista a la que era hasta entonces la primera lista.Así vas pensando todas las operaciones y sale .

JuAn4k4 #7 Jun '09

Si quieres matrices de dimensiones diferentes en ejecucion, reserva todo el tamaño de la matriz a la vez para que te de memoria contigua y puedas acceder mejor.

Hacer una matriz como lista de listas es un poco gore, más si reservas memoria celdita a celdita, te puedes morir si la matriz es grande.

¿ Para que quieres una estructura asi ?

Listadelistas puntero a Tlista2

Tlista2 es un registro de
una Tlista
una Tlista2

Tlista es un registro de
un dato
una Tlista

B

[Borrado] #8 Jun '09

Estoy con #7, y si aún así quieres hacerlo lo que yo te quería decir es lo de #6 pero sin explicar tan bien. Basicamente tienes que ir haciendo new desde el ultimo puntero de cada sublista para añadirlos todos. (Vamos, para una 4x4 hay que reservar memoria para la lista principal, cuatro nodos, y para cada uno de ellos otros tres [el primero ya está reservado]).

Aziwar #9 Jun '09 Inocente

A mi me da que lo que me falla es al pedir la memoria. Mañana pruebo como puso #8 a ver como funciona (el examen lo tengo mañana por la tarde..xDD)

Puni #10 Jun '09

pero vamos a ver, la gracia de las listas (salvo q las implementes en memoria estatica en un array) es precisamente q son dinamicas, tu no necesitas saber q tamaño quieres, vas añadiendo o quitando elementos en tiempo de ejecucion y por tanto solo tendras q reservar memoria cada vez q crees un nuevo nodo de la lista.

al crear la lista deberias guardar una referencia al primer elemento y como mucho tb al ultimo y poco mas. luego segun añadas elementos o los quites iras reservando o liberando memoria.

B

[Borrado] #11 Jun '09

Es lo que dice #10, yo en pascal lo que hacía era programarme un módulo, en el definía la lista y las funciones (crear lista, eslistavacia, buscar, añadir...) y definía el tipo también (es el fallo de pascal, que no tiene generidad xD). Entonces para añadir nodos a una multilista hacía así:

Supongamos que tenemos una lista principal L y tres secundarias L1, L2, L3. Pues bien, si queremos dimensionarla a 3x3 (auque como dijo #7, no tiene mucho sentido), simplemente añadimos nodos. Te pondría cómo hacía con las funciones pero ya no me acuerdo, tendría que mirarlo y tengo un examen el miércoles y otro el jueves xD

JuAn4k4 #12 Jun '09

#10 Imaginate que trabajas con matrices cuasi-vacias, de esas con muchos 0's, pues cuando la lees ( normalmente de fichero ) no sabes que tamaño tiene y sin embargo siempre preferiras tener toda la memoria contigua , pues en lugar de hacerlo asi el chaval igual quiere hacer una lista de listas por no saber el tamaño.. no se si me explico.

Yo solo le planteaba la posibilidad de que no necesitara una lista de listas.

¿ Podrias decir para qué necesitas dicha estructura ? Porque ya tiene que ser especial.

Aziwar #13 Jun '09 Inocente

A ver... no tengo que realizar ninguna matriz ni nada, el problema original de la práctica que suspendí era simular un supermercado en el que tuviera una lista de cajas, y dentro de cada caja una lista de personas.

Dije lo de la matriz porque creí que era el modo más fácil de ver lo que quería decir xD

Puni #14 Jun '09

Pues con ese problema yo lo haria de la siguiente manera:Un array de colas.
El array simula las cajas q tienes, q sabras cuantas son desde el principio o lo pides al usuario por teclado y tal. Y luego en si el funcionamiento de la caja es mucho mas logico con una cola, q viene siendo una lista mas facil de implementar, solo sacas elementos por la cabecera con lo q no necesitas metodo borrar y vas añadiendolos por la cola segun llegan.

JuAn4k4 #15 Jun '09

Ves como al final tenia razon que no necesitabas una lista de listas.

Si solo tienes que simular sin sacar medidas, no necesitas listas ni nada por el estilo.

Necesitas un vector de "registro"

Un entero: te marca cuantos clientes hay en la cola esperando.
Y si necesitas mas informacion pues la pones, que no creo, aunque si te piden ciertas medidas o indices de prestaciones ( tiempo medio de servicio , numero maximo de clientes ) puedes meter mas.

Si te piden tiempo medio de espera, si necesitas una lista.

¿ Que más te piden ?

Aziwar #16 Jun '09 Inocente

A ver... q no habeis entendido nada.. ese problema se puede hacer facilmente con 2 arrays o con un array de colas. Pero tiene que ser con una lista de lista pq asi lo piden, si no no hubiera problema.

Y esa es la estructura que no se manejar, una lista de lista, siempre acabo con runtimes por la memoria

DaRk-eXe #17 Jun '09

#6 +1, simplemente.

Si tienes mas dudas con lo que ha dicho #6.. mandame un MP y te hecho una mano con algun crokis y demas.

JuAn4k4 #18 Jun '09

Si es obligatorio usar lista de listas la cosa cambia.

Tienes que tener 2 tipos de Nodos.

Lista1(supermercado): Puntero a Nodo1
Nodo1(cajero):
Puntero a Lista2 (cola)
Puntero a Nodo1 (siguienteCajero)

Lista2(cola):
puntero a Nodo2 (primero ).
puntero a Nodo2( ultimo )

Nodo2(cliente):
dato (dato)
punetro a nodo2 (siguienteCliente)

Si te da runtime error es porque no haces NEW en todos los sitios bien.

Nuevo cliente en la caja "n":

comprobar que el super esta inicializado ( supermercado != null)

comprobar que tienes n cajeros.
L=supermercado.primero;
( bucle mq L.siguiente !=NULL AND THEN iteraciones < n ) L = L.siguiente;

si sales con L=NULL -> no hay cajero "n".
Obtener la cola del cajero n. (lacola)
lacola = L.cola;

anadir cliente al final : {
1º Crear el nodo -> nuevoCli = New (Nodo2);
nuevoCli.siguiente = NULL;
nuevoCli.dato = eldato;
2º Asignarlo:
si lacola.ultimo = NULL -> [lacola.primero = nuevoCli; lacola.ultimo = nuevoCli; ]
otro caso [lacola.ultimo.siguiente = nuevoCli; lacola.ultimo = nuevoCli;]
}

Para el main:

Inicializar supermercado:
Nuevo cajero:
si supermercado = null -> creas un nodo y se lo asignas al primero y ultimo de la cola supermercado.
Si supermercado != null -> se lo pones al ultimo.

etc..

DaRk-eXe #19 Jun '09

si lo unico que tienes que hacer es implementar el dibujo de #6 es que mas claro es imposible xD

edit:

Supongo que sabes manejar uan lista simple no? pues solamente tienes que hacer que los elementos de la lista sean otras listas :\ y lo de siempre.. borrado por un lado e insertado por el otro..

voy a ver si te escribo algo aunque no me acuerdo de la nomenclatura exacta de pascal.. lo mismo te hago un boceto en C xD.

croquis

estructura

//cabecera
struct lista_[tip]_cab{
	struct lista_[tip]_rep* prim;
	struct lista_[tip]_rep* ulti;
}

//lista
struct lista_[tip]_nodo{
	struct lista_[tip]_sub* nodo;
	struct lista_[tip]_nodo* sig;
//si lo quieres doblemente enlazado pues añades:
	struct lista_[tip]_sub* nodoulti;
}

//sublista
struct lista_[tip]_sub{
	[tip] valor;
	struct lista_[tip]_sub* sig;
}

typedef struct lista_[tip]_cab *lista_[tip];
typedef struct lista_[tip]_rep *lista_[tip]_rep;
typedef struct lista_[tip]_sub *lista_[tip]_subnodo;

crea y mete

Para crear la lista.. pues simplemente...

lista_[tip] lista_[tip]_crea() {
	
lista_[tip] nuevo;

nuevo=new struct lista_[tip]_cab;
if (!nuevo) {
	throw error;
}
nuevo->prim=nuevo->ulti=NULL;
return nuevo;
}

//funcion privada para crear nodos principales
lista_[tip]_rep lista_[tip]_creaNodoPrincipal() {
	
lista_[tip]_rep nuevo;

nuevo=new struct lista_[tip]_nodo;

if (!nuevo) {
	throw error;
}
nuevo->sig=null;
nuevo->nodo=null;
nuevo->ulti=null;

return nuevo;
}

//funcion privada para crear nodos secundarios..

lista_[tip]_subnodo lista_[tip]_creaNodoSecundario() {
	
lista_[tip]_subnodo nuevo;

nuevo=new struct lista_[tip]_sub;

if (!nuevo) {
	throw error;
}
nuevo->sig=null;

return nuevo;
}

Para meter en la lista principal..

void lista_[tip]_metePrincipal(lista[tip] l) {

lista_[tip]_rep nuevo;	

if (!l) {
	throw error;
}

nuevo=lista_[tip]_creaNodoPrincipal();

if (!l->prim) {
	l->prim=l->ulti=nuevo;
}else{
	//supongamos que insertamos por el primero
	nuevo->sig=l->prim;
	l->prim=nuevo;
	//si insertamos por el final..
	l->ulti->sig=nuevo;
	l->ulti=nuevo;
}
}

Para meter una lista secundaria en un nodo principal dado (num)

void lista_[tip]_meteSecundario(lista_[tip] l,int num,dato e) {

lista_[tip]_rep iterador;
lista_[tip]_subnodo nuevo,temp;
int i=0;

if (!l) {
	throw error;
}
//buscamos el nodo en el que queremos insertar..
iterador=l->prim;
while(iterador)&&(i<num) {
	iterador=iterador->sig;
	i++;
}
//no se si se podrian dar las 2 condiciones a la vez.. por si acaso siempre puedes separarlo en 2 condicionales.
if (i=num)||(!iterador) {
	throw error;
}

//si no a saltado ningun throw.. es que hemos encontrado el nodo que buscamos..

nuevo=lista_[tip]_creaNodoSecundario() 

if (!nuevo) {
	throw error;
}
nuevo->valor=e;

//si no hay elementos..
if (!iterador->nodo) {

	iterador->nodo=nuevo;

}
//insertamos opr el primero
nuevo->sig=iterador->nodo;
iterador->nodo=nuevo;
//si insertamos por el ultimo.. como no tenemos sublista doblemente enlazada (porque no me apetecia...) y asi se trabaja un poco los bucles con listas :D
//nos posicionamos en el ultimo
for(temp=iterador->nodo;temp->sig;temp=temp->sig);

temp->sig=nuevo;
}

me aburria mucho.. lo acabo de escribir con el wordpad.. pero a simple vista diria que funciona o debiera... lo siento por estar en C, pero no rekuerdo la mitad de comandos de pascal.. pero no creo que te resulte dificil adaptarlo.. el tema de borrado es algo mas delicao, pero si te ves en apuros.. MP y veo si te puedo escribir algo.

Aziwar #20 Jun '09 Inocente

creo que ya se cual es el fallo, yo en vez de crear un tipo de dato TNodo por ejemplo hago por ejemplo lista^.ult.nodo^.ult.dato := dato xD

JuAn4k4 #21 Jun '09

pero que nombres mas raros pones :S


// Puedes obviar esta estructura e incorporarla a "cola/pcola" pero yo lo veo mas claro asi.
typedef struct {
// O lo que quieras guardar de los clientes.
float tiempoLlegada;
}cliente, *pcliente;

// Nodo de una cola de clientes ( datos del cliente + siguiente cliente )
typedef struct {
pcliente cliente; // Datos del cliente
pcola siguienteCliente;
}cola,*pcola;

//Nodo de una lista de cajeros ( lista de clientes + datos del cajero + siguiente cajero )
typedef struct {
// Datos del cajero = null
pcola primerCliente;
pcola ultimoCliente;
pcajero siguienteCajero;
}cajero,*pcajero;

// El supermercado es una lista de cajeros ( Datos del supermercado + lista de cajeros )
typedef struct {
// Datos del super = null
pcajero primerCajero;
pcajero ultimoCajero;
} supermercado, *psupermercado;



/* El problema no creo que sea el definirlo pero bueno */
// Deberias tener estos dos procedimientos o funciones como los quieras hacer:

anadir(psupermercado, cajero);
anadir(pcajero, cliente);
// Tambien puedes tener
anadir(psupermercado, cliente, numeroCajero ); // Añadir al cajero n-esimo el cliente
// En ambos deberas comprobar todo lo que te dije antes


En todos tienes que hacer un "new" de una variable local y luego cambiar punteros del parametro por referencia, ya que el parametro por valor te lo "quitaran".

DaRk-eXe #22 Jun '09

#21 si lo de los nombres raros va por mi, es la nomenclatura que me enseñaron en la carrera xD y yo la encuentro bastante standar y facil de entender nose :\ xD

[tip] porke es de tipo generico sin instanciar.. (porque nose de que va el ejercicio que tiene que hacer.. asi que lo puse generico para que cambie [tip] por int,float, <random struct> )
cab de cabecera
rep de representante
nodo de nodo xD

será la costumbre supongo :\

JuAn4k4 #23 Jun '09

Para eso hazla generica y ponle un void *ELEMENTO xd es bromah

Pero no me gusta xD

DaRk-eXe #24 Jun '09

#23 se supone que es por la claridad a la hora de exportar el codigo y esos rollos.. si lees anadir(random parametros) pos no sabes exactamente que es.. y si pones lista_int_mete(adadsad) pues sabes que estas trabajando con listas dinamicas de enteros xD pero vamos.. tonterias que me obligaron a aprenderme.. si no fuera por eso.. yo seria el primero en poner metedatos(lalala) xD

JuAn4k4 #25 Jun '09

Para eso estan los nombres de identificadores.

anadir(&supermercado,cajero);
anadir(&cajero,cliente);

yo creo que queda bastante claro, no?

lista_supermercado_anadir(&supermercado,cajero);

suena redundante, no?

Usuarios habituales