3. 배열.

Presentation on theme: "3. 배열."— Presentation transcript:

1 3. 배열

2 개요 배열 (array) 첨자 연산자를 이용해 접근할 수 있는 일련의 인접한 원소들 프로토타입 자료 구조
가장 단순한 종류의 원소 컨테이너

3 3.1 Java의 배열 배열은 객체임 배열의 타입은 t[] 형태 유효한 배열 선언문 t는 배열의 원소 타입
예: 원소 타입이 int이면 배열 타입은 int[ ] 유효한 배열 선언문 int[ ] a;                // 원소는 프리미티브 타입 int임 String[ ] args;          // 원소는 객체 타입 String임 List[ ] lists;            // 원소는 인터페이스 타입 List임 double[ ][ ] matrix;     // 원소는 배열 타입 double[ ]임 int[ ][ ][ ] x3d;          // 원소는 배열 타입 int[ ][ ]임

4 프리미티브 타입의 배열을 new 연산자로 할당하면 그 원소들은 자동적으로 그 타입의 0의 값으로 초기화됨
a = new int[8];   // 8개의 int 원소로 된 배열을 할당 d = new Date();   // Date 객체를 할당 프리미티브 타입의 배열을 new 연산자로 할당하면 그 원소들은 자동적으로 그 타입의 0의 값으로 초기화됨 배열은 항상 0을 기반으로 인덱스가 부여됨 배열의 길이가 n일 때 인덱스의 범위는 0에서 n-1이 됨

5 배열의 길이는 length 필드를 이용해서 접근
int n = a.length;    // 배열 a의 원소의 수 Java는 자동으로 배열의 인덱스를 검사해 배열이 주어진 범위에서 벗어나지 않도록 함 인덱스 범위를 벗어나면 ArrayIndexOutOfBoundsException 예외를 발생시킴 초기화 리스트를 이용해 배열을 초기화할 수 있음 int a = {44, 77, 22, 33, 66};

6 배열과 관련된 기초적인 사항들 다른 객체와 마찬가지로 배열도 그에 대해 여러 개의 참조를 가질 수 있다.
int[] aa = a; 다른 곳에서와 마찬가지 방식으로 메소드의 매개변수 리스트에 배열 매개변수를 선언할 수 있다. public void print(int[] a) 배열은 이름만 이용해서 메소드로 전달된다. print(a); 배열 타입은 메소드에 대한 리턴 타입이 될 수 있다. public int[] randomArray(int n) 한 배열을 다른 배열에 할당해도 실제로 복사되는 것은 아니다. 단지 다른 이름(즉, 다른 참조)만 부여하게 된다. b = a;  // a[]와 b[]는 동일 배열이 됨

7 배열을 복사하려면 System 클래스에 정의된 arraycopy() 메소드를 이용할 수 있다.
System.arraycopy(a, 0, b, 0, a.length); 중복 배열을 생성하려면 Object 클래스에 정의된 clone() 메소드를 이용할 수 있다. b = (int[])a.clone(); clone()에 대한 리턴 타입은 Object이므로 타입을 배열로 변환시켜야 한다. 배열은 대개 for 루프를 이용해서 처리된다. java.util.Random random= new java.util.Random() for (int i = 0; i < a.length; i++) a[i] = random.nextInt(1000); 배열이 final로 선언되면 그 참조는 재할당될 수 없다. final int[] a = {22, 44, 66, 88}; a[3] = 99;     // OK a = new int[8];    // 불법임

