C: Creating a Queue in Ascending Order

Question

I'm working on a problem where the objective is to create a linked list (a queue) in ascending order regardless of what order it's entered. I've been able to construct my assignment so that it enters data and pushes it onto a stack and correctly pops the first item from the queue (this is the code below) but I cannot seem to get a working algorithm to construct the queue in ascending order.

I reworked my algorithm by using a second function within my addItem to find the correct location of any newly added structure so it now properly handles sorting. My reworked code is below.

void addItemToQueue(int *identification, float *houlyrate) {
    struct Employee *locateInsertionPoint(int *);
    struct Employee *newAddress, *here;

    newAddress = (struct Employee *) malloc(sizeof(struct Employee));   // Allocate Space for the new structure
    if (newAddress == (struct Employee *) NULL) {                       // Display Error message and terminate if allocation fails
        printf("\nERROR: Failed to allocate memory for this structure.\n");
        free(queueOut);                                                 // Free the Queue in the event memory fails to allocate new space
        exit(1);
    }

    if (queueOut == NULL) {                                             // Does queue exist
        newAddress->nextAddress = NULL;
        queueOut = newAddress;
    }
    else if (*identification < queueOut->idnum) {                       // Is the new ID Number less than the old ID Number
        newAddress->nextAddress = queueOut;
        queueOut = newAddress;
    }
    else {
        here = locateInsertionPoint(identification);                    // Use locateInsertionPoint() function to find proper place for new ID
        newAddress->nextAddress = here->nextAddress;
        here->nextAddress = newAddress;
    }
    newAddress->idnum = *identification;                                // Make new structure id num equal to the passed id num
    newAddress->hourlyrate = *houlyrate;                                // Make new structure payrate equal to the passed payrate
}


struct Employee *locateInsertionPoint (int *idnum) {
    struct Employee *one, *two;
    one = queueOut;
    two = one->nextAddress;
    if (two == NULL) {                                                  // Check if There is only 1 item
        return one;
    }
    while (1) {                                                         // LOOP
        if (*idnum < two->idnum) {                                      // Is the new ID less than current ID
            break;
        }
        else if (two->nextAddress == NULL) {                            // IF Not, is the next address NULL
            one = two;
            break;
        }
        else {                                                          // IF Not, shift pointers to read next set
            one = two;
            two = one->nextAddress;
        }
    }
    return one;
}

Answer 1

It looks as though you are trying to implement insertion sort to keep your queue sorted. If that is the case then you have a few issues in your implementation. You aren't maintaining your list properly. When you find the point where you want to insert your item into the list, you need to update the next pointer of the previous element to point to your new element in addition to setting your new element to point to the current element.

I recommend you have a look at some linked list examples, such as how to insert into a linked list. Linked lists are an integral basic data structure and it's worth the time to develop a thorough understanding.