Cộng đồng chia sẻ tri thức Lib24.vn

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

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 10:08:53


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

Mảng là một thùng chứa có thể chứa một số lượng vật phẩm cố định và các vật phẩm này phải cùng loại. 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.

  1. 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ử.
  2. Chỉ mục - 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ử.

Đại 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.

  1. Chỉ số bắt đầu bằng 0.
  2. Độ dài mảng là 10 có nghĩa là nó có thể lưu trữ 10 phần tử.
  3. 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à 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.

  1. Traverse - in tất cả các phần tử mảng từng cái một.
  2. Chèn - Thêm một phần tử tại chỉ mục đã cho.
  3. Xóa - Xóa một phần tử tại chỉ mục đã cho.
  4. Tìm kiếm - Tìm kiếm một phần tử bằng chỉ mục đã cho hoặc theo giá trị.
  5. Cập nhật - Cập nhật một yếu tố tại chỉ mục đã cho.

Trong C, khi một mảng được khởi tạo với kích thước, thì nó 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ệuGiá trị mặc định
boolsai
than0
int0
Phao nổi0,0
gấp đôi0,0f
khoảng trống
war_t0

Vận hành ngang

Hoạt động này là để đi qua các phần tử của một mảng.

Thí dụ

Theo chương trình đ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 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

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ỉ mục nào của mảng.

Ở đây, chúng ta thấy một triển khai thực tế của hoạt động chèn, trong đó chúng ta thêm 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 -

Bản thử trực tiếp

#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

Cân nhắc 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í 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 thực hiện thuật toán trên -

Bản thử trực tiếp

#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

Cân nhắc 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 -

Bản thử trực tiếp

#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

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

Cân nhắc 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í thứ 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 -

Bản thử trực tiếp

#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

Được cập nhật: 25 tháng 3 lúc 13:12:23 | Lượt xem: 418

Các bài học liên quan