제 2 장 배열과 스트링

1차원 배열 (1) 배열의 정의 배열 표현과 주소 할당 동일한 데이타형을 갖는 원소들이 2차원 장방형 구조에 놓여 있는 집합체 인덱스와 값의 쌍으로 구성된 집합이며 반드시 유한성을 갖음 배열 표현과 주소 할당 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) 주소 1 2 3 4 5 6 7 8 9 배열 원소 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) 배열 표현 배열의 주소할당 자료구조론

1차원 배열 (2) 배열의 공리 structure ARRAY(value, index) ① declare CREATE() --> array ② RETRIEVE(array, index) --> value; STORE(array, index, value) --> array; ③ for all A  array, i, j  index, x  value let ④ RETRIEVE(CREATE, i) ::= error; ⑤ RETRIEVE(STORE(A, i, x), j) ::= if EQUAL(i, j) then x else RETRIEVE(A, j); end end ARRAY 자료구조론

1차원 배열 (3) 크기가 n 인 1 차원 배열의 표현 배열의 주소값 구하기 A(i) = B + k * ( i - L ) 원소길이가 10바이트인 1차원 배열에서 50번째 원소의 주소 A(49)의 주소 = 200 +10(49-0) = 690 A(0) A(1) • • • A(n-1) 1차원 배열 A 자료구조론

다차원 배열 (1) 2차원 배열 A(p:m, q:n) A(p:m, q:n) = { A(i, j) | i = p, ..., m 과 j = q, ..., n } 배열 A의 행의 개수= m-p+1, 열 A의 열의 개수= n-q+1 배열 A의 총 원소의 개수 = (m–p+1)  (n–q+1) q q+1 . . . . n p p+1 m 2차원 배열 A(p:m, q:n) 자료구조론

(z-r+1)ⅹ(m-p+1)ⅹ(n-q+1) 다차원 배열 (2) 3차원 배열 B(r:z, p:m, q:n) B(r:z, p:m, q:n) = { B(i, j, k) | i= r, ...,z 과 j= p, ...,m 과 k= q, ...,n } 3차원 배열의 원소의 개수 (z-r+1)ⅹ(m-p+1)ⅹ(n-q+1) p z • • • • • • m 자료구조론 r q • • • n

다차원 배열 (3) n차원 배열 C(L1:U1, L2:U2, …, Ln:Un) C(L1:U1, L2:U2, …, Ln:Un) = { C(i1, i2, …, in) | k=1, 2, …, n, Lk< ik< Uk } 배열 C의 총 원소의 개수 = (U1 - L1 + 1)  (U2 - L2 + 1)  …  (Un - Ln + 1) 자료구조론

다차원 배열 (4) 배열의 물리적 표현 기억장치에는 순차적으로 저장됨으로 인하여 2종류로 표현가능 배열 A(0:1, 0:2, 0:1)의 나열 순서 A(1, 2, 1) 112 A(1, 2, 0) A(1, 1, 1) 111 A(1, 0, 1) 110 A(1, 1, 0) 109 108 A(1, 0, 0) 107 A(0, 2, 1) 106 A(0, 2, 0) A(0, 1, 1) 105 A(0, 0, 1) 104 A(0, 1, 0) 103 102 A(0, 0, 0) 101 행 방향 순서 열 방향 순서 번지 첫 번 째 면 두 번 째 면 자료구조론

다차원 배열 (5) 배열의 물리적 표현 (계속) 열 방향 순서(column major order) FORTRAN 2차원 배열 A(0:U1-1, 0:U2-1)A(i, j)의 주소 = B + jU1 + i 3차원 배열 A(0:U1-1, 0:U2-1, 0:U3-1) A(i, j, k)의 주소 = B + iU2U3 + kU2 + j 행 방향 순서(row major order) C, PASCAL, PL/1, COBOL 2차원 배열 A(0:U1-1, 0:U2-1) A(i, j)의 주소 = B + iU2 + j A(i, j, k)의 주소 = B + iU2U3 + jU3 + k 자료구조론

