2018학년도 자료구조 실습시험 예제 문제(연결리스트(Chain list) && 원형 큐(round queue) && 트리(Tree || Binary Tree) && 스택(Stack) && 이중 연결 리스트(Double Linked LIst))

중간고사와 기말고사 사이에 실습고사를 진행했다. 그 이전에, 교수님께서는 우리에게 예제 문제를 주셨는데, 그걸 받은 덕분에 지금까지 배웠던 여러가지 자료구조를 구현할 수 있었다.

/*연결 리스트*/

#include <iostream>
#include <string>
using namespace std;
class Node
{
    friend class Chain;
private:
    int data;
    Node *link;
public:
    Node(int value = NULL, Node *next = NULL);
};

class Chain
{
private:
    Node *first, *last,*cur;
    int HowMany;
public:
    Chain();
    void MakeChainNode(int value);
    void MakeChainFromLine(int len);
    void Reverse();
};

Node::Node(int value, Node *next)
{
    data = value;
    this->link = next;
}

void Chain::Reverse()
{
    Node *cur;
    Node *tail=NULL;
    while(first!=NULL)
    {
        cur = first->link;
        first->link =tail;
        tail = first;
        first = cur;
    }
    tail = tail->link;
    while(tail != NULL)
    {
        printf("%d ",tail->data);
        tail = tail->link;
    }
    cout<<endl;
}

Chain::Chain()
{
    first = NULL;
    last = NULL;

}

void Chain::MakeChainNode(int value)
{
    if(first == NULL)
    {
        last = new Node(0,NULL); first = new Node(value, last),cur = first;
    }
    else
    {
        Node *temp;
        last->data = value;
        temp = new Node(0, NULL);
        last->link = temp;
        last = temp;
    }
}
void Chain::MakeChainFromLine(int len)
{
    HowMany = len;
    for(int i = 0; i < len; i++)
    {
        int c;
        scanf("%d", &c);
        MakeChainNode(c);
    }
}


int main()
{
    int TestCase, HowMany;
    scanf("%d",&TestCase);
    for(int i = 0; i < TestCase; i++)
    {
        Chain c1 = Chain();
        scanf("%d",&HowMany);
        c1.MakeChainFromLine(HowMany);
        printf("case %d\n", i+1);
        c1.Reverse();
    }

}

/*원형 큐*/

#include <iostream>
using namespace std;

class Queue
{
private:
    int *queue;
    int first;
    int rear;
    int capacity;
public:
    Queue(int HowMany);
    void append(int value);
    int pop();
    bool isFull();
    bool isEmpty();
};
bool Queue::isFull()
{
    return (rear+1)%capacity == first ? true: false;
}
bool Queue::isEmpty()
{
    return (first == rear)? true:false;
}
Queue::Queue(int HowMany)
{
    capacity = HowMany;
    first=0;
    rear=0;
    queue = new int[HowMany];
}

void Queue::append(int value)
{
    if(isFull())
    {
        cout << "Queue is Full"<<endl;
        exit(1);
    }
    else
    {
        rear = (rear+1)%capacity;
        queue[rear] = value;
    }
}
int Queue::pop()
{
    if(isEmpty()) return -1;
    first = (first+1)%capacity;
    return queue[first];
}

int main()
{
    int HowMany;
    scanf("%d",&HowMany);
    for(int i=0; i<HowMany; i++)
    {
        int cap;
        scanf("%d", &cap);
        Queue Q = Queue(cap+1);
        for(int j =0; j<cap; j++)
        {
            int va;
            scanf("%d", &va);
            Q.append(va);
        }
        printf("case %d\n", i+1);
        for(int x = 0; x<cap; x++)
        {
            printf("%d ", Q.pop());
        }
        printf("\n");
    }
    return 0;
}

이 트리 문제는 두가지로 풀었는데(출력 예시가 잘못되어 있어서)

하나는 비교 연산 없이 무작정 집어넣는(좌편향이 될 수 밖에 없는) 트리, 그리고 나머지는 비교 후 집어넣는 트리이다.

1. 좌편향 트리

#include <iostream>
using namespace std;

