Cấu trúc dữ liệu và thuật toán - Mảng

Mảng là một vùng chứa có thể chứa một số mục cố định và những mục này phải cùng loại. Hầu hết các cấu trúc dữ liệu sử dụng mảng để triển khai 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 Mảng.

• Element - Mỗi mục được lưu trong một mảng được gọi là một phần tử.

• Index - Mỗi vị trí của một phần tử trong mảng có một chỉ số số, dùng để xác định phần tử đó.

Biểu diễn 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ỉ mục 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 phần 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à 9.

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.

• Traverse - in lần lượt tất cả các phần tử của mảng.

• Insertion - Thêm một phần tử tại chỉ mục đã cho.

• Deletion - Xóa một phần tử tại chỉ mục đã cho.

• Search - Tìm kiếm một phần tử bằng cách sử dụng chỉ số đã cho hoặc theo giá trị.

• Update - Cập nhật một phần tử tại chỉ mục nhất định.

Trong C, khi một mảng được khởi tạo với kích thước, thì nó sẽ gán các giá trị mặc định cho các phần tử của nó theo thứ tự sau.

Loại dữ liệu	Giá trị mặc định
bool	sai
char	0
int	0
Phao nổi	0,0
gấp đôi	0,0f
vô hiệu
wchar_t	0

Hoạt động theo chiều ngang

Thao tác này là duyệt qua các phần tử của một mảng.

Thí dụ

Chương trình sau đi qua 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 thi chương trình trên, nó tạo ra kết quả 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

Thao tác chèn là chèn một hoặc nhiều phần tử dữ liệu vào một mảng. Dựa trên yêu cầu, một phần tử mới có thể được thêm vào đầu, cuối hoặc bất kỳ chỉ số nhất định nào của mảng.

Ở đây, chúng tôi thấy một triển khai thực tế của hoạt động chèn, nơi chúng tôi thêm dữ liệu vào cuối mảng -

Thí dụ

Sau đây là việc triển khai 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 thi chương trình trên, nó tạo ra kết quả 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

Để biết các biến thể khác của thao tác chèn mảng, hãy nhấp vào đây

Thao tác xóa

Xóa đề cập đến việc xóa 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

Xem xét LA là một mảng tuyến tính với N các yếu tố và K là một số nguyên dương sao cho K<=N. Sau đây là thuật toán xóa một phần tử có sẵn ở vị trí ^thứ 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 triển khai 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 thi chương trình trên, nó tạo ra kết quả 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ị hoặc chỉ mục của nó.

Thuật toán

Xem xét LA là một mảng tuyến tính với N các yếu tố và K là một số nguyên dương sao cho 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 triển khai 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 thi chương trình trên, nó tạo ra kết quả 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

Cập nhật hoạt động

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

Xem xét LA là một mảng tuyến tính với N các yếu tố và K là một số nguyên dương sao cho K<=N. Sau đây là thuật toán để cập nhật một phần tử có sẵn ở vị trí ^thứ K của LA.

1. Start
2. Set LA[K-1] = ITEM
3. Stop

Thí dụ

Sau đây là việc triển khai 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 thi chương trình trên, nó tạo ra kết quả 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