Stoichkov
10-05-2011, 18:39
Hola a todos!! necesito ayuda con el tema de memoria dinámica. Tengo que hacer un programa que cree una lista doblemente enlazada(ordenarla hacia delante y hacia atrás) lo que no tengo muy claro es situar los punteros. Alguien tiene idea de cómo hacerlo??? Un saludo!"
Lo que quieres no es nada fuera de lo común... sólo hacía falta una búsqueda en google:
http://c.conclase.net/edd/index.php?cap=005
Un saludo.
Stoichkov
10-05-2011, 19:20
Gracias por responder. Sí lo que dices eso ya lo sé... pero mi duda es a la hora de introducir
[B]int dato[B] que se ordene conformo los voy metiendo, voy a repasarlo despacio a ver si lo entiendo. Un saludo hystd!!!
Tienes dos funciones que implementar para mantener siempre el orden de tu lista:
Insertar(dato)
Borrar(dato)
Con la inserción, se trata de buscar la posición en tu lista en donde irá el dato. Se presupone que los datos que se manejan permiten la ordenación (son enumerables).
Para buscar esa posición simplemente tienes que recorrer tu lista, pero nota que lo harás de forma dicotómica (búsqueda binaria), pues tu lista siempre estará ordenada.
Supongamos que está ordenada ascendentemente. Si el dato es mayor, buscarás en la mitad superior, y si no, en la mitad inferior (tomando como referencia el elemento central), el cual puede obtener mediante la longitud de tu lista entre 2 (La longitud puedes almacenarla en una variable externa y con cada inserción sumas 1, y con cada borrado, restas 1, hasta 0).
Una vez localizas la posición, simplemente actualizas las referencias "anterior" y "siguiente" de los elementos. Ejemplo:
|ant|dato|sig|...|ant|dato|sig||ant|dato|sig||ant| dato|sig|...|ant|dato|sig|
En rojo están los extremos (principio y fin de mi lista). En negrita es donde debe ir el nuevo dato a insertar.
|ant| del nuevo dato debe apuntar a |sig| del elemento anterior. Si no tiene elementos anteriores, |ant| del nuevo dato será "null", es decir, será el primer elemento de mi lista.
|sig| del dato anterior debe apuntar a |ant| del nuevo dato.
|sig| del nuevo dato debe apuntar a |ant| del dato siguiente. Si no hay dato siguiente, |sig| será "null", pues será el último elemento de mi lista.
|ant| del dato siguiente debe apuntar a |sig| del nuevo dato insertado.
Haciéndolo así, te asegurarás de tener siempre tu lista ordenada.
Con el borrado, procedes igual, actualizando las referencias |ant| y |sig| con las de los elementos inferior y posterior respectivamente.
Un saludo.
Stoichkov
12-05-2011, 17:43
Ok gracias hystd Algo parecido estoy intentando hacer. Un Saludo!!