Bài giảng Cấu trúc dữ liệu và giải thuật: Phần 2 - ThS. Hoàng Thế Phương

Tiếp nội dung phần 1, Bài giảng Cấu trúc dữ liệu và giải thuật phần 2 được biên soạn gồm các nội dung chính sau: Cấu trúc dữ liệu; Giải thuật sắp xếp và tìm kiếm;...Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Phần 2 - ThS. Hoàng Thế Phương Chương 4. Cấu trúc dữ liệu 4.1. Mảng và danh sách 4.1.1. Các khái niệm Có thể nói, mảng là cấu trúc dữ liệu căn bản và được sử dụng rộng rãi nhất trong tất cả các ngôn ngữ lập trình. Một mảng là 1 tập hợp cố định các thành phần có cùng 1 kiểu dữ liệu, được lưu trữ kế tiếp nhau và có thể được truy cập thông qua một chỉ số. Ví dụ, để truy cập tới phần tử thứ i của mảng a, ta viết a[i]. Chỉ số này phải là số nguyên không âm và nhỏ hơn kích thước của mảng (số phần tử của mảng). Trong chương trình, chỉ số này không nhất thiết phải là các hằng số hoặc biến số, mà có thể là các biểu thức hoặc các hàm. a a1 a2 ai i+1 an Lưu ý rằng cấu trúc của bộ nhớ máy tính cũng được tổ chức thành các ô nhớ, và cũng có thể truy cập ngẫu nhiên thông qua các địa chỉ. Do vậy, việc lưu trữ dữ liệu trong mảng có sự tương thích hoàn toàn với bộ nhớ máy tính, trong đó có thể coi toàn bộ bộ nhớ máy tính như 1 mảng, và địa chỉ các ô nhớ tương ứng như chỉ số của mảng. Chính vì sự tương thích này mà việc sử dụng cấu trúc dữ liệu mảng trong các ngôn ngữ lập trình có thể làm cho chương trình hiệu quả hơn và chạy nhanh hơn. Mảng có thể có nhiều hơn 1 chiều. Khi đó, số các chỉ số của mảng sẽ tương ứng với số chiều. Chẳng hạn, trong mảng 2 chiều a, thành phần thuộc cột i, hàng j được viết là a[i][j]. Mảng 2 chiều còn được gọi là ma trận (matrix). a a a a ll 2l il i+ll ^ml a a al2 a22 i2 ai+l2 m2 a a a a a lj 2j ij i+lj mj a a a a alj+l 2j+l ij+l i+lj+l mj+l a a a a a ln 2n in i+ ln mn 128 Như đã nói ở trên, mảng là cấu trúc dữ liệu dễ sử dụng, tốc độ truy cập cao. Tuy nhiên, nhược điểm chính của mảng là không linh hoạt về kích thước. Nghĩa là khi ta đã khai báo l mảng thì kích thước của nó là cố định, không thể thay đổi trong quá trình thực hiện chương trình. Điều này rất bất tiện khi ta chưa biết trước số phần tử cần xử lý. Nếu khai báo mảng lớn sẽ tốn bộ nhớ và ảnh hưởng đến hiệu suất của chương trình. Nếu khai báo mảng nhỏ sẽ dẫn đến thiếu bộ nhớ. Ngoài ra, việc bố trí lại các phần tử trong mảng cũng khá phức tạp, bởi vì mỗi phần tử đã có vị trí cố định trong mảng, và để bố trí l phần tử sang l vị trí khác, ta phải tiến hành “dồn” các phần tử có liên quan. Khác với mảng, danh sách liên kết là l cấu trúc dữ liệu có kiểu truy cập tuần tự. Mỗi phần tử trong danh sách liên kết có chứa thông tin về phần tử tiếp theo, qua đó ta có thể truy cập tới phần tử này. R. Sedgewick (Alogrithms in Java - 2002) định nghĩa danh sách liên kết như sau: Danh sách liên kết là l cấu trúc dữ liệu bao gồm l tập các phần tử, trong đó mỗi phần tử là l phần của l nút có chứa một liên kết tới nút kế tiếp. Nói “mỗi phần tử là l phần của l nút” bởi vì mỗi nút ngoài việc chứa thông tin về phần tử còn chứa thông tin về liên kết tới nút tiếp theo trong danh sách. Có thể nói danh sách liên kết là l cấu trúc dữ liệu được định nghĩa kiểu đệ qui, vì trong định nghĩa l nút của danh sách có tham chiếu tới khái niệm nút. Thông thường, một nút thường có liên kết trỏ tới một nút khác, tuy nhiên nó cũng có thể trỏ tới chính nó. Danh sách liên kết có thể được xem như là l sự bố trí tuần tự các phần tử trong l tập. Bắt đầu từ l nút, ta coi đó là phần tử đầu tiên trong danh sách. Từ nút này, theo liên kết mà nó trỏ tới, ta có nút thứ 2, được coi là phần tử thứ 2 trong danh sách, v.v. cứ tiếp tục như vậy cho đến hết danh sách. Nút cuối cùng có thể có liên kết là một liên kết null, tức là không trỏ tới nút nào, hoặc nó có thể trỏ về nút đầu tiên để tạo thành l vòng. NULL Như vậy, mặc dù cùng là cấu trúc dữ liệu bao gồm 1 tập các phần tử, nhưng giữa danh sách liên kết và mảng có 1 số điểm khác biệt sau: - Mảng có thể được truy cập ngẫu nhiên thông qua chỉ số, còn danh sách chỉ có thể truy cập tuần tự. Trong danh sách liên kết, muốn truy cập tới 1 phần từ phải bắt đầu từ đầu danh sách sau đó lần lượt qua các phần tử kế tiếp cho tới khi đến phần tử cần truy 129 cập. - Việc bố trí, sắp đặt lại các phần tử trong 1 danh sách liên kết đơn giản hơn nhiều so với mảng. Bới vì đối với danh sách liên kết, để thay đổi vị trí của 1 phần tử, ta chỉ cần thay đổi các liên kết của một số phần tử có liên quan, còn trong mảng, ta thường phải thay đổi vị trí của rất nhiều phần tử. Do bản chất động của danh sách liên kết, kích thước của danh sách liên kết có thể linh hoạt hơn nhiều so với mảng. Kích thước của danh sách không cần phải khai báo trước, bất kỳ lúc nào có thể tạo mới 1 phần tử và thêm vào vị trí bất kỳ trong danh sách. Nói cách khác, mảng là 1 tập có số lượng cố định các phần tử, còn danh sách liên kết là 1 tập có số lượng phần tử không cố định. 4.1.2. Cấu trúc lưu trữ mảng Cấu trúc dữ liệu đơn giản nhất dùng địa chỉ tính được để thực hiện lưu trữ và tìm kiếm phần tử, là mảng một chiều hay véc tơ. Thông thường thì một số từ máy sẽ được dành ra để lưu trữ các phần tử của mảng. Cách lưu trữ này được gọi là cáchlưu trữ kế tiếp (sequential storage allocation). Trường h ...