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 getAt
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
Ứ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ánThà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épDanh sách liên kết đơnCá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épCá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 Stackpop(): lấy ra và trả lại phần tử được bổ sung vào cuối cùng của StackMộ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ệtThứ 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ánLà 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 queueMột số ứng dụng của Queque
Các ứng dụng trực tiếp
Danh sách hàng đợiTruy 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ánLà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âyCâ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 .
Tài liệu Giáo viên
Lớp 2Lớ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 3Lớ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 4Sách giáo khoa
Sách/Vở bài tập
Tài liệu Giáo viên
Lớp 5Sách giáo khoa
Sách/Vở bài tập
Tài liệu Giáo viên
Lớp 6Lớ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 7Lớ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 8Sách giáo khoa
Sách/Vở bài tập
Tài liệu Giáo viên
Lớp 9Sách giáo khoa
Sách/Vở bài tập
Tài liệu Giáo viên
Lớp 10Lớ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 11Sách giáo khoa
Sách/Vở bài tập
Tài liệu Giáo viên
Lớp 12Sách giáo khoa
Sách/Vở bài tập
Tài liệu Giáo viên
Giáo viênLớ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.