Scanning a list?

This is a discussion on Scanning a list? within the C Programming forums, part of the General Programming Boards category; I have this declaration of my list: Code: typedef struct NODE{ char *name; struct NODE *next; struct NODE *prev; } ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    58

    Scanning a list?

    I have this declaration of my list:
    Code:
    typedef struct NODE{
    char *name;
    struct NODE *next;
    struct NODE *prev;
    } Person;
    with this input:

    Joe
    Sarah
    Bob
    Jill
    Sarah
    Bob

    If the name is not in the list yet, I need to add it to the end.. which is
    Code:
    sentinel->prev->next = new_node;
    and so on. I got that part.. But I dont know how to stop on a certain node if the name is already in the list, or how do I go about scanning it. Should I use another function? What code ...

    If the name is not in the list, I just use that node for the rest of the program..

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Walk the list. If current_node->name compares equal (via strcmp) with name_I_just_read_in, then stop. If you get to the end, then add a new node.

  3. #3
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    If this were my program, and I were constantly posting questions that seem obsessed with memory preservation, I would change my code to this

    Example:
    Code:
    typedef struct NODE {
      struct NODE *next;
      struct NODE *prev;
      char name[];
    } Person;
    
    Person *person(Person *og, const char *name)
    {
      struct NODE *inserted = malloc(sizeof(*node) + strlen(name) + 1), *node = og;
    
      if(!inserted)
      {
        fputs("Unable to allocate memory!", stderr);
        return node;
      }
    
      inserted->prev = inserted->next = 0;
      strcpy(inserted->name, name);
    
      /* This just allocates teh first node */
      if(!node)
        return inserted;
    
      for(;node->next;node = node->next)
      {
        int cmp = strcmp(node->name, name)
    
        /* Skip duplicates */
        if(!cmp)
          continue;
    
        if(cmp < 0)
        {
          inserted->prev = node->prev;
          inserted->next = node;
    
          if(node->prev)
            node->prev->next = inserted;
    
          node->prev = inserted;
          return og;
        }
      }
    
      if(strcmp(node->name, name) < 0)
      {
        inserted->prev = node->prev;
        inserted->next = node;
    
        if(node->prev)
          node->prev->next = inserted;
    
        node->prev = inserted;
      } else {
        inserted->prev = node;
        node->next = inserted;
      }
    
      return og;  
    }
    That should work... or something like that. I didn't compile this code or anything so sorry if there is a mistake.

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    58
    Quote Originally Posted by master5001 View Post
    If this were my program, and I were constantly posting questions that seem obsessed with memory preservation, I would change my code to this

    Example:
    Code:
    typedef struct NODE {
      struct NODE *next;
      struct NODE *prev;
      char name[];
    } Person;
    
    Person *person(Person *og, const char *name)
    {
      struct NODE *inserted = malloc(sizeof(*node) + strlen(name) + 1), *node = og;
    
      if(!inserted)
      {
        fputs("Unable to allocate memory!", stderr);
        return node;
      }
    
      inserted->prev = inserted->next = 0;
      strcpy(inserted->name, name);
    
      /* This just allocates teh first node */
      if(!node)
        return inserted;
    
      for(;node->next;node = node->next)
      {
        int cmp = strcmp(node->name, name)
    
        /* Skip duplicates */
        if(!cmp)
          continue;
    
        if(cmp < 0)
        {
          inserted->prev = node->prev;
          inserted->next = node;
    
          if(node->prev)
            node->prev->next = inserted;
    
          node->prev = inserted;
          return og;
        }
      }
    
      if(strcmp(node->name, name) < 0)
      {
        inserted->prev = node->prev;
        inserted->next = node;
    
        if(node->prev)
          node->prev->next = inserted;
    
        node->prev = inserted;
      } else {
        inserted->prev = node;
        node->next = inserted;
      }
    
      return og;  
    }
    That should work... or something like that. I didn't compile this code or anything so sorry if there is a mistake.
    lol youre funny.. thanks tho

  5. #5
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    I will wait for someone who likes to pick on me to attempt compiling it since I am not at home atm.

    You should be able to use the above like this.

    Example:
    Code:
    #include <string.h>
    #include <stdio.h>
    #include <ctype.h>
    
    typedef struct NODE {
      struct NODE *next;
      struct NODE *prev;
      char name[];
    } Person;
    
    Person *person(Person *node, const char *name);
    void destroy(Person *node);
    void print(Person *node);
    
    int main(void)
    {
      char buffer[64] = {0};
      Person *node = 0;
    
      puts("Please put in a name (or 'Q' to quit): ");
    
      while(fgets(buffer, sizeof(buffer), stdin))
      {
        strtok(buffer, "\n");
    
        if(toupper(buffer[0]) == 'Q')
          break;
    
        node = person(node, buffer);
        puts("Put in another name (or 'Q' to quit): ");
      };
    
      print(node);
      destroy(node);
    
      return 0;
    }
    
    void destory(Person *node)
    {
      Person *head = node;
    
      for(;head->prev; head = head->prev) { }
      for(node = head; node; node = head)
      {
        head = node->next;
        free(node);
      }
    }
    
    void print(Person *node)
    {
      Person *head = node;
      int i = 1;
    
      for(;head->prev; head = head->prev) { }
      for(node = head; node; node = head, ++i)
      {
        head = node->next;
        printf("&#37;02d. %s\n", i, node->name);
      }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 08:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 04:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21