전체 글

8.9 이진 트리의 추가 연산 ● 노드의 개수 - 트리안의 노드들을 전체적으로 순회하여 카운트를 센다. int get_node_count(TreeNode *node){ int count =0; if(node!=NULL){ count = 1+get_node_count(node->left) + get_node_count(node->right); } return count; } ● 단말 노드 개수 구하기 - 단말 노드는 노드의 자식 노드가 없을 때만 count를 올려준다. int get_leaf_count(TreeNode *node){ int count =0; if(node!=NULL){ if(node->left ==NULL && node->right ==NULL){ return 1; } else{ count..

8.1 트리의 개념 트리: 계층적인 자료구조로, 가족의 가계도, 회사의 조직도, 인공지능의 결정 트리 등에 사용된다. ● 트리의 용어들 노드: 트리의 구성 요소에 해당하는 각각의 데이터셋 루트 노드: 계층구조에서 최상단에 위치하는 노드 서브 노드: 루트 노드를 제외한 나머지 노드 간선(edge): 루트와 서브트리를 연결하는 선 서브트리: 특정 노드에 대한 하위 노드들의 집합 부모 노드 , 자식노드, 형제노드: 가계도에서의 위치 및 관계와 유사한 노드 조상 노드: 루트 노드~ 임의의 노드까지의 경로를 이루고 있는 노드들 후손 노드: 임의의 노드 하위에 연결된 모든 노드들(특정 노드의 서브트리에 속하는 모든 노드) 단말 노드: 자식 노드가 없는 노드/ terminal node 또는 leaf node / 반대..

01 (3) 02 삽입이나 삭제 연산을 하지 않는 나머지 데이터들을 전체적으로 한 칸씩 옮겨주어야 하므로 배열로 구현된 리스트가 가장 많이 실행시간이 소요된다. (1) 03, 04 ListNode *search(ListNode *L,element data){ //03 ListNode *temp = L->link;; for(temp;temp != L;temp = temp->link){ if(temp->data == data){ return temp; } } return NULL; } int get_size(ListNode* L){ //04 int count=1; ListNode *temp = L->link;; for(temp;temp != L;temp = temp->link){ count++; } retu..

7.5 연결 리스트로 구현한 스택 ● 연결된 스택(linked stack) : 연결리스트를 이용한 스택 - 크기가 제한되지 않은 채 동적 메모리 할당을 통해 새로운 요소를 삽입할 수 있다. - 동적 메모리 할당 및 해제에 소요되는 시간으로 인해 삽입과 삭제 시 소요 시간은 늘어난다. - top 변수를 가장 최근에 삽입된 데이터를 나타내는 정수가 아닌, 노드를 가리키는 포인터로 선언 typedef int element; typedef struct StackNode{ element data; struct StackNode* link; }StackNode; typedef struct{ StackNode *top; }LinkedStackType; 각 노드는 data 필드와 다음 노드를 가리키는 링크 필드로 이루..

7.1 원형 연결 리스트 ● 원형 연결 리스트의 소개, 정의, 처음에 삽입, 끝에 삽입 · 원형 리스트: 마지막 노드가 첫 번째 노드를 가리키는 리스트. - 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소를 가리킨다. - 하나의 노드에서 모든 노드를 거쳐 자기 자신으로 되돌아올 수 있다. - 삭제나 삽입 시 선행 노드를 가리키는 포인터를 통해 연산이 용이해진다. - 특히 리스트의 끝에 노드를 삽입하는 연산 시 모든 노드를 다시 탐색할 필요 없이 헤드 포인터가 마지막 노드를 가리키도록 구성한다. 아래는 원형 리스트의 처음에 삽입하는 코드이다. ListNode* insert_first(ListNode* head, element data){ ListNode *node = (ListNode*)ma..

01 (2) 02 (1) 인덱스를 통해 바로 접근할 수 있다 03 (3) 04 (c) 05 p = p->link; 06 q = p; 07 D 08 (4) delete는 insert와 달리 탐색을 한 후 삭제를 해야되기 때문에 DQ부터 Xn까지의 탐색이 필요 09 ListNode* insert_last(ListNode* head,element item){ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->data = item; newnode->link = NULL; ListNode* p = head; if(p==NULL) head = newnode; else { while(p->link !=NULL){ p = p->link; } p->li..

202~208p LAB ListNode* search_list(ListNode* head,element x){ ListNode* p = head; while(p !=NULL){ if(p->data == x) return p; p=p->link; } return NULL; } int where_is_x(ListNode* head,element x){ ListNode* p = (ListNode*)malloc(sizeof(ListNode)); p = head; int count =1; ListNode* search = search_list(head,x); if(search != NULL){ while(p!=search){ count++; p=p->link; } return count; } else{ count..

6.1 리스트 추상 데이터 타입 ● 리스트: 항목들이 순서 또는 위치를 가진 채로 차례대로 저장돼 있는 자료구조 - 기호로 L = (item0, item1, item2, ... , item n-1)과 같이 나타낸다. - 리스트의 기본적인 연산으로는 새로운 항목 추가(삽입), 항목 삭제(삭제), 특정한 항목 찾기(탐색) 등이 있다. ● 리스트의 구현 최상단 그림처럼 리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다. 배열 리스트는 구현이 쉽고 빠르지만 크기가 고정되고, 연결 리스트는 크기가 제한되지 않고 중간에 삽입이나 삭제를 유연하게 구현할 수 있지만 구현이 복잡하고, i번째 항목을 추출하려고 할 때는 배열을 사용할 때보다 시간이 오래 걸린다. 6.2 배열로 구현된 리스트 ● 리스트의 정의, 기초 ..

01 (a) 02 front는 첫 번째 요소의 바로 앞을 가리키기 때문에 인덱스 4, 5 에만 요소가 저장돼있으므로 (b) 03 40,50 04 (c) 05 (2) 06 | 0 1 2 3 4 | ㅡ ㅡ ㅡ ㅡ ㅡ | C A D | 07 q->data[index] 와 같이 index로 바로 접근하므로 O(1)의 시간복잡도를 가진다. (a) 08 element get_count(QueueType *q){ element count=0; if(q->front rear){ count = (q->rear - q->front); } else if(q->front > q->rear){ count = MAX_QUEUE_SIZE - (q->front - q->rear); } return count; } 09 #i..

5.5 덱이란? ● 덱: deque(Double-ended queue)는 이름 줄임말처럼, 큐의 front와 rear에서 모두 삽입, 삭제가 가능한 큐이다. *여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다. add_front, delete_front -> 스택의 push, pop add_rear, delete_front -> 큐의 enqueue, dequeue delete_rear -> 덱만 가지는 연산 원형큐 코드에 delete_rear, add_front, get_rear 연산을 추가하면 된다. *add_rear는 enqueue, delete_front는 dequeue, get_front는 peek연산과 동일하다. add_front와 delete_rear는 각각 배열의 앞과 뒤에서 인덱스를 ..