Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > structs and how to access them

Reply
Thread Tools

structs and how to access them

 
 
Martin Marcher
Guest
Posts: n/a
 
      08-10-2003
Hi,

I'm working on a program that creates a linear list of structs

struct lin_list{
struct lin_list *next;
char Name[BUFF];
};

this is what it looks like. And i got (design) problems with the search
function and delete function. I thought about searching like this

while(strcmp(list->next->Name, somestring) != 0){
list = list->next;
}

which should do the following return the elment just before the one that
is searched, this way I could easily reuse the search function for
deletion because I don't have to run it twice to get the element before
the one that gets deleted, and still use it to output the element that was
searched for by just doing

element = element->next;
fprintf(stdout, "format_here");

is this a proper way?

I admit I didn't even try wether it will work or not, because I thought
I'll ask you guys first if this is a proper logic to use.

Hope that was somehow clear

thx
Martin

--
http://wiki.mnemonisch.net

"Are [Linux users] lemmings collectively jumping off of the cliff of
reliable, well-engineered commercial software?"
(By Matt Welsh)

 
Reply With Quote
 
 
 
 
Morris Dovey
Guest
Posts: n/a
 
      08-11-2003
Martin Marcher wrote:

> I'm working on a program that creates a linear list of structs
>
> struct lin_list{
> struct lin_list *next;
> char Name[BUFF];
> };
>
> this is what it looks like. And i got (design) problems with the search
> function and delete function. I thought about searching like this
>
> while(strcmp(list->next->Name, somestring) != 0){
> list = list->next;
> }
>
> which should do the following return the elment just before the one that
> is searched, this way I could easily reuse the search function for
> deletion because I don't have to run it twice to get the element before
> the one that gets deleted, and still use it to output the element that was
> searched for by just doing
>
> element = element->next;
> fprintf(stdout, "format_here");
>
> is this a proper way?
>
> I admit I didn't even try wether it will work or not, because I thought
> I'll ask you guys first if this is a proper logic to use.


Martin...

Since you didn't want to try it out, I didn't too. You may want
to consider what happens if the search doesn't succeed (i.e. when
you reach the end of the list...

You've piqued my curiosity - why aren't you comparing somestring
to list->Name ?
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c

 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      08-11-2003
Morris Dovey wrote:
> Martin Marcher wrote:
>
> > I'm working on a program that creates a linear list of structs
> >
> > struct lin_list{
> > struct lin_list *next;
> > char Name[BUFF];
> > };
> >
> > this is what it looks like. And i got (design) problems with
> > the search function and delete function. I thought about
> > searching like this
> >
> > while(strcmp(list->next->Name, somestring) != 0){
> > list = list->next;
> > }
> >
> > which should do the following return the elment just before
> > the one that is searched, this way I could easily reuse the
> > search function for deletion because I don't have to run it
> > twice to get the element before the one that gets deleted,
> > and still use it to output the element that was searched for
> > by just doing
> >
> > element = element->next;
> > fprintf(stdout, "format_here");
> >
> > is this a proper way?
> >
> > I admit I didn't even try wether it will work or not, because
> > I thought I'll ask you guys first if this is a proper logic to
> > use.

>
> Since you didn't want to try it out, I didn't too. You may want
> to consider what happens if the search doesn't succeed (i.e.
> when you reach the end of the list...
>
> You've piqued my curiosity - why aren't you comparing somestring
> to list->Name ?


It is a well known algorithm for allowing list item deletion.
However there are traps, such as how to find the first element.
The fact that he didn't bother to try it out is significant. If
he had he might have found the problems, which are not insoluble.

--
Chuck F ((E-Mail Removed)) ((E-Mail Removed))
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


 
Reply With Quote
 
Martin Marcher
Guest
Posts: n/a
 
      08-11-2003
On Mon, 11 Aug 2003 01:42:10 +0000, CBFalconer wrote:

> Morris Dovey wrote:
>> Martin Marcher wrote:
>> > search function and delete function. I thought about searching like
>> > this
>> >
>> > while(strcmp(list->next->Name, somestring) != 0){

^^^^^^^^^^^^^^^^

That's the point, I know that I could easily test it, but as you said
there could be Problems (I guess not in my implementation of the list, as
I am using a dummy element as the first on - I guess Otherwise I just
would need a cyclic list).


>> > list = list->next;
>> > }

>>
>> Since you didn't want to try it out, I didn't too. You may want to
>> consider what happens if the search doesn't succeed (i.e. when you reach
>> the end of the list...
>>
>> You've piqued my curiosity - why aren't you comparing somestring to
>> list->Name ?


