0

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;
            }
        }
    }
}
Improve this question
4
  • Can you post struct highScore definition? Commented Mar 22, 2012 at 22:48
  • Is head initialized somewhere, before it is compared to NULL? Also, how is p[i].name populated? Commented Mar 22, 2012 at 22:52
  • This question doesn't have enough information to be answered without guesswork. Try composing a small, complete, compilable program demonstrating your problem. Then it will be easier for others to help. Commented Mar 22, 2012 at 23:30
  • @karoma SO handles spaces badly, please use 4 space for indentation next time (it's in FAQ). Commented Mar 23, 2012 at 16:46

3 Answers 3

Reset to default
1

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Also, you need to decide what to do if the new entry goes in "the same place" as some old entry. The loop above puts it in front, on the theory that "same score, but more recently achieved, means bump the old one down". But maybe you'll want something different.
0

  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)
    {
       ...
Improve this answer

1 Comment

I generally agree with your points, but I don't see how is it relevant. Also you use too small indentation and while we'r betching about practise, 8(4) char indentation, no more than 3(4) levels in loops(worst case in ()). :-* 4) step can be avoided by writing programs without errors (my teacher would say, ik its BS :D).
0

  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?

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.