lolem_1305
New Member
Download miễn phí Bài giảng Kiểu dữ liệu trừu tượng danh sách
Tìm kiếm nhị phân (Binary Search)
Tư tưởng của kỹ thuật tìm kiếm nhị phân là như sau: xét phần tử đứng giữa danh sách, nó chia danh sách thành hai phần: nửa đầu và nửa sau. (Chú ý rằng, vì danh sách được lưu trong mảng, nên ta có thể tìm thấy phần tử ở giữa danh sách chỉ với thời gian O(1)). Do danh sách được sắp xếp theo thứ tự tăng của khoá, nên tất cả các phần tử ở nửa đầu danh sách đều có khoá nhỏ hơn khoá của phần tử đứng giữa danh sách và khoá của phần tử này nhỏ hơn khoá của tất cả các phần tử ở nửa sau danh sách. Nếu khoá k của phần tử cần tìm bằng khoá của phần tử đứng giữa danh sách có nghĩa là ta đã tìm thấy; còn nếu k khác khoá của phần tử đứng giữa, ta tiếp tục tìm kiếm ở nửa đầu (nửa sau) danh sách tuỳ từng trường hợp khoá k nhỏ hơn (lớn hơn) khóa của phần tử đứng giữa danh sách. Quá trình tìm kiếm ở nửa đầu (hay nửa sau) được thực hiện bằng cách lặp lại thủ tục trên. Chúng ta có thể cài đặt thuật toán tìm kiếm nhị phân bởi hàm đệ quy hay không đệ quy. Trong hình 4.6 là hàm Search không đệ quy.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
thời.private :
Item element[MAX];
int last;
int current;
};
# include “list.template”
# endif
Hình 4.2. Định nghĩa lớp List.
Bước tiếp theo chúng ta cần cài đặt các hàm thành phần của lớp List. Trước hết, nói về hàm kiến tạo mặc định, hàm này cần tạo ra một danh sách rỗng, do vậy chỉ cần đặt giá trị cho biến last là –1, giá trị của biến current cũng là –1. Hàm này được cài đặt là hàm inline. Với cách khởi tạo này, mỗi khi cần thêm phần tử mới vào đuôi danh sách (kể cả khi danh sách rỗng), ta chỉ cần tăng chỉ số last lên 1 và đặt phần tử cần thêm vào thành phần mảng element[last].
Hàm Append được định nghĩa như sau:
template
void List :: Append (const Item& x)
{ assert (Length( ) < MAX);
last + + ;
element[last] = x;
}
Hàm Insert. Để xen phần tử x vào vị trí thứ i của danh sách, tức là x cần đặt vào thành phần element[i - 1] trong mảng, chúng ta cần dịch chuyển đoạn element[i – 1 … last] ra sau một vị trí để có chỗ cho phần tử x. Hàm Insert có nội dung như sau:
template
void List :: Insert(const Item& x, int i)
{
assert (Length( ) < MAX && 1 <= i && i <= Length( ));
last + +;
for (int k = last; k >= i; k - -)
element[k] = element[k - 1];
element[i - 1] = x;
}
Hàm Add. Hàm này cũng tương tự như hàm Insert, nó có nhiệm vụ xen phần tử mới x vào vị trí của phần tử hiện thời. Vì phần tử hiện thời được đẩy ra sau một vị trí, nên chỉ số hiện thời phải được tăng lên 1.
template
void List :: Add(const Item& x)
{
assert (Length( ) < MAX && Valid( ));
last + +;
for(int k = last; k > current; k - -)
element[k] = element[k - 1];
element[current] = x;
current + +;
}
Hàm Delete. Muốn loại khỏi danh sách phần tử ở vị trí thứ i, chúng ta cần đẩy đoạn cuối của danh sách kể từ vị trí i + 1 lên trước 1 vị trí, và giảm chỉ số last đi 1.
template
void List :: Delete(int i)
{
assert (1 <= i && i <= Length( ));
for (int k = i – 1; k < last; k + +)
element[k] = element[k + 1];
last - - ;
}
Hàm Remove. Hàm này được cài đặt tương tự như hàm Delete.
template
void List :: Remove( )
{
assert(Valid( ));
for (int k = current; k < last; k + +)
element[k] = element[k + 1];
last - - ;
}
Tất cả các hàm còn lại đều rất đơn giản và được cài đặt là hàm inline.
Bây giờ chúng ta đánh giá hiệu quả của các phép toán của KDLTT danh sách, khi mà danh sách được cài đặt bởi mảng. Ưu điểm của cách cài đặt này là nó cho phép ta truy cập trực tiếp tới từng phần tử của danh sách, vì phần tử thứ i của danh sách được lưu trong thành phần mảng element[i -1]. Nhờ đó mà thời gian của phép toán Element(i) là O(1). Giả sử danh sách có độ dài n, để xen phần tử mới vào vị trí thứ i trong danh sách, chúng ta cần đẩy các phần tử lưu ở các thành phần mảng từ element[i -1] đến element[n -1] ra sau một vị trí. Trong trường hợp xấu nhất (khi xen vào vị trí đầu tiên trong danh sách), cần n lần đẩy, vì vậy thời gian của phép toán Insert là O(n). Phân tích một cách tượng tự, chúng ta thấy rằng thời gian chạy của các phép toán Delete, Add và Remove cũng là O(n), trong đó n là độ dài của danh sách. Thời gian của tất cả các phép toán còn lại đều là O(1).
Như chúng ta đã nói, các phép toán trong bộ công cụ lặp cho phép chúng ta có thể tiến hành dễ dàng các xử lý danh sách cần đến duyệt danh sách. Chẳng hạn, giả sử L là danh sách các số nguyên, để loại khỏi danh sách L tất cả các số nguyên bằng 3, chúng ta có thể viết:
L. Start( );
while (L.Valid( ))
if (L.Current( ) = = 3)
L.Remove( ) ;
else L.Advance( ) ;
Chúng ta cũng có thể in ra tất cả các phần tử của danh sách bằng cách sử dụng vòng lặp for như sau:
for (L.Start( ); L.Valid( ); L.Advance( ))
cout << L.Current( ) << endl;
Nhận xét. Cài đặt danh sách bởi mảng có ưu điểm cơ bản là nó cho phép truy cập trực tiếp tới từng phần tử của danh sách. Nhờ đó chúng ta có thể cài đặt rất thuận tiện phép toán tìm kiếm trên danh sách, đặc biệt khi danh sách là danh sách được sắp (các phần tử của nó được sắp xếp theo thứ tự không tăng hay không giảm), nếu lưu danh sách được sắp trong mảng, chúng ta có thể cài đặt dễ dàng phương pháp tìm kiếm nhị phân. Phương pháp tìm kiếm nhị phân là một kỹ thuật tìm kiếm rất hiệu quả và sẽ được nghiên cứu trong mục 4.4.
Chúng ta đã cài đặt danh sách bởi mảng tĩnh, mảng có cỡ MAX cố định. Khi danh sách phát triển, tới lúc nào đó mảng sẽ đầy, và lúc đó các phép toán Insert, Append, Add sẽ không thể thực hiện được. Đó là nhược điểm chính của cách cài đặt danh sách bởi mảng tĩnh.
Bây giờ nói về cách thiết kế lớp List. Trong lớp List này, tất cả các hàm trong bộ công cụ lặp được đưa vào các hàm thành phần của lớp và biến lưu vị trí hiện thời cũng là một biến thành phần của lớp. Thiết kế này có vấn đề: chỉ có một biến hiện thời, do đó chúng ta không thể tiến hành đồng thời hai hay nhiều phép lặp khác nhau trên cùng một danh sách.
Mục sau sẽ trình bày một phương pháp thiết kế lớp List khác, nó khắc phục được các nhược điểm đã nêu trên.
4.3 CÀI ĐẶT DANH SÁCH BỞI MẢNG ĐỘNG
Trong mục này chúng ta sẽ thiết kế một lớp khác cài đặt KDLTT danh sách, lớp này được đặt tên là Dlist (Dynamic List). Lớp Dlist khác với lớp List đã được trình bày trong mục 4.2 ở hai điểm. Thứ nhất, danh sách được lưu trong mảng được cấp phát động. Thứ hai, các hàm trong bộ công cụ lặp được tách ra và đưa vào một lớp riêng: lớp công cụ lặp trên danh sách, chúng ta sẽ gọi lớp này là DlistIterator. Với cách thiết kế này, chúng ta sẽ khắc phục được các nhược điểm của lớp List đã được nêu ra trong nhận xét ở cuối mục 4.2.
Lớp Dlist chưa ba thành phần dữ liệu: Biến con trỏ element trỏ tới mảng được cấp phát động để lưu các phần tử của danh sách. Biến size lưu cỡ của mảng, và biến last lưu chỉ số cuối cùng mà tại đó mảng chứa phần tử của danh sách.
Lớp Dlist chứa tất cả các hàm thành phần thực hiện các phép toán trên danh sách giống như trong lớp List, trừ ra các hàm công cụ lặp (các hàm này sẽ được đưa vào lớp DlistIterator). Chúng ta đưa vào lớp Dlist hai hàm kiến tạo. Hàm kiến tạo một tham biến nguyên là cỡ của mảng được cấp phát động và hàm kiến tạo copy. Chúng ta cần đưa vào lớp Dlist hàm huỷ để thu hồi bộ nhớ đã cấp phát cho mảng element, khi mà đối tượng không còn cần thiết nữa. Lớp Dlist cũng cần có hàm toán tử gán. Định nghĩa lớp Dlist được cho trong hình 4.3.
template
class DlistIterator ;
// Khai báo trước lớp DlistIterator.
template
class Dlist
{
public:
friend class DlistIterator;
Dlist( )
{element = NULL; size = 0; last = -1; }
DList (int m);
Dlist (const Dlist & L);
~ Dlist( )
{delete [ ] element; }
Dlist & operator = (const Dlist & L);
inline bool Empty( ) const;
inline int Length( ) const;
void Insert(const Item & x, int i);
void Append(const Item & x);
void Delete(int i);
inline Item & Element(int i);
private:
Item* element;
Int size;
Int last;
};
Hình 4.3. Định nghĩa lớp Dlist
Chú ý rằng, trước khi định nghĩa lớp Dlist, chúng ta đã khai báo trước lớp DlistIterator. Khai báo này là cần thiết, bởi vì trong định nghĩa lớp Dlist, chúng ta xác định lớp DlistIterator là bạn của nó.
Sau đây chúng ta sẽ xem xét sự cài đặt các hàm thành phần của lớp Dlist. Các hàm Empty, Length, Delete và Retrieve là hàm hoàn toàn giống n...