1. about C

A. Review ! 

 

switch.. 이런거 다시 보기

 

&연산자 -> 주소

* 연산자 -> 그 주소가 가리키는 값 (dereferencing)

(c에서 포인터 = 주소. *형변수=포인터=주소값)

 

배열 array

array 예제

int* a[3]

->int형 pointer 3개를 담은 배열

 

배열의 이름 = 첫주소 (배열의 이름 변수 = 상수형태의 포인터) (arr = &arr)

배열 다음친구의 주소 = 첫주소 + 자료형

 

* 배열 선언시

int i=5;

int a[i]; 안됨 !! (변수로 배열 선언하는거 안됨)

-> 동적할당으로 하기 ! 

int *a=(int*)malloc(sizeof(int)*i);

* 동적할당시 - dangling pointer 발생 가능 (허상 포인터)

= 이미 free된 메모리 영역을 가리키는 포인터.

ex) int* ptr =malloc 하고 free 함 -> 그 메모리는 해제되엇지만 ptr은 여전히 거기 가리킴 

-> 해결방법 : free 후 해당 pointer 변수에 NULL을 할당해준다 !

 

int *list1 vs int list2[5]

- 공통점 : list1, list2 은 포인터임 ( 배열의 이름 = 배열 시작 주소 )

- 차이점 : list2는 five location 가짐

- (list2+i) = list2[i]의 주소 -> *(list2+i) = list2[i]

 

*예제

배열의 address 와 value 출력

//배열 이름이 ptr일 때 (자료형 = 포인터)
int i=0;
for (i=0;i<rows;i++){
	printf("%8u%5d\n", ptr+i, *(ptr+i));
}

 

 

* 포인터의 덧셈 연산 ->= +1 하면 해당 포인터 변수의 자료형의 크기만큼 주솟값이 증가함 (감소도 마찬가지)

(int면 해당 주소에서 +4)

 

* 주소 프린트할 때는 printf("%u\n", 주소); !! / %p : 16진수 / %d : 10진수

 

- 배열을 함수로 전달할 때 -> 무조건 포인터로 전달 ! 그냥 int형 이런식으로 하면 그냥 안댐 ㅋ 또는 int arr[] 이런식으로도 가능

(왜냐면 배열 자체가 포인터 이니가. 주소 저장하는 거니까)

int* arr = int arr[] !!

둘은 완전히 동일한 선언 !

 

2차원배열

-> 포인터는 ** !

배열의 배열임

배열은 포인터형이고 그걸 담고잇는 변수 이므로 

포인터형으로 표현할 때는 ** 해야함

(메모리는 일직선으로 저장됨 ! arr[0] - 여기에 arr[0][1,2,3,4]가 저장되고 그다음 arr[1]에 ... ) -->>

 

 

구조체

-> 여러 자료형의 변수를 묶어 나만의 새로운 자료형 만드는 것

struct structName { } ;  -> struct structName  var;이렇게 선언

이름 바꾸기 

typedef struct structName 바꿀이름; 

-> 한번에도 가능

typedef struct name { } 바꿀이름;

or

typedef struct { } 바꿀이름 ;  // 구조체 이름 생략가능)

(얘도 typedef 변수이름 바꿀이름; 이거 형식이랑 똑같은거 !)

 

- 생성과 동시에 초기화 

-> stuc a ={ 1, 2, 3 } 이렇게 가능 (선언 동시 초기화 시에만 !! )

 

- 스스로 가리키기도 가능 ! self-referential structure

typedef struct list{
	char* data;
    list* link;
}

이런식으로 다른 struct를 가리키는 꼬리에 꼬리를 무는 struct도 생성 가능 !

 

Union ( = 공용체 )

: 각 멤버 변수마다 메모리 할당하는 게 아니라, 가장 큰 메모리 가진 변수의 공간만큼만 할당된다

-> 멤버 변수 하나씩만 사용 가능 !! 오직 하나의 field만 active 됨 !!

바로 모든 멤버 변수가 하나의 메모리 공간을 공유한다다 !

