자료구조 공부#6 (배열, 구조체)

배열이란

같은 자료형의 변수를 여러개로 만드는 경우에 대부분 사용된다.

 - int list0, list1, list2, list3, list4, list5 = int list[5];

 

배열의 추상적자료형(ADT)

 

객체 : <list[n], list[n]의 값>

연산 : 

• Create(size) ::= size개의 요소를 저장할 수 있는 배열 생성
• get(A, i) ::= 배열 A의 i번째 요소 반환
• set(A, i, v) ::= 배열 A의 i번째 위치에 값 v 저장

 

1차원 배열

int list[6];
list[0] = 100;  // set 연산
value = list[0]; // get 연산

 

2차원 배열

int list[3][4]; (행,열 구조)

list[0][0]	list[0][1]	list[0][2]	list[0][3]	list[0][4]
list[1][0]	list[1][1]	list[1][2]	list[1][3]	list[1][4]
list[2][0]	list[2][1]	list[2][2]	list[2][3]	list[2][4]

 

 

구조체

구조체(structure) : 타입이 다른 데이터를 하나로 묶는 방법

 

배열(동질성)과 구조체(이질성)의 다른점

1. 구조체 선언 방법

struct studentTag{
	char name[10];  //문자 배열로된 이름
    int age; 		//나이를 나타내는 정수값
    double gpq;		//평균평점을 나타내는 실수값
}

struct studentTag s1; //s1 이 변수이름

strcpy(s1.name, "Kim");
s1.age = 20;
s1.gpq = 4.3;

 

2. 구조체 선언 방법 (typedef)

typedef struct studentTag{
	char name[10];
    int age;
    double gpa;
} student;

student s;

student s = {"Kim", 20, 4.3};

typedef struct studentTag{
	char name[10];
    int age;
    double gpa;
} student;

int main(void){
	student a = {"Kim",20, 4.3}
    student b = {"Park",21, 4.2}
}

---

다항식에서 배열의 응용

다항식의 일반적인 형태

배열을 사용한 2가지 방법

1. 다항식의 모든 항을 배열에 저장
2. 다항식의 0이 아닌 항만을 배열에 저장

 

다항식 표현 방법 #1

모든 차수에 대한 계수값을 배열에 저장

하나의 다항식을 하나의 배열로 표현

ex) 10x^5+6x+3

x^5	x^4	x^3	x^2	x^1	x^0	.	.	.
10	0	0	0	6	3	.	.	.

 

구조체와 배열로 다항식 계산 구현

 

#define MAX(a,b) (((a) > (b)) ? (a) : (b)) //a와 b를 비교해서 큰값을 MAX에 선언
#define MAX_DEGREE 101 					//다항식의 최대차수 +1

typedef struct{
	int degree;
    float coef[MAX_DEGREE];
} polynomial;

polynomial a = {5,{10,0,0,0,6,3}} // a에 5차수 10x^5+6x+3 을 선언

 

//C = A+B 다항식의 덧셈
polynomial poly_add1(polynomial A, polynomial B){
	polynomial C; // 결과 다항식
    int Apos = 0, Bpos = 0, Cpos = 0; 배열의 인덱스 값
    int degree_a = A.degree;
    int degree_b = B.degree;
    C.degree = MAX(A.degree, B.degree); // 결과 다항식의 최대 차수
    while(Apos <= A.degree && Bpos <= B.degree){
    	if(degree_a > degree_b){	//A항 > B항 일때
        	Ccoef[Cpos++] = A.coef[Aposs++]
            degree_a--;
        }
        else if (degree_a == degree_b) {
        	Ccoef[Cpos++] = A.coef[Aposs++] + B.coef[Bpos++];
            degree_a--; 
            degree_b--;
        }
        else {
        	C.coef[Cpos++] = B.coef[Bpos++];
            degree_b--;        
        }
    }
    return C;
}


// 다항식 출력함수
void print_poly(polynomial p){
	for (int i = p.degree; i>0; i--)
    	printf("%3.1f x^%d +"p.coef[p.degree-i],i);
    printf("%3.1f \n", p.coef[p.degree]);    
}

int main(void){
	polynomial a = {5, {3,6,0,0,0,10}}; // 3x^5 + 6x^4 + 10
    polynomial b = {4, {7,0,5,0,1}};    // 7x^4 + 5x^2 + 1
    polynomial c;
    print_poly(a);
    print_poly(b);
    c = poly_add1(a,b);
    printf("결과값\n");
    print_poly(c);
    return 0;

}

 

다항식 표현 방법 #2

다항식에서 0이 아닌 항만을 배열에 저장

