컴퓨터과학

    C언어로 자료구조 만들기 - 트리(BST, Binary Search Tree)

    이번에는 나를 가장 화나게 했던 트리를 만들어보고자 한다. 무슨 욕심으로 트리까지 만들려고 했는지는 모르겠지만, 어쨌거나 구현은 어느정도 되었으니까 다행이다. 여러 번 포기할 뻔 했다. 다른 부분보다도 특히 트리의 삭제부분에서 큰 문제를 겪었기 때문에 이번 포스트는 다소 화가 섞여있을지도 모른다. 트리(Tree) 구현해두었던 트리는 이진 탐색 트리(BST, Binary Search Tree)다. 이진 트리이므로 자식을 두 개씩 가질 수 있다. BST 의 경우, 부모 노드를 기준으로 값이 큰 것은 오른쪽에, 값이 작은 것은 왼쪽에 자리한다. Tree 트리는 일단 기본적으로 루트 노드가 필요하기 때문에 루트 노드 만큼은 구조체 안에다가 넣어두자. 그런데 아래의 코드 에서 _searchStack 은 어디에 쓰..

    C언어로 자료구조 만들기 - 큐(Queue), 스택(Stack)

    자, 지난 포스트에서 구현한 링크드 리스트를 기반으로 큐, 스택을 만들어보자. 링크드 리스트에서 대부분 구현이 되었기 때문에 설명할 내용은 많이 없다. 큐와 스택 둘 다 순회는 지원하지 않을 것이며 검색도 지원하지 않고 삽입과 삭제에 대한 것만이 존재한다. https://pronist.tistory.com/76 C언어로 자료구조 만들기 - 링크드 리스트(Linked List) 이번에는 지난 포스트에 이어서 C언어로 자료구조를 구현해볼 텐데, 이번에는 링크드 리스트다. 양 옆으로 삽입과 삭제가 가능한 양방향 링크드 리스트를 구현하고, 또한 중간에 데이터를 삽입 pronist.tistory.com 큐(Queue) 큐는 FIFO(First In First Out) 구조를 가지며 가장 먼저 삽입된 데이터가 나올..

    C언어로 자료구조 만들기 - 링크드 리스트(Linked List)

    이번에는 지난 포스트에 이어서 C언어로 자료구조를 구현해볼 텐데, 이번에는 링크드 리스트다. 양 옆으로 삽입과 삭제가 가능한 양방향 링크드 리스트를 구현하고, 또한 중간에 데이터를 삽입과 삭제가 가능하도록 만든다. 링크드 리스트(Linked List) 링크드 리스트는 정적 배열과 데크와는 다르게 주소값을 서로 연결하여 구성되어 있다. 따라서 메모리 공간이 연속으로 구성되어 있지는 않으며 독립적으로 구성하되, 대신 다음과 이전 주소를 노드에 저장하여 다음 노드와 이전 노드에 접근할 수 있도록 논리적으로 연결된 구조로 표현한다. Node.h 링크드 리스트에는 노드가 필요하다. 배열처럼 인덱싱을 통해 바로 값을 넣지 않는다. 노드에는 값, 이전 노드의 주소값, 다음 노드의 주소값이 들어가며 이는 구조체로 표현..

    C언어로 자료구조 만들기 - 정적 배열(Fixed Array), 데크(Deque)

    C언어로 자료구조를 만들어보는 것은 내가 예전에 했던 것인데, 부득이하게도 포트폴리오로써는 존재하지 않고 있기 때문에 늦었지만 다시 써보기로 했다. 이는 정보처리기사를 준비할 적에 만들어둔 코드인데, 어쩌다보니 자료구조까지 만들어버린 것이다. 만든 자료구조는 정적 배열, 데크, 링크드 리스트, 큐, 스택, 트리다. 정적 배열(Fixed Array) 정적 배열은 C언어에서 문법적으로 제공하는 기능이지만, 별도로 구조체, 함수를 이용하여 구현해보기로 했다. 물론 내부적으로 사용하는 것은 결국 기본 배열이지만 말이다. 배열은 연속된 메모리 공간이다. 따라서 가장 처음의 메모리 주소만 알고있더라도 다른 원소에 접근할 수 있다. 그래서 함수에서 배열을 받을 때 포인터로 받을 수 있는 것이다. 배열을 그림으로 표현..