Thread: 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..

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.

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.

Originally Posted by master5001

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

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