chương 1 cũng đồng thời đề cập đến khái niệm giải thuật, các phương pháp đánh giá độ phức tạp của giải thuật. Cuối cùng là nội dung kiến thức đề cập đến mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong khoa học máy tính. TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU 1. Dữ liệu và cấu trúc dữ liệu Kể từ khi phát minh ra máy tính, con người đã sử dụng thuật ngữ “Dữ liệu” để chỉ thông tin trong máy tính.
Dữ liệu có thể là số hoặc văn bản được lưu trữ trong bộ nhớ của thiết bị điện tử hoặc dữ kiện được lưu trữ trong tâm trí con người. Khi thế giới bắt đầu hiện đại hóa, dữ liệu trở thành một khía cạnh quan trọng trong cuộc sống hàng ngày của con người với nhiều cách sử dụng khác nhau cho phép họ lưu trữ dữ liệu theo những cách khác nhau. Dữ liệu là tập hợp các sự kiện, số liệu hoặc một tập hợp các giá trị hoặc các giá trị có định dạng chuyên biệt biểu thị nội dung của một tập hợp các mục dữ liệu (data items). Dữ liệu cần phải được “xử lý” để trở thành thông tin.
Để dữ liệu trở thành thông tin, cần xem xét một số nhân tố bao gồm người (hoặc vật) tạo ra dữ liệu và thông tin được mong muốn từ dữ liệu đó. Các mục dữ liệu có thể được phân loại thành các mục con (sub- items) khi đó được gọi là dữ liệu nhóm; các mục dữ liệu không thể phân chia được nhỏ hơn gọi là dữ liệu sơ đẳng. Ví dụ, trong một tệp cơ sở dữ liệu có mục (item) là name (tên nhân viên) được chia thành ba mục nhỏ: First, Middle và Last. Trong khi mục ID của nhân viên không thể được phân chia thành các mục con nhỏ hơn nữa.
Hình 1-1: Minh hoạ các mục dữ liệu 2 Trong Hình 1-1, các mục như ID, Gender (Giới tính), Street (Đường), v., là các mục dữ liệu sơ đẳng; Name (Tên) và Address (Địa chỉ) là các mục dữ liệu nhóm. Cấu trúc dữ liệu là một định dạng tổ chức, quản lý và lưu trữ dữ liệu thường được chọn để truy cập dữ liệu một cách hiệu quả. Chính xác hơn, cấu trúc dữ liệu là tập hợp các giá trị dữ liệu, mối quan hệ giữa chúng và các hàm hoặc thao tác có thể áp dụng cho dữ liệu, tức là nó là cấu trúc đại số về dữ liệu. Nghiên cứu cấu trúc dữ liệu cho phép chúng ta hiểu cách tổ chức dữ liệu và quản lý luồng dữ liệu nhằm tăng hiệu quả của bất kỳ quy trình hoặc chương trình nào.
Dữ liệu có thể được quản lý theo nhiều cách khác nhau, như mô hình logic hoặc toán học cho một tổ chức dữ liệu cụ thể được gọi là cấu trúc dữ liệu. Phạm vi của một mô hình dữ liệu cụ thể phụ thuộc vào hai yếu tố: 1. Cấu trúc dữ liệu phải phản ánh mối tương quan rõ ràng giữa dữ liệu với đối tượng trong thế giới thực. Việc sử dụng cấu trúc dữ liệu phải mang lại tính hiệu quả.
Một số ví dụ về cấu trúc dữ liệu là Mảng (Array), Danh sách liên kết (Linked List), Ngăn xếp (Stack), Hàng đợi (Queue), Cây (Trees), v. Việc lựa chọn cấu trúc dữ liệu phù hợp cho một chương trình là một nhiệm vụ khó đối với người phát triển phần mềm. Khi các ứng dụng ngày càng trở nên phức tạp và lượng dữ liệu tăng lên mỗi ngày, điều này có thể dẫn đến các vấn đề về tìm kiếm dữ liệu, về tốc độ khi xử lý nhiều yêu cầu, v. Cấu trúc dữ liệu hỗ trợ các phương pháp khác nhau để tổ chức, quản lý và lưu trữ dữ liệu một cách hiệu quả.
Với sự trợ giúp của cấu trúc dữ liệu, chúng ta có thể dễ dàng duyệt qua các mục dữ liệu. Cấu trúc dữ liệu cung cấp tính hiệu quả, khả năng sử dụng lại và tính trừu tượng. Cấu trúc dữ liệu đóng vai trò quan trọng trong ngành khoa học máy tính. Một cấu trúc dữ liệu cần đáp ứng các mục tiêu sau: Tính chính xác: Cấu trúc dữ liệu được thiết kế để hoạt động chính xác cho tất cả các loại đầu vào dựa trên miền quan tâm.
Nói cách khác, tính chính xác là mục tiêu chính của Cấu trúc dữ liệu, mục tiêu này luôn phụ thuộc vào các vấn đề mà Cấu trúc dữ liệu nhằm giải quyết. Hiệu quả: Cấu trúc dữ liệu cũng đòi hỏi phải hiệu quả. Nó sẽ xử lý dữ liệu nhanh chóng mà không cần sử dụng nhiều tài nguyên máy tính như dung lượng bộ nhớ. Trong trạng thái thời gian thực, hiệu quả của cấu trúc dữ liệu là yếu tố chính quyết định sự thành công và thất bại của quy trình.
Việc chọn cấu trúc dữ liệu không phù hợp có thể dẫn đến thời gian chạy chậm hoặc mã không phản hồi. Một số yếu tố sau đây cần được cân nhắc khi chọn cấu trúc dữ liệu, 3 cụ thể là: (i) Loại thông tin lưu trữ, (ii) Thông tin được sử dụng như thế nào, (iii) Dữ liệu được lưu giữ ở đâu sau khi được tạo lập, (iv) Cách tốt nhất để tổ chức dữ liệu là gì và (v) Những khía cạnh nào của việc quản lý dự trữ bộ nhớ và lưu trữ cần được quan tâm. Phân loại các kiểu cấu trúc dữ liệu Cấu trúc dữ liệu được biểu diễn trong máy tính một cách rất đa đạng và phong phú. Dựa vào các tiêu chí cụ thể, chúng ta có thể phân loại cấu trúc dữ liệu thành nhiều loại khác nhau.
Dựa trên tiêu chí về cách thức tổ chức và hợp thành cấu trúc dữ liệu, chúng ta có thể chia cấu trúc dữ liệu thành hai nhóm chính và được thể hiện như trong Hình 1-2. Cấu trúc dữ liệu nguyên thủy (Primitive Data Structure): là cấu trúc dữ liệu bao gồm các số và ký tự được cung cấp sẵn bởi các ngôn ngữ lập trình chương trình. Các kiểu dữ liệu cơ bản như Integer, Float, Character và Boolean thuộc cấu trúc dữ liệu nguyên thủy. Cấu trúc dữ liệu không nguyên thủy (Non-Primitive Data Structure): là những cấu trúc dữ liệu được xây dựng từ những cấu trúc dữ liệu nguyên thủy.
Trọng tâm của các cấu trúc dữ liệu này là hình thành một tập hợp các thành phần dữ liệu đồng nhất (cùng loại dữ liệu) hoặc không đồng nhất (các loại dữ liệu khác nhau). Hình 1-2: Phân loại cấu trúc dữ liệu trong máy tính Trong nhóm cấu trúc dữ liệu không nguyên thuỷ, dựa trên cấu trúc và cách sắp xếp dữ liệu, chúng ta có thể chia các cấu trúc dữ liệu này thành hai loại: (i) Cấu trúc dữ 4 liệu tuyến tính (Linear Data Structure) và (ii) Cấu trúc dữ liệu phi tuyến tính (Non- Linear Data Structure). Cấu trúc dữ liệu tuyến tính Cấu trúc dữ liệu tuyến tính là là cấu trúc dữ liệu trong đó các phần tử dữ liệu được sắp theo thứ tự tuần tự. Các cấu trúc dữ liệu tuyển tính phổ biến bao gồm: mảng, danh sách liên kết, ngăn xếp và hàng đợi.
Cấu trúc dữ liệu tuyến tính được phân thành hai loại dựa trên việc phân bổ bộ nhớ: Cấu trúc dữ liệu tĩnh: Các cấu trúc dữ liệu có kích thước cố định được gọi là cấu trúc dữ liệu tĩnh. Bộ nhớ cho các cấu trúc dữ liệu này được cấp phát tại thời điểm biên dịch và người dùng không thể thay đổi kích thước của chúng sau khi được biên dịch; tuy nhiên, dữ liệu được lưu trữ trong đó có thể bị thay đổi. Mảng là ví dụ điển hình nhất về Cấu trúc dữ liệu tĩnh vì chúng có kích thước cố định. Cấu trúc dữ liệu động: Các cấu trúc dữ liệu có kích thước động được gọi là Cấu trúc dữ liệu động.
Bộ nhớ của các cấu trúc dữ liệu này được cấp phát tại thời gian chạy và kích thước của chúng thay đổi trong thời gian này. Người dùng có thể thay đổi kích thước cũng như các thành phần dữ liệu được lưu trữ trong các cấu trúc dữ liệu này tại thời điểm chạy chương trình. Danh sách liên kết, ngăn xếp và hàng đợi là những ví dụ phổ biến về cấu trúc dữ liệu động. Cấu trúc dữ liệu phi tuyến tính Cấu trúc dữ liệu phi tuyến tính là cấu trúc dữ liệu trong đó các phần tử dữ liệu không được sắp theo thứ tự tuần tự mà chỉ tồn tại một mối quan hệ phân cấp giữa các mục dữ liệu riêng lẻ.
Các loại cấu trúc dữ liệu phi tuyến tính là cây, đồ thị, v. Như đã đề cập về vai trò của cấu trúc dữ liệu đối với khoa học máy tính, để hướng đến hoàn thành vai trò của mình, cấu trúc dữ liệu thường được áp dụng một số thao tác cơ bản sau: Duyệt (Traversing): là thao tác truy cập từng thành phần trong cấu trúc dữ liệu để quản lý nội dung của nó. Ví dụ như yêu cầu cần phải hiển thị thông tin của tất cả nhân viên trong một cơ quan. Tìm kiếm (Searching): là thao tác tìm kiếm một hoặc nhiều thành phần trong cấu trúc dữ liệu đáp ứng các ràng buộc nhất định.
Phần tử dữ liệu như vậy có thể có hoặc không có trong tập hợp các phần tử dữ liệu đã cho. Ví dụ như yêu cầu cần tìm kiếm tên của tất cả nhân viên có kinh nghiệm trên 5 năm trong một cơ quan. 5 Chèn (Insertion): là thao tác chèn hoặc thêm các phần tử dữ liệu mới vào cấu trúc dữ liệ. Ví dụ như yêu cầu chèn thêm thông tin chi tiết về một nhân viên mới mà công ty đã thuê gần đây.
Xóa (Deletion): là thao tác loại bỏ (remove) hoặc xóa (delete) một phần tử dữ liệu cụ thể khỏi danh sách các phần tử dữ liệu đã cho. Ví dụ như yêu cầu sử dụng thao tác xóa để xóa dữ liệu của một nhân viên đã nghỉ việc trên 5 năm. Sắp xếp (Sorting): là thao tác sắp xếp các thành phần dữ liệu theo thứ tự nhất định (Tăng dần hoặc Giảm) dần tùy thuộc vào loại ứng dụng. Ví dụ như yêu cầu sắp xếp tên của nhân viên trong một bộ phận theo thứ tự bảng chữ cái.
Hợp nhất (Merging): là thao tác kết hợp các phần tử dữ liệu của hai danh sách đã được sắp xếp để tạo thành một danh sách duy nhất gồm các phần tử dữ liệu cũng được sắp xếp. Tạo (Creating): là thao tác dùng để cấp phát bộ nhớ cho các thành phần dữ liệu của chương trình. Chúng ta có thể thực hiện thao tác này bằng cách sử dụng câu lệnh khai báo. Việc tạo cấu trúc dữ liệu có thể diễn ra trong thời gian biên dịch (Compile) hoặc thời gian chạy chương trình (Run-time).