자료구조 클래스별 요약정리

1. class Array

class Array {
public:
    int arr_size = 10000; //Array의 크기가 필요하다
    int* array; //동적할당을 위한 int포인터가 필요하다
    int count = 0; //배열의 개수가 필요하다

 

 

int at(int idx) {}

void set(int idx, int value) {}

void add(int idx, int value) {}

 

2. Singly LinkedList

class Node {
public:
    int data; //값이 필요하다
    Node* next; //다음노드 포인터가 필요하다

 

class SinglyLinkedList {
public:
    Node* head; //첫노드
    Node* tail; //끝노드

 

int empty() {}
    
void addFront(int data) {}
    
int removeFront() {}
    
int front() {}

 

3. Stack (based Array)

class Stack {
public:
    int capacity; //스택의 크기
    int* stack; //동적할당을 위한 int포인터
    int t; //스택상단 위치의 index값

 

int empty() {}
    
int top() {}
    
void push(int data) {}
    
int pop() {}
    
int size() {}

 

4. Stack (based Singly LinkedList)

class Node {
public:
    int data; //값
    Node* next; //다음노드 포인터

 

class LinkedList {
public:
    Node* head; //첫노드
    Node* tail; //끝노드

 

int empty() {}

void append(int data) {}

int remove() {
    u = head; p = head;
    while(p->next != NULL) {
         u = p;
         p = p->next;
    }
    if(p == head) {head,tail = NULL;}
    u->next = NULL; tail = u; delete p;
}

int peek() {}

 

class Stack {
public:
    int n; //스택의 크기
    LinkedList* stack; //list의 포인터

 

int empty() { return stack->empty(); }

int top() { stack->tail->data; }

void push(int data) { stack->append(data); n++; }

int pop() { return stack->remove(); }

int size() { return n; }

 

5. Queue (based Array)

class Queue {
public:
    int capacity; //queue의 크기
    int* queue; //동적할당을 위한 int포인터
    int f; //앞부분 index값
    int r; //뒷부분이전 index값

 

int empty() { if((r+1)%capacity == f) }
    
int size() { return (r-f+1 + capacity)%capacity; }
    
void front() {}
    
void rear() {}
    
void enqueue(int data) {
    if(size()+1 == capacity)
        cout<<"Full\n";
    else {
        r = (r+1)%capacity;
        queue[r] = data;
    }
}
    
void dequeue() {
    if(empty())
        cout<<"Empty\n";
    else {
        cout<<queue[f]<<"\n";
        queue[f] = 0;
        f = (f+1)%capacity;
    }
}

 

6. Queue (based Singly LinkedList)

class Node {
public:
    int data; //값
    Node* next; //다음노드

 

class LinkedList {
public:
    Node* head; //첫노드
    Node* tail; //끝노드

 

int empty() {}
    
void append(int data) {}
    
int remove_front() {}
    
int peek_front() {}
    
int peek_rear() {}

 

class Queue {
public:
    int n; //개수
    int capacity; //큐의 크기
    LinkedList* queue; //list포인터

 

int size() {return n}

int empty() {return n==0}
    
void front() { queue->peek_front() }
    
void rear() { queue->peek_rear() }
    
void enqueue(int data) {
    if(n+1 != capacity) {
        queue->append(data); n++;
}
    
void dequeue() { queue->remove_front() }

 

7. Sequence (based Iterator, Doubly LinkedList)

class Node {
public:
    int e; //값
    Node* prev; //이전노드
    Node* next; //다음노드

 

class Iterator {
public:
    Node* v; //특정노드를 저장하기 위한 포인터

 

Iterator(Node* u) { v = u; }

int &operator*() { return v->e; }

bool operator==(const Iterator &p) const { return this->v == p.v; }

bool operator!=(const Iterator &p) const {}

Iterator &operator++() {
    v = v->next;
    return *this;
}

Iterator &operator--() {}

friend class Sequence;

 

class Sequence {
public:
    int n; //sequence의 개수
    Node* header; //맨앞 더미노드
    Node* trailer; //맨뒤 더미노드

 

Sequence() {
        this->n = 0;
        this->header = new Node;
        this->trailer = new Node;
        header->next = trailer;
        trailer->prev = header;
}

int size() const { return n; }

bool empty() const { return (n==0); }

Iterator begin() const { return Iterator(header->next); }

Iterator end() const { return Iterator(trailer); }

void insert(const Iterator &p,const int e) {
    Node* w = p.v;
    Node* u = w->prev;
    Node* v = new Node;
    v->e = e;

    v->next = w;
    w->prev = v;
    v->prev = u;
    u->next = v;
    this->n++;
}

void insertFront(const int e) { insert(begin(),e); }

void insertBack(const int e) {}

void erase(const Iterator &p) {
    if(size() == 0)
        cout<<"Empty\n";
    else {
        Node* v = p.v;
        Node* w = v->next;
        Node* u = v->prev;

        u->next = w;
        w->prev = u;

        delete v;
        this->n--;
    }
}

void eraseFront() {}

void eraseBack() { erase(--end()); }

Iterator atIndex(int i) const {
    Iterator p = begin();
    for(int j=0; j<i; j++) {
        ++p;
    }
    return p;
}

int indexOf(const Iterator& p) const {
    Iterator q = begin();
    int j = 0;
    while(q != p) {
        ++q;
        ++j;
    }
    return j;
}

 

Sequence se;
Iterator iter;
int data;

se.insert(iter,data);

se.erase(iter);

iter = se.begin();

iter = se.end();

++iter;

--iter;

 

8. Tree (based vector)

class Node {
public:
    int data; //값
    Node* parent; //부모
    vector<Node*> child_vector; //자식 노드들 벡터

 

void setParent(Node* parent) {}
    
void insertChild(Node* child) {}
    
void deleteChild(Node* child) {
    child_vector.erase(child_vector.begin() + i);
}

 

class Tree {
public:
    Node* root; //최상단 루트노드
    vector<Node*> tree; //트리 전체노드저장을 위한 벡터

 

int size() {}
    
void insertNode(int parent, int data) {}
    
void deleteNode(int data) {
    if(tree[i] == root)
        return;
    Node* target = tree[i];
    Node* parent = tree[i]->parent;
    for(Node*& child : target->child_vector) {
        parent->insertChild(child);
        child->setParent(parent);
    }
    
    parent->deleteChild(target);
    tree.erase(tree.begin()+i);
    delete target;
    return;
}

void postorder(Node* p) {
    for(Node*& child : p->child_vector) {
        postorder(child);
    }
    cout<<p->data<<" ";
}

void preorder(Node* p) {
    cout<<p->data<<" ";
    for(Node*& child : p->child_vector) {
        preorder(child);
    }
}

int printDepth(Node* p) {
    if(p == root)
        return 0;
    return 1+printDepth(p->parent);
}