在第i個位置添加節點

我想創建一個大小爲5的鏈接列表並在第i個位置添加一些節點。在第i個位置添加節點

我將在鏈接列表的隨機位置say（0,5和2）添加節點。

這是它看起來像在位置0

 0 
+---------+ 
| 1 | 
+---------+ --> NULL 
| next | 
+---------+

這是它看起來像在位置5

 0    1    2    3    4 
+---------+ +---------+ +---------+ +---------+ +---------+ 
| 1 | | Empty | | Empty | | Empty | | 2 | 
+---------+-------------------------------------------->+---------+-->NULL 
| next | | node | | node | | node | | next | 
+---------+ +---------+ +---------+ +---------+ +---------+

所以節點1,2將所述節點將所述節點， 3是空的並且0鏈接到4.

這就是它在位置1添加節點的樣子。

 0    1    2    3    4 
+---------+ +---------+ +---------+ +---------+ +---------+ 
| 1 | | 2 | | Empty | | Empty | | 2 | 
+---------+-->+---------+------------------------------>+---------+-->NULL 
| next | | next | | node | | node | | next | 
+---------+ +---------+ +---------+ +---------+ +---------+

所以節點2,3是空的，0是與1和1連接到4

我試圖實現它，但它沒有任何打印。請指教。謝謝。

#include <iostream> 

struct node 
{ 
    int x; 
    node *next; 
}; 

node * head = NULL; 
node * newNode; 
node * temp; 

void addNode(int pos, int size) 
{ 
    /*if head is null, initialize a new node 
     set data = 1 for head; 
    */ 
    if(head == NULL && pos == 0) 
    { 
     newNode = new node; 
     head = newNode; 
     head->x = 1; 
     temp = head; 
     temp->next=NULL; 
    } 
    else 
    { 
     /* 
     Adding a node at ith position. 
     1. check if the the position is less than the size of the link list. 
     2. set the temp position to be 0(head) 
     3. use the temp pointer and go to the ith postion. 
     4. create new node at ith position. 
     5. set data = 2 for the node at ith position. 
    */ 
     if (pos < size) 
     { 
      for(int i=0; i < size; i++) 
      { 
       temp = head; 
       temp = temp->next; 

       if (pos == i) 
       { 
        newNode = new node; 
        temp = newNode; 
        temp->x = 2; 
        temp->next = NULL; 
       } 
      } 
     } 
    } 
} 

void Print() { 
    while(head->next != NULL) 
    { 
     std::cout<< head->x << std::endl; 
     head=head->next; 
    } 
} 

int main() 
{ 
    int input = 0; 
    while (true) { 
     std::cout << "1. Add Node and Print " << std::endl; 

     std::cin >> input; 
     switch (input) { 
      case 1: 
       addNode(0, 5); 
       addNode(5, 5); 
       addNode(1, 5); 
       Print(); 
       break; 
      default: 
       std::cout<<"Bad Input"; 
       break; 
     } 
     std::cin.get(); 
    } 
    return 0; 
}

來源

2015-05-09 user3429531

so what'Empty'; atm當你嘗試添加新的節點時，迭代器（'temp'）將會爲空，然後嘗試解引用它。 – amdixon

所以我可以在第i個位置添加節點嗎？如果我在位置0處添加一個新節點，然後在位置5處添加一個新節點，那麼對於我來說，2-4節點的位置將是「空的」。我就是這麼看的。或者我錯了？ – user3429531

你必須爲'Empty'定義一些符號值，然後沿着它們創建新的節點（它們爲空）。大多數人將鏈接列表視爲僅添加到尾部函數而不是位置 - 是否需要設置職位？ – amdixon

正如我已瞭解你的問題，你想編寫函數，將在指定的指數，如果指數比列表會自動擴展您的列表的當前大小設置節點的值。（糾正我，如果我錯了）

這很容易。您需要遍歷列表，而計數器i（請參見下面的代碼）小於指定的位置。如果列表小於您創建節點並將其值標記爲某個特定值EMPTY。當計數器等於位置時，則將節點的值設置爲value。

#include <iostream> 

struct node { 
    int data; 
    node* next; 
}; 

#define EMPTY -1 

node * head = NULL; 

void setNode(int pos, int value) { 
    if(head == NULL) { 
     head = new node; 
     head->data = EMPTY; 
     head->next = NULL; 
    } 
    node* p = head; 
    for(int i = 0; i < pos; i++) { 
     if(p->next == NULL) { 
      p->next = new node; 
      p->next->data = EMPTY; 
      p->next->next = NULL; 
     } 
     p = p->next; 
    } 
    p->data = value; 
} 

void print() { 
    node* p = head; 
    while(p != NULL) { 
     std::cout << p->data << " "; 
     p = p->next; 
    } 
    std::cout << std::endl; 
} 

int main() { 
    setNode(0, 1); 
    setNode(5, 2); 
    setNode(1, 3); 
    print(); 
    return 0; 
}

而且在你的代碼有打印功能的錯誤：

你改變了head變量。
由於while循環中的條件，列表的最後一個值未打印。

來源

2015-05-09 17:08:35 NikolayKondratyev

在第i個位置添加節點

回答

相關問題