Функция вставки для связанного списка в порядке убывания вставки - разрешен только головной узел

Question

Мне было поручено создать программу на C, которая вставляет пользовательский ввод в просто связанный список, но со следующими ограничениями:

• Узлы должны быть отсортированы в порядке убывания;
• Разрешено использовать только монитор головного узла (хвостовой узел для мониторинга не разрешен).

Это текущий код для моей функции вставки:

void insert(struct snode *node, struct snode *aux) {
    if (aux) {
        if (node->n >= monitor.head->n) {
            node->next = monitor.head;
            monitor.head = node;
            return;
        }
        if (node->n < aux->n) {
            node->next = aux->next;
            aux->next = node;
            return;
        } else
            insert(node, aux->next);
    }
}

Проблема, в которой я застрял, заключается в следующем: если я введу, например, 5, затем 9, затем 1, список будет отсортирован как 9 -> 1 -> * 1017. * -> NULL, должно быть 9 -> 5 -> 1 -> NULL. Что мне здесь не хватает? Потому что я перепробовал все, что мог придумать.

Вот полная программа на случай, если она поможет:

#include <stdio.h>
#include <stdlib.h>

/* GLOBAL VARS */
struct snode {
    int n;
    struct snode *next;
};
struct smonitor {
    struct snode *head;
} monitor;

/* FUNCTION PROTOTYPING */
void insert(struct snode *node, struct snode *aux);
void search(int s, struct snode *aux);
struct snode *aloc(int p);
void print(struct snode *aux);
void readInputFile();

/* MAIN LOOP */
int main() {
    int p, s;
    int opt;
    _Bool endMain = 1;
    while (endMain == 1) {
        struct snode *aux = monitor.head;
        printf("Define Option:\n0-Exit\n1-Insert\n2-Search\n3-Print\n");
        scanf("%d", &opt);
        switch (opt) {
          case 0:
            endMain = 0;
            break;
          case 1:
            printf("Define node:\n");
            scanf("%d", &p);
            struct snode *node = aloc(p);
            if (monitor.head == NULL)
                monitor.head = node;
            else
                insert(node, aux);
            break;
          case 2:
            printf("Define search term:\n");
            scanf("%d", &s);
            search(s, aux);
            break;
          case 3:
            printf("List is:\n");
            print(aux);
            printf("[NULL]\n");
            break;
          case 4:
            readInputFile();
            break;
          default:
            printf("INVALID OPTION\n");
        }
    }
    return 0;
}

/* FUNCTIONS */
void insert(struct snode *node, struct snode *aux) {
    if (aux) {
        if (node->n >= monitor.head->n) {
            node->next = monitor.head;
            monitor.head = node;
            return;
        }
        if (node->n < aux->n) {
            node->next = aux->next;
            aux->next = node;
            return;
        } else
            insert(node, aux->next);
    }
}

void search(int s, struct snode *aux) {
    if (aux) {
        if (s == aux->n)
            printf("HIT - Node %d found\n", aux->n);
        else
            search(s, aux->next);
    } else
        printf("NO HIT - Node not found\n");
}

struct snode *aloc(int p) {
    struct snode *node;
    node = (struct snode *)malloc(sizeof(struct snode));
    node->n = p;
    node->next = NULL;
    return node;
}

void print(struct snode *aux) {
    if (aux) {
        printf("[%d]-", aux->n);
        print(aux->next);
    }
}

void readInputFile() {
     FILE *fp;
     int input;
     struct snode *p;
     struct snode *aux;

     fp = fopen("/home/user/inputFile.txt", "r");
     printf("Nodes added:\n");
     while (fscanf(fp, "%d", &input) != EOF) {
         p = aloc(input);
         aux = monitor.head;
         if (monitor.head == NULL)
             monitor.head = p;
         else
             insert(p, aux);
         printf("[%d]-", input);
    }
    printf("\n");
    fclose(fp);
}

Заранее спасибо за любую помощь, которую вы, ребята, можете оказать! : D

/ ------------------------------- EDIT ----------- ------------------------- / После отзывов вашего парня и некоторых тестов мне удалось найти решение, возможно, не лучшее его воплощение, и есть другие ответы с разными реализациями (которые очень ценятся! :)), но вот новая версия этой вставки Функция, еще раз спасибо всем за советы! : D

void insert (struct snode *node, struct snode *aux, struct snode *pre){
    if(aux){
        if(node->n >= monitor.head->n){
            node->next = monitor.head;
            monitor.head = node;
            return;
        }
        if((pre->n >= node->n) & (node->n >= aux->n)){
            pre->next = node;
            node->next = aux;
            return;
        }
        if((pre->n >= node->n) & (aux->next == NULL)){
            aux->next = node;
            return;
        }
        insert(node, aux->next, aux);
    }
}

Answer 1

Ваш тест неверен в insert. Помимо этого fis, вы не должны использовать глобальную переменную monitor, и позволить insert и другим функциям изменять ее - это сбивает с толку и отрицает цель передачи списка в качестве аргумента.

