본문 바로가기

자료구조

 (22)
3-2강 - Queue, Circular Queue using Dynamic Allocated Arrays(큐, 동적 할당로 만든 원형 큐) 3. Queue 1) 개념 1> rear에서만 삽입이 일어나 front에서만 삭제가 일어나는 ordered list 2> FIFO(First in First out) : 제일 먼저 들어온 것이 제일 먼저 삭제 3> 삽입 : add = put = push = insertion 4> 삭제 : delete = pop = removal 2) ADT Queue 1> object : 0개 이상의 element를 가지는 finite ordered list 2> function - Queue CreateQ(maxQueueSize) : 최대 크기가 maxStackSize인 empty queue 생성 - Boolean IsFullQ(queue, maxQueueSize) : 원소의 개수가 maxQueueSize이면 true..
3-1강 - Stack, Stack using Dynamic Arrays (스택, 동적 배열로 만든 스택) cf> Ordered List 1> 정의 - Ordered List : A = {a_0, a_1, ..., a_n-1} (n >= 0) - element : a_i - n=0이면 null list (empty list) 2> stack과 queue stack과 queue(special data type)는 ordered list(general data type)의 특수한 경우이다. 1. Stack 1) 개념 S = {a_0, a_1, ..., a_n-1} 1> top에서 삽입과 삭제가 일어나는 ordered list 2> a0는 가장 아래(bottom)에 있는 원소, a_n-1은 가장 위에(top)에 있는 원소 3> LIFO(Last in First out) : 제일 마지막으로 들어온 것이 제일 먼저 삭..
2-5강 - Multidimensional Arrays, Strings (다차원 배열, 문자열) 6. Representation of Multidimensional Arrays 1) 기본 1> 선언 a[upper_0][upper_1] ... [upper_n-1] 2> 원소의 개수 upper_0 * upper_1 * ... * upper_n-1 2) two common ways to representation multidimensional arrays row major order : stores multidimensional arrays by rows column major order : stores multidimensional arrays by columns 1> row major order - a[upper_0][upper_1] a의 각 행(upper_0)은 upper_1개의 element를 가..
2-4강 - Sparse Matrix (희소 행렬) 5. Sparse matices 0) 정의 1> sparse matrix : 원소의 다수가 0을 갖는 행렬. 2> 행렬을 2차원 배열로 표현할 때, 저장 공간의 낭비가 있다. 3> 선언 : arr[MAX_ROWS][MAX_COLS] 4> 접근 : arr[i][j] (행렬의 i행 j열에 접근) 1) ADT ADT Spase_Matrix 1> object : (3원소 쌍의 집합) - value는 item 집합의 원소이다. 2> function - Create(max_row, max_col) : maxItems(=max_rowXmax_col)개를 저장할 수 있는 sparse marix return (최대 max_row개의 행과 max_col개의 열을 저장할 수 있는 sparse matix return) - T..
2-3강 - Polynomials (다항식) 4. Polynomials cf> array는 그 자체로 [1]자료 구조이며 [2]또다른 ADT 구현할 수 있다. 1) ADT - ordered list(linear list) 0> 예시 (4번째 예시처럼 공백 리스트도 있다. - 일주일의 요일들: (일요일, 월요일, 화요일, 수요일, 목요일, 금요일, 토요일) - 건물의 층 : (지하, 로비, 일층, 이층) - 미국의 제2차 세계대전 참전 연도 : (1941, 1942, 1943, 1944, 1945) ​- 스위스의 제2차 세계대전 참전 연도 : ( ) 1> Object - object : a set of ordered pairs of (전제: a_i는 계수, e_i는 지수, e_i는 0이상의 정수) (사실 sum of terms이다.) 2> funct..
2-2강 - 구조체와 공용체 3. Structures and Unions 1) Structures 1> 설명 - type이 다른 data를 그룹화 - 각 항목은 type과 name으로 구분된다. - 다른 언어에서는 'record'라고 부르기도 한다. - C언어에서는 'struct' (구조체)로 표기한다. 2> 예시 1 (기본) // 1. 구조체 정의 및 선언 struct { char name[10]; int age; float salary; } person; // 2. 멤버 접근 strcpy(person.name,"james"); person.age = 10; person.salary = 35000 - 변수(name) : person - 3개의 field 존재 3> 예시 2 (typedef) // 1. 구조체 정의 typedef s..
2-1강 - ADT array, 동적 할당 cf> ADT 1) 구체적인 기능의 완성 과정은 서술하지 않고 오로지 순수하게 기능이 무엇인지만 나열하는 것 2) 속성 1> Objects (Characters) : ADT의 내부 속성 (OOP에서 classd의 내부 필드와 유사) ex> 자동차의 바퀴, 문, 핸들 등 2> Functions (Operations) : ADT의 연산 ex> 자동차 : 운전을 하다 1. Arrays 1) The Abstract Data Type 0> array를 단순히 '일련의 연속적인 메모리 위치'로만 보지 말자 - object : 의 쌍으로 구성된 집합 (index와 value간에 mapping이 존재) - Functions (주목) : retrieving a value, storing a value (value를 불러..
1-6강 - Performance measurement (시간 측정) 0. Intro 1> C standard library를 이용한다. #include 1. Method 1 start = clock(); stop = clock(); duration = ((double)(stop-start))/CLOCKS_PER_SEC; 2. Method 2 start = time(NULL); stop = time(NULL); duration = (double)difftime(stop,start);

티스토리툴바