CODEWITHSUNDEEP
clinked-list
karoma
karoma

Reputation: 1558

Adding to a sorted linked list

I'm trying to get my program to insert a score into a place within an ordered linked list. It compiles fine but crashes when I launch it. Linked lists aren't exactly my speciality so I'm sure I've made an error somewhere. p[i].score and p[i].name are defined just before this piece of code and the list is initially empty.

struct highScore
{
    char name[10];
    int score;
    struct highScore *next;
};
struct highScore *head,*currentScore,*newScore, *temp;

if(head==NULL)
{
    head = currentScore = newScore;
    currentScore->score = p[i].score;
    strcpy(currentScore->name, p[i].name);
}
else
{
    currentScore = head;      

    while (currentScore->next != NULL)
    {
        while(p[i].score < currentScore->score)
        {
            currentScore = currentScore->next;
            if (currentScore->next->score < p[i].score)
            {
                newScore = (struct highScore *)malloc(sizeof(struct highScore));

                newScore->score = p[i].score;
                strcpy(newScore->name, p[i].name);

                temp = currentScore->next;
                currentScore->next = newScore;
                currentScore = newScore;
                currentScore->next = temp;
            }
        }
    }
}

Upvotes: 0

Views: 820

Answers (3)

torek
torek

Reputation: 488213

Your current code is kind of a mess (as others noted).

What you need, in pseudocode, is something like this:

new_entry = create_new_entry(data); /* allocate the new stuff */
for (some loop to find where new_entry is to insert)
    ... loop contents ...
insert new_entry;

The tricky part with singly-linked lists is that you can only do an "insert before" operation, which looks like:

new_entry->next = what_new_goes_before;
what_new_goes_after->next = new_entry;

and this requires that there be "something that new_entry goes after". This is where the special case test for:

if (head == NULL)

comes from: if head is NULL, there's no existing entry you could go after. Unfortunately, there's also the case where the new entry goes first, so you need to test for both of these:

if (head == NULL || goes_before(new_entry, head)) {
    /* i.e., there is no head yet, or new_entry goes before head */
    new_entry->next = head;
    head = new_entry;
} else {
    /* there is something for new_entry to go after, so find it */
    for (old_entry = head; !goes_before(new_entry, old_entry);)
        prev = old_entry;
        if ((old_entry = old_entry->next) == NULL)
            break;
    new_entry->next = old_entry;
    prev->next = new_entry;
}

However, there's a very useful trick with pointers-to-pointers in C here. Instead of writing a loop that has to run at least once (to set prev above—note that we know the result of !goes_before() on the first trip), we can have a pointer variable pp that will point to some struct highScore * pointer:

struct highScore **pp, *p;

Initially, we'll have this point to head. As we run through the loop trying to find the item that the new entry goes-before, we'll change it to point to each old-entry's struct highScore * pointer called next:

for (pp = &head; !goes_before(new_entry, p = *pp); pp = &p->next)
    continue;

The loop terminates when new_entry goes before *pp (whose value is now in p), so now we need only set the new entry's next and update *pp:

new_entry->next = p;
*pp = new_entry;

and the whole thing is done in four lines (plus the 5th declaration line).

Upvotes: 1

Ed Heal
Ed Heal

Reputation: 60007

  1. The line

    head = currentScore = newScore;

    You have not initialized newScore - hence the rest of that if statement is doomed.

  2. Are you adding items in order, or is the list supposed to end up in order?

Upvotes: 0

paulsm4
paulsm4

Reputation: 121669

  1. Break your code out into functions. For example, "initialize()", "insert()", "find()" and "delete()" might all be useful functions.

  2. Don't use global variables. For example, "*head" and "*currentScore" are probably the only variables you'd even consider making global.

  3. Write test programs for every function.

  4. Single-step through every test program under the debugger.

IMHO .. PSM

PS: For example:

struct *highScore
insert (struct ** head, struct *highScore newScore)
{
  struct *hiScore currentScore;

  // Assumes "newScore" element is already filled in
  if(*head==NULL)
  {
    *head = newScore;
    newScore->next = NULL;
    return newScore;
  }
  else
  {
    currentScore = *head;      
    while (currentScore->next != NULL)
    {
       ...

Upvotes: 0

Related Questions