VietTuts

Tự Học Lập Trình Online

  • Home
  • Java
  • Servlet
  • JSP
  • Struts2
  • Hibernate
  • Spring
  • MyBatis
  • Java WS
  • C
  • C++
  • C#
  • Python
  • PHP
  • Excel
  • VBA
  • Web
    • JavaScript
    • JQUERY
    • JSON
    • AJAX
    • CSS
    • HTML
    • HTML5
    • Node.js
    • Angular 7
  • SQL
    • MySQL
    • SQL Server
  • Misc
    • Eclipse
    • Phần mềm tiện ích
    • Cấu trúc DL&GT
    • Selenium Test

Cấu Trúc Dữ Liệu & Giải Thuật

Tổng quan về cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu là gì? Giải thuật là gì? Cài đặt môi trường

Giải Thuật

Giải thuật tiệm cận Giải thuật tham lam Giải thuật chia để trị Giải thuật qui hoạch động

Cấu Trúc Dữ Liệu Mảng

Cấu trúc dữ liệu mảng

Danh sách liên kết - Linked list

Cấu trúc dữ liệu Linked List Cấu trúc dữ Doubly Linked List Cấu trúc dữ Circular Linked List

Ngăn Xếp & Hàng Đợi

Cấu trúc dữ liệu ngăn xếp - Stack Cấu trúc dữ hàng dợi - Queue

Một Số Giải Thuật Tìm Kiếm

Tìm kiếm tuyến tính - Linear Search Tìm kiếm nhị phân - Binary Search Tìm kiếm nội suy - Interpolation Search Cấu trúc dữ liệu Hash Table

Một Số Giải Thuật Sắp Xếp

Giải thuật sắp xếp Sắp xếp nổi bọt - Bubble Sort Sắp xếp chèn - Insertion Sort Sắp xếp chọn - Selection Sort Sắp xếp trộn - Merge Sort Sắp xếp nhanh - Quick Sort Giải thuật Shell Sort Giải thuật quay lui - Back Tracking

Cấu Trúc Dữ Liệu Đồ Thị (Graph)

Cấu trúc dữ liệu đồ thị Tìm kiếm theo chiều sâu - Depth First Search Tìm kiếm theo chiều sâu - Breadth First Search
1 / 3
❮ ❯

Cấu trúc dữ liệu mảng


Giải thuật qui hoạch động (Dynamic Programming)
Cấu trúc dữ liệu danh sách liên kết (Linked List)

Nội dung chính

  • Cấu trúc dữ liệu mảng là gì?
    • Ưu điểm của mảng :
    • Nhược điểm
  • Mảng động
  • Biểu diễn Cấu trúc dữ liệu mảng
  • Phép toán cơ bản được hỗ trợ bởi mảng
  • Hoạt động chèn phần tử vào mảng
    • Ví dụ
    • Giải thuật
  • Hoạt động xóa phần tử từ mảng
    • Ví dụ
    • Giải thuật
  • Hoạt động tìm kiếm
    • Ví dụ
    • Giải thuật
  • Hoạt động cập nhật (Hoạt động update)
    • Giải thuật

Cấu trúc dữ liệu mảng là gì?

Mảng (Array) là một trong các cấu trúc dữ liệu quan trọng nhất. Mảng có thể lưu giữ 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 đều sử dụng mảng để triển khai giải thuật. Dưới đây là các khái niệm quan trọng liên quan tới Mảng.

  • Phần tử: Mỗi mục được lưu giữ 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 để nhận diện phần tử.

Mảng gồm các bản ghi có kiểu giống nhau, có kích thước cố định, mỗi phần tử được xác định bởi chỉ số

Mảng là cấu trúc dữ liệu được cấp phát lien tục cơ bản

Ưu điểm của mảng :

Truy câp phàn tử vơi thời gian hằng số O(1)

Sử dụng bộ nhớ hiệu quả

Tính cục bộ về bộ nhớ

Nhược điểm

Không thể thay đổi kích thước của mảng khi chương trình dang thực hiện


Mảng động

Mảng động (dynamic aray) : cấp phát bộ nhớ cho mảng một cách động trong quá trình chạy chương trình trong C là malloc và calloc, trong C++ là new

Sử dụng mảng động ta bắt đầu với mảng có 1 phàn tử, khi số lượng phàn tử vượt qua khả năng của ảng thì ta gấp đôi kích thước mảng cuc và copy phàn tử mảng cũ vào nửa đầu của mảng mới

Ưu điểm : tránh lãng phí bộ nhớ khi phải khai báo mảng có kích thước lớn ngay từ đầu

Nhược điểm: + phải thực hiện them thao tác copy phần tử mỗi khi thay đổi kích thước. + một số thời gian thực hiện thao tác không còn là hằng số nữa


Biểu diễn Cấu trúc dữ liệu mảng

Mảng có thể được khai báo theo nhiều cách đa dạng trong các ngôn ngữ lập trình. Để minh họa, chúng ta sử dụng phép khai báo mảng trong ngôn ngữ C:

Cấu trúc dữ liệu mảng

Hình minh họa phần tử và chỉ mục:

Cấu trúc dữ liệu mảng

Dưới đây là một số điểm cần ghi nhớ về cấu trúc dữ liệu mảng:

  • Chỉ mục bắt đầu với 0.

  • Độ dài mảng là 10, nghĩa là mảng có thể lưu giữ 10 phần tử.

  • Mỗi phần tử đều có thể được truy cập thông qua chỉ mục của phần tử đó. Ví dụ, chúng ta có thể lấy giá trị của phần tử tại chỉ mục 6 là 27.


Phép toán cơ bản được hỗ trợ bởi mảng

Dưới đâ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:

Kiểu dữ liệu Giá trị mặc định
bool false
char 0
int 0
float 0.0
double 0.0f
void
wchar_t 0

Hoạt động chèn phần tử vào mảng

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.

Ví dụ

Giả sử LA là một mảng tuyến tính không có thứ tự có N phần tử và K là một số nguyên dương thỏa mãn K <= N. Dưới đây là giải thuật chèn phần tử A vào vị trí thứ K của mảng LA.

Giải thuật

Output:

1. Bắt đầu
2. Gán J=N
3. Gán N = N+1
4. Lặp lại bước 5 và 6 khi J >= K
5. Gán LA[J+1] = LA[J]
6. Gán J = J-1
7. Gán LA[K] = ITEM
8. Kết thúc

Sau đây là code đầy đủ của giải thuật trên trong ngôn ngữ C:


