본문 바로가기

C++87

C++ 기초 : tree (2) 이진 트리도 종류가 있습니다. '완전 이진 트리'라는 것인데요.자식 노드를 반드시 2개씩 모두 채워 나가는 트리입니다.  완전 이진 트리는 배열로 구현을 합니다. 아래 그림을 통해 완전 이진 트리를어떻게 배열로 구현하는지 살펴 봅시다. 위와 같은 완전 이진 트리가 있습니다. 1번 노드는 해당 트리에서 루트 노드이며2번과 3번 노드를 자식 노드를 데리고 있습니다. 2번 노드는 4와 5번을 자식 노드로,3번 노드는 6과 7번을 자식 노드로 데리고 있습니다.  1번 노드를 배열의 0번 인덱스에 넣습니다. 이 상태에서 자식 노드인 2번 노드를 넣으려고 합니다. 첫 번째 자식 노드의 자리는 2k + 1입니다.여기서 k는 부모 노드가 있는 인덱스 번호이죠. 두 번째 자식 노드의 자리는 2k + 2입니다. 즉 1번 .. 2024. 4. 26.
C++ 기초 : tree (1) list는 노드를 관리합니다. 노드를 vertex(정점)라고 부르기도 합니다. 이러한 노드 간의 연결 관계를 표현할 수 있으면이것은 그래프입니다. 예를 들어 지하철 노선 같은 경우도그래프라고 볼 수 있죠.    아래 그림을 보시죠. 그래프의 연결 관계를 봤을 때처음 노드에서 한 바퀴를 돌아다시 처음 노드로 돌아올 수 있다면이를 순환(Circuit, Cycle) 가능하다고 표현합니다.  그러나 트리는 아래 그림처럼 이러한 순회가 불가능한 그래프입니다. 연결 관계를 보면 맨 아래 노드에서처음 노드로 갈 방법이 없죠?    그래프(Graph)와 트리(Tree)는 모두 자료 구조이며,트리는 그래프의 일종입니다. 포함 관계를 그림으로 표현하자면 위 그림과 같죠.  트리는 부모 노드와 자식 노드를 연결한 구조로가족.. 2024. 4. 26.
C++ 기초 : inline 함수를 선언하고 정의를 하기 위해Ctrl + . 을 통해 정의 부분을 만들면'inline'이라는 키워드가 붙습니다. 이게 무슨 의미일까요? 함수 A(){  ...  함수 B();  ...} 자, 위와 같은 함수가 있습니다. 함수 A를 호출하면 쭉 코드가 실행되다가함수 B 호출 구문을 만나 Stack 영역에 함수 B를 호출하고여기서 함수 B를 실행한 뒤 반환하고다시 함수 A로 돌아와 남은 코드를 실행하고 함수 A가 종료될 것입니다. 근데 만약 함수 B 앞에 inline 키워드를 붙이면함수 B를 호출했을 때 함수 B로 점프하여 실행하지 않고함수 A 코드에 함수 B 코드를 붙여넣고 함수 A를 실행하면서 그대로 실행합니다.즉 실제로 함수 B를 호출하는 구문이 없다고 봐도 되는 거죠.  이러한 경우 함수 B 호출.. 2024. 4. 26.
C++ 기초 : list iterator 직접 구현한 list 클래스에도iterator를 구현하겠습니다. 일단 list 역할은 하는 cList 클래스에inner 클래스인 iterator를 만듭니다. list에서 iterator가 갖고 있어야 하는 정보는어떤 list가 관리하는 노드인가,즉 list의 주솟값을 알아야 하고어떤 노드를 가리킬 것인가즉 node의 주솟값을 알아야 합니다. 해당 iterator가 사용할 수 있는지,사용할 수 없는지 확인할 수 있는멤버 bValid도 만들었습니다.  이후 iterator의 생성자와 소멸자를 만듭니다. 기본 생성자는 list를 가리키는 m_pList와 노드를 가리키는 m_pNode의 값을 이니셜라이저를 통해nullptr로 초기화합니다. 이렇게 만들어진 iterator는 사용할 수 없는 iterator이므로 .. 2024. 4. 25.
C++ 기초 : erase (2) erase 함수를 구체적으로 작성하겠습니다. 아래 코드를 보시죠. 235번째 줄 if 문에 조건이 하나 더 추가되었습니다. vector의 데이터 개수를 나타내는멤버 m_iCount의 값보다 iterator의 인덱스 값이 크거나 같을 때도오류 창이 출력됩니다. 만약 vector의 데이터 개수가 3개인데 3번째 인덱스 또는 그 이상의 인덱스에 접근하면 오류로 인지하는 거죠.  242 ~ 247번째 줄은 vector의 데이터가 복사되는 과정입니다.빈 공간이 생기면 뒤에 있는 데이터로 빈 공간을 채워 주는 거죠. 여기서 생각을 조금 해 보면,만약 3개의 데이터가 있고 0번째 인덱스 공간을 제거했습니다.그러면 1번째 인덱스의 값이 0번째 인덱스로 복사되고,2번째 인덱스의 값이 1.. 2024. 4. 24.
C++ 기초 : erase (1) 이제 erase 함수를 구현해 볼 건데erase 함수가 어떤 역할을 하는지 알아야겠죠? 아래 코드를 보시면 표준 라이브러리에서 제공하는 vector를 통해 가변 배열을 만들었고 해당 가변 배열에는 10과 20이 차례대로 들어 있습니다. 그리고 10이 있는 공간을 iteraor를 통해가리키고 있죠. vector의 멤버 함수 erase를 통해iterator가 가리키는 공간을 제거합니다.즉 첫 번째 공간을 제거하는 것이죠. 가변 배열은 중간에 빈 공간을 두면안됩니다. 그래서 첫 번째 공간을 다음 데이터가 메꾸게 되죠. 위 같은 경우에는 10이 제거되어 첫 번째 공간을20으로 메꾸게 되겠죠.  그러면 iterator는 자연스럽게 20을 가리키게 되겠고iterator.. 2024. 4. 24.

티스토리툴바