C/Visual C - Mitad de una lista doble

   
Vista:

Mitad de una lista doble

Publicado por Jhonny (10 intervenciones) el 30/07/2016 21:55:48
Hola amigos tengo el siguiente problema, de una lista doblemente enlazada, quiero saber cual es el nodo que esta en la mitad de la lista y su valor, ejemplo si tengo esta lista {4,5,6,8,9,1,3}, deberia imprimirme el 8.

He implementado estas dos funciones, una actualiza el nodo cada ves que se inserta un valor en la lista y otro para obtener el nodo de la mitad.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void ActMitad(bool mitad){
             if( cont == 0 ){
                  mit = NULL;
             }
             else{
             int remainder = cont%2;
             if(mitad){
                     if( remainder == 0 ){
                     mit = mit->prev;
            }
            }
            else{
                 if( remainder == 1 ){
                     mit = mit->next;
                     }
        }
 
             if( cont == 1 ){
                  mit = first;
             }
 
    }
}
		int avelider(){
    if( cont > 0 ) return mit->edad;
    else return -1;
}

Pero esto me da error, se queda pegada la ejecucion cuando inserto mas de un valor a la lista!

Alguna idea de porque sucede? Gracias.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Aarón Castillo

Mitad de una lista doble

Publicado por Aarón Castillo acuarium_329@hotmail.com (8 intervenciones) el 31/07/2016 20:48:58
No sé si hayas implementado tu lista ligada desde 0, si fue el caso te recomiendo que hagas esto:

1.- Crea un atributo global que indique el tamaño de la lista:
1
int tamanho = 0;

2.- Cada vez que agregues o elimines un elemento, incrementa automáticamente esa variable:

1
2
3
4
5
6
7
8
9
10
11
addElemento(Elemento elemento){
           .....
          if (operacion_exitosa)
             tamanho ++;
     }
 
     removeElemento(Elemento elemento){
           .....
          if (operacion_exitosa)
             tamanho --;
     }

3.- Finalmente cuando implementes la función daElementoEnmedio, puedes hacer algo así:

1
2
3
4
5
6
7
8
9
10
11
     //Tomas en cuenta el primer elemento de la lista para recorrerla.
     daElementoEnMedio(Elemento elemento){
              int pivote = floor(tamanho/2) //Para obtener la mitas de la longitud de la lista  y si la lista tiene número de elementos  impar, se le aplica la función floor.
 
            //Luego se llega hasta el elemento que ocupa la mitad de la posición de la lista.
             for (int i = 0, i < pivote, i ++)
                   elemento = elemento -> next;
 
            //Se regresa el elemento que ocupa la posición de la mitad.
            return elemento;
      }

Cualquier cosa estoy a tus órdenes.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Mitad de una lista doble

Publicado por Jhonny (10 intervenciones) el 31/07/2016 21:01:17
Claro, entiendo, la idea es que sea de Orden constante, es decir que simplemente me indique el nodo del medio.

Por eso es que tenia que al momento de insertar, fuese actualizando un nodo mitad, para que luego que consulte sea de tiempo constante

Yo he logrado hacer la funcion pero de Orden N, recorriendo una sola vez la lista
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Aarón Castillo

Mitad de una lista doble

Publicado por Aarón Castillo (8 intervenciones) el 31/07/2016 21:21:53
Ahora comprendo, sólo que hay un pequeño inconveniente, nunca vas a lograr obtener el nodo de enmedio con una complejidad constante, porque la naturaleza misma de la lista no te lo permite, esto es, si estás tratando de actualizar el nodo de en medio (asumiendo que esté en una posición k) siempre vas a tener que recorrer los k -1 elementos anteriores para poder llegar a ése, uses el método que uses, incluso siendo simple o doblemente ligada, vas a tener que hacer el mismo recorrido.

Aún si usaras técnicas como la búsqueda binaria de todas formas tienes que recorrer elementos previamente para poder llegar al nodo que quieras.

Lo que se me ocurre es que hagas una fusión de una lista con una tabla hash, en el sentido en que cuando añadas un nodo guardes la referencia del nodo en la tabla hash, de esta manera cuando quieras acceder al de enmedio tomas directamente el elemento en la tabla hash y eso sí es constante. Obviamente hay ahora que tomar consideraciones con respecto de la tabla hash (evitar colisiones y esas cosas).

De hecho veo en tu código que estás implementando una especie de búsqueda binaria, ¿pero qué significa avelider, first y reminder? tengo una idea pero para no ser erróneo en la lógica de código te lo pregunto. De hecho sería muy productivo si compartes en palabras lo que tratabas de hacer en esa sección del código.

Saludos.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Mitad de una lista doble

