在双向链表中添加重复项（字符串）

Question

目前正在研究双链表的实现。听起来可能很奇怪，我想要重复项添加到我的链接列表中。我正在按排序顺序将 newNode 添加到列表中。

以下函数不添加重复节点。

struct Node
{
    char name[42];
    struct Node *next;
    struct Node *prev;
};

void addSorted(struct Node **head, struct Node *newNode)
{
    struct Node* current;
    // Special case for the head end
    if ((*head == NULL) || strcmp((*head)->name, newNode->name) >= 0)
    {
        newNode->next = *head;
        *head = newNode;
    }
    else
    {
        // Locate the Node before the point of insertion
        current = *head;
        while (current->next != NULL &&
                strcmp(current->next->name, newNode->name) <= 0)
        {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

struct Node* GetNewNode(char *name)
{
    struct Node* newNode = malloc(sizeof (struct Node));

    strcpy(newNode->name, name);
    newNode->prev = NULL;
    newNode->next = NULL;

    return newNode;
}

int main(void)
{
    // Some Irrelevant Code
    if (strncmp(operator, "a", 1) == 0)
    {
        temp = GetNewNode(name);

        addSorted(&head, temp);
    }
 }

Answer 1

使用双向链表，最好先找到需要插入的地方

// pseudo code
current = head;
while (current) 
{
    if ( strcmp( name, current -> name) ... )  // your logic for your sort order
    {

    }
    current = current->next;
}

找到要插入的位置后，当您想将项目插入列表时，您有四种情况需要处理。您必须根据需要处理 head/tail 更改以及向内和向外指向或指向 null。

添加到一个完全空的列表中（head和tail指向记录，prev和next为null）
添加到最前面（head得到一个新值，新记录prev为null，）
加到最后（tail得到一个新值，新记录next为null）
加到中间（head/tail不变）

Answer 2

我认为主要是你没有处理好prev指针，还有第一个if，应该有两种情况，

if(*head==NULL)
{
 *head=newNode;
}
else if(strcmp((*head)->name, newNode->name) >= 0)
{
 (*head)->prev=newNode;//ADD THIS LINE
 newNode->next = *head;
 *head = newNode;
}

在else条件下做如下修改

newNode->next = current->next;
current->next->prev = newNode;//CHANGE HERE
current->next=newNode;//ADD THIS LINE
newNode->prev=current;//ADD THIS LINE

Answer 3

除了已经讨论过的prev指针管理器之外，还有一些额外的地方是您自讨苦吃。首先，使用 define 设置静态 name 数组的大小是明智的（这将成为验证 name 大小的必要条件）：

#define MAXN

struct Node
{
    char name[MAXN];    /* use a define for static allocation size */
    struct Node *next;
    struct Node *prev;
};

这导致了 GetNewNode 中的两个问题。首先你需要验证你的内存分配：

    struct Node* newNode = malloc(sizeof (struct Node));

    if (!newNode) { /* validate all memory allocations */
        fprintf (stderr, "%s() memory allocation failed.\n", __func__);
        exit (EXIT_FAILURE);
    }

然后，如果 name > 41 chars:

，您还必须验证 name 的长度，以防止超出数组末尾的写入

    size_t namelen = strlen (name);

    if ( namelen > MAXN - 1) { /* validate string length */
        fprintf (stderr, "%s() name length (%zu) exceeds %d .\n", 
                 __func__, namelen, MAXN);
        return NULL;
    }

注意：通过使用define设置name的长度，定义MAXL作为您的长度验证测试。

接下来，在 GetNewNode 中验证 name 的长度并 returned NULL -- 你现在必须处理 return 中的 main() 以及为 head:

提供的声明

int main (void)
{
    struct Node *head = NULL;               /* head must be declared */

    if (strncmp(operator, "a", 1) == 0)
    {
        temp = GetNewNode(name);

        if (temp)                           /* validate return  */
            addSorted(&head, temp);
    }
}

如果您的意图是创建一个 循环列表 ，那么您有几个额外的条件必须在 addSorted 中测试并做出适当的响应。具体来说，您必须 (1) 在 *head = NULL 时创建列表。

如果您之前的陈述 newNode->next = *head; *head = newNode; 是正确的，则您必须 (2) 说明列表是 self-referencial 的情况（即只有一个节点指代自身的现在时）。

然后您还有两个条件要测试 (3) newNode->name 是否排在当前 (*head)->name 之前，您必须在其中插入 newNode 作为 新的第一个节点 在列表中；最后 (4) newNode->name 在当前 (*head)->name.

之后排序的情况

即使使用 线性 head/tail 列表，您也需要解决上面的 (3) & (4) .如果您还有其他问题，请告诉我。

在双向链表中添加重复项（字符串）

Add duplicate items(string) in doubly linked list

c

doubly-linked-list