모든 멤버 변수가 같은 메모리를 공유하므로, 공용체는 한 번에 하나의 멤버 변수밖에 사용할 수 없습니다.

(메모리 부족할 때 사용되었엇음.)

---

B. Practice ! 

The Polynomials (다항식)

ADT

A(x), B(x) 식이 주어졌을 때 더하기와 곱셈 할 수 있도록 해보장

ADT 만드러보자 abstraction ~

Representation 1.

typedef struct{
    int degree;
    float coeff[max_degree]; 
    // 이 프로그램 내에서 가능한 최고차항만큼 일단 배열 생성해놓음 ㄷ ㄷ 동적할당도 아니라닝
};

// 맨앞 [0] 이 최고차항. 점점 내림차순 !
// coeff[i]= x^(n-i)

배열 형식으로 저장. (하나의 struct에 전부 저장) 높은차항->낮은차항 전부

-> 가장 무식한 방법. 이렇게 하면 x^100 + 1 일 때 중간 차항들 다 0 인데 공간 잡혀잇는것. 매우 비효율적

 

Representation 2.

하나의 항에 대한 struct을 만들어서 그 배열을 만듦

typedef struct{
	float coeff; //계수
    int expon; //차수
}polynomial;

poly_term[Max_term]; // 최대 가능한 항의 개수 !

(위에는 해당 배열에 모든 차수에 대한 공간을 할당하여 배열 만들었지만

여기는 가능한 항들의 개수만큼 일단 공간을 만들어 두고 거기에 사용할 항들을 넣는것.

위는 최대 차수 공간, 아래는 최대 항 개수 공간을 만들어둔다)

 

덧셈연산

: 모든건 큰 하나의 배열 (poly_term)을 만들어서 한다

각 항은 terms 이라는 배열에 poly라는 구조체의 형식으로 저장되어잇음 ~~ 구조체로 ~~

그래서 각 다항식도 아래 보이는 것처럼 순서대로 쭉 저장함

더하는 것도 B(x) 다음 자리부터 해당 더해진 식이 저장됨 !! ~~~

각 항은 terms 이라는 배열에 poly라는 구조체의 형식으로 저장되어잇음 ~~ 구조체로 ~~

// 걍 대충 이 방법일때 덧셈 어캐하는 지 해보기

