Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › Ordered Linked List Add Function - C
New Posts  All Forums:Forum Nav:

Ordered Linked List Add Function - C

post #1 of 5
Thread Starter 
Okay guys, I have a bug in my C project that I just can't get and it's driving me insane.

The program I'm working with takes names from general input, parses them into names and stores them in a linked ordered list. ( ordered by first name)
So, my program has two .c files, one main.c and one list.c.

list.c contains a struct...
Code:
struct node
{
  char *firstName;
  char *lastName;
  struct node *next;
};

And three functions, one that makes that takes two char pointers and makes the head (one pointer is a first name, the other pointer is a last name) and returns the head. One that takes a struct pointer for the head and a struct pointer for the new item it added. And one that prints out the contents of the list.

I know my makeList function and printList function works, because thorough testing, my problem is my add function...
Code:
struct node * addNode(struct node *head, struct node *newNode)
{   
  //If there is only one node in the list
  if (strcmp(newNode->firstName, head->firstName) < 0)
    {
      newNode->next = head;
      head = newNode;
    }

  //If there is more then one node in the list
  else
    {

      struct node *current, *prev;
      int found;

      current = head;
      prev = current;
      found = 0;

      while ( current->next != 0 && found == 0)
        {
          if ( strcmp(newNode->firstName, current->firstName) < 0)
            {
              found = 1;
            }

          prev = current;
          current = current->next;
        }
      
      if ( found == 1 )
        {
          prev->next = newNode;
          newNode->next = current;
        }
      else
        {
          current->next = newNode;
        }
    }

  return head;
}


If i put in the input...

Christian Doe
Alex Smith
Tony John
Joe Leone

I get...

Alex Smith
Christian Doe
Tony John
Joe Leone


It only prints out of order if there are 4 or more items put into the list...
Can anyone spot out any bugs I have? I tried a whole bunch of stuff, and I'm ready to pull my hair out.
Cheers guys.
Griever
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-3570K ASUS P8Z77-V Deluxe MSI R7950 Twin Frozr 3GB Corsair Vengeance 16GB 1600Mhz 
Hard DriveCoolingOSMonitor
OCZ Vertex Plus 120GB Corsair h100 Windows 7 Professional Asus VS228H-P 21.5In 
KeyboardPowerCase
Razer Black Widow Ultimate Corsair AX850 NZXT Switch 810 White 
  hide details  
Reply
Griever
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-3570K ASUS P8Z77-V Deluxe MSI R7950 Twin Frozr 3GB Corsair Vengeance 16GB 1600Mhz 
Hard DriveCoolingOSMonitor
OCZ Vertex Plus 120GB Corsair h100 Windows 7 Professional Asus VS228H-P 21.5In 
KeyboardPowerCase
Razer Black Widow Ultimate Corsair AX850 NZXT Switch 810 White 
  hide details  
Reply
post #2 of 5
Thread Starter 
Just pumping with more names to see what I'm dealing with.

Say I use...

Alex Smith
Christian Doe
Tony John
Barry White
Joe Leone
Nick Free
Eric Richards
Sal Free

I get...

Alex Smith
Barry White
Christian Doe
Eric Richards
Nick Free
Sal Free
Tony John
Joe Leone

As output.
Griever
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-3570K ASUS P8Z77-V Deluxe MSI R7950 Twin Frozr 3GB Corsair Vengeance 16GB 1600Mhz 
Hard DriveCoolingOSMonitor
OCZ Vertex Plus 120GB Corsair h100 Windows 7 Professional Asus VS228H-P 21.5In 
KeyboardPowerCase
Razer Black Widow Ultimate Corsair AX850 NZXT Switch 810 White 
  hide details  
Reply
Griever
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-3570K ASUS P8Z77-V Deluxe MSI R7950 Twin Frozr 3GB Corsair Vengeance 16GB 1600Mhz 
Hard DriveCoolingOSMonitor
OCZ Vertex Plus 120GB Corsair h100 Windows 7 Professional Asus VS228H-P 21.5In 
KeyboardPowerCase
Razer Black Widow Ultimate Corsair AX850 NZXT Switch 810 White 
  hide details  
Reply
post #3 of 5
Does this help?
Code:
struct node * addNode(struct node *head, struct node *newNode)
{   
  struct node *n = head;
  while (n->next != null && strcmp(newNode->firstName, n->next->firstName) < 0) n = n->next;
  newNode->next = n->next;
  n->next = newNode;
  return head; //why head? fluent interface?
}

Edited by metala - 11/20/12 at 4:00am
Ferberite
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz Lenovo Thinkpad Edge E520 AMD Radeon HD 6630M 6GB DDR3 @ 1333MHz  
Hard DriveHard DriveOSOS
Samsung 850EVO HITACHI HTS727550A9E364 7.2krpm Debian 7.0 Win7 
OSMonitorMonitorKeyboard
Win8 15.6 Zoll 16:9, 1366x768 Pixel, AUO23EC, spiege... 24" Dell U2412M, 1920x1200 Integrated + External 
PowerCase
20V, 4.5A Lenovo Thinkpad Edge 
  hide details  
Reply
Ferberite
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz Lenovo Thinkpad Edge E520 AMD Radeon HD 6630M 6GB DDR3 @ 1333MHz  
Hard DriveHard DriveOSOS
Samsung 850EVO HITACHI HTS727550A9E364 7.2krpm Debian 7.0 Win7 
OSMonitorMonitorKeyboard
Win8 15.6 Zoll 16:9, 1366x768 Pixel, AUO23EC, spiege... 24" Dell U2412M, 1920x1200 Integrated + External 
PowerCase
20V, 4.5A Lenovo Thinkpad Edge 
  hide details  
Reply
post #4 of 5
Thread Starter 
Quote:
Originally Posted by metala View Post

Does this help?
Code:
struct node * addNode(struct node *head, struct node *newNode)
{   
  struct node *n = head;
  while (n->next != null && strcmp(newNode->firstName, n->next->firstName) < 0) n = n->next;
  newNode->next = n->next;
  n->next = newNode;
  return head; //why head? fluent interface?
}

He's making us return head incase the actual head of the list changes, I guess there are better ways to do it. But he wants us to do it this way. :/

And I'll give it a try in a sec.

It didn't work :/
Edited by Saucee - 11/20/12 at 9:24am
Griever
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-3570K ASUS P8Z77-V Deluxe MSI R7950 Twin Frozr 3GB Corsair Vengeance 16GB 1600Mhz 
Hard DriveCoolingOSMonitor
OCZ Vertex Plus 120GB Corsair h100 Windows 7 Professional Asus VS228H-P 21.5In 
KeyboardPowerCase
Razer Black Widow Ultimate Corsair AX850 NZXT Switch 810 White 
  hide details  
Reply
Griever
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i5-3570K ASUS P8Z77-V Deluxe MSI R7950 Twin Frozr 3GB Corsair Vengeance 16GB 1600Mhz 
Hard DriveCoolingOSMonitor
OCZ Vertex Plus 120GB Corsair h100 Windows 7 Professional Asus VS228H-P 21.5In 
KeyboardPowerCase
Razer Black Widow Ultimate Corsair AX850 NZXT Switch 810 White 
  hide details  
Reply
post #5 of 5
Strange...
Look what i just got:
Code:
metala@ferberite:~/tmp/c$ ./a.out 
Alex Smith
Christian Doe
Tony John
Barry White
Joe Leone
Nick Free
Eric Richards
Sal Free

Printing...

My Head
Tony John
Sal Free
Nick Free
Joe Leone
Eric Richards
Christian Doe
Barry White
Alex Smith

And the source
Code:
metala@ferberite:~/tmp/c$ cat test.c 
#include <stdio.h>


struct node
{
  char *firstName;
  char *lastName;
  struct node *next;
};

struct node * addNode(struct node *head, struct node *newNode)
{   
  struct node *n = head;
  while (n->next != NULL && strcmp(newNode->firstName, n->next->firstName) < 0) 
          n = n->next;
  newNode->next = n->next;
  n->next = newNode;
  return head; //why head? fluent interface?
}

int main(){
        struct node *head = malloc(sizeof(struct node));
        struct node *n;
        char fname[21];
        char lname[21];

        head->firstName = "My";
        head->lastName = "Head";

        do {
                n = malloc(sizeof(struct node));
                if (scanf("%20s%20s", fname , lname) != 2)
                        break;

                n->firstName = malloc(strlen(fname) + 1);
                strcpy(n->firstName, fname);
                n->lastName = malloc(strlen(lname) + 1);
                strcpy(n->lastName, lname);

                addNode(head, n);

        } while (1);

        printf("\nPrinting...\n\n");
        n = head;
        while (n != NULL) {
                printf("%s %s\n", n->firstName, n->lastName);
                n = n->next;
        }
        return 0;
}

So the only thing you sould change is the comparison operator of the strcmp from less than to greater than.
So I guess you have error somwhere else...

EDIT: Fixed possible mem corruption if you enter 20 chars per name
Edited by metala - 11/22/12 at 6:02pm
Ferberite
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz Lenovo Thinkpad Edge E520 AMD Radeon HD 6630M 6GB DDR3 @ 1333MHz  
Hard DriveHard DriveOSOS
Samsung 850EVO HITACHI HTS727550A9E364 7.2krpm Debian 7.0 Win7 
OSMonitorMonitorKeyboard
Win8 15.6 Zoll 16:9, 1366x768 Pixel, AUO23EC, spiege... 24" Dell U2412M, 1920x1200 Integrated + External 
PowerCase
20V, 4.5A Lenovo Thinkpad Edge 
  hide details  
Reply
Ferberite
(14 items)
 
  
CPUMotherboardGraphicsRAM
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz Lenovo Thinkpad Edge E520 AMD Radeon HD 6630M 6GB DDR3 @ 1333MHz  
Hard DriveHard DriveOSOS
Samsung 850EVO HITACHI HTS727550A9E364 7.2krpm Debian 7.0 Win7 
OSMonitorMonitorKeyboard
Win8 15.6 Zoll 16:9, 1366x768 Pixel, AUO23EC, spiege... 24" Dell U2412M, 1920x1200 Integrated + External 
PowerCase
20V, 4.5A Lenovo Thinkpad Edge 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Application Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Application Programming › Ordered Linked List Add Function - C