Kim's Programming

이번에는 큐를 동적으로 만들어 보겠습니다. 큐(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를 이용하여 리스트 각각을 구별하게 되며 ..

단순연결 리스트를 만들기 전에 기본적인 사항들 몇개 짚고 가겠습니다. 노드 앞에서 보았듯이 단순연결 리스트는 앞에서 뒤로 한방향으로만 연결이 되어 있으며 제일 뒤의 노드의 Link값은 NULL이 들어갑니다. 우선 단순 연결 리스트의 노드 구조체부터 살펴보겠습니다.12345typedef struct ListNode{ int VALUE;//값 struct ListNode *Link;//다음 노드의 주소를 저장}ListNode;cs노드는 값을 저장하는 VALUE변수와 다음 노드를 가리키기 위한 포인터 변수로 이루어져 있습니다. 노드가 구조체이기 때문에 다음 노드를 가리키는 포인터 또한 구조체를 가리키는 포인터를 선언해 주어야합니다. 다음은 노드를 생성하는 방법입니다. 동적으로 리스트를 만드는 것이므로 노드 객..