将节点插入C中的分类链接列表

Question

我需要将节点插入到排序的链接列表中。该列表具有一个虚拟节点。

void add(Node **nodeArray, int setNumber) {
    char userString[5];
    Node *head = nodeArray[setNumber];      /* head pointer to first element of array (dummy) */
    Node *newNode = malloc(sizeof(Node));   /* new node to be added to array */
    Node *tmp = head;
    printf("Please enter some data: ");
    scanf("%s", userString);
    strncpy(newNode->data, userString, DATA_SIZE);  /* copies string entered by the user to data field of new node */
    newNode->next = NULL;   /* initializes next field of new node to NULL */

    while (tmp->next) 
        tmp = tmp->next;        /* points head to next element in list */
    tmp->next = newNode;    /* adds element to list */
}

这将列表末尾的节点插入。我了解附加形式的逻辑。您可以向前看下一个节点，如果新节点小于下一个节点，则将新节点指向下一个节点，然后将上一个节点指向新节点。有人可以帮助我在代码中实现这一点。这是我到目前为止所拥有的，但不起作用。

if (!tmp->next)
    tmp->next = newNode;
else {
    while (tmp->next) {
        if (strcmpa((tmp->next)->data, newNode->data) < 0) {
            newNode->next = tmp->next;
            tmp->next = newNode;
        } //else if (strcmpa((tmp->next)->data, newNode->data) > 0) {
            //tmp->next = newNode;
        //}
        tmp = tmp->next;
    }
}

这是比较函数：

int strcmpa(char *s1, char *s2) {
   while (*s1 && tolower(*s1) == tolower(*s2))
   {
      s1++;
      s2++;
   }
   return tolower(*s1) - tolower(*s2);
}

Answer 1

您快到了，但是tmp->next应重定向到newNode本身，而不是newNode->next。实际上，这是一个不使用的，因为在该命令时，newNode->next是tmp->next，您正在重新分配一个已经存在的值。

您想要的是tmp指向X，指向next，然后指向X。因此，正式，

X = tmp->next;
tmp->next = newNode;
newNode->next = X;

可以凝结为

newNode->next = tmp->next; /* using the X where originally stored */
tmp->next = newNode; /* rewriting that memory has to wait till now */

---

更新： tmp之后的上述代码链接newNode（我认为这是您需要的）。但是在排序列表中，您会发现第一个tmp需要在节点后出现，因此您需要在此之前进行。这带来了两个问题：

1. 您需要在 tmp点之前修改项目，因为新节点会去那里，因此您需要保留一个更多变量，

2. 有时您需要将新节点放在没有以前的节点的一开始。

在加号方面，上面还优雅地处理!tmp->next（最后插入），因此您实际上不需要其他分支。

它看起来像

Node* head = (whatever);
Node* prev = NULL;
Node* tmp;
for(tmp = head; tmp && strcmpa(tmp->data, newNode->data) < 0; tmp = tmp->next) {
    prev = tmp;
}
/* now tmp points to the first larger node or to NULL and prev is its preceding node.
 * If there's none (if the head is already larger) then prev = NULL. */
if(prev == NULL) {
    newNode->next = head;
    head = newNode; /* Don't forget to update this in the array where you took head from! */
} else {
    newNode->next = prev->next;
    prev->next = newNode;
}

如果head是NULL，并且使用单个条目创建链接列表。

---

这集中在插入上。关于您的其余代码（最初以注释发布）：

• 如果您在无限制的%s scanf上覆盖userString缓冲区，则该程序将失败。设置限制。

• 有限，您不需要不安全的strncpy。使用普通的strcpy保证它将无效您的字符串。

• 您的strcmpa看起来不错。但是，请确保tolower()使用''的输入来完成您期望的。这正确比较字符串：

  char toLower(char in) { 
    if(in >= 'A' && in <= 'Z')
      return in + 'a' - 'A';
    else
      return in;
  }