class Node
{
    friend class Tree;
private:
    int value;
    Node *left;
    Node *right;
public:
    Node(int val)
    {
        this->value = val;
        this->left = NULL;
        this->right = NULL;
    }
    Node(int val, Node *left, Node *right)
    {
        this->value = val;
        this->left = left;
        this->right = right;
    }
};
class Tree
{
private:
    Node *root;
public:
    Tree(){root = new Node(NULL);}
    void add(Node* root, int val);
    void preorder(Node* current);
    void MakeTree(int HowMany);
    void visit(Node* current);
    void inorder(Node* current);
    void print();
};
void Tree::add(Node* root, int val)
{
    Node *temp = new Node(val);
    if(root->left == NULL)
    {
        root->left = new Node(val);
    }
    else if(root->right == NULL)
        root->right = new Node(val);
    else
        add(root->left, val);
}

void Tree::MakeTree(int HowMany)
{
    int c;
    scanf("%d", &c);
    root->value = c;
    for(int i=0; i<HowMany-1;i++)
    {
        scanf("%d",&c);
        add(this->root,c);
    }
}

void Tree::print()
{
    preorder(this->root);
    printf("\n");
    inorder(this->root);
}

void Tree::inorder(Node* current)
{
    if(current != NULL)
    {
        inorder(current->left);
        visit(current);
        inorder(current->right);
    }
}

void Tree::preorder(Node* current)
{
    if(current != NULL)
    {
        visit(current);
        preorder(current->left);
        preorder(current->right);
    }
}
void Tree::visit(Node* current)
{
    printf("%d ", current->value);
}

int main()
{
    int TestCase;
    scanf("%d", &TestCase);
    for(int i=0; i<TestCase; i++)
    {
        int HowMany;
        Tree t1 = Tree();
        scanf("%d",&HowMany);
        t1.MakeTree(HowMany);
        printf("case %d\n", i+1);
        t1.print();
        printf("\n");
    }
    return 0;

이진 트리

#include <iostream>
using namespace std;

class Node
{
    friend class Tree;
private:
    int value;
    Node *left;
    Node *right;
public:
    Node(int val)
    {
        this->value = val;
        this->left = NULL;
        this->right = NULL;
    }
    Node(int val, Node *left, Node *right)
    {
        this->value = val;
        this->left = left;
        this->right = right;
    }
};
class Tree
{
private:
    Node *root;
public:
    Tree(){root = new Node(NULL);}
    void add(Node* root, int val);
    void preorder(Node* current);
    void inorder(Node* current);
    void MakeTree(int HowMany);
    void visit(Node* current);
    void print();
};
void Tree::add(Node* root, int val)
{
    Node *temp = new Node(val);
    if(root->value > val)
    {
        if(root->left != NULL)
        {
            add(root->left, val);
        }
        else
        {
            root -> left = new Node(val);
        }
    }
    else
    {
        if(root->right != NULL)
        {
            add(root->right, val);
        }
        else
        {
            root -> right = new Node(val);
        }
    }
}

void Tree::MakeTree(int HowMany)
{
    int c;
    scanf("%d", &c);
    root->value = c;
    for(int i=0; i<HowMany-1;i++)
    {
        scanf("%d",&c);
        add(this->root,c);
    }
}

void Tree::print()
{
    printf("preoreder\n");
    preorder(this->root);
    printf("\n");
    printf("inorder\n");
    inorder(this->root);
}

void Tree::preorder(Node* current)
{
    if(current != NULL)
    {
        visit(current);
        preorder(current->left);
        preorder(current->right);
    }
}
void Tree::inorder(Node* current)
{
    if(current != NULL)
    {
        inorder(current->left);
        visit(current);
        inorder(current->right);
    }
}
void Tree::visit(Node* current)
{
    printf("%d ", current->value);
}

int main()
{
    int TestCase;
    scanf("%d", &TestCase);
    for(int i=0; i<TestCase; i++)
    {
        int HowMany;
        Tree t1 = Tree();
        scanf("%d",&HowMany);
        t1.MakeTree(HowMany);
        printf("case %d\n", i+1);
        t1.print();
        printf("\n");
    }
    return 0;
}

배열 스택 버전과 링크드 리스트를 이용한 스택 버전을 따로 만들었다.

배열을 이용한 스택

#include <iostream>
using namespace std;

class Stack
{
private:
    int *Arr;
    int size;
    int capacity;
public:
    Stack(int HowMany);
    void push(int val);
    int pop();
};

Stack::Stack(int HowMany)
{
    Arr = new int[HowMany];
    size = 0;
    capacity=HowMany;
}

void Stack::push(int val)
{
    if(size == capacity)
    {
        int *temp = new int[capacity*2];
        while(Arr)
        {
            temp = Arr;
            temp++;
            Arr++;
        }
        *Arr = *temp;
        push(val);
    }
    Arr[size]=val;
    size++;
}

int Stack::pop()
{
    int temp = Arr[size-1];
    Arr[size-1] = 0;
    size--;
    return temp;
}

int main()
{
    int TestCase;
    scanf("%d",&TestCase);
    for(int i=0; i < TestCase; i++)
    {
        int HowMany;
        scanf("%d",&HowMany);
        Stack s1= Stack(HowMany);
        for(int j=0; j < HowMany; j++)
        {
            int c;
            scanf("%d",&c);
            s1.push(c);
        }
        printf("case %d\n", i+1);
        for(int j=0; j < HowMany; j++)
        {
            printf("%d ", s1.pop());
        }
        printf("\n");
    }
}

링크드 리스트를 이용한 스택

#include <iostream>
using namespace std;
class Node
{
    friend class Stack;
private:
    int data;
    Node* next;
public:
    Node(int val = 0, Node* pos = NULL)
    {
        data = val;
        next = pos;
    }
};
class Stack
{
private:
    Node* first;
    Node* last;
public:
    Stack()
    {
        first = NULL;
        last = NULL;
    }
    void push(int val);
    int pop();
    void PrintAll();
};

void Stack::push(int val)
{
    if(first == NULL)
    {
        first = new Node(val, last);
    }
    else
    {
        Node* tmp = new Node(val, first);
        first = tmp;
    }
}

int Stack::pop()
{
    Node* tmp = first;
    first = tmp->next;
    return tmp->data;
}

void Stack::PrintAll()
{
    Node* cur = first;
    while(cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main()
{
    int TestCase;
    scanf("%d",&TestCase);
    for(int i = 0; i<TestCase; i++)
    {
        int HowMany;
        scanf("%d",&HowMany);
        Stack s1 = Stack();
        for(int j =0; j<HowMany; j++)
        {
            int c;
            scanf("%d",&c);
            s1.push(c);
        }
        s1.PrintAll();
    }
    return 0;
}

5. 이중연결 리스트

#include <iostream>
using namespace std;

class Node
{
    friend class DoubleList;
private:
    Node* left;
    Node* right;
    int data;
public:
    Node(int value = 0, Node* Left = NULL);
};

class DoubleList
{
private:
    Node* first;
    Node* last;
public:
    DoubleList(){first = NULL; last = NULL;}
    void MakeNode(int val);
    void PrintReverse();

};

Node::Node(int value, Node* Left)
{
    data = value;
    left = Left;
    right = NULL;
}
void DoubleList::MakeNode(int value)
{
    if(first == NULL)
    {
        first = new Node(value,NULL);
        last = new Node(NULL,first);
        first->right = last;
    }
    else
    {
        Node* tmp= new Node(NULL,last);
        last->data = value;
        last->right = tmp;
        last = tmp;
    }
}


void DoubleList::PrintReverse()
{
    Node* cur = last;
    cur = cur->left;
    do
    {
        printf("%d ", cur->data);
        cur = cur->left;
    }while(cur != NULL);
    printf("\n");
}

int main()
{
    int TestData;
    scanf("%d",&TestData);
    for(int i=0; i < TestData; i++)
    {
        int HowMany;
        scanf("%d",&HowMany);
        DoubleList D1 = DoubleList();
        for(int j = 0; j < HowMany; j++)
        {
            int c;
            scanf("%d",&c);
            D1.MakeNode(c);
        }
        printf("case %d\n", i+1);
        D1.PrintReverse();
    }
    return 0;
}

뭐, 다 하기도 했고, 추가로 만들기 까지 했으니까 걱정은 없었다.

이것들이 모두 들어가 있는 소스 파일은 첨부

ForExam.cpp