Cấu Trúc Dữ Liệu – Wikipedia Tiếng Việt

Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả.[1][2]

Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng. Kinh nghiệm trong việc xây dựng các hệ thống lớn cho thấy khó khăn của việc triển khai chương trình, chất lượng và hiệu năng của kết quả cuối cùng phụ thuộc rất nhiều vào việc chọn cấu trúc dữ liệu tốt nhất.

Mỗi loại cấu trúc dữ liệu phù hợp với một vài loại ứng dụng khác nhau, một số cấu trúc dữ liệu dành cho những công việc đặc biệt. Ví dụ, các B-tree đặc biệt phù hợp trong việc thiết kế cơ sở dữ liệu. Sau khi cấu trúc dữ liệu được chọn, người ta thường dễ nhận thấy thuật toán cần sử dụng. Đôi khi trình tự công việc diễn ra theo thứ tự ngược lại: cấu trúc dữ liệu được chọn do những bài toán quan trọng nhất định có thuật toán chạy tốt nhất với một số cấu trúc dữ liệu cụ thể. Trong cả hai trường hợp, việc lựa chọn cấu trúc dữ liệu là rất quan trọng.

Tổng quan

[sửa | sửa mã nguồn]

Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên đó được cung cấp bởi một ngôn ngữ lập trình.

Tri thức đó đã dẫn đến sự nổi lên của nhiều ngôn ngữ lập trình và phương pháp thiết kế được hình thức hóa, mà trong đó, nhân tố tổ chức quan trọng là các cấu trúc dữ liệu chứ không phải các thuật toán. Đa số ngôn ngữ có một tính năng thuộc dạng hệ thống module cho phép các cấu trúc dữ liệu được tái sử dụng an toàn trong các ứng dụng khác nhau, bằng cách dùng các giao diện có điều khiển để che các chi tiết cài đặt đã được kiểm thử. Đặc biệt, các ngôn ngữ lập trình hướng đối tượng như C++ và Java sử dụng lớp (class) cho mục đích này.

Vì cấu trúc dữ liệu có tính chất quyết định đối với các chương trình chuyên nghiệp nên có rất nhiều hỗ trợ về cấu trúc dữ liệu trong các thư viện chuẩn của các ngôn ngữ lập trình hiện đại, ví dụ thư viện mẫu chuẩn của C++, Java API, và Microsoft .NET Framework.

Các cấu trúc xây dựng căn bản của hầu hết các cấu trúc dữ liệu là mảng (array), bản ghi (record), tổ hợp phân biệt(?) (discriminated union), và tham chiếu (reference). Ví dụ, tham chiếu khả rỗng (có thể có giá trị null) là một kết hợp của tham chiếu và cấu trúc discriminated union, và cấu trúc dữ liệu liên kết đơn giản nhất, danh sách liên kết, được xây dựng từ các bản ghi và các tham chiếu khả rỗng.

Các nguyên tắc cơ bản

[sửa | sửa mã nguồn]

Ngôn ngữ hỗ trợ

[sửa | sửa mã nguồn]

Hầu hết hợp ngữ và những ngôn ngữ lập trình cấp thấp, chẳng hạn BCPL (Basic Combined Programming Language), không hỗ trợ sẵn cấu trúc dữ liệu. Ngôn ngữ lập trình ở cấp cao và một số hợp ngữ ở mức cao có những cú pháp hay chức năng sẵn có hỗ trợ những cấu trúc dữ liệu nhất định như là bản ghi và mảng. Ví dụ ngôn ngữ C và Pascal hỗ trợ kiểu cấu trúc và bản ghi bên cạnh hỗ trợ mảng một chiều và mảng đa chiều.

Hầu hết những ngôn ngữ lập trình đều có những thư viện có sẵn, hỗ trợ việc xây dựng cấu trúc dữ liệu, chẳng hạn bộ thư viện chuẩn C++, Java Collections Framework và .Net Framework.

Các cấu trúc dữ liệu thường dùng

[sửa | sửa mã nguồn]

• Mảng (cấu trúc dữ liệu) (array list)
• Ngăn xếp (stack)
• Hàng đợi (queue)
• Bảng băm (hash table)
• Danh sách liên kết (linked list)
• Cây (cấu trúc dữ liệu) (tree)
• Đồ thị (cấu trúc dữ liệu) (graph)

Xem thêm

[sửa | sửa mã nguồn]

