극복해내자 나의 슬럼프!!
21/07/19
List Polynomials
Additions
- 항을 저장하기 위한 메모리 공간을 할당하고 그것의 시작주소를 가리키게하는 rear, c도 같은 곳을 가리키게 한다.
- a의 지수와 b의 지수를 비교하고, a=b면 a+b(계수 값을 더한다), 지수 값을 그대로 작성.
- 저장하기 위한 새로운 노드 만들기 -> rear의 링크는 새롭게 만든 항을 가리키게 바꾸기
( rear는 새롭게 만들어진 노드를 가리키기 때문에 다항식의 맨 마지막을 가리킨다.)
- 그 다음 항으로 옮겨감. 지수값을 비교했는데 a< b 이면, b 계수의 항은 새로운 노드로 생성해야하기 때문에 b가 가지고 있는 항을 그대로 copy하여 이어 붙인다. rear의 링크는 새롭게 만든 항과 연결하고, rear는 마지막 항을 가리킴.
- a와 b를 또 비교하고, a의 계수값이 더 크면 새로운 항이 들어갈 공간을 만들고, rear의 링크와 연결하여 다음 노드를 가리키게 하고, rear는 가장 마지막 항으로 이동한다.
- 4,5번 반복하여 다항식 끝까지 만들기
- c라는 변수를 정의한 이유? a,b를 합한 다항식의 시작부분을 가리키는 변수로 이용하기 위해. 하지만 현재 엉뚱한 곳을 가리키고 있음.
- c를 c의 링크로 옮기게 하고 그 c를 리턴하기. rear를 가장 끝값을 가리키게 한다.
List polynomials 관련 operations
Erasing Polynomials
다항식 a와 b를 덧셈하고 c를 만들었기 때문에 더 이상 a,b는 필요하지 않기에 이 둘을 시스템에 반납하기 위한 코드
- 포인터가 null이 아닌 동안, temp ptr를 가리키게 하고, 그 다음 것을 또 가리키게 한 다음 free를 시킴.
\중요\
*ptr = (*ptr)->link;를 하는 이유?
앞의 항 부분을 free 시키고 나면 링크의 주소값이 사라지기 때문에 그것을 저장해두는 것임.
Memory Reuse
avail 이라는 것을 선언
avail : 이제는 더이상 사용하지 않는 모든 다항식들을 묶어놓은(모아둔) 리스트들의 첫번째 노드를 가리키는 변수
예시로, A,B,C라는 다항식이 있고 avail은 전역변수.
A와 B를 더이상 쓰고 싶지 않은 다항식이라면 A가 B의 시작 노드를 avail이 A의 시작 노드를 가리키게 하는 것임. 두개의 리스트가 쫙 묶이게 되고 새로운 다항식을 만들 때, 다항식을 사용할 때 잘 가공 되어있기 때문에 다 지우고, 새로운 다항식들의 노드들로 활용.
맨 앞에 있는 avail이 가리키고 있는 노드에 다시 새로운 다항식을 넣어 사용하면 데이터를 사용하기 용이함.
이러한 함수 getNode 콜하면
if(avail) {
node = avail;
avail = avail->link;
}
else MALLOC(node, sizeof(*node));
return node
1) 재활용 할 수 있는 공간이 존재한다면 콜하여 재사용하기
2) 없다면 새로운 공간 할당하기
avail은 대기 상태에 있는 노드들이 묶여있는 리스트의 첫번째 주소값만 가지고 있음.
만약, 더이상 필요가 없어져서 대기상태에 있는 리스트에 새로운 항을 추가하려 할 때? 맨 뒤가 아닌 (맨 뒤면 리스트를 스캔해서 뒤로 보내야하는 수고가 필요함) avail이 가리키고 있는 위치에 저장함.
circular representation
마지막 노드가 맨 앞을 가리키는 링크필드
장점: 어떤 노드에서 시작하든 맨 시작 노드로 돌아올 수 있음.
특징 : zero polymonial
첫번째 시작 노드라는 걸 표현하기 위해서 비워둠
계수 값이 -1로 설정되어있음
Erasing a Circular List
void crease(polyPointer* ptr)
{
polyPointer temp;
if (*ptr) {
temp = (*ptr)->link;
(*ptr)->link = avail;
avail = temp;
*ptr = NULL;
}
}