8 배열의 테스팅 LISTING 3.1: Testing Arrays 1 public class Main {
2 private static java.util.Random random = new java.util.Random(); 4 public static void main(String[] args) { 5 int[] a = randomInts(10,1000); 6 int[] aa = (int[])a.clone(); // creates a duplicate of a in aa 7 print(a); 8 print(aa); 9 a[0] = a[1] = a[2] = 888; 10 print(a); 11 print(aa); } public static int[] randomInts(int n, int range) { 15 int[] a = new int[n]; 16 for (int i = 0; i < n; i++) a[i] = random.nextInt(range); 18 return a; } public static void print(int[] a) { 22 System.out.print("{" + a[0]); 23 for (int i = 1; i < a.length; i++) 24 System.out.print("," + a[i]); 25 System.out.println("}"); } 27 }

9 출력 결과    {102,955,717,249,649,596,131,414,849,759}    {888,888,888,249,649,596,131,414,849,759}

10 3.2 Java에서 배열의 프린팅 배열은 객체 배열의 이름은 실제로는 배열에 대한 참조 변수의 이름임 배열의 원소 프린팅
이 변수는 메모리에서 배열의 시작 주소를 저장함 이 변수를 프린트하면 메모리 주소를 16진수로 보여주게 됨 출력 문자열: [I : 타입 int[]의 배열임을 의미 @73d6a5 : 배열이 저장된 메모리의 주소 배열의 원소 프린팅 반복문을 이용해 한번에 한 원소씩 프린트

11 배열 참조의 프린팅 LISTING 3.2: Printing an Array Reference
1 public class Print { 2 public static void main(String[] args) { 3 int[] a = {66, 33, 99, 88, 44, 55, 22}; 4 System.out.println(a); 5 } 6 } 출력 결과   

12 3.3 간단한 배열 알고리즘 최대값 원소의 발견 주어진 시이퀀스(배열)에서 최대 원소를 찾는 일 알고리즘 3.1
입력: 비교가능한 원소들의 시이퀀스 . 출력: 인덱스 값 m. 후조건: 모든 i에 대해, am≥ai.    1. m=0으로 놓음.    2. 단계 3을 i = 1부터 n-1까지 반복.    3. 만약 ai>am이면, m = i로 설정.    4. m을 리턴.

13 자리교환(스왑) 두 원소의 위치를 서로 바꾸는 것 알고리즘 int 배열에 대한 swap 메소드
입력: 비교가능한 원소들의 시이퀀스 와 인덱스 값 i와 j. 후조건: 원소 ai와 aj가 교환됨    1. x = ai로 놓음.    2. ai = aj로 설정.    3. aj= x로 설정. int 배열에 대한 swap 메소드 LISTING 3.3: The swap() Method 1 void swap(int[] a, int i, int j) { 2 int x = a[i]; 3 a[i] = a[j]; 4 a[j] = x; 5 }

14 3.4 객체의 배열 배열의 원소 프리미티브 타입 참조 타입 모든 원소는 동일한 타입
해당 배열에 대해 선언된 원소 타입의 확장(클래스)에 속하는 다른 타입이 될 수도 있음 -> 이질 배열(heterogeneous array)이 가능 이질 배열의 예: 리스팅 3.4

15 객체의 이질 배열 LISTING 3.4: A Heterogeneous Array of Objects
1 public class ObjectArray { 2 public static void main(String[] args) { 3 String s="Mercury"; 4 Float x = new Float( ); 5 java.util.Date d = new java.util.Date(); 6 int[] a = new int[] {11, 33, 55, 77, 99}; 7 Object[] objects = {s, x, d, a}; 8 print(objects); 9 } 10

16 11 static void print(Object[] a) {
12 System.out.print("{" + a[0]); 13 for (int i=1; i<a.length; i++) System.out.print("," + a[i]); 15 System.out.println("}"); 16 if (a[0] instanceof String) System.out.println(((String)a[0]).charAt(6)); 18 if (a[1] instanceof Float) 19 System.out.println(((Float)a[1]).isNaN()); 20 if (a[2] instanceof java.util.Date) System.out.println(((java.util.Date)a[2]).getTime()); 22 if (a[3] instanceof int[]) 23 System.out.println(((int[])a[3]).length); 24 } 25 }

17 출력 결과      {Mercury, ,Sat May 12 12:41:43 EDT      y      false           5

18 3.5 순차 탐색 순차 탐색 (선형 탐색 또는 직렬 탐색) 알고리즘 구현: 리스팅 3.5 시간 복잡도: Θ(n)
주어진 목표 값을 찾아 리스트를 앞에서부터 순차적으로 탐색 목표가 발견된 첫 번째 위치를 리턴; 목표가 발견되지 않으면 음수를 리턴 알고리즘 입력: 시이퀀스 와 목표 값 x 출력: 인덱스 값 i 후조건: ai = x 또는 모든 aj≠x일 때 i = -n    1. 0에서 n-1의 각 i에 대해, 단계 2를 수행.    2. ai = x이면, i를 리턴.    3. -n을 리턴. 구현: 리스팅 3.5 시간 복잡도: Θ(n)

19 순차 탐색 LISTING 3.5: The Sequential Search
1 public class TestSequentialSearch { 2 3 public static void main(String[] args) { 4 int[] a = {66, 44, 99, 33, 55, 22, 88, 77}; 5 System.out.println("search(a," "): " search(a,55)); 6 System.out.println("search(a," "): " search(a,50)); 7 } 9 public static int search(int[] a, int target) { for (int i = 0; i < a.length; i++) if (a[i] == target) return i; 12 return -a.length; 13 } 14 }

20 출력 결과      {66,44,99,33,55,22,88,77}      search(a,55): 4      search(a,50): -8

21 3.6 복잡도 분석 점근적 비례 (asymptotically proportional)
두 함수는 그들의 비율과 그 비율의 역에 대해 어떤 상수값으로 상한값이 주어지면 점근적으로 비례 예: 두 함수 f(n) = 4n-3과 g(n)=n은 점근적으로 비례 두 함수의 비율인 f(n)/g(n) = (4n-3)/(n) = 4-3/n은 4에 의해 상한값이 주어짐 그 역은 g(n)/f(n) = (n)/(4n-3) = 1/(4-3/n)은 1에 의해 상한값이 주어짐 n이 커지면 3/n은 아주 작아지므로 f(n)/g(n)은 거의 4와 같아지고, 이는 f(n)≈4g(n)임을 의미 g(n)=n에 점근적으로 비례적인 모든 함수의 집합을 Θ(n)으로 표기 f(n)=4n-3은 복잡도 클래스 Θ(n)의 한 원소가 됨 이를 4n-3∈Θ(n) 또는 4n-3 = Θ(n)으로 표기.

22 대부분의 알고리즘들의 실행 시간 행위는 Θ(1), Θ(lg n), Θ(n), Θ(n lg n), Θ(n2), Θ(n3), Θ(2n)의 7개 주요 범주의 하나에 속함
이 범주들을 복잡도 클래스(complexity class) 또는 점근적 성장 클래스(asymptotic growth class)라고 함 Θ(1) : 상수 시간(constant time) Θ(n2) : 제곱 시간(quadratic time) Θ(n3) : 큐빅 시간(cubic time) 5개의 상이한 복잡도 클래스의 정의 O(g(n)) = {f(n)|f(n)/g(n)에 한계값이 주어짐} Ω(g(n)) = {f(n)|g(n)/f(n)에 한계값이 주어짐} Θ(g(n)) = {f(n)|f(n)/g(n)과 g(n)/f(n)에 한계값이 주어짐} o(g(n)) = {f(n)|n→∞일 때 f(n)/g(n)→0} ω(g(n)) = {f(n)|n→∞일 때 g(n)/f(n)→0} “big oh of g(n)”, “big omega of g(n)”, “big theta of g(n)”, “little oh of g(n)”, “little omega of g(n)”이라고 발음

23 복잡도 클래스들간의 관계 Θ(g) = O(g)∩Ω(g) o(g(n)) ⊂ O(g(n))―Θ(g(n))
ω(g(n)) ⊂ Ω(g(n))―Θ(g(n)) 

24 3.7 이진 탐색 주어진 시이퀀스가 정렬이 되어 있을 때 알고리즘 구현: 리스팅 3.6 시간 복잡도: Θ(lg n)
주어진 시이퀀스를 반복적으로 반으로 나누어가며, 각 단계에서 그 범위에 목표를 포함하는 반쪽에 집중 알고리즘 입력: 시이퀀스와 목표 값 x 출력: 인덱스 값 i 선조건: 시이퀀스는 정렬되어 있음 후조건: ai = x; 또는 모든 j<p에 대해서 aj<x이고 모든 j≥p에 대해서 aj>x일 때 i = -p-1    1. p=0, q=n-1로 놓음.    2. p≤q이면 단계 2-5를 반복.    3. i = (p+q)/2로 놓음.    4. ai = x이면, i를 리턴.    5. ai < x이면, p = i+1로 놓음; 그렇지 않으면 q = i-1로 놓음.    6. -p-1을 리턴. //x를 위치시킬 인덱스, -(-p-1)-1=p 구현: 리스팅 3.6 시간 복잡도: Θ(lg n)

25 이진 탐색 LISTING 3.6: The Binary Search 1 public class TestBinarySearch {
3 public static void main(String[] args) { 4 int[] a = {22, 33, 44, 55, 66, 77, 88, 99}; System.out.println("search(a," "): " + search(a, 55)); System.out.println("search(a," "): " + search(a, 50)); 7 } 9 static int search(int[] a, int x) { 10 int p = 0, q = a.length-1; 11 while (p <= q) { // search the segment a[p..q] 12 int i = (p+q)/2; // index of element in the middle 13 if (a[i] == x) return i; 14 if (a[i] < x) p = i+1; // search upper half 15 else q = i-1; // search lower half 16 } 17 return -p-1; // not found } 19 }

26 출력 결과      search(a,55): 3      search(a,50): -4

27 3.8 java.util.Arrays 클래스 배열 조작을 위한 여러 유틸리티 메소드를 제공
모두 static 선언으로 되어 있음 (접두어 “Arrays”에 의해 호출됨) 메소드의 일부 public static int binarySearch(double[] a, double x) public static boolean equals(double[] a, double[] b) public static void fill(double[] a, double x) public static void fill(double[] a, int lo, int hi, double x) public static void sort(double[] a)

28 java.util.Arrays 클래스의 사용
LISTING 3.7: Using the java.util.Arrays Class 1 public class TestJavaUtilArrays { 3 public static void main(String[] args) { 4 int[] a = {77, 44, 55, 22, 99, 66, 33, 88}; 5 print(a); 6 java.util.Arrays.sort(a); 7 print(a); 8 test(a,55); 9 test(a,60); 10 test(a,88); 11 test(a,90); } static void test(int[] array, int target) { int i = java.util.Arrays.binarySearch(array,target); 15 System.out.print("target="+target+", i="+i); 16 if (i >= 0) System.out.println("\ta[" + i + "]=" + array[i]); 17 else System.out.println("\tInsert " + target+" at a["+(-i-1)+"]"); } static void print(int[] a) { 21 // See lines in Listing 3.1 on page 8 } 23 }

29 출력 결과    a = {77,44,55,22,99,66,33,88}    a = {22,33,44,55,66,77,88,99}    target=55, i=3  a[3]=55    target=60, i=-5 Insert 60 at a[4]    target=88, i=6  a[6]=88    target=90, i=-8 Insert 90 at a[7]

30 3.9 사용자 정의 IntArrays 클래스 int 배열을 위한 “집에서 만든(homegrown)” IntArrays 클래스: 리스팅 3.8

31 LISTING 3.8: A User-Defined Utility IntArrays Class
1 public class IntArrays { 2 private static java.util.Random random = new java.util.Random(); 4 /** Determines whether the specified array is in ascending order. 7 a the array. 8 true if a[] is in ascending order, otherwise false. */ public static boolean isSorted(int[] a) { 11 for (int i = 1; i < a.length; i++) 12 if (a[i] < a[i-1]) return false; 13 return true; } 16 /** Prints all the elements in the specified array. 19 a the array. */ public static void print(int[] a) { 22 System.out.print("{" + a[0]); 23 for (int i = 1; i < a.length; i++) 24 System.out.print("," + a[i]); 25 System.out.println("}"); }

32 28 /** Returns a new array of n random integers. If range>0, then
30 * the elements will be uniformly distributed in the range 31 * 0 <= a[i] < range; otherwise, they will range over all int values. 34 n the length of the new array. 35 range determines the range of the element values. 36 IllegalArgumentException. 37 the new array. */ 39 public static int[] randomInts(int n, int range) { 40 if (n<0 || range<2) throw new IllegalArgumentException(); 41 int[] a = new int[n]; 42 for (int i=0; i<n; i++) 43 a[i] = random.nextInt(range); 44 return a; 45 } 47 /** Returns a new array of size n that contains the elements of 49 * the specified array a and 0s thereafter. 51 a the array to be copied. 52 n the length of the new array. 53 IllegalArgumentException. 54 the new array */

33 56 public static int[] resize(int[] a, int n) {
if (n<a.length) throw new IllegalArgumentException(); int[] aa = new int[n]; 59 System.arraycopy(a, 0, aa, 0, a.length); 60 return aa; } 63 /** Interchanges element i with element j in the specified array. 66 a the array. 67 i index of one element. 68 j index of the other element. 69 */ public static void swap(int[] a, int i, int j) { 71 int ai = a[i], aj = a[j]; 72 if (ai == aj) return; 73 a[i] = aj; 74 a[j] = ai; 75 } 76 }

34 3.10 java.util.Vector 클래스 버전 1.1에서 java.util 패키지에 Vector 클래스 도입
그 이후로 java.util.ArrayList 클래스로 대체 크기조정가능 배열(resizable array) 한 배열을 동일 원소들을 포함하는 더 큰 배열로 대체하는 프로그래밍 기법 새 배열은 기본 배열의 2배의 길이를 갖게 됨 정수 배열의 크기 조정 LISTING 3.9: Resizing an Integer Array 1 int[ ] resized(int[ ] a) { 2 int n=a.length; 3 int[ ] aa = new int[2*n]; 4 System.arraycopy(a,0,aa,0,n); 5 return aa; 6 } Vector 클래스 그림 3.4, 리스팅 3.10 – 3.13

35 Vector 클래스

36 java.util.Vector 클래스의 단순화된 버전
LISTING 3.10: A Simplified Version of the java.util.Vector Class 1 public class Vector { 2 protected Object[] objects; // backing array 3 protected int size; // actual number of Objects stored 4 protected static final int CAPACITY=10;   6 public Vector(int capacity) {   7 if (capacity<=0) throw new IllegalArgumentException("capacity<=0"); 8 objects = new Object[capacity];   9 }   11 public Vector() { 12 this(CAPACITY); } public int size() { 16 return size; } 19 //... protected void resize() { 22 int n=objects.length; 23 Object[] temp = new Object[2*n]; 24 System.arraycopy(objects, 0, temp, 0, n); 25 objects = temp; } 27 }

37 Vector 클래스를 위한 toString() 메소드
LISTING 3.11: A toString() Method for the Vector Class 1 public String toString() { 2 if (size == 0) return "()"; 3 StringBuffer buf = new StringBuffer("(" + objects[0]); 4 for (int i = 1; i < size; i++) 5 buf.append("," + objects[i]); 6 return buf + ")"; 7 }

38 배열을 적재하는 생성자 LISTING 3.12: A Constructor That Loads an Array
1 public Vector(Object[] a) { 2 int n = a.length; 3 objects = new Object[2*n]; 4 System.arraycopy(a,0,objects,0,n); 5 size = n; 6 }

39 Vector 클래스의 테스팅 LISTING 3.13: Testing the Vector Class
1 public static void main(String[] args){ 2 Vector v = new Vector(args); 3 System.out.println(v); 4 } 출력 결과 A:＼>java TestVector alpha beta gamma delta      (alpha,beta,gamma,delta)

40 3.11 다차원 배열 2차원 배열: 배열의 원소가 다시 배열 2차원 배열의 사용: 리스팅 3.14 배열 a[ ][ ]
분리된 배열들의 배열 각 컴포넌트 배열의 크기가 다름 -> 울퉁불퉁한 배열 (ragged array) 배열 b[ ][ ] 균일 컴포넌트 배열 3개 모두가 4-원소 서브-배열(행)

41 2-차원 배열의 사용 2 public static void main(String[] args) {
LISTING 3.14: Using Two-Dimensional Arrays 1 public class TwoDimensionalArrays { 2 public static void main(String[] args) { 3 int[][] a = new int[3][]; // an array of 3 sub-arrays (rows) 4 a[0] = new int[]{22,44,66,88}; // the first row 5 a[2] = new int[]{33,77}; // the third row 6 System.out.println("a: " + a + "\na.length: " + a.length); 7 IntArrays.print(a[0]); 8 IntArrays.print(a[2]); 9 System.out.println("a[2].length: " + a[2].length); 10 int[][] b = { { 22,44,66,88 }, // the first row of b { 0, 0, 0, 0 }, // the second row of b { 33,55,77, 0 } }; // the third row of b 13 System.out.println("b: " + b + "\nb.length: " + b.length); 14 IntArrays.print(b[0]); 15 IntArrays.print(b[2]); 16 System.out.println("b[2].length: " + b[2].length); } 18 }

42 출력 결과    a:    a.length: 3    {22,44,66,88}    {33,77}    a[2].length: 2    b:    b.length: 3    {33,55,77,0}    b[2].length: 4

43 완전한 java.util.Vector 클래스

44 예제 3.2: 파스칼의 삼각형 예제: Pascal’s Triangle
j≤i인 행 i와 열 j의 원소에 이항 계수 cij를 가지는 2-차원 배열 순환 관계 cij = ci-1,j-1+ci-1,j 성립 즉, 삼각형 내부의 수는 바로 위의 수와 왼쪽 상단의 수의 합

45 파스칼의 삼각형 1 public class PascalsTriangle {
2 public static void main(String[] args) { 3 int rows = Integer.parseInt(args[0]); 4 int[][] a = init(rows); 5 print(a); 6 } 8 static int[][] init(int n) { 9 int[][] a = new int[n][n]; 10 for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) if (j == 0 || j == i) a[i][j] = 1; else a[i][j] = a[i-1][j-1] + a[i-1][j]; 14 return a; 15 } static void print(int[][] a) { 18 for (int i = 0; i < a.length; i++) { for (int j = 0; j <= i; j++) print(a[i][j], 5); System.out.println(); } } static void print(int n, int w) { 26 // prints n right-justified in a field on width w: 27 String s = "" + n, blanks = “ "; 28 int len = s.length(); 29 System.out.print(blanks.substring(0, w-len) + s); } 31 }

46 명령어 라인 인자 7(args[0]으로)에 대한 출력 결과
     1      1   1      1   2   1      1   3   3   1      1   4   6   4   1      1   5  10  10   5   1      1   6  15  20  15   6   1

47 3.12 사례 연구: 용어 색인의 구축 용어색인(concordance) :
문서에 있는 모든 단어에 대한 인덱스로서 각 단어의 각 어커런스에 대한 위치(권, 장, 절, 페이지, 문장, 라인 번호)를 나열 마크 앤토니의 연설의 용어 색인 : 예제 3.3

48 예제 3.3 : 텍스트 문서와 그 용어 색인

49 용어 색인을 위한 ADT는 맵이라고 부름 맵(map) 각 입력을 다른 출력으로 매핑하는 입력-출력 장치 처럼 사용
입력은 단어, 출력은 그 단어를 발견할 수 있는 라인 번호의 리스트 입력 x를 키(key), 출력 y를 그 값(value)이라고 함 사전, 연관 배열, 조사 테이블(look-up table)이라고도 함

50 Map 타입에 대한 추상 데이터 타입 ADT: Map
String get(String key)    리턴: 주어진 키에 대한 현재 값, 또는 발견하지 못하면 널.    후조건: 이 맵은 변경되지 않음. String put(String key, String value)    리턴: 주어진 키에 대한 옛날 값, 또는 발견하지 못하면 널.    후조건: 항목 쌍 (키, 값)이 맵에 존재함. int size()    리턴: 맵의 항목 쌍의 수. String toString()    리턴: 전체 컬렉션의 문자열 표현.

51 Map 인터페이스 LISTING 3.16: A Map Interface 1 public interface Map {
2 public String get(String key); 3 public String put(String key, String value); 4 public int size(); 5 public String toString(); 6 }

52 ArrayMap 클래스에 대한 UML 다이어그램

53 용어 색인 자료 구조

54 ArrayMap 클래스 LISTING 3.17: An ArrayMap Class
1 public class ArrayMap implements Map { 2 private static final int INITIAL_LENGTH=10; 3 private Entry[] a = new Entry[INITIAL_LENGTH]; 4 private int size; 6 public String get(String key) { 7 for (int i = 0; i < size; i++) if (a[i].key.equals(key)) return a[i].value; 9 return null; } public String put(String key, String value) { 13 for (int i = 0; i < size; i++) if (a[i].key.equals(key)) return a[i].setValue(value); 15 if (size == a.length) resize(); 16 a[size++] = new Entry(key,value); 17 return null; 18 } private void resize() { 21 Entry[] aa = new Entry[2*a.length]; 22 System.arraycopy(a, 0, aa, 0, a.length); 23 a = aa; }

55 public int size() { 27 return size; } public String toString() { 31 StringBuffer buf = new StringBuffer(); 32 for (int i = 0; i < size; i++) buf.append(a[i] + "\n"); 34 return buf.toString(); } private static class Entry { 38 String key, value; 40 public Entry(String key, String value) { this.key = key; this.value = value; } public String setValue(String value) { 46 String oldValue = this.value; 47 this.value = value; 48 return oldValue; } public String toString() { 52 return key + ": " + value; } } 55 }

56 ArrayMap 클래스의 테스팅 LISTING 3.18: Testing the ArrayMap Class
1 import java.io.*; // defines the FileReader and BufferedReader classes 2 import java.util.StringTokenizer; 4 public class Main { 5 6 public Main(String file) { 7 Map map = new ArrayMap(); 8 int lineNumber = 0; 9 try { BufferedReader in = new BufferedReader(new FileReader(file)); String line = in.readLine(); while(line != null) { lineNumber; StringTokenizer parser = new StringTokenizer(line, " ,:;-.?!"); while (parser.hasMoreTokens()) { String word = parser.nextToken().toUpperCase();

57 17 String list = map.get(word);
if (list == null) map.put(word, "" + lineNumber); else map.put(word, list + "," + lineNumber); } System.out.println(lineNumber + ":\t" + line); line = in.readLine(); 23 } 24 in.close(); } catch(IOException e) { System.out.println(e); } System.out.println(map); System.out.println("lines: " + lineNumber); System.out.println("distinct words: " + map.size()); 29 } 30 31 public static void main(String[] args) { 32 new Main(args[0]); 33 } 34 }

58 리스팅 3. 18의 솔루션은 모든 단어와 그 라인 번호들의 리스트를 프린트한다
리스팅 3.18의 솔루션은 모든 단어와 그 라인 번호들의 리스트를 프린트한다. 그러나, 단어들은 문서에서 파싱된 순서대로 프린트된다.    FRIENDS: 1    ROMANS: 1    COUNTRYMEN: 1    LEND: 1    ME: 1,33,35    YOUR: 1    EARS: 1    I: 2,12,24,28,29,29,35    COME: 2,12,35    TO: 2,2,12,13,16,28,29,31,32,35    BURY: 2    CAESAR: 2,5,6,8,18,19,34    ...

59 항목을 알파벳 순서로 삽입 LISTING 3.19: Inserting the Entries in Alphabetical Order 1 public String put(String key, String value) { 2 int i=0; 3 while (i<size) { 4 if (a[i].key.equals(key)) return a[i].setValue(value); 5 if (a[i].key.compareTo(key) > 0) break; 6 ++i; 7 } 8 if (size == a.length) resize(); 9 System.arraycopy(a, i, a, i+1, size-i); 10 a[i] = new Entry(key, value); size; 12 return null; 13 }

60 용어 색인 자료 구조 새로운 키 COFFIN의 삽입 전의 상태

61 용어 색인 자료 구조 새로운 키 COFFIN의 삽입을 위한 공간 확보 후의 상태