[서평] 자료구조

소개

자료구조
이언배, 박영배, 임해철 저. 한국방송통신대학교출판부 2011년 7월 25일 초판
서평입니다

목차

1. 자료구조

2. 이해
2.1. 배열과 레코드
2.2. 스택과 큐
2.3. 연결리스트
2.4. 트리
2.5. 그래프

본문내용

1. 자료구조
추상자료형, 알고리즘 등이 책의 많은 비중을 차지하고 있다. 개인적으로 이해한 바를 정리해 보는 기회로 삼는다. 초심자라 이해하지 못한 부분이 많았음을 미리 고백한다.

2. 이해
2.1. 배열과 레코드
<1>
48쪽 희소행렬의 전치 알고리즘 설명이다.
(1) 열의 값을 순서대로 나래비 세운다. 02103을 00123으로.
(2) 기존 열을 바꾸어야 할 전치행렬의 행으로 옮긴다. 00123으로 써준다.
(3) 열에 붙어있는 행과 값은 그대로 이동한다.
알고리즘 상 for문이 두 개라서 복잡도가 n제곱이 된다. 51쪽 for (i=0;i<n;i++), for (j=1;j<=t; j++)

<2>
40쪽 두 다항식의 덧셈 연산 알고리즘 설명이다. P1과 P2를 더해 P3을 만든다.
(1) 6행은 p2의 최고차항이 P1보다 큰 경우다. 이 경우 P2의 계수(coef(p2,maxExp(p2))와 지수(maxExp(p2)를 P3항으로 옮긴다. 옮겨진 P2의 계수화 지수는 삭제된다.
(2) 9항은 p1과 p2항의 최고차항이 같은 경우다. 이 경우 p1과 p2의 계수를 더해서 p3에 넣는다. 옮겨진 p1과 p2의 항은 삭제된다.
(3) 14항은 p1의 최고차항이 p2의 최고차항보다 큰 경우로 p1의 계수와 지수를 p3에 넣고
p1에서 그 항을 삭제한다.
(4) 최고차항끼리의 비교, 삭제를 반복하고 남은 항은 19항에 따라 p3의 항에 복사된다.
예를 들어 보면 이해가 용이하겠다.
p1은 2x^8 - 7x^5 + 3x^2 -2
p2는 x^5 + 10x^3 - 2x^2
p3는 2x^8 - 6x^5 + 10x^3 + 3x^2 -2

<3>
53쪽 알고리즘, 두번째 희소행렬의 전치 알고리즘의 설명이다. 그림 2.19의 표를 먼저 만든다.
(1) 기존 행렬의 열을 기준으로 갯수를 센다. 0은 2개, 1은 하나, 2도 하나, 3도 하나다.
0 1 2 3
2개 1개 1개 1개

참고자료

· 없음