Expert: Zlatko - 5/22/2010

Question
QUESTION: Hello.
Given a (dynamic allocated) list in C:

/* The solution must use this type of list,even if a list with a pointer *prev and a pointer *next make things

easier */

typedef struct elem {
 int value;
 struct elem * next; /* pointer to the next elem */
} Elem;

typedef Elem * List; /* Pointer at the current elem of the list */

I need to define a RECURSIVE function.Inputs are:a list of integer and a integer
Function prototype:
List delete(List l,int val)

The function must delete every occurrence of val (the element from the list is deleted if l->value = val)
(
What create difficultes to me is to delete RECURSIVELY an element from the list,WITHOUT a pointer *prev,WITHOUT

add more parameters to the function <-- those hypothesis are forces by the exercise directives
I tried considering couple of elements,and if the second element of the couple has to been deleted I set (to the

element pointed by the second element of the couple) the pointer next of the first element of the couple and i

delete(free()) the element to delete.
If the element is the first(or the last) I delete it and set the new list head to the next element (or to NULL if

there is no next element).
THE PROBLES I CAN'T RESOLVE ARE:
- how to the determinate when I'm on the FIRST element
- how to handle couple of elements WITHOUT add parameters to the functions,WITHOUT alterate list structure AND

WITHOUT use a ITERATIVE function
)
Thanks in advance.

ANSWER: Hello Manuel.

You do not need to know if you are on the real first element of the list. For the purpose of the delete function, the Elem pointer passed in as "l" is the first element. The recursive idea is to accept sub-lists and return sub-lists which are then attached to the main list.

I hope it will become clear with the code and comments below. I have renamed the delete function to deleteElem, because delete is a C++ keyword.

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

typedef struct elem {
   int value;
   struct elem * next; /* pointer to the next elem */
} Elem;

typedef Elem * List; /* Pointer at the current elem of the list */

List deleteElem(List l, int val)
{
   /* every recursive function needs an exit condition to stop the recursion */
   if (l == NULL) return NULL;

   /*
   the deleteElem function works on a sublist.
   The head of the sublist is l.
   l points to the first element of the sublist.
   if the first value is to be deleted, the function returns the list
   resulting from deleting val from the sublist starting from l->next
   */
   if (l->value == val)
   {
       List next = l->next;
       free(l);
       return deleteElem(next, val);
   }

   /*
   if the first element (l) is not to be deleted, l->next gets the result of
   deleting val from the sublist starting at l->next.
   */
   l->next = deleteElem(l->next, val);
   return l;
}

List init()
{
   List first = NULL;
   int x;

   for(x = 0; x < 10; x++)
   {
       Elem* e = (Elem*)malloc(sizeof(Elem));
       e->value = x % 3;
       e->next = NULL;

       if (first == NULL) first = e;
       else
       {
         e->next = first;
         first = e;
       }
   }

   return first;
}

void print(List l)
{
   if (l == NULL)
   {
       printf("List is empty\n");
       return;
   }

   while(l != NULL)
   {
       printf("%d ", l->value);
       l = l->next;
   }
   printf("\n");
}

int main(void)
{
   List l = init();
   printf("The list\n");
   print(l);

   printf("Delete 0\n");
   l = deleteElem(l, 0);
   print(l);

   printf("Delete 1\n");
   l = deleteElem(l, 1);
   print(l);

   printf("Delete 2\n");
   l = deleteElem(l, 2);
   print(l);

   return 0;
}

---------- FOLLOW-UP ----------

QUESTION: it's perfect but if the element to eliminate is the first it miss (infinitive loop)

(
List Definition:

typedef struct elem {
 char * val;
 struct elem_s * next;
} Elem;

typedef Elem * List;

)

The function I used is the following (the same,just it works on strings dynamic allocated):

List deleteElem(List l,char* s)
{
if (l==NULL)
  return NULL;
if (strcmp(l->val,s)==0)
{
 List aux=l->next;
 free(l->val); /* I deallocate the space for the field "l->val" which is a dynamic allocated string.I tried also omitting this instruction but same problem */
 free(l);
 return deleteElem(aux,s);
}
l->next=deleteElem(l->next,s);
return l;
}

Thanks again

ANSWER: I'm sorry I cannot re-create the problem. Please send me your entire program, and I'll have a look at it.

---------- FOLLOW-UP ----------

QUESTION: just try your code but eliminating the FIRST element of the list

Answer
I did try it.

The program I sent you makes a list of
0 2 1 0 2 1 0 2 1 0
It then deletes all the zeros, then all the ones, then all the twos, finally ending up with an empty list. I believe the algorithm is good, but you may have another problem causing the infinite loop. Send me a private question if you don't want your code seen by others. Or, send your code to zlatko.c.help at gmail.com