0

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

4

3 回答 3

3

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

#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("%s\n", 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;
}
于 2013-09-12T22:15:34.737 回答
1

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

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

要实现这一点，您必须同时使用strcmp()theif和while条件。

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

于 2013-09-12T23:57:49.327 回答
0

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

请注意按字母排序和按 ascii 排序之间的区别。这不一样。（字母：11 > 9，ascii：11 < 9）

于 2013-09-12T20:59:59.153 回答