?
Solved

recursive

Posted on 2006-06-02
11
Medium Priority
?
336 Views
Last Modified: 2010-04-15
Hi all,
 This is my function,
void deleteListLoop(node* &head)
{
      node *tmp= head;
      node *follow_tmp;

      head = NULL;

      while(tmp->next != NULL)
      {
            follow_tmp= tmp;
            tmp = tmp->next;
            printf("data of node being delete is %d\n",follow_tmp->data);
            free(follow_tmp);
      }
      free(tmp);
      head = NULL;
}

please help me to convert to recursive instead of using loop. Thanks a lot.
0
Comment
Question by:valleytech
  • 5
  • 3
9 Comments
 
LVL 24

Accepted Solution

by:
fridom earned 252 total points
ID: 16817831
You code does not compile.
And it has a memory leak.

So let us see  
1) first you have a pointer to the start of the list
2) you have a follow up node which will get the next element of the list
3) you can free the given parameter which you should hand over by reference
because you are going to reset it.
4) you call the same function again with the follower

pseudo C

void deleteListRec (struct node ** head)  // not * &head
  struct node *i_head = *head;
   struct node *next = i_head->next;
   if (NULL == i_head)
       /* done */
  else
     free(i_head);
     i_head = NULL;
     deleteListRec(&next);


that should give you enough of an idea to get on yourself

Regards
Friedrich


0
 

Author Comment

by:valleytech
ID: 16817935
how can my program work? I just compiled and it worked. You can run it

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

struct node{
      int data;
      node* next;
};

void add (node* &head, int a);
void printList(node *head);
void deleteListLoop(node* &head);

void main(void)
{
      int a;
      int yes;
      node *head =NULL;
      int objecta;
      objecta=0;
      printf("do you want to add node? 1 for Yes:  ");
      scanf("%d",&yes);
      while ( yes == 1)
      {
            printf("Enter a new number : ");
            scanf("%d",&a);
            add (head, a);

            printList(head);
            
            printf("do you want to add node? 1 for Yes:  ");
          scanf("%d",&yes);
      }
      yes = 0;
      printf("empty linked list? 1 by LOOP, 2 by RECURSIVE for:  ");
      scanf("%d",&yes);
      if( yes == 1)
      {
            deleteListLoop(head);
            printList(head);
      }
      else
      {
      }
}

void deleteListLoop(node* &head)
{
      node *tmp= head;
      node *follow_tmp;

      head = NULL;

      while(tmp!= NULL)
      {
            follow_tmp= tmp;
            tmp = tmp->next;
            printf("data of node being delete is %d\n",follow_tmp->data);
            free(follow_tmp);
      }
      free(tmp);
      head = NULL;
}

void printList(node *head)
{
      node *tmp= head;

      if(head == NULL)
            printf("List is empty\n");

      while(tmp!= NULL)
      {
            printf(" %d ",tmp->data);
            if(tmp->next != 0)
                  tmp= tmp->next;
            else
                  tmp = 0;
      }
      printf("\n");
}
void add (node* &head, int a)
{
      node *tmp= head;
      node* ptr= new node;
      ptr->data= a;
      ptr->next = NULL;
      
      if(head == NULL) //no node at all
      {
            head = ptr;
      }
      else
      {
            while(tmp->next != 0)
            {
                  tmp= tmp->next;
            }
            tmp->next= ptr;

      }
}
0
 
LVL 24

Expert Comment

by:fridom
ID: 16818009
of course that does not work (as usuayl if you just write thing done.
The error is easy to spot I probably dereference a NULL pointer. That will not work of course.
So the code should be
 free
 i_head = NULL.
 if (next) {
   } else {
    return
}

self post
"Great, keep in mind to not post you have not really run and which does not compile cleanly"

Friedrich
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 

Author Comment

by:valleytech
ID: 16818054
My code WORKS. You can copy and run whole program.
 I don't get your idea Friedrick. sorry.
0
 
LVL 24

Expert Comment

by:fridom
ID: 16818055
Hardly here we go:
gcc -std=c99 -Wall -g ltest.c -ldmalloc
ltest.c:34: Fehler: expected »)« before »*« token

Compilation exited abnormally with code 1 at Fri Jun  2 18:21:25

in that line is the mentioned prototyp.

I don't know what compiler you'r usign but it is not running in C mode maybe this may work in C++
I have no idea however.

And you still have  bug in you code
head = NULL and
tmp != NULL can not owrk you assign tmp to head and set it to NULL so on accessing tmp it should crash.

No I don't think your code has a chance to run.

Regards
Friedrich

Regards
Friedrich
0
 
LVL 24

Expert Comment

by:fridom
ID: 16818095
If you do not belive me let's see what the others say. You code does not compile here:

Here are all the error messages I got:
ltest2.c: In Funktion »main«:
ltest2.c:17: Fehler: »node« nicht deklariert (erste Benutzung in dieser Funktion)
ltest2.c:17: Fehler: (Jeder nicht deklarierte Bezeichner wird nur einmal aufgeführt
ltest2.c:17: Fehler: für jede Funktion in der er auftritt.)
ltest2.c:17: Fehler: »head« nicht deklariert (erste Benutzung in dieser Funktion)
ltest2.c:26: Warnung: Implizite Deklaration der Funktion »add«
ltest2.c:28: Warnung: Implizite Deklaration der Funktion »printList«
ltest2.c:38: Warnung: Implizite Deklaration der Funktion »deleteListLoop«
ltest2.c: Auf höchster Ebene:
ltest2.c:46: Fehler: expected »)« before »*« token
ltest2.c:64: Fehler: expected »)« before »*« token
ltest2.c:81: Fehler: expected »)« before »*« token

