c언어 linked list를 활용한 stack 구현하기

Question

안녕하세요. 도움이 필요해 글을 올립니다. 대학과제중인데 몇일을 봐도 모르겠네요. push는 잘 작동하는데 pop에서 메모리 오류가 나오는 것 같습니다. 코드에 어떤 문제가 있을까요.. 제발 도와주세요..#include #include #define MAX_SIZE 10struct Node { int data; struct Node* link;};struct Node* front = NULL; // front is empty initiallystruct Node* top = NULL; // rear is empty initiallyint n_nodes = 0; // a variable to store number of nodes in queueint stack_full() { if(n_nodes == MAX_SIZE) return 1; else return 0;}int stack_empty() { if(top == NULL) return 1; else return 0;}void push(int x) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); // test if memory allocation failed if(temp == NULL) { printf("Memory allocation failed. "); exit(1); } temp->data = x; temp->link = NULL; if(front == NULL && top == NULL){ front = top = temp; n_nodes++; return; } top->link = temp; top = temp; n_nodes++;}int pop() { // free a deleted (disconnected) node struct Node* temp = top; int num; num = top->data; top->data = top->link; free(temp); return num;}// helper function: traverse queue from front to rear and print elementsvoid print_stack() { struct Node* n; n = front; printf("stack ="); while (n != NULL) { printf(" %d ", n->data); n = n->link; } printf(" ");}// helper function: run a series of enqueues// input arguments: int arr[] <- an array from which input values are taken// input arguments: int num <- total number of elements to pushvoid run_pushes(int arr[], int num) { for(int i=0; i %d , ", value); } else { printf("stack empty! "); } print_stack(); }}int main() { int numbers[] = {3, 9, 4, 5, 2, 1, 6, 8, 7, 5, 8}; print_stack(); run_pushes(numbers, 5); run_pops(3); run_pushes(numbers, 10); run_pops(11); run_pushes(numbers, 11);}

bot99 · Accepted Answer

단방향 연결리스트로 스택을 구현하려면, 첫번째 원소가 top이 되고 원소의 추가는 맨 앞에서 이루어지는 형태로 구현해야 합니다. 위의 소스코드처럼 구현하면 pop 동작 시에 맨 마지막 노드(top)의 이전 노드를 구하기 위해 처음인 front부터 n번의 순회가 이루어져야 하고, 이는 비효율적입니다.하지만 이런 식으로 구현하게 되면, 이제는 print_stack() 함수가 비효율적으로 동작하는 문제가 있습니다. 여기에 대한 해결책으로는 양방향 연결리스트로 스택을 구현하는 것이죠.일단 print_stack()의 효율성을 포기하고 단방향 연결리스트로 구현하면 다음과 같습니다.#include #include #define MAX_SIZE 10 struct Node { int data; struct Node* link; }; struct Node* top = NULL; int n_nodes = 0; int stack_full() { if (n_nodes == MAX_SIZE) return 1; else return 0; } int stack_empty() { if(top == NULL) return 1; else return 0; } void push(int x) { struct Node * temp = malloc(sizeof(*temp)); if (temp == NULL) { printf("Memory allocation failed. "); exit(1); } temp->data = x; temp->link = top; top = temp; n_nodes++; return; } int pop() { struct Node * temp = top; int num; if ( stack_empty() ) { printf("Error: Can't pop from empty stack. "); return -1; } num = top->data; top = top->link; free(temp); return num; } void print_stack() { int i; if ( stack_empty() ) { printf("Stack: "); return; } i = pop(); print_stack(); printf("%d ", i); push(i); return; } void run_pushes(int arr[], int num) { for(int i=0; i %d , ", value); } else { printf("stack empty! "); } print_stack(); printf(" "); } } int main() { int numbers[] = {3, 9, 4, 5, 2, 1, 6, 8, 7, 5, 8}; print_stack(); printf(" "); run_pushes(numbers, 5); run_pops(3); run_pushes(numbers, 10); run_pops(11); run_pushes(numbers, 11); return 0; }

selfless · Answer

chatGPT를 이용해보세요.아래는 chatGPT의 답변입니다.pop 함수의 문제는 아래 부분입니다.int pop() {     // free a deleted (disconnected) node     struct Node* temp = top;     int num;     num = top->data;     top->data = top->link;     free(temp);     return num; } int pop() {     // free a deleted (disconnected) node     struct Node* temp = top;     int num;     num = top->data;     top->data = top->link;     free(temp);     return num; }여기서 top이 가리키는 노드를 제거하려고 할 때, top->data 대신에 top->link를 사용하고 있습니다. 따라서 노드 자체가 아닌 노드가 가리키는 다음 노드를 제거하게 됩니다.올바른 pop 함수는 다음과 같습니다.int pop() {     // free a deleted (disconnected) node     struct Node* temp = top;     int num;     num = top->data;     top = top->link;     free(temp);     n_nodes--;     return num; }int pop() {     // free a deleted (disconnected) node     struct Node* temp = top;     int num;     num = top->data;     top = top->link;     free(temp);     n_nodes--;     return num; }여기서는 top->link 대신 top을 업데이트하여 다음 노드가 아닌 현재 노드를 제거하고 있습니다. 또한 노드가 제거될 때마다 n_nodes 변수를 감소시켜줘야 합니다.제안드리는 수정 사항을 반영하시면 코드가 정상적으로 작동할 것입니다.

신히 · Answer

chatGPT는 거짓말을 잘하니 조심하셔야 합니다free 하는곳에서 top이 아니라 top->link 가 맞겠네요. 물론, 이것만 수정했다고 잘 돌아가는 소스는 아닙니다.free(top->link);&#x1f680; 소스 테스트 해보기

c언어 linked list를 활용한 stack 구현하기

3개의 답변

Q&A 목록