[데이터 구조] 12차시 헤더 노드와 다항식의 리스트 표현 | 덧셈

1. 헤더 노드

1) 기존 연결 리스트 처리 알고리즘

- 문제점: 첫 번째 노드나 마지막 노드, 그리고 리스트가 공백인 경우에 따라 처리 방법이 각기 달라, 서로 예외적인 경우로 처리해야 함

 

2) 헤더 노드(header node)를 추가하는 방법

- 상기 문제가 되는 예외 경우를 가급적 제거하고, 코드를 간단하게 하기 위한 해결책으로 사용 가능

- 헤더 노드에는 리스트를 처리하는데 1️⃣필요한 포인터나 2️⃣통계 정보를 미리 저장

• 리스트의 첫 번째 노드를 가리키는 포인터
• 리스트의 길이
• 마지막 노드를 가리키는 포인터 등의 필요 정보

⭐헤더 노드의 구조가 리스트의 노드 구조와 달라도 문제 없음

원래의 경우의 수

 

3) 헤더 노드를 가진 연결 리스트의 정의

typedef struct listNode { /*리스트 노드 구조*/
    char data[5];
    struct listNode* link; /*양 방향이면 rlink, llink*/
} listNode;

typedef struct h_linkedList {	/*리스트 헤더 노드 구조*/
	int length;		/*리스트의 길이(노드 수)*/
    listNode* head;	/*첫 번째 노드에 대한 포인터*/
    listNode* tail;	/*마지막 노드에 대한 포인터*/
} h_linkedList;

 

 

 

4) 헤더 노드를 가진 연결 리스트 표현

 

 

 

5) 공백 리스트에서의 헤더 노드

- length가 0이고, head가 null, tail이 null인 헤더 노드로 표현

 

 

 

6) 모조 노드 사용(꼭 필요한 것은 아님)

- 리스트 처리의 단순화를 위해 모조 노드(보조 추가 노드, dummy node라고도 부름)의 형태를 사용하기도 함

 

1️⃣ 단순 연결 원형 리스트의 공백 리스트 구조

 

 

2️⃣ 모조 노드를 사용해 표현한 이중 연결 원형 리스트의 공백 리스트 구조

 

 

 

 

2. 다항식의 리스트 표현과 덧셈

1) 다항식(Polynomials)

- 다항식은 일반적으로 0이 아닌 항들의 합으로 표현함. -> 단순 연결 리스트로 표현해보자!

다항식의 일반적인 형태

 

- 각 항(Polynomial term)은 하나의 노드로 표현

 

 

 

 

 

 

- 다항식을 단순 연결 리스트(singly linked list)로 표현한 예시

 

 

 

2) 다항식의 덧셈

 

[if a->expon == b -> expon, 지수가 같을 때]

1️⃣ 다항식 a와 b 두 항의 계수를 더한 값을 d에 다음과 같이 만들어 간다.
- a와 b 두 항의 계수를 더한 값을 계수(coefficient)로 가지고
- a->expon(지수) (또는 b->expon)을 지수(exponent)를 갖는
- node를 생성하여 polynomial d의 끝(rear)에 추가해 나간다.

 

2️⃣ polynomial 변수 a와 b가 현재 가리키고 있는 다음 term들을 가리키게 한다.

 

 

 

[if a->expon < b -> expon]

 

3️⃣ polynomial 변수 b가 가리키고 있는 term을 polynomial d의 끝에 추가한다.

4️⃣ polynomial 변수 b가 현재 가리키고 있는 다음 term들을 가리키게 한다.

 

 

 

[if a->expon > b -> expon]

 

5️⃣ polynomial 변수 a가 가리키고 있는 term을 polynomial d의 끝에 추가한다.

6️⃣ polynomial 변수 a가 현재 가리키고 있는 다음 term들을 가리키게 한다.

 

 

[if a->expon < b -> expon]

위 과정과 같음

 

 

[if b == NULL]

 

 

 

 

3) 다항식 추가 예제

 

- 두 다항식의 덧셈 연산, C(x) <- A(x) + B(x), 결과는 C에 완성

• 순회 포인터 변수 p와 q를 사용
  : 다항식 A와 B의 항들을 따라 순회하는 데 사용
  
  
• p와 q가 가리키는 항들의 지수(exp) 관계에 따라 3가지 경우
  1️⃣ p.exp = q.exp : 지수가 같은 경우
  ▶️ 두 계수를 더해서 0이 아니면, 새로운 항을 만들어 결과 다항식 C에 추가한다.
  ▶️ p와 q는 모두 다음 항으로 이동한다.
  
  2️⃣ p.exp < q.exp : q의 지수가 큰 경우, q만 결과 C로 나가고, q 중가
  ▶️ q가 지시하는 항을 새로운 항으로 복사하여 결과 다항식 C에 추가한다.
  ▶️ q만 다음 항으로 이동한다.
  
  3️⃣ p.exp > q.exp : p의 지수가 큰 경우
  ▶️ p가 지시하는 항을 새로운 항으로 복사하여 결과 다항식 C에 추가한다.
  ▶️ p만 다음 항으로 이동한다.

 

 

 

 

 

4) 다항식에 새로운 항을 첨가(추가)하는 알고리즘

 

 

 

5) 연결 리스트로 표현된 다항식의 덧셈

 

 

6) 다항식의 덧셈(padd) 함수의 분석

 

• Exponent 비교 ▶️ 지수(exponent)의 비교 회수: O(m+n)
  - min{m, n} <= 비교 횟수 <= m+n-1
  - (m=n)인 경우, 비교 횟수가 (m+n-1)이 된다.
  - 그러므로 최대 O(m+n), 그러므로 O(2n)
  
  
• Coefficient 덧셈 ▶️ 계수(coefficient)의 덧셈: O(min{m, n})
  - 0 <= 덧셈 횟수 <= min{m, n}
  - 지수가 같은 항이 없으면 덧셈은 없음, 덧셈은 항이 작은 쪽 기준으로 결정됨
  - 그러므로 최대 O(min{m, n}), 그러므로 O(n)
  
  
• Polynomial d에 포함될 새로운 node 생성 ▶️ 생성 회수: O(m+n)
  - max{m, n} <= 생성 횟수 <= m+n
  - 한쪽이 길면 긴 쪽 만큼 d가 길어짐, 최대인 경우는 지수가 같은 항이 없는 경우
  - 그러므로 최대 O(m+n), 그러므로 O(2n)
  
  
• 최종: worst case time complexity O(m+n), 그러므로 최종 O(n)
  - O(m+n) + O(min{m,n}) + O(m+n) = O(2n) + O(n) + O(2n) = O(n), 그러므로 O(n)