피보나치 수열, 하노이 탑, 링크드리스트, 배열형 스택

작성 언어 : C++

 

[피보나치 수열]

 

#include <iostream>

using namespace std;

void Fibonacci(int first, int second)
{
    int temp1 = second;
    int temp2 = first + second;
    cout << temp1 << endl;
    
     Fibonacci(temp1, temp2);  
}

int main()
{
    Fibonacci(0,1);

    return 0;
}

 

[하노이탑]

참고 코드 : https://velog.io/@k_gu_wae123/C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-11729%EB%B2%88-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9C

#include <iostream>

using namespace std;


void Hanoi(int n, int a, int b, int c) {
	if (n == 1) {
        cout << a << c << endl;
		return;
	}
	else {
		Hanoi(n - 1, a, c, b);
        cout << a << c << endl;
		Hanoi(n - 1, b, a, c);
	}

}

int main() {
	int N = 3;

	Hanoi(N, 1, 2, 3);
	
	return 0;
}

 

 

[링크드리스트]

 

#include <iostream>

using namespace std;

class Node
{
public:
    int value;
    Node* prev;
    Node* next;

    Node()
    {
        value = 0;
        next = nullptr;
    }
};


class LinkedList
{
private:
    Node* head = nullptr;
    Node* tail = nullptr;
    int size = 0;
public:
    bool IsEmpty();
    void AddNode(int value); 
    void AddNode(int value, int position);
    void RemoveNode(int value);
    int SearchValue(int value);
    void Show();
    int GetSize();
};

bool LinkedList::IsEmpty()
{
    return (head == nullptr);
}

void LinkedList::AddNode(int value)
{
    Node* newNode = new Node;
    newNode->value = value;
    size++;

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

void LinkedList::RemoveNode(int value)
{
    Node* currentNode = new Node;
    currentNode = head;

    while(currentNode != nullptr)
    {
        if(currentNode->value == value && currentNode != head)
        {
            currentNode->prev->next = currentNode->next;
        }
        currentNode = currentNode->next;
    }
}

//지정해 준 위치에 추가
void LinkedList::AddNode(int value, int position) 
{
    Node* newNode = new Node;
    newNode->value = value;
    size++;

    if(position == 0){
        newNode->next = head;
        head = newNode;
    }
    else
    {
        Node* currentNode = head;
        for(int i=0;i<position-1;i++){ //newNode가 n번째가 되려면 currentNode는 n-1번째가 되어야 함
            currentNode = currentNode->next;
        }
        newNode->next = currentNode->next;
        currentNode->next = newNode;
    }
}

//리스트에 존재하는 모든 값들을 출력하는 함수
void LinkedList::Show()
{
    Node* currentNode = head;

    while(currentNode != nullptr)
    {
        cout << currentNode->value << endl;
        currentNode = currentNode->next;
    }
}

//해당 value를 찾아서 그 노드를 지워주는 함수
void LinkedList::RemoveNode(int value) 
{
    Node* currentNode = head;
    Node* prevNode = head;

    while(currentNode != nullptr)//currentNode->next != nullptr로 걸면 안되는 이유는 하단에.
    {
        //찾는 요소가 0번째에 있을 때
        if(currentNode == head && currentNode->value == value)
        {
            head = currentNode->next;
            delete currentNode;
            size--;
            currentNode = head;
            continue;
        }

        prevNode = currentNode;
        currentNode = currentNode->next;

        //이거로 currentNode->next가 null일 경우 탈출시켜줌
        if(currentNode == nullptr) 
            break;

        if(currentNode->value == value)
        {
            prevNode->next = currentNode->next;
            delete currentNode;
            size--;
            currentNode = prevNode->next; 
            //이 단계에서 currentNode가 nullptr이 될 수 있기에 while 조건을 currentNode != nullptr로 걸어야 한다.
        }
    }
};

//해당 value를 찾아서 그 위치를 반환해주는 함수
int LinkedList::SearchValue(int value)
{
    Node* currentNode = head;
    int posValue = 0;

    while(currentNode != nullptr)
    {
        if(currentNode->value == value)
            return posValue;

        currentNode = currentNode->next;
        posValue++;   
    }
}

int LinkedList::GetSize()
{
    int sizeValue = 0;
    Node* currentNode = head;
    while(currentNode != nullptr)
    {
        currentNode = currentNode->next;
        sizeValue++;
    }
    return sizeValue;
}

 

[배열형 스택]

참고 코드 : https://songyeongkim.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F

#include <iostream>
#define stack_size 100
using namespace std;
 
struct stack {
    int top = -1;
    int arr[stack_size];
    void push(int data) {
        if (top == stack_size-1) {
            cout << "full" << endl;
            return;
        }
        arr[++top] = data;
    }
    int pop() {
        if (empty()) {
        	cout << "empty" << endl;
            return -1;
        }
        return arr[top--];
    }
    int peek() {
        if (empty()) {
            cout << "empty" << endl;
            return -1;
        }
        return arr[top];
    }
    bool empty() {
        return top <= -1;
    }
};