단일 링크드 리스트 뭐가 잘못된 건가요?

Question

#include #include #include typedef int Element; typedef struct LinkedNode { Element data; struct LinkedNode* link; } Node; Node* head = NULL; // 초기화 void init_list() { head = (Node*)malloc(sizeof(Node)); head->data = NULL; head->link = NULL; } int is_empty() { if (head == NULL) return 1; else return 0; } Node* get_entry(int pos) // pos 위치에 있는 요소를 반환 { Node* p = head; // 헤드 포인터 int i; for (i = 0; i < pos; i++, p=p->link){ if (p == NULL) return NULL; // pos 위치까지 데이터가 없을 경우 예외처리 } return p; } int size() // 리스트 안의 요소의 개수를 반환 { Node* p; int count = 0; for (p = head; p != NULL; p = p->link) count++; // p가 NULL까지 count++ return count; } void replace(int pos, Element val) // pos 위치를 새로운 요소 item으로 바꿈 { Node* node = get_entry(pos); // pos 위치의 요소를 가져옴 if (node != NULL) // node가 null이 아닐경우 node->data = val; // replace } Node* search_list(Element val) // 리스트에 요소 val이 있는지를 찾음 { Node* p; for (p = head; p != NULL; p = p->link) // 리스트 순회 if (p->data == val) return p; // Node의 data가 val과 같으면 return return NULL; // 찾기 실패 } void insert_next(Node * before, Node * node) // before의 다음 노드에 node를 연결 { if (node != NULL) { node->link = before->link; // node의 다음 노드를 연결해줌 before->link = node; // before의 다음 노드에 node 연결 } } void insert(int pos, Element val) // pos 위치에 새로운 요소 val을 삽입 { Node* new_node, * prev; new_node = (Node*)malloc(sizeof(Node)); // 새로운 노드 할당 new_node->data = val; if (pos == 0) { // 처음 위치 이면 new_node->link = head; // new_node에 head 연결 head = new_node; // head 재설정 } else { prev = get_entry(pos-1); // pos위치 이전 노드 가져옴 if (prev != NULL) insert_next(prev, new_node); // 새로운 노드를 pos 위치에 삽입 else free(new_node); } } Node * remove_next(Node * prev) // prev의 다음 노드를 삭제 { Node* removed = prev->link; // 삭제할 노드를 가져옴 if (removed != NULL) { prev->link = removed->link; } return removed; // 삭제할 노드 반환 (free 해줘야 함) } void delete(int pos) // pos 위치에 있는 요소를 삭제 { Node* prev, * removed; if (pos == 0 && is_empty() == 0) { // 첫번째 노드일 경우 removed = get_entry(pos); // 삭제할 노드를 가져옴 head = head->link; free(removed); // 메모리 반환 } else { prev = get_entry(pos-1); // pos위치 이전 노드 가져옴 if (prev != NULL) { remove_next(prev); // prev의 다음 노드를 삭제 free(removed); // 메모리 반환 } } } void clear_list() { while (is_empty() == 0) // list가 빌때까지 delete(0); // 첫번째 노드를 하나씩 삭제 } void print_list() { Node* p; for (p = head; p != NULL; p = p->link) printf("%d->", p->data); printf("NULL "); } Node * concat_list(Node * new_node) { if(is_empty()) return new_node; //기존 list가 비어있는 경우 else if(new_node == NULL) return new_node; //새로운 list가 비어있는 경우 else{ Node* p; //새로운 노드 생성 p = head;//노드에 기존 리스트 대입 while (p->link != NULL) { p = p->link; } //노드가 마지막 요소를 가짐 p->link = new_node; //노드가 new_node를 가르킴 return head; } } int main(void) { Element num; int pos; int n, i, j, len; char c[15]; Node* tmp_head= NULL; Node* new_head= NULL; init_list(); scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%s", c); if (strcmp(c, "insert") == 0) { scanf("%d %d ",&pos, &num); insert(pos,num); print_list();} else if (strcmp(c, "delete") == 0) { scanf("%d ", &pos); delete(pos); print_list();} else if (strcmp(c, "size") == 0) {printf("%d ", size()); print_list();} else if (strcmp(c, "empty") == 0) {printf("%d ", is_empty()); print_list();} else if (strcmp(c, "getEntry") == 0) { scanf("%d ", &pos); printf("%d ", get_entry(pos)->data); print_list();} else if (strcmp(c, "search_list") == 0) { scanf("%d ", &num); printf("%d ", search_list(num)->data); print_list();} else if (strcmp(c, "replace") == 0) { scanf("%d %d ", &pos, &num); replace(pos,num); print_list();} else if (strcmp(c, "concat_list") == 0) { tmp_head = head; init_list(); scanf("%d", &len); for (j = 0; j < len; j++) { scanf("%d %d ",&pos, &num); insert(pos,num); } printf("new_node: "); print_list(); new_head = head; head = tmp_head; head = concat_list(new_head); print_list(); } else printf("error "); } return 0; } 테스트케이스는 이렇습니다.input: 4 insert 0 1 size delete 0 size"ouptut: 1->NULL 1 1->NULL NULL 0 NULL 하지만 제가 돌렸을 때 실제 결과값으로는 1->0->NULL 2 1->0->NULL 0->NULL 1 0->NULL 이런식으로 head값이 아예 0으로 초기화가 되는건지 이렇게 되는데 아직도 뭘 잘못했는지를 모르겠습니다. 메모리 할당 방법이 잘못되었을까요? 왜 head가 0 으로 되는지 모르겠습니다..

Deer Hunter · Answer

init_list function에서 head 값들을 초기화하고 있네요.

단일 링크드 리스트 뭐가 잘못된 건가요?

1개의 답변

#linkedlist 목록