Thats because if I want to delete elemene with list->Name == 'test' and I
search for list->next->Name I can return the significant element (the one
just before 'test') and then use something like:

position = list->next; // to get the element I want to actually delete
free(position);

otherwise I would have a problem, as there is no pointer to the previous
element. My question was more if the logic of accessing and deleting items
is an [good|bad|acceptable] one then asking you guys to compile and test
this, sorry if this came thru wrong .
>
> It is a well known algorithm for allowing list item deletion. However
> there are traps, such as how to find the first element. The fact that he
> didn't bother to try it out is significant. If he had he might have found
> the problems, which are not insoluble.


As said my first element is a dummy element, so to find the first struct
containing data, i simply use the second one which solves the problem - at
least in some way.

thx
Martin

--
http://wiki.mnemonisch.net

How do I type "for i in *.dvi do xdvi i done" in a GUI?
(Discussion in comp.os.linux.misc on the intuitiveness of interfaces.)

 
Reply With Quote
 
Chris Torek
Guest
Posts: n/a
 
      08-11-2003
In article <(E-Mail Removed)>
Martin Marcher <(E-Mail Removed)> writes:
[background discussion on why he wants to have a search function
that finds "the item before the desired item":]
>... if I want to delete elemene with list->Name == 'test' and I
>search for list->next->Name I can return the significant element (the one
>just before 'test') and then use something like:
>
>position = list->next; // to get the element I want to actually delete
>free(position);
>
>otherwise I would have a problem, as there is no pointer to the previous
>element. My question was more if the logic of accessing and deleting items
>is an [good|bad|acceptable] one then asking you guys to compile and test
>this, sorry if this came thru wrong .


As I think Chuck noted, you can indeed do this, although there are
various corner cases to watch out for.

There is, however, a "more C-like" way to handle the problem. That
is, there is a way to do this in C that is forbidden in quite a few
other languages. (If there is something you can do in C and assembly,
but not in [say] Pascal, I often call that "quite C-like" .)

Suppose we have a linked-list data structure:

struct list {
struct list *next;
... actual data here ...
};

and a pointer to the head of (i.e., first entry in) the list, which
is initially NULL when the list is empty:

struct list *head = NULL;

Now, in C, we can write the "find entry in list" function so that
it returns a pointer to the <pointer that points to the entry>
(enclosed in <angle brackets> as the pointer points to that item).
Assume for the moment that the item is guaranteed to be in the list,
and consider the following code:

struct list **searchfor(key_type key) {
struct list **pp, *cur;

for (pp = &head; (cur = *pp) != NULL; pp = &cur->next) {
if (SAME_ITEM(key, cur))
break;
}
return pp;
}

Given the "item will be in the list" assumption, one of the SAME_ITEM
tests will succeed and the loop will stop via the "break". We then
return "pp", the value of the pointer through which we found "cur",
which is the matching item.

If the matching item is the head of the list, pp == &head. Otherwise
pp is the address of some list-item's "next" field. To remove the
found item, we need only write:

struct list **pp, *item;

pp = searchfor(key);
item = *pp;
*pp = item->next;

Now "item" is the found item, and *pp -- which is either "head"
itself, or the "next" element of the list entry that points to
"item" -- has been changed to point to item->next. In other words,
if we found the first item in the list, we have just modified "head"
itself, otherwise we have removed some mid-list item, or even the
last item in the list (by having item->next==NULL).

All of this hinges on the "item guaranteed to be in list" condition.
What if the item is *not* in the list?

In that case, no SAME_ITEM test will succeed, and eventually the
loop will stop on the test in the "for" itself, i.e., when cur
becomes NULL. In this case, "pp" is still valid, and is a pointer
to a "struct list *", but *pp is NULL. The searchfor() function
will return this pointer value, whatever it is.

Thus, the test for "was the item found" is:

pp = searchfor(key);
item = *pp;
if (item == NULL) /* it was not found */
...

Again, it is possible that pp == &head, in which case the list is
empty. If the list is *not* empty, however, pp points to the "next"
pointer of the last item in the list. If we now desire to add a
new item to the end of the list, we merely need to do this:

/* newitem->next = NULL; -- if not already set */
*pp = newitem;

To make searchfor() more general, it is better to modify it so that
"head" is not a "global variable" (whatever "global variable" means
to you, the reader) in searchfor(). Note that the only thing
searchfor() does with "head" is take its address. If searchfor()
simply requires the *caller* to take the address, the function
can then work on any list-head:

