elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [C] Listas enlazadas utilizando arreglos
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: [C] Listas enlazadas utilizando arreglos  (Leído 8,551 veces)
GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
[C] Listas enlazadas utilizando arreglos
« en: 5 Mayo 2016, 13:52 pm »

Las listas enlazadas implementadas con punteros tienen la flexibilidad de poder insertar elementos en cualquier parte de ellas sin mover los elementos anteriores ni posteriores, mientras que los arreglos no cuentan con esta flexibilidad.
Proponga una implementación de similar a listas enlazadas, pero de longitud fija, utilizando arreglos, y que provea esta flexibilidad.


Me maté pensandolo pero no me sale, no tengo alguna idea para empezar, ¿alguien que me pueda encaminar?, por favor.



Y tengo otra duda con un problema de tipos que tengo en mi cabeza al parecer(no tiene nada que ver con el anterior ejercicio):

Código
  1. SList slist_append(SList list, int data)
  2. {
  3.      SList newNode = malloc(sizeof(SNode));
  4.      SList node;
  5.      slist_data(newNode) = data;
  6.      slist_next(newNode) = NULL;
  7.      if (list == slist_nil()) {
  8.         return newNode;
  9.      }
  10.      node = list;
  11.      while (slist_next(node) != slist_nil()) {
  12.            node = slist_next(node);
  13.      }
  14.      /* ahora 'node' apunta al ultimo nodo en la lista */
  15.      slist_next(node) = newNode;
  16.      return list;
  17. }
  18.  

¿Por qué retorna list, no sería node?
Si yo estoy trabajando con node y no con list, a list ni siquiera lo he tocado es porque es algún puntero o algo así?

No lo entiendo

Saludos!


« Última modificación: 5 Mayo 2016, 14:17 pm por nisteeklod » En línea

LET'S DO STUFF!!
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #1 en: 5 Mayo 2016, 15:47 pm »

Hay un parte del codigo que dice..

Código
  1. node = list;

Tendriamos que ver la estructura de slist.

Ayer hice una implementacion similar

Un nodo en una lista doblemwnte ligada tiene 2 apuntadores.

Uno apunta an nodo anterior y otro al siguiente nodo.

Y Nodo Lista se podria interpretar que apunta al primer nodo y al ultimo nodo asi la lista completa sigue siendo del tipo nodo.


En línea

MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #2 en: 5 Mayo 2016, 16:31 pm »

Hace una cosa extraña.

Está pensado para modificar la misma lista que se le pasa, pero en vez de modificar directamente el parámetro list lo que hace es modificarlo y regresar un puntero con el dato modificado. Seguramente el autor pensó en esa solución para dar un valor en caso de que list fuera NULL. Pero hubiera hecho lo mismo con un puntero a puntero y el resultado habría sido más natural.

Supongamos el siguiente trozo de código:
Código
  1. SList mi_lista = NULL;
  2.  
  3. mi_lista = slist_append(mi_lista, 5);

Ahora mi_lista pasa a tener un elemento con un valor en data de 5. Continuamos con la variable mi_lista tal y como la hemos dejado en el siguiente código:
Código
  1. mi_lista = slist_append(mi_lista, 7);
Ahora mi_lista tiene dos elementos, uno que contiene el 5 y otro que contiene el 7. Se puede representar así [5 , 7].

Pero qué pasaría si hubiera:
Código
  1. SList lista_uno = NULL;
  2. SList lista_dos = NULL;
  3.  
  4. lista_uno = slist_append(lista_uno, 5);
  5. lista_dos = slist_append(lista_uno, 7);
¿Era esto lo que esperaba el autor que se hiciera?

Casi mejor hubiera sido definir la función con un puntero a puntero.
Código
  1. void slist_append(SList * list, int data) {
  2.    /* Implementación de la función */
  3. }
  4.  
  5. /* Código y más código */
  6.  
  7. SList mi_lista = NULL;
  8. slist_append(&mi_lista, 5);
  9. slist_append(&mi_lista, 7);

Ahora mi_lista estaría actualizada con [5 , 7] pero no habría posibilidad de darle a otra lista la posibilidad de acceder a los datos de ésta con lo que se previenen errores a la hora de escribir el programa.

