휴지통/자료구조-C

배열을 기반으로 힙을 구현하는데 필요한 지식들 "노드에 고유의 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다." 위 그림에서 보이듯이 , 구현의 편의를 위해서 인덱스가 0인 위치의 배열 요소는 사용하지 않는다는 사실도 앞서 언급하였다. 그럼 배열을 기반으로 힙을 구현하기 위해서 무엇을 더 알아야 할까? "왼쪽 그리고 오른쪽 자식 노드의 인덱스 값을 얻는 방법, 그리고 부모 노드의 인덱스 값을얻는 방법" 자식 노드의 인덱스 값을 얻는 방법은 데이터의 삭제를 위해서, 부모 노드의 인덱스 값을 얻는 방법은 데이터의 추가를 위해서 필요하다. 그럼 이 두가지 방법을 소개하겠다. 왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2 오른쪽 자식 노드의 인덱스 값 ..

우선순위 큐의 이해 우선순위 큐는 그 이름이 의미하듯이 큐와 관련이 있다. 하지만 공부하다 보면 그 관계가 깊지 않다고 느낄수도 있다. 제목만 봐서는 앞서 구현한 '큐'를 확장하는 수준에서 마무리가 될것 같지만 '큐'의 구현과 우선순위 큐'의 구현에는 많은 차이가 있기 때문이다. 우선순위 큐와 우선순위의 이해 큐의 핵심연산 두 가지는 다음과 같다. enqueue : 큐에 데이터를 삽입하는 행위 dequeue : 큐에서 데이터를 꺼내는 행위 이와 마찬가지로 '우선순위 큐'의 핵심 연산 두 가지도 다음과 같다. enqueue : 우선순위 큐에 데이터를 삽입하는 행위 dequeue : 우선순위 큐에서 데이터를 꺼내는 행위 반면 연산의 결과에는 차이가 있다. 큐는 연산의 결과로, 먼저 들어간 데이터가 먼저 나오..

이진 트리의 순회(Traversal) 앞서 이진 트리의 순회가 필요한 이유를 설명했으니, 바로 이어서 트리의 순회 방법을 설명하겠다. 참고로 순호의 방법 또한 재귀적이다. 순회의 세가지 방법 이진 트리를 대상으로 하는 대표적인 순회의 세 가지 방법은 다음과 같다. 전위 순회(Preorder Traversal) : 루트 노드를 먼저 중위 순회(Inorder Traversal) : 루트 노드를 중간에 후위 순회(Postorder Traversal) : 루트 노드를 마지막에 이렇듯 이진 트리를 순회하는 대표적인 방법은 다음 내용을 기준으로 세 가지로 나뉜다. "루트 노드를 언제 방문하느냐" 다음과 같은 순서 및 방향으로 순회할 경우 , 루트 노드는 중간에 방문이 이뤄지기 때문에 이러한 방식의 순회를 가리켜 중..

트리(Tree)의 접근 트리의 설명을 위해서 우리는 다음 사실을 알아야 한다. "트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다." 위의 문장에서 "게층적 관계"가 제일 눈에 뛸 것이다. 그런데 이에 뭇지않게 관심을 둬야 할 단어가 바로 '표현'이다. 자료구조하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인것으로 이해하는 경우가 많다. 앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 잇었기 때문이다 .하지만 자료구조는 근본적으로 무엇인가를 '표현'하는 도구이다. 표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다. 트리의 ADT를 다음과 같이 바라보면은 안된다. "데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있는가?" 대신 다음과 같..

큐를 설명하였으니, 이와 관련 있는 덱을 소개하고자 한다. 스택과 큐의 구조를 이해한 사오항에서 덱의 구조는 한줄로 설명이 가능하며, 양방향 리스트 까지 구현해본 경험이 있으면 덱의 구현을 일일히 설명할 필요는 없다. 덱의 이해와 ADT의 정의 "큐는 뒤로 넣고 앞으로 빼는 자료구조" 이러한 느낌으로 덱을 한 문장으로 설명하면 다음과 같다. "덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄수 있는 자료구조" 이것으로 덱의 구조는 충분히 설명되었다고 생각한다. dequeue은 double -ended queue 를 줄여서 표현한 것으로, 양방향으로 넣고 뺄수 있다는 사실에 초점이 맞춰져서 지어진 이름이다. 어쨋든 덱은 한방향으로 넣고, 양방향으로 뺄 수 있는 자료구조이기에 스택과 큐의 특성을 모두..

배열을 기반으로 큐를 구현하는 경우 몇가지 고려할 사항이 있었다. 그래서 원형 큐를 소개했고, 또 큐가 꽉 찬 경우와 텅 빈 경우를 구분하는 방법도 소개하였다. 하지만 연결리스트를 기반으로 구현하는 경우에는 의외로 신경 쓸 부분이 적다. 연결 리스트 기반 큐의 헤더파일 정의 "스택과 큐의 유일한 차이점은 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니 ,이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될꺼같다" 위의 판단은 배열 기반에서는 옳지 않았지만, 연결리스트 기반의 큐라면, 위의 판단은 어느 정도 옳다. 연결리스트를 기반으로 구현하면 앞서 논의한 고민거리들이 사라지기 때문이다. 하지만 다음과 같은 차이점이 있기 때문에 여전히 스택의 구현과는 차이가 있다고 말할 수 있다. "스택은 p..