void padd(int startA, int finishB, int startB, int finishB, int* startD, int* finishD){
	float coefficient;
    	*startD = avail; // startD는 D의 맨처음 인덱스이겟지. 이거를 avail로 설정
    
    // 1. a,b 두 식 더하는 연산. 둘 중 하나라도 항 끝나면 넘어감.
    while (startA<=finishA && startB<=finishB){
    	switch(COMPARE(term[startA].expon, term[startB].expon){
            case -1:  // a<b
            	attach(terms[startB].coef, terms[startB].expon); //이 항을 붙인다
                startB++;
                break; // switch문 조건 나갈땐 걍 무조건 이거씀 while나간다는거 아님
            case 0: //a==b
            	attach(terms[startA].coef+terms[startB].coef,terms[startA].expon);
                // 계수를 더해서 넣음. 당연
                startA++;
                startB++;
                break;
            case 1: // a>b
            	attach(terms[startA].coef, terms[startA].expon);
                startA ++;
    }
    //남은 항들 그냥 더해줌. 분명 둘중 하나가 남아잇을 거임!
    for (; startA<=finishA;startA++) // 이미 다 더해져잇으면 (b만 남아잇으면) 이거 실행도 안됨~
    	attach(terms[startA].coef, terms[startA].expon);
    //b도 똑같이! 얘도 안남아잇으면 밑에꺼 실행도 안될꺼임 (이미 조건 만족x니까. 이미 start가 finish넘엇으니까
    for (; startB<=finishB;startB++)
    	attach(terms[startB].coef, terms[startB].expon);
    
    *finishD = avail -1
    //attach할 때 avail이 하나씩 뒤로 밀렷을꺼임 ! 그래서 마지막 D의 인덱스는 딱 avail의 이전일꺼니까 그렇게 저장해줌

---

Sparse Matrices

* 그냥 행렬 저장 -> 0이 너무 많다 ! -> 새로운 방식

행렬 저장 방식 -> row, col, value의 값만 사용하여 배열을 저장한다

row, col, value를 담는 노드를 array에 하나씩 저장함

* a[0] -> 전체 row,col수, 전체 값 개수(0아닌거)를 저장함

* (b)는 transpose

 

자료구조 정의

typedef struct{
    int col;
    int row;
    int value;
} term;

term a[MAX_TERMS]; //MAX_TERMS = term + 1 (인덱스 0에 정보 저장할것이므로 !!)
//이때 maxterm은 row의 개수 / 0이 아닌 항의 개수 (value 개수)

transpose

원래 배열이랑 transpose된 배열 순서 같아야함. 뒤집어져만 잇어야댐

원래 배열은 row작은 순 - column작은 순으로 저장되어 있으므로

transpose된 배열은 컬럼 작은 순으로 쌓아줘야됨 ! -> column기준으로 !

currentB=1;
for(int i=0; i<a[0].column; i++){ // i=컬럼
    for(int j=1; j<=a[0].value(=꼭들어가야댐!!); j++){ //a의 인덱스 (순서대로). 0은 기본정보 담고잇는 것이므로 생략
        if (a[j].column==i){
            b[currentB].row=a[j].column;
            b[currentB].column=a[j].row;
            벨류도 복사
            currentB++;
        }
    }
}

 

- 복잡도

: O(terms * colums) = O (rows * columns^2) // term=c*row

 

=> fast transpose 가능 ! ; (복잡도 더 작은)

- 복잡도 : O(terms + columns)

: 기본 개념은 각 column이 저장될 곳을 미리 파악하는 것

-> column index 저장을 위한 추가적인 공간이 필요함 ! (메모리면에는 손해지만 시간 복잡도는 내려간다)

row term은 해당 인덱스가 컬럼이고 그 컬럼에 몇개의 term이 있는지를 저장함

starting pos는 몇번째 원소부터 그 컬럼에 들어가는지를 저장함 (앞에들어잇던거 +1) !

-> b 배열에서 몇번째 인덱스에 그 값이 들어가는지, 말 그대로 starting position을 정의해줌!

 

b[0].row=a[0].column; // row, column, value 저장해줌

//rowTerms초기화 후 저장
for(int i=0; i<a[0].column;i++)
    rowTerms[i]=0;
for(int i=1;i=<a[0].values; i++)
    rowTerms[a[i].column]++; // column에 term잇으면 +1 해쥼

//startingPos 저장 -> 걍 sp 이전꺼 +rowterm하면됨
startingPos[0]=1;
for(int i=1; i<a[0].column;i++){ //0인덱스는 이미 저장 햇으므로
    startingPos[i]=startingPos[i-1]+rowTerms[i-1];
}

//이제 b배열에 원소 저장!
for(int i=1; i<=a[0].values; i++){
    j=startingPos[a[i].columns]++; 
    // 배정 후 값 키움 ^^ 해당 노드의 컬럼가진원소 몇번째로 들어가는지 셈 ! 약간 한번 세면 해당 인덱스의 startingPos값이 +1되는 듯
    b[j].row=c; b[j].c=r;
    b[j].value=v; //값배정 ^^
}

starting pos 값 -> 인덱스가 됨 !!!

( ++ 해야됨 !!!! ; 값 배정 후 하나 증가시켜주는 것!!!! )

 

Matrix multiplication

: A[mxn] x B[nxp] ! 두 sparse matrices를 곱한다

* classical multiplication

for (i=0; i<rowsA;i++){
    for(j=0;j<colsB;j++){
        sum=0;
        for(k=0; k<rowsB or colsA (둘이같음) ; k++)
            sum+=a[i][k]*b[k][j];
        d[i][j]=sum;
    }
}

복잡도 = O(rowsA*colsA*colsB)