LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 09-20-2005, 05:14 PM   #1
SeniorSE
LQ Newbie
 
Registered: Nov 2004
Posts: 14

Rep: Reputation: 0
Question Recursion using linked-list of structures


Hi all. I am trying to create a program that uses a linked list of structures. I have the structure and the linked-list main pointer defined as follows:
Code:
typedef struct 
{
	struct ssidlist	*next;
	char * 		ssid;
} ssidlist;

ssidlist *ssids = NULL;
I already have the linked-list created. I have read the items from a file and loaded the list. Now I am trying to recursively delete the last entry in the list. Here is my "remove" function:
Code:
void remove_an_ssid(ssidlist *ss,int i)           /* The i variable is for testing */
{
	printf ("Removal: %i\n",++i);           /* Only for testing purposes 8?
	if (ss->next == NULL)
	{
		printf("Removing SSID: %s\n",ss->ssid);
		free(ss->ssid);
		free(ss->next);
		ss = NULL;
	}
	else
	{
		remove_an_ssid(ss->next,i);
	}
}
I am using the following call to start the removal of the last entry in the linked list.

Code:
				remove_an_ssid(&ssids,0);
What happens is that the last entry in the list is getting "freed", but the linked list is not updating properly. So, when I write the entries in the linked list to a file, the last thing written to the file is bad characters. Here is my write function:
Code:
void write_ssids(char* file)
{
	ssidlist *tmp = ssids;

	FILE *fp;
	fp = fopen(file, "w");

	printf("Writing SSIDS\n");	
	while (tmp != NULL)
	{
		fprintf(fp,"%s\n",tmp->ssid);
		printf("%s\n",tmp->ssid);
		tmp = tmp->next;
	}
	fclose(fp);
}
Thanks for your help.
Mark
 
Old 09-20-2005, 05:20 PM   #2
Matir
LQ Guru
 
Registered: Nov 2004
Location: San Jose, CA
Distribution: Ubuntu
Posts: 8,507

Rep: Reputation: 125Reputation: 125
The removal function is BAD. It tries to free things you TESTED to be NULL (ss->next).
Try this:
Code:
void remove_an_ssid(ssidlist *ss,int i)           /* The i variable is for testing */
{
	printf ("Removal: %i\n",++i);           /* Only for testing purposes */
        if (!ss->next){    /* Avoid null ptr dereference */
             printf("Null NEXT in remove_an_ssid");
             return;
        }
	if (ss->next->next == NULL)
	{
		printf("Removing SSID: %s\n",ss->next->ssid);
		free(ss->next->ssid);
		free(ss->next);
		ss->next = NULL;
	}
	else
	{
		remove_an_ssid(ss->next,i);
	}
}
 
Old 09-20-2005, 05:27 PM   #3
SeniorSE
LQ Newbie
 
Registered: Nov 2004
Posts: 14

Original Poster
Rep: Reputation: 0
I just tried that. When I compiled it, this is the result I got:

Code:
mdhkarma.c: In function ‘in_ssids_list’:
mdhkarma.c:62: warning: assignment from incompatible pointer type
mdhkarma.c: In function ‘write_ssids’:
mdhkarma.c:79: warning: assignment from incompatible pointer type
mdhkarma.c: In function ‘remove_an_ssid’:
mdhkarma.c:92: error: dereferencing pointer to incomplete type
mdhkarma.c:94: error: dereferencing pointer to incomplete type
mdhkarma.c:95: error: dereferencing pointer to incomplete type
mdhkarma.c:101: warning: passing argument 1 of ‘remove_an_ssid’ from incompatible pointer type
mdhkarma.c: In function ‘on_probe_req’:
mdhkarma.c:154: warning: passing argument 1 of ‘remove_an_ssid’ from incompatible pointer type
mdhkarma.c:198: warning: assignment from incompatible pointer type
mdhkarma.c: In function ‘load_ssids’:
mdhkarma.c:230: warning: assignment from incompatible pointer type
make: *** [mdhkarma.o] Error 1
The errors are pointing to the ss->next->next and the ss->next->ssid references.

Mark

Last edited by SeniorSE; 09-20-2005 at 05:28 PM.
 
Old 09-20-2005, 06:04 PM   #4
vladmihaisima
Member
 
Registered: Oct 2002
Location: Delft, Netherlands
Distribution: Gentoo
Posts: 196

Rep: Reputation: 33
You could try to write the definition this way:

Code:
struct ssidlist_struct{
    struct ssidlist_struct*next;
    char * ssid;
};

typedef struct ssidlist_struct ssidlist;
 
Old 09-20-2005, 06:09 PM   #5
SeniorSE
LQ Newbie
 
Registered: Nov 2004
Posts: 14

Original Poster
Rep: Reputation: 0
Thanks! The new struct definition worked beautifully!

Mark
 
Old 09-20-2005, 09:05 PM   #6
Matir
LQ Guru
 
Registered: Nov 2004
Location: San Jose, CA
Distribution: Ubuntu
Posts: 8,507

Rep: Reputation: 125Reputation: 125
Oh yeah, that original struct definition did have some issues to contend with. Hadn't even noticed. Good catch!
 
Old 09-21-2005, 02:40 AM   #7
JCipriani
Member
 
Registered: Aug 2005
Location: Pittsburgh, PA, USA
Distribution: Redhat 9, OS X 10.4.x, Win2K
Posts: 85

Rep: Reputation: 15
I'm trying for the convoluted code awards here:
Code:
int remove_an_ssid (ssidlist **head) {
  int r;
  if ((r = (*head) ? (1 + remove_an_ssid(&((*head)->next))) : 0) == 1) {
    free((*head)->ssid);
    free(*head);
    *head = NULL;
  }
  return r;
}
That one even removes the final element in a list with one element (at least... it should); I don't think any of the previously posted code handled that right. But you use it differently:
Code:
ssidlist *thelist = generate_an_ssidlist();

/* this would remove every element */
while (thelist)
  remove_an_ssid(&thelist);
... maybe.

If you don't need to do it recursively, for any particular reason, though, you may want to consider using a doubly-linked list, and storing a tail pointer as well as a head pointer. Then you can remove the last element in constant time, and not recursively.

Last edited by JCipriani; 09-21-2005 at 03:13 AM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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 Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
C++ Linked List question lowpro2k3 Programming 3 06-16-2005 10:15 AM
linked list + c dilberim82 Programming 5 05-04-2005 11:48 PM
cirular linked list pantera Programming 8 04-21-2005 06:59 AM
tar: '--no-recursion' option doesn't prevent recursion Earl Parker II Slackware 12 08-17-2004 02:49 AM
C++ linked list fun chens_83 Programming 2 08-04-2003 07:40 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 10:45 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration