Cấu trúc dữ liệu và giải thuật - chương 4

Chương 4 của bộ slide bài giảng đầy đủ về môn CTDL & GT của trường ĐHBK TP.HCM. Trình bày ngắn gọn dễ hiểu với những hiệu ứng minh họa sinh động. Giúp các bạn biết thêm về stack và queue liên kết là như thế nào? Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - chương 4 A CCẤU TRÚC DỮ LIỆU VÀ B F GIẢI THUẬT (501040) D E G Chương 4: Stack và Queue liên K kết H Con trỏ 2 Chương 4: Stack và Queue liên kết Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Biểu diễn con trỏ bằng C++ Khai báo biến: Item * item_ptr1, * item_ptr2; Tạo mới đối tượng: item_ptr1 = new Item; Hủy bỏ đối tượng: delete item_ptr1; Sử dụng: *item_ptr1 = 1378; cout StudentID; Con trỏ NULL: item_ptr2 = NULL; 3 Chương 4: Stack và Queue liên kết Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Sử dụng con trỏ trong C++ Địa chỉ của biến: Biến: int_ptr = &x; Array: arr_ptr = an_array; Dynamic array: Trong C++, array có thể được quản lý như một con trỏ và ngược lại Ví dụ: int arr[3] = {0, 1, 2, 3}; int *arr_ptr = arr; //in ra 0 – 1 – 2 cout Gán con trỏ trong C++ Gán nội dung: bình thường Gán con trỏ: nguy hiểm 5 Chương 4: Stack và Queue liên kết Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Thiết kế node liên kết Cần: Dữ liệu Con trỏ để trỏ đến node sau Constructor 6 Chương 4: Stack và Queue liên kết Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Thiết kế node liên kết bằng C++ template struct Node { Entry entry; // data members Node *next; Node( ); // constructors Node(Entry item, Node *add on = NULL); }; 7 Chương 4: Stack và Queue liên kết Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Ví dụ với node liên kết Node first_node(‘a’); Node *p0 = &first_node; Node *p1 = new Node(‘b’); p0->next = p1; Node *p2 = new Node(‘c’, p0); p1->next = p2; p1 p2 first_node p0 a b c 8 Chương 4: Stack và Queue liên kết Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Stack liên kết 9 Chương 4: Stack và Queue liên kết Khoa Công nghệ Thông tinĐH Bách Khoa Tp.HCM Khai báo stack liên kết template class Stack { public: Stack( ); bool empty( ) const; Error_code push(const Entry &item); Error_code pop( ); Error_code top(Entry &item) const; Stack(const Stack ©); ~Stack(); void operator=(const Stack ©); protected: Node *top_node; }; 10 ...