Analizando los punteros de una linked list
Agosto 10 2009 :: Estructuras de datos, c ::
Uno de los temas que es difícil de entender en C es el tema de los punteros y como se relacionan con las estructuras de datos. Lo difícil ( o por lo menos fue difícil para mi que venia de lenguajes dinámicos ) es entender que los punteros guardan direcciones a memoria y a que a partir de esto se puede hacer el entrelazamiento de diferentes estructuras apuntadas. Voy a usar los ejemplo de linked list de C & Data Structures para mostrar como se da esto.
Primero creamos la estructura y una función para insertar elementos en la misma:
struct node {
int data;
struct node *link;
};
/*Insert en versión recursiva */
struct node *insert(struct node *p, int n) {
if(p==NULL) {
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL) {
printf("Allocation Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
} else {
p->link = insert(p->link,n);
}
return(p);
}
Nota: Se hace la búsqueda del ultimo nodo para insertar en forma recursiva.
Luego hago una función para mostrar la lista:
void printnode( struct node *p) {
printf("Memory Space: %p\t Value: %d \t Link: %p\t\n",p, p-> data, p-> link);
}
void printlist ( struct node *p ) {
printf("The data values in the list are\n");
while (p!= NULL) {
printnode(p);
p = p-> link;
}
}
La función printnode, muestra primero la dirección de memoria de la estructura, después su valor y finalmente la dirección de memoria a la que apunta, de esta manera podemos ver como se enlazan los nodos dentro de la lista.
Agregando y borrando nodos.
/* a function which inserts a newly created node after the specified
node */
//node_no empieza en 0 como en los arrays
struct node * newinsert ( struct node *p, int node_no, int value ) {
struct node *temp, * temp1;
int i;
temp = p;
for(i=0; i<node_no && temp->link != NULL; i++) {
temp = temp->link;
}
if(i != node_no ) {
printf("Se pide insertar en un nodo mayor a la cantidad existente, se agrega tras el ultimo nodo existente.\n");
}
temp1 = ( struct node * )malloc ( sizeof ( struct node ));
if ( temp1 == NULL ) {
printf( " Cannot allocate \n");
exit (0);
}
temp1->data = value;
temp1->link = temp->link;
printf("The newly created node to be inserted is:\n");
printnode(temp1);
temp->link = temp1;
return(p);
}
struct node * erasenode( struct node *p, int node_no) {
struct node *temp, *prev;
int i;
temp = p;
if(node_no == 0) {
temp = p->link;
free(p);
p = temp;
} else {
i = 0;
while(i<node_no && temp->link != NULL) {
prev = temp;
temp = temp->link;
i++;
}
if(i != (node_no)) {
printf("Se pide borrar un nodo que no existe.\n");
exit(0);
}
prev->link = temp->link;
free(temp);
}
return(p);
}
Corriéndolo en el main:
int main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n-- > 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start,x);
}
printf("The created list is\n");
printlist ( start );
start = newinsert(start, 2, 7);
printlist (start);
start = erasenode(start, 2);
printlist ( start );
return 0;
}
Resultado en pantalla:
Enter the nodes to be created
5
Enter the data values to be placed in a node
5
Enter the data values to be placed in a node
4
Enter the data values to be placed in a node
3
Enter the data values to be placed in a node
2
Enter the data values to be placed in a node
1
The created list is
The data values in the list are
Memory Space: 0x81a5008 Value: 5 Link: 0x81a5018
Memory Space: 0x81a5018 Value: 4 Link: 0x81a5028
Memory Space: 0x81a5028 Value: 3 Link: 0x81a5038
Memory Space: 0x81a5038 Value: 2 Link: 0x81a5048
Memory Space: 0x81a5048 Value: 1 Link: (nil)
The newly created node to be inserted is:
Memory Space: 0x81a5058 Value: 7 Link: 0x81a5038
The data values in the list are
Memory Space: 0x81a5008 Value: 5 Link: 0x81a5018
Memory Space: 0x81a5018 Value: 4 Link: 0x81a5028
Memory Space: 0x81a5028 Value: 3 Link: 0x81a5058
Memory Space: 0x81a5058 Value: 7 Link: 0x81a5038
Memory Space: 0x81a5038 Value: 2 Link: 0x81a5048
Memory Space: 0x81a5048 Value: 1 Link: (nil)
The data values in the list are
Memory Space: 0x81a5008 Value: 5 Link: 0x81a5018
Memory Space: 0x81a5018 Value: 4 Link: 0x81a5058
Memory Space: 0x81a5058 Value: 7 Link: 0x81a5038
Memory Space: 0x81a5038 Value: 2 Link: 0x81a5048
Memory Space: 0x81a5048 Value: 1 Link: (nil)
Se ve aca como en la primera corrida los nodos estan ubicados uno tras otro en la memoria, pero al agregar un nuevo nodo se salta en el tercer nodo ( en este caso, Memory Space: 0x81a5028 Value: 3 Link: 0x81a5058 ) se salta al agregado ( Memory Space: 0x81a5058 Value: 7 Link: 0x81a5038 ) y del agregado al que antes existia contiguamente ( Memory Space: 0x81a5038 Value: 2 Link: 0x81a5048 ). Algo similar ocurre cuando se borra un nodo.
Revirtiendo y ordenando la lista.
/* a function to sort reverse list */
struct node *reverse(struct node *p) {
struct node *prev, *curr;
prev = NULL;
curr = p;
while (curr != NULL) {
p = p-> link;
curr-> link = prev;
prev = curr;
curr = p;
}
return(prev);
}
/* a function to sort a list */
struct node *sortlist(struct node *p)
{
struct node *temp1,*temp2,*min,*prev,*q;
q = NULL;
while(p != NULL) {
//Encontrar el menor de la lista p
prev = NULL;
min = temp1 = p;
temp2 = p -> link;
while ( temp2 != NULL ) {
if(min -> data > temp2 -> data) {
min = temp2;
prev = temp1;
}
temp1 = temp2;
temp2 = temp2-> link;
}
//Cambiar el link en la lista p del previo al menor al siguiente del menor
if(prev == NULL) {
p = min -> link;
} else {
prev -> link = min -> link;
}
//Agregar el menor a q
min -> link = NULL;
if( q == NULL){
q = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q as a first node*/
} else {
temp1 = q;
/* traverses the list pointed to by q to get pointer to its last node */
while( temp1 -> link != NULL) {
temp1 = temp1 -> link;
}
temp1 -> link = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q at the end of list pointed by q*/
}
}
return (q);
}
Vemos la impresión en pantalla de como quedan ordenados los nodos:
The sorted list is
The data values in the list are
Memory Space: 0x8c03048 Value: 1 Link: 0x8c03038
Memory Space: 0x8c03038 Value: 2 Link: 0x8c03018
Memory Space: 0x8c03018 Value: 4 Link: 0x8c03008
Memory Space: 0x8c03008 Value: 5 Link: 0x8c03058
Memory Space: 0x8c03058 Value: 7 Link: (nil)
The reversed list is
The data values in the list are
Memory Space: 0x8c03058 Value: 7 Link: 0x8c03008
Memory Space: 0x8c03008 Value: 5 Link: 0x8c03018
Memory Space: 0x8c03018 Value: 4 Link: 0x8c03038
Memory Space: 0x8c03038 Value: 2 Link: 0x8c03048
Memory Space: 0x8c03048 Value: 1 Link: (nil)
Referencias
C & Data Structures, Deshpande, Kakde; Charles River Media, 2004
Autor: Emiliano Martínez Luque.
Deja un Comentario
Guía de los comentarios
Tu Email es requerido pero no sera publicado.
Podes usar los siguientes tags de HTML:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>Si no comentastes antes tu comentario debera ser aprovado antes de que se lo muestre. Perdón, pero hay demasiado spam.