Publicado por Jhonny (10 intervenciones) el 31/07/2016 21:38:57
El int avelider que ves es una funcion que deberia devolver el nodo que está a la mitad.

El first, es el primer nodo de la lista

El reminder es un entero que divide entre dos el un contador, contador que indica el numero de nodos de la lista
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Aarón Castillo

Mitad de una lista doble

Publicado por Aarón Castillo (8 intervenciones) el 31/07/2016 22:19:27
Lamento hacer tantas preguntas, pero me interesa el problema. ¿Para qué sirve el booleano mitad?.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Mitad de una lista doble

Publicado por Jhonny (10 intervenciones) el 31/07/2016 22:24:26
Eso es que cada ves que insertas un nodo nuevo, se manda un true a la accion UpdateMidlle
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Aarón Castillo

Mitad de una lista doble

Publicado por Aarón Castillo (8 intervenciones) el 01/08/2016 21:59:46
Hola, creo que ya encontré el error.

Cuando agregas un elemento, como el remainder es 1, entonces eso indica que mit = mit -> next, pero ¿quién es el siguiente cuando tienes un elemento? pues NULL.

Entonces agregas el segundo elemento, como el remainder es 0, ahora mit = mit -> prev, pero el prev de NULL da un error, por lo que no se puede acceder al previo de algo nulo.

Espero esto te pueda servir.

Saludos.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Mitad de una lista doble

Publicado por Jhonny (10 intervenciones) el 01/08/2016 22:09:16
Si creo que ha de ser eso, voy a intentarlo. Tengo otro problemilla pero con listas simples, te puedo poner el ejemplo?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Aarón Castillo

Mitad de una lista doble

Publicado por Aarón Castillo (8 intervenciones) el 01/08/2016 22:32:38
Por supuesto. Estoy a tus órdenes.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Mitad de una lista doble

Publicado por Jhonny (10 intervenciones) el 01/08/2016 22:40:41
Te cuento, tengo una lista simple a la cual le voy insertando valores (de dos en dos, voy leyendo dos variables, llamo a la funcion dos veces). Luego decido eliminar valores de la lista, me pasa que cuando elimino las puntas de la lista, es decir el nodo inicial, y el final, los elimina correcto, pero si yo quiero volver a insertar los mismos valores no me deja!!!

Te lo explico asi, tengo esta lista 5 10 20 25 35 y elimino 5 y 35, los elimino, cuando ingreso esos valores nuevamente, no los ingresa

Te anexo las funciones de insertar y borrar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void borrarAve(int e)
    {
      struct listAve *listAvetemp, *listAveprev;
      listAvetemp=first;
      while(listAvetemp!=NULL)
      {
        if(listAvetemp->edad==e)
        {
          if(listAvetemp==first)
          {
            first=listAvetemp->next;
          }
          else
          {
            listAveprev->next=listAvetemp->next;
          }
          delete listAvetemp;
          break;
        }
        else
        {
          listAveprev=listAvetemp;
          listAvetemp=listAvetemp->next;
        }
      }
    }
 
void anadiraves(int e)
    {
      if(this->listAvevacia())
      {
        listAve *listAveaux=new listAve;
        listAveaux->edad=e;
        listAveaux->next=NULL;
        first=listAveaux;
        last=listAveaux;
      }
      else
      {
        listAve *listAveaux=new listAve;
        listAveaux->edad=e;
        last->next=listAveaux;
        last=listAveaux;
        last->next=NULL;
      }
      //Al insertar aves, llamamos a la accion ordenar, para ordenar la lista
      ordenarlistAve(); //Ordeno la lista por método de la burbuja
    }
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Aarón Castillo

Mitad de una lista doble

Publicado por Aarón Castillo (8 intervenciones) el 02/08/2016 03:08:25
Creo que encontré una parte del error.

Cuando estás agregando el nodo en una lista no vacía, no estás actualizando la variable first (líneas 40 a 44 del código). Eso podría explicar por qué puedes eliminar el primer elemento de la lista (porque está en tu código explícitamente), pero como no tienes una referencia a first desde el momento en que agregaste el nodo (en la lista no vacía), por eso al borrarlo ya no puedes tener acceso al nodo first.

Falta el caso del nodo last.


Dime si eso te ayuda. Saludos.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Mitad de una lista doble

Publicado por Jhonny (10 intervenciones) el 02/08/2016 03:32:37
No lo pillo, por que debería actualizar el primer nodo si la lista ya no esta vacia?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Aarón Castillo

Mitad de una lista doble

Publicado por Aarón Castillo (8 intervenciones) el 02/08/2016 04:39:59
Porque veo que haces algo como last -> next, pero no haces eso para first (first-> next), ¿no tendrías que hacer algo así para no perder las referencias? ya que, para eliminar un elemento, usas first como primer nodo.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar