처음으로 배우는 C 프로그래밍 제4부 복합 데이터 형 제 7 장 배열

제 1 절 배열(Arrays) 변수와 배열 본 장에서는 배열에 관한 다음 사항을 다룸 스칼라 변수 : 한번에 선언된 자료형의 값 하나를 저장하는 변수 일차원 배열 : 동일한 자료형의 원소들로 구성되는 간단한 리스트 본 장에서는 배열에 관한 다음 사항을 다룸 일차원 배열의 선언 배열의 초기화 배열의 저장과 사용 다차원 배열의 정의와 사용

7.1 일차원 배열 일차원 배열의 선언 배열의 첨자 배열 원소의 데이타형, 배열의 이름, 배열의 크기를 명시해야 함 배열 원소의 데이타형, 배열의 이름, 배열의 크기를 명시해야 함 예) char code[4]; double price[6]; float amount[100]; 배열의 원소들은 기억장소의 연속된 위치에 저장됨 배열의 첨자 배열의 원소의 위치를 색인 혹은 첨자 (index 혹은 subscript)라고 부름 배열의 원소를 색인 변수 혹은 첨자 변수라고 부름 예) amount[0], amount[1], ... 배열의 이름 ?, 원소의 자료형 ?, 배열의 크기 ? 원소의 크기 ? amount amount[0] amount[1] amount[99]

7.1 일차원 배열 첨자 변수의 사용 첨자 변수는 일반 스칼라 변수와 동일한 자격으로 사용됨 즉, 스칼라 변수가 유효한 곳이라면 어디에나 나타날 수 있음 예) grades[0] = 98; grades[1] = grades[0] – 11; grades[2] = 2 * (grades[0] – 6) grades[3] = 79 grades[4] = (grades[2] + grades[3] – 3)/2 total = grades[0] + grades[1] + grades[2] + grades[3] + grades[4]; 첨자는 정수로 계산되는 수식 표현도 될 수 있음 예) grades[2*i] = 99; maximum = price[0]; /* 첫번째 원소를 최대값으로 가정함 */ for(i = 1; i <= 999; ++i) /* 배열의 나머지 원소를 점검함 */ if (price[i] > maximum) /* 각 원소를 최대값과 비교함 */ maximum = price[i]; /* 최대값보다 더 큰 원소가 있으면 최대값을 원소로 재설정함 */

7.1 일차원 배열 배열 값들의 입력과 출력 주의할 점 scanf () 함수나 assign 문의 사용 예) for 문을 사용한 배열 원소의 입력과 출력 주의할 점 컴파일러는 배열의 첨자의 한계를 검사하지 않음 예) 배열 grades[]의 크기가 5 임에도 불구하고 6 개 이상의 값을 저장하려고 시도해도 C 컴파일러는 에러를 내지 않음 price[5] = 10.69; scanf(“%d %lf”, &grades[0], &price[2]); scanf(“%c”, &code[0]); scanf(“%d %d %d”, &grades[0], &grades[1], &grades[2]); for(i = 0; i <=4; ++i) printf(“Enter a grade:”); scanf(“%d”, &grades[i]); printf(“\n grades[%d]=%d”, i, grades[i]);

7.1 일차원 배열 배열을 사용한 예제 : [프로그램 7-2] #include <stdio.h> 배열을 사용한 예제 : [프로그램 7-2] #include <stdio.h> void main(void) { int i, grades[5], total = 0; for (i = 0; i <=4; ++i) { /*Enter five grades */ printf(“Enter a grade:”); scanf(“%d”, &grades[i]); } printf(“\n The total of the grades”); for (i = 0; i <= 4; ++i) { /* Display and total the grades */ printf(“%d “, grades[i]); total += grades[i]; printf(“is %d”, total); [프로그램 7-2]의 실행 결과 : Enter a grade: 85 Enter a grade: 90 Enter a grade: 78 Enter a grade: 75 Enter a grade: 92 The total of the grades 85 90 78 75 92 is 420

7.2 배열의 초기화 지역 배역과 전역 배열 지역 배열 : 함수의 내부에서 선언된 변수 7.2 배열의 초기화 지역 배역과 전역 배열 지역 배열 : 함수의 내부에서 선언된 변수 전역 배열 : 함수의 외부에서 선언된 배열 예) int gallons[20]; /*a global arra */ static double dist [25]; /*a static global array*/ void main(void) { int i; void mpg(int); /*function prototype */ for (i = 1; i <= 10; ++i) mpg(i); /*call mpg() ten times */ … } void mpg(int car_no) { int miles[15]; /*an automatic local array */ static course[15]; /*a static local array */ …. return;

7.2 배열의 초기화 배열의 초기화 주의할 점 변수의 초기화와 유사한 개념으로 배열의 원소들을 초기화 할 수 있음 7.2 배열의 초기화 배열의 초기화 변수의 초기화와 유사한 개념으로 배열의 원소들을 초기화 할 수 있음 배열의 초기치는 여러 개이므로 중괄호를 사용하여 표시함 일반적으로 프로그램의 첫 부분에서 배열을 초기화함 예) 주의할 점 초기치는 나열된 순서대로 배열의 원소에 저장되며, 초기치가 모자라면 뒷부분의 배열 원소는 0으로 초기화됨 문자 배열의 초기화 char codes[6]={'s', 'a', 'm', 'l', 'e’} ; 대신에 간단히 char codes[]=“sample”; 형식으로 할 수 있으며, 맨 뒤 원소는 \0로 채워짐 int grades[5]={98, 87, 92, 79, 85}; char codes[6]={'s', 'a', 'm', 'l', 'e’} ; double width[7]={10.96, 6.43, 2.58, .86, 5.89, 7.56, 8.22}; static int temp[4]={10, 20, 30, 40}; static float temp[4]={98.6, 97.2, 99.0, 101.5};

7.3 배열의 전달 배열을 함수의 인자로 전달하는 방안 배열 원소의 전달 첨자 변수를 함수의 인자로 사용하며, 함수로는 원소의 값이 전달됨 예) find_min(grades[2], grades[6]) : 배열 원소 grades[2]와 grades[6]이 함수 find_min()에 전달됨 (값이 전달됨) 배열 전체의 전달 배열 명을 함수의 인자로 사용하고, 이 경우 배열의 첫 원소의 주소가 함수로 전달됨 (배열의 원소는 전달되지 않음을 유의) 예) find_min(grades) : 배열 grades가 함수 find_min()에 전달됨 (첫 원소의 주소가 전달됨) 배열 인자를 전달 받는 함수는 그 인자가 배열임을 명확히 인식해야 하며, 함수 헤드에서 인자가 배열임을 명시함

7.3 배열의 전달 배열 인자 전달의 예 int nums[5]; char keys[256]; double units[500], prices[500]; 이 배열들에 대하여 다음의 함수 호출이 가능하다. find_max(nums); find_ch(keys); calc_tot(nums, units, prices); 각각의 경우에, 호출된 함수의 몸체에서 인자로 전달된 배열에 직접 접근할 수 있음; 다만, 배열 인자를 전달받은 호출된 함수는 그 인자가 배열임을 명확히 인식해야 함 예를 들면, 앞의 함수 호출에 대한 적절한 함수 헤더는 다음과 같다. int find_max(int vals[5]) char find_ch(char in_key[256]) void calc_tot(int arr1[5], double arr2[500], double arr3[500])

7.3 배열의 전달 배열 전달 프로그램 예 [프로그램 7-4 ] #include <stdio.h> void main(void) { int nums[5] = {2, 18, 1, 27, 16}; int find_max (int [], int); /*function prototype*/ printf(“The maximum value is %d”, find_max(nums, 5)); /* 함수 호출 */ } int find_max(int vals[], int num_els) { int i, max = vals[0]; for (i = 1; i < num_els; ++i) if (max < vals[i]) max = vals[i]; return(max); [프로그램 7-4]의 실행 결과 The maximum value is 27

