データ構造003|Arrays and Structures+Polynomials(2)

66785 ワード
データ構造 テキストリンク

1.構造体


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{~}変数名を使用して変数を作成するのは、複数の構造体変数を作成する際に面倒です
=>いっそ構造体の新しい変数type=>typedef struct{~}type nameを指定
=>type name変数名で新しい構造体変数を作成できます!
(ex)
  • データ型
    • の作成
    typedef struct {
char name[10];
int age;
float salary;
} humanBeing;
  • 変数宣言
    • humanBeing person1, person2;

    4)typedef構造例

    #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(ゼロ以外の整数)である場合、いずれも真(soif文が実行された)
    • である.

    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メモリ容量は1つのみ
  • sounionでは、
    • を使用できる要素は1つしかありません.
    (ex)PlayerTypeという構造体データ型宣言(uというunionを含む)&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から1つしか選択できません!=>ユニオンは自分だけのものだ!!
    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関数、そしてp 1+p 2を加算してp 3を出力

    (1)

  • の2つの関数を加えると、誰がより大きな次元を持つ子供なのかを区別します.
    =>3つの演算子を使用して2つの多項式の中で最大の回数(ドアを回すため)を検索する
  • 以降は誰がもっと大きな車を持っているのかを見つけなければならないので、大きなDegreeはp 1です.degreeと同じですか、p 2.degreeに等しいかどうかを決定した後、より大きな数字に更新されたプラス番号
    • を持たせる.
  • より大きな車数の更新式を持って戻ると
    • になります.
    
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はattach

    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に設定しています.そうすると、すでに割り当てられた車数が重複し、割り当ての問題が発生します.
    =>結果ウィンドウ
  • 2 x^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を復習して紙を暗記&コードを書く

    tf.one_hot符号化の使い方及びone-hot自己符号化
    (matlab)あるシーケンスをHuffman符号化する