휴지통/자료구조-C18 큐(Queue) 큐는 앞서 설명한 스택과 함께 언급되고 또 비교되는 자료구조이다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이것이 스택과 큐의 유일한 차이점이다. 큐(Queue)에 대한 이해 큐의 이해를 위해서 별도의 예는 필요하지 않다. 큐는 우리에게 매우 익숙한 자료구조 이기 때문이다. 예를들어 대중교통이나 패스트푸드점에서 주문을 할 때 줄을 섰던걸 생각해보면 된다. 즉 줄을 섰던게 큐의 구성이랑 같기 때문이다. 이렇듯 큐는 선입선출 구조의 자료구조이다. 때문에 'FIFO(First-in, First-out) 구조의 자료구조'라고 불린다. 큐의 ADT정의 스택과 마찬가지로 큐의 ADT도 정형화된 편이다. 그럼 큐의 핵심이라 할 수 있는 두가지 연산을 .. 2021. 2. 27. 스택을 활용한 계산기 구현 계산기 프로그램 구현 우리가 만들 계산기는 다음 두가지를 고려해서 연산이 가능해야 한다. 1. 소괄호를 파악하여 그 부분을 먼저 연산한다. 2. 연산자의 우선순위를 근거로 연산의 순위를 결정한다. 계산기의 구현에 필요한 알고리즘을 소개한다. 수식표기법 : 중위(infix), 전위(prefix), 후위(postfix) 표기법 계산기의 구현에 필요한 부가적인 것을 설명하기에 앞서 우리가 구현할 계산기에 대해 다음과 같이 기능을 제한한다. "수식을 이루는 피연산자는 한자리 숫자로만 이뤄진다고 가정" 즉 1과 3은 피연산자가 될 수 있지만, 24와 35는 피연산자가 될 수없다. 중위 표기법(infix notation) 5 + 2 / 7 전위 표기법(prefix notation) +5 / 2 7 후위 표기법(po.. 2021. 2. 24. 스택 이번에 소개하는 스택은 리스트와 마찬가지로 대표적인 선형 자료구조 이다. 스택을 도구를 이용해 설명을 하자면 '쌓아진 상자 더미'나 '쟁반 위에 쌓인 접시'로 비유할 수 있다. 즉 스택은 다음과 특성을 지닌다. "먼저 들어간 것이 나중에 나온다" 이렇듯 스택은 나중에 들어간 것이 먼저 나오는 구조이므로 '후입선출' 방식의 자료구조로 불리고, 영어로 'LIFO(Last-In, First-Out)구조의 자료구조'라고도 불린다. 스택의 ADT를 정의해 보자. 앞서 살펴본 리스트 자료구조의 ADT는 필요에 따라서 그 정의 내용에 약간 씩 차이가 있다. 그에 비해 스택의 ADT는 상대적으로 정형화된편이다. 스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 가리켜, push, pop, peek라 한다. 떄문에 스.. 2021. 2. 23. 양방향 연결 리스트 양방향 연결 리스트(doubly linked list) 또는 이중 연결리스트 라고도 불리는 이 자료구조는 그 이름이 의미하듯 노드가 양쪽 방향으로 연결된 구조의 리스트이다. 즉 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다. 양방향 연결리스트의 구조 head->2->NULL 위에서 보이듯이 하나의 노드가 자신의 왼쪽 노드과 오른쪽 노드를 동시에 가리키는 구조가 양방향 연결 리스트이다. 때문에 양방향 연결리스트의 노드를 표현하는 구조체는 다음과 같이 정의된다. typedef struct _node { Data data; //typedef int Data struct _node *next ; //오른쪽 노드를 가리키는 포인터 변수 struct _node *prev; .. 2021. 2. 16. 원형 연결 리스트 앞서 우리가 구현한 연결리스트의 마지막 노드는 NULL을 가리켯다. 바로 이 마지막 노드가 첫번째 노드를 가리키게 하면 이것이 바로 '원형 연결리스트'가된다. 즉 단순연결리스트가 다음의 구조라면 head->2->4->6->8->NULL 마지막 노드가 첫번째 노드를 가리켜서 , 연결의 형태가 원을 이루는 다음 구조의 연결리스트를 가리켜 '원형 연결 리스트'라 한다. head->2->4->6->8->2 그럼 원형 연결리스트의 특성을 더 알기위해서 숫자 1이 저장된 노드를 머리부분에 추가하겠다. head->1->2->4->6->8->1 이번엔 반대로 원래상태에서 숫자 1이 저장된 노드를 꼬리에 추가해보겠다 . head->2->4->6->8->1->2 위의 상태를 보면 다음과 같은 사실을 알 수 있다. "두 연.. 2021. 2. 15. 연결리스트 3 이제 연결리스트의 정렬 삽입을 구현해 볼것이다. 우리가 구현한 연결리스트에서 정렬기준의 설정과 관련 있는 부분은 다음과 같다. 따라서 이들은 하나로 묶어서 이해해야 한다. 1. 연결리스트의 정렬기준이 되는 함수를 등록하는 SertSortRule 함수 2. SerSortRule 함수를 통해서 전달된 함수 정보를 저장하기 위한 LinkedList의 멤버 comp 3. comp에 등록된 정렬 기준을 근거로 데이터를 저장하는 SInsert함수 위에서 언급한 세 가지를 하나의 문장으로 정리하면 다음과 같다. "SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInesrt함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다." 이렇듯 SetSort.. 2021. 2. 14. 이전 1 2 3 다음
