Giáo trình Java cơ bản - Chương 5: Mảng

Nội dung text: Giáo trình Java cơ bản - Chương 5: Mảng

1. Mảng Chỉ số phần tử mảng 0 1 2 3 4 a 7 20 5 9 3 Tên mảng Giá trị
2. Trả lời câu hỏi 1. Mảng trên có mấy chiều? 2. Các phần tử của mảng có chung đặc điểm gì? a. Màu sắc b. Hình dạng c. Số nguyên 3. Trong java, mảng trên được khai báo như thế nào? 4. Cấu trúc lệnh nào thường dùng để duyệt mảng? a. IF b. For c. While 5. Tìm các số nguyên tố trong mảng trên?
3. NỘI DUNG MẢNG o Mảng một chiều o Sao chép mảng o Mảng nhiều chiều o Tìm kiếm phần tử trong mảng một chiều o Sắp xếp các phần tử trong mảng một chiều
4. Kiểu dữ liệu mảng Java có 2 kiểu dữ liệu cơ bản: o Kiểu dữ liệu cơ sở: có 8 kiểu o Kiểu dữ liệu tham chiếu (hay dẫn xuất): có 3 kiểu - Kiểu mảng - Kiểu lớp - Kiểu giao tiếp (interface).
5. Kiểu dữ liệu mảng o Khái niệm: Mảng là tập hợp nhiều phần tử có cùng tên, cùng kiểu dữ liệu. Mỗi phần tử trong mảng được truy xuất thông qua chỉ số của nó trong mảng. o Khai báo: []; hoặc [] ; o VD: int[] iarray; hoặc int iarray[]; int[] arrInt3, arrInt4, arrInt5;
6. Kiểu dữ liệu mảng Cấp phát bộ nhớ cho mảng: o Không giống C, C++ o Kích thước của mảng phải được xác định trước khi khai báo: o VD: int arrInt[100]; //sẽ báo lỗi o Dùng từ khóa new để cấp phát bộ nhớ cho mảng. o VD: int iarrInt = new int[100];
7. Kiểu dữ liệu mảng  Khởi tạo giá trị cho mảng o Có thể khởi tạo giá trị ban đầu cho các phần tử của mảng khi nó được khai báo. o VD: int[] arrInt = {1, 2, 3, 5, 6}; char[] arrChar = {‘a’, ‘b’, ‘c’}; String arrString[] = {“Nguyen Van A”, “Tran Van B”}; Chú ý: o Luôn khởi tạo hoặc cấp phát mảng trước khi sử dụng o Một số khai báo không hợp lệ: int[5] iarray; int iarray[5];
8. Truy cập mảng o Chỉ số mảng trong Java bắt đầu từ 0. Vì vậy phần tử đầu tiên có chỉ số là 0, phần tử thứ n có chỉ số là n - 1. o Các phần tử của mảng được truy xuất thông qua chỉ số của nó đặt giữa cặp dấu ngoặc vuông ([]). o VD: int arrInt[] = {1, 2, 3}; int x = arrInt[0]; // x sẽ có giá trị là 1. int y = arrInt[1]; // y sẽ có giá trị là 2. int z = arrInt[2]; // z sẽ có giá trị là 3.
9. Chiều dài mảng – số phần tử mảng o Lấy số phần tử mảng ta dùng lệnh tenmang.length o VD: int a[]=new int[10]; int b[]={1,3,5}; Kết quả: a.length=10; b.length=3;
10. Một số ví dụ về mảng //Nhập và xuất giá trị các phần tử của một mảng các số nguyên: public class ArrayDemo { public static void main(String[] args) { int arrInt[] = new int[10]; int i; for(i = 0; i < arrInt.length; i ++) arrInt[i] = i; for(i = 0; i < arrInt.length; i ++) System.out.println("This is arrInt[" + i +"]: " + arrInt[i]); } }
11. Một số ví dụ về mảng //Tìm phần tử có giá trị nhỏ nhất (Min) và lớn nhất (Max) trong một mảng. public class TimMaxMin { public static void main(String[] args) { int nums[] = { 99, -10, 100123, 18, -978, 5623, 463, -9, 287, 49 }; int min, max; min = max = nums[0]; for(int i=1; i max) max = nums[i]; } System.out.println("Min and max: " + min + " " + max); } }
12. Một số ví dụ về mảng import java.util.Scanner; //sap xep mang public class BTMang { System.out.println("Sap xep cac phan public static void main(String[] args) { tu cua mang theo chieu tang dan:"); Scanner input =new Scanner(System.in); for(i=0;i a[j]){ //nhap mang tg=a[i]; System.out.println("Nhap vao cac phan tu a[i]=a[j]; cua mang"); a[j]=tg; for(i=0;i< a.length;i++){ } System.out.print("a"+"["+i+"]"+"=" ); } a[i]=input.nextInt(); System.out.print(a[i] + " "); } } //in mang } System.out.println("Mang vua nhap:"); } for(i=0;i<a.length;i++){ System.out.print(a[i] + " "); } System.out.println("");
13. Một số ví dụ về mảng import java.util.Scanner; public static void Sapxep(int[] a){ public class BTMang2 { int i, j, tg; public static void Nhap(int[] a){ System.out.println("Sap xep cac phan Scanner input =new Scanner(System.in); tu cua mang theo chieu tang dan:"); System.out.println("Nhap vao cac phan for(i=0;i a[j]){ System.out.print("a"+"["+i+"]"+"=" ); tg=a[i]; a[i]=input.nextInt(); a[i]=a[j]; } a[j]=tg; } } public static void In(int[] a){ } System.out.println("Mang vua nhap:"); System. out.print(a[i] + " "); for(int i=0;i<a.length;i++){ } System.out.print(a[i] + " "); } } public static void main(String[] args) { System.out.println(""); } }
14. Một số ví dụ về mảng public static void main(String[] args) { int [] a = new int[5]; BTMang2 m2 = new BTMang2(); m2.Nhap(a); //in mang m2.In(a); m2.Sapxep(a); } }
15. Sao chép mảng Sử dụng một vòng lặp: • int[] sourceArray = {2, 3, 1, 5, 10}; • int[] targetArray = new int[sourceArray.length]; • for (int i = 0; i < sourceArray.length; i++) • targetArray[i] = sourceArray[i]; Dùng lệnh gán: Gán tham chiếu của sourceArray cho targerArray • targetArray = sourceArray; Dùng tiện ích arraycopy • System.arraycopy(srcArray, src_pos, tarArray, tar_pos, length);
16. Sao chép mảng import java.util.*; public class randomfile { public static void main(String[] args) { int[] s = {1,3,5,7,9,11,13,15}; int[] d = {2,4,6,8,10,12,14}; System.out.println(" mang d ban dau "); for(int i =0; i kết quả mảng d: for(int i =0; i< d.length; i++){ phần tử 6,8,10,12 được System.out.print(" "+d[i]); thay bằng 7,9,11,13 } } }
17. Mảng nhiều chiều o Khai báo n chiều trong java [][] [] ; hoặc [][] [] o Ví dụ khai báo mảng 2 chiều int a[][]; int[][] a;
18. Mảng nhiều chiều o Khai báo 1 mảng kèm theo cấp phát bộ nhớ cho mảng n chiều [][] [] = new [Số phần từ 1][Số phần tử 2] [Số phần tử n] o Ví dụ khai bào mảng 2 chiều (ma trận 2 hàng 3 cột) int a[][]=new int[2][3];
19. Mảng nhiều chiều o Truy xuất đến phần tử của mảng nhiều chiều A ta dùng cú pháp A[n-1][m-1] [k-1]; o Ví dụ truy xuất mảng 2 chiều int a[][]={ {3,4}, {2,8}, }; o Lúc đó: a[0][0]=3; a[0][1]=4; a[1][0]=2; a[1][1]=8;
20. Độ dài mảng nhiều chiều • Lấy số dòng của mảng: ArrayName.length • Lấy số phần tử của dòng i: ArrayName[i].length • Ví dụ: Cho mảng sau: int[][] array = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; – Khi đó: array.length cho kết quả là 4. array[0].length cho kết quả là 3
21. Một số ví dụ về mảng // Nhập và xuất giá trị của các phần tử trong một mảng hai chiều public class TwoD_Arr { public static void main(String[] args) { int t, i; int mang[][] = new int[3][4]; for(t=0; t < 3; ++t){ for(i=0; i < 4; ++i){ mang[t][i] = (t*4)+i+1; System.out.print(mang[t][i] + “ “); } System.out.println(); } } }
22. Lớp java.util.Arrays • Cung cấp một số phương thức xử lý các mảng: – 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 ) • Mỗi phương thức trên có cách thực hiện khác nhau cho các kiểu dữ liệu cơ sở (byte, short, int, long, float, double, char và boolean) và kiểu đối tượng.
23. Tìm kiếm trong mảng • Tìm kiếm là quá trình tìm một phần tử xác định trong mảng. – Ví dụ: Tìm một sinh viên trong danh sách SV. • Tìm kiếm là một thao tác cơ bản trong lập trình. • Có nhiều giải thuật và cấu trúc dữ liệu để tìm kiếm. Hai giải thuật cơ bản là: tìm kiếm tuyến tính (linear search) và tìm kiếm nhị phân (binary search).
24. Tìm kiếm tuyến tính • Phương pháp tìm kiếm tuyến tính so sánh phần tử khóa key với mỗi phần tử trong mảng. • Việc tìm kiếm sẽ kết thúc khi tìm thấy một phần tử mảng bằng key hoặc khi duyệt hết mảng mà không tìm thấy. • Ví dụ minh họa: Tạo một mảng 2 chiều (7 x 9) có các phần tử là các số nguyên ngẫu nhiên nằm trong [0- 1000) rồi hiển thị ra màn hình. Nhập số n từ bàn phím. Tìm kiếm và trả về số lần xuất hiện của tất cả các phần tử có giá trị bằng số vừa nhập vào. Nếu không tìm thấy thì in ra chuỗi “Khong tim thay!”.
25. Tìm kiếm nhị phân • Để thực hiện được tìm kiếm nhị phân, các phần tử mảng phải được sắp xếp theo thứ tự tăng/giảm dần. Giả sử mảng được sắp xếp tăng dần: 2 4 7 10 11 45 50 59 60 66 69 70 79
26. Tìm kiếm nhị phân • Trước tiên so sánh giá trị cần tìm (key) với phần tử nằm giữa mảng. Có thể xảy ra 3 trường hợp sau: – Nếu key bằng phần tử giữa ⇒ kết thúc vì tìm thấy. – Nếu key nhỏ hơn phần tử giữa, lặp lại việc tìm key trong nửa đầu của mảng theo phương pháp nhị phân. – Nếu key lớn hơn phần tử giữa, lặp lại việc tìm key trong nửa cuối của mảng theo phương pháp nhị phân.
27. Tìm kiếm nhị phân
28. Tìm kiếm nhị phân • Viết chương trình tạo và nhập dữ liệu cho mảng 1 chiều có 10 phần tử kiểu int có giá trị tăng dần rồi in ra màn hình. Nhận một số từ bàn phím, tìm kiếm nhị phân rồi trả về vị trí của phần tử tìm được. Nếu không tìm thấy thì in ra chuỗi “Không tìm thấy!”.
29. Sắp xếp mảng • Hoán đổi vị trí các phần tử trong mảng để có được một mảng trong đó các phần tử có thứ tự tăng/giảm dần • Có nhiều thuật toán có thể được dùng để sắp xếp: – Chọn (selection sort): Tìm phần tử lớn trong mảng rồi đổi chỗ với phần tử cuối cùng của mảng – Nổi bọt (bubble sort): So sánh một phần tử với phần tử kế nó, nếu lớn hơn thì đổi chỗ – Trộn (Merge sort),
30. Sắp xếp chọn Mảng chưa sắp xếp: int[] myList = {2, 9, 5, 4, 8, 1, 6}; 2, 9, 5, 4, 8, 1, 6 => 2, 6, 5, 4, 8, 1, 9 (Số PT = 7) 2, 6, 5, 4, 8, 1 => 2, 6, 5, 4, 1, 8 (Số PT = 6) 2, 6, 5, 4, 1 => 2, 1, 5, 4, 6 (Số PT = 5) 2, 1, 5, 4 => 2, 1, 4, 5 (Số PT = 4) 2, 1, 4 => 2, 1, 4, (Số PT = 3) 2, 1 => 1, 2 Kết quả: 1, 2, 4, 5, 6, 8, 9
31. Sắp xếp nổi bọt Dãy chưa sắp xếp: int[] myList = {2, 9, 5, 4, 8, 1, 6}; Lần 1: 2, 5, 4, 8, 1, 6, 9 Lần 2: 2, 4, 5, 1, 6, 8, 9 Lần 3: 2, 4, 1, 5, 6, 8, 9 Lần 4: 2, 1, 4, 5, 6, 8, 9 Lần 5: 1, 2, 4, 5, 6, 8, 9 Lần 6: 1, 2, 4, 5, 6, 8, 9
32. Một số ví dụ về mảng Viết chương trình cho phép o Nhập các phần tử mảng từ bàn phím. o In mảng o Sắp xếp mảng tăng dần. o Sắp xếp mảng giảm dần. o Cho biết vị trị và giá trị phần tử lớn nhất, nhỏ nhất trong mảng. o Cho biết mảng có bao nhiêu số nguyên tố, in ra danh sách các số nguyên tố. o Cho biết mảng có bao nhiêu số hoàn hảo, in ra danh sách các số hoàn hảo. o Cho phép thêm vào 1 phần tử ở đầu mảng, cuối mảng và ở vị tí bất kỳ (nhập từ bàn phím). o Cho phép xóa một phần tử ở đầu mảng, cuối mảng và xóa ở vị trí bất kỳ (nhập từ bàn phím).