鏈表插入/缺失

Question

    // ConsoleApplication1.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 
#include <iostream> 
using namespace std; 

struct Node { 
    int data; 
    Node* next; 
}; 
Node* head = NULL; 
int size; 
Node* tail = NULL; 

void printLinkedList() { 
    Node *search = head; 
    if (head == NULL) { 
     cout << "linkedlist is empty" << endl; 
    } 
    else { 
     while (search != NULL){ 
      cout << search->data << endl; 
      search = search->next; 
     } 
    } 
} 
int sizeLinkedList() { 
    size = 1; 
    Node* current = head; 
    while (current->next != NULL) { 
     current = current->next; 
     size = size + 1; 
     } 
    cout << size << endl; 
    return size; 
} 

Node *getNode(int position){ 
    Node *current = head; 
    for (int i = 0; i<position; i++) 
    { 
     current = current->next; 
    } 

    return current; 
} 
void appendNode(int n) { 
    Node *newNode = new Node; //creating new node 
    newNode->data = n; 
    newNode->next = NULL; 
    if (head == NULL) 
    { 
     head = newNode; 
     return; 
    } 
    else { 
     Node *current = head; 
     while (current->next != NULL) { 
      current = current->next; 
     } 
     current->next = newNode; 

    } 
    } 

void insertNode(int n, int position) { 
    Node *newNode = new Node; 
    newNode->data = n; 
    newNode->next = NULL; 
    int size = sizeLinkedList(); 
    if (position = 0){ 
     if (head == NULL) { 
      head = newNode; 
     } 
     else{ 
      newNode->next = head; 
      head = newNode; 
     } 
    } 

    else if (position == size) { 
     appendNode(n); 
    } 

    else { 
     Node *prevNode = getNode(position-1); 
     Node *nextNode = getNode(position); 
     prevNode->next = newNode; 
     newNode->next = nextNode; 

      } 

     } 


void deleteNode(int position) { 
    Node *currentNode; 

    int size = sizeLinkedList(); 
    if (size == 0) { 
     return; 
    } 
    if (position == 0) { 
     currentNode = head->next; 
     head = currentNode; 
    } 
    else if (position == size-1) { 
     getNode(position - 1)->next = NULL; 
     delete getNode(position); 

      } 
    else { 
     getNode(position - 1)->next = getNode(position+1); 
     delete getNode(position); 
    } 
     } 




//making a dynamic array only via pointers in VC++ 
    void makeArray() { 
    int* m = NULL; 
    int n; 
    cout << "how many entries are there?"<<endl; 
    cin >> n; 
    m = new int[n]; 
    int temp; 
    for (int x = 0; x < n; x++){ 
     cout << "enter item:"<< x+1<< endl; 
     cin >> temp; 
     *(m + x) = temp; 
    } 
    for (int x = 0; x < n; x++){ 
     cout << x+1 + ":" << "There is item: "<<*(m+x) << endl; 

    } 
    delete[]m; 
} 
int main() { 
    int x; 
    //makeArray(); 
    appendNode(1); 
    appendNode(2); 
    appendNode(32); 
    appendNode(55); 
    appendNode(66); 
    //insertNode(2, 0); 
    printLinkedList(); 
    deleteNode(3); 
    printLinkedList(); 
    sizeLinkedList(); 
    cin >> x; 

} 

我只是想練習 我刪除功能，最後else語句心不是工作代碼和幾個功能的鏈接列表，並在邏輯上我不能找出原因， 作爲我插入函數沒有任何語句正在工作，甚至不在頭或位置0.然而附加項目，返回大小，打印列表，刪除第一個和最後一個元素的作品。

謝謝！如果列表爲空

Answer 1

1. sizeLinkedList將無法​​正常工作
2. 您使用size爲不同的變量在不同的範圍（其不能回0）（在主要適用範圍，並在deleteNode）。雖然不是嚴重錯誤，但這很混亂。

