473,320 Members | 2,177 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

structs and how to access them

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)

Nov 13 '05 #1
8 2039
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

Nov 13 '05 #2
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 (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #3
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.)

Nov 13 '05 #4
In article <pa****************************@gmx.at>
Martin Marcher <ma*******@gmx.at> 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 (40°39.22'N, 111°50.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.
Nov 13 '05 #5
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 mailto:jo********@earthlink.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Nov 13 '05 #6


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: xa*@abowers.combase.com (remove the x)
http://www.geocities.com/abowers822/

Nov 13 '05 #7
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)
Nov 13 '05 #8
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 mailto:jo********@earthlink.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Nov 13 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: news.microsoft.com | last post by:
Hi, I am using structs and am also using property accessors to access those private member fields... TO me this is a good way of handling them, but I find alot of people using direct access to...
11
by: Roman Hartmann | last post by:
hello, I do have a question regarding structs. I have a struct (profil) which has a pointer to another struct (point). The struct profil stores the coordinates of points. The problem is that I...
5
by: Paminu | last post by:
Why make an array of pointers to structs, when it is possible to just make an array of structs? I have this struct: struct test { int a; int b;
17
by: goldfita | last post by:
I saw some code that appeared to do something similar to this struct foo { char offset; int d; }; struct foo { int a; int b;
5
by: Bilgehan.Balban | last post by:
Hi, I am currently brushing up my c++ knowledge and I would like to ask you about the differences between classes and C structs, in the function/method perspective. 1) Is it correct to say...
8
by: Christian Christmann | last post by:
Hi, I was wondering how the =operator works for struct. When I for example define a struct as follows: struct point { int a; char *c;
61
by: Marty | last post by:
I am new to C# and to structs so this could be easy or just not possible. I have a struct defined called Branch If I use Branch myBranch = new Branch(i); // everything works If I use Branch...
17
by: Johan Tibell | last post by:
Could someone outline the pros and cons of typedefing pointers to structs like this? typedef struct exp_ { int val; struct exp_ *child; } *exp; (This is straight from memory so it might not...
29
by: Dom | last post by:
I'm really confused by the difference between a Struct and a Class? Sometimes, I want just a group of fields to go together. A Class without methods seems wrong, in that it carries too much...
43
by: JohnQ | last post by:
Are a default constructor, destructor, copy constructor and assignment operator generated by the compiler for a struct if they are not explicitely defined? I think the answer is yes, because...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.