So whatever you tell me, the compiler tells me otherwise following the points, I see that the compiler is right
and you are wrong:
first it has to be always struct node or you have to use a typedef. You don't have that in your code.
You dereference a NULL pointer so even if you program would compile it would crash on run time.

Friedrich
0
 

Author Comment

by:valleytech
ID: 16818160
I run the code in windows xp, and Visual c++ 6.0 can compile and run it. It's strange.
0
 
LVL 22

Assisted Solution

by:grg99
grg99 earned 248 total points
ID: 16820262
Theres not much point in doing a recursice delete on a single-linked list..  It's VERY helpful if each node had more than one link.  But here's the general idea:

del( nodeptr p ){
if( p ) {
     del( p->next );
    free(p);
}
}

0
 
LVL 24

Expert Comment

by:fridom
ID: 16822148
Not the code you posted: Here's the outptu of MSVC 6
-------------------Configuration: ltest - Win32 Debug--------------------
Compiling...
ltest2.c
h:\programming\c\list_test\ltest2.c(6) : error C2061: syntax error : identifier 'node'
h:\programming\c\list_test\ltest2.c(7) : error C2059: syntax error : '}'
h:\programming\c\list_test\ltest2.c(9) : error C2143: syntax error : missing ')' before '*'
h:\programming\c\list_test\ltest2.c(9) : error C2143: syntax error : missing '{' before '*'
h:\programming\c\list_test\ltest2.c(9) : error C2059: syntax error : '&'
h:\programming\c\list_test\ltest2.c(9) : error C2059: syntax error : ')'
h:\programming\c\list_test\ltest2.c(10) : error C2143: syntax error : missing ')' before '*'
h:\programming\c\list_test\ltest2.c(10) : error C2143: syntax error : missing '{' before '*'
h:\programming\c\list_test\ltest2.c(10) : error C2059: syntax error : ')'
h:\programming\c\list_test\ltest2.c(11) : error C2143: syntax error : missing ')' before '*'
h:\programming\c\list_test\ltest2.c(11) : error C2143: syntax error : missing '{' before '*'
h:\programming\c\list_test\ltest2.c(11) : error C2059: syntax error : '&'
h:\programming\c\list_test\ltest2.c(11) : error C2059: syntax error : ')'
h:\programming\c\list_test\ltest2.c(17) : error C2065: 'node' : undeclared identifier
h:\programming\c\list_test\ltest2.c(17) : error C2297: '*' : illegal, right operand has type 'int *'
h:\programming\c\list_test\ltest2.c(18) : error C2143: syntax error : missing ';' before 'type'
h:\programming\c\list_test\ltest2.c(19) : error C2065: 'objecta' : undeclared identifier
h:\programming\c\list_test\ltest2.c(26) : warning C4013: 'add' undefined; assuming extern returning int
h:\programming\c\list_test\ltest2.c(28) : warning C4013: 'printList' undefined; assuming extern returning int
h:\programming\c\list_test\ltest2.c(38) : warning C4013: 'deleteListLoop' undefined; assuming extern returning int
h:\programming\c\list_test\ltest2.c(46) : error C2143: syntax error : missing ')' before '*'
h:\programming\c\list_test\ltest2.c(46) : error C2143: syntax error : missing '{' before '*'
h:\programming\c\list_test\ltest2.c(46) : error C2059: syntax error : '&'
h:\programming\c\list_test\ltest2.c(46) : error C2059: syntax error : ')'
h:\programming\c\list_test\ltest2.c(64) : error C2143: syntax error : missing ')' before '*'
h:\programming\c\list_test\ltest2.c(64) : error C2143: syntax error : missing '{' before '*'
h:\programming\c\list_test\ltest2.c(64) : error C2059: syntax error : ')'
h:\programming\c\list_test\ltest2.c(65) : error C2054: expected '(' to follow 'head'
h:\programming\c\list_test\ltest2.c(81) : error C2143: syntax error : missing ')' before '*'
h:\programming\c\list_test\ltest2.c(81) : error C2143: syntax error : missing '{' before '*'
h:\programming\c\list_test\ltest2.c(81) : error C2059: syntax error : '&'
h:\programming\c\list_test\ltest2.c(81) : error C2059: syntax error : ')'
Error executing cl.exe.

So you can tell whatever you like , the code you posted here does not work neither on Windows nor on Linux

The needed corrections are
- declare a global head or give it to all functions as  parameter
- write struct node or have a type def struct node { ....} node;
- fix you deleteion code the following never will get executed:
node *tmp= head;
     node *follow_tmp;

     head = NULL;

     while(tmp!= NULL)
     {
          follow_tmp= tmp;

You never will run into the loop
all the nodes won't get freed you have a gapping memory leak
  }
     free(tmp);
     head = NULL;

you're freeing a NULL pointer which is perfectly valid but surely not what you like to do.

Take the code you posted here and try you luck with your compilation it won't work. DOT

Friedrich

0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
Suggested Courses

862 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question