Por otra parte esconder un puntero dentro de un typedef no es muy buena práctica, pero cada uno hace lo que quiere.

Por otra parte, sobre la primera pregunta: tal vez un array de punteros. Los elementos apuntados no se mueven de su sitio, lo que cambias son los punteros del array y tienes un array para acceder a ellos.
En línea

GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #3 en: 5 Mayo 2016, 16:34 pm »

Esta es la implementación ahora te leo MAFUS xD

Código
  1. typedef struct _SNode {
  2.        int    data;
  3.        struct _SNode *next;
  4. } SNode;
  5.  
  6. typedef SNode *SList;
  7.  
  8. #define slist_data(l)       (l)->data
  9. #define slist_next(l)       (l)->next
  10. #define slist_nil()         NULL
  11.  


Código
  1. #include <stdlib.h>
  2. #include "SList.h"
  3.  
  4. SList slist_append(SList list, int data)
  5. {
  6.      SList newNode = malloc(sizeof(SNode));
  7.      SList node;
  8.      slist_data(newNode) = data;
  9.      slist_next(newNode) = NULL;
  10.      if (list == slist_nil()) {
  11.         return newNode;
  12.      }
  13.      node = list;
  14.      while (slist_next(node) != slist_nil()) {
  15.            node = slist_next(node);
  16.      }
  17.      /* ahora 'node' apunta al ultimo nodo en la lista */
  18.      slist_next(node) = newNode;
  19.      return list;
  20. }
  21.  
  22. SList slist_prepend(SList list, int data)
  23. {
  24.      SList newNode = malloc(sizeof(SNode));
  25.      slist_next(newNode) = list;
  26.      slist_data(newNode) = data;
  27.      return newNode;
  28. }
  29.  
  30. void  slist_destroy(SList list)
  31. {
  32.      SList nodeToDelete;
  33.  
  34.      while (list != slist_nil()) {
  35.            nodeToDelete = list;
  36.            list = slist_next(list);
  37.            free(nodeToDelete);
  38.      }
  39. }
  40.  
  41. void  slist_foreach(SList list, VisitorFuncInt visit, void *extra_data)
  42. {
  43.      SList node = list;
  44.  
  45.      while (node != slist_nil()) {
  46.            visit(slist_data(node), extra_data);
  47.            node = slist_next(node);
  48.      }
  49. }
  50.  

Tengo un lío de tipos en la cabeza. ¿Por qué regresa un puntero si los dos están declarados de la misma forma AAAHHHH WTFF !! ?


Citar
¿Era esto lo que esperaba el autor que se hiciera?

No te entiendo bien, pero no creo ¿por qué así?
Yo sólo pregunté por qué retorna node jaja tengo más confusión ahora.
 
« Última modificación: 5 Mayo 2016, 16:49 pm por nisteeklod » En línea

LET'S DO STUFF!!
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #4 en: 5 Mayo 2016, 16:42 pm »

Por otra parte, sobre la primera pregunta: tal vez un array de punteros. Los elementos apuntados no se mueven de su sitio, lo que cambias son los punteros del array y tienes un array para acceder a ellos.

La solucion de MAFUS es totalmente valida.


Proponga una implementación de similar a listas enlazadas, pero de longitud fija, utilizando arreglos, y que provea esta flexibilidad.


Aun así si lo que quieren es no usar apuntadores, el campo next podría ser una variable entera que sea el index relativo al elemento de la tabla por ejemplo si next  es 4 y quien inserta ahi un nuevo nodo, el nodo se escribe al final de la tabla y entonce el nodo que tenia next = 4 se cambia por final y ahora el nodo final es su valor next tendría 4.

Es casi lo mismo pero es otra solución, aun así utilizando arreglos lo veo poco practico por que no sabes cuantos nodos serán insertados

En línea

GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #5 en: 5 Mayo 2016, 17:04 pm »

AlbertoBSD, puedes escribir un troso de código o algún ejemplo así me queda un poco más claro para guiarme no digo que lo hagas es que estoy medio perdido.
Encima el Viernes de la semana que viene rindo, pero llego bien si entiendo esto.
En línea

