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 предыдущего элемента, чтобы указать на ваш новый элемент, а также на то, чтобы ваш новый элемент указывал на текущий элемент.

Я рекомендую вам ознакомиться с некоторыми примерами связанных списков, например, как вставить в связанный список. Связанные списки являются неотъемлемой базой данных, и стоит потратить время на глубокое понимание.