在鏈接列表中的特定元素之後添加元素並刪除第一個元素

Question

我努力解決這個問題，但只設法部分解決它。

我在這個方法的問題是，我需要另一個元素的後面添加一個元素：

例子：add 5 1

5是鏈表的元素，但我想5後加1 。

實施例：設鏈表包含這些元素：2 3 7

我調用方法來添加1個AFTE r 3，add 3 1，所以結果假定爲2 3 1 7，但用我的方法結果是2 1 3 7，這是我的問題。

第二個問題是，我無法處理的第一個元素：

例子：add 2 1

彷彿第一個元素不存在它的作用：

void addNodeAtPos(link *head, int pos,int addelement) 
{ 
    link prev=NULL; 

    link curr =*head; 

    link newNode = (link)malloc(sizeof(node)); 

    newNode->data = addelement; 


    while(curr->next != NULL) 
    { 

       prev = curr; 
     curr = curr->next; 


     if(curr->data == pos) 
    { 

     newNode->next = curr; 
     prev->next = newNode; 

     break; 
    } 
    } 

    } 

我這裏的問題是我不能刪除第一個元素：

void deletenode(link *head,int s){ 

    bool found = false; 

    node *curr = *head, *prev=NULL; 

    while(curr != NULL){ 

     // match found, delete 
     if(curr->data == s){ 

      found = true; 
      // found at top 

      if(prev == NULL){ 

       link temp = *head; 

       curr->next= prev; 
       delete(temp); 
       // found in list - not top 
      }else{ 
       prev->next = curr->next; 
       delete(curr); 
      } } 
     // not found, advance pointers 
     if(!found){ 
      prev = curr; 
      curr = curr->next; } 
     // found, exit loop 
     else curr = NULL; } 




    } 

Answer 1

這裏是解決第一個問題

if(curr->data == pos) 
{ 
    // tempNode = curr->next; 
    // improvement as suggested by @Rerito 
    newNode->next = curr->next; 
    curr->next = newNode; 
    break; 
} 

Answer 2

您似乎在使用非循環雙向鏈表。因此，列表的兩端都標有NULL。現在，在我看來，你以非常C的方式使用C++ ......（NULL不會在C++中使用，有nullptr關鍵字）。

我會處理您的問題，假設您使用C而不是C++。

// Note that I pass a link **ptr, NOT a link *ptr ... 
void addNodeAtPos(link **head, int pos, int addelement) { 
    // I am assuming head will be a valid pointer, if not, please add the appropriate checks. 
    link *newNode = NULL, *cur = *head; 
    if (NULL == (newNode = malloc(sizeof(link))) 
     return; 
    newNode->data = addelement; 
    while (cur != NULL) { 
     if (cur->data == pos || NULL == cur->next) { 
      newNode->next = cur->next; 
      newNode->prev = cur; // remove this line if there is no prev pointer. 
      cur->next = newNode; 
      if (NULL != newNode->next) { // remove this if clause if there is no prev pointer 
       newNode->next->prev = newNode; 
      } 
      break; 
     } 
     cur = cur->next; 
    } 
} 

沒有指定，如果沒有找到「位置」你應該做的，我認爲你只是在這種情況下，列表的末尾添加的元素。

現在，考慮您的問題移除的第一個元素：

void deleteNode(link **head, int el) 
{ 
    // I assume you wont pass a `NULL` ptr as @head 
    link *cur = *head, *prev = NULL; 
    while (cur != NULL) { 
     if (cur->data == el) { 
      next = cur->next; 
      prev = cur->prev; 
      free(cur); 
      if (NULL != next) 
       next->prev = prev; 
      if (NULL != prev) 
       prev->next = next; 
      else 
       *head = next; 
      break; 
     } 
     cur = cur->next; 
    } 
} 

爲什麼你需要傳遞一個link **head而不是link *head？因爲當你刪除列表的頭部時，你必須確保它不再被訪問，因此你需要更新你在其他地方使用的頭部指針。這是在上述函數的*head = next;聲明中所做的。

如果使用單鏈表（只有一個指針指向下一個元素，而不是以前的），溶液變成如下：

void deleteNode(link **head, int el) 
{ 
    // I assume you wont pass a `NULL` ptr as @head 
    link *cur = *head, *prev = NULL, *next = NULL; 
    while (cur != NULL) { 
     if (cur->data == el) { 
      if (NULL != prev) 
       prev->next = cur->next; 
      else 
       *head = cur->next; 
      free(cur); 
      break; 
     } 
     prev = cur; 
     cur = cur->next; 
    } 
}