7.4 이차원 배열 이차원 배열 행과 열로 구성됨 예) 3행 4열로 구성되는 2차원 배열 : val 8 16 9 52 7.4 이차원 배열 이차원 배열 행과 열로 구성됨 예) 3행 4열로 구성되는 2차원 배열 : val 8 16 9 52 3 15 27 6 14 25 2 10 이차원 배열의 선언 예) int val[3][4]; 배열 내의 원소들은 첨자 변수 형태로 지칭하며, 스칼라 변수나 일차원 배열의 변수와 동일한 자격으로 사용됨 num = val[2][3]; val[0][0] = 62; new_num = 4* (val[1][0] – 5); sum_row0 = val[0][0] + val[0][1] + val[0][2] + val[0][3];

7.4 이차원 배열 지역 배열과 전역 배열 이차원 배열의 초기화 : 두가지 방법 2차원 배열의 초기화는 행 우선 방식임 7.4 이차원 배열 지역 배열과 전역 배열 1차원 배열과 동일한 개념임 이차원 배열의 초기화 : 두가지 방법 2차원 배열의 초기화는 행 우선 방식임 첫 행이 전부 초기화된 후에, 두번째행, …, 마지막 행 순서로 초기화됨 주어진 초기치값이 모자라면 행 우선으로 초기화시키고, 나머지 원소들은 널 값으로 채움 int val[3][4] = { {8, 16, 9, 52}, {3, 15, 27, 6}, {14, 25, 2, 10} }; int val[3][4] = { 8, 16, 9, 52, 3, 15, 27, 6, 14, 25, 2, 10 };

7.4 이차원 배열 2 차원 배열의 입출력 예 : [프로그램 7-6] #include <stdio.h> 7.4 이차원 배열 2 차원 배열의 입출력 예 : [프로그램 7-6] #include <stdio.h> void main(void) { int i, j, val[3][4] = { 8, 16, 9, 52, 3, 15, 27, 6, 14, 25, 2, 10}; /*multiply each element by 10 and display it */ printf(“\nDisplay of multiplied elements \n”); for (i = 0; i < 3; ++i) print (“\n”); /*start a new line*/ for ( j = 0; j < 4; ++j) val[i][j] = val[i][j] * 10; printf(“%3d ”, val[i][j]); } /*end of inner loop */ } /*end of outer loop */ } [프로그램 7-6]의 샐행 결과 Display of multiplied elements 80 160 90 520 30 150 270 60 140 250 20 100

7.4 이차원 배열 2 차원 배열의 전달 1 차원 배열의 경우와 동일한 원리로 함수의 원소 (값)가 전달되거나 배열명(첫번째 원소의 주소)이 전달됨 배열명을 전달 받은 함수에서 배열 원소값에 대한 변경은 원래 배열에 대하여 직접 가해짐 : 프로그램 7-2 참고 함수의 인자로 배열을 전달하는 예 : int test[7][9]; char code[26][10]; float stocks[256][52]; 위의 선언에 대하여 다음의 함수호출은 유효하다: find_max(test); obtain(code); price(stocks); 호출된 함수는 이차원 배열임을 인식해야 하므로 호출되는 함수의 함수 헤더는 다음과 같다. int find_max(int test[7][9]); char obtain(char code[26][10]); void price(float stocks[256][52]);

