[알고리즘] 연결리스트 스택 구현(자료구조6)

연결 리스트 스택 방식

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 구조체 정의
typedef struct Node {
    int x;                // 노드의 데이터 필드
    struct Node* link;    // 다음 노드를 가리키는 링크 필드
} Node;

// 노드를 연결 리스트에 삽입하는 함수
Node* insertNode(Node* tail, int data) {
    // 새로운 노드 생성
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        fprintf(stderr, "메모리 할당 실패.\n");
        return NULL;
    }
    // newNode 초기화
    newNode->x = data;
    newNode->link = NULL;

    if (tail == NULL) {
        return newNode; // 빈 리스트에 첫 노드를 삽입
    } else {
        tail->link = newNode; // 이전 노드의 link를 새로운 노드로 설정
        return newNode; // tail 포인터 갱신
    }
}

// 노드를 연결 리스트에서 삭제하는 함수
Node* deleteNode(Node* head, bool* check) {
    if (head == NULL) {
        printf("리스트가 비어 있습니다.\n");
        return NULL; // 빈 리스트에서 삭제를 시도하면 아무것도 변경하지 않음
    } else if (head->link == NULL) {
        // 하나의 노드만 존재할 때
        free(head);
        *check = true;
        return NULL;
    } else {
        Node* temp = head;
        Node* prev = NULL;

        while (temp->link != NULL) {
            prev = temp;
            temp = temp->link;
        }
        if (prev == NULL) {
            free(head);
            return NULL;
        } else {
            prev->link = NULL;
            free(temp);
            return prev;
        }
    }
}

// 연결 리스트를 출력하는 함수
void displayList(const Node* head) {
    if (head == NULL) {
        printf("리스트가 비어 있습니다.\n");
        return;
    }

    const Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->x);
        temp = temp->link;
    }
    printf("NULL\n");
}

// 특정 데이터를 검색하는 함수
void searchNode(const Node* head, int x) {
    const Node* temp = head;
    bool found = false;

    while (temp != NULL) {
        if (x == temp->x) {
            printf("찾는 %d가 있습니다.\n\n", temp->x);
            found = true;
            break;
        }
        temp = temp->link;
    }

    if (!found) {
        printf("%d를 찾을 수 없습니다.\n\n", x);
    }
}

int main(int argc, const char* argv[]) {
    Node* head = NULL;
    Node* tail = NULL;
    int n, x;
    bool check = true; // check 변수 초기화

    while (1) {
        printf("0 -> 종료\n");
        printf("1 -> 삽입\n");
        printf("2 -> 삭제\n");
        printf("3 -> 찾기\n");
        printf("4 -> 출력\n");
        printf("입력 -> ");
        scanf("%d", &n);

        if (n == 0) {
            break;
        } else if (n == 1) {
            printf("입력 -> ");
            scanf("%d", &x);
            if (check) {
                head = tail = insertNode(tail, x);
                check = false; // 첫 노드 삽입 후 check 업데이트
            } else {
                tail = insertNode(tail, x);
            }
        } else if (n == 2) {
            if (check) {
                puts("더 이상 삭제가 불가능 합니다.");
            } else {
                tail = deleteNode(head, &check);
            }
        } else if (n == 3) {
            printf("찾으려는 숫자를 입력: ");
            scanf("%d", &x);
            searchNode(head, x);
        } else if (n == 4) {
            displayList(head);
        }
    }

    // 메모리 해제
    while (head != NULL) {
        Node* temp = head;
        head = head->link;
        free(temp);
    }

    return 0;
}

 

 

기능

• 삽입
• 삭제
• 검색
• 출력