Linked вставка списка/удаление

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; 

} 

Я просто пытаюсь кодировать Linked List с парой функций на практике Моя функция удаления, последнее другое заявление разве работает, и логически я не могу понять, почему, за мой Функция вставки ни одна из инструкций не работает, даже на голове или в позиции 0. Однако добавляются элементы, возвращающие размер, печать списка, удаление первого и последнего элементов.

спасибо!

Answer 1

1. sizeLinkedList не будет работать правильно, если список пуст (он не может возвращать 0)
2. вы используете size в различных переменных в различных областях (в основном уровне, и в deleteNode). Это довольно запутанно, хотя и не совсем неправильно.

3. в deleteNode, эта последовательность не будет работать:

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

   установки next указатель на узел предварительного чтобы position на NULL будет мешать при попытке getNode(position) в следующей строке, поскольку она пересекает список на основе 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. Я также переписал функцию insertNode, включающую комментарий, предоставленный @ 0x499602D2.

Вот модифицированная версия кода, который имеет текущую последовательность в 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(); 
}