Môn Cấu Trúc Dữ Liệu Và Giải Thuật (Phần 1), Cấu Trúc Dữ Liệu Và Giải Thuật Là Gì

Cấu trúc dữ liệu
Vector
List
Stack
Queue
Tree
Hash
Table
Dictionary…

Cấu trúc dữ liệu (Data Structure) là gì ?

Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả.

Bạn đang xem: Môn cấu trúc dữ liệu và giải thuật

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

Cấu trúc tuyến tính là một cấu trúc trong đó các phần tử nằm trên một đường không có nhánh, và các phần tử liên tiếp nhau

Một số ví dụ:Danh sách (lists)Vector, chuỗi (vectors, sequences)Danh sách kiểu ngăn xếp, danh sách kiểu hàng đợi (stack, queue)

*

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

Kiểu dữ liệu trừu tượng Vector là sự mở rộng của khái niệm mảng. Vector là một mảng lưu trữ một dãy các đối tượng với số lượng tùy ý

*

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)Các thao tác trên vectorint get
At
Rank
(int r, object &o): Trả lại phần tử có chỉ số r, nhưng không loại bỏ nóint replace
At
Rank
(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 insert
At
Rank
(int r, object o): Chèn phần tử o vào vị trí rint remove
At
Rank
(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 Vectorint is
Empty
() 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 NMộ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 get
At
Rank
(r,o) được thực hiện trong thời gian O(1) bằng việc trả lại V

*

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 đơnDanh 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.

*

*

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à trailerheader

*

*

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 Stackpop(): 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.

Xem thêm: Nước Hoa Lancome Miracle 100Ml, Lancome Miracle Edp 100Ml New 2020

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
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.
*

Lớp 1

Tài liệu Giáo viên

Lớp 2

Lớp 2 - Kết nối tri thức

Lớp 2 - Chân trời sáng tạo

Lớp 2 - Cánh diều

Tài liệu Giáo viên

Lớp 3

Lớp 3 - Kết nối tri thức

Lớp 3 - Chân trời sáng tạo

Lớp 3 - Cánh diều

Tài liệu Giáo viên

Lớp 4

Sách giáo khoa

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 5

Sách giáo khoa

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 6

Lớp 6 - Kết nối tri thức

Lớp 6 - Chân trời sáng tạo

Lớp 6 - Cánh diều

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 7

Lớp 7 - Kết nối tri thức

Lớp 7 - Chân trời sáng tạo

Lớp 7 - Cánh diều

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 8

Sách giáo khoa

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 9

Sách giáo khoa

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 10

Lớp 10 - Kết nối tri thức

Lớp 10 - Chân trời sáng tạo

Lớp 10 - Cánh diều

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 11

Sách giáo khoa

Sách/Vở bài tập

Tài liệu Giáo viên

Lớp 12

Sách giáo khoa

Sách/Vở bài tập

Tài liệu Giáo viên

Giáo viên

Lớp 1

Lớp 2

Lớp 3

Lớp 4

Lớp 5

Lớp 6

Lớp 7

Lớp 8

Lớp 9

Lớp 10

Lớp 11

Lớp 12


*

Cấu trúc dữ liệu và giải thuật
Một số khái niệm về Giải thuật Cấu trúc dữ liệu mảng (Array)Danh sách liên kết - Linked Lists
Ngăn xếp & Hàng đợi
Một số Giải thuật tìm kiếm
Một số Giải thuật sắp xếp
Cấu trúc dữ liệu đồ thị (Graph)Cấu trúc dữ liệu cây
Đệ qui (Recursion)Tài liệu tham khảo

Với các sinh viên chuyên nghành tin học thì cụm từ Cấu trúc dữ liệu (Data Structure) không còn là xa lạ. Đây là một môn học bắt buộc và sẽ là thực sự khó cho bất kỳ sinh viên nào nếu không có sự chuẩn bị kỹ lưỡng và dành cách tiếp cận tích cực cho môn học này. Vậy Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả.

Dưới đây là danh sách các bài hướng dẫn trong loạt bài Cấu trúc dữ liệu và Giải thuật:

Mục lục Cấu trúc dữ liệu và giải thuật

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

Một số khái niệm về Giải thuật


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

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

Ngăn xếp & Hàng đợi

Một số Giải thuật tìm kiếm


Một số Giải thuật sắp xếp

Cấu trúc dữ liệu đồ thị (Graph)

Cấu trúc dữ liệu cây

Đệ qui (Recursion)

Loạt bài Cấu trúc dữ liệu và Giải thuật được viết dựa trên nguồn tài liệu nước ngoài cùng với tìm hiểu một số nguồn tài liệu khác cộng với sự hiểu biết của bản thân về Cấu trúc dữ liệu và giải thuật, do đó không tránh khỏi một số thiếu sót. Nếu bạn đọc hay độc giả có bất kỳ ý kiến đóng góp nào thì mong các bạn comment ngay phần dưới trang để bọn mình kịp thời sửa chữa để có thể cung cấp cho các bạn loạt bài hướng dẫn Cấu trúc dữ liệu và Giải thuật hoàn thiện nhất.

canthiepsomtw.edu.vn xin chân thành cảm ơn và chúc các bạn học tốt !!!


Đã có app Viet
Jack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và i
OS.

*

*

Follow fanpage của team https://www.facebook.com/canthiepsomtw.edu.vnteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.canthiepsomtw.edu.vn để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

Leave a Reply

Your email address will not be published. Required fields are marked *

x

Welcome Back!

Login to your account below

Retrieve your password

Please enter your username or email address to reset your password.