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

 

 


Tema destacado:


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ordenar lista simplemente enlazada en lenguaje C.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] 3 Ir Abajo Respuesta Imprimir
Autor Tema: Ordenar lista simplemente enlazada en lenguaje C.  (Leído 17,670 veces)
NOB2014


Desconectado Desconectado

Mensajes: 366



Ver Perfil
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #10 en: 7 Julio 2016, 22:19 pm »

Hola, que tengan un muy buen día. -
ivancea96, no lo intente de esa manera porque a la apurada leí que era muy costoso hacerlo directamente sobre la lista y como Alberto me sugirió hacerlo de la otra manera no lo pensé demasiado y lo intente, pero no hay caso no solo no me sale, sino que ahora también descubro que no tenía demasiado conocimiento de estructuras anidadas, en conclusión estoy en un pozo demasiado profundo y muy confundido. -
Descarte el código que deje en el primer post y lo estoy intentando con el programa que esta en el video de Alberto sin el borrado de nodo, lo que ocurre es que podría aprenderme la sintaxis de memoria y continuar pero tengo claro que esa no es la forma de estudiar en serio. -
En definitiva, voy a respirar muy profundo, pensar tranquilo e intentar interpretar lo que ahora me tiene ocupado que son las 2 estructuras, créanme que si los tuviera sentado frente a una computadora a algunos de Uds. ni siquiera así intentaría pedirles alguna ayuda dado que es algo que me da vueltas con respecto a las dos estructuras pero no logro expresar exactamente lo que no entiendo.
En conclusión, voy a seguir pensando en el tema y si me surge alguna duda concreta la voy a postear.

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. //LsL001
  5.  
  6. struct nodo{
  7. int dato;
  8. struct nodo *siguiente;
  9. };
  10.  
  11. struct lista{
  12. struct nodo *primero;
  13. struct nodo *ultimo;
  14. };
  15.  
  16. struct lista *agregar( struct lista *L, int dato );
  17. struct nodo *crear( int dato );
  18.  
  19. int main( void ){
  20. struct lista *Lista = NULL;
  21.  
  22. Lista = agregar( Lista, 1 );
  23. Lista = agregar( Lista, 2);
  24. Lista = agregar( Lista, 3);
  25.  
  26. return 0;
  27. }
  28.  
  29. struct lista *agregar( struct lista *L, int dato ){
  30. if( L != NULL ){
  31. struct nodo *e = crear( dato );
  32. printf( "\n Creando elemento con valor %d", dato );
  33. L->ultimo->siguiente = e;
  34. L->ultimo = e;
  35.  
  36. return L;
  37. }else{
  38. struct nodo *e = crear( dato );
  39. struct lista *l = calloc( sizeof( struct lista ), 1 );
  40. printf( "\n Inicializando la lista con valor %d", dato );
  41. l->primero = e;
  42. l->ultimo = e;
  43.  
  44. return l;
  45. }
  46. }
  47.  
  48. struct nodo *crear( int dato ){
  49. struct nodo *e = calloc( sizeof( struct nodo), 1 );
  50. e->dato = dato;
  51. e->siguiente = NULL;
  52.  
  53. return e;
  54. }
  55.  
  56. /*
  57. ============================== LsL001 ==============================
  58. - Definir estructura.
  59. - Inicializar.
  60. - Agregar elementos.
  61. - Ordenar elementos.
  62. - Borrar elementos.
  63.  */
       

Saludos.   


En línea

abraza las cosas y personas malas como si fueran tu mas preciada joya,Son tus mas grandes maestros de paciencia sabiduría y amor y cuando lo abrazas dejan de causar dolor.-
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #11 en: 8 Julio 2016, 01:43 am »

Yo sugerí el pasarlo a un arreglo externo para que no lo vieras como una lista ligada.

El algoritmo es el mismo para la lista ligada, lo que cambia contra tu arreglo es el acceso a los elementos de la lista y las condiciones de parada...

En el ordenamiento de burbuja que tenias se compara dos valores y si uno es mayor se hace el cambio de variable, esto para ordenar la lista

Enronces lo que necesitas es guardar las direcciones de memoria en un apuntador por ejemplo (pivotey actual). Hacer la comparación

Código
  1. //While o for aquí
  2. //guardar valores de actual y siguiente
  3. if(pivote->dato > actual->dato){
  4. //hacer cambio de variable aqui.
  5. }
  6. //fin while o for
  7.  

Solo necesitas traducir el algoritmo que ya tienes de burbuja por el correspondiente a lista ligada

Te propongo que hagas el ejercicio a mano.

usando este ejemplo como datos del la Lista:

Código
  1. /*
  2. Variable Entera
  3. tmp
  4.  
  5. Variables Nodos:
  6. Pivote
  7. Actual
  8.  
  9. Lista:
  10. [200]->[150]->[100]->[50]->[0]->[40]->NULL
  11. Primero                         Ultimo
  12. */
  13.  

Tu algoritmo burbuja ya lo tienes:

Código
  1. for(i=0; i<cont-1; i++) {
  2. for(j=i+1; j<cont; j++) {
  3. if( tmp[i] > tmp[j] ){
  4. aux = tmp[i];
  5. tmp[i] = tmp[j];
  6. tmp[j] = aux;
  7. }
  8. }
  9. }
  10.  

Solo tienes que cambiar las variables temp[i,j] por los correspondientes.

Saludos


No me pude resistir  :xD
Código
  1. void ordenar_lista(struct lista *L) {
  2. //Elegir metodo de ordenamiento
  3. // Burbuja
  4. struct nodo *pivote = NULL,*actual = NULL;
  5. int tmp;
  6. if(L != NULL) {
  7.  
  8. pivote = L->primero; //i = 0
  9. while(pivote != L->ultimo) { //for(i=0; i<cont-1; i++) {
  10. actual = pivote->siguiente; //j=i+1
  11. while(actual != NULL) { //for(j=i+1; j<cont; j++) {
  12. if(pivote->dato > actual->dato) { //if( tmp[i] > tmp[j] ){
  13. tmp = pivote->dato; //aux = tmp[i];
  14. pivote->dato = actual->dato; //tmp[i] = tmp[j];
  15. actual->dato = tmp; //tmp[j] = aux;
  16. }
  17. actual = actual->siguiente; //j++
  18. }
  19. pivote = pivote->siguiente; //i++
  20. }
  21. }
  22. else {
  23. printf("Error lista no inicializada");
  24. }
  25. /*
  26. Pivote
  27. Actual
  28. [200]->[150]->[100]->[50]->[0]->[40]->NULL
  29. Primero                         Ultimo
  30.  
  31. */
  32. }


« Última modificación: 9 Julio 2016, 16:33 pm por AlbertoBSD » En línea

NOB2014


Desconectado Desconectado

Mensajes: 366



Ver Perfil
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #12 en: 10 Julio 2016, 00:12 am »

Hola, gente. -
Les pido un esfuerzo más, alguien que tenga mucho tiempo y ganas me podría decir si lo que puse en las imágenes es medianamente correcto. -




Saludos. 
En línea

abraza las cosas y personas malas como si fueran tu mas preciada joya,Son tus mas grandes maestros de paciencia sabiduría y amor y cuando lo abrazas dejan de causar dolor.-
ivancea96


Desconectado Desconectado

Mensajes: 3.412


ASMático


Ver Perfil WWW
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #13 en: 10 Julio 2016, 01:45 am »

No me pareció ver nada relevante, salvo que usas siempre calloc. calloc es lo mismo que malloc, solo que inicializa la memoria a 0. Salvo que realmente lo necesites, te recomendaría usar malloc.
En línea

NOB2014


Desconectado Desconectado

Mensajes: 366



