[DS] Ch2. Arrays and Structures

Structures

- data item들의 collection

struct {
	char name[10];
    int age;
    float salary;
    } person;

=> structure 멤버 변수에 "."을 통해 접근 가능함

strcpy(person.name, "james");
person.age = 10;
person.salary = 35000;

typedef

typedef struct humanBeing
{
	char name[10];
    int age;
    float salary;
};

• Variable declaration(변수 선언) : typedef를 붙이면 humanBeing 자체가 하나의 type이 됨.
  ex) humanBeing person1, person2; 와 같이 변수로 선언 가능
• Equality check : 불가
  ex) if (person1 == person2) -> X
  대신, person1.name == person2.name / person1.age == person2.age와 같은 방식으로 서로가 같은지 다른지 체크하는 것은 가능
• Replacement : 가능
  ex) person1 = person2
  strcpy(person1.name, person2.name);
  person1.age = person2.age
  person1.salary = person2.salary

Embedding a structure within structure

typedef struct {  // date라는 type 정의됨
	int month;
    int day;
    int year;
} date;

	char name[10];
    int age;
    float salary;
    date dob;  // date라는 type에는 생년월일 정보 저장됨(month, day, year)
};

(human_being type의 변수) . dob . (date type의 개체)
person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

typedef struct list {  // list라는 type 정의됨
	char data;
    list *link;  // list type을 가리키는 포인터 link
};

list [data | link]
list item1, item2, item3;
=>
item1[data | link]
item2[data | link]
item3[data | link]
item1.data = 'a';
item2.data = 'b';
item3.data = 'c';
=>
item1['a' | link]
item2['b' | link]
item3['c' | link]
item1.link = item2.link = item3.link = NULL;
=>
각 list의 끝 = NULL
item1['a' | NULL]
item2['b' | NULL]
item3['c' | NULL]
item1.link = &item2;
item2.link = &item3;
=>
item1['a' | link] --> item2['b' | link] --> item3['c' | link]

Polynomials

• 다항식 -> 일종의 ordered list(linear list)

• P(x) = a1x^e1 + ... + anx^en
  a1, a2, ... , an -> 계수(coefficient)
  e1, e2, ... , 2n -> 지수(exponent)
  a1x^e1, a2x^e2, ... , anx^en -> 항(term)

• 다항식이 몇 차인가?(차수) => 가장 큰 지수값

• A(x) = 3x^20 + 2x^5 + 4 => 20차 다항식
  B(x) = x^4 + 10x^3 + 3x^2 + 1 => 4차 다항식

• Ordered list (linear list) : 데이터의 순서가 있는 집합
  ex) Days-of-week : (Mon, Tue, Wed, Thu, Fri, Sat, Sun)

• Operations on ordered list :

1. list 길이
2. 읽는 순서(오->왼 / 왼->오)
3. i번째 원소값 반환
4. i번째 원소값 변경
5. i번째 위치에 값 삽입
6. i번째 항목 삭제

ADT of Polynomial

• <exponent, coefficient>의 쌍으로 나타낼 수 있음. => <ei, ai>
  

Polynomial Representation

ex)
A(x) = 2x^100 + 3x^5 - x^2 + x
B(x) = x^99 - 2x^5 + x^3 + x^2 + 1
...........................................................................................................
A(x)+B(x) = 2x^100 + 2x^99 + x^5 + x^3 + x + 1
.
코드로 구현하려면 A(x)와 B(x)의 최고차항의 차수 개수만큼의 array 생성,
각 차수를 더한 array 생성.
But, 차수가 클 경우 array 크기가 커지므로 메모리 낭비가 커짐.
A(x) : n차, B(x) : n차라면 -> O(n) : 차수에 비례하는 계산 시간 소요

• typedef로 type polynomial 생성

#define MAX_DEGREE 101  // 최고차항 차수 + 1
typedef struct {
	int degree;
    float coef[MAX_DEGREE];
    } polynomial;
    polynomial a;
    a.degree = n
    a.coef[i] = an-i, o<=i<=n

-> 메모리 낭비 큼.

• store only non-zero terms (차수가 0이 아닌 항만 저장)

#define MAX_TERMS 100
typedef struct {
	float coef;
    int expon;
    } polynomial;
    polynomial terms[MAX_TERMS];
    int avail = 0;
    int starta, finisha;

exponent 값 비교 순서 : 0-3 => 1-2 => 1-3 => 1-4 => 1-5
위의 경우, A(x) 항이 n개, B(x) 항이 m개라면, O(n+m) : 포인터가 움직이는 횟수에 비례(attach되는 횟수에 비례)

Polynomial Addition Code

아래는 call by reference의 경우 (&로 보내고 *로 받음)

#define MAX_TERMS 100
typedef struct {
	float coef;
    int expon;
    } polynomial;
    polynomial terms[MAX_TERMS];
    int avail = 0;
    int starta, finisha;
    
// add A(x) and B(x) to obtain D(x)

void padd(int startA, int finishA, int startB, int finishB, int *startD, int *finishD) 
// *startD, *finishD : 포인터인 이유? => 결과를 return 해줘야 해서
{
	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:  // equal exponents
            	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++;
        }
        // add in remaining terms of A(x)
        for ( ; startA <= finishA; startA++)
        	attach(terms[startA].coef, terms[startA].expon);
        // add in remaining terms of B(x)
        for ( ; startB <= finishB; startB++)
        	attach(terms[startB].coef, terms[startB].expon);
        *finishD = avail - 1;
}

void attach(float coefficient, int exponent)
{ // add a new term to the polynomial
	if (avail >= MAX_TERMS) {
    	fprintf(stderr, "Too many terms in the polynomial\n");
        exit(EXIT_FAILURE);
    }
    terms[avail].coef = coefficient;
    terms[avail++].expon = exponent;
    // = terms[avail].expon = exponent;
    //   avail += 1;
}

Polynomial Multiplication

• A(x) = 2x^100 + 3x^5 + 2
  B(x) = x^5 + x^3 + x
  .........................................................
  A(x)*B(x) = 2x^105 + 2x^103 + 2x^101 + 3x^10 + 3x^8 + 3x^6 + 2x^5 + 2x^3 + 2x
• 계수(coefficient)끼리는 곱, 지수(exponenet)끼리는 합