Thread: counting nodes

  1. #1
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    counting nodes

    ok I FINALLY got this program to work correctly!!!
    now we have been asked to add a function that counts the nodes.

    Here's my whole program thus far.

    [code]


    /*********************/
    /* stack.c */
    /*********************/


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


    struct node {
    int data; /* 1st item of node */
    struct node *next; /* 2nd item of node */
    };

    struct node *first = NULL; /* global variable */
    struct node *new_node; /* need pointers for
    dynamic mem alloc */

    /* PROTOTYPES - all made as void types */

    void push(int insert_value);
    void pop();
    void print_list();
    void choice_list(void);
    void count_nodes();


    /* count_nodes : counts the number of nodes in current list */
    void count_nodes()
    {
    for (new_node = first; new_node != NULL; new_node = new_node->next) {
    new_node++;}
    printf("Number of nodes in your list is %d",new_node);
    }


    /* push : adds a value entered to list */
    void push(int insert_value)
    {
    new_node=malloc(sizeof(struct node));
    new_node->data = insert_value;
    new_node->next = first;
    first = new_node;
    }

    /* pop : deletes value/node on top of list */
    void pop()
    {
    if (first == NULL) {
    return ;
    }
    else {
    printf("You want to delete %d.\n",first->data);
    first = first->next;
    printf("So here is your list now :\n");
    print_list();
    return ;
    }
    }

    /* print_list : prints out the values in list with -> to show order of list */
    void print_list()
    {
    if (new_node == NULL) {
    return ;
    }

    else {
    while (new_node != NULL) {
    printf("%d -> ",new_node->data);
    new_node = new_node->next;
    }

    printf("NULL\n\n");
    }
    }

    /* choice_list : prompt to user to make of what function to do next */
    void choice_list(void)
    {
    printf("Choose one of the following.\n"
    "0 To end program\n"
    "1 To add a value to list\n"
    "2 To remove a value from list\n"
    "3 To count number of nodes in list\n");
    }

    /* START OF MAIN */
    main()
    {
    int number,choice;

    for( ; ; ) {
    choice_list();
    printf("Enter your choice :");
    scanf("%d",&choice);
    printf("\n");

    switch(choice) {
    case 0:
    printf("You have ended the program.\n"
    "Good-bye !!\n\n");
    exit(0);

    case 1:
    printf("Enter a number integer : ");
    scanf("%d",&number);
    push(number);
    print_list();
    break;

    case 2:
    pop();
    break;

    case 3:
    count_nodes();
    break;

    default:
    printf("That is an invalid choice\n\n");
    break;

    }
    printf("\n");
    }
    printf("End of run.\n");
    return 0;
    }
    Sue B.

    dazed and confused


  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > struct node *new_node; /* need pointers for
    dynamic mem alloc */
    This should really be a local variable.

    for (new_node = first; new_node != NULL; new_node = new_node->next) {
    new_node++;}
    printf("Number of nodes in your list is %d",new_node);

    Try
    int count = 0;
    for (new_node = first; new_node != NULL; new_node = new_node->next) {
    count++;}
    printf("Number of nodes in your list is %d",count);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    thanks, here's more to add to the program

    so cool. Thanks, Salem !!! I started to do it that way, but wasn't sure.


    now lastly, how to delete a node with a given value:
    instructor said this is a bit tricky to do. but he didn't give any hints about it.

    Code:
    /*********************/
    /*  stack.c          */
    /*********************/
    
    
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct node {
       int data;                      /*  1st item of node */
       struct node *next;              /*  2nd item of node */
    };
    
    struct node *first = NULL;        /*  global variable  */
    struct node *new_node;            /*  need pointers for
                                          dynamic mem alloc  */
    
    void push(int insert_value);
    void pop();
    void print_list();
    void choice_list(void);
    void count_nodes();
    
    struct node *search_list(struct node *list, int n);
    struct node *delete_from_list(struct node *list, int n);
    
    
    void count_nodes()
    {
      int count;
      for (new_node = first; new_node != NULL;
                  new_node = new_node->next) {
          count++;
      }
      printf("The number of nodes in your list is %d\n\n",
               count);
    }
    void push(int insert_value)
    {
       new_node=malloc(sizeof(struct node));
       new_node->data = insert_value;
       new_node->next = first;
       first = new_node;
    }
    
    void pop()
    {
      if (first == NULL)   {
       return ;
    
      }
      else  {
        printf("You want to delete %d.\n",first->data);
        first = first->next;
        printf("So here is your list now :\n");
        print_list();
        return ;
      }
    }
    
    void print_list()
    {
      if (new_node == NULL) {
      return ;
      }
    
      else   {
         while (new_node != NULL)   {
            printf("%d -> ",new_node->data);
            new_node = new_node->next;
         }
    
         printf("NULL\n\n");
    
      }
    }
    
    void choice_list(void)
    {
      printf("Choose one of the following.\n"
             "0   To end program\n"
             "1   To add a value to list\n"
             "2   To remove a value from list\n"
             "3   To count number of nodes in list\n"
             "4   To delete a specific value in list\n");
    }
    
    
    main()
    {
       int number,choice;
       int x;
    
       for( ; ; )   {
         choice_list();
         printf("Enter your choice :");
         scanf("%d",&choice);
         printf("\n");
    
         switch(choice)   {
          case 0:
            printf("You have ended the program.\n"
                   "Good-bye !!\n\n");
            exit(0);
    
          case 1:
            printf("Enter a number integer : ");
            scanf("%d",&number);
            push(number);
            print_list();
            break;
    
          case 2:
            pop();
            break;
    
          case 3:
            count_nodes();
            break;
      */  not sure about this at all  */
    
          case 4:
            printf("Which value in list do you want to delete?"\n);
            scanf("%d",first->data);
            search_list(????,first->data);
            delete_from_list(?????,first->);
            break;
    
          default:
            printf("That is an invalid choice\n\n");
            break;
    
        }
       printf("\n");
      }
      printf("End of run.\n");
      return 0;
    }
    so here's my first stab at the functions search_list and
    delete_from_list which look like they are both used to find the value to delete and then implement the deletion itself.

    Please critique as you wish. Be kind, though. I am a newbie trying to make sense of this difficult language.

    Code:
    /*   search_list  : finds a value in your list  */
    
    struct node *search_list(struct node *list, int n)      
    {   
        
        for (; list  != NULL; list = list->next)
            if (list->data == n)
                 return list;
        return NULL;
    }
    
    
    /*  delete_from_list  : deletes value/node from list when given a value   */
    
    struct node *delete_from_list(struct node *list, int in)
    {
         for (cur = list, prev = NULL;
            cur != NULL && cur -> data !=n;
            prev = cur, cur = cur->next)
         ;
         
         if (cur == NULL)
           return list;                 /*n was not found */
         if (prev == NULL)
           list = list->next;        /* n is in the first node */
         else 
           prev->next = cur->next;      /* n is in some other node */
         free (cur);
         return list;
    }

    my biggest questions

    Where do you declare CUR and PREV to be the current and previous nodes ?

    What the heck is list for exactly (first and new_node are already pointers used do I need another pointer?) and how do you call the functions where list is an argument?
    Sue B.

    dazed and confused


  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You declare the prev and current nodes in the function itself. The idea of a function is to keep things as self-contained as possible. If you are deleting a node, you, unless otherwise required, usually don't return anything, or return an error state:
    Code:
    int deleteNode( struct node *list, int value )
    {
       struct node *prev, *curr;
       for( prev = curr = list; curr; )
       {
          /* if we find our value, delete and stop searching */
          if ( curr->value == value )
          {
             if ( prev != curr )
                prev->next = cur->next;
             else 
                list = curr->next;
    
             free( curr );
             return 0; /* success */
          }
          prev = curr;
          curr = curr->next;
       }
       return -1;
    }
    That should do it. Double linked lists are _SO_ much better for this. Infinitely easier. None of this loop crap and worrying about what is current what is previous...

    Quzah.

  5. #5
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    using the following main() function:

    how do I call the delete_node function ???
    what argument is used in the call for the *list

    Code:
    main()
    {
       int number,choice;
       int x;
    
       for( ; ; )   {
         choice_list();
         printf("Enter your choice :");
         scanf("%d",&choice);
         printf("\n");
    
         switch(choice)   {
          case 0:
            printf("You have ended the program.\n"
                   "Good-bye !!\n\n");
            exit(0);
    
          case 1:
            printf("Enter a number integer : ");
            scanf("%d",&number);
            push(number);
            print_list();
            break;
    
          case 2:
            pop();
            break;
    
          case 3:
            count_nodes();
            break;
      */  not sure about this at all  */
    
          case 4:
            printf("Which value in list do you want to delete?"\n);
            scanf("%d",first->data);
     
            deleteNode( XXXXX      ,first->data);        <--------- what goes here where XXXXX is??
    
           break;
    
          default:
            printf("That is an invalid choice\n\n");
            break;
    
        }
       printf("\n");
      }
      printf("End of run.\n");
      return 0;
    }
    here's your function
    Code:
    int deleteNode( struct node *list, int value )
    {
       struct node *prev, *curr;
       for( prev = curr = list; curr; )
       {
          /* if we find our value, delete and stop searching */
          if ( curr->value == value )
          {
             if ( prev != curr )
                prev->next = cur->next;
             else 
                list = curr->next;
    
             free( curr );
             return 0; /* success */
          }
          prev = curr;
          curr = curr->next;
       }
       return -1;
    }
    Sue B.

    dazed and confused


  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The function takes two arguments:

    1) The head of the list. (ie: the top, your node anchor.)
    2) The value in a given node, to delete.

    You could use it something like:
    Code:
    if( deleteNode( myLinkedList, someInteger ) < 0 )
    {
       printf("Error deleting node: %d not found in list.\n",  someInteger );
    }
    else
    {
       printf("Node containing %d deleted succesfully.\n", someInteger );
    }
    Or, in your case (no pun intended):
    Code:
    case 4:
        printf("Which value in list do you want to delete?"\n);
        scanf("%d",  &someInteger );
        if( deleteNode( myLinkedList, someInteger ) < 0 )
        {
            printf("Error deleting node: %d not found in list.\n",  someInteger );
        }
        else
        {
            printf("Node containing %d deleted succesfully.\n", someInteger );
        }
    break;
    Quzah.

  7. #7
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    function deleteNode not working properly;
    I try adding nodes; then deleting the top value (#2 in choices);
    then printing; all work fine until I choose #5 to delete any value in list.

    What is wrong here?
    Is the call of the function wrong (case 5)?
    Is the function wrong ?

    it goes into infinite loop if i add to list then try to delete using choice 5.

    Please explain my errors

    Code:
    59 /accounts/student2/srbkpk>more stack1.c
    /*********************/
    /*  stack.c          */
    /*********************/
    
    
    #include <stdio.h>
    #include <stdlib.h>
    
    struct node {
       int data;                      /*  1st item of node */
       struct node *next;              /*  2nd item of node */
    };
    
    struct node *first = NULL;        /*  global variable  */
    struct node *new_node;            /*  need pointers for
                                          dynamic mem alloc  */
    
    void push(int insert_value);
    void pop();
    void print_list();
    void choice_list(void);
    void count_nodes();
    int deleteNode(struct node *list,int value);
    
    void count_nodes()
    {
      int count;
      for (new_node = first; new_node != NULL;
                  new_node = new_node->next) {
          count++;
      }
      printf("The number of nodes in your list is %d\n\n",
               count);
    }
    void push(int insert_value)
    {
       new_node=malloc(sizeof(struct node));
       new_node->data = insert_value;
       new_node->next = first;
       first = new_node;
    }
    
    void pop()
    {
      if (first == NULL)   {
       return ;
      }
      else  {
        printf("You want to delete %d.\n",first->data);
        first = first->next;
        printf("So here is your list now :\n");
        print_list();
        return ;
      }
    }
    
    void print_list()
    {
      if (new_node == NULL) {
      return ;
      }
    
      else
           printf("\n\nHere is your list:  \n");
    
       {
           while (new_node != NULL)   {
    
    
              printf("%d \n",new_node->data);
              new_node = new_node->next;
           }
    
           printf("NULL\n\n");
       }
    }
    
    void choice_list(void)
    {
      printf("\n\n\nChoose one of the following.\n"
             "0   To end program\n"
             "1   To add a value to list\n"
             "2   To remove a value from list\n"
             "3   To count number of nodes in list\n"
             "4   To print list \n"
             "5   To delete a specific value from your list\n");
    }
    
    int deleteNode( struct node *list, int value )
    {
       struct node *prev, *cur;
       for( prev = cur = list; cur; )
       {
          /* if we find our value, delete and stop searching */
          if ( cur->data == value )
          {
             if ( prev != cur )
                prev->next = cur->next;
             else
                list = cur->next;
    
             free( cur );
             return 0; /* success */
          }
          prev = cur;
          cur = cur->next;
       }
       return -1;
    }
    
    main()
    {
       int number,choice;
    
       for( ; ; )   {
         choice_list();
         printf("Enter your choice :");
         scanf("%d",&choice);
         printf("\n");
    
         switch(choice)   {
          case 0:
            printf("You have ended the program.\n"
                   "Good-bye !!\n\n");
            exit(0);
    
          case 1:
            printf("Enter a number integer : ");
            scanf("%d",&number);
            push(number);
            break;
    
          case 2:
            pop();
            break;
    
          case 3:
            count_nodes();
            break;
    
          case 4:
            print_list();
            break;
    
          case 5:
            printf("What value do you want to delete from"
                   " your list : \n");
            scanf("%d",&first->data);
            if (deleteNode(first,first->data)<0)  {
               printf("Error deleting node; %d not found"
                          "in list\n",first->data);
               }
            else {
               printf("Node containing %d deleted successfully\n",
                       first->data);
            }
            break;
    
          default:
            printf("That is an invalid choice\n\n");
            break;
    
        }
       printf("\n");
      }
      printf("End of run.\n");
      return 0;
    }
    Sue B.

    dazed and confused


  8. #8
    Registered User C_Coder's Avatar
    Join Date
    Oct 2001
    Posts
    522
    A couple of things:
    You declare struct node *first and initialise it to NULL Then pass it to a function where you are using it, but it doesn't point to a structure(I may have missed something, apologises's in advance if i have).

    Also you free the pointer cur in the function delete_node but it wasn't created dynamically so I don't think your allowed to free it.

    lastly in the scanf in case 5 you use the & in front of first, I dont think thats neccessary.

    Thats all I saw if I'm wrong about some of it, sorry in advance.

    All spelling mistakes, syntatical errors and stupid comments are intentional.

  9. #9
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    deleting a node by value

    Anyone else care to give a shot to how to delete a specific node.
    Quzah's code is not working, maybe cause I call the function wrong, maybe cause I need to use existing struct variables declared globally, I don't know.

    case 5 and deleteNode function aren't in sync, and I am out of ideas here.

    The code I wrote earlier with search_list and delete_from_list functions supposedly working together to find a number in a list then delete, that was from the book, but I don't see that that worked either. ....... the variables (pointers) cur (for current node) and prev (for previous node) seem to be the key to this dumb thing, but I don't get it.
    Sue B.

    dazed and confused


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. counting nodes BST
    By qubit67 in forum C Programming
    Replies: 2
    Last Post: 05-01-2007, 07:46 AM
  2. Programmatically creating nodes in a treeview problem
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 10-12-2006, 02:41 PM
  3. interchange nodes in a linked list
    By Gustavo in forum C++ Programming
    Replies: 0
    Last Post: 10-26-2004, 07:14 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM