Mảng

Chỉ số phần tử mảng

0

1

2

3

4

7

20

5

9

3

a

Tên mảng

Giá trị

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

b. For

c. While

mảng? a. IF

5. Tìm các số nguyên tố trong mảng trên?

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

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).

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.

[]; hoặc [] ;

hoặc int iarray[];

o Khai báo: o VD: int[] iarray; int[] arrInt3, arrInt4, arrInt5;

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];

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.

int[] arrInt = {1, 2, 3, 5, 6};

o VD: 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];

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.

Chiều dài mảng – số phần tử mảng

int a[]=new int[10]; int b[]={1,3,5};

o Lấy số phần tử mảng ta dùng lệnh tenmang.length o VD: Kết quả:

a.length=10; b.length=3;

Một số ví dụ về mảng

arrInt[i] = i;

System.out.println("This is arrInt[" + i +"]: " +

}

//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 ++) for(i = 0; i < arrInt.length; i ++) arrInt[i]); }

Một số ví dụ về mảng

int nums[] = { 99, -10, 100123, 18, -978, 5623, 463, -9,

if(nums[i] < min) min = nums[i]; if(nums[i] > max) max = nums[i];

int min, max; min = max = nums[0]; for(int i=1; i < 10; i++){ } System.out.println("Min and max: " + min + " " + max);

//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) { 287, 49 }; } }

Một số ví dụ về mảng

//sap xep mang System.out.println("Sap xep cac phan tu cua mang theo chieu tang dan:"); for(i=0;ia[j]){ tg=a[i]; a[i]=a[j]; a[j]=tg; } } System.out.print(a[i] + " "); } } }

import java.util.Scanner; public class BTMang { public static void main(String[] args) { Scanner input =new Scanner(System.in); int [] a = new int[5]; int i, j, tg; //nhap mang System.out.println("Nhap vao cac phan tu cua mang"); for(i=0;i< a.length;i++){ System.out.print("a"+"["+i+"]"+"=" ); a[i]=input.nextInt(); } //in mang System.out.println("Mang vua nhap:"); for(i=0;i

Một số ví dụ về mảng

import java.util.Scanner; public class BTMang2 { public static void Nhap(int[] a){ Scanner input =new Scanner(System.in); System.out.println("Nhap vao cac phan tu cua mang"); for(int i=0;i< a.length;i++){ System.out.print("a"+"["+i+"]"+"=" ); a[i]=input.nextInt(); } } public static void In(int[] a){ System.out.println("Mang vua nhap:"); for(int i=0;i

public static void Sapxep(int[] a){ int i, j, tg; System.out.println("Sap xep cac phan tu cua mang theo chieu tang dan:"); for(i=0;ia[j]){ tg=a[i]; a[i]=a[j]; a[j]=tg; } } System.out.print(a[i] + " "); } } public static void main(String[] args) { ……………………… }

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); } }

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);

Sao chép mảng

System.out.print(" "+d[i]);

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< d.length; i++){ } System.out.print("\n"); System.arraycopy(s,3,d,2,4); System.out.println(" mang d sau"); for(int i =0; i< d.length; i++){ System.out.print(" "+d[i]); } }

import java.util.*; public class randomfile { }

copy 4 phần tử của mảng s, bắt đầu tại vị trí thứ 3 là 7,9,11,13 rồi chép sang mảng d, bắt đầu tại vị trí thứ 2 -> kết quả mảng d: phần tử 6,8,10,12 được thay bằng 7,9,11,13

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;

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

int a[][]=new int[2][3];

dữ liệu>[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)

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;

Độ dài mảng nhiều chiều

int[][] array = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}};

• 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:

– Khi đó:

array.length cho kết quả là 4. array[0].length cho kết quả là 3 ……

Một số ví dụ về mảng

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] + “ “);

public static void main(String[] args) { } System.out.println();

// 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 { } } }

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.

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).

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!”.

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

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.

Tìm kiếm nhị phân

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!”.

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),…

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

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

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).