Ver Perfil
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #14 en: 10 Julio 2016, 02:07 am »

Hola, ivancea96. -
Yo no puse las imágenes para que lo que está escrito sea relevante, solo para que me digan si tienen algún error de concepto. - 

Alberto, No puedo creer lo que estoy viendo, posteaste el código y yo sin enterarme, no lo puedo creer

Saludos.   
En línea

abraza las cosas y personas malas como si fueran tu mas preciada joya,Son tus mas grandes maestros de paciencia sabiduría y amor y cuando lo abrazas dejan de causar dolor.-
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #15 en: 10 Julio 2016, 02:30 am »

La imagen que pusiste esta bien.

Yo le sugerí calloc para que el nodo este limpio, y comente que igualar el dato siguiente a NULL es innecesario si se usa calloc.

  • Si usas calloc, no se inicializa en NULL el elemento siguiente
  • Si usas malloc, es necesario inicializar el elemento en NULL

Efectivamente puse el código por que no me pude resistir y aqui dejo el ejemplo para probarlo de forma completa:

Código
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4.  
  5. struct nodo {
  6. int dato;
  7. struct nodo *siguiente;
  8. };
  9.  
  10. struct lista {
  11. struct nodo *primero;
  12. struct nodo *ultimo;
  13. int elementos;
  14. };
  15.  
  16. struct lista *agregar_elemento(struct lista *L, int dato);
  17. struct nodo *crear_elemento(int dato);
  18. void ordenar_lista(struct lista *L);
  19. struct lista *eliminar_indice(struct lista *L, int indice);
  20. int obtener_indice(struct lista *L,int indice);
  21.  
  22. int main() {
  23. struct lista *Lista = NULL;
  24. int i = 0;
  25. srand(time(NULL));
  26. while(i < 30) {
  27. Lista = agregar_elemento(Lista,rand() % 1000);
  28. i++;
  29. }
  30. ordenar_lista(Lista);
  31. i = 0;
  32. while(i < 30) {
  33. printf("Elemento %i: %i\n",i+1,obtener_indice(Lista,i+1));
  34. i++;
  35. }
  36.  
  37. /*
  38. Lista = agregar_elemento(Lista,2);
  39. Lista = agregar_elemento(Lista,3);
  40. Lista = eliminar_indice(Lista,3);
  41. Lista = eliminar_indice(Lista,2);
  42. Lista = eliminar_indice(Lista,1);
  43. printf("apuntador de la lista %p\n",Lista);
  44. Lista = eliminar_indice(Lista,1);
  45. */
  46. return 0;
  47. }
  48.  
  49. struct lista *agregar_elemento(struct lista *L, int dato) {
  50. if(L != NULL) {
  51.  
  52. struct nodo *e = crear_elemento(dato);
  53. printf("Creando elemento con valor %i\n",dato);
  54. L->ultimo->siguiente = e;
  55. L->ultimo = e;
  56. L->elementos++;
  57. return L;
  58. }
  59. else {
  60. struct nodo *e = crear_elemento(dato);
  61. struct lista *l = calloc(sizeof(struct lista),1);
  62. printf("Inicializando lista con valor %i\n",dato);
  63. l->primero = e;
  64. l->ultimo = e;
  65. l->elementos++;
  66. return l;
  67. }
  68. }
  69.  
  70. struct nodo *crear_elemento(int dato) {
  71. struct nodo *e = calloc(sizeof(struct nodo),1);
  72. e->dato = dato;
  73. e->siguiente = NULL; //Fines didacticos ya que Calloc devuelve en 0
  74. return e;
  75. }
  76.  
  77. struct lista *eliminar_indice(struct lista *L, int indice) {
  78. if(L != NULL) {
  79. if(indice <= L->elementos && indice > 0) {
  80. struct nodo *anterior = L->primero;
  81. struct nodo *pivote = L->primero;
  82. int i = 1;
  83. //printf("while");
  84. while(i < indice) {
  85. //printf("Elemento actual %i\n",pivote->dato);
  86. anterior = pivote;
  87. pivote = pivote->siguiente;
  88. i++;
  89. }
  90. //pivote ya tiene el elemento a eliminar
  91. printf("Elemento a eliminar %i\n",pivote->dato);
  92. if(pivote->siguiente != NULL) {
  93. printf("NO el ultimo elemento\n",pivote->dato);
  94. if(pivote != L->primero) {
  95. printf("Y no es el primero\n");
  96. anterior->siguiente = pivote->siguiente;
  97. free(pivote);
  98. }
  99. else {
  100. printf("Si es el primero\n");
  101. L->primero = pivote->siguiente;
  102. free(pivote);
  103. }
  104. }
  105. else {
  106. printf("Es el ultimo elemento\n",pivote->dato);
  107. if(pivote != L->primero ) {
  108. anterior->siguiente = NULL;
  109. free(pivote);
  110. L->ultimo = anterior;
  111. }
  112. else {
  113. printf("Y tamien es el primero\n");
  114. free(pivote);
  115. }
  116. }
  117. L->elementos--;
  118. if(L->elementos == 0) {
  119. printf("Eliminando Lista\n");
  120. free(L);
  121. return NULL;
  122. }
  123. else {
  124. return L;
  125. }
  126. }
  127. else {
  128. printf("El indice pedido es mayor que los elementos existentes\n");
  129. return L;
  130. }
  131. }
  132. else {
  133. printf("No se puede procesar una lista NO inicializada\n");
  134. return NULL;}
  135. }
  136.  
  137. void ordenar_lista(struct lista *L) {
  138. //Elegir metodo de ordenamiento
  139. // Burbuja
  140. struct nodo *pivote = NULL,*actual = NULL;
  141. int tmp;
  142. if(L != NULL) {
  143.  
  144. pivote = L->primero; //i = 0
  145. while(pivote != L->ultimo) { //for(i=0; i<cont-1; i++) {
  146. actual = pivote->siguiente; //j=i+1
  147. while(actual != NULL) { //for(j=i+1; j<cont; j++) {
  148. if(pivote->dato > actual->dato) { //if( tmp[i] > tmp[j] ){
  149. tmp = pivote->dato; //aux = tmp[i];
  150. pivote->dato = actual->dato; //tmp[i] = tmp[j];
  151. actual->dato = tmp; //tmp[j] = aux;
  152. }
  153. actual = actual->siguiente; //j++
  154. }
  155. pivote = pivote->siguiente; //i++
  156. }
  157. }
  158. else {
  159. printf("Error lista no inicializada");
  160. }
  161. /*
  162. Pivote
  163. Actual
  164. [200]->[150]->[100]->[50]->[0]->[40]->NULL
  165. Primero                         Ultimo
  166.  
  167. */
  168. }
  169.  
  170. int obtener_indice(struct lista *L,int indice) {
  171. struct nodo *aux;
  172. int i = 1;
  173. aux = L->primero;
  174. while(i < indice) {
  175. aux = aux->siguiente;
  176. i++;
  177. }
  178. return aux->dato;
  179. }

