Listas Ligadas
Listas Ligadas
1
UVM
5.1 Objetivos
El estudiante manejará el tad Lista
Ligada, sobre memoria estática
Listas Ligadas
3
UVM
5.2 Temas a Cubrir
Definición
Pila Ligada
Cola Ligada
Lista Ligada
Lista Doblemente Ligada
Listas Ligadas
4
UVM
5.3 Definición
Una lista es una colección de elementos
ordenada de acuerdo a las posiciones
de éstos (secuencia, relación
predecesor-sucesor)
Listas Ligadas
5
UVM
5.4 Pila Ligada
Listas Ligadas
6
UVM
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
Listas Ligadas
7
UVM
struct node *push(struct node *p, int value)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL) {
printf("No Memory available Error\n");
exit(0);
}
temp->data = value;
temp->link = p;
p = temp; return(p);
}
Listas Ligadas
8
UVM
struct node *pop(struct node *p, int *value)
{
truct node *temp;
if(p==NULL) {
printf(" The stack is empty can not pop Error\n");
exit(0);
}
*value = p->data;
temp = p; p = p->link;
free(temp); return(p);
}
Listas Ligadas
9
UVM
5.5 Cola Ligada
Listas Ligadas
10
UVM
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
Listas Ligadas
11
UVM
void insert(struct node **front, struct node **rear, int value)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
/* creates new node
using data value
passed as parameter */
if(temp==NULL)
{
printf("No Memory available Error\n");
exit(0);
}
temp->data = value;
temp->link=NULL;
if(*rear == NULL)
{
*rear = temp;
*front = *rear;
}
else
{
(*rear)->link = temp;
*rear = temp;
}
Listas Ligadas
12
}
UVM
void delete(struct node **front, struct node **rear, int *value)
{
struct node *temp;
if((*front == *rear) && (*rear == NULL))
{
printf(" The queue is empty cannot delete Error\n");
exit(0);
}
*value = (*front)->data;
temp = *front;
*front = (*front)->link;
if(*rear == temp)
*rear = (*rear)->link;
free(temp);
}
Listas Ligadas
13
UVM
5.6 Lista Ligada
# include <stdio.h>
# include <stdlib.h>
struct node {
int info;
struct node *next;
} ;
typedef struct node *NODEPTR;
Listas Ligadas
14
UVM
NODEPTR getnode()
{
NODEPTR p;
p = (NODEPTR) malloc(sizeof(struct node));
return(p);
}
void freenode(NODEPTR p)
{
free(p);
}
Listas Ligadas
15
UVM
void insafter(NODEPTR p, int x)
{
NODEPTR q;
if (p == NULL) {
printf("insercion nula\n");
exit(1);
}
q = getnode();
q -> info = x;
q -> next = p -> next;
p -> next = q;
}
Listas Ligadas
16
UVM
void insend(NODEPTR *plist, int x)
{
NODEPTR p ,q;
p = getnode();
p->info = x;
p->next = NULL;
if (*plist == NULL)
*plist = p;
else {
for (q = *plist; q->next != NULL; q = q->next)
;
q->next = p;
}
}
Listas Ligadas
17
UVM
void delafter(NODEPTR p, int *px)
{
NODEPTR q;
if ((p == NULL) || (p -> next == NULL)) {
printf("remocion nula\n");
exit(1);
}
q = p ->next;
*px = q -> info;
p -> next = q -> next;
freenode(q);
}
Listas Ligadas
18
UVM
NODEPTR search(NODEPTR list, int x)
{
NODEPTR p;
for (p = list; p != NULL; p = p->next)
if (p->info == x)
return (p);
return (NULL);
}
Listas Ligadas
19
UVM
5.6 Lista Doblemente Ligada
Listas Ligadas
20
UVM
Tarea #5 (entrega 28 Marzo 2009)
Escriba un programa en C que solicite
una expresión aritmética que use varios
paréntesis y que, por medio de una
pila ligada, verifique si la expresión
ttiene el mismo número de paréntesis
abiertos que cerrados.
Listas Ligadas
21
UVM
Listas Ligadas
22
UVM