Ngôn ngữ Java - Bài 3: Mảng và xâu

BÀI 3: MẢNG VÀ XÂU PHẦN 1: NGÔN NGỮ JAVA 2 Mảng Cấu trúc dữ liệu v Trong nhiều bài toán, một số dữ liệu có cấu trúc tự nhiên §  Ví dụ : Texts are sequences of characters Images are matrices of pixels Classes contain sets of students v Java cung cấp một số lớp và tool gọi là cấu trúc dữ liệu §  hỗ trợ tổ chức dữ liệu §  thuận lợi trong việc truy cập và cập nhập dữ liệu Một số cấu trúc dữ liệu §  Array/Arrays (the data structure we will cover) §  ArrayList §  HashSet §  LinkedHashSet §  LinkedList §  TreeSet §  Vector §  HashMap 5 Opening problem v Xét chương trình sau : How many days' temperatures? 7 Day 1's high temp: 45 Day 2's high temp: 44 Day 3's high temp: 39 Day 4's high temp: 48 Day 5's high temp: 37 Day 6's high temp: 46 Day 7's high temp: 53 Average temp = 44.57142857142857 4 days were above average. 6 What makes the problem hard? v Không sử dụng biến, cần 2 lần nhập giá trị vào §  để tính giá trị trung bình, thông qua tổng tích luỹ §  để đếm số lần lớn hơn giá trị trung bình v Sử dụng biến §  Cần khai báo bao nhiêu biến để chứa? v Cần một cách -> khai báo nhiều biến một lần. 7 Mảng v array: Đối tượng chứa nhiều giá trị cùng loại. §  element: một giá trị trong mảng §  index: số nguyên chỉ vị trí của giá trị trong mảng 3 72 84 -6 17 5 26 -2 49 12 value 9 8 7 6 5 4 3 2 1 0 index element 0 element 4 element 9 8 Khai báo mảng v  Khai báo/khởi tạo mảng : [] = new []; v  Ví dụ : int[] numbers = new int[10]; v  length: bất kỳ số nguyên nào: int x = 2 * 3 + 1; int[] data = new int[x % 5 + 2]; 0 0 0 0 0 0 0 0 0 0 value 9 8 7 6 5 4 3 2 1 0 index 9 Tự động khởi tạo mảng v Khi mảng được khởi tạo, tất cả phần tử được khởi tạo tự động tương đương giá trị 0. §  int: 0 §  double: 0.0 §  boolean: false §  object type: null (null means "no object")‏ 10 Ví dụ v Mảng double v Mảng booleans 0.0 0.0 0.0 0.0 0.0 value 4 3 2 1 0 index false false false false value 3 2 1 0 index 11 Gán phần tử mảng v Gán giá trị cho phần tử mảng: [] = ; v Ví dụ: numbers[0] = 27; numbers[3] = -6; 0 0 0 0 0 0 -6 0 0 27 value 9 8 7 6 5 4 3 2 1 0 index 12 Truy cập phần tử mảng v Cú pháp : [] v Ví dụ: System.out.println(numbers[0]); if (numbers[3] < 0) { System.out.println("Element 3 is negative."); } 0 0 0 0 0 0 -6 0 0 27 value 9 8 7 6 5 4 3 2 1 0 index 13 Vượt quá giới hạn mảng v Đọc/ghi index bên ngoài khoảng rộng của mảng dẫn tới một ArrayIndexOutOfBoundsException. v VÍ dụ : int[] data = new int[10]; System.out.println(data[0]); // okay System.out.println(data[-1]); // exception! System.out.println(data[9]); // okay System.out.println(data[10]); // exception! 0 0 0 0 0 0 0 0 0 0 value 9 8 7 6 5 4 3 2 1 0 index 14 Mảng và vòng lặp for v  Mảng thường được dùng với vòng lặp for v Example: for (int i = 0; i < 8; i++) { System.out.print(numbers[i] + " "); } System.out.println(); // end the line of output Output: 0 4 11 0 44 0 0 2 15 Mảng và vòng lặp for for (int i = 0; i < 8; i++) { numbers[i] = 2 * i; } v What’s in the array? 14 12 10 8 6 4 2 0 value 7 6 5 4 3 2 1 0 index 16 Mảng và vòng lặp for for (int i = 0; i < 8; i++) { numbers[i] = i * i; } v What’s in the array? 49 36 25 16 9 4 1 0 value 7 6 5 4 3 2 1 0 index 17 Trường length v Trường length chứa số lượng phần tử. v Cú pháp : .length v NB: Trường -> không sử dụng () String's .length()! 18 Ví dụ for (int i = 0; i < numbers.length; i++) { System.out.print(numbers[i] + " "); } Output: 0 1 4 9 16 25 36 49 v What expression refers to the last element of an array? The middle element? 19 Bài toán nhiệt độ v Solve the following problem: How many days' temperatures? 7 Day 1's high temp: 45 Day 2's high temp: 44 Day 3's high temp: 39 Day 4's high temp: 48 Day 5's high temp: 37 Day 6's high temp: 46 Day 7's high temp: 53 Average temp = 44.57142857142857 4 days were above average. 20 Solution // This program reads several days' temperatures from the user // and computes the average and how many days were above average. import java.util.*; public class Weather { public static void main(String[] args) { Scanner console = new Scanner(System.in); System.out.print("How many days' temperatures? "); int days = console.nextInt(); int[] temperatures = new int[days]; // array to store days' temperatures int sum = 0; for (int i = 0; i < days; i++) { // read/store each day's temperature System.out.print("Day " + (i + 1) + "'s high temp: "); temperatures[i] = console.nextInt(); sum += temperatures[i]; } double average = (double) sum / days; int count = 0; // see if each day is above average for (int i = 0; i < days; i++) { if (temperatures[i] > average) { count++; } } // report results System.out.println("Average temp = " + average); System.out.println(count + " days above average"); } } 21 Ưu điểm của mảng v Arrays store a large amount of data accessible from one variable. v Arrays let us access data in random order. §  Cassette tape vs. DVD v Arrays can represent sequential data. §  An array of quiz scores can store not just the scores, but also the order in which the quizzes were taken. 22 Câu lệnh khởi tạo mảng v Khởi tạo nhanh : [] = {, , ..., }; v Ví dụ: int[] numbers = { 12, 49, -2, 26, 5, 17, -6 }; v Tiện lợi khi biết trước giá trị các phần tử. -6 17 5 26 -2 49 12 value 6 5 4 3 2 1 0 index 23 Ví dụ int[] a = { 2, 5, 1, 6, 14, 7, 9 }; for (int i = 1; i < a.length; i++) { a[i] += a[i - 1]; } v What’s in the array? 9 7 14 6 1 5 2 value 6 5 4 3 2 1 0 index 44 35 2814 87 24 In mảng : Arrays.toString v Arrays.toString: tham số trả về String các giá trị mảng. v Example: int[] a = { 2, 5, 1, 6, 14, 7, 9 }; for (int i = 1; i < a.length; i++) { a[i] += a[i - 1]; } System.out.println("a is " + Arrays.toString(a)); Output: a is [2, 7, 8, 14, 28, 35, 44] 25 Dịch chuyển các phần tử trong mảng 26 Chèn phần tử v Chèn một giá trị vào mảng số nguyên đã sắp xếp, (dữ nguyên kích thước mảng)? 18 2 37 3 64 6 1 value 4 1 0 index 6 2 18 3 37 3 1 value 4 1 0 index 27 Chèn phần tử public static void insertInOrder(int[] array, int num) { int insertionIndex = findInsertionIndex(array, num); if (insertionIndex < array.length) { for (int i = array.length - 1; i >= insertionIndex + 1; i--) { array[i] = array[i-1]; } array[insertionIndex] = num; } } public static int findInsertionIndex(int[] array, int num) { for (int i = 0; i < array.length; i++) { if (num < array[i]) { return i; } } return array.length; } 28 Quay trái phần tử 9 2 7 3 5 8 3 value 4 1 0 index 7 2 5 3 3 9 8 value 4 1 0 index 29 Quay trái phần tử public static void rotateLeft(int[] array) { int first = array[0]; for (int i = 0; i < array.length - 1; i++) { array[i] = array[i + 1]; } array[array.length - 1] = first; } Enum v Tạo các kiểu dữ liệu bao gồm tập các giá trị rời rạc v Ví dụ: public enum Monster{ZOMBIE, VAMPIRE, DEMON, WEREWOLF}; v Tên của Enum được viết hoa -> kiểu dữ liệu v Tất cả giá trị đều được viết hoa -> hằng số; Mỗi thực thể sẻ có một giá trị Enum v Định nghĩa một biến kiểu enum : Monster m = Monster.ZOMBIE; v Sư dụng để kiểm tra giá trị : if(m == Monster.ZOMBIE) System.out.println(“Zombie approaching!”); v Sử dụng trong tham số của phương thức : myMethod(Monster m){} v Sử dung như đối số: myMethod(Monster.ZOMBIE); 34 Mảng nhiều chiều 35 Chứa giá trị của một bảng ? 8 sinh viên có 10 điểm thi : Chứa dữ liệu? 7.5 4.5 9.5 2 7 8.5 1 8.5 7.5 6 4.5 2 9 9 5.5 4 7.5 6 5 9 36 Solution 1: 1 sinh viên/mảng double [] student1 = new double[10]; ... double [] student8 = new double[10]; student1: ... student8: 7.5 4.5 9.5 2 7 8.5 1 8.5 7.5 6 4.5 2 9 9 5.5 4 7.5 6 5 9 37 Solution 2: 1 mảng/môn double [] quiz1 = new double[8]; ... double [] quiz10 = new double[8]; quiz1: ... quiz10: 7.5 4.5 6 9 38 Solution 3: Mảng 2 chiều! double [][] quizScores = new double[8][10]; quizScores: 7.5 4.5 9.5 2 7 8.5 1 8.5 7.5 6 4.5 2 9 9 5.5 4 7.5 6 5 9 quizScores[0][6] quizScores[7][9] Mảng 2 chiều trong bộ nhớ v Mảng của mảng! double [][] quizScores = new double[4][3]; quizScores quizScores[0] quizScores[1] quizScores[2] quizScores[3] Mảng 2 chiều không đều double [][] quizScores = new double[4][]; quizScores[0] = new double[3]; quizScores[2] = new double[5]; quizScores quizScores[0] quizScores[1] quizScores[2] quizScores[3] 44 Xử lý text 45 Xử lý text v  text processing: Duyệt, sửa, định dạng. §  Text processing thường sử dụng vòng lặp for để duyệt từng ký tự của xâu. v  2 kiểu dữ liệu char String Biểu diễn một ký tự riêng lẻ Biểu điễn chuổi ký tự Dữ liệu kiểu gốc Kiểu đối tượng; không phải kiểu gốc Sử dụng dấu nháy đơn ' Sử dụng dấu nháy kép e.g.: ‘T’ ‘t’ ‘3’ ‘%’ ‘\n’ e.g.: “We the people” “1. Twas brillig, and the slithy toves\n” “” “T” 46 Characters v char: Kiểu dữ liệu gốc, biểu diễn một ký tự đơn lẻ. v  Những ký tự riêng lẻ trong xâu String có giá trị kiểu char. v  Các ký tự thường được bao quanh bởi dấu ', ví dụ'a' or '4' or '\n' or '\'' v  Khái báo, khởi tạo, sử dụng như các kiểu khác. char letter = 'S'; System.out.println(letter); // prints S Strings v  String: Kiểu đối tượng biểu diễn chuỗi ký tự §  Length: 0, 1 hoặc dài hơn §  Mỗi phần tử: char §  "string" §  Khai báo, khởi tạo, gán và sử dụng biến String như dữ liệu khác String s = “Hello, world\n”; // declare, init System.out.println(s); // use value s = s + “I am your master\n”; // concatenate // and assign 48 Các phương thức của String Các kiểu đối tượng có thể có các phương thức kiểu dữ liệu gốc . returns the index where the start of the given string appears in this string (-1 if not found)‏ indexOf(str)‏ returns a new string with all uppercase letters toUpperCase()‏ returns a new string with all lowercase letters toLowerCase()‏ returns the characters in this string from index1 up to, but not including, index2 substring(index1,index2)‏ returns the number of characters in this string length()‏ returns the character at the given index charAt(index)‏ Description Method name 49 Phương thức charAt v  Truy cập một ký tự. String word = “cola”; char firstLetter = word.charAt(0); if (firstLetter == 'c') { System.out.println("C is for cookie!"); } charAt(i): ‘c’ ‘o’ ‘l’ ‘a’ Index i: 0 1 2 3 Starts at 0! Gọi các phương thức của String v Giả sử s biến kiểu String v Cú pháp: s.() v Some examples: String s = “Cola”; int len = s.length(); // len == 4 char firstLetter = s.charAt(0); // ‘C’ int index = s.indexOf(“ol”); // index == 1 String sub = s.substring(1,3); // “ol” String up = s.toUpperCase(); // “COLA” String down = s.toLowerCase(); // “cola” 51 Fun with char! v char có thể được nối với String. char initial = 'P'; System.out.println(initial + ". Diddy"); v  So sánh bằng các toán tử quan hệ. §  'a' < 'b' and 'Q' != 'q' §  Caution: Không dùng được với String! v  Example: // print the alphabet for (char c = 'a'; c <= 'z'; c++) { System.out.print(c); } 52 char vs. String v 'h' is a char char c = 'h'; §  char : kiểu dữ liệu gốc -> không có phương thức §  Không được gọi: c.length() or c.toUpperCase()‏ v "h" is a String String s = "h"; §  Đói tượng -> có phương thức. §  can say s.length() 1 §  can say s.toUpperCase() "H" §  can say s.charAt(0) 'h' Numbers vs Strings v  345 is an int int i = 345; §  int values are primitive; you cannot call methods on them §  CAN perform arithmetic: i = i * 2; // i==690 §  CANNOT say i.length() or i.charAt(0)‏ v  “345" is a String String s = “345"; §  Strings are objects; they contain methods that can be called §  can say s.length() // returns 3 §  can say s.charAt(1) // returns ‘4’ §  CANNOT perform arithmetic: s = s * 2; // ERROR! 54 So sánh string v  Nên dùng phương thức equals để so sánh 2 đối tượng . v  Example: Scanner console = new Scanner(System.in); System.out.print("What is your name? "); String name = console.next(); if (name.equals("Barney")) { System.out.println("I love you, you love me,"); System.out.println("We're a happy family!"); } 55 So sánh strings v Đối tượng String có nhiều phương thức có thể được sử dụng trong điều kiện . whether this string’s beginning matches the argument startsWith(str)‏ whether this string’s end matches the argument endsWith(str)‏ whether this string contains the same characters as the other, ignoring upper- vs. lowercase differences equalsIgnoreCase(str) ‏ whether this string contains exactly the same characters as the other string equals(str)‏ Description Method 56 So sánh strings: Examples §  if (title.endsWith("M.D.")) { System.out.println("What's your number?"); } §  if (fullName.startsWith("Giorgio")) { System.out.println("When are you retiring?"); } §  if (lastName.equalsIgnoreCase("lumBerg")) { System.out.println("I need your TPS reports!"); } §  if (name.toLowerCase().indexOf("sr.") >= 0) { System.out.println("You must be old!"); } Chuyển đổi kiểu dữ liệu int x = 2640; int y = 5280; return x / y; // integer arithmetic double z = (double) x; return z / y; // double arithmetic Ép kiểu Biểu thức ép kiểu: () Chuyển expression into sang kiểu . Examples: (double) 2640 == 2640.0 (int) 32.7 == 32 (int) ‘A’ == ?? (char) 97 == ?? (String) ‘A’ == ?? (String) 27 == ?? Ép kiểu Biểu thức ép kiểu: () Chuyển expression into sang kiểu . Examples: (double) 2640 == 2640.0 (int) 32.7 == 32 (int) ‘A’ == 65 (char) 97 == ‘a’ (String) ‘A’ == TypeCastException (String) 27 == TypeCastException Ép kiểu với String? Ép kiểu (String) không sử dụng được với các kiểu dữ liệu gốc như char, int, vàdouble. Có nhiều cách để ép kiểu String: Converting to strings: int x to String: x + “” or “” + x double x to String: x + “” or “” + x char, boolean, or float x to String: same thing Ép kiểu với String? Ép kiểu (String) không sử dụng được với các kiểu dữ liệu gốc như char, int, vàdouble. Có nhiều cách để ép kiểu String: Converting from strings: String s to int: Integer.parseInt(x) String s to double: Double.parseDouble(x) String s to char: Character.parseChar(x) Đọc vào Strings Có thể sử dụng Scanners: next() và hasNext(). Example: Please enter your name: Alexander Pieter Yates Name 1 has 9 letters Name 2 has 6 letters Name 3 has 5 letters Solution import java.util.Scanner; public class NameLength { public static void main(String [] args) { Scanner scan = new Scanner(System.in); System.out.print(“Please enter your name”); int i=1; while(scan.hasNext()) { String s = scan.next(); int length = s.length(); System.out.println(“Name “ + i + “ has “ + length + “ letters”); i++; } } } Lớp Scanner (tiếp) return method Description int nextInt() Reads the next token, converts it to an int (if possible), and returns the int value. double nextDouble() Reads the next token, converts it to a double (if possible), and returns the double value. String next() Reads the next token, and returns it. boolean hasNext() Returns true if there are more tokens. 68 StringBuilder /StringBuffer v Một lựa chọn khác cho lớp String v StringBuilder/StringBuffer is more flexible than String. You can add, insert, or append new contents into a string buffer, whereas the value of a String object is fixed once the string is created. 69 StringBuilder v Lớp StringBuilder hỗ trợ cho lớp String. v Mềm dẻo hơn String. §  Có thể thêm, chèn hoặc nối nội dung mới vào bộ đệm string String: đối tượng được cố định khi được tạo. v Thường phân tách StringBuilder thành String khi hoàn thành khởi tạo. 70 StringBuilder Constructors 71 Modifying Strings in the Builder 72 toString, capacity, length, setLength, và charAt 73 Ví dụ StringBuilder stringBuilder = new StringBuilder("Welcome to "); stringBuilder.append("Java"); stringBuilder.delete(8, 11) changes the builder to Welcome Java. stringBuilder.deleteCharAt(8) changes the builder to Welcome o Java. stringBuilder.reverse() changes the builder to avaJ ot emocleW. stringBuilder.replace(11, 15, "HTML") changes the builder to Welcome to HTML. stringBuilder.setCharAt(0, 'w') sets the builder to welcome to Java. StringTokenizer v boolean hasMoreTokens() v String nextToken() v String nextToken(String delim) 74 26/08/15 StringTokenizer +countTokens(): int +hasMoreTokens():boolean +nextToken(): String +nextToken(delim: String): String