Recursion using linked-list of structures

SeniorSE · 09-20-2005, 05:14 PM

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

Matir · 09-20-2005, 05:20 PM

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);
	}
}

SeniorSE · 09-20-2005, 05:27 PM

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

vladmihaisima · 09-20-2005, 06:04 PM

You could try to write the definition this way:

Code:

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

typedef struct ssidlist_struct ssidlist;

SeniorSE · 09-20-2005, 06:09 PM

Thanks! The new struct definition worked beautifully!

Mark

Matir · 09-20-2005, 09:05 PM

Oh yeah, that original struct definition did have some issues to contend with. Hadn't even noticed. Good catch!

JCipriani · 09-21-2005, 02:40 AM

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.