Вот модифицированная версия:

#include <stdio.h>
#include <stdlib.h>

/* STRUCTURES */
struct snode {
    int n;
    struct snode *next;
};
struct smonitor {
    struct snode *head;
};

/* FUNCTION PROTOTYPES */
void insert(struct snode *node, struct smonitor *mon);
void search(int s, struct smonitor *mon);
struct snode *aloc(int p);
void print(struct smonitor *mon);
void readInputFile(struct smonitor *mon);
int flush(void);

/* MAIN LOOP */
int main() {
    int p, s;
    int opt;
    struct smonitor monitor = { NULL };
    _Bool endMain = 0;

    while (!endMain) {
        printf("Define Option:\n0-Exit\n1-Insert\n2-Search\n3-Print\n");
        if (scanf("%d", &opt) != 1)
            break;
        switch (opt) {
          case 0:
            endMain = 1;
            break;
          case 1:
            printf("Define node:\n");
            if (scanf("%d", &p) != 1) {
                flush();
                break;
            }
            struct snode *node = aloc(p);
            if (node == NULL) {
                fprintf(stderr, "allocation failure\n");
                break;
            }
            insert(node, &monitor);
            break;
          case 2:
            printf("Define search term:\n");
            if (scanf("%d", &s) != 1) {
                flush();
                break;
            }
            search(s, &monitor);
            break;
          case 3:
            printf("List is:\n");
            print(&monitor);
            break;
          case 4:
            readInputFile(&monitor);
            break;
          default:
            printf("INVALID OPTION\n");
            break;
        }
    }
    return 0;
}

/* FUNCTIONS */

int flush(void) {
    int c;
    while ((c = getchar()) != EOF && c != '\n')
        continue;
    return c;
}

void insert(struct snode *node, struct smonitor *mon) {
    struct node *aux;
    if (mon->head == NULL || node->n > mon->head->n) {
        node->next = mon->head;
        mon->head = node;
        return;
    }
    aux = mon->node
    while (aux->next && node->n <= aux->next->n) {
        aux = aux->next;
    }
    node->next = aux->next;
    aux->next = node;
}

void search(int s, struct smonitor *mon) {
    struct snode *aux = mon->head;
    while (aux) {
        if (s == aux->n) {
            printf("HIT - Node %d found\n", aux->n);
            return;
        }
        aux = aux->next;
    }
    printf("NO HIT - Node not found\n");
}

struct snode *aloc(int p) {
    struct snode *node;
    node = (struct snode *)malloc(sizeof(struct snode));
    if (n != NULL) {
        node->n = p;
        node->next = NULL;
    }
    return node;
}

void print(struct smonitor *mon) {
    struct snode *aux = mon->head;
    while (aux) {
        printf("[%d]-", aux->n);
        aux = aux->next;
    }
    printf("[NULL]\n");
}

void readInputFile(struct smonitor *mon) {
     FILE *fp;
     int input;

     fp = fopen("/home/user/inputFile.txt", "r");
     if (fp == NULL) {
         fprintf(stderr, "cannot open file /home/user/inputFile.txt\n");
         return;
     }
     printf("Nodes added:\n");
     while (fscanf(fp, "%d", &input) == 1) {
         struct snode *p = aloc(input);
         if (p == NULL) {
             fprintf(stderr, "\nallocation failure\n");
             break;
         }
         insert(p, mon);
         printf("[%d]-", input);
    }
    printf("\n");
    fclose(fp);
}

Answer 2

логика вставки, единственная гарантия, что логика верна, а не оптимальная реализация. Если ссылка длинная, она не будет работать с рекурсией.

1. Если aux является головкой, а узел больше, чем aux, узел вставляется в головка
2. Если aux-> next равно нулю, узел вставляется в конец
3. Если узел больше, чем aux-> next, узел должен быть вставлен между aux и aux-> следующий
4. В противном случае положить aux назад

Измените функцию вставки на

void insert(struct snode *node, struct snode *aux)
{
    if (aux) {
        if(aux == monitor.head && node->n >= aux->n) {
            node->next = monitor.head;
            monitor.head = node;
        } else if (!aux->next) {
            aux->next = node;
        } else if(node->n >= aux->next->n) {
            node->next = aux->next;
            aux->next = node;
        } else {
            insert(node, aux->next);
        }
    }
}

Answer 3

Проблема возникает из-за этой части insert() кода:

        if(node->n < aux->n){      // <=========
                node->next = aux->next;
                aux->next = node;
            ....
            ....

Последовательность вставки 5, 9 и 1. Когда вы вставляете 1, тогда связанный список будет

-------      -------
|  9  |----->|  5  |
-------      -------

значение node->n равно 1, а значение aux->n равно 9. Таким образом, сравнение условия if оценивается как true:

if(node->n < aux->n){

и узел со значением 1, вставленный сразу после узла 9, и вы получаете последовательность 9, 1 и 5.