제 3 강. 배열 (Array) 자료구조 1
제 3 강. 배열자료구조 학습목차 1. 배열의개념 2. 구조체 3. 희소 (Sparce) 행렬 4. 다차원배열의저장 2
1. 배열의개념 리스트는일상생활에서가장많이쓰이는자료형태이다. 예 ) 학생의명단, 은행거래고객명단, 월별판매액등 배열 (Array) 은컴퓨터언어에서리스트를저장하는데이터타입이다. 리스트와배열은같은개념이지만다른차원의용어이다. C 언어로표현된리스트의예 int student[100]; /* 학생의번호 100 개 */ char name[100][]; /* 문자배열의배열 */ int sales[12]; /* 월판매액 12개 */ 3
배열에관한연산 ( 생성, 삽입, 삭제등 ) - 새로운배열의생성예 ) int x[5]; /* 언어에따라첨자는 0혹은 1에서시작 C 는 0부터시작한다. */ integer integer integer integer integer x[0] x[1] x[2] x[3] x[4] - 순서 (order) 를유지하는배열에서데이터의삽입과삭제 - 배열에값을삭제 integer ( 나머지값을한칸씩이동 ) 삽입 X[0] X[1] X[2] X[3] X[4] integer integer integer integer integer X[0] X[1] X[2] X[3] X[4] integer integer integer integer integer 삭제 - 배열에새로운값삽입 ( 나머지값들을한칸씩이동 ) integer 4
배열과기억장소 배열은기억장소에서연속된위치를차지한다. 예 ) int list[5]; /* sizeof() 함수는데이터의길이를 byte로반환하는함수 */ /* C 언어에서 sizeof(int) 의값은 2 byte 이지만시스템에따라서 4 byte 인경우도있다. */ 변수 기억장소주소 list[0] 시작주소값 ) list[1] + sizeof(int) list[2] + 2 sizeof(int) list[3] + 3 sizeof(int) list[4] + 4 sizeof(int) 5
포인터타입이란? 포인터타입은데이터가기억장소의주소를저장하는타입이다. 사람이사는모든집에 주소 가있고컴퓨터의기억장소도 주소 가있다. 기억장소 -> 기억장소의주소 -> 주소를저장하는기억장소 1020 번지 777 1020 번지 1020 기억장치 ( 정수저장 ) 기억장소주소 주소를기억하는변수 ( 포인터변수 ) 서울시하늘동 100 번지 서울시하늘동 100 번지 장소 ( 집 ) 주소 주소를기록한종이 6
포인터타입예 int x; /* 내용을저장하는변수 */ int *y; /* 주소를저장하는변수 */ int z; x = 10; /* 내용 10을저장 */ y = &x; /* 변수 x의주소를저장 */ Z = *y; /* 주소 y가가리키는곳의내용을저장 */ /* z = x와같은의미가된다. */ int a[20]; /* 배열변수 a는주소값으로처리한다. */ /* 그이유는배열의내용전체를이동할경우보다주소값을알려주면편하기때문이다. */ 7
[ 포인터타입예 1 ] - * 연산자와 [] 연산자, & 연산자 #include <stdio.h> void main( ) { int iarr[5] ={10, 20, 30, 40, 50}; printf("%d %d %d %d %d\n", iarr[0], iarr[1], iarr[2], iarr[3], iarr[4]); printf("%d %d %d %d %d\n", *(iarr+0), *(iarr+1), *(iarr+2), *(iarr+3), *(iarr+4)); printf("%d %d %d %d %d\n", *&iarr[0], *&iarr[1], *&iarr[2], *&iarr[3], *&iarr[4]); } 8
[ 포인터타입예 2 ] - 문자와정수형데이터의저장길이 #include <stdio.h> void main ( ) { char carr[5] = {'A', 'B', 'C', 'D', 'E'}; printf("%x %x %x %x %x\n", carr, carr+1, carr+2, carr+3, carr+4); } #include <stdio.h> void main( ) { int iarr[5] ={10, 20, 30, 40, 50}; printf("%x %x %x %x %x\n", iarr, iarr+1, iarr+2, iarr+3, iarr+4); } 9
[ 포인터타입예 3 ] - char 형배열주소의연산 #include <stdio.h> void main ( ) { char carr2[2][2] = {'A','B','C','D'}; printf("%x %x %x %x\n", &carr2[0][0], carr2, carr2[0], carr2[1]); printf("%x %x %x %x\n", &carr2[0][0]+1, carr2+1, carr2[0]+1, carr2[1]+1); } 10
- char 형배열주소의연산 배열에대표주소 배열행에대표주소 carr2 carr2[0] 12ff7c 65 ( A ) carr2[0][0] +1 +1 carr2[1] 12ff7d 12ff7e 66 ( B ) 67 ( C ) carr2[0][1] carr2[1][0] +1 12ff7f 68 ( D ) carr2[1][1] 12ff80 char carr2[2][2] 11
- 배열에대한예제프로그램 #define MAX_SIZE 100 float sum(float [], int); int i; 전역변수선언 void main(void) { 주프로그램 float input[max_size], answer; for(i=0; i < MAX_SIZE; i++) input[i] = (float)i; answer = sum(input, MAX_SIZE); printf( The sum is: %f\n, answer); } float sum(float list[], int n) { int i; float tempsum = 0; for(i= 0; i < n; i++) tempsum += list[i]; return tempsum; } 함수프로그램 12
- 배열에대한예제프로그램 선언부분설명 /* 이부분에선언된변수들은프로그램전체에서사용한다 */ #define MAX_SIZE 100 /* 상수 MAX_SIZE 값을 100으로선언한다 */ float sum(float [], int); /* 함수 sum() 을선언한다. 미리선언을해야 main() 에서인식을한다. */ int i; /* 정수형변수 I 선언 */ 13
- 배열에대한예제프로그램 main() 프로그램설명 /* C 프로그램에서 main() 은반드시 1개있어야한다. */ int main( ) { float input[max_size], answer; /* 실수형배열변수 input[], answer 선언 */ /* for 문은 for( 초기문, 조건문, 실행문 ) 반복문 ; 으로초기문장은 1번실행하고조건문이 false나 0이될때까지조건문-> 반복문-> 실행문을반복실행한다. */ for(i=0; i < MAX_SIZE; i++) input[i] = (float)i; /* for 문을실행하여 input[i] = I 문장을 100번반복실행한다. input[] 배열을초기화시킨다.*/ answer = sum(input, MAX_SIZE); /* 함수 sum() 을호출한다. 인자는배열 input과 MAX_SIZE 이다. */ printf( The sum is: %f\n, answer); /* 결과를출력하는문장이다. */ } 14
- 배열에대한예제프로그램 함수 sum() 설명 /* 함수는인자를받아서결과를반환한다. sum() 의인자는 list[] 와 n이다. */ float sum(float list[], int n) { int i; /* 변수 i의선언, 함수안에서만사용할수있다 */ float tempsum = 0; for(i= 0; i < n; i++) tempsum += list[i]; /* tempsum += list[i]; 문장을 n번실행한다 */ return tempsum; /* tempsum 값을반환한다. */ } 15
2 구조체 (Structures) - 구조체는데이터를표현하는단위이다. 예 ) 학생의명단, 은행거래고객명단, 월별판매액등 그러나학생의명단은학생의학번과이름, 주소고객명단은고객의이름, 주소, 계좌번호등으로여러개의작은값 ( 필드 ) 들이합해서한개의데이터를구성한다. 이러한데이터타입은복합데이터에해당된다. 복합데이터를 1개의변수로표현하는방법은구조체 (structure) 를사용한다. - 구조체는각데이터가타입과이름을갖는다. 16
구조체의예 사람 (person) 데이터타입어떤사람의신상에관해컴퓨터에저장할때 3개의필드로구성된다고하자. 1) 이름 (name) 은문자배열로구성 2) 나이 (age) 는정수 (integer) 변수로구성 3) 급여 (salary) 는실수 (float) 변수로구성 C 언어로아래와같이선언이된다. struct { char name[10]; int age; float salary; } person; struct char [ ] integer float person name age salary 17
구조체에데이터저장 struct person person1; strcpy(person1.name, james ); /* strcpy() 함수는문자열을복사하는함수 */ person1.age = 10; person1.salary = 35000; struct james person1 name 10 age 35000 salary 18
typedef statement - - 구조체타입을선언한다. typedef struct human_being { char name[10]; int age; float salary; }; 혹은 typedef struct { char name[10]; int age; float salary; } human_being; type char [ ] integer float human_being name age salary 19
struct 타입 치환문 (assignment) - - struct 전체를치환한다 human_being person1, person2; person1 = person2; - struct 필드단위로치환한다. strcpy(person1.name, person2.name); person1.age=person2.age; person1.salary=person2.salary; 20
Struct 의배열 - 구조체의배열은다음과같이선언된다. struct { char name[10]; int age; float salary; } person; struct person lady[5]; lady[0] lady[1] lady[2] lady[3] lady[4] name Here!! age Here!! salary Here!! lady[3].name lady[2].age lady[1].salary 21
자기참조구조체 (Self-referential structures) 구조체의필드중하나가구조체에대한포인터를나타내는타입이다. 앞으로배울연결리스트, 트리, 그래프의구현에쓰이는방법이다. 다른구조체를연결하고있기때문에동적기억장소 (dynamic storage management) 구현에쓰이는방법이다 typedef struct list { char data; list *link; }; type char list * struct list data link Link 필드의값 - 기억장소에대한포인터로 list 타입을가리킨다. - 아무것도가리키지않으면 0(NULL) 값을갖는다. /* UNIX 시스템에서실제프로그램코드 */ struct node { int data; struct node * link; }; typedef struct node list_node; typedef list_node * list_ptr; 22
자기참조구조체노드선언 List_node item1, item2, item3; item1.data = a ; item2.data = b ; item3.data = c ; item1.link = item2.link = item3.link = NULL; item1 a item2 b item3 c 23
자기참조구조체의연결 item1 a item1.link=&item2; item2.link=&item3; item2 b item3 c 24
3. 희소 (Sparce) 행렬 - 배열의응용예 예 ) 행렬을프로그램에저장하려면다음과같이선언을하게된다. 열 0 열 1 열 2 열 3 열 4 열 5 행 0 15 0 0 22 0 15 int A[6,6] 행 1 0 11 3 0 0 0 행 2 0 0 0-6 0 0 행 3 0 0 0 0 0 0 행 4 91 0 0 0 0 0 행 5 0 0 28 0 0 0 행렬을표현하는데필요한기억장소의크기는 - m *n (m 행, n 열 ) - 공간복잡도 (space complexity) S(m, n) = m * n 25
만약 m과 n의값이크다면 (m=1000, n=10000), 행렬을표현하는데필요한기억장소의크기는? - 1000 * 10000 = 10,000,000 - 기억공간활용의비효율성 개선된방법의사용 - 큰행렬은값이 0인항이많다. 0이아닌항을 < 행, 열, 값 > 로저장한다. - 공간복잡도 (space complexity) S(m, n) = 3 * (0이아닌항의수 ) < m * n col 0 col 1 col 2 row 0-27 3 4 row 1 6 82-2 row 2 109-64 11 row 3 12 8 9 row 4 48 27 47 26
C 언어로희소행렬의자료구조를선언하면다음과같다. #define MAX_TERMS 101 typedef struct { int col; int row; int value; } term; term a[max_terms]; - a[0].row: 행의수 - a[0].col: 열의수 - a[0].value: 0이아닌항의수 27
희소 (sparse) 행렬의표현된모습 row col value a[0] [1] [2] [3] [4] [5] [6] [7] [8] 6 0 0 0 1 1 2 4 5 6 0 3 5 1 2 3 0 2 8 15 22 15 11 3-6 91 28 - 공간복잡도 (space complexity) S(n, m) = 3 * t where t: 0이아닌항의수 - 공간복잡도는행과열의수에무관하며 0 이아닌값과관계있다. 28
4. 다차원배열의저장 1차원배열은기억장소에순서대로저장한다. N차원배열이어떻게 1차원의물리적인기억장소에저장이될까? N차원배열의임의의원소는기억장소의어디에저장되어있는가? int a[upper0][upper1] [uppern-1] /* 선언 */ 배열의 전체원소의수 n-1 upperi i=0 예 ) int a[6][7][8] 으로선언될때 - 전체원소의수 = 6 * 7 * 8 = 336 (units) 29
다차원배열의저장방법 - 행우선저장 (row major order) 1행, 2행, 3행 순으로저장 - 열우선저장 (column major order) 1열, 2열, 3열 순으로저장 예 ) 행우선저장 (rows major order) 으로저장했을때 : a[0][0] [0] a[0][0] [1] 시작주소 a[0][0] [uppern-1-1] a[0] [1][0] a[0] [1][uppern-1-1] a[0] [2][0] a[1][0] [0] 30
a[2][5] [3] 항은기억장소의어디에있을까? - 시작주소 + 시작부터의위치 - : 시작주소라고가정 1 차원배열 a[u0] 에서 a[i] 은? a[0] : a[1] : + 1 a[u0-1] : + (u0-1) a[i] = + i 예 ) int x[8] 로선언되어있을때, x[0] 의주소가 100번지이면, x[5] 의주소는?(integer 형이기억장소를 2 byte 차지한다고가정 ) -> int[5] 의주소 = 100 + 5 X 2 = 110 번지 31
2 차원배열에서 a[u0][u1] 는? i 0 1 u 1-1 0 +1 +(u 1-1) 1? u 0-1 a[i][j] = + i u 1 + j j 예 ) int x[4][5] 로선언되어있을때, x[0][0] 의주소가 100 번지이면, X[2][3] 의주소는? ( 행우선저장, integer 형이기억장소를 2 byte 차지한다고가정 ) -> X[2][3] 의주소 = 100 + 2 ( 2 X 5 + 3 ) = 126 번지 32
3 차원배열에서 a[u0][u1][u2] 는? a[i][j][k] = + i u1 u2 + j u2 + k = + u2[i u1 + j] + k 예 ) int x[3][4][5] 로선언되어있을때, x[0][0][0] 의주소가 100 번지이면, int[2][3][4] 의주소는? ( 행우선저장, integer 형이기억장소를 2 byte 차지한다고가정 ) -> X[2][3][4] 의주소 = 100 + 2 ( 2 X 4 X 5 + 3 X 5 + 4 ) 예 ) int x[3][4][5] 로선언되어있을때, x[0][0][0] 의주소가 100 번지이면, int[2][3][4] 의주소는? ( 열우선저장, integer 형이기억장소를 2 byte 차지한다고가정 ) -> X[2][3][4] 의주소 = 100 + 2 ( 2 + 3 X 3 + 4 X 3 X 4 ) N 차원배열의경우 a[u0][u1] [un-1] 는? a[i0][i1] [in-1] = + ij aj, aj = uk, 0 < j < n-1 an-1 = 1 33
Q/A 1. ( 배열의저장 ) 시작위치가 100 이고원소의길이가 4 바이트인 1 차원리스트가배열에저장되어있을때 9 번째원소의주소는얼마인가? 2. (2 차원배열의저장 ) 행우선저장방식의 2 차원배열 int A[5][3] 에서 A[3][1] 은몇번째원소인가? 3. (2 차원배열의저장 ) 행우선저장방식의 2 차원배열 int A[5][3] 에서 A[3][1] 의주소는? A[0][0] 은 100 번지에저장되어있고 int 는 4 바이트씩차지한다. 4. (3 차원배열의저장 ) 열우선저장방식의 3 차원배열 int A[5][3][4] 에서 A[3][1][2] 의주소는? A[0][0][0] 은 100 번지에저장되어있고 int 는 4 바이트씩차지한다. 34
Review 리스트는가장많이사용되는자료의형태이다. 배열은프로그램언어에서데이터타입이다. 리스트를배열을이용하면쉽게표현할수있다. 다차원배열을기억장소에표현하는방법은행우선과열우선방법이있다. 구조체는여러개의다른데이터를한개의데이터로묶는데사용한다. 구조체의특별한형태로자기참조구조체가있다. ( 일상생활데이터 ) ( 컴퓨터데이터 ) 이름, 나이, 주민등록번호데이터들나이의모임, 이름의모임배열한사람에관한데이터 ( 이름, 나이, ) 구조체여러사람의데이터구조체의배열 포인터타입 ( 주소값 ) 데이터가저장된기억장소주소를다루는타입을포인터타입이라한다. 선언은 *, 변수의주소값은 &, 주소값의참조는 * 연산자를이용한다. 배열변수는자동으로포인터형으로선언된다. 35