전체 글
-
[Data Structure] 연결 리스트 : 트리알고리즘 & 자료구조 2021. 1. 25. 14:15
트리는 연결리스트를 기반으로 한 새로운 데이터 구조다. 연결 리스트에서 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어있다고 볼 수 있다. 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 된다. 가장 높은 층에서 트리가 시작되는 노드를 '루트' 라고 한다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 '자식 노드' 라고 한다. 위의 그림을 살펴보자, 뭔가 규칙을 찾았는가? 왼쪽이 자식 노드는 자신의 값보다 작고 오른쪽 자식 노드는 자신의 값보다 크다. 따라서 이런 트리 구조는 이진 검색을 수행하는데 유리하다. #include #include //이진 검색 트리의 노드 구조체 typedef struct node { //..
-
[Data Structure]연결 리스트 : 코딩알고리즘 & 자료구조 2021. 1. 24. 23:11
#include #include //연결 리스트의 기본 단위가 되는 node 구조체를 정의 typedef struct node { //node 안에서 정수형 값이 저장되는 변수를 name으로 지정 int number; //다음 node의 주소를 가리키는 포인터를 *next로 지정. struct node *next; }node; int main(void) { //list라는 이름의 node 포인터를 정의한다. 연결 리스트의 가장 첫번째 node를 가리킬 것이다 //이 포인터는 현재 아무것도 가리키고 있지 않아서 NULL로 초기화한다 node *list = NULL; //새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킴 node *n = malloc(sizeof(node)); if(n == N..
-
[Data Structure]연결 리스트 : 도입알고리즘 & 자료구조 2021. 1. 24. 16:37
배열에서는 각 인덱스의 값이 메모리 상에서 연이어 저장 되어 있다. 하지만 꼭 그럴필요가 있을까? 각 값이 메모리상의 여러군데 퍼져 있다고 해도 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있을것이다. 이를 '연결 리스트' 라고 한다. 위의 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음값의 주소 (포인터)를 저장한다. 3은 다음값이 없기에 NULL을 다음 값의 주소로 저장한다. 연결 리스트를 사용하기 위해서는 아래 코드와 같이 간단한 구조체로 정의할 수 있다. //typedef struct 대신에 typedef stuct node 라고 'node'를 함께 명시해 주는 것은, //구조체 안에서 node를 사용하기 위함이다. typedef..