#include <stdio.h>
main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;
   
   printf("Danh sach phan tu trong mang ban dau:\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("Danh sach phan tu cua mang sau hoat dong chen:\n");
 
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

Kết quả:

Chèn phần tử vào mảng trong C

Hoạt động xóa phần tử từ mảng

Hoạt động xóa là xóa một phần tử đang tồn tại từ một mảng và tổ chức lại các phần tử còn lại trong mảng đó.

Ví dụ

Giả sử LA là một mảng tuyến tính có N phần tử và K là số nguyên dương thỏa mãn K <= N. Dưới đây là thuật toán để xóa một phần tử có trong mảng LA tại vị trí K.

Giải thuật

Output:

1. Bắt đầu
2. Gán J=K
3. Lặp lại bước 4 và 5 trong khi J < N
4. Gán LA[J-1] = LA[J]
5. Gán J = J+1
6. Gán N = N-1
7. Kết thúc

Sau đây là code đầy đủ của giải thuật trên trong ngôn ngữ C:


#include <stdio.h>
main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5;
   int i, j;
   
   printf("Danh sach phan tu trong mang ban dau:\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("Danh sach phan tu trong mang sau hoat dong xoa:\n");
 
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

Kết quả:

Xóa phần tử từ mảng trong C

Hoạt động tìm kiếm

Bạn có thể thực hiện hoạt động tìm kiếm phần tử trong mảng dựa vào giá trị hay chỉ mục của phần tử đó.

Ví dụ

Giả sử LA là một mảng tuyến tính có N phần tử và K là số nguyên dương thỏa mãn K <= N. Dưới đây là giải thuật để tìm một phần tử ITEM bởi sử dụng phương pháp tìm kiếm tuần tự (hay tìm kiếm tuyến tính).

Giải thuật

Output:

1. Bắt đầu
2. Gán J=0
3. Lặp lại bước 4 và 5 khi J < N
4. Nếu LA[J] là bằng ITEM THÌ TỚI BƯỚC 6
5. Gán J = J +1
6. In giá trị J, ITEM
7. Kết thúc

Sau đây là code đầy đủ của giải thuật trên trong ngôn ngữ C:


#include <stdio.h>
main() {
   int LA[] = {1,3,5,7,8};
   int item = 5, n = 5;
   int i = 0, j = 0;
   
   printf("Danh sach phan tu trong mang ban dau:\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("Tim thay phan tu %d tai vi tri %d\n", item, j+1);
}

Kết quả:

Tìm kiếm phần tử trong mảng trong C

Hoạt động cập nhật (Hoạt động update)

Hoạt động cập nhật là update giá trị của phần tử đang tồn tại trong mảng tại chỉ mục đã cho.

Giải thuật

Giả sử LA là một mảng tuyến tính có N phần tử và K là số nguyên dương thỏa mãn K <= N. Dưới đây là giải thuật để update giá trị phần tử tại vị trí K của mảng LA.

Output:

1. Bắt đầu
2. Thiết lập LA[K-1] = ITEM
3. Kết thúc

Sau đây là code đầy đủ của giải thuật trên trong ngôn ngữ C:


#include <stdio.h>
main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5, item = 10;
   int i, j;
   
   printf("Danh sach phan tu trong mang ban dau:\n");
 
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
    
   LA[k-1] = item;   printf("Danh sach phan tu trong mang sau hoat dong update:\n");
 
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

Kết quả:

Cập nhật mảng trong C
Giải thuật qui hoạch động (Dynamic Programming)
Cấu trúc dữ liệu danh sách liên kết (Linked List)

Recent Updates

Xuất dữ liệu ra màn hình console trong JavaCài đặt môi trường JavaJava Swing - Bài tập quản lý sinh viên trong javaLinkedList trong javaArrayList trong javaBài tập java có lời giảiXác thực dữ liệu (Data Validation) trong ExcelSắp xếp dữ liệu trong ExcelLọc dữ liệu (Data Filter) trong ExcelHeader và Footer trong ExcelMàu văn bản và màu nền (background) trong ExcelCăn chỉnh văn bản trong ExcelSắp Tết 2026 Rồi! - Còn bao nhiêu ngày nữa là đến tết 2026?

VietTuts on facebook

Học Lập Trình Online Miễn Phí - VietTuts.Vn
Danh Sách Bài Học

Học Java | Hibernate | Spring
Học Excel | Excel VBA
Học Servlet | JSP | Struts2
Học C | C++ | C#
Học Python
Học SQL

Bài Tập Có Lời Giải

Bài tập Java
Bài tập C
Bài tập C++
Bài tập C#
Bài tập Python
Ví dụ Excel VBA

Câu Hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java
25 câu hỏi phỏng vấn servlet
75 câu hỏi phỏng vấn jsp
52 câu hỏi phỏng vấn Hibernate
70 câu hỏi phỏng vấn Spring
57 câu hỏi phỏng vấn SQL

Scroll back to top

Copyright © 2016 VietTuts.Vn all rights reserved. | Liên hệ | Chính sách - riêng tư | sitemap.html | sitemap_index.xml