struct list **searchfor(struct list **phead, key_type key) {
struct list **pp, *cur;

for (pp = phead; (cur = *pp) != NULL; pp = &cur->next) {
if (SAME_ITEM(key, cur))
break;
}
return pp;
}

/* and then later: */
pp = searchfor(&head, key);

In practice, however, linked-list walking is so trivial that doing
this sort of fancy "search, but return a pointer to the pointer
that points to the item" thing is rarely worthwhile. You can just
do the loop in-line wherever needed (e.g., for deletion), and do
the more obvious loop in-line where practical (e.g., for insertion).
If your list is sorted, it might be OK to use this scheme -- but
maintaining sorted lists is not something one should do all that
often either (the time complexity is O(n^2); if the lists are short,
the extra code does not pay off, and if the lists are long, you
are probably better off with a balanced tree or hash table or some
such).
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.
 
Reply With Quote
 
Joe Wright
Guest
Posts: n/a
 
      08-11-2003
CBFalconer wrote:
>
> Morris Dovey wrote:
> > Martin Marcher wrote:
> >
> > > I'm working on a program that creates a linear list of structs
> > >
> > > struct lin_list{
> > > struct lin_list *next;
> > > char Name[BUFF];
> > > };
> > >
> > > this is what it looks like. And i got (design) problems with
> > > the search function and delete function. I thought about
> > > searching like this
> > >
> > > while(strcmp(list->next->Name, somestring) != 0){
> > > list = list->next;
> > > }
> > >
> > > which should do the following return the elment just before
> > > the one that is searched, this way I could easily reuse the
> > > search function for deletion because I don't have to run it
> > > twice to get the element before the one that gets deleted,
> > > and still use it to output the element that was searched for
> > > by just doing
> > >
> > > element = element->next;
> > > fprintf(stdout, "format_here");
> > >
> > > is this a proper way?
> > >
> > > I admit I didn't even try wether it will work or not, because
> > > I thought I'll ask you guys first if this is a proper logic to
> > > use.

> >
> > Since you didn't want to try it out, I didn't too. You may want
> > to consider what happens if the search doesn't succeed (i.e.
> > when you reach the end of the list...
> >
> > You've piqued my curiosity - why aren't you comparing somestring
> > to list->Name ?

>
> It is a well known algorithm for allowing list item deletion.
> However there are traps, such as how to find the first element.
> The fact that he didn't bother to try it out is significant. If
> he had he might have found the problems, which are not insoluble.
>

I've done it this way...

typedef struct node {
size_t size;
void *allo;
struct node *next;
} node;
static node dummy; /* size == 0 and pointers == NULL */
static node *head = &dummy; /* point to the dummy */
static node *prev, *this, *that; /* pointers for keeping track of
things. */

/* Find the node containing allo == p.
Return pointer to the node or NULL if not found. */

static node *
fnd(void *p) {
for (this = head->next; this; prev = this, this = this->next) {
if (this->allo == p)
break;
}
return this;
}

--
Joe Wright (E-Mail Removed)
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
 
Reply With Quote
 
Al Bowers
Guest
Posts: n/a
 
      08-11-2003


Joe Wright wrote:
> CBFalconer wrote:
>
>>Morris Dovey wrote:
>>
>>>Martin Marcher wrote:
>>>
>>>
>>>>I'm working on a program that creates a linear list of structs
>>>>
>>>>struct lin_list{
>>>> struct lin_list *next;
>>>> char Name[BUFF];
>>>>};
>>>>
>>>>this is what it looks like. And i got (design) problems with
>>>>the search function and delete function. I thought about
>>>>searching like this
>>>>
>>>>while(strcmp(list->next->Name, somestring) != 0){
>>>> list = list->next;
>>>>}
>>>>
>>>>which should do the following return the elment just before
>>>>the one that is searched, this way I could easily reuse the
>>>>search function for deletion because I don't have to run it
>>>>twice to get the element before the one that gets deleted,
>>>>and still use it to output the element that was searched for
>>>>by just doing
>>>>
>>>>element = element->next;
>>>>fprintf(stdout, "format_here");
>>>>
>>>>is this a proper way?
>>>>
>>>>I admit I didn't even try wether it will work or not, because
>>>>I thought I'll ask you guys first if this is a proper logic to
>>>>use.
>>>
>>>Since you didn't want to try it out, I didn't too. You may want
>>>to consider what happens if the search doesn't succeed (i.e.
>>>when you reach the end of the list...
>>>
>>>You've piqued my curiosity - why aren't you comparing somestring
>>>to list->Name ?

