프로그래밍/자료구조14 [C언어와 함께 자료구조를] 연결리스트로 큐 구현하기 큐 개념 다시 보기 큐는 줄, 대기행렬 이라는 의미가 있습니다. 줄서서 먹는 맛집은 온 순서대로 들어가게 되는 것과 같은 개념이라고 생각하시면 됩니다. 큐를 대표하는 말은 선입선출( FIFO : First In First Out)인데요, 거꾸로 생각하면 후입후출(LILO : Last In Last Out)도 틀린 말은 아닌 것 같습니다. 큐의 연산도 딱 두가지 put과 get입니다. 뭐 책에 따라서 enqueue, dequeue라는 말도 쓰이긴 하지만 의미만 통하면 별 문제는 없어 보입니다. put은 큐에 데이터를 넣는것, get은 큐에서 데이터를 가져오는 것입니다. 연결리스트로 큐 구현하기 배열을 이용한 큐에서는 큐의 크기가 정해져 있었지만, 연결리스트에서는 그런 제약조건이 없습니다. (이론상 컴이 더.. 2020. 7. 29. [C언어와 함께 자료구조를] 연결리스트로 스택 구현 스택 개념 다시보기 스택(Stack)은 단어의 뜻에서 의미하듯 쌓아 놓는 구조로 매우 간단합니다. 예를 들면, 책 10권을 차례대로 쌓았다고 하면 책을 치우기 위해서 맨 위에서 부터 차례차례 치워나가는 방식이라고 할까요? 가장 나중에 쌓은 책이 먼저에 치워지니 LIFO(First-In Last-Out)이라고도 하고 가장 먼저 쌓은 책이 나중에 치워지니 FILO(First-In Last-Out)이라고도 부를 수 있겠네요. 스택을 조작하는 연산은 딱 두가지만 기억하자고 했는데. 스택에 집어넣는 연산 push와 스택에서 빼내는 연산 pop입니다. 연결리스트로 스택 구현하기 스택의 구현은 배열을 사용하던 연결리스트(Linked list)를 사용하던 상관없지만, 이전 포스팅에서는 연결리스트를 이용한 스택을 구현해.. 2020. 7. 29. [C언어와 함께 자료구조를] 이진트리 순회 (Binary Tree Traverse) 트리(Tree)구조는 배열과 리스트 처럼 분명한 순회 순서(Traversal Order)를 갖지 않고 여러개의 순회 순서를 정의 할 수 있습니다. 트리(Tree)의 모든 노드들을 한 번씩 중복없이 순회하는 방법 4가지에 대해 이야기 해보려 합니다. 트리 순회하는 방법은 먼저 루트(Root)를 먼저 타는 방법 (전위 순회 : Preorder traverse), 루트를 중간에 타는 방법 (중위 순회 : Inorder Traverse), 루트를 나중에 타는 방법 (후위 순회 : Postorder Traverse), 마지막으로 층별로 타는 방법 (층별 순회 : Level order Traverse)등이 있습니다. 트리를 순회하는 방법 (앞 3가지)을 C언어로 구현하려면 재귀호출(Recursive Call)을 이.. 2020. 7. 4. [C언어와 함께 자료구조를] 트리 (Tree) - 용어 정리와 이진트리 지금까지 다뤄본 자료구조들을 모두 선형적인 일차원 구조였습니다. 즉, 처음부터 끝까지 차례로 이동하면 모든 노드를 거칠 수 있었죠. 하지만 트리(Tree)는 대표적인 비선형구조(Non-linear structure)로 2차원구조 입니다. 트리(Tree) 구조는 일상에서도 많이 볼 수 있는데요, 대표적으로 탐색기 폴더구조를 들 수 있습니다. 로컬디스크(C:)에 여러 폴더들이 존재하고 그 하위 폴더 그 아래 하위 폴더 등으로 구성되는 구조입니다. 트리(Tree) 구조는 나무를 거꾸로 뒤집어 놓은 것 같은 모양입니다. 가장 위에 있는 노드를 root라 하고 거기서 시작하여 가지 (link)가 밑으로 향하며 맨 아래에 잎(leaf)이 달려 있습니다. 위 그림을 가지고 트리(Tree)구조에서 일반적으로 사용하는 .. 2020. 7. 3. [C언어와 함께 자료구조를] 환형연결리스트 (Circular Linked List) 환형연결리스트(또는 원형연결리스트 Circular Linked List)는 단순연결리스트(Simple Linked List)의 Tail노드가 Head노드를 가리키고 있는 구조로 머리가 꼬리를 문 뱀모양의 둥근 모양을 하고 있습니다. 환형연결리스트의 연산은 단순연결리스트의 것과 비슷합니다. 다른 것은 환형연결리스트는 Tail이라는 개념이 없다는 것 뿐입니다. 해결하려는 문제에 따라 자연스럽게 환형연결리스트를 사용해야 되는 경우가 있습니다. 예를들어, 어떤 다각형의 변은 그 자체로 하나의 루프를 형성하므로 다각형의 꼭지점을 환형리스트의 노드로 표현하는것이 적절한 방법입니다. 여기서는 환형연결리스트의 대표적인 "요셉의 문제"를 코드로 알아보도록 하겠습니다. "요셉의 문제"는 A부터 J까지의 10명의 사람이 시.. 2018. 11. 20. [C언어와 함께 자료구조를] 연결리스트 (Linked List) - 개념과 구현 지난 시간에는 스택과 큐의 개념과 배열로 각각 구현을 해봤습니다. 이번에 살펴 볼 연결리스트(Linked List)는 정적인 배열과 달리 동적인 자료구조로 필요한 경우 할당하여 사용하고 필요가 없어지면 해제하는 식으로 메모리 관리가 가능하기 때문에 메모리를 절약할 수 있다는 장점이 있습니다. 연결리스트(링크드리스트 : Linked List)의 개념 연결리스트는 노드(Node)와 링크(Link)로 구성되며, 노드는 실제 정보를 담고 있는 하나의 단위이고, 링크는 노드간의 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리로 이해 하시면 됩니다. 연결리스트는 각 노드별 링크의 개수와 연결 상태에 따라 다양한 형태로 구성 될 수 있는데요. 단순 연결리스트, 환형 연결리스트, 이중 연결.. 2018. 11. 20. 이전 1 2 3 다음
