Estructuras De Datos, Tad Listas

Ejercicio 5.3
1
/*
Estructuras de datos y metodos algoritmicos
Ejercicio 5.3 (lista doblemente enlazada)
vk, 19/04/2012
2
3
4
5
*/
6
7
8
#include
#include
9
10
11
12
13
typedef struct elem {
int val;
unsigned int es_valido;
} Elem;
14
15
16
17
18
19
typedef struct nodo_lista {
Elem valor;
struct nodo_lista *sig;
struct nodo_lista *ant;
} Nodo;
1 / 30
21
2223
24
25
typedef struct lista {
unsigned int longitud;
Nodo *izquierdo;
Nodo *derecho;
} Lista;
26
27
28
29
30
31
32
33
34
35
36
37
Lista *lista_vacia(void);
void anadir_izq(Elem *, Lista *);
void anadir_der(Lista *, Elem *);
Lista *unitaria(Elem *);
Elem *izquierdo(Lista *);
int elim_izq(Lista *);
Elem *derecho(Lista *);
int elim_der(Lista *);
intes_lista_vacia(Lista *);
Lista *concatenar(Lista *, Lista *);
unsigned int longitud(Lista *);
38
2 / 30
39
40
41
42
43
int
main(void)
{
Lista *mi_lista, *l1, *l2, *l3;
Elem *mi_elem;
44
45
printf("\nCreacion de mi_lista vacia ...\n");
46
47
mi_lista = lista_vacia();
48
3 / 30
49
printf("\nVerificando si mi_lista es vacia ...\n"
);
50
51
52
if ( es_lista_vacia(mi_lista) ) printf("ok:mi_lista es vacia\n");
else { printf("Error: mi_lista no es vacia\n");
exit(1); }
53
54
printf("\nInsertando ...\n");
55
56
57
58
59
60
61
62
63
64
65
mi_elem = malloc(sizeof(Elem));
mi_elem->val = 12;
anadir_der(mi_lista, mi_elem);
mi_elem->val = 11;
anadir_izq(mi_elem, mi_lista);
mi_elem->val = 13;
anadir_der(mi_lista, mi_elem);
free(mi_elem);
printf("mi_lista tiene %delementos\n", longitud(
mi_lista));
4 / 30
66
printf("\nVerificando ...\n");
67
68
69
70
if ( (mi_elem=izquierdo(mi_lista)) == NULL )
printf("---> Funcion izquierdo: error de lista
vacia\n");
else printf("Primer elemento: %d\n", mi_elem->val
);
71
72
73
74
if ( (mi_elem=derecho(mi_lista)) == NULL )
printf("---> Funcion derecho: error de lista
vacia\n");
else printf("Ultimoelemento: %d\n", mi_elem->val
);
75
5 / 30
76
77
printf("\nCreando la lista unitaria l3 y la lista
vacia l2\n");
printf(" para concatenarlas en l1 ...\n");
78
79
80
81
82
83
mi_elem = malloc(sizeof(Elem));
mi_elem->val = 14;
l3 = unitaria(mi_elem);
free(mi_elem);
printf("Lista l3 tiene %d elemento\n", longitud(
l3));
84
85
86
87
l2 = lista_vacia();
l1 = concatenar(l2,l3);printf("Lista l1 tiene %d elemento\n", longitud(
l1));
88
6 / 30
89
printf("\nConcatenando mi_lista con l1 en l2 ...\
n");
90
91
92
93
free(l2);
l2 = concatenar(mi_lista,l1);
printf("Lista l2 tiene %d elementos\n", longitud(
l2));
94
95
96
97
if ( (mi_elem=izquierdo(l2)) == NULL )
printf("---> Funcion izquierdo: error de lista
vacia\n");
else printf("Primer elemento: %d\n",mi_elem->val
);
98
99
100
101
if ( (mi_elem=derecho(l2)) == NULL )
printf("---> Funcion derecho: error de lista
vacia\n");
else printf("Ultimo elemento: %d\n", mi_elem->val
);
102
7 / 30
103
printf("\nEliminando de l2 ...\n");
104
105
106
107
108
109
if ( (mi_elem=izquierdo(l2)) == NULL )
printf("---> Funcion izquierdo: error de lista
vacia\n");
else printf("Primerelemento: %d\n", mi_elem->val
);
if ( elim_izq(l2) == -1 )
printf("---> Funcion elim_izq: error de cola
vacia\n");
110
111
112
113
114
115
if ( (mi_elem=derecho(l2)) == NULL )
printf("---> Funcion derecho: error de lista
vacia\n");
else printf("Ultimo elemento: %d\n", mi_elem->val
);
if ( elim_der(l2) == -1 )
printf("---> Funcion elim_der: error de cola
vacia\n");
116
8 / 30
117118
119
120
121
if ( (mi_elem=izquierdo(l2)) == NULL )
printf("---> Funcion izquierdo: error de lista
vacia\n");
else printf("Primer elemento: %d\n", mi_elem->val
);
if ( elim_izq(l2) == -1 )
printf("---> Funcion elim_izq: error de cola
vacia\n");
122
123
124
125
126
127
128
if ( (mi_elem=derecho(l2)) == NULL )
printf("---> Funcion derecho: error de lista
vacia\n");
else...