Kim's Programming

스택(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변수와 다음 노드를 가리키기 위한 포인터 변수로 이루어져 있습니다. 노드가 구조체이기 때문에 다음 노드를 가리키는 포인터 또한 구조체를 가리키는 포인터를 선언해 주어야합니다. 다음은 노드를 생성하는 방법입니다. 동적으로 리스트를 만드는 것이므로 노드 객..

연결 리스트 지난 포스팅에서는 배열을 이용한 리스트를 구현해 보았습니다. 하지만 배열은 크기가 지정이 되어있어서 넣는 양의 한계가 있으며 그렇다고 무한정 늘려서 만들게 되면 또 쓸데없는 메모리 낭비를 할 가능성이 매우 높아집니다. 그래서 만드는 것이 연결 리스트 입니다. 연결 리스트는 여러 개의 작은 공간을 연결하여 하나의 자료구조를 표현하며 또 크기 변경이 유연하며 낭비를 하지 않아 더 효율적으로 메모리를 사용할 수 있습니다. 동적으로 구현된 연결 리스트는 메모리 안에서 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요가 없습니다. 다음으론 연결리스트의 장단점을 알아 보겠습니다. 장점 삽입 및 삭제가 용이연속된 메모리 공간이 필요없음크기 제한이 없음(시스템이 허용하는 메모리한해서) 단점 구현이 ..

리스트(List) 리스트란 순서를 가진 항목들의 모임입니다. ADT를 정의하면 저장 형태는 데이터를 나란히 저장을 하며 저장 특성으로는 중복된 데이터의 저장을 허용한다는 것입니다. 리스트 자료구조의 ADT의 예시는 다음과 같습니다. (지정 하기 나름입니다) 리스트의 초기화데이터 저장 (데이터 추가)저장된 데이터의 탐색 및 탐색 초기화다음 데이터 참조(반환)바로 이전에 참조(반환)이 이루어진 데이터의 삭제현재 저장되어 있는 데이터의 수 반환 그럼 이걸 C언어 함수 같이 만들어 볼까요? ListInit(&list) :: 리스트 초기화Linsert(&list, item) :: 데이터 저장LFirst(&list, item) :: 저장된 데이터의 탐색 및 탐색 초기화LNext(&list, item) :: 다음 데..

자료구조 & 알고리즘 프로그램에서 데이터를 표현하는 것을 자료 구조라고 합니다. 일반적으로 프로그램을 자료구조 + 알고리즘 이라고 표현을 할 수 있죠. 일반적인 자료구조와 알고리즘을 모두 가지고 있는 프로그램을 예시를 들어보겠습니다. 위의 소스와 같이 한 프로그램은 자료구조와 알고리즘이 있다는 것을 확인 할 수 있고 데이터 표현을 자료구조(배열)을 통해서 하고 있으며 더하는 방식의 데이터처리(알고리즘)를 하고 있다는 것을 확인 할 수 있습니다. 그럼 자료구조에 대해서 알아보겠습니다. 자료구조 그렇다면 자료 구조의 정확한 의미는 무엇일까요? 그리고 왜 사용할까요? 자료구조는 데이터의 특성에 따라 분류, 구성, 저장하는 모든 작업을 의미합니다. 또 이렇게 분류, 구성을 함으로써 데이터를 효율적으로 사용할 수..