[ 자료구조 및 알고리즘 ] 5.연결 자료구조 -5. 다항식의 연결 자료 구조 표현

다항식의 연결 자료구조 표현

 단순 연결 리스트를 이용하여 다항식 표현

• 다항식의항:단순연결리스트의노드 

 

 노드구조

• 각항에대해서계수와지수를저장
• 계수를 저장하는 coef와 지수를 저장하는 expo의 두 개의 필드로 구성
• 링크필드:다음항을연결하는포인터로구성

• 노드에 대한 구조체 정의

typedef struct Node {
	float coef;
	int expo;
	struct Node *link;
};

 

다항식의 단순 연결 리스트 표현 예 

 

다항식 연결 자료구조의 삽입 연산

다항식에 항을 추가하는 알고리즘

• 다항식 리스트 포인터 PL과 coef 필드 값을 저장한 변수 coef, expo 필드 값을 저장한 변수 expo, 리스트 PL의 마지막 노드의 위치를 지시하는 포인터 last를 매개변수로 사용

❶<< 공백 다항식에서의 항 삽입 연산 > > 

• 초기상태

1. PL ← new;

• 포인터 new의 값을 리스트 포인터 PL에 저장하여, 노드 new가 리스트 PL의 첫 번째 노드가 되도록 연결

2. last ← new;

• 포인터 new의 값을 포인터 last에 저장하여, 포인터 last가 리스트 PL의 마지막 노드인 노드 new를 가리키도록 지정

❷<< 다항식에서의 항 삽입 연산 >> 

• 초기상태

1. last.link ← new;

• 포인터 new의 값을 노드 last의 링크에 저장하여, 노드 new를 노드 last의 다음 노드로 연결

2. last ← new;

• 포인터 new의 값을 포인터 last에 저장하여, 노드 new를 리스트 PL의 마지막 노드로 지정

 

 

 다항식 리스트 A에 appendTerm() 알고리즘을 사용하여 2x0항(상수항 2) 추가 예

 

다항식의 덧셈 연산

덧셈 A(x)+B(x)=C(x)를 단순 연결 리스트 자료구조를 사용하여 연산

• 다항식 A(x)와 B(x), C(x)의 항을 지시하기 위해서 세 개의 포인터를 사용 

• 포인터 p : 다항식 A(x)에서 비교할 항을 지시
• 포인터 q : 다항식 B(x)에서 비교할 항을 지시
• 포인터 r : 덧셈연산 결과 만들어지는 다항식 C(x)의 항을 지시

 

p.expo < q.expo : 다항식 B(x) 항의 지수가 큰 경우

• 포인터 q가 가리키는 다항식 B(x)의 항을 C(x)의 항으로 복사

• q가 가리키는 항에 대한 처리가 끝났으므로 q를 다음 노드로 이동

 

p.expo = q.expo : 두 항의 지수가 같은 경우

• p.coef와 q.coef를 더하여 C(x)의 항, 즉 r.coef에 저장하고 지수가 같으므로 p.expo(또는 q.expo)를 r.expo에 저장
• 다음 항을 비교하기 위해 포인터 p와 q를 각각 다음 노드로 이동

 

p.expo>q.expo:다항식A(x)항의지수가큰경우

• 포인터p가가리키는다항식A(x)의항을C(x)의항으로복사

• p가가리키는항에대한처리가끝났으므로p를다음노드로이동

 

 다항식의 덧셈 알고리즘

 

다항식의덧셈 예)

1.  4x^3항과 3x^4항에 대한 처리

• p.expo < q.expo이므로 지수가 큰 q 노드를 리스트 C에 복사

• 포인터q는다음노드로이동

2.  4x3항과 1x^3 항에 대한 처리

• p.expo = q.expo 이므로 두 노드의 coef 필드의 값을 더하고, expo 필드의 값을 복사한 노드(5x^3항)를 리스트 C에 추가

• 포인터p와q는다음노드로이동

3.  3x^2항과 2x^1 항에 대한 처리

• p.expo>q.expo이므로지수가큰p노드를리스트C에복사 

• 포인터p는다음노드로이동

4.  5x^1항과 2x^1 항에 대한 처리

• p.expo = q.expo 이므로 두 노드의 coef 필드의 값을 더하고, expo 필드의 값을 복사한 노드(7x^1항)를 리스트 C에 추가

• 포인터p와q는다음노드로이동

5.  B(x)의 남은 항에 대한 처리

• 포인터p가null이므로다항식A(x)의항에대한처리끝

• 처리할항이남아있는다항식B(x)의포인터q는null이될때까지모든노드를 복사하여 리스트 C에 추가

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

typedef struct ListNode{ //다항식 리스트의 노드 구조 정의 
	float coef;
	int expo;
	struct ListNode* link;
} ListNode;
typedef struct ListHead{ //다항식 리스트의 헤더 노드 구조 정의 
	ListNode* head;
} ListHead;
ListHead* createLinkedList(void) //공백 다항식 리스트 생성 연산 
{
	ListHead* L;
	L = (ListHead *)malloc(sizeof(ListHead)); 
    L->head = NULL;
	return L;
}