글 읽기 - 양방향 연결리스트와 덱

choyj1127 2년 전 0

꽤나 정석대로 풀었다고 생각합니다..그런데 런타임에러가 나왔네요 도와주세요ㅠ

/*양방향 연결리스트*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int Data;
typedef struct _node {
    struct _node* next;
    struct _node* prev;
    Data data;
}Node;

typedef struct _deque {
    Node* head;
    Node* tail;
    int numOfData;
}Deque;

void DequeInit(Deque* pdeq) {
    pdeq->head = NULL; pdeq->tail = NULL; pdeq->numOfData = 0;
}
int DIsEmpty(Deque* pdeq) {
    if (pdeq->head == NULL) return 1;
    else return 0;
}
int DCount(Deque* pdeq) {
    return pdeq->numOfData;
}
void DAddFirst(Deque* pdeq, Data data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    
    newNode->next=pdeq->head;
    if(pdeq->head==NULL) pdeq->tail=newNode;
    else pdeq->head->prev=newNode;
    
    newNode->prev=NULL;
    pdeq->head=newNode;
    (pdeq->numOfData)++;
}
void DAddLast(Deque* pdeq, Data data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    
    newNode->prev=pdeq->tail;
    
    if(pdeq->head==NULL) pdeq->head=newNode;
    else pdeq->tail->next=newNode;
    
    newNode->next=NULL;
    pdeq->tail=newNode;
    (pdeq->numOfData)++;
}

Data DRemoveFirst(Deque* pdeq) {
    Node* rnode=pdeq->head;
    Data rdata=rnode->data;
    if(pdeq->head==NULL) return -1;
    
    pdeq->head=pdeq->head->next;
    free(rnode);
    
    if(pdeq->head==NULL) pdeq->tail=NULL;
    else pdeq->head->prev=NULL;
    
    (pdeq->numOfData)--;
    return rdata;
}
Data DRemoveLast(Deque* pdeq) {
    Node* rnode=pdeq->tail;
    Data rdata=rnode->data;
    if(pdeq->head==NULL) return -1;
    
    pdeq->tail=pdeq->tail->prev;
    free(rnode);
    if(pdeq->tail==NULL) pdeq->head=NULL;
    else pdeq->tail->next=NULL;
    
    (pdeq->numOfData)--;
    return rdata;
}
Data DGetFirst(Deque* pdeq) {
    if (pdeq->head == NULL) return -1;
    return pdeq->head->data;
}
Data DGetLast(Deque* pdeq) {
    if (pdeq->head == NULL) return -1;
    return pdeq->tail->data;
}

int main() {
    Deque deq; DequeInit(&deq);
    int N; scanf("%d", &N);
    char command[15]; int x;
    for (int i = 0; i < N; i++) {
        gets(command);
        if (strcmp(command, "push_front")==0) {
            scanf("%d", &x);
            DAddFirst(&deq, x);
        }
        else if (strcmp(command, "push_back")==0) {
            scanf("%d", &x);
            DAddLast(&deq, x);
        }
        else if (strcmp(command, "pop_front")==0) {
            printf("%d\n", DRemoveFirst(&deq));
        }
        else if (strcmp(command, "pop_back")==0) {
            printf("%d\n", DRemoveLast(&deq));
        }
        else if (strcmp(command, "size")==0) {
            printf("%d\n", DCount(&deq));
        }
        else if (strcmp(command, "empty")==0) {
            printf("%d\n", DIsEmpty(&deq));
        }
        else if (strcmp(command, "front")==0) {
            printf("%d\n", DGetFirst(&deq));
        }
        else if (strcmp(command, "back")==0) {
            printf("%d\n", DGetLast(&deq));
        }
    }

    return 0;
}

uuiip7878 2년 전 0

정확히 어떤 에러가 나나요? Segfault 등등...

uuiip7878 2년 전 0

예제는 넣어보신 건가요? gcc 환경 기준 push_front push_back이 작동을 정상적으로 하지 않네요... pop_back pop_front는 둘 다 세그폴트(런타임 에러 중 하나) 뜨는 것 같습니다.

15
push_back 1 //실제로는 아무것도 넣지 않고 있습니다...
push_front 2 //상동
front
//-1
back
//-1
size
//0
empty
//1
pop_front
//Segmentation Fault로 인한 프로그램 중단

choyj1127 2년 전 0

Add관련된 함수가 이상한 것 같아서 수정했습니다.

비주얼로 돌려보니까 제가 입출력 함수가 뭐를 잘못 알고 있었던건지 command 입력후에 strcmp가 작동이 안되서 어떤 리스트 작동도 되지 않는 것 같은데 어떻게 수정하는게 맞는건지.. 조금만 조언 부탁드릴게요ㅠㅠ

/*양방향 연결리스트*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int Data;
typedef struct _node {
    struct _node* next;
    struct _node* prev;
    Data data;
}Node;

typedef struct _deque {
    Node* head;
    Node* tail;
    int numOfData;
}Deque;

void DequeInit(Deque* pdeq) {
    pdeq->head = NULL; pdeq->tail = NULL; pdeq->numOfData = 0;
}
int DIsEmpty(Deque* pdeq) {
    if (pdeq->head == NULL) return 1;
    else return 0;
}
int DCount(Deque* pdeq) {
    return pdeq->numOfData;
}
void DAddFirst(Deque* pdeq, Data data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    if (pdeq->head == NULL) {
        pdeq->tail = newNode;
        newNode->next = newNode;
    }
    else {
        pdeq->head->prev = newNode;
        newNode->next = pdeq->head;
    }
    newNode->prev = NULL;
    pdeq->head = newNode;
    (pdeq->numOfData)++;
}
void DAddLast(Deque* pdeq, Data data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    if (pdeq->head == NULL) {
        pdeq->head = newNode;
        newNode->prev = newNode;
    }
    else {
        pdeq->tail->next = newNode;
        newNode->prev = pdeq->tail;
    }

    newNode->next = NULL;
    pdeq->tail = newNode;
    (pdeq->numOfData)++;
}

Data DRemoveFirst(Deque* pdeq) {
    Node* rnode = pdeq->head;
    Data rdata = rnode->data;
    if (pdeq->head == NULL) return -1;

    pdeq->head = pdeq->head->next;
    free(rnode);

    if (pdeq->head == NULL) pdeq->tail = NULL;
    else pdeq->head->prev = NULL;

    (pdeq->numOfData)--;
    return rdata;
}
Data DRemoveLast(Deque* pdeq) {
    Node* rnode = pdeq->tail;
    Data rdata = rnode->data;
    if (pdeq->head == NULL) return -1;

    pdeq->tail = pdeq->tail->prev;
    free(rnode);
    if (pdeq->tail == NULL) pdeq->head = NULL;
    else pdeq->tail->next = NULL;

    (pdeq->numOfData)--;
    return rdata;
}
Data DGetFirst(Deque* pdeq) {
    if (pdeq->head == NULL) return -1;
    return pdeq->head->data;
}
Data DGetLast(Deque* pdeq) {
    if (pdeq->head == NULL) return -1;
    return pdeq->tail->data;
}

int main() {
    Deque deq; DequeInit(&deq);
    int N; scanf("%d", &N);
    char command[15]; int x;
    for (int i = 0; i < N; i++) {
        fgets(command,sizeof(command),stdin);
        if (strcmp(command, "push_front") == 0) {
            scanf("%d", &x);
            DAddFirst(&deq, x);
        }
        else if (strcmp(command, "push_back") == 0) {
            scanf("%d", &x);
            DAddLast(&deq, x);
        }
        else if (strcmp(command, "pop_front") == 0) {
            printf("%d\n", DRemoveFirst(&deq));
        }
        else if (strcmp(command, "pop_back") == 0) {
            printf("%d\n", DRemoveLast(&deq));
        }
        else if (strcmp(command, "size") == 0) {
            printf("%d\n", DCount(&deq));
        }
        else if (strcmp(command, "empty") == 0) {
            printf("%d\n", DIsEmpty(&deq));
        }
        else if (strcmp(command, "front") == 0) {
            printf("%d\n", DGetFirst(&deq));
        }
        else if (strcmp(command, "back") == 0) {
            printf("%d\n", DGetLast(&deq));
        }
    }

    return 0;
}

uuiip7878 2년 전 0

strcmp보단 fgets가 문제 같아보이네요.

//before
fgets(command,sizeof(command),stdin); //space를 기준으로 입력받지 못함 = push_back 다음 숫자까지 문자열로 받아버림
//after
scanf("%s",command); //space가 입력의 기준이므로 push_back 등의 인자를 추가로 받는 명령을 제대로 처리 가능

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

문제

문제

출처

ICPC

양방향 연결리스트와 덱

choyj1127 2년 전 0

uuiip7878 2년 전 0

uuiip7878 2년 전 0

choyj1127 2년 전 0

uuiip7878 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말