배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합

Presentation on theme: "배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합"— Presentation transcript:

1 배열과 ADT(1/2) 연속된 메모리 위치의 집합 <index, value>쌍의 집합
자료구조와 그 기억장소 구현의 혼동 <index, value>쌍의 집합 set of mappings (or correspondence) between index and values array : I  ai

2 배열과 ADT(2/2) ADT Array object : index의 각 값에 대하여 집합 item에 속한 한 값이
존재하는 <index, value>쌍의 집합. index는 일차원 또는 다차원 유한 순서 집합이다. 예를 들면, 1차원의 경우 {0, …., n-1}과 2차원 배열{(0,0), (0,1), (1,1), (1,2), (2.0), (2,1), (2,2)} 등이다. functions : 모든 A∈Array, i∈index, x∈item, j, size∈integer Array create(j, list) ::= return j차원의 배열 여기서 list는 i번째 원소가 i번째 차원의 크기인 j-tuple이며 item들은 정의 되지 않았음. item Retrieve(A, i) ::= if (i∈index) return 배열 A의 인덱스 i값과 관련된 항목. else return 에러. Array Store(A, i, x) ::= if (i ∈ index) end Array < Array 추상 데이터 타입 >

3 C언어에서의 배열(1/4) C의 일차원 배열 int list[5], *plist[5]; 포인터 해석
정수값 : list[0], list[1], list[2], list[3], list[4] 정수포인터 : plist[0], plist[1], plist[2], plist[3], plist[4] 포인터 해석 int *list1; int list2[5]; list2 = list2[0]를 가리키는 포인터 list2 + I = list[i]를 가리키는 포인터 (list2+i) = &list2[i], *(list+i) = list2[i] 변 수 메모리 주소 List[0] 기본주소 = a List[1] a + sizeof(int) List[2] a + 2 ·sizeof(int) List[3] a + 3 ·sizeof(int) List[4] a + 4 ·sizeof(int)

4 C언어에서의 배열(2/4) 배열 프로그램의 예 #define MAX_SIZE 100
float sum(float []), int; int i; void main(void) { for(i=0; i<MAX_SIZE; i++) input[i] = I; answer = sum(input, MAX_SIZE); printf(“The sum is: %f\n”, answer); } float sum(float list[], int n) float tempsum = 0; for(i = 0; i<n; i++) tempsum += list[i]; return tempsum;

5 C언어에서의 배열(3/4) 호출시 input(=&input[0])은 임시 장소에 복사 역참조(dereference)
형식 매개 변수 list와 연관 역참조(dereference) list[i]가 “=”기호 우측  (list + i)가 가리키는 값 반환 list[i]가 “=”기호 좌측  값을 (list + i) 위치에 저장 ※ C언어의 매개변수 전달방식 : call-by-value  배열 매개변수는 그 값을 변경함

6 C언어에서의 배열(4/4) 예제[일차원 배열의 주소 계산] int one[] = {0, 1, 2, 3, 4};
printf1(&one[0], 5) void print1 (int *ptr, int rows) {/* print out a one-dimensional array using a pointer */ int i; printf (“Address Contents\n”); for (i=0; i<rows; i++) printf(“%8u%5d\n”, ptr + i, *(ptr + i)); printf(“\n”); } 주소 1228 1230 1232 1234 1236 내용 1 2 3 4 < 1차원 배열의 주소 계산 >

7 동적 할당 배열(1/4) 1차원 배열 ※ N<1이거나 정렬할 수의 리스트를 저장 할 메모리가 충분치 않을때 실패
int i, n, *list; printf(“Enter the number of number to generate: ”); scanf(“%d”, &n”); If (n < 1) { fprintf(stderr, “Improper value of n \n”); exit (EXIT_FAILURE); } MALLOC(list, n * sizeof(int)); ※ N<1이거나 정렬할 수의 리스트를 저장 할 메모리가 충분치 않을때 실패

8 동적 할당 배열(2/4) 2차원 배열 int x[3][5] < 2차원 배열의 동적 생성 > [0] [1] [2]
[4] x[0] x[1] x[2] int ** make2dArray(int rows, int cols) { /* create a two dimensional rows  cols array */ int **x, i; /* get memory for row pointers */ MALLOC (x, rows * sizeof (*x));; /* get memory for each row */ for (i = 0; i < rows; i++) MALLOC(x[i], cols * sizeof(**x)); return x; } < 2차원 배열의 동적 생성 >

9 동적 할당 배열(3/4) Ex> Calloc / Realloc 함수 510 2차원 정수 배열에 대한 메모리 할당
이 배열의 [2][4]원소에 정수 6을 지정 Calloc / Realloc 함수 calloc : 사용자가 지정한 양의 메모리를 할당하고 할당된 메모리를 0으로 초기화 Realloc : malloc이나 calloc으로 이미 할당된 메모리 크기 재조정 int *myArray; myArray = make2dArray(5, 10); myArray[2][2] = 6 int *x; x = calloc(n, sizeof(int))

10 동적 할당 배열(4/4) #define CALLOC(p, n, s)\ if(!((p) = calloc(n, s))) {\
fprintf(stderr, “Insufficient memory”):\ exit(EXIT_FAILURE):\ } #define REALLOC(p, s)\ if(!((p) = realloc(n, s))) {\ fprintf(stderr, “Insufficient memory”):\ exit(EXIT_FAILURE):\ }

11 구조와 유니언(1/5) 구조(structure) : struct 타입이 다른 데이터를 그룹화 (레코드)
데이터 항목의 집단 – 각 항목은 타입과 이름으로 식별 구조의 멤버 연산자 struct { char name[10]; int age; float salary; } person; strcpy(person.name, “james”); person.age = 10; person.salary = 35000;

12 구조와 유니언(2/5) typedef 문장을 사용한 구조 데이터 타입 생성 변수선언
전체 구조의 동등성 검사 : if (person1 == person2) 구조 치환 : person1 = person2 strcpy(person1.name, person2.name); person1.age = person2.age; person1.salary = person2.salary; typedef struct human_being{ char name[10]; int age; float salary; }; typedef struct { char name[10]; int age; float salary; } human_being; or human_being person1, person2 ; if (strcmp(person1.name, person2.name)) printf(“두사람의 이름은 다르다.\n”); else printf(“두사람의 이름은 같다.”)

13 구조와 유니언(3/5) 구조의 동등성 검사 #define FALSE 0 #define TRUE 1
int humansEqual (humanBeing person1, humanBeing person 2) {/* 만일 personal과 person2가 동일인이면 TRUE를 반환하고 그렇지 않으면 FALSE를 반환한다. */ if (strcmp(person1.name, person2.name)) return FALSE; if (person1.age != person2.age) if (person1.salary != person2.salary) return TRUE; } < 구조의 동등성을 검사하는 함수 >

14 구조와 유니언(4/5) 유니언 Union의 필드들은 메모리 공간을 공용 한 필드 만 어느 한 시점에 활동적이 되어 사용 가능
typedef struct sex_type { enum tagField {female, male} sex; union { int children; int beard; } u; }; typedef struct human_being { char name[10]; int age; float salary; sex_type sex_info; human_being person1, person2;

15 구조와 유니언(5/5) 값 할당 구조의 내부 구현 struct {int i, j; float a, b;} or struct {int i; int j; float a; float b;} 오름차 주소의 위치를 이용하여 저장 구조 내 빈 공간을 두거나 채워넣기(padding)를 할수 있다. 구조는 같은 메모리 경계에서 시작하고 끝나야 함 짝수바이트거나 4, 8, 16등의 배수가 되는 메모리 경계 person1.sex_info.sex = male; person1.sex_info.u.beard = FALSE; person2.sex_info.sex = female; person2.sex_info.u.children = 4;

16 자기 참조 구조 구성요소중 자신을 가리키는 포인터가 존재하는 구조 typedef struct list { char data;
list *link; }; list item1, item2, item3; item1.data = ‘a’; item2.data = ‘b’; item3.data = ‘c’; item1.link = item2.link = item3.link = NULL; item1.link = &item2; 구조들을 서로 연결 item2.link = &item3; (item1 → item2 → item3)

17 추상 데이터 타입(1/5) 순서 리스트(Ordered list, linear list) 원소들의 순서가 있는 모임
A = (a1, a2, …, an) ai : atom, n=0 : empty list 한주일의 요일들(일, 월, 화, 수, 목, 금, 토) 카드 한 벌의 값(ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, j, q, k) 건물의 층(지하실, 로비, 일층, 이층) 미국의 2차 세계 대전 참전 연도(1941, 1942, 1943, 1944, 1945) 연산 리스트의 길이의 n의 계산 리스트의 항목을 왼쪽에서 오른쪽 (오른쪽에서 왼쪽)으로 읽기 리스트로부터 i번째 항목을 검색, 0≤i≤n 리스트의 i번째 항목을 대체, 0≤i≤n 리스트의 i번째 위치에 새로운 항목을 삽입(i번째 위치,0≤i≤n) 리스트의 i번째 항목을 제거(i번째 항목, 0≤i<n)

18 추상 데이터 타입(2/5) 순서리스트의 표현 메모리(기억장소) 표현 순차 사항 (sequential mapping)
물리적 인접성(arrays) 비순차 사항(non-sequential mapping) 비연속적 기억장소 위치 리스트 : pointer(links)를 가지는 노드 집합

19 추상 데이터 타입(3/5) 기호 다항식의 조작 A(x) = 3x20+2x5+4, B(x) = x4+10x3+3x2+1
A(x) = ∑aixi와 B(x) = ∑bixi A(x) + B(x) = ∑(ai+bi)xi A(x) · B(x) = ∑(aixi ·(∑bjxj)) A(x) = anxn + an-1xn-1 + … + a1x1 + a0x0 axe a : coefficient an ≠ 0 e : exponent – unique x : variable x - 차수(degree) : 다항식에서 가장 큰 지수

20 추상 데이터 타입(4/5) Polynomial 추상 데이터 타입 Structure Polynomial
Objects : P(x) = a1xe1 + … + anxen : <ei, ai>의 순서쌍 집합. 여기서 ai는 Coefficient, ei는 Exponents. ei(≥0)는 정수 Function : 모든 poly, poly1, poly2 ∈ polynomial, coef ∈ Coefficients Expon ∈ Exponents에 대해 Polynomial Zero() ::= return 다항식, p(x) = 0 Boolean IsZero(poly) ::= if(poly) return FALSE else return TRUE Coefficient Coef(poly, expon) ::= if(expon∈poly) return 계수 else return 0 Exponent Lead_Exp(poly) ::= return poly에서 제일 큰 지수 Polynomial Attach(poly, coef, expon) ::= if(expon∈poly) return 오류 else return <coef, exp>항이 삽입된 다항식 poly

21 추상 데이터 타입(5/5) Polynomial Remove(poly, expon) ::= if(expon∈poly)
return 지수가 expon인 항이 삭제된 다항식 poly else return 오류 Polynomial SingleMult(poly, coef, expon) ::= return 다항식 poly·coef·xexpon Polynomial Add(poly1, poly2) ::= return 다항식 poly1+poly2 Polynomial Mult(poly1, poly2) ::= return 다항식 poly1·poly2 end polynomial

22 다항식의 표현(1/4) 다항식의 표현(I) 지수들의 내림차순으로 정돈
a : polynomial, n < MAX_DEGREE A(x) = ∑aixi a.degree = n, a.coef[i] = an-i, 0≤i≤n #define MAX_DEGREE /* 다항식의 최대 차수 +1*/ typedef struct int degree; float coef[MAX_DEGREE]; } polynomial; ※ A = (n, an, an-1, … , a1, a0) degree of A n+1 coefficients 예) A(x) = x4+10x3+3x : n = 4 A = (4, 1, 10, 3, 0, 1) : 6 elements

23 다항식의 표현(2/4) 다항식의 표현(II) 함수 padd의 초기 버전 a.degree << MAX_DEGREE
 a.coef[MAX_DEGREE]의 대부분이 필요없음 함수 padd의 초기 버전 /* d = a + b, 여기서 a, b, d는 다항식이다. */ d = Zero(); while (! IsZero(a) && ! IsZero(b)) do { switch COMPARE(Lead_Exp(a), Lead_Exp(b)) { case -1: d = Attach (d, Coef(b, Lead_Exp(b)), Lead_Exp(b)); b = Remove(b, Lead_Exp(b)); break;

24 다항식의 표현(3/4) case 0: sum = Coef(a, Lead_Exp(a)) + Coef(b, Lead_Exp(b)); if (sum) { Attach(d, sum, Lead_Exp(a)); a = Remove(a, Lead_Exp(a)); b = Remove(b, Lead_Exp(b)); } break; case 1; d = Attach(d, Coef(a, Lead_Exp(a)), Lead_Exp(a)); a 또는 b의 나머지 항을 d에 삽입한다.

25 다항식의 표현(4/4) A(x) = 2x1000+1 B(x) = x4+10x3+3x2+1 2 1 10 3 1000 4
MAX_TERMS /* 항 배열의 크기*/ typedef struct { float coef; int expon; } polynomial; Polynomial terms[MAX_TERMS]; int avail = 0; startA finishA startB finishB avail coef 2 1 10 3 1000 4 exp 1 2 3 4 5 6 A(x) : <starta, finisha> finisha = starta + n - 1

26 다항식의 덧셈(D=A+B)(1/2) void padd(int starta, int finisha, int startb, int finishb, int *startd, int *finishd); { /* A(x)와 B(x)를 더하여 D(x)를 생성한다. */ float coefficient; *startd = avail; while (starta <= finisha && startb <= finishb) switch (COMPARE(terms[starta].expon, term[startb].expon)) { case -1: /* a의 expon이 b의 expon보다 작은 경우 */ attach(terms[startb].coef, terms[startb].expon); startb++; break; case 0: /*지수가 같은 경우 */ coefficient = terms[starta].coef + terms[startb].coef; if(coefficient) attach(coefficient, terms[starta].expon); starta++; startb++; break; case 1: /* a의 expon이 b의 expon보다 큰 경우 */ attach(terms[starta].coef, terms[starta].expon); starta++;

27 다항식의 덧셈(2/2) < 두 다항식을 더하는 함수 > < 새로운 항을 첨가하는 함수 >
/* A(x)의 나머지 항들을 첨가한다. */ for(; starta <= finisha; starta++) attach(terms[starta].coef, term[starta].expon); /* B(x)의 나머지 항들을 첨가한다. */ for(; starta <= finishb; startb++) attach(terms[startb].coef, terms[startb].expon); *finishd = avail – 1; < 두 다항식을 더하는 함수 > void attach(float coefficient, int exponent) { /* 새 항을 다항식에 첨가한다. */ if (avail >= MAX_TERMS) { fprintf(stderr, “다항식에 항이 너무 많다.”); exit(1); } terms[avail].coef = coefficient; terms[avail++].expon = exponent; } < 새로운 항을 첨가하는 함수 >

28 알고리즘 padd의 분석 m, n(>0) ; 각각 A와 B의 0이 아닌 항의 수 while 루프
각 반복마다 starta나 startb 또는 둘 다 값이 증가 반복 종료→ starta <= finisha && startb <= finishb 반복 횟수 ≤ m+n-1 for 루프 : O(m+n) ∴ 연산시간 = O(n+m) ※ 문제점 avail = MAX_TERMS ?  불필요한 다항식 제거후 배열 끝에 연속적인 가용공간 생성(압축 함수) - 데이터 이동시간, 각 다항식의 starti, finishi 변경

29 희소 행렬(sparse matrix)(1/3)
mn matrix A ≡ A[MAX_ROWS][MAX_COLS] 희소행렬 no. of total elements no. of non-zero elements << small col0 col1 col2 row0 -27 3 4 row1 6 82 -2 row2 109 -64 11 row3 12 8 9 row4 48 27 47 col0 col1 col2 col3 col4 col5 row0 15 22 -15 row1 11 3 row2 -6 row3 row4 91 row5 28

30 희소 행렬(2/3) 희소 행렬의 추상데이터 타입 ADT sparseMatrix
object: 3원소 쌍 <행, 열, 값>의 집합이다. 여기서, 행과 열은 정수이고 이 조합은 유일하며, 값은 item집합의 원소이다. functions : 모든 a, b∈sparseMatrix, x∈item, i, j, maxCol, maxRow∈index에 sparseMatrix Create(maxRow, maxCol) ::= return maxItems까지 저장할 수 있는 sparseMatrix 여기서 최대 행의 수는 maxRow이고 최대 열의 수는 maxCol이라 할때 maItems = maxRowmaxCol이다. sparseMatrix Transpose(a) ::= return 모든 3원소 쌍의 행과 열의 값을 교환하여 얻은 행렬 sparseMatrix Add(a,b) ::= if a와 b의 차원이 같으면 return 대응 항들 즉, 똑같은 행과 열의 값을 가진 항들을 더해서 만들어진 행렬 else return 에러

31 희소 행렬(3/3) 희소 행렬의 표현 3원소쌍<행(row), 열(col), 쌍(value)>으로 표현
전치연산을 효율적으로 표현하기 위해 오름차순으로 조직 열 인덱스가 오름차순으로 정렬되도록 조직 연산 종료를 보장하기 위해 행과 열의 수와 행렬 내에 있는 0이 아닌 항의 수를 알아야 함 sparseMatrix Multiply(a,b) ::= if a의 열의 수와 b의 행의 수가 같으면 return 다음 공식에 따라 a와 b를 곱해서 생성된 행렬 d : d(i, j) = ∑(a[i][k] b[k][j]) 여기서 d(i, j)는 (i, j)번째 원소이다. else return 에러

32 행렬의 전치(Matrix Transpose)(1/3)
원소 <i, j, 값>을 가져와서 전치 행렬의 원소 <j, i, 값>으로 저장 ex) (0, 0, 15) 는 (0, 0, 15) (0, 3, 22) 는 (3, 0, 22) (0, 5, -15) 는 (5, 0, -15) 행 열 값 a[0] 6 8 a[1] 15 a[2] 3 22 a[3] 5 -15 a[4] 1 11 a[5] 2 a[6] -6 a[7] 4 91 a[8] 28 행 열 값 b[0] 6 8 b[1] 15 b[2] 4 91 b[3] 1 11 b[4] 2 3 b[5] 5 28 b[6] 22 b[7] -6 b[8] -15

33 행렬의 전치(2/3) 희소 행렬의 전치 for (j = 0; j < colums; j++)
for(i = 0; i < rows; i++) b[j][i] = a[i][j]; void transpose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ { int n, i, j, currentb; n = a[0].value; /* 총 원소 수 */ b[0].row = a[0].col; /* b의 행 수 = a의 열 수 */ b[0].col = a[0].row; /* b의 열 수 = a의 행 수 */ b[0].value = n; if (n>0) { /* 0이 아닌 행렬 */ currentb = 1; for (i=0; i=a[0].col; i++) /* a에서 열별로 전치 */ for (j=1; j<n; j++) /* 현재의 열로부터 원소를 찾는다 */ if (a[j].col = = I { /* 현재의 열에 있는 원소를 b에 첨가한다. */ b[currentb].row = a[j].col; b[currentb].col = a[j].row; b[currentb].value = a[j].value; currentb++; } }

34 행렬의 전치(3/3) 희소 행렬의 빠른전치 void fasttranspose(term a[], term b[]) /* a를 전치시켜 b를 생성 */ { int rowTerms[MAX_COL], startingPose[MAX_COL]; int i, j, numCol = a[0].col, numTerms = a[0].value; b[0].row = numCols; b[0].col = a[0].row; b[0].value = numTerms; if (numTerms >0) { /* 0이 아닌 행렬 */ for(i=0; i<numCols; i++) rowTerms[i] = 0; for(i=1; i<=numTerms; i++) rowTerms[a[i].col]++; startingPos[0]=1; for(i=1; i<num_cols; i++) startingPos[i] = startingPos[i=1] + rowTerms[i-1]; for(i=1; i<=numTerms; i++) { j=startingPos[s[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[i].value = a[i].value; } }

35 행렬 곱셈(1/3) 정의 mn행렬 A와 np행렬 B가 주어질 때 곱셈 결과 행렬인
D는 mp차원을 가지며, 0≤i≤m, 0≤j≤p에 대해 원소<i, j>는 다음과 같다. = < 두 희소 행렬의 곱셈 >  두 희소행렬의 곱셈 결과는 희소행렬이 아니다

36 행렬 곱셈(2/3) 희소 행렬의 곱셈 void mmult (term a[], term b[], term d[]) { /* 두 희소 행렬을 곱한다. */ int i, j, column, total B = b[0].value, totalD = 0; int rowsA = a[0].row, colsA = a[0].col; totalA = a[0].value; int colsB = b[0].col; int rowBegin = 1, row = a[1].row, sum=0; int rowB[MAX_TERMS][3]; If (colsA != b[0].row) { fprintf(stderr, “Incompatible matrices\n”); exit(1); } fastTranspose(b, newB); /* 경계 조건 설정 */ a[totalA+1].row = rowA; newB[totalB+1].row = colsB; newB[totalB+1].col = 0; column = newB[1].row; for (j=1; j<= totalB+1) { /* a의 행과 b의 열을 곱한다. */ if (a[i].row != row) { storeSum(d, &totalD, row, column, &sum); i = rowBegin; for (; newB[j].row = = column; j++) ; column = newB[j].row;

37 행렬 곱셈(3/3) } else if (newB[j].row != column) {
storeSum(d, &totalD, row, column, &sum); i = rowBegin; column = newB[j].row; else switch (COMPARE(a[i].col, newB[j].col)) { case -1: /*a의 다음항으로 이동 */ i++; break; case 0: /*항을 더하고, a와 b를 다음 항으로 이동 */ sum += (a[i++].value * newb[j++].value); break; case 1 : /* b의 다음 항으로 이동 */ j++; } /* for j <= totalB + 1문의 끝 */ for (; a[i].row = = row; i++) ; rowBegin = i; row = a[i].row; } /* for i <= totalA문의 끝 */ d[0].row = rowsA; d[0].col = colsB; d[0].value = totalD;

38 다차원 배열의 표현(1/3) 배열의 원소 수 : a[upper0][upper1]….[uppern-1] =
다차원 배열 표현 방법 행 우선 순서(row major order) A[upper0][upper1] 열 우선 순위(column major order) A[0][0] A[0][1] ··· A[0][upper1-1] ···· row0 row1 row2 rowupper0-1 A[0][0] A[1][0] ··· A[upper0-1][0] ···· col0 col1 col2 colupper1-1

39 다차원 배열의 표현(2/3) 주소 계산 (2차원 배열 – 행우선 표현)
α = A[0][0]의 주소 A[i][0]의 주소 = α + i · upper1 A[i][j]의 주소 = α + i · upper1 + j 주소 계산 (3차원 배열) : A[upper0][upper1][upper2] 2차원 배열 upper1  upper2  upper0개 A[i][0][0] 주소 = α + i · upper1 · upper2 A[i][j][k] 주소 = α + i · upper1 · upper2 + j · upper2 + k A[upper0][upper1]…[uppern-1] α = A[0][0]…[0]의 주소 a[i0][0]…[0] 주소 = α + i0upper1upper2…uppern-1 a[i0][i1][0]…[0] 주소 = α + i0upper1upper2…uppern-1 + i1upper2upper3…uppern-1

40 다차원 배열의 표현(3/3) a[i0][i1]…[in-1] 주소 = α + i0upper1upper2…uppern-1
+ in-2uppern-1 + in-1 = α 여기서 : 0≤ j < n-1

41 스트링(1/4) 추상 데이터 타입 ADT String object : 0개 이상의 문자들의 유한 집합
function : 모든 s, t ∈ string, i, j, m ∈ 음이 아닌 정수 string Null(m) ::= 최대 길이가 m인 스트링을 반환 초기는 NULL로 설정되며, NULL은 “”로 표현된다. integer Compare(s, t) ::= if (s와 t가 같으면) return 0 else if (s가 t에 선행하면) return -1 else return +1 Boolean IsNull(s) ::= if (Compare(s, NULL)) return FALSE else return TRUE Integer Length(s) ::= if (Compare(s, NULL)) s의 문자를 반환 else return 0 string Concat(s, t) ::= if (Compare(s, NULL)) s뒤에 t를 붙인 스트링을 반환 else return s string Substr(s, i, j) ::= if ((j>0) && (i+j-1)<Length(s)) s에서 i, i+1, i+j-1의 위치에 있는 스트링을 반환 else return NULL

42  스트링(2/4) C언어에서 스트링 널 문자 \0으로 끝나는 문자 배열을 의미 d o g \0 h o u s e \0
#define MAX_SIZE /* 스트링의 최대 크기 */ char s[MAX_SIZE]={“dog”}; char t[MAX_SIZE]={“house”};  char s[]={“dog”}; char t[]={“house”}; s[0] s[1] s[2] s[3] t[0] t[1] t[2] t[3] t[4] t[5] d o g \0 h o u s e \0 < C언어에서 스트링 표현 >

43 스트링(3/4) 스트링 삽입의 예 a m o b i l e \0 u t o \0 \0 a \0 a u t o \0 a u t
s a m o b i l e \0 t u t o \0 temp \0 initially temp a \0 (a) after strncpy (temp, s, i) temp a u t o \0 (b) after strcat (temp, t) temp a u t o m b i l e \0 (c) after strcat (temp, (s+i))

44 스트링(4/4) 스트링 삽입 함수 void strnins (char *s, char *t, int i)
{ /* 스트링 s의 i번째 위치에 스트링 t를 삽입 */ char string[MAX_SIZE], *temp = string; if (i < 0 && i > strlen(s) ) { fprintf(strerr, “Position is out of bounds \n”); exit(1); } if (!strlen(s)) strcpy(s, t); else if (strlen(t)) { strncpy (temp, s, i); strcat (temp, t); strcat (temp, (s + i)); strcpy (s, temp);