컴퓨터과학54 [자료구조] 6주차 - 트리 (Tree) Tree 선형 자료구조의 한계 2개 이상의 관계를 표현할 수 없음 계층적 구조 하나의 근원(root)으로부터 파생됨 한 노드가 여러 개의 노드로 전파됨 순환하는 경로(cycle path)가 없음 트리 루트(root)라고 불리는 특별한 노드가 있음 연결된 모든 노드의 쌍은 재귀적으로 부모자식관계(parent-child relation)을 맺음 순환하는 경로(cycle path)가 없음 용어 node (vertex) Root node, Leaf node, Internal node 부모 노드(Parent node), 자식 노드(Child node), 형제 노드(Sibling node) 조상 노드(Ancesor node), 후손 노드(Descendent node) 부분 트리 (subtree) Degree of .. 2021. 2. 1. [자료구조] 5주차 - 정렬 (Sorting) Sorting 리스트 연산은 정렬된 리스트일 때 성능이 더 좋음 정렬 : 데이터를 정해진 키에 따라서 크기 순으로 배열 하는 것 O(n^2) 정렬 알고리즘 : 버블, 삽입, 선택, ··· 이동 기반 : 삽입 정렬 교환 기반 : 버블 정렬, 선택 정렬 O(n log n) 정렬 알고리즘 : 합병, 쾌속, ··· 분할 정복 방식(divide&conquer) : 합병, 쾌속 트리 구조 이용 : 히입 정렬 O(n^2) 정렬 : 삽입, 버블, 선택 삽입 정렬(Insertion sort) 추가(insert) 연산에 기반한 정렬 알고리즘 정렬되지 않은 리스트의 원소들을 차례로 정렬된 리스트에 추가하며 정렬을 수행 배열의 가장 앞자리부터 정렬된 부분 배열을 생성하고 그 크기를 증가시킴 void insert( int x,.. 2021. 1. 29. [자료구조] 4주차 - 스택(Stack)과 큐(Queue) Stack 원소와 그 도착한 시간을 반대순서로 저장한 리스트 원소의 추가와 제거가 탑(top)이라 불리는 한 끝에서만 일어나는 리스트 Last-In First-Out (LIFO 또는FILO) push와 pop 스택의 자료구조 class Stack { int size; DataType *Items; int TOP; } 스택의 연산 생성 (CreateStack) void Stack::CreateStack( int_size ) { size = _size ; tItem= new Datatype[size]; TOP = 0; } 엠티 (IsEmpty) int Stack::is_Empty( ) { return ( TOP == 0 ); } 풀 (IsFull) int Stack::is_Full ( ) { return (.. 2021. 1. 28. [자료구조] 3주차 - 연결 리스트 (Linked list) Linked List 원소들이 메모리에서 임의의 위치에 배치되어 있음 한 원소는 다음 원소를 가리키는 주소 (link, pointer)를 가지고 있음(포인터 기반의 자료구조) node = data + link, node는 메모리의 임의의 위치에 배치됨 단일 연결 리스트 (singly linked list) : node 당 하나의 link 정의 class node { data_type item; node *link; }; class hnode { node *link; }; 생성 void main ( ) { hnode first; } 검색 (선형 탐색만 가능) 보류 node *hnode::search( data_type item ) { return this->link->search ( item ); } no.. 2021. 1. 27. 이전 1 ··· 8 9 10 11 12 13 14 다음