반응형

자료구조 5

자료구조 – 이중 연결리스트[doubly linked list] C언어

이중 연결리스트는 단순 연결리스트 자료구조를 확장한 형태이다. 단순 연결리스트를 정확히 이해했다면, 이중 연결리스트에 대한 구조 또한 쉽게 이해할 수 있다. 2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어 왼편(단순연결리스트), 오른편(이중연결리스트)의 차이는 prev의 유무다. prev의 역할은 next와 비슷한데 next가 다음 노드(NODE)를 참조하는 것에 반해 prev는 이전 노드(NODE)를 참조한다. 이런 구조적인 차이로 인해 알고리즘도 약간의 변화가 생기게 된다. 단순 연결 리스트의 삽입, 삭제와 이중 연결 리스트의 삽입, 삭제에 대한 비교를 하면 쉽게 이해할 수 있다. 위 그림은 단순 연결리스트의 메모리의 구조를 모식적으로 나타낸 것이..

자료구조 -트리(Tree) C언어

트리의 특징 2차원적 구조를 가짐. 이에 반해 자료구조 배열, 연결리스트, 스택, 큐...등은 1차원 선형적 구조를 갖음. 2014/02/28 - [프로그래밍/C언어] - 동적배열 자료구조의 시작 2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어 2014/03/21 - [프로그래밍/C언어] - 자료구조 스택(stack) C언어 2014/03/22 - [프로그래밍/C언어] - 자료구조 큐(Queue) C언어 용어정리 차수 - 자식 노드의 개수 잎 - 자식 노드가 0인 노드 서브트리(sub Tree) - 트리 내부의 작은 트리 포리스트(Forest) - 트리가 여러 개 모인 것. 레벨(level) - 루트에서 그 노드까지의 거리를 말함.(루트레벨 :1) 높..

자료구조 큐(Queue) C언어

스택은 데이타의 출입구가 한 군데인데 반해, 큐는 데이타 입출입이 양뱡향입니다. FIFO(First in First Out)구조를 가졌습니다. 터널을 지나는 자동차를 생각해보면 터널은 큐고 터널의 길이는 큐의 크기가 됩니다. 그리고 자동차는 데이타가 되겠죠. 큐도 스택과 비슷하고 데이타의 입력방향과 출력방향이 다르다는 것만 주의하면 됩니다. 스택에서는 offset(오프셋)을 기억하는 변수를 하나만 두었지만, 큐에서는 입력과 출력의 위치가 다르기 때문에 두개를 두어야합니다. 데이타가 머리부터 차례로 입력된다 생각하고 변수를 정하면, FIFO구조기때문에 출력위치는 머리가 됩니다. 그리고 입력위치는 꼬리가 되겠죠. 출력위치를 가리키는 변수를 head, 입력위치를 가리키는 변수를 tail이라고 하면 구조는 다음..

자료구조 스택(stack) C언어

스택(stack)도 연결리스트와 마찬가지로 선형자료구조다. 우리가 알고있는 메모리의 스택도 같은 구조를 가진다. 스택의 특성은 LIFO(Last in First Out)으로 저장되는 구조인데, 스택을 비우는 순서는 가장 마지막으로 넣은 정보부터 빠지게된다. 책을 박스에 차곡차곡 쌓아서 보관해 놓았는데, 다시 책들을 꺼내기 위해서는 맨 위에서부터 빼내야 하는 이치와 같다. 우리가 알고있는 재귀함수를 이용하는 것도 스택의 특성을 사용한다. 좀 더 예를 들어보면 우리가 C프로그래밍을 할 때 가장먼저 호출되는 함수는 main함수다. 하지만 main함수는 가장 마지막에 반환된다. (LIFO == FILO ) 우리가 구현하고자 하는 스택을 간략히 표현해 보겠다. 2014/02/28 - [프로그래밍/C언어] - 동적..

자료구조 - 연결리스트[linked list] C언어

연결리스트는 동적배열과 비슷하지만 동적배열에 비해 데이터를 유연하게 삽입, 삭제할 수가 있다. 동적배열의 경우엔 삽입을 하기위해선 배열의 크기를 체크하고 배열의 공간이 꽉 차있다면 realloc을 하였다. 그리고 삽입, 삭제할 지점 이후의 자료들은 메모리의 이동이 이루어지기 때문에, 삽입시 부자연스럽기도 하다. 동적배열과의 연결리스트의 차이점은 배열의 특성은 메모리공간에서 연속이라는 점이다. 그래서 첨자연산으로 빠른 속도가 보장되지만, 메모리가 연속이어야 하기 때문에, 삽입과 삭제가 번거롭다. 하지면 연결리스트는 메모리상에 연속이지 않아도 된다. 다음데이터에 대한 링크정보를 지니고 있기때문에 가능한 일이다. 2014/02/28 - [프로그래밍/C언어] - 동적배열 자료구조의 시작 2014/03/17 - ..

반응형