Cấu trúc dữ liệu Mảng
Mảng (Array) là một trong các cấu trúc dữ liệu quan trọng nhất. Nó có thể lưu trữ 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 sử dụng các mảng để thực hiện các thuật toán của chúng. Sau đây là các thuật ngữ quan trọng để hiểu khái niệm về Array
- Phần tử - Mỗi mục được lưu trữ trong một mảng được gọi là một phần tử.
- Chỉ mục(Index) - Mỗi vị trí của một phần tử trong một mảng có một chỉ mục số, được sử dụng để xác định phần tử.
Cấu trúc dữ liệu mảng
Mảng có thể được khai báo theo nhiều cách khác nhau trong các ngôn ngữ khác nhau. Để minh họa, hãy lấy khai báo mảng C.
Mảng có thể được khai báo theo nhiều cách khác nhau trong các ngôn ngữ khác nhau. Để minh họa, hãy lấy khai báo mảng C.
Theo minh họa ở trên, sau đây là những điểm quan trọng cần được xem xét.
- Chỉ số bắt đầu bằng 0.
- Độ dài mảng là 10 có nghĩa là nó có thể lưu trữ 10 phần tử.
- Mỗi yếu tố có thể được truy cập thông qua chỉ mục của nó. Ví dụ: chúng ta có thể tìm nạp một phần tử ở chỉ số 6 là 27.
Hoạt động cơ bản
Sau đây là các hoạt động cơ bản được hỗ trợ bởi một mảng.
- Duyệt: In tất cả các phần tử mảng theo cách in từng phần tử một.
- Chèn: Thêm một phần tử vào mảng tại chỉ mục đã cho.
- Xóa: Xóa một phần tử từ mảng tại chỉ mục đã cho.
- Tìm kiếm: Tìm kiếm một phần tử bởi sử dụng chỉ mục hay bởi giá trị.
- Cập nhật: Cập nhật giá trị một phần tử tại chỉ mục nào đó.
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:
Loại dữ liệu
Giá trị mặc định
bool - false
Char - 0
int - 0
float - 0.0
double - 0.0f
void
wchar_t - 0
Thao tác duyệt phần tử
Hoạt động này là để duyệt các phần tử của một mảng.
Thí dụ
Chương trình duyệt và in các phần tử của một mảng:
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Khi chúng tôi biên dịch và thực hiện chương trình trên, nó sẽ tạo ra kết quả như sau -
Đầu ra
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Thao tác chèn
Hoạ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.
Thí dụ
Sau đây là việc thực hiện thuật toán trên:
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
n = n + 1;
while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Khi chúng tôi biên dịch và thực hiện chương trình trên, nó sẽ tạo ra kết quả như sau:
Đầu ra
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
Thao tác xóa
Xóa đề cập đến việc loại bỏ một phần tử hiện có khỏi mảng và tổ chức lại tất cả các phần tử của một mảng.
Thuật toán
Giả sử LA là một mảng tuyến tính với N yếu tố và K là một số nguyên dương như vậy mà K <= N . Sau đây là thuật toán để xóa một phần tử có sẵn tại vị trí K của LA
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
Thí dụ
Sau đây là việc thực hiện thuật toán trên:
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Khi chúng tôi biên dịch và thực hiện chương trình trên, nó sẽ tạo ra kết quả như sau:
Đầu ra
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8
Hoạt động tìm kiếm
Bạn có thể thực hiện tìm kiếm một phần tử mảng dựa trên giá trị của nó hoặc chỉ mục của nó.
Thuật toán
Giả sử LA là một mảng tuyến tính với N yếu tố và K là một số nguyên dương như vậy mà K <= N . Sau đây là thuật toán để tìm một phần tử có giá trị ITEM bằng cách sử dụng tìm kiếm tuần tự.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
Thí dụ
Sau đây là việc thực hiện thuật toán trên:
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
printf("Found element %d at position %d\n", item, j+1);
}
Khi chúng tôi biên dịch và thực hiện chương trình trên, nó sẽ tạo ra kết quả như sau:
Đầu ra
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
Hoạt động cập nhật
Hoạt động cập nhật đề cập đến việc cập nhật một phần tử hiện có từ mảng tại một chỉ mục nhất định.
Thuật toán
Giả sử LA là một mảng tuyến tính với N yếu tố và K là một số nguyên dương như vậy mà K <= N . Sau đây là thuật toán để cập nhật một yếu tố có sẵn tại vị trí K của LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop
Thí dụ
Sau đây là việc thực hiện thuật toán trên:
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
Khi chúng tôi biên dịch và thực hiện chương trình trên, nó sẽ tạo ra kết quả như sau:
Đầu ra
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
- Hiếu Kiều -
Bài viết nổi bật
Bài viết nổi bật