>>
>>It is a well known algorithm for allowing list item deletion.
>>However there are traps, such as how to find the first element.
>>The fact that he didn't bother to try it out is significant. If
>>he had he might have found the problems, which are not insoluble.
>>

>
> I've done it this way...
>
> typedef struct node {
> size_t size;
> void *allo;
> struct node *next;
> } node;
> static node dummy; /* size == 0 and pointers == NULL */
> static node *head = &dummy; /* point to the dummy */
> static node *prev, *this, *that; /* pointers for keeping track of
> things. */
>
> /* Find the node containing allo == p.
> Return pointer to the node or NULL if not found. */
>
> static node *
> fnd(void *p) {
> for (this = head->next; this; prev = this, this = this->next) {
> if (this->allo == p)
> break;
> }
> return this;
> }
>


I don't believe this solves the concern of the OP.
If the return value is not NULL, then you have returned
a pointer value which points to the found node.
Now, you want to delete that node.
You can do this by using the return value of function fnd as
the arguement in function free.
However, once the node is freed, the linked list is broken
because the node previous(if there is one) to the deleted
node how points to space that has been deallocated.

There are ways to get around this problem but IMO I think
a better way is to redesign your struct and associated functions.

You could make the struct

typedef struct lin_list
{
struct lin_list *prev;
struct lin_list *next;
char Name[256];
}lin_list;

Then the search and deletion functions are more easily made.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUFF 256

typedef struct lin_list{
struct lin_list *prev;
struct lin_list *next;
char Name[BUFF];
}lin_list;

lin_list *AddListNode(lin_list **head, const char *name);
void DeleteListNode(lin_list **p, lin_list *del);
lin_list *SearchList(lin_list *head, const char *name);
void FreeList(lin_list **p);
void PrintList(lin_list *p);

int main(void)
{
lin_list *tmp,*list = NULL;

AddListNode(&list,"Abe Lincoln");
AddListNode(&list,"Bill Clinton");
AddListNode(&list,"George Washington");
AddListNode(&list, "George Bush");
if(tmp = SearchList(list,"Bill Clinton"))
DeleteListNode(&list,tmp); /* delete a node */
PrintList(list);
FreeList(&list);
return 0;
}

lin_list *AddListNode(lin_list **p, const char *name)
{
lin_list *tmp, *current;

if((tmp = malloc(sizeof(*tmp))) == NULL) return NULL;
strncpy(tmp->Name,name,BUFF);
tmp->next = NULL;
if(*p == NULL)
{
tmp->prev = NULL;
*p = tmp;
return tmp;
}
for(current = *p; ; current = current->next)
if(current->next == NULL) break;
current->next = tmp;
tmp->prev = current;
return tmp;
}

void DeleteListNode(lin_list **p, lin_list *del)
{
if(del == *p) /* the head is being deleted */
{
if(del->next)
del->next->prev = NULL;
*p = del->next;
}
else
{
del->prev->next = del->next;
del->next->prev = del->prev;
}
free(del);
return;
}

lin_list *SearchList(lin_list *head, const char *name)
{
for( ; head ; head = head->next)
if(strcmp(head->Name,name) == 0) break;
return head;
}

void FreeList(lin_list **p)
{
lin_list *current, *tmp;

for(current = *p; current; current = tmp)
{
tmp = current->next;
free(current);
}
*p = NULL;
return;
}

void PrintList(lin_list *p)
{
for( ; p; p = p->next)
puts(p->Name);
return;
}



--
Al Bowers
Tampa, Fl USA
mailto: http://www.velocityreviews.com/forums/(E-Mail Removed) (remove the x)
http://www.geocities.com/abowers822/

 
Reply With Quote
 
Martin Marcher
Guest
Posts: n/a
 
      08-11-2003
On Mon, 11 Aug 2003 00:54:49 -0600, Chris Torek wrote:
> In practice, however, linked-list walking is so trivial that doing this
> sort of fancy "search, but return a pointer to the pointer that points to
> the item" thing is rarely worthwhile. You can just do the loop in-line
> wherever needed (e.g., for deletion), and do the more obvious loop in-line
> where practical (e.g., for insertion). If your list is sorted, it might be
> OK to use this scheme -- but maintaining sorted lists is not something one
> should do all that often either (the time complexity is O(n^2); if the
> lists are short, the extra code does not pay off, and if the lists are
> long, you are probably better off with a balanced tree or hash table or
> some such).