LET'S DO STUFF!!
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #6 en: 5 Mayo 2016, 20:10 pm »

Código
  1.  
  2. typedef struct {
  3. int anterior;
  4. int valor;
  5. int siguiente;
  6. }Nodo;
  7.  
  8. int main() {
  9. Nodo lista[100];
  10. }
  11.  

Los nodos podrían insertarse en el primer hueco disponible dentro del arreglo, las variables anterior y siguiente podrian apuntar a la posicion relativa dentro del la lista.
En línea

GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #7 en: 6 Mayo 2016, 09:15 am »

Citar
Está pensado para modificar la misma lista que se le pasa, pero en vez de modificar directamente el parámetro list lo que hace es modificarlo y regresar un puntero con el dato modificado. Seguramente el autor pensó en esa solución para dar un valor en caso de que list fuera NULL. Pero hubiera hecho lo mismo con un puntero a puntero y el resultado habría sido más natural.

¿Cómo que un puntero al dato modificado si los dos tienen el mismo tipo!?

Último ejercicio que me queda sigo intentando pero pregunto por si las dudas después me quedo trabado

Suponga que está implementando una lista doblemente enlazada. Si en lugar de guardar punteros a los nodos previo y siguiente, guarda un xor de ambos punteros: ¿puede recorrer la lista en ambas direcciones ¿Cómo? Defina en C la estructura correspondiente, ¿qué problemas puede encontrar?

Es lo último, denme una mano en esta.

Saludos!
« Última modificación: 6 Mayo 2016, 09:43 am por nisteeklod » En línea

LET'S DO STUFF!!
MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #8 en: 6 Mayo 2016, 10:10 am »

La funciones lo que hacen es devolver el inicio de la lista modificada.
Le entregas la lista y la modificación y la función te la devuelve modificada.

Si quieres que sea más específico deberás decirme exactamente que es que no entiendes.
« Última modificación: 6 Mayo 2016, 16:23 pm por MAFUS » En línea

GGZ

Desconectado Desconectado

Mensajes: 144



Ver Perfil
Re: [C] Listas enlazadas utilizando arreglos
« Respuesta #9 en: 6 Mayo 2016, 17:53 pm »

Código
  1.  
  2. SList slist_append(SList list, int data)
  3. {
  4.      SList newNode = malloc(sizeof(SNode));
  5.      SList node;
  6.      slist_data(newNode) = data;
  7.      slist_next(newNode) = NULL;
  8.      if (list == slist_nil()) {
  9.         return newNode;
  10.      }
  11.      node = list;
  12.      while (slist_next(node) != slist_nil()) {
  13.            node = slist_next(node);
  14.      }
  15.      /* ahora 'node' apunta al ultimo nodo en la lista */
  16.      slist_next(node) = newNode;
  17.      return list;
  18. }
  19.  

Ya sé que el objetivo de la funcón es que devuelva la lista modificada pero no entiendo adónde la modifica, si no toca a list.
A la lista original (list) nunca lo toca, lo único que hace es decir que node = list y de ahí trabaja con node, pisa todos los datos que hay en node (por el node = slist_next(node)), por eso para mí falta algo como slist_next(list)=node;

No logro entender la lógica del código, no sé donde la modifica a lista, para mi esta devolviendo la misma lista que se le pasó sin modificación alguna.
« Última modificación: 6 Mayo 2016, 17:55 pm por nisteeklod » En línea

LET'S DO STUFF!!
Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Listas enlazadas en c++
Programación C/C++
N3r0 3 8,524 Último mensaje 13 Julio 2010, 12:42 pm
por N3r0
[C] Listas enlazadas.
Programación C/C++
The Swash 5 31,567 Último mensaje 26 Octubre 2011, 04:56 am
por brians444
listas enlazadas
Programación C/C++
javier210186 3 2,837 Último mensaje 25 Octubre 2011, 02:33 am
por javier210186
venta de boletos de autobuses utilizando (colas ,listas o arboles) y archivos
Programación C/C++
Anduresu 2 3,960 Último mensaje 4 Agosto 2020, 03:43 am
por Anduresu
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines