Kim's Programming

덱(Deque) - 동적 - 특징과 정의 Deque이란 Double Ended Queue의 준말로 기존의 큐와는 다르게 앞뒤 어디로든 자료를 넣을 수 있고 어디로든 자료를 뺄수 있는 자료구조 형태를 의미합니다. 전반적인 기능들은 큐와 같기 때문에 배열로는 구현을 안하고 동적으로만 구현을 하겠습니다. 덱은 다음과 같은 구조체를 사용하여 만들게 됩니다.1234567891011121314#include#include struct Node{ int Item; Node *Prev; Node *Next;};struct Deque{ Node *header; Node *tailer;};cs그냥 느낌상으로는 이중 연결 리스트정도의 느낌입니다. 덱(Deque) - 동적 - ADT void init_Deque() 12345..

이번에는 큐를 동적으로 만들어 보겠습니다. 큐(Queue) - 동적 - 구조 큐를 동적으로 만들 때는 다음과 같은 구조체를 이용하게 됩니다. 12345678910111213#include#includestruct QueueNode{ QueueNode *Link; int VALUE;};struct Queue{ QueueNode *header;//제일 앞 포인터 QueueNode *tailer;//제일 뒤 포인터 QueueNode *Temp_Tail;//제일 뒤 바로 앞 포인터};Colored by Color Scriptercs이번엔 포인터를 3개를 사용했습니다. 큐를 만들때 이번엔 단순연결 리스트를 이용하여 만들었습니다. 단순 연결리스트는 다시 뒤로 돌아가기 힘들기 때문에 포인터를 하나더 썼습니다. 큐(Q..

큐(Queue) - 구조 우선 큐란 스텍과는 다르게 나가는 출구와 들어가는 입구가 따로 있는 자료구조입니다. 그리고 먼저 들어온것이 먼져 나가기 때문에 FIFO(First-In-First-Out) 자료구조라고도 부릅니다. 큐를 배열로 표현할 때는 2가지 경우가 있으며 다음과 같은 특징을 가집니다.. 선형 큐 : 배열을 선형으로 사용하여 큐를 구현 삽입을 계속하기 위해서는 요소들을 이동시켜야한다. 문제점이 많기 때문에 사용되지 않는다. 원형 큐 : 배열을 원형으로 사용(생각)하여 큐를 구현(이것을 사용) 큐(Queue) - 원형 큐를 이용 원형큐를 이용하게 되면 다음과 같은 원형 형식의 배열을 사용하게 됩니다. 하지만 배열에서는 앞과 뒤를 구분할 것이 필요하기 떄문에 두 가지 포인터를 사용하여 인덱스를 구..

스택(Stack) - 동적할당 이번에는 동적할당을 통해서 스텍을 구현해 보겠습니다. 우선 구현에 앞서서 동적 스택 구현에 사용된 구조체부터 보고 가겠습니다.123456789101112#include#includetypedef struct ELEMENT{ int item; ELEMENT *LINK = NULL;}ELEMNT;typedef struct STACK{ int top = 0; ELEMENT *HEADER = NULL;}STACK;cs아까와 같지만 이번에는 포인터를 이용하여 다음 노드를 가르킵니다. 연결 리스트와 같은 원리를 이용하는 것입니다. 이번엔 ADT 구현을 하나하나 살펴 보겠습니다. 이번에는 배열에서 구현한 것과는 다르게 앞에서 넣고 앞에서 빼는 형태입니다. 또한 배열과는 다르게 동적할당은..

스택(Stack) 이번에는 자료구조중 스택(Stack)을 알아보겠습니다. 스택이라는 것은 Stack이라는 단어의 사전적 의미에서도 볼 수 있고 위의 그림에서 볼 수 도 있듯이 쌓아놓은 더미를 뜻합니다. 스택(Stack)의 특징 스택은 후입선출(LIFO)의 특징을 가지고 있습니다. LIFO란 Last-In-First-Out으로 가장 나중에 들어온것이 가장 먼져 나간다는 것을 의미합니다. 말그대로 상자를 쌓아뒀다가 제일 밑에 것을 빼내고 싶으면 위에 것들을 다 치운다음 제일 밑에 것을 움직 일 수 있는 것과 같다고 생각하면 됩니다. 스택(Stack)의 구조 스텍은 후입선출의 구조를 가지므로 입구가 하나라고 생각할 수 있습니다. 구조는 다음과 같이 볼 수 있습니다. 스택의 가장 위쪽인(가장 나중에 들어온 자료..

이중 연결 리스트 이중 원형 연결 리스트의 등장은 단순 연결의 문제점을 보완하기 위해 만들 수 있습니다. 어떤 문제점이 있을까요?단순 연결 리스트의 문제점 선행 노드를 찾기 힘듬!(다시 돌아오거나 따로 소스를 복잡하게 짜서 받아놔야함)삽입이나 삭제시에 반드시 선행 노드를 필요로함.이런것을 보완하는게 이중 연결 리스트인데 이중 연결 리스트의 특징에 대해 알아 보겠습니다. 이중 연결 리스트의 특징 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트링크가 양방향이므로 양방향으로 검색이 가능하지만 공간을 많이 차지하고 코드가 복잡하다는 단점을 가짐 이중 연결 리스트의 노드는 다음과 같은 형태와 소스를 가지게 됩니다.123456typedef struct ListNode//노드 개별을 의미{..

단순 원형 연결 리스트 앞에서 단순 연결 리스트를 해보았습니다. 하지만 이번에 알아볼 것은 단순 '원형' 연결 리스트 인데요 단순 원형 연결 리스트는 단순 연결 리스트와 어떤 차이가 있을 까요? 단순 연결 리스트의 단점 부터 알아보겠습니다. 단순 연결 리스트 단점 특정 노드 검색시 대상 이전의 도드들에 대해서 검색 불가검색시 항상 첫 노드부터 검색 이를 보완할 수 있는것이 단순 원형 연결 리스트 인데요. 다음은 단순 원형 연결 리스트의 특징 및 장점들입니다. 단순 원형 연결 리스트의 특징 첫 번째 노드와 마지막 노드를 가리키도록 구성첫 번째 노드와 마지막 노드의 구분이 없음어떤 노드의 연결 필드에서도 NULL값은 갖지 않음현재 위치에서 계속해서 검색 작업을 할 수 있음첫번 째 노드와 마지막 노드를 가리키..

지난 포스팅에서 기본적인 사항과 삽입, 삭제 구현을 알아보았으니 이번에는 실제 함수 구현을 보겠습니다.ADT는 배열에서 구현한것과 같지만 배열이 아닌 동적 할당을 통해서 만들었습니다. 우선 필요한것은 노드! 그리고 노드들을 묶어줄 녀석이 필요합니다.12345678910typedef struct ListNode{ int VALUE; struct ListNode *Link;}ListNode; typedef struct List{ ListNode *header;}List;cs노드 각각을 표현하기 위한 ListNode 구조체와 노드들의 집합 즉 헤더를 나타내기 위한 List 구조체를 만들어서 이용하였습니다. 이렇게 만드는 이유는 앞에서도 설명하였듯이 리스트는 header를 이용하여 리스트 각각을 구별하게 되며 ..