[BCSD] 2. DataStructure - 2019.01.28

자료구조

정의

• 전산학에서 자료를 효율적으로 이용 할 수 있도록 컴퓨터에 저장하는 방법
• 여러 종류가 있으며, 이러한 각각의 자료구조는 각자의 연산 및 목적에 맞추어져 있다.
• 프로그램을 설계할 때, 어떠한 자료구조를 선택할지는 가장 우선적으로 고려되어야 한다.

분류

• 선형 구조

  • 배열 : 가장 일반적인 구조 / 메모리 상에 같은 타입의 자료가 연속적으로 저장된다.
  • 스택 : LIFO (Last In First Out)
  • 큐 : FIFO (First In First Out)
    안드로이드에서 가장 많이 쓰임
  • 덱 : 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조
  • 연결 리스트
    1. 연결 리스트 : 각 노드에 자료와 다음 노드를 가리키는 참조값으로 구성된다.
    2. 원형 열결 리스트 : 마지막 노드가 처음 노드를 가리키는 연결 리스트.
    3. 이중 연결 리스트 : 각 노드에 이전 노드와 다음 노드를 가리키는 참조값들로 구성된다.

• 비선형 구조

  • 그래프 : 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
    • 유향 그래프 : 방향성을 가지는 그래프
    • 무향 그래프 : 방향성을 가지지 않는 그래프
  • 트리 : 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조
    • 이진 트리 : 자식이 쵀대 두 개인 트리
    • 전위, 중위, 후위

구현

연결 리스트

#include<iostream>
using namespace std;

typedef struct Node{
    int data;
    struct Node *next;
} Node;

int main(){
    Node *head = NULL;
    Node *tail = NULL;
    Node *cur = NULL;

    Node *newNode = NULL;
    int readData;

    while(1){
        cout << "Enter : ";
        cin >> readData;
        if(readData < 1)    break;

        newNode = new Node();
        newNode->data = readData;
        newNode->next = NULL;

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

        tail = newNode;
    }
    cout << endl;

    cout << "Total Data Stored : ";
    if(head == NULL){
        cout << "NO DATA" << endl;
    }
    else{
        cur = head;
        cout << cur->data << " ";

        while(cur->next != NULL){
            cur = cur->next;
            cout << cur->data << " ";
        }
    }

    cout << "\n\n";

    if(head == NULL)    return 0;
    else{
        Node *delNode = head;
        Node *delNextNode = head->next;

        cout << head->data << " IS DELETED!" << endl;
        delete delNode;

        while(delNextNode != NULL){
            delNode = delNextNode;
            delNextNode = delNextNode->next;

            cout << delNode->data << " IS DELETED!" << endl;
            delete delNode;
        }
    }
}

트리

#include<cstdio>
#include<iostream>
using namespace std;

class Node {
    public :
        char data;
        Node *parent;
        Node *brother;
        Node *child;
        Node() { }
        Node(char data) : data(data), parent(0), brother(0), child(0) { }

        ~Node() {
            parent = NULL;
            brother = NULL;
            child = NULL;
        }
};

void InsertNode(Node *R, char data){
    Node *newNode = new Node(data);
    newNode->parent = R;

    Node *cur = R->child;

    if(cur == 0)    R->child = newNode;
    while(cur != 0){
        if(cur->brother == 0){
            cur->brother = newNode;
            break;
        }
        cur = cur->brother;
    }
}

void upDataNode(Node *R, char searchNode, char data){
    if(R == 0) return;
    if(R->data == searchNode){
        R->data = data;
        return;
    }
    if(R->brother != 0)    upDataNode(R->brother, searchNode, data);
    if(R->child != 0) upDataNode(R->child, searchNode, data);

    return;
}

void deleteNode(Node *R, char searchNode){
    if(R == 0) return;
    if(R->data == searchNode){
        Node *parent = R->parent;

        if(parent->child == R){
            Node *temp = R;
            parent->child = R->brother;
            delete temp;
        }
        else{
            Node *cur = parent->child;
            Node *pre = 0;
            while (cur != 0){
                if(cur->data == searchNode){
                    Node *temp = cur;
                    pre->brother = cur->brother;
                    delete temp;
                    break;
                }
                pre = cur;
                cur = cur->brother;
            }
        }
    }

    if(R->brother != 0)    deleteNode(R->brother, searchNode);
    if(R->child != 0)    deleteNode(R->child, searchNode);

    return;
}

void deleteTree(Node *R){
    if(R==0)    return;

    deleteTree(R->brother);
    deleteTree(R->child);
    delete R;
    R = 0;
}