링크 된 목록의 끝에서 삭제

Question

6 개의 난수를 생성하고 링크 된 목록에 넣고 출력하는 프로그램을 작성 중입니다. 그런 다음 6 개의 숫자를 모두 얻으면 첫 번째 노드를 삭제하고 나머지 5 개를 출력 한 다음 마지막 노드를 삭제하고 노드 4가 남을 때까지 나머지 4 개를 앞뒤로 출력합니다. 어쨌든 나는 연결된 목록을 생성하고 노드를 저장하여 출력 할 수 있으며 매번 첫 번째 노드를 삭제할 수 있지만 마지막 노드를 삭제하는 방법을 알 수는 없습니다. 마지막 노드를 삭제하는 방법에 대한 도움을 주시면 매우 감사하겠습니다. 나는 당신이 당신의 MCVE (입력, 출력, 삽입 등)의 나머지 부분을 완료 한

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
#include "SortedLinkedList.h" 

using namespace std; 

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

node *head = NULL; 

void push_sorted(int value) 
{ 
    node *newNode = new node; 
    newNode->data = value; 
    newNode->next = NULL; 
    if(head == NULL) 
    { 
     head = newNode; 
    } 
    else 
    { 
     node *newNode_2 = head; 
     while(newNode_2->next != NULL) 
     { 
      newNode_2 = newNode_2-> next; 
     } 
     newNode_2->next = newNode; 
    } 
} 

void pop_front() 
{ 
    node *temp; 
    temp = head; 
    head = head->next; 
    free(temp); 
} 

void pop_back() 
{ 
} 

bool isEmpty(int count) 
{ 
    if(count == 0) 
    { 
     return false; 
    } 

    else 
    { 
     return true; 
    } 

} 

void print() 
{ 
    node* current = head; 
    while(current != NULL) 
    { 
     cout << current-> data << " "; 
     current = current->next; 
    } 
    cout << endl; 
} 
int main() 
{ 
    int count = 6; 
    const int NUMS = 6;  //insert elements into the sorted linked list in an ascending order 
    const int RANGE = 21; //each element is in the range [-10, 10] 
    /*SortedLinkedList mylist;*/ 
    srand(time(0)); 
    for (int i = 0; i < NUMS; i++) 
    { 
     int data = (rand() % RANGE) - 10; 
     cout << "Adding " << data << " to the sorted linked list: " << endl; 
     push_sorted(data); 
     print(); 
    } 

    while ((isEmpty(count) == true)) 
    { 
     cout << "Removing from front..." << endl; 
     pop_front(); 
     print(); 
     count --; 
     cout << "Removing from back..." << endl; 
     pop_back(); 
     print(); 
     count --; 
    } 
    system("pause"); 
    return 0; 
} 

Answer 1

... 마지막 노드를 삭제하는 함수와 pop_back를 사용하고 있습니다. (그러나 구조체 내부의 메서드를 이동하는 것이 좋습니다.)

다음 재귀 솔루션을 제공하기로 결정했습니다. 오직 하나의 테스트만으로도 효과가있는 것으로 보입니다.

만약 당신이 재귀를 이해하지 못한다면, 당신은 루프 반복 접근법을 다루는 것이 좋습니다. 재귀를 이해한다면 많은 사람들이 쉽게 찾을 수있는 루프 반복 접근법을 사용해야합니다.

void pop_back() 
{ 
    bool isLast = false; 
    if(nullptr != head) // does list have any elements? 
    { 
     // use the recursive form to find last, and 
     // return a bool to find the next to last 
     isLast = head->pop_backR(); // recurse to last element 

     if (isLast) // i.e. only 1 element in list, the head 
     { 
     delete (head); // remove it 
     head = nullptr; 
     } 
    } 

    // note: on std::list, calling pop_back when container empty is undefined. 
    // tbd - throw underflow? your choice here 
} 


bool pop_backR() 
{ 
    if(nullptr == next) 
     return true; // last node found, return feedback to previous node 

    // last node not found, continue search 
    bool nxtIsLast = next->pop_backR(); 

    // check - did we find the last element yet? 
    if (nxtIsLast) 
    { 
     // at this point we know next is last 
     delete (next); // so delete last 
     next = nullptr; // remove it from list 
     return false; // we are done, now decurse with no more deletes 
    } 
    else // previous recursion did not find it 
     return false; 
} 

이것은 제대로 작동하는 것으로 보이지만 잘 테스트되지 않았습니다. 내 시스템에

출력 -

Adding -9 to the sorted linked list: 
-9 
Adding 0 to the sorted linked list: 
-9 0 
Adding -6 to the sorted linked list: 
-9 0 -6 
Adding 10 to the sorted linked list: 
-9 0 -6 10 
Adding -8 to the sorted linked list: 
-9 0 -6 10 -8 
Adding -3 to the sorted linked list: 
-9 0 -6 10 -8 -3 
Removing from front... 
0 -6 10 -8 -3 
Removing from back... 
0 -6 10 -8 
Removing from front... 
-6 10 -8 
Removing from back... 
-6 10 
Removing from front... 
10 
Removing from back...