Bài giảng Cấu trúc dữ liệu và giải thuật chương 3: Danh sách, ngăn xếp và hàng đợi

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Lý thuyết Phần 2 (Chương 3) Danh sách, Ngăn xếp và Hàng đợi „ Giới thiệu khái niệm ADT (Kiểu dữ liệu trừu tượng – Abstract Data Type) „ Danh sách N ă ế„ g n x p „ Hàng đợi Vũ Anh Dũng - Khoa CNTT 2 Kiểu dữ liệu trừu tượng „ Là tập các đối tượng tương ứng với tập các thao tác „ Danh sách, tập hợp,… có thể coi là kiểu dữ liệu trừu tượng „ C++ cho phép viết các thao tác và được gọi là á hươ thứ c c p ng c „ Ví dụ : Tập hợp là một ADT với các thao Vũ Anh Dũng - Khoa CNTT 3 tác : add, remove, find, union,… Danh sách (List) „ Danh sách tổng quát có dạng A0,A1, A2,…, AN-1 „ Kích thước N và nếu N=0 : danh sách rỗng Một ố th tá hổ biế„ s ao c p n : „ printList : in danh sách „ makeEmpty : làm rỗng danh sách „ find : trả về vị trí lần đầu tiên một phần tử xuất hiện trong danh sách Vũ Anh Dũng - Khoa CNTT 4 Danh sách (List) „ Một số thao tác phổ biến (tiếp) : „ findKth : trả về phần tử ở vị trí cụ thể „ insert : thêm 1 phần tử vào danh sách „ remove : xóa 1 phần tử khỏi danh sách Vũ Anh Dũng - Khoa CNTT 5 Sử dụng mảng để cài đặt danh sách „ Các thao tác : „ printList: thực hiện trong thời gian tuyến tính „ findKth : chiếm thời gian hằng số „ insert và remove đòi hỏi tốn kém nhiều thời gian (Ví dụ : trường hợp thêm vào vị trí đầu tiên là tốn kém thời gian nhất) „ Trường hợp dùng mảng lưu trữ danh sách Vũ Anh Dũng - Khoa CNTT 6 không phải là lựa chọn tốt nhất Danh sách liên kết(LinkedList) „ Hình ảnh về danh sách liên kết ế„ Danh sách liên k t tránh được việc chèn và xóa phần tử theo chi phí tuyến tính (dịch ể ế ố ầchuy n liên ti p 1 s ph n tử) Vũ Anh Dũng - Khoa CNTT 7 Danh sách liên kết(LinkedList) „ Danh sách liên kết : „ Chuỗi các nút (node) „ Không cần lưu trữ liền kề trong bộ nhớ „ Mỗi nút chứa phần tử và liên kết đến nút tiếp theo (next link) „ Nút cuối cùng có next link là NULL Vũ Anh Dũng - Khoa CNTT 8 Danh sách liên kết(LinkedList) „ Phép xóa phần tử (remove): ầ„ Phép thêm ph n tử (insert): Vũ Anh Dũng - Khoa CNTT 9 Danh sách liên kết(LinkedList) „ Loại bỏ mục cuối cùng : „ Phải tìm mục phía trước mục cuối cùng „ Đổi liên kết next của nó thành NULL „ Cập nhật liên kết duy trì nút cuối cùng „ Có thể dùng ds liên kết đôi (nối kép): Vũ Anh Dũng - Khoa CNTT 10 Giới thiệu STL „ Ba thành phần chính của STL : „ Container (Collection) : các cấu trúc dữ liệu sẵn có như List, Vector, Set,…. „ Iterator : giống con trỏ, dùng để truy cập các phần tử trong Container „ Algorithms : Các thuật toán thao tác dữ liệu, tìm kiếm, sắp xếp, ….. Vũ Anh Dũng - Khoa CNTT 11 Vector „ Lợi thế của việc sử dụng vector là nó có thể đánh chỉ số trong thời gian hằng. „ Bất lợi của của nó là thao tác chèn thêm các mục mới và loại bỏ các mục hiện có là tốn kém, trừ khi những thay đổi này được thực hiện ở cuối vector . Vũ Anh Dũng - Khoa CNTT 12 List „ Lợi thế của việc sử dụng list là việc chèn thêm mục mới và việc loại bỏ các mục hiện có là chi phí thời gian thấp „ Bất lợi là danh sách không dễ dàng có thể đánh chỉ số. Vũ Anh Dũng - Khoa CNTT 13 Vector và List trong STL „ Cả vector và list đều có một số phương thức chung : „ int size( ): trả về kích thước hiện tại của đối tượng chứa(container). „ void clear( ): xóa toàn bộ container. „ bool empty( ): trả về true nếu đối tượng chứa không bao chứa phần tử nào, và false nếu ngược lại. Vũ Anh Dũng - Khoa CNTT 14 Vector và List trong STL „ void push_back( const Object & x ): thêm x vào cuối danh sách. ố ố„ void pop_back( ): loại bỏ đ i tượng ở cu i danh sách. „ const Object & back( ) const: trả về đối tượng ở cuối của danh sách (một hàm biến đổi trả về một tham chiếu cũng được cung cấp). „ const Object & front ( ) const: trả về đối tượng ở đầu của ế ổ ề ếdanh sách (một hàm bi n đ i trả v một tham chi u cũng được cung cấp). Vũ Anh Dũng - Khoa CNTT 15 Vector và List trong STL „ Hai phương thức sau đây chỉ được cung cấp cho list (nối kép): „ void push_front( const Object & x ): thêm x vào đầu danh sách. „ void pop_front ( ): loại bỏ đối tượng ở đầu của danh sách. Vũ Anh Dũng - Khoa CNTT 16 Vector và List trong STL „ Các phương thức của Vector: „ v.[idx]: trả về đối tượng ở vị trí idx trong vector, không có sự kiểm tra ranh giới. „ v.at(int idx): trả về đối tượng ở vị trí idx trong vector „ int capacity( ): kích thước có thể lưu trữ t ớ khi ấ hát l i ấ hát l i ẽ tă ấ đôirư c c p p ạ , c p p ạ s ng g p . „ void reserve(int newCapacity): thiết lập dung lượng mới Vũ Anh Dũng - Khoa CNTT 17 . Iterator „ Trên danh sách đòi hỏi khái niệm về vị trí, trong STL vị trí được đại diện bởi iterator „ Trong list, vị trí được thể hiện bởi list::iterator „ Trong vector, vị trí được thể hiện bởi vector::iterator Vũ Anh Dũng - Khoa CNTT 18 Iterator „ Trong STL list và các containers class trong TLD, đều có hai phương thức : „ iterator begin( ) trả về iterator đầu tiên „ iterator end( ) trả về iterator ối ùcu c ng Vũ Anh Dũng - Khoa CNTT 19 Iterator „ Các phép toán trên iterator „ itr++ và ++itr: chuyển iterator itr tới vị trí tiếp theo *itr: truy cập đến phần tử được trỏ tới„ ở vị trí của iterator itr „ Ví dụ : for( vector::iterator itr = v.begin( ); itr != v.end( ); ++itr ) Vũ Anh Dũng - Khoa CNTT 20 cout << *itr << endl; Iterator „ Ba thao tác phổ biến nhất đòi hỏi các iterator đó là thêm và loại bỏ khỏi danh sách (hoặc vector hoặc list) „ iterator insert(iterator pos, const Object &x): thêm x vào danh sách, trước vị trí được đưa ra bởi iterator pos. „ iterator erase( iterator pos ): loại bỏ đối tượng ở vị trí được cho bởi iterator, ề ế Vũ Anh Dũng - Khoa CNTT 21 trả v iterator là vị trí ti p theo Iterator „ Ba thao tác phổ biến nhất đòi hỏi các iterator đó là thêm và loại bỏ khỏi danh sách (hoặc vector hoặc list) (tiếp) „ iterator erase(iterator start, iterator end):loại bỏ tất cả các mục bắt đầu ở vị trí start, cho tới nhưng không bao gồm end Vũ Anh Dũng - Khoa CNTT 22 Xóa các phần tử lẻ sử dụng Iterator 1 template 2 void removeEveryOtherItem( Container & lst ) 3 { 4 typename Container:iterator itr = lst.begin( ); 5 while ( itr != lst.end( ) ) 6 { 7 itr = lst.erase( itr ); 9 if( itr != lst.end( ) ) 10 ++itr; 11 } 12 } Vũ Anh Dũng - Khoa CNTT 23 Const_Iterator • iterator begin( ) • const_iterator begin( ) const • iterator end( ) • const_iterator end( ) const void print( const list & lst, ostream & out = cout ) { typename Container::iterator itr = lst.begin( ); while( itr != lst.end( ) ) { *i dlout << tr << en ; *itr = 0; // Chỗ này có thể bị lỗi nếu dùng const_iterator itr++; } Vũ Anh Dũng - Khoa CNTT 24 } In một Collection 1 template 2 void printCollection( const Container & c, ostream & out = cout ) 3 { i4 f( c.empty( ) ) 5 out << "(empty)"; 6 else 7 { 8 typename Container::const_iterator itr = c.begin( ); 9 out << "[ " << *itr++; // In ra mục đầu tiên 10 11 while ( itr != c.end( ) ) 12 out << ", " << *itr++; 13 out << " ]" << endl; 14 } 15 } Vũ Anh Dũng - Khoa CNTT 25 In một đối tượng chứa bất kỳ Cài đặt Vector „ Mảng đơn giản là một biến con trỏ trỏ tới một khối bộ nhớ; kích thước mảng thực sự phải được chỉ rõ. „ Khối bộ nhớ có thể được cấp phát bằng new(), ằnhưng sau đó phải được giải phóng b ng delete(). „ Khối bộ nhớ không thể thay đổi kích thước được ( h khối i l hể đ lấn ưng một mớ và ớn có t ược y ra và được khởi tạo bằng khối cũ, và sau đó khối cũ có thể được giải phóng) Vũ Anh Dũng - Khoa CNTT 26 . Cài đặt Vector „ 1. Vector sẽ duy trì mảng gốc (bằng một biến con trỏ trỏ tới khối bộ nhớ được cấp phát), dung lượng mảng và số hiệ thời đ l t ữ t V tmục n ược ưu r rong ec or. „ 2. Vector sẽ thi hành ba hàm quan trọng : hàm tạo sao chép và toán tử =, và sẽ cung cấp một hàm hủy. „ 3. Vector sẽ cung cấp một thủ tục resize sẽ thay đổi (thường là thành một con số lớn hơn) kích thước của V t à ột thủ t ẽ th đổi (th ờ là thà hec or v m ục reserve s ay ư ng n một con số lớn hơn) dung lượng của Vector. Dung lượng được thay đổi bằng cách giành lấy một khối bộ nhớ mới Vũ Anh Dũng - Khoa CNTT 27 của mảng gốc, sao chép khối cũ vào trong khối mới, và phục hồi khối cũ Cài đặt Vector (Xem Vector_Code) „ 4. Vector sẽ cung cấp một cài đặt của toán tử [] (như được nhắc đến trong Phần 1.7.2, toán tử [] thường được cài đặt ới ả hiê bả hà t ậ à hà biế đổi)v c p n n m ruy c p v m n . „ 5. Vector sẽ cung cấp các thủ tục cơ bản, chẳng hạn như size, empty, clear (chúng thường là các câu lệnh một dòng), back, pop_back, và cả push_back. Thủ tục push_back sẽ gọi reserve nếu kích thước và dung lượng là như nhau . „ 6. Vector sẽ cung cấp sự hỗ trợ cho iterator và const_iterator, và các phương thức begin và end liên quan. Vũ Anh Dũng - Khoa CNTT 28 Cài đặt List (Xem List_Code) „ 1. Lớp List, nó sẽ chứa các liên kết tới cả hai đầu, kích thước của danh sách, và một lượng lớn các phương thức. „ 2 Lớp Node nó có khả năng là một private. , nested class. Một nút bao chứa dữ liệu và các con trỏ trỏ tới nút phía trước và nút kế tiếp , cùng với các hàm tạo thích hợp. Vũ Anh Dũng - Khoa CNTT 29 Cài đặt List „ 3. Lớp const_iterator, nó trừu tượng hóa khái niệm vị trí, và là public nested class. const_iterator lưu trữ một con trỏ trỏ tới nút “hiện tại”, và cung cấp sự thi hành của các thao tác iterator cơ sở, tất cả dưới dạng các toán tử được nạp chồng chẳng hạn như =, ==, !=, và ++. „ 4. Lớp iterator, nó trừu tượng hóa khái niệm vị trí, và là public nested class. iterator có chức năng giống với const iterator, ngoại trừ toán tử * _ trả về một tham chiếu tới mục đang được xem, thay vì một tham chiếu hằng tới mục đó. Một vấn đề quan trọng về mặt kỹ thuật đó là một iterator có thể được sử dụng trong bất cứ thủ tục nào yêu cầu một const_iterator, nhưng ngược lại thì không đúng. Nói cách khác, iterator “là một” const_iterator. Vũ Anh Dũng - Khoa CNTT 30