자료구조 (Data Structures) Chapter 1 Basic Concepts
Overview : Data (1) Data vs Information (2) Data Linear list( 선형리스트 ) - Sequential list : - Linked list : Nonlinear list( 비선형리스트 ) - Tree : - Graph : (3) Data Structure Data와그와연관된 Algorithm을학습및연구 2
1. Basic Concepts (1) Data Abstraction and Encapsulation (2) Algorithm Specification (3) Performance Analysis and Measurement 3
1.1 Overview : System life cycle (1) Requirements( 요구정의 ) (2) Analysis( 분석 ) (3) Design( 설계 ) 4
1.1 Overview : System life cycle (4) Refinement and Coding( 정제와코딩 ) (5) Verification( 검증 ) - Correctness proofs - Testing - Error removal Implementation( 구현 ) 5
1.2 Object-oriented Design 1.2.1 Algorithm Decomposition vs Object-oriented Decomposition 1.2.2 Definitions 1) Object 2) Object-Oriented Programming 3) Object-Oriented Language 6
1.3 Data Abstraction and Encapsulation (1)Data Encapsulation (Information Hiding) (2) Data Abstraction (3) Data Type (4) Abstract Data Type [Example 1.1] ADT Natural Number 7
1.5 Algorithm Specification 1.5.1 Introduction 1) Definition of algorithm 2) Representation of algorithm - Natural language(english) - Graphic representation(flowchart) - Program language(c++) 8
[Example 1.2] selection sort 1) 요구정의 : 입 출력정의 - 입력 : 정렬되지않은정수 ( 개수 : 고정 (n?), 가변 ) - 출력 : 정렬된정수 n개 2) 분석 : 세분화 입력 - 정렬 - 출력 9
[Example 1.2] selection sort 3) 설계가. 입력 - 입력방법 : 파일, 화면, 생성 - 자료구조 : 정수배열나. 정렬 - 정렬방법표현 ( 자연어 ) 정렬되지않는정수들중에서가장작은값을찾아서정렬된리스트다음자리에놓는다. 다. 출력 - 출력방법 : 파일, 화면 10
[Example 1.2] selection sort 4) 코딩가. 주프로그램 int main() { int arr[100], n; n = input_file(arr); // 자료입력 ( 파일 ) sort(arr, n); // 정렬 output_con(arr, n); // 출력 ( 화면 ) return 0; 나. 함수프로그램 - 입력함수 : int input_fun(int*); - 정렬함수 : void sort(int*, const int); - 출력함수 : void output_fun(int*, const int); 11
[Example 1.2] selection sort - 파일입력 int input_file(int *a) { int i, n=0; ifstream In; In.open("sort.dat"); In >> i; while (In){ a[n++] = i; In >> i; In.close(); return n; 12
[Example 1.2] selection sort - 정렬 ( 프로그램 1.8) void sort(int *a, const int n) { for(int i=0; i<n; i++) { int j=i; for(int k=i+1; k<n; k++) if(a[k]<a[j])j=k; int temp=a[i]; a[i]=a[j]; a[j]=temp; return; 13
[Example 1.2] selection sort - 화면출력 void output_con(int *a, const int n) { int i; cout << endl << "* sorted list *" << endl; for(i=0; i<n; i++) cout << setw(4) << a[i]; cout << endl; return 0; 14
1.5 Algorithm Specification 1.5.2 Recursive Algorithms Direct recursion Indirect recursion 15
[Example 1.3] Binary search 1) 요구정의 : 입 출력정의 - 입력정렬된정수 ( 개수 : n?), 탐색정수 - 출력탐색정수가있을때 : 위치번호 (index) 탐색정수가없을때 : -1 2) 분석 : 세분화정렬된정수입력 { 탐색정수입력 - 탐색 - 출력 반복 16
[Example 1.3] Binary search 3) 설계가. 입력 - 입력방법 : 정렬된정수 ( 파일, 생성 ), 탐색정수 ( 화면 ) - 자료구조 : 정렬된정수 ( 배열 ), 탐색정수 ( 정수형변수 ) 나. 탐색 - 탐색방법표현정렬된정수들중에서가장가운데위치한정수 (middle) 와탐색정수 (x) 를비교하여 middle > x 일때앞부분에서탐색반복 middle < x 일때뒷부분에서탐색반복 middle = x 일때탐색완료다. 출력 - 출력방법 : 화면 17
[Example 1.3] Binary search 4) 코딩가. 주프로그램 int main() { int arr[20], n; int x, p; n = input_sorted_file(arr); cout << "Enter one of data to search : "; cin >> x; while(!cin.eof()){ //end of data : Ctrl-z p = BinarySearch(arr, x, n); cout << p << endl; cout << "Enter one of data to search :"; cin >> x; return 0; 18
[Example 1.3] Binary search 나. 함수프로그램 - 탐색함수 비순환프로그램 ( 프로그램 1.10) 순환프로그램 ( 프로그램 1.11) 19
[Example 1.3] Binary search - 비순환프로그램 ( 프로그램 1.10) int BinarySearch(int *a, const int x, const int n) { for(int left=0, right=n-1; left<=right;) { int middle=(left+right)/2; // cout << left << right << middle << endl; if(x>a[middle])left=middle+1; if(x<a[middle])right=middle-1; if(x==a[middle])return middle; return -1; 20
[Example 1.3] Binary search - 순환프로그램 ( 프로그램 1.11) int BinarySearch(int *a, const int x, const int left, const int right) { if(left<=right) { int middle=(left+right)/2; // cout << left << right << middle << endl; if(x>a[middle])return BinarySearch(a, x, middle+1, right); if(x<a[middle])return BinarySearch(a, x, left, middle-1); if(x==a[middle])return middle; return -1; 21