Genera 30 números aleatorios y los ordena en la misma lista.

Saludos!
En línea

NOB2014


Desconectado Desconectado

Mensajes: 366



Ver Perfil
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #16 en: 10 Julio 2016, 02:50 am »

Que más se puede pedir, gracias por tu tiempo y ya me pongo a estudiar tú código. -
Es una buena oportunidad para decir algo que hace mucho disiento con la mayoría de los que responden en los foros, el tema de retacear código, por aquello de que no se hacen tareas y el prejuicio de que nadie aprende con copiar y pegar, digo, no les parece que es mejor(si tienen el tiempo necesario) escupir código, como leí por allí que un modelador retaba a un participante con esta frase y que los que preguntamos nos hagamos cargo de que es lo que nos conviene?.           

Saludos y un abrazo para todos.
En línea

abraza las cosas y personas malas como si fueran tu mas preciada joya,Son tus mas grandes maestros de paciencia sabiduría y amor y cuando lo abrazas dejan de causar dolor.-
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #17 en: 10 Julio 2016, 05:23 am »

¡Buenas!

Si sabes que la lista no está ordenada, lo que yo haría seria introducir los datos en un árbol binario y luego generar una nueva lista haciendo un recorrido inorden. Siempre puedes crear árboles binarios según distintos criterios de comparación. La forma más sencilla sería pasar como argumento la función de comparación a la función que inserte los nuevos nodos en el árbol:
Código
  1. int insertar_nodo_arbol(tuestruct *dato, int (*cmp)(struct1,struct2));
  2.  

