[자료구조 - C언어] 자료구조 제12강: 연결 리스트 - 다항식(1)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

0. Use Case

• $ 프롬프트로 입력
• 공백 입력 가능 ~ 무시
• 계수는 정수, 지수는 양수
• calc f 1 = f(1)을 의미 ~ 다음 줄에 결괏값 출력
• g= f + g ~ 두 개의 다항식을 정해, 새로운 다항식을 만들 수 있다
• 기존에 존재하던 다항식을 덮어쓸 수 있다
• 입력 - 차수에 대한 내림차순 X, 동일 차수의 항이 여럿
• 출력 - 차수에 대한 내림차순 O,
• 동일 이름의 함수를 새로 정의 O
• 연결리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynomial을 정의
  • 각각의 항을 연결 리스트로 연결 & 차수에 대한 내림차순
  • 동일 차수의 항을 2개 이상 X, 계수가 0인 항 존재 X
  • 하나의 항은 계수와 지수로 정의, 하나의 항은 구조체 Term으로 정의
  • 변수 x의 값이 주어질 때 값 계산하는 함수 제공

 

1. 자료구조

struct term{
    int coef;           //계수
    int expo;           //차수
    struct term *next;  //다음 노드
};
typedef struct term Term;

typedef struct polynomial{
    char name;       //다항식의 이름
    Term *first;     //다항식을 구성하는 첫 번째 항의 주소
    int size;        //항의 개수
} Polynomial;

Polynomial *polys[MAX_POLYS];    //다항식들에 대한 포인터의 배열
int n = 0;                       //저장된 다항식의 개수

 

2. create instance

• 객체를 생성하고 기본값으로 초기화해주는 함수를 따로 만들어 사용하면 초기화 오류를 예방할 수 있다.

Term *create_term_instance(){
    Term *t = (Term *)malloc(sizeof(Term));
    t -> coef = 0;
    t -> expo = 0;
    t -> next = NULL;

    return t;    //생성된 주소를 리턴
}

Polynomial *create_polynomial_instance(char name){
    Polynomial *ptr_poly = (Polynomial *)malloc(sizeof(Polynomial));
    ptr_poly -> name = name;
    ptr_poly -> size = 0;
    ptr_poly -> first = NULL;
    return ptr_poly;
}

 

3. add_term(int c, int e, Polynomial *poly)

• poly가 가리키는 다항식에 새로운 하나의 항 (c, e)를 추가하는 함수
  

  

  • (0) 추가하려는 위치를 투 포인터를 이용해서 찾기
    • 삽입하려는 위치의 앞 노드 주소를 알아야 뒤에 삽입할 수 있으므로 투 포인터 사용
  • (1) 추가하려는 항과 동일 차수의 항이 이미 있는 경우 - 기존 항의 계수만 변경
    • 동일한 e값을 가진 노드가 이미 있는 경우
      • c값을 계산한 후 c값이 0인지 아닌지 확인 필요
        • c값이 0일 때 제일 첫 항에 위치한 경우 노드 삭제
        • c값이 0일 때 중간에 위치한 경우 노드 삭제
  • (2) 그렇지 않은 경우: 새로운 항을 삽입(내림차순 중간에 삽입)
    • 새로운 노드를 생성, 값 입력
      • q뒤에 삽입
        • 제일 첫 번째 위치에 삽입해야 하는 경우(q==NULL)
        • 중간에 삽입하는 경우

void add_term(int c, int e, Polynomial *poly){
    //계수가 0이라면 실제로 존재하지 않음
    if(c==0)
        return;

    //투포인터 생성
    Term *p = poly -> first;
    Term *q = NULL;
        //(0) 삽입할 위치 찾기
    while(p!=NULL && p->expo > e){
        q = p;
        p = p->next;
    }

    //(1) 동일 차수의 항이 존재하는 경우
    if(p != NULL && p->expo == NULL){
        p->coef += c;
        //원래는 계수가 0이 아니었는데, 계산 후 0이 된 경우
        //그 노드를 제거해야 한다
        //제거시 이전 노드의 주소가 필요
        //즉, q의 다음 노드를 제거
        if(p->coef == 0){
            //q가 NULL이면 첫 번째 노드 삭제
            if(q==NULL){
                poly->first = p->next;
            }else{
                q->next = p->next;
            }
            poly->size--;
            free(p);  //불필요해진 노드 p는 free
        }
        return;
        }

    //(2) 동일 차수의 항이 존재하지 않는 경우
    // - 새로운 노드를 만들어 다항식에 노드를 추가
    Term *term = create_term_instance();
    term->coef = c;
    term->expo = e;

    //q 바로 뒤에 삽입
    if(q==NULL){  //맨 앞에 삽입하는 경우
        term->next = poly->first;
        poly->first = term;
    }
    else{         //그렇지 않은 경우
        term->next = p;
        q->next = term;
    }
    poly->size++;
}

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=UviSUv21iB8&feature=emb_imp_woyt