Мне было поручено создать программу на 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);
}
}