3. 在deleteNode，該序列將無法工作：

   else if (position == size-1) { 
       getNode(position - 1)->next = NULL; 
       delete getNode(position); 
       } 
   

   設置之前position爲NULL節點將與非常下一行試圖干擾getNode(position)在next指針，因爲它穿越列表根據next。解決方法是扭轉這兩條線。

4. 同樣，在deleteNode你的最後一個序列將不會爲類似工作的原因所在，因爲要修改的下一個指針：

   else { 
       getNode(position - 1)->next = getNode(position+1); 
       delete getNode(position); // this list traversal will skip the node to delete! 
       } 
   

   這裏的解決方案是這樣的：

   else { 
       currentNode = getNode(position); 
       getNode(position - 1)->next = getNode(position+1); 
       delete currentNode; 
       } 
   

5. 我還重寫了包含@ 0x499602D2提供的註釋的insertNode函數。

下面是一個修改版本的代碼已經在main當前的序列固定：

#include <iostream> 
using namespace std; 

struct Node { 
    int data; 
    Node* next; 
}; 
Node* head = NULL; 
int size = 0; 
Node* tail = NULL; 

void printLinkedList() { 
    Node *search = head; 
    if (head == NULL) { 
     cout << "linkedlist is empty" << endl; 
    } 
    else { 
     while (search != NULL){ 
      cout << search->data << endl; 
      search = search->next; 
     } 
    } 
} 
int sizeLinkedList() { 
    size = 0; 
    if (head->next != NULL){ 
     size = 1; 
     Node* current = head; 
     while (current->next != NULL) { 
     current = current->next; 
     size = size + 1; 
     } 
     } 
    cout << size << endl; 
    return size; 
} 

Node *getNode(int position){ 
    Node *current = head; 
    for (int i = 0; i<position; i++) 
    { 
     current = current->next; 
    } 

    return current; 
} 
void appendNode(int n) { 
    Node *newNode = new Node; //creating new node 
    newNode->data = n; 
    newNode->next = NULL; 
    size++; 
    if (head == NULL) 
     { 
     head = newNode; 
     return; 
     } 
    else { 
     Node *current = head; 
     while (current->next != NULL) { 
      current = current->next; 
      } 
     current->next = newNode; 
     } 
    } 

void insertNode(int n, int position) { 
    Node *newNode = new Node; 
    newNode->data = n; 
    newNode->next = NULL; 
    if (position == 0){ 
      newNode->next = head; 
      head = newNode; 
    } 

    else if (position == sizeLinkedList()) { 
     appendNode(n); 
    } 

    else { 
     Node *prevNode = getNode(position-1); 
     Node *nextNode = getNode(position); 
     prevNode->next = newNode; 
     newNode->next = nextNode; 
     } 
    } 


void deleteNode(int position) { 
    Node *currentNode; 

    int my_size = sizeLinkedList(); 
    if ((my_size == 0) || (position > my_size)) { 
     return; 
     } 
    if (position == 0) { 
     currentNode = head->next; 
     head = currentNode; 
     } 
    else if (position == size-1) { 
     delete getNode(position); 
     getNode(position - 1)->next = NULL; 
     } 
    else { 
     currentNode = getNode(position); 
     getNode(position - 1)->next = getNode(position+1); 
     delete currentNode; 
     } 
    } 




//making a dynamic array only via pointers in VC++ 
    void makeArray() { 
    int* m = NULL; 
    int n; 
    cout << "how many entries are there?"<<endl; 
    cin >> n; 
    m = new int[n]; 
    int temp; 
    for (int x = 0; x < n; x++){ 
     cout << "enter item:"<< x+1<< endl; 
     cin >> temp; 
     *(m + x) = temp; 
    } 
    for (int x = 0; x < n; x++){ 
     cout << x+1 + ":" << "There is item: "<<*(m+x) << endl; 

    } 
    delete[]m; 
} 
int main() { 
    int x; 
    //makeArray(); 
    appendNode(1); 
    appendNode(2); 
    appendNode(32); 
    appendNode(55); 
    appendNode(66); 
    insertNode(2, 0); 
    printLinkedList(); 
    deleteNode(3); 
    printLinkedList(); 
    sizeLinkedList(); 
}