7.4 이차원 배열 2 차원 배열의 전달 프로그램 예 : [프로그램 7-7] 실행 결과 : 8 16 9 52 3 15 27 6 7.4 이차원 배열 2 차원 배열의 전달 프로그램 예 : [프로그램 7-7] #include <stdio.h> void main(void) { int i, j, val[3][4] = { 8, 16, 9, 52, 3, 15, 27, 6, 14, 25, 2, 10}; void display(int [3][4]); /*function prototype */ display(val); } void display(int nums[3][4]) { int row-num, col_num; for (row_num = 0; row_num < 3; ++row_num) for (col_num = 0; col_num <4; ++col_num) printf(“%4d\n”, nums[row_num][col_num]); printf(“\n”); 실행 결과 : 8 16 9 52 3 15 27 6 14 25 2 10

7.4 이차원 배열 6 개의 2차원 배열로 간주됨 10 6 4 다차원 배열 각 차원의 크기를 배열명 다음에 명시함으로서 생성됨 7.4 이차원 배열 다차원 배열 각 차원의 크기를 배열명 다음에 명시함으로서 생성됨 예) int response[10][4][6]; 4 10 6 response[0][0][0] response[9][3][0] response[9][3][5] : 마지막 원소 6 개의 2차원 배열로 간주됨

7.5 자주 사용되는 에러들 배열의 선언을 하지 않았을 경우 배열의 첨자 영역을 벗어난 경우 7.5 자주 사용되는 에러들 배열의 선언을 하지 않았을 경우 invalid indirection error message 배열의 첨자 영역을 벗어난 경우 충돌 (crash) 혹은 메모리로부터 접근가능한 원소가 아니라는 메시지 출력 배열의 모든 원소를 검침할 만큼 반복문의 첨자 크기가 충분하지 못한 경우 배열의 원소가 10개인데 for 문의 인덱스가 충분하지 못한 경우 배열의 초기화를 생략한 경우 대부분의 컴파일러가 자동으로 0으로 초기화시키지만 그렇지 않을수 있음

7.6 요약 1. 1차원 배열은 동일한 자료형을 갖는 데이터의 리스트를 저장할 수 있는 자료구조이다. 이러한 배열을 선언할 때는 반드시 배열의 크기와 배열에 저장될 값에 대한 자료형이 주어져야 한다. 예를 들어 다음과 같은 선언문은100개의 정수를 저장할 수 있는 배열을 만든다 int num[100]; 2. 배열의 원소들은 메모리 상에서 연속적으로 저장되어지며, 배열의 이름과 첨자로써 참조된다(예: num[22]). 첨자로 음수는 사용될 수 없으며, 첨자 0은 항상 배열의 첫번째 원소를 가리킨다. 3. 2차원 배열은 행과 열의 값 모두를 지정함으로써 선언된다. 선언의 예는 다음과 같다. float rates[12][20]; 위 선언은 12행 20열의 실수형 값을 저장하기 위해 메모리 공간을 확보한다. 이차원 배열의 각 원소들은 행과 열의 첨자를 제공함으로써 접근 가능하다. 첫 행과 첫 열에 위치하는 원소는 행과 열의 첨자로 0(zero)을 갖는다. 4. 배열은 배열의 이름을 함수의 인자로 전달함으로서 함수에 전달된다. 실제적으로 전달 되는 값은 배열의 첫번째 원소가 저장된 주소값이다. 따라서 호출된 함수는 전달된 주소를 사용하여 배열의 복사본이 아니라 실제 배열에 직접 접근한다. 호출된 함수에서는 전달될 배열의 이름(실제로 주소임)을 받을 수 있도록 인자를 선언해야 한다. 인자의 선언시 일반적으로 배열의 행의 크기는 생략할 수 있다.

7.7 보충 설명 검색과 정렬의 필요성 검색 알고리즘 실험 결과로 발생한 자료의 정렬 리스트 내에 있는 특정한 이름을 찾는 작업 검색 알고리즘 선형 검색 : 알고리즘이 간단하며, 자료들이 정렬될 필요가 없음 이진 검색 : 자료들이 정렬되어 있는 경우 적용이 가능하며, 선형 검색보다 빠름

