Chương 1. KHÁI QUÁT VỀ TÌM KIẾM VÀ VẤN ĐỀ TỔ CHỨC DỮ LIỆU
1.2. Tổ chức dữ liệu trong tìm kiếm thông tin
Cấu trúc dữ liệu [1] là một lĩnh vực nghiên cứu lâu đời của khoa học máy tính. Hầu hết các chương trình được viết ra, chạy trên máy tính, dù lớn hay nhỏ, dù đơn giản hay phức tạp, đều phải sử dụng cấu trúc dữ liệu. Có thể nói rằng không có một chương trình máy tính nào mà không cần và không có dữ liệu để xử lý. Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian, dữ liệu đưa ra (output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý nghĩa rất quan trọng trong toàn bộ hệ thống chương trình. Việc tổ chức cấu trúc dữ liệu quyết định rất lớn đến chất lượng của phần mềm cũng như công sức của người lập trình trong việc thiết kế cài đặt chương trình. Trong khoa học máy tính, cấu trúc dữ liệu là cách lưu trữ dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. 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. 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. Sau khi cấu trúc dữ liệu được chọn, người ta thường dễ dàng 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. Đúng như Giáo sư Niklaus Wirth, người sáng tác ra ngôn ngữ Pascal đã có một triết lý: Cấu trúc dữ liệu + Giải thuật = Chương trình. Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
thì việc thể hiện chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian.
Với các cấu trúc dữ liệu được xây dựng từ các kiểu cơ sở như: kiểu thực, kiểu nguyên, kiểu ký tự... hoặc từ các cấu trúc đơn giản như mẩu tin, tập hợp, mảng... lập trình viên có thể giải quyết hầu hết các bài toán đặt ra. Các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này có đặc điểm chung là không thay đổi được kích thước, cấu trúc trong quá trình sống, do vậy thường cứng nhắc, gò bó khiến đôi khi khó diễn tả được thực tế vốn sinh động, phong phú. Các kiểu dữ liệu kể trên được gọi là các kiểu dữ liệu tĩnh.
Một số đối tượng dữ liệu trong chu kỳ sống của nó có thể thay đổi về cấu trúc, độ lớn, như danh sách các học viên trong một lớp học có thể tăng thêm, giảm đi... Khi đó nếu cố tình dùng những cấu trúc dữ liệu tĩnh đã biết như mảng để biểu diễn những đối tượng đó lập trình viên phải sử dụng những thao tác phức tạp, kém tự nhiên khiến chương trình trở nên khó đọc, do đó khó bảo trì và nhất là khó có thể sử dụng bộ nhớ một cách có hiệu quả.
Do bản chất của các dữ liệu tĩnh, chúng sẽ chiếm vùng nhớ đã dành cho chúng suốt quá trình hoạt động của chương trình. Tuy nhiên, trong thực tế, có thể xảy ra trường hợp một dữ liệu nào đó chỉ tồn tại nhất thời hay không thường xuyên trong quá trình hoạt động của chương trình. Vì vậy việc dùng các cấu trúc dữ liệu tĩnh sẽ không cho phép sử dụng hiệu quả bộ nhớ.
Do vậy, nhằm đáp ứng nhu cầu thể hiện sát thực bản chất của dữ liệu cũng như xây dựng các thao tác hiệu quả trên dữ liệu, cần phải tìm cách tổ chức kết hợp dữ liệu với những hình thức mới linh động hơn, có thể thay đổi kích thước, cấu trúc trong suốt thời gian sống. Các hình thức tổ chức dữ liệu như vậy được gọi là cấu trúc dữ liệu động. Và Stack, Queue, DEQueue, Heap,... cũng là cấu trúc dữ liệu động.
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
1.2.2. Một số cấu trúc dữ liệu 1.2.2.1. Stack
Stack (ngăn xếp) là một kiểu danh sách được trang bị hai phép toán bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử cũng ở cuối danh sách [4].
Có thể hình dung Stack như hình ảnh một chồng đĩa, đĩa nào được đặt vào chồng sau cùng sẽ nằm trên tất cả các đĩa khác và sẽ được lấy ra đầu tiên.
Vì nguyên tắc “vào sau ra trước” đó, Stack còn có tên gọi là danh sách LIFO (Last In First Out) và vị trí cuối danh sách được gọi là đỉnh (Top) của Stack.
Ví dụ về mô hình Stack trong thực tế:
Hình 1.4. Mô hình Stack trong thực tế 1.2.2.2. Queue
Queue (hàng đợi) là một kiểu danh sách được trang bị hai phép toán bổ sung một phần tử vào cuối danh sách (Rear) và loại bỏ một phần tử ở đầu danh sách (Front) [4].
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
Có thể hình dung Queue như một đoàn người xếp hàng mua vé: Người nào xếp hàng trước sẽ được mua vé trước. Vì nguyên tắc “vào trước ra trước”
đó, Queue còn có tên gọi khác là dánh sách kiểu FIFO (First In First Out).
Ví dụ về mô hình Queue trong thực tế:
Hình 1.5. Mô hình Queue trong thực tế 1.2.2.4. Heap
Heap [5] thực chất là một cây cân bằng thỏa mãn các điều kiện sau:
Một nút có không quá 2 nút con;
Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha của nó. Với Heap Min thì ngược lại.
Với cách định nghĩa trên thì Heap chứa các phần tử có thể giống nhau.
Ngoài ra chúng ta còn có Heap chỉ chứa các phần tử khác nhau.
Ví dụ về Hình 1.6 là Heap Max, trong đó Heap[1] là phần tử có độ ưu tiên lớn nhất, còn mọi phần tử Heap[i] khác đều có độ ưu tiên bé hơn Heap[i div 2] (Heap[i div 2] là cha của Heap[i])
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
Hình 1.6. Heap Max chứa các phần tử có thể giống nhau
Hình 1.7 là Heap Min, chính vì vậy Heap[1] là phần tử có độ ưu tiên bé nhất.
Hình 1.7. Heap Min chứa các phần tử khác nhau 10
8 8
7 4 6 1
3 5
5
9 18
10 11 19 21
13 15
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/
Chương 2