자료구조 003 | Arrays and Structures + Polynomials (2)

67102 단어 자료구조자료구조

1. Structure 구조체

1) person 이라는 변수를 하나 생성

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

2) 해당 구조체 변수에 접근

strcpy(person.name, "james"); //문자열 부분은 str copy 라는 기능으로 접근!
person.age = 10;
person.salary = 35000;

3) typedef struct 로 아예 새로운 data type 생성

=> 위의 struct{~} 변수명으로 변수 생성하는 것은 여러개 구조체 변수 만들 때 귀찮
=> 아예 구조체 새로운 변수 type을 지정해주는 것 => typedef struct {~} type명
=> type명 변수명 만 해주면 새로운 구조체 변수 생성 가능!

(ex)

  • 자료형 생성
typedef struct {
char name[10];
int age;
float salary;
} humanBeing;
  • 변수 선언
humanBeing person1, person2;

4) typedef struct 예제

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

#define FALSE 0
#define TRUE 1

typedef struct {
  char name[10];
  int age;
  float salary;
} humanBeing; //humanBeing 이라는 구조체 변수 type 생성

int humans_equal(humanBeing, humanBeing); //함수 선언, 함수 매개변수가 구조체 humanBeing 타입 - 넘겨줄 때 그냥 구조체 변수 명으로 넘겨주면 된다

void main() {

  humanBeing person1, person2;
  int rv;
 
  strcpy(person1.name, "James");
  person1.age = 10;
  person1.salary = 35000;

  strcpy(person2.name, "James");
  person2.age = 10;
  person2.salary = 35000;

  if(humans_equal(person1, person2))
    printf("The two human beings are the same.\n");
  else
    printf("The two human beings are NOT the same.\n");
}
  
int humans_equal(humanBeing person1, humanBeing person2) {
  /* returns TRUE if person1 and person2 are the same human being, 
     otherwise return FALSE */
  if(strcmp(person1.name, person2.name)) //같으면 0 , 다르면 1
  //만약 서로 달라서 1이나오면 FALSE인 상황
    return FALSE;
  if(person1.age != person2.age)
    return FALSE;
  if(person1.salary != person2.salary)
    return FALSE;
  return TRUE; //모두 다 같아서 IF(0)이 나오면 그것은 거짓이라 IF문 STATE의 RETURN들 다 무시되고 TRUE가 출력된다.
}
  • strcmp는 같으면 0, 같지 않으면 1
  • if(0)은 거짓 if(0이외의 정수)는 모두 참 (so if문 실행됨)

5) 구조체는 다른 구조체의 멤버로 사용 가능

(ex) 

typedef struct {
int month;
int day;
int year;
} date;

typedef struct {
char name[10];
int age;
float salary;
date dob;
} humanBeing;
  • 구조체=> 빌려온 다른 구조체 => 빌려온 다른 구조체의 멤버 로 접근 가능
person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

2. Unions

  • union은 하나의 memory 공간만 차지
  • so union 안의 하나의 요소만 사용 가능

(ex) playerType이라는 구조체 자료형 선언 (u라는 유니언 포함) & 이 구조체 자료형을 baseballPlayer이라는 구조체 자료형에서 멤버로 사용


typedef struct {
enum tagField {pitcher, hitter} role;
union {
int SO;
int HR;
} u;
} playerType;

typedef struct {
char name[10];
int age;
float salary;
date dob;
playerType playerInfo;
} baseballPlayer;

이때 baseballPlayer 구조체에서 playertype의 u라는 union의 멤버 지정해줄 때 SO 또는 HR 둘 중에 하나만 선택 가능! => 유니온은 오직 자신안에 있는 것중 하나만!!

baseballPlayer person1, person2;


person1.playerInfo.role = pitcher;
person1.playerInfo.u.SO = 163;
//person1.playerInfo.u.HR = 24; => 이렇게 동시에 지정하면 error!

person2.playerInfo.role = hitter;
person2.playerInfo.u.HR = 24;

3. Self Referential System

  • 자신의 다음 아이를 가리키는 구조
typedef struct {
char data;
list *link;
} list;
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;

4. Polynomials

4-1 DENSE MATRIX 의 경우 (차수 없는 경우도 공간 할당하는 배열)

//============================================================================//
// ex008: dense representation of polynomials using arrays                    //
//============================================================================//
#include <stdio.h>
#include <stdlib.h>

#define MAX_DEGREE 101

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

polynomial polynomial_add(polynomial, polynomial);
void polynomial_print(polynomial);

