Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 2: Kiểu dữ liệu, cấu trúc dữ liệu và mô hình dữ liệu

Trong máy tính điện tử (MTĐT), các dữ liệu dù có bản chất khác nhau như thế nào (số nguyên, số thực, hay xâu ký tự, .), đều được biểu diễn dưới dạng nhị phân. Mỗi dữ liệu được biểu diễn dưới dạng một dãy các số nhị phân 0 hoặc 1. Về mặt kỹ thuật đây là cách biểu diễn thích hợp nhất, vì các giá trị 0 và 1 dễ dàng được mã hoá bởi các phần tử vật lý chỉ có hai trạng thái. Chúng ta sẽ không quan tâm đến cách biểu diễn này của dữ liệu, cũng như các cách tiến hành các thao tác, các phép toán trên các dữ liệu được biểu diễn dưới dạng nhị phân. Cách biểu diễn nhị phân của dữ liệu rất không thuận tiện đối với con người. Việc xuất hiện các ngôn ngữ lập trình bậc cao (FORTRAN, BASIC, PASSCAL, C .) đã giải phóng con người khỏi những khó khăn khi làm việc với cách biểu diễn trong máy của dữ liệu. Trong các ngôn ngữ lập trình bậc cao, các dữ liệu, hiểu theo một nghĩa nào đó, là sự trìu tượng hoá các tính chất của các đối tượng trong thế giới hiện thực. Nói dữ liệu là sự trìu tượng hoá từ thế giới hiện thực, vì ta đã bỏ qua những nhân tố, tính chất mà ta cho là không cơ bản, chỉ giữ lại những tính chất đặc trưng cho các đối tượng thuộc phạm vi bài toán đang xét. Chẳng hạn, vị trí của một đối tượng trong thực tiễn, được đặc trưng bởi cặp số thực (x,y) (đó là toạ đoạ đê-các của một điểm trong mặt phẳng). Do đó, trong ngôn ngữ Pascal, vị trí một đối tượng được biểu diễn bởi bản ghi gồm hai trường tương ứng với hoành độ và tung độ của một điểm. Trong toán học có các khái niệm biểu diễn đặc trưng về mặt số lượng và các quan hệ của các đối tượng trong thế giới hiện thực, đó là các khái niệm số nguyên, số thực, số phức, dãy, ma trận, . Trên cơ sở các khái niệm toán học này, người ta đã đưa vào trong các ngôn ngữ lập trình bậc cao các dữ liệu kiểu nguyên, thực, phức, mảng, bản ghi, . Tuy nhiên do tính đa dạng của các bài toán cần xử lý bằng MTĐT, chỉ sử dụng các kiểu dữ liệu có sẵn trong các ngôn ngữ lập trình bậc cao là chưa đủ để mô tả các bài toán. Chúng ta phải cần đến các cấu trúc dữ liệu. Đó là các dữ liệu phức tạp, được xây dựng nên từ các dữ liệu đã có, đơn giản hơn bằng các phương pháp liên kết nào đó. Để giải quyết một bài toán bằng MTĐT, ta cần xây dựng mô hình dữ liệu mô tả bài toán. Đó là sự trìu tượng hoá các đặc trưng của các đối tượng thuộc phạm vi vấn đề mà ta quan tâm, các mối quan hệ giữa các đối tượng đó. Dùng làm các mô hình dữ liệu trong tin học, chúng ta sẽ sử dụng các mô hình toán học như danh sách, cây, tập hợp, ánh xạ, quan hệ, đồ thị, .