C/Visual C - Insersión ordenada en lista enlazada simple

   
Vista:

Insersión ordenada en lista enlazada simple

Publicado por Diego (146 intervenciones) el 02/10/2016 20:20:00
Buenas tardes, según lo veo no puedo asignarle NULL a un puntero, lo cual me parece extraño. Y quisiera que me dijeran porque tengo violación de acceso al intentar crear la lista.

listas.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef LISTAS_H
#define LISTAS_H	
	#include <stdint.h>
	#include <inttypes.h>
	#include <string.h>
	#include <stdlib.h>
	#include <stdio.h>
	struct nodo {
		uint64_t dni;
		char *nombre;
		struct nodo *psig;
	};
	typedef struct nodo * Lista;
	void CrearLista(Lista *);
	void Insertar(Lista *, uint64_t, char *);
	void MostrarLista(Lista *);
 
#endif

listas.c
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
#include "listas.h"
void CrearLista(Lista *l)
{
	*l = NULL;
}
void Insertar(Lista *l, uint64_t dni, char *nombre)
{
	uint64_t resul;
	Lista ant, act;
	Lista nue = malloc(sizeof(struct nodo) * 1);
	nue->dni = dni;
	nue->nombre = nombre;
	nue->psig = NULL;
	act = *l;
	ant = *l;
	resul = strcmp(act->nombre, nue->nombre);
	while ((act != NULL)&&(resul <= 0)){
		ant = act;
		act = act->psig;
	}
	if (ant == act){
		nue->psig = *l;
		*l = nue;
	}else{
		ant->psig = nue;
		nue->psig = act;
	}
}
void MostrarLista(Lista *l)
{
	Lista l_aux = *l;
	while (l_aux != NULL){
		printf("%" PRIu64 "\t", l_aux->dni);
		printf("%s\n", l_aux->nombre);
		l_aux = l_aux->psig;
	}
}

prueba.c
1
2
3
4
5
6
7
8
9
10
11
12
#include "listas.h"
int main (int argc, char *argv[]){
	Lista mi_lista;
	CrearLista(&mi_lista);
	Insertar(&mi_lista, 36117118, "DIEGO");
	Insertar(&mi_lista, 92678184, "LEONOR");
	Insertar(&mi_lista, 98765432, "ABELINO");
	Insertar(&mi_lista, 12345678, "FELIPE");
	Insertar(&mi_lista, 56478901, "SOLEDAD");
	MostrarLista(&mi_lista);
	return EXIT_SUCCESS;
}
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

Insersión ordenada en lista enlazada simple

Publicado por Diego (146 intervenciones) el 02/10/2016 20:39:28
Ya arreglé el problema del NULL. bastó con cambiar lo por esto:
1
2
3
4
void CrearLista(Lista *l)
{
	l = NULL;
}

Tambien arreglé el hecho de que no me ordene alfabeticamente los nombre.
Usaba una variable uint64_t para guardar el resultado de strcmp y simpre daba >= 0 por la naturaleza del tipo de dato.
LO arreglé así:
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
void Insertar(Lista *l, uint64_t dni, char *nombre)
{
	long int resul;
	Lista ant, act;
	Lista nue = malloc(sizeof(struct nodo) * 1);
	nue->dni = dni;
	nue->nombre = nombre;
	nue->psig = NULL;
	act = *l;
	ant = *l;
	resul = strcmp(act->nombre, nue->nombre);
	while ((act != NULL)&&(resul < 0)){
		ant = act;
		act = act->psig;
		if (act != NULL){
			resul = strcmp(act->nombre, nue->nombre);
		}
	}
	if (ant == act){
		nue->psig = *l;
		*l = nue;
	}else{
		ant->psig = nue;
		nue->psig = act;
	}
}

Ahora ordena correctamente los campos, pero hay algo que no comprendo en la salida y es que me muste "1 \t nombre del programa"
Ya que nunca ingresé estos datos a la lista, no veo porqué salen al momento de imprimir.
Salida:
1
2
3
4
5
6
7
acus@acus-desktop:~/compilar$ ./prueba.exe
1	./prueba.exe
98765432	ABELINO
36117118	DIEGO
12345678	FELIPE
92678184	LEONOR
56478901	SOLEDAD
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

Insersión ordenada en lista enlazada simple

Publicado por Tom (515 intervenciones) el 03/10/2016 21:40:57
Ante este tipo de problemas (sinceramente, creo que tu código debería cascar con SIGSEGV, es la primera vez que veo ese comportamiento :)) en mi opinión es mejor dividir los procesos aunque ya sean cortos.

Además, a estas alturas, ya debes plantearte la posibilidad de que la memoria pueda agotarse, y pensar de antemano qué vas a hacer en tal caso.

En este ejemplo, por simplificar, en caso de error simplemente se finaliza (no es tan fácil como pueda parecer recuperar un proceso que ha agotado la memoria del sistema) y además _no_ ordeno la lista (¿ quizás sería mejor usar una lista doblemente enlazada ?).

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/* vim: set ts=2 sw=2: */
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
struct Nodo {
	unsigned long	dni;
	char	*nombre;
	struct Nodo	*next;
};
 
/* */
struct Nodo* creaLista() {
	return NULL;
}
 
/* */
struct Nodo* creaNodo(unsigned long dni, char nombre[]) {
	struct Nodo *n = (struct Nodo*)malloc(sizeof(struct Nodo));
 
	if(!n) {
		fprintf(stderr, "Error al obtener memoria para nuevo nodo.\n");
		exit(1);
	}
 
	n->dni = dni;
	n->nombre = strdup(nombre);
	n->next = NULL;
 
	return n;
}
 
/* */
struct Nodo* insertaOrden(struct Nodo *l, struct Nodo *n) {
	struct Nodo *tmp = l;
 
	while(tmp) {
		if(! tmp->next) {
			tmp->next = n;
			return l;
		}
		tmp = tmp->next;
	}
	return n;
}
 
/* */
struct Nodo* inserta(struct Nodo *l, unsigned long dni, char nombre[]) {
 
	return insertaOrden(l, creaNodo(dni, nombre));
}
 
/* */
int main(int argc, char *argv[]) {
	struct Nodo	*lista = creaLista(); /* = NULL */
 
	lista = inserta(lista, 1, "Clodoveo");
	lista = inserta(lista, 2, "Aureliano");
	lista = inserta(lista, 3, "Zoilo");
	lista = inserta(lista, 4, "Florencio");
 
	for(struct Nodo *tmp = lista; tmp; tmp = tmp->next) {
		printf("%s %ld\n", tmp->nombre, tmp->dni);
	}
}

Por cierto, strdup() también puede devolver NULL si no hay memoria disponible; Y además, al menos en Linux, es posible que malloc() y familia fallen _antes_ de que se agote la memoria del sistema, al superar ciertos límites globales configurables.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
1
Comentar

Insersión ordenada en lista enlazada simple

Publicado por Diego (146 intervenciones) el 04/10/2016 00:00:11
Gracias, por la sugerencia. EL problema que tenía era que la funcion insertar necesitaba que la lista ya contenga elementos. Lo arreglé creando el primer elemento y luego insertar los siguientes.
También volví a corrergir el CrearLista, Y lo dejé como en un principio.
1
2
3
4
void CrearLista(Lista *l)
{
	*l = NULL;
}

Con esas correccciones la lista ya funciona correctamente.
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