(계수, 차수) 형식으로 배열에 저장

ex) 10x^5+6x+3 ->? [(10,5),(6,1),(3,0)]  - 순서쌍 형식으로 배열에 저장

 

#define MAX_TERM 101

struct{
	float coef; // 계수
    int expon; // 차수
} terms[MAX_TERMS];

int avail;

 

구조체 배열 형식으로 순서쌍 배열을 구현한 코드

 

term 구조체 배열 구조 설명 이미지

첫번쨰 식을 계수와 차수로 각각 넣고 그 다음 배열공간에 다음 다항식을 넣는 식이다.

avail은 이걸 다넣은 다음 다시 term에 추후 더한 결과값을 넣기위해 빈공간을 알기위해 선언해둔 변수이다.

메모리 아낄려구 이미 변수 구조부터 부터 여러 삽질이 시작된다..

 

#include<stdio.h>
#include<stdlib.h>

#define MAXTERMS 101
struct{
	float coef;
    int expon;
} terms[MAX_TERMS]
		={{8,3}, {7,1}, {1,0}, {10,3}, {3,2}, {1,0}};
        // (8X^3 + 7x^1 + 1) , (10X^3 + 3X^2 + 1)

// 위에 다항식을 다 넣고 남는 공간 배열의 위치
int avail = 6        
        
        
// 각각 차수 비교후 케이스를 나누기 위한 함수        
// 두개 정수 비교
char compare(int a, int b){
	if(a>b) return ">";
    else if (a==b) return "=";
    else return "<";
}

// 새로운 항을 다항식 구조체 배열에 추가하는 함수
void attach(float coef, int expon){
	if( avail > MAX_TERMS){
    	fprintf(stderr, "항의 개수가 너무 많음\n");
        exit(1);
    }
    terms[avail].coef=coef;
    terms[avail++].expon = expon;
}

//C = A+B
poly_add2(int As, int Ae, int Bs, int Be, int *Cs, int *Ce){
	float tempcoef;
    *Cs = avail;
    while (As <= Ae && Bs <= Be){
    	switch(compare(terms[As].expon, terms[Bs].expon)){
        case '>':
        	atttach(terms[As].coef, terms[As].expon);
            As++;
            break;
        case '=':
        	tempcoef = terms[As].coef + terms[bs].coef;
            if (tempcoef) attach(tempcoef, terms[As].expon);
            As++;
            Bs++;
            break;
        case '<':
        	attach(terms[Bs].coef, terms[Bs].expon);
            Bs++;
            break;
        }
    }
    for(; As<= Ae; As++)
    	attach(terms[As].coef, terms[As].expon);
    for(; Bs<= Be; Bs++)
    	attach(terms[Bs].coef, terms[Bs].expon);
    *Ce = avail = 1;    
}


void print_poly(int s, int e){
	for(int i = s; i < e; i++){
		printf("%3.1fx^%d", terms[i].coef, terms[i].expon);
    }
    printf("%3.1fx^%d\n", terms[e].coef, terms[i].expon);
}

int main(void){
	int As = 0, Ae = 2, Bs = 3, Be = 5, Cs, Ce;
    poly_add2(As, Ae, Bs, Be, &Cs, &Ce);
    print_poly(As, Ae);
    print_poly(Bs, Be);
    printf("------------------------\n");
    print_poly(Cs,Ce);
    return 0;
}

 

뭐야 이거 무서워 아무래도 교수님이 직접 구현하신 코드를 하나하나 읽어보면 메모리 절약 이라는거에 어마어마한 신경을 쓴거 같다... 구조체 배열 두개로 쓸만한 부분도 최대한 배열 하나로만 구현해서 계산하고 처리를 한다.
심지어 임시로 저장할 부분을 포인터를 써가면서 줄하나하나 줄이는 모습..
단순히 메모리 용량을 아끼기 위해서 함수 한두개가 추가되고 계산도 복잡해지는 모습이 눈에 띌것이다.
교수님도 요즘에는 메모리 용량이 부족할일이 적어지니 알고만 있으라는 식으로 설명했으니 참고만 하자..

 

---

느낀점 : 다항식을 사용하는데 배열을 사용할 수 있는데, 요즘시대엔 메모리가 부족할 일은 없어서 차수에 맞춰 같은항에 차수의 값을 넣는 식으로 많이 사용한다고 한다. 메모리를 아끼기 위해선 다른 방법도 있다는데 교수님께선 크게 다루지 않으셔서 알고 싶으면 개인적으로 알아보아야 할거 같다.

복학하고 구조체와 배열을 사용하여 코드를 하는걸 오랜만에 봤다. 재밌었다.