'자료구조'에 해당되는 글 2건

  1. 2009.03.29 [LinkedList] reverse
  2. 2009.03.22 다항식 곱셈
중대 컴공2009.03.29 00:15

LinkedList에 저장되어있는 값들을 역순으로 정렬하는 것이다.

처음에 생각한 것으로는 처음부터 끝까지 한번 돌면서 Stack에 하나씩 주소를 push 해주는 것이다.

그리고 하나씩 pop하면서 다시 LinkedList를 연결한다. 그러면 마지막 주소부터 하나씩 새로 Link해주는 것이다.


위와 같은 순서로 진행된다.

하지만....

교수님의 얘기는 처음부터 끝까지 한번 움직이면 역순으로 정렬이 되어야 한다고 한다.....;

포인터 3개로 하면 가능하다고 한다.

다음이 내가 고민끝에 생각해낸 결과이다.


분명 빨간색 펜이었는데.... 검정색으로 스캔이 되어버렸다는;;;
신고
Posted by 초프(초보 프로그래머)
중대 컴공2009.03.22 17:07



학번 두개를 가지고 다항식을 하나만든다. 이렇게 만든 두개의 다항식으로 곱셈을 한다.

과제가 다항식의 곱셈이었지만 어느새 다른부분이 더욱 집중이 되어버린;;

그 다른부분중 하나가 addTerm(zeroP(),3,2) 이런 부분이다.

zeroP() : 빈 다항식 배열을 만들어서 주소를 리턴
addTerm() : 다항식 배열에 계수와 차수를 저장한다.

다항식을 만들때 이렇게 함수를 사용하여 만들었음
출력은 다항식이 만들어지는 과정과 곱한 결과가 나오게 하였음.


학번 두개로 다항식을 만든 규칙은 첫번째 학번을 정렬을 하여 20075278 을 87752200 으로 만든다.
그리고 두번째 학번에서 0을 제외한 숫자들을 계수로 한다. 20075277을 275277을 계수로 한다.
그래서 다항식 2X^8 + 7X^7 + 5X^7 + 2X^5 + 7X^2 + 7X^2 을 만든다.
차수가 같은것은 더해주므로 2X^8 + 12X^7 + 2X^5 + 14X^2 이 된다. 이렇게 두개를 만드는 것이다.

 // 빈 다항식
 poly = zeroP();

 // 계수와 차수를 이용해서 다항식을 만든다.
 for(i=0; i<MAX_SIZE; i++)
 {
     if(!rank[i]) break;
     poly = addTerm(poly,rank[i],degree[i]);
 }


이 부분이 다항식을 만들어 주는 과정이다. 위에 규칙으로 만들어진 차수와 계수는 degree, rank배열에 저장된다.
두 배열을 가지고 다항식을 만들어주는 것이다.

정렬은 총 3번이 들어갔다. 당항식을 만들때 각각 한번씨 쓰고 마지막으로 곱셈결과를 정렬할때 한번 쓰인다.
정렬 알고리즘은 알고리즘 시간에 배웠던 삽입정렬을 사용하였음.

곱셈 알고리즘은 일반 손으로 계산할때 하는 방식으로 하였습니다;; 비효율적일수도 있지만;

신고
Posted by 초프(초보 프로그래머)