void main() {
  int i;
  polynomial p1;   // p1 = 3x^2 + 2x + 4
  polynomial p2;   // p2 = x^4 + 10x^3 + 3x^2 + 1
  polynomial p3;

  // initialize all coefficients to zero.
  p1.degree = -1;
  p2.degree = -1;
  for(i=0; i<MAX_DEGREE; i++) {
    p1.coef[i] = 0;
    p2.coef[i] = 0;
  }

  // assign coefficients of p1 and p2.
  p1.degree = 2; p1.coef[2] = 3; p1.coef[1] = 2; p1.coef[0] = 4;
  p2.degree = 4; p2.coef[4] = 1; p2.coef[3] = 10; p2.coef[2] = 3; p2.coef[0] = 1;
 
  polynomial_print(p1);
  polynomial_print(p2);

  p3 = polynomial_add(p1, p2);
  polynomial_print(p3);
}

polynomial polynomial_add(polynomial p1, polynomial p2) {

  /* complete this function */

}

void polynomial_print(polynomial p) {

  /* complete this function */

}

==> complete this function을 채워서 p1+p2를 하면 이를 더한 p3를 출력하도록 하기

(1)

  • 두 함수를 더할 때 더욱 큰 차수를 가지고 있는 아이가 누구인지 구별해야 한다
    => 삼항 연산자를 사용해서 두 다항식에서 가장 큰 차수 찾아내기 (for문 돌릴 때 사용 위해)
  • 이후 누가 더 큰 차수를 가지고 있는지 찾아내야 해서 largerDegree가 p1.degree와 같은지, p2.degree와 같은지 파악한 후 더 차수가 큰 애가 갱신된 더하기 값을 가지도록 하기
  • 더 큰 차수를 가지고 있던, 갱신된 식을 return 해주면 됨

polynomial polynomial_add(polynomial p1, polynomial p2) {

  int i, largerDegree;
  largerDegree=p1.degree>p2.degree?p1.degree:p2.degree;

  	if(largerDegree==p1.degree){
  		for(i=0;i<=largerDegree;i++){
			p1.coef[i]=p1.coef[i]+p2.coef[i];
		}
		return p1;
	}
	
  	if(largerDegree==p2.degree){
  	for(i=0;i<=largerDegree;i++){
  		p2.coef[i]=p1.coef[i]+p2.coef[i];
  	}
  	}
	return p2;
	
}

(2)

  • 계수가 0이라면 그냥 건너뛰기
  • 계수가 1이라면 x^차수 만 출력
  • 위의 두 경우 모두 아니라면 계수+x^차수 출력
  • for 문 돌릴 때는 최고 차수 기준으로 돌리기

void polynomial_print(polynomial p) {

  int i; 
  for(i=p.degree;i>=0;i--){
  	if(p.coef[i]!=0){
  		if(i==0){
  			printf("%d", p.coef[i]);
  			break;
		  }
		else if(p.coef[i]==1){
			printf("x^%d", i);
		}
		else{
			printf("%dx^%d", p.coef[i],i);
		}
	  }
	  printf("+");
  } 
printf("\n");
}

=> 출력 결과

4-2 SPARSE MATRIX ADDITION 경우

=> ADD 부분을 채워넣기

#include <stdio.h>
#include <stdlib.h>
#define MAX_TERMS 100
#define COMPARE(x, y) (x < y ? -1 : (x > y ? 1 : 0))

typedef struct {
  int coef;
  int expon;
} polynomial;

// shared memory for storing polynomials
polynomial terms[MAX_TERMS];
int avail = 0;

void polynomial_add(int, int, int, int, int*, int*);
void polynomial_print(int, int);
void attach(int, int);

void main() {

  // starta and finisha defines polynomial a
  int starta, finisha;
  int startb, finishb;
  int startc, finishc;

  starta = avail;
  terms[avail].expon = 1000; terms[avail].coef = 2; 
  //차수 & 계수를 각각 저장, avail은 다음 아이가 들어올 수 있는 장소 
  //따라서 한번 넣어지면 avail ++ 로 갱신시켜줘야 함 
  avail++;
  terms[avail].expon = 0; terms[avail].coef = 1;
  finisha = avail;
  avail++;

  startb = avail;
  terms[avail].expon = 4; terms[avail].coef = 1;
  avail++;
  terms[avail].expon = 3; terms[avail].coef = 10;
  avail++;
  terms[avail].expon = 2; terms[avail].coef = 3;
  avail++;
  terms[avail].expon = 0; terms[avail].coef = 1;
  finishb = avail;
  avail++;

  polynomial_add(starta, finisha, startb, finishb, &startc, &finishc);

  polynomial_print(starta, finisha);
  polynomial_print(startb, finishb);
  polynomial_print(startc, finishc);
}

void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd) {


}

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

void polynomial_print(int starta, int finisha) {
  int i;
  for(i = starta; i <= finisha; i++) {
    if(i == starta) printf("%dx^%d", terms[i].coef, terms[i].expon);
    else printf(" + %dx^%d", terms[i].coef, terms[i].expon);
  }
  printf("\n");
}

(1) TRIAL (1) => SWITCH 에서 ERROR

void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd) {

  /* complete this function */
  int i,j, largestart, smallstart, largeend, smallend;
  largestart=finisha-starta+1>finishb-startb+1?starta:startb;
  largeend=finisha-starta+1>finishb-startb+1?finisha:finishb;
  smallstart=finisha-starta+1<finishb-startb+1?starta:startb;
  smallend=finisha-starta+1<finishb-startb+1?finisha:finishb;
  
  for(i=largestart;i<=largeend;i++){
  	for(j=smallstart;j<=smallend;j++){
		switch(COMPARE(temps[i].expon, [j].expon)){
			case -1 : temps
				attatch(temps[j].expon, temps[j].coef);
				break;
			case 0 : 
				attatch(temps[i].expon, temps[i].coef+temps[j].coef);
				break;
			case 1 : 
			attatch(temps[i].expon, temps[i].coef);
				break;
			
		}
	  }
  }

}
  • 에러 이유 : terms => temps라고 썼고 attach 를 attatch라고 썼다

2) TRIAL 2

void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd) {

  /* complete this function */
  int i,j, largestart, smallstart, largeend, smallend;
  largestart=finisha-starta+1>finishb-startb+1?starta:startb;
  largeend=finisha-starta+1>finishb-startb+1?finisha:finishb;
  smallstart=finisha-starta+1<finishb-startb+1?starta:startb;
  smallend=finisha-starta+1<finishb-startb+1?finisha:finishb;
  
  *startd = avail;
  
  for(i=largestart;i<=largeend;i++){
  	for(j=smallstart;j<=smallend;j++){
  	 	switch(COMPARE(terms[i].expon, terms[j].expon)){
			case -1 : 
				attach(terms[j].coef, terms[j].expon);
				break;
			case 0 : 
				attach(terms[i].coef+terms[j].coef, terms[i].expon);
				break;
			case 1 : 
				attach(terms[i].coef, terms[i].expon);
				break;
		}
	  }
  }
}
  • 이를 고친 이후에도 나는 이중 for문을 돌려서 항상 어느때나 -1,0,1로 나눠지게 경우를 설정해놨는데 이렇게 해놓으면 이미 할당된 차수가 중복되어서 배정되는 문제가 생긴다
    => 결과창

  • 2x^1000이 계속 반복해서 자리를 차지하고 있다 -> 중복의 경우가 발생

모범답안

void polynomial_add(int starta, int finisha, int startb, int finishb, int *startd, int *finishd) {
  /* add a(x) and b(x) to obtain d(x) */
  int coefficient; //계수 더해서 저장해줄 정수의 변수 하나 저장
  *startd = avail; // startd의 장소는 현재 avial => startc는 finishb다음에 들어올 예정이므로
  while(starta <= finisha && startb <= finishb) //a와 b의 start가 end에 도달하기 전이라면
    switch(COMPARE(terms[starta].expon, terms[startb].expon)) {
    //서로 가장 큰 차수를 비교한다
    
      case -1: //경우 1 : 만약 a의 차수 < b의 차수라면 
        attach(terms[startb].coef, terms[startb].expon);
      //b의 차수가 c의 차수 정하는 중에 더 앞에 와야 하므로 b의 차수 붙여주고
        startb++
      //b의 차수는 사용 완료 되었으니깐 하나 더해서 b의 다음 차수를 startb로 설정
        break;
      case 0: //경우2 : a의 차수 == b의 차수 => 배열 c에 해당 계수 두개 더한걸 계수로 전해주고 차수는 둘 중에 아무거나~
        coefficient = terms[starta].coef + terms[startb].coef;
        if(coefficient) attach(coefficient, terms[starta].expon);
        starta++; startb++;
        break;
      case 1://경우3 : a의 차수 > b의 차수
        attach(terms[starta].coef, terms[starta].expon);
        //a의 차수가 c의 차수 정하는 중에 b보다 크니깐 더 앞에 와야 하므로 a의 차수 붙여주고
        starta++;
        //a의 차수는 사용 완료 되었으니깐 하나 더해서 a의 다음 차수를 starta로 설정
    }
    
    //a랑 b랑 비교 마무리 되고 조금더 짧았던 쪽은 홀로 남음..
    //이 홀로 남은 애는 순서대로 attach 해주면 마무으리 된다!
  /* 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;
}

스스로 꼭 padd 복습해서 종이 암기 & 코드 짜보기

Node.js와 JavaScript 공부(#9일차)
SQL StudyLog1

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage