반응형 [C Data structure] C 자료 구조8 [C] 자료구조 - 기본 트리(LCRS Tree - LeftChildRightSibling Tree) 스택과 큐는 데이터의 삽입과 삭제를 한 쪽에서만 한다는 단점을 가지고 있습니다. 양쪽 방향에서 하면 더 효율적이지 않을까요 스택과 큐에서 정했던 Front와 Rear에 모두 데이터의 삽입과 삭제를 해주는 자료 구조가 바로 덱입니다. LCRS 트리 구조체 만들었던 자료 구조들은 모두 노드를 통해 데이터를 처리했습니다. 트리도 마찬가지로 노드와 간선으로 구성되므로 노드 구조체를 만들어 줍니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 // 트리 데이터 타입 정의 typedef char ElementType; // 트리 노드 구조체 typedef struct LCRSNode { // 왼쪽 자식 노드를 가리키는 포인터 struct LCRSNode* LeftChild; // 오른쪽 형제 노드를 .. 2023. 11. 17. [C] 자료구조 - 연결 리스트 큐 (Linked List Queue) 배열로 작성한 원형 큐는 한 번에 용량을 받아서 생성합니다. 아무리 큐의 Rear와 Front가 연결되어 있다고 해도 큐가 다 차는 경우에는 크기를 변경할 수 없다는 단점을 가지고 있습니다. 큐의 용량의 제한 없이 동적으로 생성할 수 있는 연결 리스트로 구현하는 큐가 필요합니다. 연결 리스트 큐 구조체 데이터를 저장하고 관리하기 위한 노드 구조체를 만듭니다. 1 2 3 4 5 6 7 8 9 // 큐 데이터 타입 정의 typedef int ElementType; // 연결 리스트 큐 노드 구조체 typedef struct Node { ElementType Data; struct Node* NextNode; } Node; 연결 리스트를 사용한 큐는 다음 노드를 가리킬 포인터가 필요합니다. 작성한 노드 구조체.. 2023. 11. 15. [C] 자료구조 - 원형 큐 (Circular Queue) 배열로 만든 선형 큐는 데이터가 나오는 Front가 마지막의 인덱스에 도달할 경우 앞에 데이터를 넣을 수 있지만, 큐가 가득 찼다고 판단합니다. ㅁㅁㅁㅁFront 이런 문제를 해결하기 위해서 배열의 처음과 끝을 연결하면, Rear가 배열의 앞으로 변경되어 데이터를 넣을 수 있습니다. 또한 미리 할당한 메모리만 사용하기 때문에 관리가 간편하며, 동적 할당과 해제에 필요한 오버헤드가 없어집니다. 원형 큐 구조체 데이터를 저장하고 관리하기 위한 노드 구조체를 만듭니다. 1 2 3 4 5 // 노드 구조체 typedef struct Node { ElementType Data; } Node; 배열을 사용한 원형 큐이기 때문에 연결 리스트처럼 다음 노드를 가리킬 포인터가 필요없습니다. 이제 노드를 만들었고 원형 큐.. 2023. 11. 13. [C] 자료구조 - 연결 리스트 스택 (Linked List Stack) 구현한 배열 스택(Array Stack)은 자유 저장소에 동적으로 생성되지만, 한 번에 용량을 전달 받아서 생성하게 됩니다. 전달 받은 용량만큼 스택을 사용할 수 있고, 배열인만큼 크기를 변경할 수 없다는 단점을 가지고 있습니다. 링크드 리스트는 배열의 크기 고정에 대한 단점을 보안합니다. 배열 스택의 단점을 보안하기 위해 연결 리스트를 사용한 링크드 리스트 스택을 구현합니다. 연결 리스트 스택 구조체 배열 스택과 다르게 연결 리스트 스택은 인덱스로 접근하지 않고 노드안의 포인터를 사용합니다. 연결 리스트처럼 스택의 노드 구조체 안에 다음 노드를 가리킬 Next 포인터를 만들어줍니다. 1 2 3 4 5 6 // 스택의 노드 구조체 typedef struct Node { ElementType Data; s.. 2023. 11. 12. [C] 자료구조 - 배열 스택 (Array Stack) 이번 주제는 스택(Stack)입니다. 스택은 선입후출(First In Last Out)의 구조로 먼저 들어간 데이터보다 나중에 들어간 데이터가 먼저 나오는 자료구조입니다. 뒤로 가기와 앞으로 가기의 기능 구현 등을 포함한 우리가 사용하고 있는 여러 프로그램에서 볼 수 있습니다. 스택은 배열과 링크드 리스트로 구현 가능 합니다. 그 중에서 배열은 구현이 쉽다는 장점과 용량을 동적으로 할당할 수 없다는 단점을 가지고 있습니다. 배열 스택 구조체 이전에 구현했던 자료들처럼 스택을 구성하는 노드들을 만듭니다. 1 2 3 4 5 // AS 노드 typedef struct Node { ElementType Data; } Node; 배열 스택을 구성하는 노드 구조체입니다. 연결 리스트처럼 다음 노드의 위치를 저장할 .. 2023. 11. 9. [C] 자료구조 - 원형 연결 리스트(Circular Linked List - CLL) 단일 연결 리스트와 이중 연결 리스트는 원형 연결 리스트는 연결 리스트에서 Tail이 Head를 가리키는 데이터 구조입니다. Head와 Tail의 이동이 간단하고, 다시 탐색할 필요가 없습니다. 노드들이 고리처럼 연결되어 있어 무한 루프를 사용해서 반복적으로 순회할 수 있습니다. 따라서 순환과 반복 작업의 무한 스크롤 인터페이스 등에서 사용할 수 있습니다. 이중 연결 리스트의 노드 구체의 수정없이 구현할 수 있습니다. 단일에서 이중 연결 리스트로 구현에서는 이전 노드의 주소를 저장하고 있는 포인터를 추가했지만, 원형 연결 리스트는 단순히 Head의 Prev 포인터가 NULL이 아니라, Tail을 가리키면 됩니다. 물론 Tail의 Next 포인터는 Head를 가리키면 됩니다. 원형 연결 리스트의 연산 자료.. 2023. 10. 31. [C] 자료구조 - 이중 연결 리스트(Doubly Linked List - DLL) 단일 연결 리스트는 다음 노드를 가리키는 포인터가 1개입니다. 특정 노드를 찾기 위해서 Head부터 Tail까지 순차적으로 탐색해야 한다는 단점이 있습니다. 따라서 현재 노드에서 이전 노드로 돌아갈 수 없고 다시 Head부터 탐색이 필요합니다. 이중 연결 리스트는 노드를 가리키는 포인터를 1개 추가하여 탐색을 보안하였습니다. 다음 노드를 가리키는 포인터뿐만 아니라 이전 노드를 가리키는 포인터를 추가하는 방법입니다. 1 2 3 4 5 6 typedef struct tagNode { int Data; struct tagNode* PrevNode; struct tagNode* NextNode; } Node; ▲ 이전 노드를 가리키는 포인터 변수를 추가해줍니다. 이중 연결 리스트의 연산 자료구조를 사용할 때는 .. 2023. 10. 30. [C] 자료구조 - 단일 링크드 리스트(Single Linked List - SLL) C언어에서는 배열은 크기의 고정으로 유연하게 변경할 수 없다는 단점이 있습니다. 이를 해결하기 위해 리스트의 자료구조를 사용합니다. 리스트는 스택, 큐 등의 자료 구조를 구현에 사용됩니다. 링크드 리스트(Linked List) 링크드 리스트는 각 노드의 연결로 구성되어 있습니다. 노드는 데이터를 보관하는 필드와 다음 노드를 연결해줄 포인터로 구성됩니다. ▲ 단일 노드의 구성 노드를 여러 개를 만들고 포인터에 다음 노드에 대한 포인터를 사용하면 연결 리스트가 됩니다. 연결 리스트의 맨 앞 노드는 Head이고, 마지막 노드는Tail입니다. ▲ 연결 리스트의 구성 이렇게 노드를 통해 연결을 해주면, 필요할 경우 새 노드를 만들어서 연결해주면 됩니다. 구현 그럼 C 언어로 노드를 표현해봅시다! 1 2 3 4 5.. 2023. 10. 19. 이전 1 다음 반응형
