[자료구조] 3.배열

1. 배열의 개념

배열 : 같은 자료형을 가진 연속된 메모리 공간

2. 배열의 응용 - 다항식

다항식을 배열로 표현하는 방법에는 두 가지 방법이 있다.

1 ) 모든 계수를 순서대로 배열에 저장하는 방법

   ex) 5X^2 + 4X + 1 

5

4

1

 -> 덧셈 방법 (두 번째 방법보다는 간단)

#include
#define MAX(a,b) ((a>b)?a:b)
#define MAX_DEGREE 100
typedef struct{
   int degree;    //차수 
   int coef[MAX_DEGREE]; //계수 
}polynomial;
polynomial poly_add(polynomial A, polynomial B){
 
 polynomial C;
 int A_index=0, B_index=0, C_index=0;
 int A_degree=A.degree;
 int B_degree=B.degree;
 C.degree = MAX(A.degree, B.degree);
 
 while(A_index<=A.degree && B_index <=B.degree){
  
  if(A_degree > B_degree){
   C.coef[C_index++] = A.coef[A_index++];
      A_degree--;
      
     } else if(A_degree == B_degree){
      C.coef[C_index++]=A.coef[A_index++]+B.coef[B_index++];
      A_degree--;
      B_degree--;
      
     }else{
      C.coef[C_index++] = B.coef[B_index++];
      B_degree--;
    }
 }
 return C;
 
}
int main(){
 polynomial a = { 4, {1,2,3,4,5}};
 polynomial b = { 3, {1,2,3,4}};
 
 polynomial c = poly_add(a,b);
 
 printf("%d %d %d %d %d",c.coef[0], c.coef[1], c.coef[2], c.coef[3], c.coef[4]);
 
 }
 

2) 0이 아닌 계수들을 (계수, 차수)의 형식으로 구조체 배열에 저장하는 방법

  ex) 5X^3 + 4X + 1 

5	4	1
3	1	0

다항식에 따라서 첫 번째 방법이 공간을 많이 차지할 수도 있고 두 번째 방법이 공간을 많이 차지할 수도 있다.

3. 배열의 응용 - 희소행렬

희소 행렬이란 행렬의 값이 대부분 0인 경우를 말한다. 

이러한 행렬을 배열로 표현하는 방법에는 두 가지가 있다.

1) 2차원 배열을 사용하여 모든 항을 표현하는 방법

   ex)  A = 1  2  0  

               0  0  6

               7  0  0

1	2	0
0	0	6
7	0	0

 -> 덧셈 방법 (두 번째 방법보다는 간단)

#include<stdio.h>
#define ROWS 3
#define COLS 3
 
void matrix_add(int A[ROWS][COLS], int B[ROWS][COLS], int C[ROWS][COLS]){
    int r,c;
    for(r=0;r<ROWS;r++){
        for(c=0;c<COLS;c++){
            C[r][c] = A[r][c] + B[r][c];
        }
    }
}
 
int main(){
    int array1[ROWS][COLS] = {{1,2,0},{0,0,6},{7,0,0}};
    int array2[ROWS][COLS] = {{0,2,1},{6,0,0},{0,0,7}};
    int array3[ROWS][COLS];
    matrix_add(array1, array2, array3);
    
    printf("%d  %d  %d\n", array3[0][0], array3[0][1], array3[0][2]);
    printf("%d  %d  %d\n", array3[1][0], array3[1][1], array3[1][2]);
    printf("%d  %d  %d\n", array3[2][0], array3[2][1], array3[2][2]);
    
}

2) 항이 0이 아닌 요소들만을 (행, 열, 값)으로 표현하는 방법

   ex)  A = 1  2  0  

               0  0  6

               7  0  0

0	0	1
0	1	2
2	3	6
3	0	7