/ C

자료구조 정복하기 with C++ (6)Chain 연결리스트

자료구조 정복하기 with C++ (6)Chain 연결리스트

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 자료구조는 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 자료구조를 코딩하면서 공부하기로 했습니다.

Chain 연결리스트

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됩니다.

Chain 연결리스트 기능

연결리스트의 기능은 다음과 같습니다.

  1. 체인에 아이템 입력
  2. 체인 붙이기(concat)
  3. 체인 역순으로 바꾸기

Chain

Chain.h

Chain의 헤더파일

#pragma once
#include <iostream>

using namespace std;

template <class T> class Chain; // forward declaration

template <class T>
class ChainNode {
    friend class Chain<T>;
public:
    ChainNode(T element) { data = element; };

private:
    T data;
    ChainNode<T>* link;
};

template <class T>
class Chain {
public:
    Chain() { first = 0; }; 			// 0으로 시작하는 생성자
   
    void InsertBack(const T& e);		//노드 삽입
    void Concatenate(Chain<T>& b);		//연결리스트 붙이기
    void Reverse();						//연결리스트 역순으로 변환
    void print();						//연결리스트 출력

private:
    ChainNode<T>* first;
    ChainNode<T>* last;
};

Chain.cpp

Chain 소스코드

#include "Chain.h"
#include <iostream>

using namespace std;

template <class T>
void Chain<T>::InsertBack(const T& e)
{
    if (first) {// nonempty chain
        last->link = new ChainNode<T>(e);
        last = last->link;
    }
    else first = last = new ChainNode<T>(e);
}

template <class T>
void Chain<T>::Concatenate(Chain<T>& b)
{// b is concatenated to the end of *this.
    if (first) { last->link = b.first; last = b.last; }
    else { first = b.first; last = b.last; }
    b.first = b.last = 0;
}

template <class T>
void Chain<T>::Reverse()
{// A chain is reversed so that (a sub 1 , ... , a sub n) becomes (a sub n ,  ... ,a sub 1).
    ChainNode<T>* current = first, * previous = 0;  // previous trails current
    while (current) {
        ChainNode<T>* r = previous;
        previous = current;               // r trails previous
        current = current->link;  // current moves to next node
        previous->link = r;  // link previous to preceding node
    }
    first = previous;
}

template <class T>
void Chain<T>::print() 
{
    ChainNode<T>* current = first;

    while (current->link != NULL) 
    {
        cout << current->data << " ";
        current = current->link;
    }
    cout << current->data << " ";
}

결과

main.cpp

#include "Chain.h"
#include <iostream>

using namespace std;

int main() {
	
	Chain<int> a;
	Chain<int> b;
	
	//a 체인에 1, 2, 5 입력
	a.InsertBack(1);
	a.InsertBack(2);
	a.InsertBack(5);
	a.print();

	//b 체인에 3, 4 입력
	b.InsertBack(3);
	b.InsertBack(4);
	b.print();

	//a에 b 붙이기
	a.Concatenate(b);
	a.print();

	//a 리버스
	a.Reverse();
	a.print();
	

	return 0;
}

후위 표기식 계산기를 구현했습니다. 결과가 잘 나옵니다!