De esta manera puedes tener funciones que devuelvan <0, 0, >0 según se comparen los structs siguiendo distintos criterios.

Por ejemplo con un árbol de enteros podrías tener una función
Código
  1. int intcmp(int a, int b)
  2. {
  3.    return a-b;
  4. }
  5.  

para cadenas de caracteres podrías utilizar strcmp, o para un struct con un campo entero y otro una cadena podrías tener dos funciones para ordenarlo con distintos criterios:
Código
  1. struct Cosa
  2. {
  3.    int x;
  4.    char *s;
  5. };
  6.  
  7. int cmp_cosa_int(struct Cosa *a, struct Cosa *b)
  8. {
  9.    return a->x - b->x;
  10. }
  11.  
  12. int cmp_cosa_str(struct Cosa *a, struct Cosa *b)
  13. {
  14.    return strcmp(a->s , b->s);
  15. }
  16.  

Así al pasar los nodos de la lista al arbol solo tendrías que pasar como segundo argumento la función de comparación que quisieses.

Código
  1. int insertar_nodo_arbol(struct Cosa **raiz, struct Cosa *dato, int (*cmp)(struct Cosa *, struct Cosa *))
  2. {
  3.    //...
  4. }
  5.  

¡Saludos!
« Última modificación: 10 Julio 2016, 05:31 am por do-while » En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
NOB2014


Desconectado Desconectado

Mensajes: 366



Ver Perfil
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #18 en: 12 Julio 2016, 18:48 pm »

