在雙向鏈表中添加重複項（字符串）

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

我認爲主要的一點是，你還沒有采取的護理prev點呃，也爲第一，如果，應該有兩種情況，

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

在其他條件做如下修改

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

Answer 2

使用雙向鏈表時，最好先找到需要插入的位置。

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

    } 
    current = current->next; 
} 

一旦你找到了點插入，你有一個四種情形處理時要插入一個項目進入到列表中有。您必須處理頭部/尾部變化以及向內和向外指向或根據需要變爲空。

• 添加到一個完全空列表（頭和尾點的記錄，prev和next爲null）
• 添加到前面（頭得到一個新的價值，新的記錄分組爲null）
• 添加到結束（尾得到一個新的價值，新的紀錄下一個爲空）
• 添加到中間（頭/尾不變）

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長度爲防止寫入超出如果name > 41 chars了您的數組的結束：

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長度和返回NULL - 你現在必須與head提供的聲明一起處理中main()返回：

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）佔條件時，該列表自我的借鑑（即目前只有一個節點是指本身）。

然後你有兩個條件測試（3）是否newNode->name各種當前(*head)->name之前，你必須插入newNode在列表中的新的第一點;最後（4）當前(*head)->name之後newNode->name排序的情況。

即使有一個線性頭/尾列表與你將需要解決兩個（3）&上述（4）。如果您還有其他問題，請告訴我。