• Danh sách các cấu trúc dữ liệu
• Mô hình dữ liệu
• Danh sách liên kết

Tham khảo

[sửa | sửa mã nguồn]

1. ^ Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. Hoa Kỳ National Institute of Standards and Technology. ngày 15 tháng 12 năm 2004. Online version Accessed ngày 21 tháng 5 năm 2009.
2. ^ Entry data structure in the Encyclopædia Britannica (2009) Online entry accessed on ngày 21 tháng 5 năm 2009.

Đọc thêm

[sửa | sửa mã nguồn]

• Peter Brass, Advanced Data Structures, Cambridge University Press, 2008.
• Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley, 3rd edition, 1997.
• Dinesh Mehta and Sartaj Sahni Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 2007.
• Niklaus Wirth, Algorithms and Data Structures, Prentice Hall, 1985.

Liên kết ngoài

[sửa | sửa mã nguồn]

Tìm hiểu thêm vềCấu trúc dữ liệutại các dự án liên quan
	Từ điển từ Wiktionary
	Tập tin phương tiện từ Commons
	Danh ngôn từ Wikiquote
	Văn kiện từ Wikisource
	Tủ sách giáo khoa từ Wikibooks
	Tài nguyên học tập từ Wikiversity

• UC Berkeley video course on data structures
• Descriptions from the Dictionary of Algorithms and Data Structures
• CSE.unr.edu
• Data structures course with animations
• Data structure tutorials with animations Lưu trữ ngày 18 tháng 6 năm 2012 tại Wayback Machine
• An Examination of Data Structures from.NET perspective
• Schaffer, C. Data Structures and Algorithm Analysis

Wikimedia Commons có thêm hình ảnh và phương tiện về Cấu trúc dữ liệu.

x t s Cấu trúc dữ liệu
Kiểu	Collection · Container
Trừu tượng	Danh sách · Mảng kết hợp · Multimap · Set · Multiset · Double-ended queue · Hàng đợi · Hàng đợi ưu tiên · Ngăn xếp
Mảng	Mảng động · Sparse array · Circular buffer · Mảng bit · Bảng băm
Liên kết	Danh sách liên kết · Unrolled linked list · Danh sách liên kết XOR · Skip list
Cây	B-cây · Cây tìm kiếm nhị phân (tự cân bằng: AA, AVL, đỏ đen, splay) · Đống (nhị phân, nhị thức, Fibonacci) · Trie
Đồ thị	Đồ thị có hướng · Directed acyclic graph · Sơ đồ quyết định nhị phân · Siêu đồ thị
Danh sách cấu trúc dữ liệu

x t s Các kiểu dữ liệu
Không xác định	Bit Byte Trit Tryte Word Mảng bit
Số	Độ chính xác tùy ý hay bignum Phức Thập phân Dấu phẩy tĩnh Dấu phẩy động Độ chính xác thấp Minifloat Bán chính xác bfloat16 Độ chính xác đơn Độ chính xác kép Độ chính xác bậc bốn Độ chính xác bậc tám Độ chính xác mở rộng Long double Nguyên có dấu và không dấu Khoảng Hữu tỉ
Con trỏ	Địa chỉ vật lý ảo Tham chiếu
Văn bản	Ký tự Chuỗi kết thúc rỗng
Phức hợp	Kiểu dữ liệu đại số tổng quát Mảng Mảng kết hợp Lớp Phụ thuộc Equality Quy nạp Giao Danh sách Đối tượng siêu đối tượng Kiểu tùy chọn Tích Bản ghi hay Struct Refinement Tập hợp Hợp tagged
Khác	Boole Kiểu đáy Collection Kiểu liệt kê Ngoại lệ Kiểu hàm Kiểu dữ liệu mờ Kiểu dữ liệu đệ quy Đèn báo Stream Kiểu đỉnh Lớp kiểu Kiểu đơn vị Void
Chủ đềliên quan	Kiểu dữ liệu trừu tượng Cấu trúc dữ liệu Tổng quát Kind siêu lớp Kiểu đối tượng Đa hình tham số Kiểu dữ liệu cơ bản Giao thức giao diện Đa hình dẫn xuất Hàm tạo kiểu Chuyển đổi kiểu Hệ thống kiểu Lý thuyết hình thái Biến

