按插入降序插入链表的函数 - 只允许头节点

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 -> 5 -> 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

/----------------------------编辑-------- ----------------------------/ 在你们的反馈和一些测试之后，我设法找到了一个解决方案，可能不是它的最佳实现，还有其他不同实现的答案（非常感谢！:)），但这是该插入的新版本函数，再次感谢大家的指点！ :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() 代码的这一部分造成的：

        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.

Answer 2

您的测试在 insert 中不正确。除此之外，你不应该使用全局变量 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 3

插入逻辑，只保证逻辑正确，不保证最优实现。如果 link 很长，递归将不起作用。

如果aux为head且node大于aux，node插入到头
如果aux->next为空，节点插入到最后
如果node大于aux->next，node应该插入到辅助和辅助->下一个
否则将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);
        }
    }
}

按插入降序插入链表的函数 - 只允许头节点

Insert function for linked list in descending order of insertion - only head node permited

c

linked-list

singly-linked-list