Cấu trúc dữ liệu và giải thuật là gì ? (tt)

Một phần tử có thể được truy cập, chèn thêm hoặc loại bỏ đi khi biết chỉ số của nó.
Khi thực hiện các thao tác trên có thể xảy ra lỗi nếu chỉ số của phần tử không chính xác (Vd, chỉ số âm)

Tham Khảo Thêm: Sinh học 8 Bài 9: Cấu tạo và tính chất của cơ

Các thao tác trên vector

int getAtRank(int r, object &o): Trả lại phần tử có chỉ số r, nhưng không loại bỏ nó
int replaceAtRank(int r, object o, object & o1): Thay thế phần tử có chỉ số r bằng phần tử o và trả lại phần tử bị thay thế
int insertAtRank(int r, object o): Chèn phần tử o vào vị trí r
int removeAtRank(int r, object &o): loại bỏ phần tử tại vị trí r, và trả lại phần tử bị loại bỏ
int size() cho biết kích thước của Vector
int isEmpty() cho biết Vector có rỗng hay không?

Cài đặt vector bằng mảng

Sử dụng mảng V có kích thước N
Một biến n lưu trữ kích thước của vector (số phần tử được lưu trữ)
Phép toán getAtRank(r,o) được thực hiện trong thời gian O(1) bằng việc trả lại V[r]

Các ứng dụng của vector

Ứng dụng trực tiếp
- Lưu trữ tập hợp các đối tượng (cơ sở dữ liệu đơn giản)
Ứng dụng gián tiếp
- Cấu trúc dữ liệu bổ trợ cho các thuật toán
- Thành phần của các cấu trúc dữ liệu khác

b. Danh sách liên kết

Mô hình cấu trúc dữ liệu trừu tượng Linked List là một dãy các vị trí lữu trữ các đối tượng với số lượng tùy ý.
Nó thiết lập một mối quan hệ trước/sau giữa các vị trí
- Danh sách liên kết đơn
- Danh sách liên kết kép

Danh sách liên kết đơn

Các nút (node) được cài đặt bao gồm:
- Phần tử lưu trữ trong nó
- Một liên kết đến nút kế tiếp
Sử dụng môt con trỏ header, trỏ vào node đầu danh sách và con trỏ trailer trỏ vào node cuối danh sách.

Tham Khảo Thêm: Người lái đò sông Đà-Nguyễn Tuân | Tóm tắt, dàn ý và bài văn 2022

Danh sách liên kết kép

Các nút (node) được cài đặt bao gồm:
- Phần tử lưu trữ trong nó
- Một liên kết đến nút trước nó
- Một liên kết đến nút kế tiếp
Có hai nút đặc biệt là trailer và header

c. Stack

Stack là cách tổ chức lưu trữ các đối tượng dưới dạng một danh sách tuyến tính mà việc bổ sung đối tượng và lấy các đối tượng ra được thực hiện ở cùng một đầu của danh sách. Stack được gọi là danh sách kiểu LIFO (Last In First Out – vào sau ra trước)

Các phép toán chính:
- push(Object o): bổ sung đối tượng o vào Stack
- pop(): lấy ra và trả lại phần tử được bổ sung vào cuối cùng của Stack

Một số ứng dụng của Stack

Các ứng dụng trực tiếp
- Lưu lại các trang Web đã thăm trong một trình duyệt
- Thứ tự Undo trong một trình soạn thảo
- Lưu chữ các biến khi một hàm gọi tới hàm khác, và hàm được gọi lại gọi tới hàm khác, và cứ tiếp tục như vậy
Các ứng dụng gián tiếp
- Cấu trúc dữ liệu bổ trợ cho một số thuật toán
- Là một thành phần của những cấu trúc dữ liệu khác

d. Cấu trúc dữ liệu hàng đợi – Queque

Queue là cách tổ chức lưu trữ các đối tượng dưới dạng một danh sách tuyến tính mà việc bổ sung đối tượng được thực hiện ở đầu danh sách và việc lấy đối tượng ra được thực hiện ở cuối của danh sách. Queue còn được gọi là danh sách kiểu FIFO (First In First Out – vào trước ra trước)

Các phép toán chính thực hiện trên queue:
- enqueue(Object o): bổ sung một phần tử o vào cuối của queue.
- dequeue(Object &o): Xóa đi phần tử đầu của queue

Tham Khảo Thêm: Trình bày đặc điểm tự nhiên miền Đông Trung Quốc

Một số ứng dụng của Queque

Các ứng dụng trực tiếp
- Danh sách hàng đợi
- Truy nhập các nguồn dùng chung (ví dụ máy in trong mạng cục bộ)
- Đa lập trình
Các ứng dụng không trực tiếp
- Cấu trúc dữ liệu hỗ trợ cho các thuật toán
- Làm thành phần của các cấu trúc dữ liệu khác

2. Cấu trúc dữ liệu phi tuyến tính – Tree

Có rất nhiều loại cây, và sự phân biệt giữa chúng là dựa vào bậc của từng cây. Trong thực tế cây có rất nhiều ứng dụng

Một số ứng dụng tiêu biểu:

Tổ chức file trong máy tính (được tổ chức theo cấu trúc phân cấp).
Ứng dụng cho các thuật toán tìm kiếm.
Ứng dụng trong các thuật toán tìm đường.

Ví dụ sử dụng cấu trúc dữ liệu dạng cây

Cây mô tả sự phân chia hệ thống files:

Cây nhị phân biểu diễn các biểu thức toán học

Một cây nhị phân biểu diễn một biểu thức. Cây này biểu diễn biểu thức ((((3+1)3/((9-5)+2))-((3(7-4))+6)). Giá trị được kết hợp lại tại nút trong có nhãn “/” là 2.

Trên đây một số khái niệm và định nghĩa cơ bản của Cấu trúc dữ liệu Bài chia sẻ này mình đã tham khảo các tài liệu trên mạng và đúc kết được khi tham gia buổi talk của cô giáo Vũ Thị Thanh Huyền Trưởng bộ môn CNTT Trường Cao đẳng thực hành FPT Polytechnic ĐN. Mong mọi nguời bỏ qua sai xót và góp ý cho mình cải thiện . mình xin dừng bài viết ở đây! Cảm ơn mọi người đã theo dõi.

1. Cấu trúc tuyến tính

a. Kiểu dữ liệu trừu tượng vector