자료구조 6

[C언어] 트리(Tree)

트리(Tree) 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. 트리구조를 사용하여 컴퓨터의 디렉터리 구조, 집안의 족보, 기업의 조직도 등을 표현할 수 있다. 트리 관련 용어 노드(node) -> 트리의 구성요소, A, B, C, D, E, F와 같은 요소 간선(edge) -> 노드와 노드를 연결하는 연결선 루트 노드(root node) -> 트리 구조에서 최상위에 존재하는 노드, A와 같은 노드 단말 노드(terminal node), 잎사귀 노드(leaf node) -> 아래로 다른 노드가 연결되어 있지 않은 노드, C, D, E, F와 같은 노드 내부 노드(internal node), 비단말 노드(nonterminal node) -> 단말 노드를 제외한 ..

[자료구조 - C언어] 큐(Queue)

Queue - FIFO(First In First Out) 형식 큐(queue)는 스택과 반대로 입구와 출구가 나뉘어 있습니다. 즉, 가장 먼저 들어온 자료가 가장 먼저 나가게 되는 형식입니다. 1 #include 2 #include 3 4 typedef struct node{ 5 char value; 6 struct node *prev; 7 struct node *next; 8 }NODE; 9 10 typedef struct _queue{ 11 NODE *head; 12 NODE *tail; 13 }QUEUE; 14 15 QUEUE *queue_create(){ 16 QUEUE *queue; 17 queue = (QUEUE*)malloc(sizeof(QUEUE)); 18 19 queue->head = ..

[자료구조 - C언어] 스택(Stack)

Stack - LIFO형식 스택에서는 자료를 넣고 빼는 곳이 하나만 있는 LIFO(Last In First Out) 형식이다. 즉, 제일 처음 들어간 자료가 가장 마지막에 나오게 된다. #include#include #include typedef struct node{ char value; struct node *next; }NODE; NODE *stack_push(NODE *top_node, char value){ NODE *new_top_node = NULL; new_top_node = (NODE*)malloc(sizeof(NODE)); new_top_node->value = value; new_top_node->next = top_node; return new_top_node; } NODE *sta..

[자료구조 - C언어] Linked List(3) - delete

Delete - 노드 삭제하기 delete_node : 인덱스 값과 삭제할 노드의 개수를 입력하여 해당 노드를 삭제함. #include #include typedef struct node { char value; struct node *next_node; }NODE; NODE *create_node(char v){ NODE *mynode; mynode = (NODE*)malloc(sizeof(NODE)); mynode->value = v; mynode->next_node = NULL; return mynode; } void append_node(NODE* h, NODE* n) { struct node *tail; if (h == NULL || n == NULL) return; tail = h; while..

[자료구조 - C언어] Linked List(2) - create, insert

사용된 함수 create_node : 동적 메모리를 할당받아 메인 함수에서 입력받은 값을 구조체 멤버 변수(value)에 대입함. append_node : tail노드에 새로운 노드를 붙이는 역할을 함. prepend_node : head노드 앞에 새로운 노드를 붙이는 역할을 함. print_node : 생성된 노드를 출력함. Create - 노드 생성하기 - 배열을 이용하여 "string"으로 노드 구성하기 - #include #include typedef struct node { char value; struct node* next_node; }NODE; NODE* create_node(char v) { NODE* mynode; mynode = (NODE*)malloc(sizeof(NODE)); //..

[자료구조 - C언어] Linked List

Array대신 Linked List를 사용하는 이유는 무엇일까? 예를 들어, char arr[6] = "linked"; 이런 배열이 있다고 하자. 0~5까지의 배열 칸에 알파벳이 하나씩 들어가 있을 것이다. 여기서 'n'을 삭제하려면 'n' 삭제하고 뒤에 있는 나머지 배열 칸의 값들을 전부 복사하여 한 칸씩 앞에 넣어 줘야 한다. 이렇게 배열 인덱스를 바꿔 주는 것은 번거롭고 복잡하기 때문에 "링크드 리스트(Linked List)"를 사용하여 추가, 삭제 등 각 노드의 수정을 용이하게 한다. 연습하기 1 헤드 노드 하나만 생성하여 값을 넣고 다음 노드에는 NULL로 설정하기 #include typedef struct node { char value; struct node *next_node; }NODE;..