在 C 中按字母顺序插入链表中

Question

任何人都可以提供一个简短的示例，说明如何使用 strcmp（） 函数根据指针结构中的第一项按字母顺序将新节点插入链表中。不是真的在寻找答案，而只是用一个模棱两可的例子来解释，无法真正找到一个直接的答案，所以我希望有人可以帮助我。提前谢谢。

Answer 1

你去吧（这个使用指向函数的指针）

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct llist {
    char *value;
    struct llist *next;
};
int compare (struct llist *one , struct llist *two)
{
return strcmp(one->value, two->value);
}
void add(struct llist **pp, char *value, int (*cmp)(struct llist *l, struct llist *r)) {
    struct llist *new;
    new = malloc(sizeof(*new));
    new->value = value;
    for ( ; *pp != NULL; pp = &(*pp)->next) {
        if (cmp(*pp, new) > 0 ) break;
        }
    new->next = *pp;
    *pp = new;
}
void display(struct llist *ptr) {
    for (; ptr != NULL; ptr = ptr->next) {
        printf("%sn", ptr->value);
    }
}
int main(void) {
    struct llist *root = NULL;
    add(&root, "item1", compare);
    add(&root, "item2", compare);
    add(&root, "item4", compare);
    add(&root, "item3", compare);
    display(root);
    return 0;
}

Answer 2

假设您的链表节点如下所示：

typedef struct node {
    char* str;
    struct node* next;
} NODE;

如果要将新节点插入按字母顺序排序的链表中，则需要考虑四种情况：

1. 列表为空，因此要插入的节点是第一个/唯一的节点
2. 要插入的节点按字母顺序位于列表中第一个节点之前
3. 节点将插入中间
4. 节点将插入到列表的末尾。

但是，假设：

1. 空列表正确设置为 NULL ，并且
2. 要插入的节点的next已正确设置为 NULL

您可以通过组合前两种情况和后两种情况来处理插入，以便您只有一个逻辑选择：将新节点作为第一个节点或列表中的某个其他节点插入。

这是一个解决这两种情况的简单算法。

algorithm insert
receives: list, pointer to linked list
    toInsert, pointer to new node for insertion
returns: pointer to updated list with new node inserted. 
1. if (list is null OR toInsert->value is less than list->value)  
    1.1 set toInsert->next to list
    1.2 set list to toInsert
2. else
    2.1 set pPre to list
    2.2 set pWalk to list->next
    2.3 loop while (pWalk is not null AND toInsert->value is greater than pPre->value)
        2.3.1 set pPre to pWalk;
        2.3.2 set pWalk to pWalk->next;
    2.4 set pPre->next to toInsert;    
    2.5 set toInsert->next to pWalk;
3. return

要实现这一点，您必须在if和while条件下使用 strcmp()。

请记住，strcmp()按 ASCII 顺序比较字符串，而不是"按字母顺序"。 就strcmp()而言，'B'是在'A'之后，但在'a'之前。如果您需要不区分大小写的严格字母排序，则必须编写自己的忽略大小写的strcmp()版本，并在insert()中使用函数指针。

Answer 3

如果链表已经按字母顺序排序，则必须迭代到应该在新节点之后的第一个节点，并在它之前插入新节点。您需要记住迭代中当前节点之前的节点，因为最后一个节点的next指针现在应该指向新节点。您可能需要唯一地处理某些情况，例如列表的大小为零或在边框处插入。

请注意按字母顺序排序和按 ASCII 排序之间的区别。这是不同的。（按字母顺序：11> 9，ASCII：11 <9）