C:按升序创建队列

Question

我正在解决一个问题，其目标是按升序创建一个链接列表(队列)，无论输入的顺序如何。我已经能够构造我的作业，以便它输入数据并将其插入堆栈并正确地从队列中弹出第一个项目(这是下面的代码)，但我似乎无法获得一个工作算法来构造队列升序。

我通过使用 addItem 中的第二个函数来重新设计我的算法，以找到任何新添加的结构的正确位置，以便它现在可以正确处理排序。我重新设计的代码如下。

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

看起来您正在尝试实现插入排序来保持队列排序。如果是这种情况，那么您在实现中会遇到一些问题。您没有正确维护您的列表。当您找到要将项目插入到列表中的点时，除了将新元素设置为指向之外，还需要更新前一个元素的 next 指针以指向新元素当前元素。

我建议您看一些链表示例，例如如何插入链表。链表是一个完整的基本数据结构，值得花时间进行彻底的理解。