x t s Khoa học máy tính
Chú ý: Bản mẫu này cơ bản dựa trên Hệ thống xếp loại điện toán ACM năm 2012.
Phần cứng	Mạch in Thiết bị ngoại vi Vi mạch Vi mạch tích hợp Hệ thống trên vi mạch (SoC) Tiêu thụ năng lượng (Điện toán xanh) Tự động hóa thiết kế điện tử Tăng tốc phần cứng Bộ xử lý Kích thước / Dạng thức
Tổ chức hệ thống máy tính	Kiến trúc máy tính Độ phức tạp tính toán Độ tin cậy hệ thống Hệ thống nhúng Hệ thống thời gian thực
Mạng máy tính	Kiến trúc mạng Giao thức mạng Phần cứng mạng Bộ lập lịch trình mạng Hiệu suất mạng Dịch vụ mạng
Tổ chức phần mềm	Trình thông dịch Middleware Máy ảo Hệ điều hành Chất lượng phần mềm
Ký pháp và công cụ phần mềm	Mẫu hình lập trình Ngôn ngữ lập trình Trình biên dịch Ngôn ngữ miền chuyên biệt Ngôn ngữ mô hình hóa Khung phần mềm Môi trường phát triển tích hợp Quản lý cấu hình phần mềm Thư viện phần mềm Kho chứa phần mềm
Phát triển phần mềm	Biến điều khiển Quy trình phát triển phần mềm Phân tích yêu cầu Thiết kế phần mềm Xây dựng phần mềm Triển khai phần mềm Công nghệ phần mềm Bảo trì phần mềm Nhóm lập trình Mô hình nguồn mở
Lý thuyết tính toán	Mô hình tính toán Ngẫu nhiên Ngôn ngữ hình thức Lý thuyết Automat Lý thuyết khả tính Lý thuyết độ phức tạp tính toán Logic Ngữ nghĩa
Thuật toán	Thiết kế thuật toán Phân tích thuật toán Hiệu quả thuật toán Thuật toán ngẫu nhiên Hình học tính toán
Toán học về điện toán	Toán học rời rạc Xác suất Thống kê Phần mềm toán học Lý thuyết thông tin Giải tích toán học Giải tích số Khoa học máy tính lý thuyết
Hệ thống thông tin	Hệ quản trị cơ sở dữ liệu Hệ thống lưu trữ thông tin Hệ thống thông tin doanh nghiệp Hệ thống thông tin xã hội Hệ thống thông tin địa lý Hệ thống hỗ trợ ra quyết định Hệ thống điều khiển quá trình Hệ thống thông tin đa phương tiện Khai phá dữ liệu Thư viện số Nền tảng máy tính Tiếp thị kỹ thuật số World Wide Web Truy hồi thông tin
Bảo mật	Mật mã học Các phương pháp hình thức Hacker bảo mật Dịch vụ bảo mật Hệ thống phát hiện xâm nhập Bảo mật phần cứng Bảo mật mạng An toàn thông tin Bảo mật ứng dụng
Tương tác người–máy	Thiết kế tương tác Điện toán xã hội Điện toán khắp nơi Trực quan hóa Khả năng tiếp cận
Tương tranh	Tính toán tương tranh Tính toán song song Điện toán phân tán Đa luồng Đa xử lý
Trí tuệ nhân tạo	Xử lý ngôn ngữ tự nhiên Biểu diễn tri thức và suy luận Thị giác máy tính Lập kế hoạch và lên lịch tự động Phương pháp tìm kiếm Phương pháp điều khiển Triết học về trí tuệ nhân tạo Trí tuệ nhân tạo phân tán
Học máy	Học có giám sát Học không có giám sát Học tăng cường Học đa tác vụ Kiểm chứng chéo
Đồ họa	Hoạt hình Thực tế mở rộng Tăng cường Hỗn hợp Ảo Kết xuất Thao túng hình ảnh Bộ xử lý đồ họa Nén ảnh Mô hình hóa dạng khối
Điện toán ứng dụng	Điện toán lượng tử Thương mại điện tử Phần mềm doanh nghiệp Toán học tính toán Vật lý tính toán Hóa học tính toán Sinh học tính toán Khoa học xã hội tính toán Kỹ thuật tính toán Điện toán khả vi Y tế tính toán Nghệ thuật số Xuất bản điện tử Chiến tranh mạng Bầu cử điện tử Trò chơi video Soạn thảo văn bản Vận trù học Công nghệ giáo dục Quản lý tài liệu
Thể loại Đề cương Thuật ngữ

Bài viết này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.

• x
• t
• s