Well I do this more to get two tasks in one, my next course will be "System
Programming under UNIX" which obviously deals with C and since I don't
have any experience at all this will be a good exercise and second (why I
code the list) is that the exam for Algorithms and Datastructures will be
soon. I thought trying to code lists, hash-tables, trees (and search thru them
with the introduced algorithms) would be another good exercise, maybe I'll
even get to 'external searching' - I don't know a better translation, I
mean the kind of searching where you can't have all the data in memory and
therefore have to leave parts of it on the disk.

Well anyway pointers to pointers, like you used it, is quite a topic to
work thru for now.

thx
Martin
--
http://wiki.mnemonisch.net

"Oh, I've seen copies [of Linux Journal] around the terminal room at The
Labs."
(By Dennis Ritchie)
 
Reply With Quote
 
Joe Wright
Guest
Posts: n/a
 
      08-11-2003
Al Bowers wrote:
>
> Joe Wright wrote:
> > CBFalconer wrote:
> >
> >>Morris Dovey wrote:
> >>
> >>>Martin Marcher wrote:
> >>>
> >>>
> >>>>I'm working on a program that creates a linear list of structs
> >>>>
> >>>>struct lin_list{
> >>>> struct lin_list *next;
> >>>> char Name[BUFF];
> >>>>};
> >>>>
> >>>>this is what it looks like. And i got (design) problems with
> >>>>the search function and delete function. I thought about
> >>>>searching like this
> >>>>
> >>>>while(strcmp(list->next->Name, somestring) != 0){
> >>>> list = list->next;
> >>>>}
> >>>>
> >>>>which should do the following return the elment just before
> >>>>the one that is searched, this way I could easily reuse the
> >>>>search function for deletion because I don't have to run it
> >>>>twice to get the element before the one that gets deleted,
> >>>>and still use it to output the element that was searched for
> >>>>by just doing
> >>>>
> >>>>element = element->next;
> >>>>fprintf(stdout, "format_here");
> >>>>
> >>>>is this a proper way?
> >>>>
> >>>>I admit I didn't even try wether it will work or not, because
> >>>>I thought I'll ask you guys first if this is a proper logic to
> >>>>use.
> >>>
> >>>Since you didn't want to try it out, I didn't too. You may want
> >>>to consider what happens if the search doesn't succeed (i.e.
> >>>when you reach the end of the list...
> >>>
> >>>You've piqued my curiosity - why aren't you comparing somestring
> >>>to list->Name ?
> >>
> >>It is a well known algorithm for allowing list item deletion.
> >>However there are traps, such as how to find the first element.
> >>The fact that he didn't bother to try it out is significant. If
> >>he had he might have found the problems, which are not insoluble.
> >>

> >
> > I've done it this way...
> >
> > typedef struct node {
> > size_t size;
> > void *allo;
> > struct node *next;
> > } node;
> > static node dummy; /* size == 0 and pointers == NULL */
> > static node *head = &dummy; /* point to the dummy */
> > static node *prev, *this, *that; /* pointers for keeping track of
> > things. */
> >
> > /* Find the node containing allo == p.
> > Return pointer to the node or NULL if not found. */
> >
> > static node *
> > fnd(void *p) {
> > for (this = head->next; this; prev = this, this = this->next) {
> > if (this->allo == p)
> > break;
> > }
> > return this;
> > }
> >

>
> I don't believe this solves the concern of the OP.
> If the return value is not NULL, then you have returned
> a pointer value which points to the found node.
> Now, you want to delete that node.
> You can do this by using the return value of function fnd as
> the arguement in function free.
> However, once the node is freed, the linked list is broken
> because the node previous(if there is one) to the deleted
> node how points to space that has been deallocated.
>
> There are ways to get around this problem but IMO I think
> a better way is to redesign your struct and associated functions.
>
> You could make the struct
>

[snip}

I should have included more code. Note that fnd() will have set 'prev'
to point to the node preceding 'this', therefore...

void
Free(void *ptr) {
if (fnd(ptr)) {
prev->next = this->next;
free(this->allo);
free(this);
}
}

--
Joe Wright (E-Mail Removed)
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Packed structs vs. unpacked structs: what's the difference? Daniel Rudy C Programming 15 04-10-2006 08:10 AM
Array of structs instead of an array with pointers to structs? Paminu C Programming 5 10-11-2005 07:18 PM
const structs in other structs Chris Hauxwell C Programming 6 04-27-2004 07:03 PM
structs with fields that are structs Patricia Van Hise C Programming 5 04-05-2004 01:37 AM



Advertisments