C 언어이론 2006. 12. 15 PLATFORM TEAM 정용학
차례 배열과포인터 구조체와공용체 자료구조 C 언어숙지사항 2
배열과포인터 - 배열 배열의정의와형식 동일한데이터형을저장할수있는변수들의연속된집합 자료형배열명 [ n ] int temp[3]; 배열의크기 변수명 저장된값 메모리주소 초기화 sizeof(int) * 3 = 12Byte int temp[3] = { 1, 2, 3 }; temp[0] 1 0x 001F2000 0x 001F2001 0x 001F2002 0x 001F2003 int temp = { 1, 2 }; 0x 001F2004 int temp[4] = { 1 }; int temp[4] = { 0 }; temp[1] 2 0x 001F2005 0x 001F2006 0x 001F2007 0x 001F2008 4 Byte 씩차이가남 temp[2] 3 0x 001F2009 0x 001F200A 0x 001F200B 3
배열과포인터 - 다차원배열 2 차원배열 자료형배열명 [ 행의개수 ] [ 열의개수 ] int temp[3][2]; 배열의크기 = 3 * 2 * sizeof(int) = 24Byte 초기화 int temp[3][2] = { { 10, 20 }, { 30, 40 }, { 50, 60 } }; int temp[3][2] = { 10, 20, 30, 40, 50, 60 }; int temp[3][2] = { {10, 20 }, { }, { 50, 60 } }; 다차원배열 자료형배열명 [ 크기 1 ] [ 크기 2 ] [ 크기 3 ] [ 크기 n ] 크기제한없으나사용빈도적음 4
배열과포인터 - 포인터 포인터의정의와형식 메모리내의특정위치의주소 를값으로갖는변수 자료형 * 변수명 포인터변수에주소저장시는번지연산자 (&) 사용 가리키는주소의값참조시별표연산자 (*) 사용 int* ptr; int x = 10; ptr = &x; printf( %d,*ptr); 변수명 x 저장된값 10 메모리주소 0x 001F201A 0x 001F201B 0x 001F201C 0x 001F201D..... 0x 33002105 ptr 001F201A 0x 33002106 0x 33002107 0x 33002108 5
배열과포인터 - 포인터 포인터의메모리크기 데이터형에관계없이주소값을저장하기때문에메모리크기가같음 int*, char*, double*, float* 모두메모리크기가같음 운영체제마다메모리크기가틀리게나옴 포인터의자료형을정하는이유 포인터가가리키는메모리주소로이동후몇바이트를읽을지를결정하는요소이기때문 포인터사용장점 메모리효율적 속도빠름 6
배열과포인터 1 차원배열과포인터와의관계 배열명은배열의첫번째항목을가리키는포인터상수 1 차원배열에서값을참조하려면 * 가 1 개있어야함 int array[3] = {1,2,3}; array == &array[0]; *array == array[0]; * 기호 변수의시작주소를가리키는포인터 [ ] 기호 배열의시작주소를가리키는포인터 가리키는주소를변경할수없는상수 7
배열과포인터 1 차원배열과포인터와의관계 배열포인터에정수를더하면, 현재가리키는항목에서다음항목으로이동 int array[3]={1,2,3}; 변수명 저장된값 메모리주소 0x 001F2000 array == 0x001F2000 array[0] 1 0x 001F2001 0x 001F2002 0x 001F2003 0x 001F2004 array +1 == array + sizeof(int) * 1 == 0x001F2000 + (4*1) == 0x001F2004 array[1] 2 0x 001F2005 0x 001F2006 0x 001F2007 0x 001F2008 array +2 == array + sizeof(int) * 2 == 0x001F2000 + (4*2) == 0x001F2008 array[2] 3 0x 001F2009 0x 001F200A 0x 001F200B *(array +2) == *(0x001F2008) == 3 8
배열과포인터 2 차원배열과포인터와의관계 2 차원배열 자료형 (* 포인터명 ) [ 열의개수 ] int array [3][4]; int (* ptr)[4] = array; printf( %p, array); printf( %p, &array[0][0]); printf( %p, array[0]); printf( %p, array[1]); printf( %p, array[2]); printf( %p, ptr); printf( %p, ptr + 1); printf( %p, ptr + 2); printf( %p, array); printf( %p, array + 1); printf( %p, array + 2); ptr == array ptr == array[0] ptr == &array[0][0] ptr + 1 == array + 1 ptr + 1 == array[1] ptr + 1 == &array[1][0] *ptr == array[0] *(ptr + 1) == array[1] *(*(ptr + 0) + 0) == array[0][0] *(*(ptr + 0) + 1) == array[0][1] *(*(ptr + 0) + 2) == array[0][2] *(*(ptr + 1) + 0) == array[1][0] *(*(ptr + 1) + 1) == array[1][1] *(*(ptr + 1) + 2) == array[1][2] 9
배열과포인터 - 포인터배열 char (*ptr)[3] 열의개수가 3 개인 2 차원배열포인터 메모리할당 : 4Byte char* ptr[3] 주소를저장할수있는영역이 3 개인포인터배열 메모리할당 : 12Byte 10
배열과포인터 배열과포인터차이점 배열과포인터차이점 배열명은상수이기때문에배열명에주소를대입할수없다 배열명에 ++, -- ( 증감연산자 ) 사용불가 int array[3]; array++; //error 발생 배열은메모리가자동적으로설정, 포인터는설정되지않음 char str = hello ; char array[10]; char* ptr; strcpy(array, str); strcpy(ptr, str); //error 발생 여러개의문자열저장시배열보다포인터가메모리절약가능 11
배열과포인터 - 문자열 문자형배열을사용하여표현 char str1[8] = happy! ; 변수명 저장된값 메모리주소 str1[0] h 0x 001F2008 str1[1] a 0x 001F2009 str1[2] p 0x 001F200A str1[3] p 0x 001F200B str1[4] y 0x 001F200C str1[5]! 0x 001F200D str1[6] \0 0x 001F200E 문자열의끝을알려주는널문자 str1[7] \0 0x 001F200F 12
char* str2 = happy! ; 배열과포인터 - 문자열 변수명 저장된값 메모리주소 실행문 str2 0x001F2008 h a p p y! \0 0x001E0044 0x 001F2008 0x 001F2009 0x 001F200A 0x 001F200B 0x 001F200C 0x 001F200D 0x 001F200E printf( %s,str2); printf( %s,str2+1); printf( %s,str2+2); 출력결과 happy! appy! ppy! 13
배열과포인터 - 문자열관련함수 char* strcpy(char* dest, const char* src) src 문자열이 dest 로복사, dest 번지가 return char* strcat(char* dest, const char* src) dest 뒤에 src 를연결 int strcmp(const char* s1, const char* s2) s1과 s2가같으면 0 s1 > s2 이면양수 s1 < s2 이면음수 char* strstr(const char* string, const char* strsearch) string 에서 strsearch 를찾으면그포인터를 return, 없으면 NULL return char* strtok(char* strtoken, const char* strdelimit) strtoken 에서구분자 strdelimit 을이용하여토큰으로잘라냄 14
배열과포인터 - 문자열관련함수 char* strchr(const char* string, int c) string문자열중에 c라는문자가있으면그포인터를 return 찾을대상이없는경우 NULL return char* strset(char* string, int c) 문자열을 c 문자로채움 char* strlwr(char* string) 모든문자를소문자로바꿈 char* strupr(char* string) 모든문자를대문자로바꿈 char* strrev(char* string) 문자열을거꾸로뒤집음 15
배열과포인터 - 이중포인터 포인터의포인터 포인터변수의주소를저장 참조연산자 2개사용 (**) 변수명 저장된값... 메모리주소 0x 001F2000 int x = 10; int* ptr; int** pptr; x 10 0x 001F2001 0x 001F2002 0x 001F2003 0x 001F2004 ptr = &x; ptr 001F2000 0x 001F2005 0x 001F2006 pptr = &ptr; 0x 001F2007... 0x 002F2008 pptr 001F2004 0x 002F2009 0x 002F200A 0x 002F200B 16
배열과포인터 - 널포인터 널포인터 포인터의초기화, 가리키고있는것이없음 int* ptr = NULL; 에러체크 int *ptr = (int *)malloc(sizeof(int)); if(ptr == NULL){ //error } 일반변수의초기화 main 문밖에서선언하고초기화안하면 0 으로초기화 main 문안에서선언하고초기화안하면쓰레기값이저장 17
배열과포인터 - void 형포인터 void 형포인터 자료형이정해져있지않은포인터 가리키는대상의실제값을읽기위해서는캐스팅연산자사용 void* ptr; c(char) x 0x 001F2000 0x 001F2004 i(int) 36... void 포인터 ptr f(float) 1.5 0x 001F2007 0x 001F2008... 0x 001F200B 0x 001F200C float f; void* ptr; ptr = &f; printf( %.2f, *(float *)ptr ); d(double) 7.23... 0x 001F2013 18
배열과포인터 함수포인터 함수포인터 함수의메모리시작주소를저장하는포인터 리턴형 (* 변수명 ) ( 인자...) int sum(int a, int b); int (*ptr)(int, int); int val; ptr = sum; // ptr = val = (* ptr)(31, 4); // val = ptr(31,4) 함수포인터배열 int (*ptr[3])(int, int); ptr[0] = &Plus; ptr[1] = &Minus; ptr[2] = &Multi; 19
배열과포인터 동적메모리할당 정적할당과동적할당 정적할당 : 컴파일시메모리크기가결정됨 ( 일반변수, 함수 ) 동적할당 : 프로그램이실행되는도중에원하는크기만큼메모리확보 동적할당의단점 : 시간 void* malloc(size_t size) 동적으로메모리할당 성공시할당된메모리의시작주소를리턴, 실패시 NULL 리턴 리턴형이 void* 라서어떤형으로든변환해서사용가능 size 는할당받고싶은메모리바이트수 (sizeof() 연산자사용 ) void* calloc(size_t num, size_t size) 기본은 malloc() 함수와같다 차이점은메모리내용을 0 으로초기화 20
배열과포인터 동적메모리할당 void* realloc(void* memblock, size_t size) 이전에할당된동적메모리의크기를조정 memblock 은이전메모리시작주소 size 가 0 일경우메모리해제후 NULL 리턴 공간부족시다른메모리공간에동적할당 void* memset(void* s, int c, size_t n) 메모리영역을초기화 malloc + memset = calloc void* memcpy(void* dest, const void* src, size_t n) src 번지의데이터를 dest 가지정하는번지로 n Byte 복사 dest 의포인터를리턴, 실패시 NULL 리턴 21
배열과포인터 동적메모리할당 void free(void* memblock) 기존에동적으로할당받은메모리를해제 free() 안할경우메모리누수 메모리해제시조심 3 2 1 A 1000 12 1000 memory table 2 B 2 C 2000 3000 22
구조체와공용체 - 구조체 구조체의뜻 여러자료형의변수들을묶어서하나의자료형으로선언하고사용 구조체선언 struct employee{ char name[10]; int pay; }; struct employee Jung; struct employee{ char name[10]; int pay; } Jung; typedef struct employee{ char name[10]; int pay; } employee; employee Jung; 구조체의메모리구조 char name[10] + int pay = 10Byte(+2 Byte 패딩 ) + 4Byte = 16Byte char name[10] int pay 23
점연산자 (. ) 구조체와공용체 - 구조체연산자 구조체변수의데이터항목을지정 struct employee Jung; strcpy(jung.name, JYH ); Jung.pay = 5000; 화살표연산자 ( ) 구조체형포인터에서포인터가가리키는데이터항목을지정 struct employee* Jung; Jung = (employee *)malloc(sizeof(employee)); strcpy(jung name, JYH ); Jung pay = 5000; 24
구조체와공용체 - 공용체 공용체 여러자료형을동일한저장공간에이용하는자료형 선언은구조체와같음 메모리사용공간을줄이기위해 union employee{ char name[10]; int pay; } Jung; 공용체의메모리구조 구조체와공용체의차이점 10Byte + (2Byte 패딩 ) = 12Byte char name[10] int pay 25
구조체와공용체 - 중첩구조체 구조체안에구조체를포함시키는것 struct major{ char name[30]; int grade; } ; struct employee{ char name[10]; int pay; struct major ice; } Jung; 변수참조 중첩구조체참조시점연산자두번사용 strcpy(jung.ice.name, Information Communication ) ; Jung.ice.grade = 143; Jung.pay = 10000; 26
구조체와공용체 - 자기참조구조체 자기참조구조체 구조체안에서자기자신을참조함 자료구조 list 의핵심 struct list{ int score; struct list* link; } ; struct list* one; struct list* two; one score 100 link one = (struct list*)malloc(sizeof(struct list)); two = (struct list*)malloc(sizeof(struct list)); one score = 100; two score = 200; one link = two; two link = NULL; score 200 link NULL 27
구조체와공용체 - 함수인자 함수인자에구조체넣기 typedef struct employee{ char name[10]; int pay; } employee; void func_struct (employee* J) { printf( %d,j->pay); //... } int main() { employee* Jung; Jung = (employee *)malloc(sizeof(employee)); Jung->pay = 1000000; func_struct(jung); return 0; } 28
구조체와공용체 - 메모리크기 char name[10] 은 10 Byte 지만시스템구조상 4Byte 단위로패딩하기때문에 4 x 3 = 12Byte 로계산됨 struct employee{ char name[10]; int pay; }; struct employee Jung; sizeof(struct employee) = 16Byte union employee{ char name[10]; int pay; }; struct employee Jung; sizeof(union employee) = 12Byte #pragma pack(n) n 은 2 의제곱만가능 (1,2,4,8) pack(1) 일경우 1Byte 단위로패딩하기때문에위의예에서구조체는 14Byte 공용체는 10Byte 로계산됨
자료구조 - 리스트 노드 data : 원소의값을저장 link : 다음노드의주소를저장 data link 단순연결리스트 노드가하나의링크필드에의하여다음노드와연결되는구조 삽입연산 1FF3 3DD0 0255 1FF3 A 3DD0 B 0255 C NULL NULL 20A3 20A3 D 2 3DD0 1 1 새로운노드가 B 를가리킴 2 전노드 (A) 가새로운노드 (D) 를가리킴 30
자료구조 - 리스트 삭제연산 1FF3 1FF3 A 3DD0 3DD0 1 0255 C NULL NULL B 0255 1A 노드가앞노드 (B) 의 link(c) 를가리킴 원형연결리스트 단순연결리스트의마지막노드가 NULL 대신첫번째노드를가리킴 현재노드의바로이전노드접근시순회해야함 이중연결리스트 리스트의링크가양쪽방향으로순회가가능 두개의링크와데이터필드로구성됨 llink data rlink 31
자료구조 - 스택 스택 가장마지막에삽입된자료가가장먼저삭제됨 LIFO (Last-In-First-Out) 순차자료구조 ( 선형스택 ), 연결자료구조 ( 연결스택 ) C B B B A A A A 공백스택 A 삽입 (PUSH A) B 삽입 (PUSH B) C 삽입 (PUSH C) 삭제 (POP) 32
자료구조 - 큐 큐 삽입된순서대로삭제 FIFO (First-In-First-Out) 순차자료구조 ( 선형큐, 원형큐 ) - 메모리낭비, 사용크기제한 연결자료구조 ( 연결큐, 덱큐 ) front 저장된원소중에서첫번째원소삭제연산하는곳 rear 저장된원소중에서마지막원소삽입연산하는곳 33
자료구조 - 트리 트리 비선형자료구조 ( 스택, 큐, 리스트는선형자료구조 ) 계층형자료구조 예 : 가계도 B A C 루트노드 : A 단말노드 : D, E, F, G 레벨 0 : A 레벨 1 : B, C 레벨 2 : D, E, F, G 최대차수 (degree) : 3 트리의높이 (depth) : 2 D E F G 34
자료구조 - 트리 이진트리 모든노드의차수를 2 이하로정한트리 포화이진트리, 완전이진트리, 편향이진트리 순차자료구조 ( 배열 ), 연결자료구조 ( 리스트 ) 이진트리의순회 전위순회 D L R A,B,C ( 파랑 ) A 중위순회 L D R B,A,C ( 녹색 ) 후위순회 L R D B,C,A ( 빨강 ) B C 35
자료구조 - 정렬 정렬의의미 순서없이배열되어있는자료들을작은것부터큰것순서의오름차순이나반대로내림차순으로재배열하는것 실행방법에따른분류 비교식정렬 : 비교하고자하는각키값들을한번에두개씩비교하여교환하는방식 분산식정렬 : 키값을기준으로자료를여러개의부분집합으로분해하고, 각부분집합을정렬함으로써전체를정렬하는방식 정렬장소에따른분류 정렬장소 장점 단점 내부정렬 메인메모리 속도가빠름 대용량의자료정렬불가능 외부정렬 대용량의보조기억장치 대용량의자료정렬가능 속도가느림 36
자료구조 - 정렬 삽입정렬 정렬되어있는곳에정렬할새로운레코드를삽입하는방식 알고리즘이간단 버블정렬 서로인접한데이터들을자리바꿈하면서정렬 효율성은떨어지나구현이쉬움 선택정렬 루프를돌때마다정렬대상범위중에서가장작은수를선택하여정렬되지않은리스트중에처음위치에있는데이터와바꾸어나가는방식 속도면에서삽입, 버블보다빠름 퀵정렬 pivot 이라는임의의값설정후배열의양끝방향에서부터탐색을시작해서 pivot 값보다큰값과작은값을발견하여서로치환하는방식 37
자료구조 - 정렬 히프정렬 Heap : 여러개의노드들가운데에서가장큰값또는작은값을가지는노드를가장빠르게찾도록만들어진자료구조 Priority Queue : 우선순위를가진큐 heap 구조로저장후 root 추출하고재정렬후 root 추출 ( 반복 ), 속도빠름 병합정렬 (2-way, n-way) 이미정렬된두개이상의배열을하나의레코드로합침 쉘정렬 삽입, 버블은인접리스트를비교하지만쉘정렬은멀리있는원소교환 기준간격을전체원소개수의 ½ 로줄여가면서반복수행 기수정렬 기억공간낭비가심하나속도가빠름 일, 십, 백, 천순으로차례차례정렬 38
자료구조 - 검색 검색 기억공간에저장된데이터중에서원하는데이터를찾는것 각레코드를구분하는 key 가필요 선형검색 ( 순차검색 ) 한쪽끝에서한개씩순서대로검색하는방법 조직화필요없어서편하지만비효율적 이진탐색 정렬된데이터에서정해진값과의대소구분으로원하는데이터찾음 이진탐색트리 : 이진탐색에접합하도록만들어진자료구조 39
C 언어숙지사항 - call 전달방식 호출시 원본변수에미치는영향 typedef struct employee{ char name[100]; int pay; } employee; Call by value 값 인자에들어있는값만을호출함수에복사 없음 Call by reference 주소 변수자체를인자로넘겨줌 있음 void func_struct1(employee* J); {... } void func_struct2(employee J); {... } 40
C 언어숙지사항 - store class 기억장소 기억클래스자동변수내부정적변수외부정적변수외부변수레지스터변수 수정자 auto static static extern register 변수의사용범위선언된함수, 블록의내부선언된함수, 블록의내부변수가선언된파일선언된파일, 또는외부파일선언된함수, 블록의내부 extern 모든함수에서참조가가능한전역변수 외부파일에서사용가능 프로그램종료할때까지기억장소할당되고소멸되지않음 기본적으로함수는 extern 41
C 언어숙지사항 - store class static 내부형정적변수 : 함수내에서만참조 외부형정적변수 : 외부에서참조 처음에만지정된값으로초기화되고그다음부터초기화안됨 실행속도는빠르나메모리낭비가있음 register CPU 에있는 register 사용해서속도가빠름 변수개수에한계가있음 주소연산자사용불가능 42
우선순위 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 C 언어숙지사항 - 우선순위 연산자 ( ) [ ]. a++ a--( 후위 ) ++a --a! ~ sizeof( 형 ) - +( 부호 ) &( 주소 ) *( 역참조, 간접 ) * / % + - << >> < > <= >= ==!= & ^ &&?: = += -= *= /= %= <<= >>= &= = ^=,( 콤마연산자 ) 계산방향 ( 결합법칙 ) 43
참고문헌 C / C++ 개발자를위한포인터실무 KIN 진용훈저, 사이텍미디어 C 로배우는쉬운자료구조 이지영저, 한빛미디어 Win32 Api 연구사이트 http://www.winapi.co.kr 44
45 질의응답및토의