Mảng tĩnh

Mảng một chiều

Mảng là một kiểu dữ liệu chứa các phần tử cùng loại được chứa trong một khối bộ nhớ liên tiếp. Trong một mảng A có kích thước N , mỗi vị trí bộ nhớ được đánh một chỉ số duy nhất i với điều kiện 0<= i <N, tức là chỉ số của mảng luôn luôn được bắt đầu từ 0 và phải nhỏ hơn kích thước của mảng. Để truy cập đến mỗi phần tử của mảng ta chỉ cần biết chỉ số của chúng, khi ta viết A[i] có nghĩa là ta đang truy cập tới phần tử thứ i của mảng A.

Ví dụ:

Ta có mảng A với kích thước là 8 phần tử, phần tử đầu tiên của mảng được bắt đầu từ vị trí ô nhớ có địa chỉ là 1200

Địa chỉ

Giá trị

Phần tử mảng

1200

f

A[0]

1201

h

A[1]

1202

h

A[2]

1203

a

A[3]

1204

y

A[4]

1205

t

A[5]

1206

I

A[6]

1207

a

A[7]

 

Chú ý:

  • Kích thước của một mảng phải được khai báo trước khi ta chèn dữ liệu vào mảng đó.

  • Các phần tử trong mảng phải có cùng kiểu dữ liệu.

  • Trong C++ kích thước của một mảng tĩnh sau khi khai báo là cố định và không thể thay đổi được, vì vậy ta không thể khai báo kích thước của một mảng tĩnh là biến được.

Ví dụ:

Trong trường hợp sau trình biên dịch sẽ báo lỗi.

int N = 100;

int A[N];

Nhưng đoạn mã sau hoàn toàn có thể chạy được.


#define N 100

int A[N];

Sự khác nhau ở đây là do tính chất của C++. Với trường hợp thứ nhất, giá trị của N là không xác định từ thời điểm biên dịch tới thời điểm chạy runtime. Do vậy tại thời điểm biên dịch trình biên dịch sẽ báo lỗi do kích thước của mảng không được chỉ rõ.

Ở trường hợp thứ 2 do chúng ta sử dụng một kỹ thuật đặc biệt trong lập trình đó là tiền xử lý. Khi này tại thời điểm biên dịch chương trình, giá trị của N đã được xác định, đồng nghĩa với việc trình biên dịch đã biết được kích thước của mảng nên lỗi biên dịch sẽ không xảy ra ở đây.

Một số điểm cần chú ý khi làm việc với mảng:

Coi kích thước của mảng là N.

Thời gian truy cập tới một phần tử của mảng:

  • O(1) - Điều này là có thể vì tất cả các phần tử của mảng được chứa trong các vị trí ô nhớ liên tiếp.

Thời gian tìm kiếm:

  • O(N) trong trường hợp tìm kiếm tuần tự (Sequential Search).

  • O(log N) cho trường hợp tìm kiếm nhị phân (Binary Search) và nếu mảng đã được sắp xếp từ trước.

Thời gian chèn dữ liệu vào mảng:

  • O(N) - Trường hợp xấu nhất xảy ra khi ta muốn chèn dữ liệu vào vị trí đầu tiên của mảng và phải thực hiện dịch toàn bộ phần tử tiếp theo của mảng, trường hợp tốt nhất xảy ra khi ta muốn chèn một phần tử vào vị trí cuối của phần dữ liệu trong mảng.

Thời gian cần thiết để xóa một phần tử trong mảng:

  • O(N) Xảy ra khi ta muốn xóa phần tử đầu tiên của mảng và đòi hỏi ta phải thực hiện dịch tất các các phần tử còn lại của mảng về vị trí có chỉ số nhỏ hơn chỉ số hiện tại của chúng 1 đơn vị, đây cũng là trường hợp xấu nhất.

 Mảng hai chiều

Mảng hai chiều có đầy đủ các tính chất của bảng một chiều như:

  • Dữ liệu được điền trong một khối các ô nhớ liên tiếp.

  • Các phần tử trong cùng một mảng phải có cùng kiểu dữ liệu.

  • Kích thước của mảng hai chiều phải được khai báo trước khi ta chèn dữ liệu vào bảng đó (chính xác hơn, kích thước của mảng phải được xác định trong thời gian biên dịch chương trình).

Mô hình biểu diễm của mảng hai chiều A[6][5] như sau:

 
 

Cột 0

Cột 1

Cột 2

Cột 3

Cột 4

Hàng 0

A[0][0]

A[0][1]

A[0][2]

A[0][3]

A[0][4]

Hàng 1

A[1][0]

A[1][1]

A[1][2]

A[1][3]

A[1][4]

Hàng 2

A[2][0]

A[2][1]

A[2][2]

A[2][3]

A[2][4]

Hàng 3

A[3][0]

A[3][1]

A[3][2]

A[3][3]

A[3][4]

Hàng 4

A[4][0]

A[4][1]

A[4][2]

A[4][3]

A[4][4]

Hàng 5

A[5][0]

A[5][1]

A[5][2]

A[5][3]

A[5][4]

 

Độ phức tạp thời gian khi ta thao tác trên mảng hai chiều cũng giống như khi ta thao tác trên mảng một chiều.

Các cách khai báo, khởi tạo mảng

Ta có hai cách khởi tạo mảng đó là khởi tạo ngay trong lúc khai báo hoặc khởi tạo sau khi đã khai báo mảng.

Với mảng một chiều:

Khởi tạo ngay khi khai báo:

        int A[4] = {5,4,6,7}; // A[0] = 5, A[1] = 4, A[2] = 6, A[3] = 7;

        int A[4] = {5,4};       // A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 0;

        int A[4] = {};           // A[0] = 0, A[1] = 0, A[2] = 0, A[3] = 0;

        int A[] = {5,4,6,7};   // A[0] = 5, A[1] = 4, A[2] = 6, A[3] = 7;

        int A[] = {};              // Lỗi biên dịch, giống trường hợp khai báo int A[0];

Khởi tạo sau khi khai báo:

        int A[4];

        A[0] = 5;

        A[1] = 4;

        A[2] = 6;

        A[3] = 7;

Với mảng hai chiều:

Khởi tạo ngay khi khai báo:

int A[3][4] = {

        {0, 2, 3, 5},  /* Hàng có chỉ sô 0 */

       {0, 9, 1, 4},  /* Hàng có chỉ sô 1 */

       {0, 2, 7, 5}   /* Hàng có chỉ sô 2 */

};

Ngoài cách khởi tạo như trên ta còn có cách làm tương đương như sau.

        int A[3][4] = {0,2,3,5,0,9,1,4,0,2,7,5};

Khởi tạo sau khi khai báo:

        int A[2][2];

        A[0][0] = 1;

        A[0][1] = 1;

        A[1][0] = 2;

        A[1][1] = 3;

Tổng kết:

Trong bài học này có đề cập tới một số nội dụng về độ phức tạp thời gian của từng phép toán, ngoài ra còn có khái niệm và độ phức tạp về bộ nhớ của các phép toán. bạn có thể tìm hiểu thêm về các vấn đề này tại đây.

Để hiểu hơn về cách làm việc với mảng các bạn cũng có thể tham khảo thêm các dạng bài tập liên quan tới mảng bao gồm:

  • In mảng một chiều theo thức tự đảo ngược của các phần tử.

  • <TO DO list - còn nhiều nữa tại đây>.

** Nếu bạn muốn viết các nội dung đặt biệt thì hãy làm theo hướng dẫn sau

Xem thêm 10 bình luận
Viết blog mới của bạn
Báo lỗi trang
Đang tải