Array, Structure, and Pointer 2019 SANGJI University Kwang-Man Ko ()
배열 (array) 이란? 같은형의변수를여러개만드는경우에사용 int A0, A1, A2, A3,,A9; int A[10]; 0 1 2 3 4 5 6 7 8 9 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[0]; for(i=1;i<n;i++){ if( score[i] > tmp ) tmp = score[i]; } Array, Structure, and Pointer 2
배열 (array) 동일자료형 (same type) 의자료들이순서 (linear) 있게구성된집합 연속된기억공간차지 유한한개수의자료가저장됨 직접접근 (direct access) 기준위치에대한상대적위치를나타내는인덱스 (index) 를사용하여가능 Array, Structure, and Pointer 3
int A[10]; 배열을구성하는원소의개수 (size) : 10 인덱스 : 0, 1,, 9 배열을구성하는각원소의자료형 : int 배열이차지는연속된기억공간의크기 4 byte * 10 = 40 byte 시작주소 (base) A[0] A[1] A[9] 인덱스 ( 첨자 ) 배열이름 : 기억장소의시작위치 ( 주소 ) Array, Structure, and Pointer 4
배열의선언과생성 배열의선언 (declaration) 과생성 자료형 배열이름 배열의크기 배열예 ( in C) 자료형배열이름 [ 배열크기 ] ; int A[10] ; 시작주소 (base) : A A[0] A[1] A[9] Array, Structure, and Pointer 5
선언 (declaration) Java 에서배열의선언과생성 생성될배열시작위치저장 ( 배열이름 ) int dsint [] ; 1) int dsint [] 생성 (creation) 힙메모리에서배열크기만큼의기억공간을 할당한후시작주소를배정 dsint = new int[3] ; 2) dsint = new int[3] 3) 생성된배열의시작주소전달 dsint[0] dsint[1] dsint[2] Array, Structure, and Pointer 6
배열의생성과초기화 int array[3]; int array[3] = { 1, 2, 3 } ; int array[] = { 1, 2, 3 } ; 배열의크기가초기값의수에따라결정 위배열의크기? Q) Java 언어를사용하여동일하게선언과생성하면? Array, Structure, and Pointer 7
1 차원배열 배열의종류 가장간단한형태로서길이가 n으로초기화된배열 0에서 n-1까지의전체 n개의자료저장가능 일차원배열의선언과생성 int array[10] ; // in C/C++ int array = new int[10] ; // in Java 순차매핑 (sequential mapping) 배열의논리적순서와메모리의물리적순서를같게표현 순차표현 (sequential representation) 순차매핑을이용하여자료표현 Array, Structure, and Pointer 8
예 ) int A[6] ; A[0] A[1] A[2] A[3] A[4] A[5] base+sizeof(int) base+5*sizeof(int) base int dsint = new int[10]; Array, Structure, and Pointer 9
2 차원배열 int A[3][4]; A[0][0] A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] A[2][0] A[2][1] A[2][2] A[0][3] A[1][3] A[2][3] A[0][1] A[0][2] A[0][3] A[1][0] A[2][3] 실제메모리안에서의위치 Array, Structure, and Pointer 10
다차원배열 (Multi dimensional array) 여러개의일차원배열들의중첩된구조 다차원배열을실제일차원메모리에표현하는방법? 행우선방법, 열우선방법 Array, Structure, and Pointer 11
다차원배열 => 일차원배열매핑 행우선순서방법 (row major order) 이차원배열을 행 별로분할 분할된행들을차례로연결 하나의가상적인일차원배열로매핑 열우선순서방법 (column major order) 이차원배열을 열 별로분할 분할된열들을차례로연결 하나의가상적인일차원배열로만들어매핑 Array, Structure, and Pointer 12
열 / 행우선방법 (row/column-major order) in C int array [2][3] = { {1,2,3}, {4,5,6} }; 1 2 3 열 (row) 우선방식 (1, 2, 3, 4, 5, 6) 4 5 6 행 (column) 우선방식 (1, 4, 2, 5, 3, 6) Array, Structure, and Pointer 13
열 / 행우선방법 (row/column-major order) in Java int array ; // 선언 array = new int[2][3] ; // 생성 array = new int[2][3] = { {1,2},{3,4},{5,6} } ; // 초기화 기억공간표현? Array, Structure, and Pointer 14
인덱스를통한직접접근 배열원소의접근 배열은메모리상에연속된기억공간차지 인덱스의계산을통해해당객체에직접접근 크기 n의배열, 인덱스범위 0 n-1 배열이름은메모리상에서배열의시작위치. &array[i] = &array[0] + ( i * sizeof( type) ) &array[0] = &array[0] + ( 0 * sizeof( int ) ) = 1000 &array[1] = &array[0] + ( 1 * sizeof( int ) ) = 1004 &array[2] = &array[0] + ( 2 * sizeof( int ) ) = 1008 &array[3] = &array[0] + ( 3 * sizeof( int ) ) = 1012 참고, &array[0] = 1000, sizeof(int) = 4 Array, Structure, and Pointer 15
int array[4] = {10, 20, 30, 40}; //in C 메모리주소 array = &array[0] = 1000 1000 10 array[0] 1004 20 array[1] 1008 30 array[2] 1012 40 array[3] Array, Structure, and Pointer 16
int array = new int[4]; 1) int array[] 2) array = new int[4] 3) 생성된배열의시작주소전달 4) 초기화 array[0] array[1] array[2] array[3] Array, Structure, and Pointer 17
일차원배열초기화 (in Java) 배열의초기화 배열을선언하고생성한다음에초기화를하는방법 int [ ] dsint; // 배열선언 dsint = new int [10]; // 배열생성 dsint [0] = 12; // 배열의초기화 dsint [1] = 53; 배열을동시에선언하고생성한후에초기화를하는방법 int dsint [ ] = new int [10]; // 배열선언및생성 dsint [0] = 12; // 배열의초기화 dsint [1] = 53; 일차원배열초기화 (in C)??? Array, Structure, and Pointer 18
기억장소할당방법 프로그램이메모리를할당받는방법 정적 (static) 메모리할당 => 스택 (stack) 동적 (dynamic) 메모리할당 => 힙 (heap) 정적메모리할당 (static memory allocation) 메모리의크기는프로그램이시작하기전에결정 컴파일시간에기억장소의크기결정, 실행시불변. 프로그램의수행도중에그크기가변경될수는없음. 처음에결정된크기보다더큰입력이들어온다면처리하지못할것이고더작은입력이들어온다면남은메모리공간은낭비. 예, 변수나배열의선언 int buffer[100]; char name[] = data structure"; Array, Structure, and Pointer 19
동적메모리할당 (dynamic memory allocation) 프로그램의실행도중에메모리를할당받는것 필요한만큼만할당을받고또필요한때에사용하고반납 메모리를매우효율적 (= 탄력적 ) 으로사용가능 main() { int *pi; pi = (int *) malloc( sizeof(int) );...... free(pi); } // 동적메모리할당 // 동적메모리사용 // 동적메모리반납 Array, Structure, and Pointer 20
동적메모리할당관련라이브러리함수 ( in C ) malloc(size) // 메모리할당 free(ptr) // 메모리할당해제 sizeof(var) // 변수나타입의크기반환 ( 바이트단위 ) 동적메모리할당방법 ( in C++ )? 동적메모리할당방법 ( in Java )? Array, Structure, and Pointer 21
배열연산 검색 (search) 삽입 (insert) 삭제 (delete) Array, Structure, and Pointer 22
순차배열 배열응용 : 순차배열 배열내에저장된값들이어떤일정한규칙에의해정렬 오름차순, 내림차순, 빠른검색제공 첨가시에매우많은시간필요 배열에저장되어있는값들을서로비교 정해진자리에값을삽입 자리이동 Array, Structure, and Pointer 23
다항식의일반적인형태 배열의응용 : 다항식 n p( x) a x a a x a n n 1 n 1 x... 1 0 프로그램에서다항식을처리하려면다항식을위한자료구조가필요 어떤자료구조를사용해야다항식의덧셈, 뺄셈, 곱셈, 나눗셈연산을할때편리하고효율적일까? 배열을사용한 2 가지방법 1) 다항식의모든항을배열에저장 2) 다항식의 0 이아닌항만을배열에저장 Array, Structure, and Pointer 24
다항식표현방법 #1 모든차수에대한계수값을배열로저장 하나의다항식을하나의배열로표현 5 4 3 2 1 0 10x 0x 0x 0x 6x 3x 0 1 2 3 4 5 6 7 8 9 10 coef 10 0 0 0 6 3 typedef struct { int degree; float coef[max_degree]; } polynomial; polynomial a = { 5, {10, 0, 0, 0, 6, 3} }; Array, Structure, and Pointer 25
동일자료형 vs. 이질자료형 배열 구조체 필드 0 1 Array, Structure, and Pointer 26
구조체 구조체 (structure): 타입이다른데이터를하나로묶는방법 배열 (array): 타입이같은데이터들을하나로묶는방법 배열 구조체 필드 0 1 char carray[100]; struct example { char cfield; int ifield; float ffield; double dfield; }; struct example s1; Array, Structure, and Pointer 27
구조체의사용예 구조체의선언과구조체변수의생성 struct person { char name[10]; int age; float height; }; struct person a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 구조체변수선언 typedef 을이용한구조체의선언과구조체변수의생성 typedef struct person { char name[10]; int age; float height; } person; person a; // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 구조체변수선언 Array, Structure, and Pointer 28
구조체의대입과비교연산 구조체변수의대입 : 가능 struct person { char name[10]; int age; float height; }; main( ) { person a, b; b = a; } // 문자배열로된이름 // 나이를나타내는정수값 // 키를나타내는실수값 // 가능 구조체변수끼리의비교 : 불가능 main( ) { } if( a > b ) printf("a 가 b 보다나이가많음 "); // 불가능 Array, Structure, and Pointer 29
자체참조구조체 자체참조구조체 (self-referential structure): 필드중에자기자신을가리키는포인터가한개이상존재하는구조체 연결리스트나트리에많이등장 typedef struct ListNode { char data[10]; struct ListNode *link; } ListNode; Array, Structure, and Pointer 30
포인터 (pointer) 포인터 : 다른변수의주소를가지고있는변수 26 주소 char a='a'; char *p; p = &a; 26 포인터 p A 변수 a 포인터가가리키는내용의변경 : * 연산자사용 주소 *p= 'B'; 26 26 B 포인터 p 변수 a Array, Structure, and Pointer 31
포인터와관련된연산자 & 연산자 : 변수의주소를추출 *p 주소 26 &a * 연산자 : 포인터가가리키는곳의내용을추출 26 포인터 p A 변수 a p // 포인터 *p // 포인터가가리키는값 *p++ // 포인터가가리키는값을가져온다음, 포인터를한칸증가. *p-- // 포인터가가리키는값을가져온다음, 포인터를한칸감소. (*p)++ // 포인터가가리키는값을증가. Array, Structure, and Pointer 32
int a; // 정수변수선언 int *p; // 정수포인터선언 int **pp; // 정수포인터의포인터선언 p = &a;// 변수 a와포인터 p를연결 pp = &p; // 포인터 p와포인터의포인터 pp를연결 Array, Structure, and Pointer 33
포인터의종류 void *p; int *pi; float *pf; char *pc; int **pp; 디양한포인터 // p 는아무것도가리키지않는포인터 // pi 는정수변수를가리키는포인터 // pf 는실수변수를가리키는포인터 // pc 는문자변수를가리키는포인터 // pp 는포인터를가리키는포인터 struct test *ps; // ps 는 test 타입의구조체를가리키는포인터 void (*f)(int) ; // f 는함수를가리키는포인터 포인터의형변환 : 필요할때마다형변환가능 void *p; pi=(int *) p; Array, Structure, and Pointer 34
배열과포인터 배열의이름 : 사실상의포인터와같은역할 10 14 18 22 26 30 A[0] A[1] A[2] A[3] A[4] A[5] A 컴파일러가배열의이름을배열의첫번째주소로대치 Array, Structure, and Pointer 35
구조체의포인터 구조체의요소에접근하는연산자 : -> 98 ps 98 2 3.14 s.i = ps->i s.f = ps->f s main( ) { struct { } int i; float f; } s, *ps; ps = &s; ps->i = 2; ps->f = 3.14; Array, Structure, and Pointer 36
포인터의포인터 89 56 26 56 포인터의포인터 pp 26 포인터 p A 변수 a int a; int *p; int **pp; p = &a; pp = &p; // 정수변수변수선언 // 정수포인터선언 // 정수포인터의포인터선언 // 변수 a와포인터 p를연결 // 포인터 p와포인터의포인터 pp를연결 Array, Structure, and Pointer 37
포인터연산 포인터에대한사칙연산 : 포인터가가리키는객체단위로계산 p // 포인터 p+1 // 포인터 p가가리키는객체의바로뒤객체 p-1 // 포인터 p가가리키는객체의바로앞객체 10 14 18 22 26 30 A[0] A[1] A[2] A[3] A[4] A[5] p-1 p p+1 Array, Structure, and Pointer 38
포인터사용시주의할점 포인터가아무것도가리키고있지않을때는 NULL 로설정 int *pi=null; 초기화가안된상태에서사용금지 main() { char *pc; *pc = 'E ; } // 포인터 pi는초기화가안되어있음 // 위험한코드 포인터타입간의변환시에는명시적인타입변환사용 int *pi; float *pf; pf = (float *)pi; Array, Structure, and Pointer 39
동적메모리할당 프로그램이메모리를할당받는방법 정적메모리 (static memory) 동적메모리 (dynamic memory) 정적메모리할당 메모리의크기는프로그램이시작하기전에결정 프로그램의수행도중에그크기가변경될수는없다. 만약처음에결정된크기보다더큰입력이들어온다면처리하지못할것이고더작은입력이들어온다면남은메모리공간은낭비될것이다. ( 예 ) 변수나배열의선언 int buffer[100]; char name[] = data structure"; 동적메모리할당 프로그램의실행도중에메모리를할당받는것 필요한만큼만할당을받고또필요한때에사용하고반납 메모리를매우효율적으로사용가능 Array, Structure, and Pointer 40
동적메모리할당 전형적인동적메모리할당코드 main( ) { int *pi; pi = (int *)malloc(sizeof(int));...... free(pi); } // 동적메모리할당 // 동적메모리사용 // 동적메모리반납 동적메모리할당관련라이브러리함수 malloc(size) free(ptr) // 메모리할당 // 메모리할당해제 sizeof(var) // 변수나타입의크기반환 ( 바이트단위 ) Array, Structure, and Pointer 41
malloc(int size) 동적메모리할당라이브러리 size 바이트만큼의메모리블록을할당 (char *)malloc(100) ; /* 100 바이트로 50 개의정수를저장 */ (int *)malloc(sizeof(int));/* 정수 1 개를저장할메모리확보 */ (struct Book *)malloc(sizeof(struct Book))/* 하나의구조체생성 */ free(void ptr) ptr 이가리키는할당된메모리블록을해제 sizeof 키워드 변수나타입의크기반환 ( 바이트단위 ) size_t i = sizeof( int ); // 4 struct AlignDepends { char c; int i; }; size_t size = sizeof(struct AlignDepends); // 8 int array[] = { 1, 2, 3, 4, 5 }; size_t sizearr = sizeof( array ) / sizeof( array[0] ); // 20/4=5 Array, Structure, and Pointer 42
동적메모리할당예제 struct Example { int number; char name[10]; }; void main() { struct Example *p; } p=(struct Example *)malloc(2*sizeof(struct Example)); if(p==null){ fprintf(stderr, "can't allocate memory\n") ; exit(1) ; } p->number=1; strcpy(p->name,"park"); (p+1)->number=2; strcpy((p+1)->name,"kim"); free(p); Array, Structure, and Pointer 43