글 읽기 - 덱 구현 문제 SegFault와 InvalidPointer 발생

tori1753 2년 전 1

pop_front와 pop_back에서 delete구문을 빼면 SegFault에러가. 넣으면 Invalid Pointer에러가 발생합니다.

예제를 넣었을땐 잘 작동하였는데, 뭐가문제인지 잘 모르겠습니다.

//baekjoon ps xx

#include <iostream>
#include <deque>
#include <string>

using namespace std;

struct node
{
    int data;
    node *previous;
    node *next;
    node()
    {
        data = 0;
        next = NULL;
        previous = NULL;
    }
    void setdata(const int &data)
    {
        this->data = data;
    }
    int getdata()
    {
        return this->data;
    }
    void setnext(node *next)
    {
        this->next = next;
    }
    node *getnext()
    {
        return this->next;
    }
    void setprevious(node *previous)
    {
        this->previous = previous;
    }
    node *getprevious()
    {
        return this->previous;
    }
};

class mydeque
{
private:
    node begin;
    node end;
    int _size;

public:
    mydeque()
    {
        begin.setnext(&end);
        end.setprevious(&begin);
        _size = 0;
    }
    void push_front(const int &n)
    {
        node *temp = new node();
        temp->setdata(n);
        temp->setnext(begin.getnext());
        temp->setprevious(&begin);
        (*begin.getnext()).setprevious(temp);
        begin.setnext(temp);
        _size++;
    }
    void push_back(const int &n)
    {
        node *temp = new node();
        temp->setdata(n);
        temp->setprevious(end.getprevious());
        temp->setnext(&end);
        (*end.getprevious()).setnext(temp);
        end.setprevious(temp);
        _size++;
    }
    void pop_front()
    {
        if (_size == 0)
            cout << -1 << '\n';
        else
        {
            cout << (*begin.getnext()).getdata() << '\n';
            node *tempptr = (*begin.getnext()).getnext();
            delete begin.getnext();
            begin.setnext(tempptr);
            _size--;
        }
    }
    void pop_back()
    {
        if (_size == 0)
            cout << -1 << '\n';
        else
        {
            cout << (*end.getprevious()).getdata() << '\n';
            node *tempptr = (*end.getprevious()).getprevious();
            delete end.getprevious();
            end.setprevious(tempptr);
            _size--;
        }
    }
    void size()
    {
        cout << _size << '\n';
    }
    void empty()
    {
        if (_size == 0)
            cout << 1 << '\n';
        else
            cout << 0 << '\n';
    }
    void front()
    {
        if (_size == 0)
            cout << -1 << '\n';
        else
            cout << (*begin.getnext()).getdata() << '\n';
    }
    void back()
    {
        if (_size == 0)
            cout << -1 << '\n';
        else
            cout << (*end.getprevious()).getdata() << '\n';
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    mydeque dq;
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        static string str;
        static int input;
        cin >> str;
        if (str == "push_front")
        {
            cin >> input;
            dq.push_front(input);
        }
        else if (str == "push_back")
        {
            cin >> input;
            dq.push_back(input);
        }
        else if (str == "pop_front")
            dq.pop_front();
        else if (str == "pop_back")
            dq.pop_back();
        else if (str == "size")
            dq.size();
        else if (str == "empty")
            dq.empty();
        else if (str == "front")
            dq.front();
        else if (str == "back")
            dq.back();
    }
    return 0;
}

dldyddlwl 2년 전 1

아래에 있습니다.

// 연결을 잘해주셨는데! 놓치신 부분이 있습니다.

// pop front의 경우에

// begin -> deleteOne -> tempptr에서, tempptr의 prev가 begin으로 설정되지 않았습니다.

// begin -> tempptr
// begin ?<-? tempptr


// pop back의 경우에
// tempptr -> deleteOne -> end 에서, tempptr의 next가 end로 설정되지 않았습니다.

// tempptr <- end
// tempptr ?->? end


// 이렇게 화살표로 하나씩 그림을 그리면서 하시면 좀 더 실수를 줄일 수 있습니다.


void pop_front()
    {
        if (_size == 0)
            cout << -1 << '\n';
        else
        {
            cout << (*begin.getnext()).getdata() << '\n';
            node *tempptr = (*begin.getnext()).getnext();
            delete begin.getnext();
            begin.setnext(tempptr);
            _size--;

            // 추가해주세요
            tempptr->setprevious(&begin);        
            
        }
    }
    void pop_back()
    {
        if (_size == 0)
            cout << -1 << '\n';
        else
        {
            cout << (*end.getprevious()).getdata() << '\n';
            node *tempptr = (*end.getprevious()).getprevious();
            delete end.getprevious();
            end.setprevious(tempptr);
            _size--;
            
           // 추가해주세요
            tempptr->setnext(&end);
        }
    }

tori1753 2년 전 0

감사합니다 선생님..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

덱 구현 문제 SegFault와 InvalidPointer 발생

tori1753 2년 전 1

dldyddlwl 2년 전 1

tori1753 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말