Mảng cấu_trúc dữ_liệu Trong khoa_học máy_tính cấu_trúc dữ_liệu mảng hoặc mảng là một cấu_trúc dữ_liệu bao_gồm một nhóm các phần_tử giá_trị hoặc biến mỗi phần_tử được xác_định ít_nhất bằng một chỉ_số index hoặc khoá key Mảng được lưu theo cách có_thể tính được vị_trí của các phần_tử từ giá_trị của một tuple chỉ_số bằng một biểu_thức toán_học Thí_dụ một mảng có 10 biến_số nguyên với các chỉ_số từ 0 đến 9 có_thể lưu trong 10 word tại địa_chỉ bộ_nhớ 2000 2004 2008 2036 Do_đó phần_tử có chỉ_số i sẽ nằm ở địa_chỉ 2000 4 i Do khái_niệm ma_trận trong toán_học có_thể được biểu_diễn bằng một bảng hai chiều nên đôi_khi mảng hai chiều cũng được gọi là ma_trận Một_số trường_hợp khái_niệm vector được dùng để chỉ mảng mặc_dù bộ tuple là khái_niệm chính_xác hơn về mặt toán_học Mảng thường được dùng để hiện_thực các bảng nhất_là bảng tìm_kiếm Từ bảng đôi_khi có cùng nghĩa với mảng Mảng là một trong những cấu_trúc dữ_liệu cũ và quan_trọng nhất và hầu_hết các chương_trình đều dùng nó Các cấu_trúc dữ_liệu khác cũng được hiện_thực bằng mảng thí_dụ như danh_sách hoặc chuỗi Nó rất hiệu_quả trong việc tận_dụng cách đánh địa_chỉ trên máy_tính Trong hầu_hết các máy_tính hiện_đại và các thiết_bị lưu_trữ ngoài bộ_nhớ là chuỗi một_chiều các word và chỉ_số của nó chính là địa_chỉ Bộ_xử_lý đặc_biệt là bộ_xử_lý vector thường tối_ưu_hoá các tác_vụ trên mảng Sự hữu_dụng của mảng nằm ở chỗ chỉ_số của các phần_tử có_thể tính_toán được vào lúc chương_trình đang chạy Tính_năng này cho_phép một lệnh lặp có_thể xử_lý một số_lượng lớn các phần_tử trong mảng Do_đó các phần_tử trong cấu_trúc mảng cần phải có cùng kích_thước và cùng kiểu dữ_liệu Tập_hợp các bộ chỉ_số và địa_chỉ của các phần_tử cũng như công_thức tính địa_chỉ các phần_tử thường nhưng không phải luôn_luôn cố_định khi mảng đang được sử_dụng Khái_niệm mảng thường dùng có nghĩa là kiểu dữ_liệu mảng được cung_cấp bởi hầu_hết các ngôn_ngữ_lập_trình cấp cao nó bao_gồm tập_hợp các giá_trị hoặc biến có_thể lựa_chọn bằng một hoặc nhiều chỉ_số được tính_toán trong lúc chạy Kiểu dữ_liệu mảng thường được hiện_thực bằng cấu_trúc mảng tuy_nhiên một_số ngôn_ngữ_lập_trình có thể_hiện_thực bằng bảng băm cây tìm_kiếm hoặc các cấu_trúc dữ_liệu khác Khi mô_tả các giải_thuật khái_niệm này cũng được dùng để chỉ mảng liên_kết một mô_hình lý_thuyết khoa_học máy_tính kiểu dữ_liệu trừu_tượng hay ADT để sử_dụng các tính_chất thiết_yếu của mảng Lịch_sử Các máy_tính kỹ_thuật_số đầu_tiên dùng chương_trình được viết bằng ngôn_ngữ_máy để tạo và truy_xuất cấu_trúc mảng cho các bảng dữ_liệu vector và tính_toán ma_trận và các mục_đích khác Von_Neumann viết chương_trình sắp_xếp mảng sắp_xếp trộn vào năm 1945 khi đang xây_dựng chương_trình lưu_trữ máy_tính đầu_tiên Đánh chỉ_số cho mảng ban_đầu được dùng trong mã tự sửa_đổi và sau đó dùng trong thanh ghi chỉ_số và truy_xuất giáng tiếp Một_số máy_tính lớn thiết_kế vào thập_niên 1960 như Burroughs B5000 và hậu_duệ của nó có những lệnh đặc_biệt để đánh chỉ_số cho mảng bao_gồm kiểm_tra biên của chỉ_số Hợp ngữ nói_chung không có hỗ_trợ đặc_biệt cho mảng ngoài việc dùng các hỗ_trợ từ phần_cứng Ngôn_ngữ_lập_trình cấp cao đầu_tiên bao_gồm FORTRAN 1957 COBOL 1960 và ALGOL 60 1960 có hỗ_trợ mảng nhiều chiều và sau đó là C 1972 Trong C 1983 có các class template cho mảng nhiều chiều với số_lượng chiều là cố_định trong lúc chương_trình đang chạy cũng như các mảng có số chiều thay_đổi được khi chương_trình đang chạy Ứng_dụng Mảng được dùng để hiện_thực các vector và các ma_trận cũng như các loại bảng chữ_nhật Nhiều cơ_sở_dữ_liệu từ nhỏ đến lớn chứa hoặc bao_gồm các mảng một_chiều mà các phần_tử là các bản ghi Mảng cũng được dùng để hiện_thực các cấu_trúc dữ_liệu khác như đống bảng băm hàng đợi hai đầu_hàng đợi ngăn xếp xâu và VList_Một hoặc nhiều mảng lớn đôi_khi được dùng để giả_lập cấp_phát bộ_nhớ_động trong chương_trình nhất là cấp_phát memory pool Mảng có_thể dùng để xác_định một phần hoặc toàn_bộ luồng thực_thi của chương_trình nhiều câu_lệnh codice _ 1 như là một_cách thu gọn nếu không sẽ lặp lại Trong trường_hợp này nó được biết như là bảng điều_khiển và được dùng kết_hợp với mục_tiêu xây_dựng trình thông_dịch chương_trình có luồng thực_thi thay_đổi tuỳ theo giá_trị trong mảng Mảng có_thể chứ các con_trỏ tới chương_trình con hoặc số chương_trình con tương_ứng có_thể được xử_lý bằng lệnh SWITCH để chỉnh hướng thực_thi của chương_trình Định_danh cho phần_tử và công_thức tính địa_chỉ Mảng một_chiều Khi các đối_tượng dữ_liệu được lưu_trữ trong một mảng các đối_tượng riêng_lẻ được chon thông_qua một chỉ_số index thường là một biến_số nguyên không âm Các chỉ_số này còn được gọi là chỉ_số dưới subscript Một chỉ_số ánh xạ giá_trị của mảng đến một đối_tượng được lưu_trữ Có ba cách để đánh chỉ_số cho các phần_tử trong mảng BULLET 0 đánh chỉ_số từ không BULLET 1 đánh chỉ_số từ một BULLET n đánh chỉ_số từ n Hiệu_quả Sự hiệu_quả so với các cấu_trúc dữ_liệu khác So với danh_sách liên_kết việc truy_cập đến một phần_tử trong mảng nhanh hơn với độ phức_tạp là O 1 Tuy_nhiên để xoá một phần_tử không phải là phần_tử cuối thì sử_dụng cấu_trúc mảng không hiệu_quả Bởi_vì công_việc này cần tốn thời_gian cho việc dịch_chuyển các phần_tử còn lại lấp vào chỗ trống của mảng Ý_nghĩa của số chiều Số chiều của mảng tương_ứng với số chỉ_số index cần để xác_định được phần_tử đó Ví_dụ Trong mảng một_chiều a N với N là số phần_tử a i biểu_diễn phần_tử thứ i i N của mảng Trong mảng hai chiều a N M với N M là giới_hạn của mỗi chiều tương_ứng a i j biểu_diễn phần_tử ở hàng i cột j của mảng
Mảng ( cấu_trúc dữ_liệu )