Menu
▾
▴
Re: [Dev-C++] Single Linked List-IV
|
From: Luigi S. <gi...@li...> - 2003-06-11 05:43:37
|
> > > On Sat, Jun 07, 2003 at 09:38:34PM +0200, Per Westermark wrote:
> > > [...]
> > >
> > > I know it's a bit extra noisy with dual indirection, but
> > > since the code
> > > is C and not C++, slstore() can't take references to pointers.
> > >
> > > /Per W
> > On Sun, June 08, 2003 9:15 AM +0200, Luigi Santillo wrote:
> > Probably, he could have avoided the double indirection using
> > something like:
> >
> > struct slist
> > {
> > struct address *start;
> > struct address *last;
> > };
> >
> > so that a pointer to "struct slist" would be used, still allowing
> > all changes to "start" and "last" to be made.
> Mon, 9 Jun 2003 06:09:28 +0300 Ioannis Vranos wrote:
> And why use such tricks in the first place and not single pointers?
Well the "trick" I suggest above, reflects my personal C-newbie tastes :-)
I immagine that experienced programmers have more elegant solutions.
However, allow me to say something about the interface of a list
which, for simplicity, has the following two functions:
- push_back = append an element
- pop_front = extract front element
So far, 3 solutions seem to have arisen:
#1: "dual indirection" proposed by Andre' Macario Barros
#2: "list structure" (that is, the newbie "trick" suggested by me)
#3: "single pointers" as I seem to have understood from mail sent
by Ioannis Vranos
Here is a possible way the 3 interfaces might look.
--------------- #1: dual indirection ---------------------
#ifndef list_h
#define list_h
struct l_node
{
void *data; /* address of item to be stored */
struct l_node *next; /* next element on the list */
};
/* add data to the back, return 0 if unable to allocate memory for a
new element, 1 on success */
int
l_push_back(void *data, struct l_node **head_ptr, struct l_node **tail_ptr);
/* pop data from front of a list, return 0 if there is nothing on the
list or pointer stored on the list */
void *
l_pop_front(struct l_node **head_ptr, struct l_node **tail_ptr);
#endif
--------------- #1: end ----------------------------------
---------------- #2: list structure ---------------------
#ifndef list_h
#define list_h
struct l_node
{
void *data; /* address of item to be stored */
struct l_node *next; /* next element on the list */
};
struct list
{
struct l_node *head; /* first node: where pop occurs */
struct l_node *tail; /* last node: where push occurs */
};
/* add data to the back, return 0 if unable to allocate memory for a
new element, 1 on success */
int
l_push_back(void *data, struct list *lptr);
/* pop data from front of a list, return 0 if there is nothing on the
list or pointer stored on the list */
void *
l_pop_front(struct list *lptr);
#endif
---------------- #2: end ---------------------------------
---------------- #3: single pointers ---------------------
#ifndef list_h
#define list_h
struct l_node
{
void *data; /* address of item to be stored */
struct l_node *next; /* next element on the list */
};
/* add data to the back, return 0 if unable to allocate memory for a
new element, 1 on success */
int
l_push_back(void *data, struct l_node *head, struct l_node *tail);
/* pop data from front of a list, return 0 if there is nothing on the
list or pointer stored on the list */
void *
l_pop_front(struct l_node *head, struct l_node *tail);
#endif
---------------- #3: end ---------------------------------
It is clear to me that, upon pushing some data on the list, the
"head" might change while the "tail" will surely change; thus:
- solution proposed by Andre' Macario Barros (dual indirection),
is correct, in fact passing the address of "head" and "tail"
allows changes made by function "l_push_back" to be seen outside
the scope of the function.
- my "trick" (list structure) is correct too, in fact by passing
the address of the list structure and modifying "head" and "tail"
inside function "l_push_back", again changes are seen outside
the scope of the function.
- using "single pointers", seems not to be correct, in that changes
made to "head" and "tail", are changes made to a copy of the pointers
local to the function "l_push_back", thus the updated values are
not seen outside the scope of the function.
Similar reasoning holds for function "l_pop_front".
For the sake of completeness, here are the 3 implementations which
complete the "list" and which I have used for my simple tests.
---------------- #1: dual indirection --------------------
#include <stdlib.h>
#include "list.h"
/********************************************************************/
int
l_push_back(void *data, struct l_node **head_ptr, struct l_node **tail_ptr)
{
struct l_node *nptr = malloc(sizeof(struct l_node));
if (nptr) /* load node and link it */
{
nptr->data = data;
nptr->next = 0; /* new node will be last one */
if (*tail_ptr) /* there is already something */
(*tail_ptr)->next = nptr;
else /* first node */
*head_ptr = nptr;
*tail_ptr = nptr; /* new nodes becomes last one */
return 1;
}
else
return 0;
}
/********************************************************************/
void *
l_pop_front(struct l_node **head_ptr, struct l_node **tail_ptr)
{
void *data = *head_ptr ? (*head_ptr)->data : 0;
if (*head_ptr) /* detach first node */
{
struct l_node *ptr = *head_ptr;
*head_ptr = ptr->next; /* set new head */
free(ptr); /* deallocate memory */
if (*head_ptr == 0) /* there is nothing left */
*tail_ptr = 0; /* reset tail pointer */
}
return data;
}
---------------- #1: end ---------------------------------
---------------- #2: list structure ---------------------
#include <stdlib.h>
#include "list.h"
/********************************************************************/
int
l_push_back(void *data, struct list *lptr)
{
struct l_node *nptr = malloc(sizeof(struct l_node));
if (nptr) /* load node and link it */
{
nptr->data = data;
nptr->next = 0; /* new node will be last one */
if (lptr->tail) /* there is already something */
lptr->tail->next = nptr;
else /* first node */
lptr->head = nptr;
lptr->tail = nptr; /* new nodes becomes last one */
return 1;
}
else
return 0;
}
/********************************************************************/
void *
l_pop_front(struct list *lptr)
{
void *data = (lptr->head) ? lptr->head->data : 0;
if (lptr->head) /* detach first node */
{
struct l_node *ptr = lptr->head;
lptr->head = ptr->next; /* set new head */
free(ptr); /* deallocate memory */
if (lptr->head == 0) /* there is nothing left */
lptr->tail = 0; /* reset tail pointer */
}
return data;
}
---------------- #2: end ---------------------------------
---------------- #3: single pointers ---------------------
#include <stdlib.h>
#include "list.h"
/********************************************************************/
int
l_push_back(void *data, struct l_node *head, struct l_node *tail)
{
struct l_node *nptr = malloc(sizeof(struct l_node));
if (nptr) /* load node and link it */
{
nptr->data = data;
nptr->next = 0; /* new node will be last one */
if (tail) /* there is already something */
tail->next = nptr;
else /* first node */
head = nptr;
tail = nptr; /* new nodes becomes last one */
return 1;
}
else
return 0;
}
/********************************************************************/
void *
l_pop_front(struct l_node *head, struct l_node *tail)
{
void *data = head ? head->data : 0;
if (head) /* detach first node */
{
struct l_node *ptr = head;
head = ptr->next; /* set new head */
free(ptr); /* deallocate memory */
if (head == 0) /* there is nothing left */
tail = 0; /* reset tail pointer */
}
return data;
}
---------------- #3: end ---------------------------------
Finally here are the 3 functions I used to test the "list"
---------------- #1: dual indirection --------------------
#include <stdio.h>
#include "list.h"
static void
print(const struct l_node *head);
int
main()
{
struct l_node *head = 0; /* first element */
struct l_node *tail = 0; /* last element */
int data[] = { 1 , 2, 3, 0 }; /* data */
int *p = 0; /* iterator */
puts("\n\n1) Loading list from back");
for (p = data; *p; p++) /* add another element to the list */
{
printf("\n\npushing value: %d\n", *p);
l_push_back(p, &head, &tail);
print(head);
}
puts("\n\n2) Popping values from front");
while ((p = (int *)l_pop_front(&head, &tail)))
{
printf("\n\npopped value: %d\n", *p);
print(head);
}
return 0;
}
/********************************************************************/
void
print(const struct l_node *head)
{
const struct l_node *iter;
printf("%5s %10s %10s\n", "data", "node", "next");
for (iter = head; iter; iter = iter->next)
{
int *p = (int *)iter->data;
printf("%5d %10p %10p\n", *p, iter, iter->next);
}
}
---------------- #1: end ---------------------------------
---------------- #2: list structure ---------------------
#include <stdio.h>
#include "list.h"
static void
print(const struct list *lptr);
int
main()
{
struct list ls = { 0, 0 }; /* list to be filled */
int data[] = { 1 , 2, 3, 0 }; /* data */
int *p = 0; /* iterator */
puts("\n\n1) Loading list from back");
for (p = data; *p; p++) /* add another element to the list */
{
printf("\n\npushing value: %d\n", *p);
l_push_back(p, &ls);
print(&ls);
}
puts("\n\n2) Popping values from front");
while ((p = (int *)l_pop_front(&ls)))
{
printf("\n\npopped value: %d\n", *p);
print(&ls);
}
return 0;
}
/********************************************************************/
void
print(const struct list *lptr)
{
struct l_node *iter;
printf("%5s %10s %10s\n", "data", "node", "next");
for (iter = lptr->head; iter; iter = iter->next)
{
int *p = (int *)iter->data;
printf("%5d %10p %10p\n", *p, iter, iter->next);
}
}
---------------- #2: end ---------------------------------
---------------- #3: single pointers ---------------------
#include <stdio.h>
#include "list.h"
static void
print(const struct l_node *head);
int
main()
{
struct l_node *head = 0; /* first element */
struct l_node *tail = 0; /* last element */
int data[] = { 1 , 2, 3, 0 }; /* data */
int *p = 0; /* iterator */
puts("\n\n1) Loading list from back");
for (p = data; *p; p++) /* add another element to the list */
{
printf("\n\npushing value: %d\n", *p);
l_push_back(p, head, tail);
print(head);
}
puts("\n\n2) Popping values from front");
while ((p = (int *)l_pop_front(head, tail)))
{
printf("\n\npopped value: %d\n", *p);
print(head);
}
return 0;
}
/********************************************************************/
void
print(const struct l_node *head)
{ /* same implementation of the case #1: "dual indirection" */ }
---------------- #3: end ---------------------------------
Excuse me for the long post and forgive me if I have missed the point
about the "single pointer" approach; at the heart I am a newbie and
have much yet to learn.
Regards
--
>> gisan >>
|