7.7 보충 설명 선형 검색 : 프로그램 7-8 #include <stdio.h> #define TRUE 1 #define FALSE 0 #define NUMEL 10 void main(void) { int nums[NUMEL] = {5,10,22,32,45,67,73,98,99,101}; int item, location; int linearSearch(int[], int, int); printf(“Enter the item you are searching for: “); scanf(“%d”, &item); location = linearSearch(nums, NUMEL, item); if (location > -1) printf(“The item was found at index\ location %d \n”, location); else printf(“The item was not found in the array\n”); } linearSearch(int list[], int size, int key) { /* this function returns the location of key in the list */ /* a 1 is returned if the value is not found */ int index=-1, found, i; found = FALSE; i = 0; while(i<size && ! found) { if (list[i] == key) { found = TRUE; index = i; } i++; return(index);

7.7 보충 설명 이진 탐색의 원리 순서화된 리스트에서 찾는 아이템을 리스트의 중앙에 위치한 원소와 비교한다. 비교 결과 다음 3가지 가능성이 존재한다. (1) 요구되어진 아이템이 중앙 원소와 같을 경우 검색이 성공적으로 완료되었으며, 더 이상의 검색은 필요하지 않다. (2) 중앙 원소보다 큰 값을 가질 경우 찾고자 하는 아이템이 중앙 원소보다 큰 값을 갖기 때문에, 그 아이템은 반드시 중앙값을 기준으로 리스트의 뒷부분에 존재하게 된다. 즉, 처음부터 중앙에 위치한 원소까지의 앞부분은 다음으로 진행될 검색에서 제외시키고 뒷부분을 갖고서 이진 탐색을 순환적으로 호출한다. (3) 중앙 원소보다 작은 값을 가질 경우 찾고자 하는 아이템이 중앙 원소보다 작기 때문에, 그 아이템은 반드시 리스트의 전반부에 존재하게 된다. 즉, 중앙 원소부터 뒷부분은 앞으로 진행될 검색에서 제외되며, 리스트의 앞부분을 가지고 이진 탐색을 순환적으로 호출한다.

7.7 보충 설명 이진 탐색 binarySearch(int list[], int size, int key) { #include <stdio.h> #define TRUE 1 #define FALSE 0 #define NUMEL 10 void main(void) { int nums[NUMEL] = {5,10,22,32,45,67,73,98,99,101}; int item, location; int binarySearch(int[], int, int); printf(“Enter the item you are searching for: “); scanf(“%d”, &item); location = binarySearch(nums, NUMEL, item); if (location > -1) printf(“The item was found at index\ location %d \n”, location); else printf(“The item was not found in the array\n”); } binarySearch(int list[], int size, int key) { int index, found, left, right, midpt; index = -1; found = FALSE; left = 0; right = size -1; while (left <= right && !found) { midpt = (int)((left+right)/2); if (key == list[midpt]) { found = TRUE; index = midpt; } else if (key > list[midpt]) left = midpt + 1; else right = midpt -1; return(index);

7.7 보충 설명 정렬 알고리즘 선택 정렬의 원리 Initial List Pass1 Pass2 Pass3 Pass4 외부 정렬 알고리즘 : 디스크를 사용 내부 정렬 알고리즘 : 주 메모리만 사용 선택 정렬 : 프로그램 7-10 교환 정렬 : 프로그램 7-11 선택 정렬의 원리 Initial List Pass1 Pass2 Pass3 Pass4 690 32 32 32 32 307 307 155 155 155 32 690 690 307 307 155 155 307 690 426 426 426 426 426 690

7.7 보충 설명 최대값 두번째 큰값 교환 정렬의 원리 1st Pass 2nd Pass …. 690 307 307 307 307 32 32 307 690 32 32 32 307 155 32 32 690 155 155 155 307 155 155 155 690 426 426 426 426 426 426 426 690 690 690 최대값 두번째 큰값