특수 행렬 (1) 희소 행렬(sparse matrix) 행렬의 많은 원소들이 0으로 구성되어 있는 행렬 7 행5 9 행4 3 7 행5 9 행4 3 행3 11 -6 행2 28 행1 5 20 행0 열5 열4 열3 열2 열1 열0 -8 -1 열6 -3 행6 자료구조론

특수 행렬 (2) 희소 행렬(sparse matrix)의 표현 기억 장소의 낭비를 줄이기 위한 표현 방법 0 인 아닌 원소들에 대하여 (행, 열, 값) 의 형태로 표현 행/열 1 2 7 7 11 1 20 2 5 5 3 6 -1 4 1 2 28 5 2 2 -6 6 2 4 11 7 3 3 3 8 4 9 9 5 2 7 10 5 6 -8 자료구조론 11 6 1 -3

특수 행렬 (3) 전치 행렬(transpose matrix) 행렬에서 (i, j)에 위치한 원소를 (j, i)로 옮기는 행렬 행/열 1 2 7 7 11 행/열 열0 열1 열2 열3 열4 열5 열6 1 20 2 4 9 행0 20 9 3 1 6 -3 행1 -3 4 2 1 28 행2 28 -6 7 5 2 2 -6 행3 3 6 2 5 7 7 3 3 3 행4 11 8 4 2 11 행5 5 9 5 5 행6 -1 -8 10 6 -1 자료구조론 11 6 5 -8

특수 행렬 (4) 삼각 행렬(triangular matrix) 행과 열의 수가 같은 정방 행렬로서, 대각선을 중심으로 한쪽 부분이 0 인 행렬 상삼각 행렬 X 하삼각 행렬 X 자료구조론

특별한 행렬 (5/5) 하삼각 행렬의 표현 주소 배열 원소 1 A(0,0) 2 A(1,0) 3 A(1,1) 4 A(2,0) 5 6 7 8 9 10 배열 원소 A(0,0) A(1,0) A(1,1) A(2,0) A(2,1) A(2,2) A(3,0) A(3,1) A(3,2) A(3,3) 주소 할당 A(0,0) A(1,0) A(1,1) A(2,0) A(2,1) A(2,2) A(3,0) A(3,1) A(3,2) A(3,3) 하삼각 행렬 자료구조론

C 언어에서의 배열 1차원 배열의 선언 2차원 배열의 선언 데이타형태[] 배열명 = 데이타형태[원소수]; 데이타형태[][] 배열명 = 데이타형태[원소수][원소수]; 자료구조론

C 언어에서의 1차원 배열 int A[6]; A[0] A[1] A[2] A[3] A[4] A[5] base base+sizeof(int) base+2*sizeof(int) base+3*sizeof(int) base+4*sizeof(int) base+5*sizeof(int) 자료구조론

C 언어에서의 2차원 배열 int A[3][4]; 실제 메모리안에서의 위치 A[2][0] A[2][1] A[2][2] … A[1][3] 실제 메모리안에서의 위치 자료구조론

스트링의 표현 방법 (1) 정의 일련의 문자들의 집합 1차원적인 문장의 배열, 공백과 구두점 같은 특수 문자들을 포함한 모든 유효한 문자를 사용한 문자들의 모임 ex) “Silla University”, .. 등 대부분의 경우 문자 데이터형의 1차원 배열로 표현 C 언어에서 스트링 정의: char str[100]; 스트링의 끝임을 표시하기 위해 스트링 마지막 문자로 NULL(‘\0’)을 사용 자료구조론

스트링의 표현 방법 (2) 스트링의 표현방법 순차 스트링 스트링 S에 대하여, S의 연속적인 문자들을 위하여 문자 코드들을 연속적인 워드에 나타내는 방법 1워드 처리속도 빠르지만 기억장소 활용도 낮음 비압축 스트링 • • • M E O \0 자료구조론

스트링의 표현 방법 (3) 스트링의 표현방법 고정길이 스트링 압축 스트링 연결 리스트 P A C K E D S T R I N 1워드 P A C K E D S T R I N G XXX XXX XXX XXX ••• 자료구조론

스트링의 표현 방법 (4) 스트링의 표현방법 가변길이 스트링 스트링의 길이를 예측하기 어려운 경우 사용하는 방법 ex) 어셈블러의 매크로 확장이나 스트링 결합과 같이 새로운 스트링을 다른 데이터의 함수로 계산하는 경우, .. 등. 프로그램 수행 도중 변화를 처리 자료구조론

스트링 연산 (1) 스트링 연산 결합(concatenation) 삽입(insertion) 두 스트링을 연쇄적으로 연결한 합성된 스트링이 결과로 나오는 연산 예) F = “KIM”, L = “LR” 일 때 F||L 이면 S=“KIMLR” 삽입(insertion) 스트링을 구성하는 문자와 문자 사이에 새로운 스트링을 삽입하는 연산 예) S = “OPQRST”일 때 “PQ” S  “P, Q” 이면 S = “OP, QRST” 자료구조론

스트링 연산 (2) 스트링 연산 삭제 (deletion) 교체 (replacement) 스트링을 구성하는 문자들 중의 하나 이상의 문자를 제거하는 연산 예) S = “OPQRST”일 때 “P”  S  “ “ 이면, S = “OQRST” 교체 (replacement) 스트링을 구성하는 문자들 중의 하나 이상의 문자를 바꾸는 연산 예) S = “$ 3.00” 일때 “3.00”  S  “3.50”이면 S = “$3.50” 으로 바뀐다. 자료구조론

스트링 연산 (3) 스트링 연산 서브스트링(substring) 패턴 매칭(pattern matching) 스트링을 구성하는 연속적인 문자들 중에서 일부를 찾아 새로운 스트링을 만드는 연산 패턴 매칭(pattern matching) 스트링 중 지정된 서브스트링을 찾는 것으로, 지정된 서브 스트링이 있으면 참이고, 없으면 거짓인 연산 예) S = “OPQRST”일때 “P”  S의 결과는 참 자료구조론

스트링 연산 (4) 스트링 연산 인덱싱 (indexing) 스트링 내에서 어떤 문자 또는 서브 스트링의 위치를 정수로 나타내는 연산 예) P = “LINKED LIST”인 P에서 “LIS”의 인덱싱 = 8 (만약 ,해당 문자가 없으면 0이며, 복수 개이면 최초의 경우가 해당) 자료구조론

C 언어에서 스트링 연산(1) 결합연산 스트링 s1과 s2를 결합한 결과를 반환 char *concate (char *s1, char *s2){ char *s3; int len1, len2, len3, i; len1=strlen(s1); len2=strlen(s2); len3=len1+len2; s3=malloc(len3+1); i=0; while(*s1){ s3[i++]=*s1; s1++; } s3[I++]=*s2; s2++; s3[I]=‘/0’; return(s3); 자료구조론

C 언어에서 스트링 연산(2) 서브스트링 연산 S1의 i위치에서부터 시작하여 j개의 문자를 스트링 s2로 만드는 함수 char *substr (char *s1, int i, int j){ int k, limit; char *temp; temp=malloc(j); If((i+j) <= strlen(s10) limit =i+j; else limit = strlen(s1); for(k=i; k<1; k++) temp[k-i] = s1[i]; for(k=limit-i; k<strlen(s1); k++) temp[k}=‘ ‘; temp[strlen(s1)]=‘/0’; return(temp); } 자료구조론

C 언어에서 스트링 연산(3) C 라이브러리 함수 헤드 파일: <string.h> 주요 함수: int strlen(const char *str); int strcmp(const char *str1, const char *str2); int strncmp(const char *str1, const char *str2, const int n); char* strcat(char *dest, const char *src); char* strncat(char *dest, const char *src, const int n); char* strcpy(char *dest, const char *src); char* strncpy(char *dest, const char *src, const int n); 자료구조론

C 언어에서 스트링 연산(4) C 라이브러리 함수 주요 함수: char* strchr(const char *str, const char ch); char* strrchr(const char *str, const char ch); char* strstr(const char *str, const char *key); char* strpbrk(const char *str, const char *delimiter); char* strspn(const char *str, const char *delimiter); char* strcspn(const char *str, const char *delimiter); char* strtok(char *str, const char *delimiter); 자료구조론

구조체 구조체(structure): 타입이 다른 데이터를 하나로 묶는 방법 배열(array): 타입이 같은 데이터들을 하나로 묶는 방법 구조체 필드 struct example { char cfield; int ifield; float ffield; double dfield; }; struct example s1; 배열 1 char carray[100]; 자료구조론

구조체의 사용예 구조체의 선언과 구조체 변수의 생성 typedef을 이용한 구조체의 선언과 구조체 변수의 생성 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; // 구조체 변수 선언 자료구조론

구조체의 대입과 비교 연산 구조체 변수의 대입: 가능 구조체 변수끼리의 비교: 불가능 struct person { char name[10]; // 문자배열로 된 이름 int age; // 나이를 나타내는 정수값 float height; // 키를 나타내는 실수값 }; main() { person a, b; b = a; // 가능 } 구조체 변수끼리의 비교: 불가능 main() { if( a > b ) printf("a가 b보다 나이가 많음"); // 불가능 } 자료구조론

자체참조 구조체 자체 참조 구조체(self-referential structure): 필드중에 자기 자신을 가리키는 포인터가 한 개 이상 존재하는 구조체 연결 리스트나 트리에 많이 등장 typedef struct ListNode { char data[10]; struct ListNode *link; } ListNode; 자료구조론

포인터(pointer) 포인터: 다른 변수의 주소를 가지고 있는 변수 포인터가 가리키는 내용의 변경: * 연산자 사용 주소 26 ‘A’ 변수 a 주소 포인터 p 포인터: 다른 변수의 주소를 가지고 있는 변수 char a='A'; char *p; p = &a; 포인터가 가리키는 내용의 변경: * 연산자 사용 26 ‘B’ 변수 a 주소 포인터 p *p= 'B'; 자료구조론

포인터와 관련된 연산자 & 연산자: 변수의 주소를 추출 * 연산자: 포인터가 가리키는 곳의 내용을 추출 26 &a *p ‘A’ int a; // 정수 변수 선언 int *p; // 정수 포인터 선언 int **pp; // 정수 포인터의 포인터 선언 p = &a; // 변수 a와 포인터 p를 연결 pp = &p; // 포인터 p와 포인터의 포인터 pp를 연결 자료구조론

디양한 포인터 포인터의 종류 포인터의 형변환: 필요할 때마다 형변환하는 것이 가능하다. void *p; // p는 아무것도 가리키지 않는 포인터 int *pi; // pi는 정수 변수를 가리키는 포인터 float *pf; // pf는 실수 변수를 가리키는 포인터 char *pc; // pc는 문자 변수를 가리키는 포인터 int **pp; // pp는 포인터를 가리키는 포인터 struct test *ps; // ps는 test 타입의 구조체를 가리키는 포인터 void (*f)(int) ; // f는 함수를 가리키는 포인터 포인터의 형변환: 필요할 때마다 형변환하는 것이 가능하다. void *p; pi=(int *) p; 자료구조론

함수의 파라미터로서의 포인터 함수안에서 파라미터로 전달된 포인터를 이용하여 외부 변수의 값 변경 가능 void swap(int *px, int *py) { int tmp; tmp = *px; *px = *py; *py = tmp; } main() int a=1,b=2; printf("swap을 호출하기 전: a=%d, b=%d\n", a,b); swap(&a, &b); printf("swap을 호출한 다음: a=%d, b=%d\n", a,b); 자료구조론

배열과 포인터 배열의 이름: 사실상의 포인터와 같은 역할 컴파일러가 배열의 이름을 배열의 첫번째 주소로 대치 10 A[0] A 14 A[1] 18 A[2] 22 A[3] 26 A[4] 30 A[5] 컴파일러가 배열의 이름을 배열의 첫번째 주소로 대치 자료구조론

구조체의 포인터 구조체의 요소에 접근하는 연산자: -> main() { struct { int i; float f; 3.14 98 2 ps s s.I = ps->i s.f = ps->f main() { struct { int i; float f; } s, *ps; ps = &s; ps->i = 2; ps->f = 3.14; } 자료구조론

포인터의 포인터 56 26 ‘A’ 변수 a 포인터 p 89 포인터의 포인터 pp int a; // 정수 변수 변수 선언 int *p; // 정수 포인터 선언 int **pp; // 정수 포인터의 포인터 선언 p = &a; // 변수 a와 포인터 p를 연결 pp = &p; // 포인터 p와 포인터의 포인터 pp를 연결 자료구조론

포인터 연산 포인터에 대한 사칙연산: 포인터가 가리키는 객체단위로 계산된다. 10 A[0] p 14 A[1] 18 A[2] p+1 // 포인터 p가 가리키는 객체의 바로 뒤 객체 p-1 // 포인터 p가 가리키는 객체의 바로 앞 객체 10 A[0] p 14 A[1] 18 A[2] 22 A[3] 26 A[4] 30 A[5] p+1 p-1 자료구조론

포인터 사용시 주의할 점 포인터가 아무것도 가리키고 있지 않을 때는 NULL로 설정 초기화가 안된 상태에서 사용 금지 int *pi=NULL; 초기화가 안된 상태에서 사용 금지 main() { char *pc; // 포인터 pi는 초기화가 안되어 있음 *pc = 'E’; // 위험한 코드 } 포인터 타입간의 변환시에는 명시적인 타입 변환 사용 int *pi; float *pf; pf = (float *)pi; 자료구조론

동적 메모리 할당 (1) 프로그램이 메모리를 할당받는 방법 정적 메모리 할당 정적 메모리 할당(Static Memory Allocation) 동적 메모리 할당(Dynamic memory Allocation) 정적 메모리 할당 메모리의 크기는 프로그램이 시작하기 전에 결정 프로그램의 수행 도중에 그 크기가 변경될 수는 없다. 만약 처음에 결정된 크기보다 더 큰 입력이 들어온다면 처리하지 못할 것이고 더 작은 입력이 들어온다면 남은 메모리 공간은 낭비될 것이다. (예) 변수나 배열의 선언 int buffer[100]; char name[] = “data structure"; 자료구조론

동적 메모리 할당 (2) 동적 메모리 할당 프로그램의 실행 도중에 메모리를 할당받는 것 필요한 만큼만 할당을 받고 또 필요한 때에 사용하고 반납 메모리를 매우 효율적으로 사용가능 단점: 운영체제로 부터 메모리를 할당받는 것만큼의 실행 시간 지연 할당받은 메모리는 받드시 반환하여야 함 메모리 200바이트가 필요한데…. 운영체제 프로그램 자료구조론

동적 메모리 할당 (3) 전형적인 동적 메모리 할당 코드 동적 메모리 할당 관련 라이브러리 함수 main() { int *pi; pi = (int *)malloc(sizeof(int)); // 동적 메모리 할당 ... … // 동적 메모리 사용 free(pi); // 동적 메모리 반납 } 동적 메모리 할당 관련 라이브러리 함수 malloc(size) // 메모리 할당 free(ptr) // 메모리 할당 해제 sizeof(var) // 변수나 타입의 크기 반환(바이트 단위) 자료구조론

동적 메모리 할당 라이브러리 malloc(int size) free(void ptr) sizeof 키워드 (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 자료구조론

동적 메모리 할당 예제 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); 자료구조론