Hola, buen día. -
Todavía no llegue a leer sobre arboles binarios solo sé que está dentro del capitulo que estoy estudiando, igual ya hice un enlace en mis apuntes para cuando llegue al tema tratar de interpretar tu propuesta. -
La consulta que les voy a efectuar tal vez les resulte infantil, pero créanme que hace más de un día que intento interpretar como funciona pero no hay caso. -
Les pregunto en que lugar de la función ordenar se modifica la estructura nodo, hay 2 punteros a estructura pivote y actual, pero no veo que en ningún lugar se iguale L con el puntero pivote, estoy escribiendo el hilo y regreso a la función para tratar de darme cuenta como funciona pero nada. -     

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct nodo{
  5. int dato;
  6. struct nodo *siguiente;
  7. };
  8.  
  9. struct lista{
  10. struct nodo *primero;
  11. struct nodo *ultimo;
  12. };
  13.  
  14. struct lista *ingresos( struct lista *L );
  15. struct lista *agregar( struct lista *L, int dato );
  16. struct nodo *crear( int dato );
  17. struct lista *ordenar(struct lista *L);
  18. void mostrar(struct lista *L);
  19.  
  20.  
  21. int main( void ){
  22. struct lista *Lista = NULL;
  23.  
  24. Lista = ingresos( Lista );
  25. Lista = ordenar( Lista );
  26. mostrar( Lista );
  27.  
  28. free(Lista);
  29. return 0;
  30. }
  31.  
  32. struct lista *ingresos( struct lista *L ){
  33. int i;
  34.  
  35. for( i=8; i>0; i-- ){
  36. printf( "\n %d", i );
  37. L = agregar( L, i );
  38. }
  39.  
  40. return L;
  41. }
  42.  
  43.  
  44. struct lista *agregar( struct lista *L, int dato ){
  45. if( L != NULL ){
  46. struct nodo *e = crear( dato );
  47. L->ultimo->siguiente = e;
  48. L->ultimo = e;
  49.  
  50. return L;
  51. }else{
  52. struct nodo *e = crear( dato );
  53. struct lista *l = calloc( sizeof( struct lista ), 1 );
  54. l->primero = e;
  55. l->ultimo = e;
  56.  
  57. return l;
  58. }
  59. }
  60.  
  61. struct nodo *crear( int dato ){
  62. struct nodo *e = calloc( sizeof( struct nodo), 1 );
  63. e->dato = dato;
  64. e->siguiente = NULL;
  65.  
  66. return e;
  67. }
  68.  
  69. struct lista *ordenar(struct lista *L){
  70. struct nodo *pivote = NULL,*actual = NULL;
  71. int tmp;
  72. if(L != NULL){
  73. pivote = L->primero;
  74. while(pivote != L->ultimo){
  75. actual = pivote->siguiente;
  76. while(actual != NULL){
  77. if(pivote->dato > actual->dato){
  78. tmp = pivote->dato;
  79. pivote->dato = actual->dato;
  80. actual->dato = tmp;
  81. }
  82. actual = actual->siguiente;
  83.     }
  84. pivote = pivote->siguiente;
  85.     }
  86. }
  87.   else{
  88.     printf("Error lista no inicializada");
  89.    }
  90. return L;
  91. }
  92.  
  93. void mostrar(struct lista *L){
  94. struct nodo *auxiliar;
  95. int i=0;
  96. auxiliar = L->primero;
  97.  
  98.    printf("\n\n Mostrando lista ordenada:\n");
  99.  
  100. while (auxiliar!=NULL) {
  101. printf( "\n %d", auxiliar->dato);
  102. auxiliar = auxiliar->siguiente;
  103. i++;
  104. }
  105. if (i==0) printf( "\nLa lista está vacía!!\n" );
  106. }
  107.  

Saludos.
En línea

abraza las cosas y personas malas como si fueran tu mas preciada joya,Son tus mas grandes maestros de paciencia sabiduría y amor y cuando lo abrazas dejan de causar dolor.-
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.696


🏴 Libertad!!!!!


Ver Perfil WWW
Re: Ordenar lista simplemente enlazada en lenguaje C.
« Respuesta #19 en: 12 Julio 2016, 19:07 pm »

Vas bien, la funcion ordenar nunca modifica la estructura de la lista.

Solo mueve el valor dato de un nodo a otro, incluso todos los nodos siguen en la misma direccion de memoria. Solo se cambia el dato.

si te fijas la funcion que puse en mi codigo es Void por lo cual no regresa valor.

Saludos
En línea

Páginas: 1 [2] 3 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Lista Simplemente enlazada ayuda
Programación C/C++
Cpp 1 2,052 Último mensaje 11 Diciembre 2014, 07:29 am
por eferion
Borrar nodo en lista simplemente enlazada[C]
Programación C/C++
NOB2014 4 6,043 Último mensaje 28 Julio 2016, 14:22 pm
por NOB2014
Borrar ultimo nodo lista simplemente enlazada
Programación C/C++
robertoesimez 5 5,299 Último mensaje 23 Marzo 2017, 07:22 am
por MAFUS
Problema con una lista simplemente enlazada en C++
Programación C/C++
Mike_EDD 1 2,827 Último mensaje 4 Septiembre 2017, 22:24 pm
por ivancea96
Modificacion del orden de una lista simplemente enlazada
Programación C/C++
Beginner Web 4 2,409 Último mensaje 3 Septiembre 2018, 01:57 am
por Beginner Web
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines