제2장 배열과구조

2.1 배열(추상데이타타입) 배열과 구조 • 연속된 메모리 위치의 집합 - 자료구조와 그 기억장소 구현의 혼동 • <index, value>쌍의 집합 set of mappings (or correspondence) between index and values array : i → ai

2.1 배열(추상데이타타입) Structure Array Objects : index의 각 값에 대하여 집합 item에 속한 한 값이 존재하는 <index, value>쌍의 집합. index는 일차원 또는 다차원의 유한 순서 집합이다. 예를 들면, 일차원의 경우 {0,‥, n-1}과 이차원 배열 {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)}, 등이다.

2.1 배열(추상데이타타입) 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) return 새로운 쌍<i, x>가 삽입된 배열 A. end Array

2.1 배열(추상데이타타입) 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]

2.1 배열(추상데이타타입) 변수 메모리 주소 ----------------------------  변수           메모리 주소 ---------------------------- list[0] 기본주소 = α = 1000 list[1] α + sizeof(int) list[2] α + 2・sizeof(int) list[3] α + 3・sizeof(int) list[4] α + 4・sizeof(int)

2.1 배열(추상데이타타입) 포인터 해석 int *list1; int list2[5]; list2 = list2[0]를 가리키는 포인터 list2 + i = list2[i]를 가리키는 포인터 (list2+i) = &list2[i],  *(list+i) = list2[i]

2.1 배열(추상데이타타입) 예제 배열의 합을 계산하는 프로그램 작성

2.1 배열(추상데이타타입) #define MAX_SIZE 100 float sum(float [], int); float input[MAX_SIZE], answer; 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) { int i; float tempsum = 0; for (i = 0; i < n; i++) tempsum += list[i]; return tempsum; }

2.1 배열(추상데이타타입) • 호출시 input(=&input[0])은 임시 장소에 복사 - 형식 매개 변수 list와 연관 • 역참조(dereference) - list[i]가 "="기호 우측 ⇨ (list + i)가 가리키는 값 반환 - list[i]가 "="기호 좌측 ⇨ 값을 (list + i) 위치에 저장

2.1 배열(추상데이타타입) C 언어의 매개변수 전달방식 : call-by-value ? 배열 매개변수는 그 값을 변경함

2.1 배열(추상데이타타입) 예제 2.1 [일차원 배열의 주소 계산] : int one[] = {0, 1, 2, 3, 4}; print1(&one[0], 5)

2.1 배열(추상데이타타입) void print1(int *ptr, int row) { /* 포인터를 사용한 일차원 배열의 출력 */ int i; printf("Address Contents\n"); for (i=0; i<rows; i++) printf("%8u%5d\n", ptr+i, *(ptr+i) ); printf("\n"); }

Intel 386환경 => 정수의 사이즈(2바이트) 2.1 배열(추상데이타타입) 주 소 내 용 1228 0 1230 1 1232 2 1234 3 1236 4 Intel 386환경 => 정수의 사이즈(2바이트)

2.2 구조&유니언 구조(structure) : struct • 타입이 다른 데이타를 그룹화 (레코드) • 데이타 항목의 집단 - 각 항목은 타입과 이름으로 식별 struct { char name[10]; int age; float salary; } person;

2.2 구조&유니언 배열 int i[3] 구조 struct person i[3]; int char name[10]; int age; float salary; } person; 2.2 구조&유니언 배열 int i[3] 구조 struct person i[3]; int char name[10]; int age; float salary; i[0] i[0] int char name[10]; int age; float salary; i[1] i[1] int char name[10]; int age; float salary; i[2] i[2]

2.2 구조&유니언 구조의 멤버 연산자=> “.” strcpy(man.name, "james"); man.age =10; man.salary = 35000; struct { char name[10]; int age; float salary; } person; struct person man; char name[10]; int age; float salary;

2.2 구조&유니언 typedef 문장을 사용한 구조 데이타 타입 생성 typedef struct human_being {    typedef struct { char name[10];                     char name[10];       int age;                       int age;             float salary;                       float salary;  } ;                             } human_being ;

2.2 구조&유니언 변수 선언 human_being person1, person2 ; if (strcmp(person1.name, person2.name)) printf("두 사람의 이름은 다르다.\n"); else printf("두 사람의 이름은 같다.\n"); - 전체 구조의 동등성 검사 :  if (person1 == person2) - 구조 치환 :  person1 = person2 strcpy(person1.name, person2.name); person1.age = person2.age; person1.salary = person2.salary;

2.2 구조&유니언 구조 속의 또다른 구조 정의 typedef struct { int month; int day; int year;     } date;      typedef struct human_being {            char name[10]; int age; float salary; date dob; }; [예] Human_being person1; person1.dob.month = 2; person1.dob.day = 11; person1.dob.year = 1944;

2.2 구조&유니언 유니언(union) • union의 필드들은 메모리 공간을 공용 • 한 필드 만 어느 한 시점에 활동적이 되어 사용 가능

2.2 구조&유니언 typedef struct sex_type { enum tag_field {female, male} sex; union { int children; int beard; } u ; }; typedef struct human_being { char name[10]; int age; float salary; date dob; sex_type sex_info; human_being person1, person2; 값 할당 person1.sex_info.sex = male; person1.sex_info.u.beard = FALSE; person2.sex_info.sex = female; person2.sex_info.u.children = 4;

2.2 구조&유니언 구조 유니언 char name[10]; int age; float salary; struct { char name[10]; int age; float salary; } person; 유니언 typedef struct sex_type { enum tag_field {female, male} sex; union { int children; int beard; } u ; }; char name[10]; int age; float salary; enum tag_field sex; int children; enum tag_field sex; int beard;

2.2 구조&유니언 sex children beard id typedef struct sex_type { int sex; union { int children; int beard; } u ; int id; }; sex children beard id

2.2 구조&유니언 자체참조 구조 (self_referential structure) • 구성요소중 자신을 가리키는 포인터가 존재하는 구조         typedef struct list {            char data;    list *link;    };    

2.2 구조&유니언 list item1, item2, item3; item1.data = 'a'; typedef struct list {            char data;    list *link;    };   2.2 구조&유니언 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; Item3.link = &item3; data link a b c

순서 리스트 (Ordered list, linear list) 2.3 다항식 추상 데이터 타입 순서 리스트 (Ordered list, linear list) 원소들의 순서가 있는 모임 A = (a1, a2, ..., an) ai   : atom n=0  : empty list 예) Days-of-week (Mon, Tue, Wed, Thu, Fri, Sat, Sun)  : list 1st   2nd  3rd  4th  5th  6th  7th   : order

2.3 다항식 추상 데이터 타입 연 산 길이계산 n 읽기 (R→ L, L→ R) 항목검색 i-th element, 0≤i<n 항목수정 i-th element's value, 0≤i<n    항목삽입 (i번째 위치, 0≤i≤n)  i, i+1, ..., n-1 ⇨ i+1, i+2, ..., n 항목삭제 (i번째 항목, 0≤i<n)  i+1, ..., n-1 ⇨ i, i+1, ..., n-2

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

2.3 다항식 추상 데이터 타입 기호 다항식의 조작 다항식의 덧셈, 곱셈연산을 위한 자료구조 A(x) = 3x20 + 2x5 + 4 B(x) = x4 + 10x3 + 3x2 + 1 다항식의 덧셈, 곱셈연산을 위한 자료구조

2.3 다항식 추상 데이터 타입 다항식표현법 A(x)=anxn+an-1xn-1+...+a1x1+a0x0 axe a : coefficient an ≠ 0 e : exponent - unique x : variable x 차수(degree) : 다항식에서 가장 큰 지수

2.3 다항식 추상 데이터 타입 polynomial 추상 데이타 타입 Structure Polynomial Object: 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  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

2.3 다항식 추상 데이터 타입 다항식의 표현 (I) - 지수들은 내림차순으로 정돈 #define MAX_DEGREE 101 /* 다항식의 최대 차수 + 1 */ typedef struct { int degree;       float coef[MAX_DEGREE];        } polynomial;

2.3 다항식 추상 데이터 타입 a : polynomial, n < MAX_DEGREE A(x)=Sum (aixi) typedef struct { int degree;       float coef[MAX_DEGREE];        } polynomial; a : polynomial, n < MAX_DEGREE A(x)=Sum (aixi) a.degree = n a.coef[i] = an-i, 0 ≤ i ≤ n

2.3 다항식 추상 데이터 타입 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+3x2+1   : n = 4 A = (4, 1, 10, 3, 0, 1)    : 6 elements

2.3 다항식 추상 데이터 타입 다항식의 표현 (II) a.degree << MAX_DEGREE ⇨ a.coef[MAX_DEGREE]의 대부분이 필요없음 A(x) = x1000 + 1         : n = 1000 A = (1000, 1, 0,..., 0, 1)   : 1002 elements ↳ 999

2.3 다항식 추상 데이터 타입 A(x) = bm-1xem-1 + bm-2xem-2 + ... + boxe0 where bi ≠ 0 , 0≤i≤m-1, em-1>em-2>...>eo≥0 A = (m, em-1, bm-1, em-2, bm-2, ... , e0, b0) ↳ # of non-zero terms 예) A(x) = x4+10x3+3x2+1 ⇨ A = (4, 4, 1, 3, 10, 2, 3, 0, 1) A(x) = x1000 +1 ⇨ A = ( 2, 1000, 1, 0, 1)

2.3 다항식 추상 데이터 타입 다항식 덧셈 알고리즘 D=A+B

#define COMPARE(x,y) ((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1) 함수 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: /* a < b */ d = Attach (d, Coef(b, Lead_Exp(b)), Lead_Exp(b)); b = Remove(b, Lead_Exp(b)); break; case 0: /* a = b */ 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)); } case 1: /* a > b */ d = Attach(d, Coef(a, Lead_Exp(a)), Lead_Exp(a)); a 또는 b의 나머지 항을 d에 삽입한다.

2.3 다항식 추상 데이터 타입 자료구조 선택 배열 ? 구조체 ? 공용체 ?

2.3 다항식 추상 데이터 타입 MAX_TERMS 100 /* 항 배열의 크기 */ typedef struct { float coef;                 int expon; } Polynomial; Polynomial terms[MAX_TERMS]; int avail = 0; <= 전역변수

2.3 다항식 추상 데이터 타입 A(x)=2x1000+1 B(x)=x4+10x3+3x2+1          starta  finisha startb                finishb  avail               ↓       ↓       ↓                          ↓      ↓ A(x) : <starta, finisha> finisha = starta+n-1 coef 2 1 1 10 3 1 c 1000 4 3 2

void padd(int starta, int finisha, int startb, int finishb, int 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, terms[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++; } /* A(x)의 나머지 항들을 첨가한다 */ for(; starta <= finisha; starta++) /* B(x)의 나머지 항들을 첨가한다 */ for(; starta <= finishb; startb++) attach(terms[startb].coef, terms[startb].expon);       *finishd = avail-1;

2.3 다항식 추상 데이터 타입 void attach(float coefficient, int exponent) {    /* 새 항을 다항식에 첨가한다. */ if (avail >= MAX_TERMS) { fprintf(stderr, "다항식에 항이 너무 많다."); exit(1);      } terms[avail].coef = coefficient; terms[avail++].expon = exponent; }

2.3 다항식 추상 데이터 타입 알고리즘 padd 의 분석 : • m, n (>0) : 각각 A와 B의 0이 아닌 항의 수 • while 루프 - 각 반복마다 starta나 startb 또는 둘 다 값이 증가 - 반복 종료 -> starta <= finisha && startb <= finishb - 반복 횟수 ≤ m+n-1 A(x) = Sum(i=0, i=m) x2i 와 B(x) = Sum(i=0, i=n) x2i+1   • for 루프 :  O(m+n) ∴ 연산시간 =  O(n+m)

2.3 다항식 추상 데이터 타입 ※ 문제점 avail = MAX_TERMS ? ⇨ 불필요한 다항식 제거후 배열 끝에 연속적인 가용공간 생성(압축 함수) - 데이타 이동시간, 각 다항식의 starti, finishi 변경

과제물 프로그램 2.2 배열의 주소 출력하는 P/G (print1) 자체참조구조 P/G 다항식의 덧셈 P/G