Mảng la gì
Mảng (Array) là một trong các cấu trúc dữ liệu quan trọng nhất. Mảng có thể lưu giữ một số phần tử cố định và các phần tử này nền có cùng kiểu. Hầu hết các cấu trúc dữ liệu đều sử dụng mảng để triển khai giải thuật. Dưới đây là các khái niệm quan trọng liên quan tới Mảng. Show
Mảng gồm các bản ghi có kiểu giống nhau, có kích thước cố định, mỗi phần tử được xác định bởi chỉ số Mảng là cấu trúc dữ liệu được cấp phát lien tục cơ bản Ưu điểm của mảng :Truy câp phàn tử vơi thời gian hằng số O(1) Sử dụng bộ nhớ hiệu quả Tính cục bộ về bộ nhớ Nhược điểmKhông thể thay đổi kích thước của mảng khi chương trình dang thực hiện Mảng độngMảng động (dynamic aray) : cấp phát bộ nhớ cho mảng một cách động trong quá trình chạy chương trình trong C là malloc và calloc, trong C++ là new Sử dụng mảng động ta bắt đầu với mảng có 1 phàn tử, khi số lượng phàn tử vượt qua khả năng của ảng thì ta gấp đôi kích thước mảng cuc và copy phàn tử mảng cũ vào nửa đầu của mảng mới Ưu điểm : tránh lãng phí bộ nhớ khi phải khai báo mảng có kích thước lớn ngay từ đầu Nhược điểm: + phải thực hiện them thao tác copy phần tử mỗi khi thay đổi kích thước. + một số thời gian thực hiện thao tác không còn là hằng số nữa Biểu diễn Cấu trúc dữ liệu mảngMảng có thể được khai báo theo nhiều cách đa dạng trong các ngôn ngữ lập trình. Để minh họa, chúng ta sử dụng phép khai báo mảng trong ngôn ngữ C: Hình minh họa phần tử và chỉ mục: Dưới đây là một số điểm cần ghi nhớ về cấu trúc dữ liệu mảng:
Phép toán cơ bản được hỗ trợ bởi mảngDưới đây là các hoạt động cơ bản được hỗ trợ bởi một mảng:
Trong ngôn ngữ C, khi một mảng được khởi tạo với kích cỡ ban đầu, thì nó gán các giá trị mặc định cho các phần tử của mảng theo thứ tự sau: Kiểu dữ liệuGiá trị mặc địnhboolfalsechar0int0float0.0double0.0fvoidwchar_t0Hoạt động chèn phần tử vào mảngHoạt động chèn là để chèn một hoặc nhiều phần tử dữ liệu vào trong một mảng. Tùy theo yêu cầu, phần tử mới có thể được chèn vào vị trí đầu, vị trí cuối hoặc bất kỳ vị trí chỉ mục đã cho nào của mảng. Phần tiếp theo chúng ta sẽ cùng triển khai hoạt động chèn trong một ví dụ thực. Trong ví dụ này, chúng ta sẽ chèn dữ liệu vào cuối mảng. Ví dụGiả sử LA là một mảng tuyến tính có N phần tử và K là số nguyên dương thỏa mãn K <= N. Dưới đây là giải thuật để update giá trị phần tử tại vị trí K của mảng LA. Lưu ý: vì số phần tử của mảng là 1 số cố định nên sau khi đã khai báo mảng ta không thể thêm 1 phần tử mới hay xóa phần tử hiện tại đi nhé. Cách khai báo mảng một chiềuDựa theo định nghĩa về mảng, để khai báo một mảng ta cần có:
Giả sử ta cần khai báo 1 mảng có kiểu dữ liệu số nguyên, gồm 5 phần tử, có tên là arr Ở Java ta có 2 cách khai báo:
int[] arr = {1,2,3,4,5}; // theo chuẩn thì người ta thường dùng cách kb này hoặc int arr[] = {1, 2, 3, 4 ,5}; Cách này dùng khi ta đã biết mảng đó có chính xác 5 phần tử là: 1, 2, 3, 4, 5 Ví dụ khác: Mảng kiểu chuỗi: String arr = {“a”, “b”, “c”};
int[] arr = new int[5]; Cách này dùng nếu ta không biết trước mảng số nguyên này gồm những số nào. Ta có thể xem được số phần tử của mảng bằng cách: caodangytehadong.edu.vnth Cách truy xuất/tham chiếu đến một phần tử của mảng một chiềuNhững phần tử được sắp xếp trong mảng được đánh số theo số thứ tự (index). Phần tử đầu tiên của mảng có index là 0 Related Articles
Phần tử cuối cùng của mảng có index là số phần tử mảng – 1 Với mảng số nguyên {1, 2, 3, 4, 5}, ta có: arr[0] = 1; arr[1] = 2; arr[2] = 3; arr[3] =4; arr[4] =5; Không có phần tử nào có index nhỏ hơn 0 hoặc lớn hơn 4 cả, nếu ta cố tình tham chiếu đến, chương trình sẽ báo lỗi ( ném ra ngoại lệ caodangytehadong.edu.vnyIndexOutOfBoundsException), lỗi này thường gặp khi chúng ta làm việc với kiểu mảng hay danh sách. Tổng quát, để tham chiếu đến 1 phần tử thứ i của mảng: arr[i] với 0 <= i <= caodangytehadong.edu.vn – 1 hoặc (0 <= i < caodangytehadong.edu.vn ) Liệt kê các phần tử của mảng một chiều bằng vòng lặp cơ bảnBởi vì ta luôn biết số phần tử của mảng rồi nên thường dùng vòng lặp for có sử dụng index để liệt kê: hoặc ( ở đây i đóng vai trò là index của mảng arr nên 0 <= i < số phần tử của mảng ) Có 1 cách khác sử dụng vòng for để liệt kê phần tử của mảng mà ko sử dụng index: Đó là những gì về mảng một chiều mà mình muốn giới thiệu đến các bạn. Đến đây bài viết cũng đã khá dài rồi, mình biết mấy bạn không thích dài nên thôi mình sẽ cố gắng viết ngắn gọn, đủ ý nhất có thể. Hẹn gặp lại các bạn ở phần sau: Kiểu Khai Báo Mảng ở Java – Mảng hai chiều và các mảng đa chiều khác |