TÀI LIỆU: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Chia sẻ: Thu Phương | Ngày: | Loại File: PDF | Số trang:62

Thêm vào BST

Báo xấu

139
lượt xem 30
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dùng C++ để diễn đạt = Có vấn đề? Mã giả (pseudo code). Giả lập, thường là dễ hiểu, không chi tiết đến các kỹ thuật lập trình. Ở cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiên. Hoặc rất chi tiết: như dùng ngôn ngữ tựa Pascal, tựa C++.Kiểu trừu tượng (abstract type): định nghĩa interface (tập các entry). Entry. Tên method. Danh sách tham số hình thức. Đặc tả chức năng. Chưa có dữ liệu bên trong, chưa dùng được. Chỉ dùng để thiết kế ý niệm....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: TÀI LIỆU: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

Giới thiệu A C Môn học giới thiệu: CẤU TRÚC DỮ LIỆU VÀ B Các cấu trúc dữ liệu cơ bản F GIẢI THUẬT (501040) D Các giải thuật điển hình trên các cấu trúc dữ liệu đó Dùng phương pháp hướng đối tượng. E Ngôn ngữ lập trình minh hoạ: G Giới thiệu môn học Mã giả (pseudocode) K C++ (không được giảng dạy chính thức trong môn H học) 2 Giới thiệu m ôn học Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Nội dung Tài liệu tham khảo Chương 1. Tổng quan [1] Kruse, R. L., and Ryba, A. J. 1999. Data Structures Chương 2. Stack and Program Design in C++. Prentice- Hall Inc. Chương 3. Queue [2] Trân, N. N. B. 2001. Giáo trình Cấu trúc Dữ liệu và Chương 4. Stack và Queue liên kết Giải thuật. KhoaCNTT, ĐH Bách KhoaTp.HCM Chương 5. Đệ qui [3] Jesse Liberty, 1997. Teach Yourself C++ in 21 Chương 6. List và String days. ISBN: 0- 672- 31070- 8, SAMS Chương 7. Tìm kiếm [4] Davis Chapman, 1998. Teach Yourself Visual C++ 6 Chương 8. Sắp xếp in 21 days. ISBN: 0- 672- 31240- 9, SAMS Chương 10. Cây nhị phân Chương 11. Cây nhiều nhánh Chương 9. Bảng và truy xuất thông tin 3 4 Giới thiệu m ôn học Giới thiệu m ôn học Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Vấn đề ngôn ngữ lập trình Giải thuật bằng mã giả Ví dụ: Mã giả của bubble sort Dùng C++ để diễn đạt => Có vấn đề? Mã giả (pseudo code) Giải thuật 1 Giải thuật 2 Giả lập, thường là dễ hiểu, không chi tiết đến các kỹ Algorithm Bubble sort Algorithm Bubble sort thuật lập trình Input: The list A of n elements is Input: The list A of n elements is given given Ở cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiên Output: The list A is sorted Output: The list A is sorted Hoặc rất chi tiết: như dùng ngôn ngữ tựa Pascal, tựa C++ 1. for outter in 0..(n- 2) 1. loop for n time 1.1. for inner in 0..(n- 2 - outter) 1.1. for each pair in the list 1.1.1. if Ainner+1 < Ainner 1.1.1. if it is not in ordered 1.1.1.1. swap Ainner, Ainner+1 1.1.1.1. exchange them End Bubble sort End Bubble sort 5 6 Giới thiệu m ôn học Giới thiệu m ôn học Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin 1
So sánh mã giả và NNLT Giải thuật bằng ngôn ngữ lập trình Nhận xét: Ví dụ: Lập trình cụ thể Bubble sort Mã giả 1: gần với cách trao đổi của con người nhất Giải thuật 1: Pascal Giải thuật 2: C++ nhưng khó lập trình nhất procedure BubbleSort(var A: list); v oid BubbleSort(list A) Mã giả 2: dễ lập trình hơn var i,j: int; { Phương pháp: begin int i, j; Đầu tiên: cách giải quyết vấn đề bằng máy tính số for i := 1 to n - 1 do for (i=0; i < n- 2; i++) (giải thuật bằng mã giả) for j := 1 to (n - 1 - i) do for (j=0; j
Nội dung thi Trao đổi phục vụ học tập Hai nội dung chính: Trang Web: Phần lý thuyết: http://www.dit.hcmut.edu.vn/~thang/CTDL Thực hiện giải thuật bằng tay (vẽ hình minh hoạ) Có các mục: hỏi đáp, thông tin chi tiết, lịch giảng dạy Thiết kế cấu trúc dữ liệu theo yêu cầu Cán bộ giảng dạy: Đánh giá độ phức tập giải thuật ThS. Nguyễn Ngô Bảo Trân (tran@dit.hcmut.edu.vn) Phần lập trình: ThS. Bùi Hoài Thắng (thang@dit.hcmut.edu.vn) Trình bày giải thuật chi tiết bằng m ã giả Trợ giảng: Hiện thực bằng ngôn ngữ lập trình C++ Nguyễn Lưu Đăng Khoa (nldkhoa@dit.hcmut.edu.vn) Dương Ngọc Hiếu (dnhieu@dit.hcmut.edu.vn) 13 14 Giới thiệu m ôn học Giới thiệu m ôn học Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin Sinh viên senior Sinh viên senior: A B C D Các buổi tiếp SV phục vụ môn học: T.Thắng: C.Trân: 15 Giới thiệu m ôn học Đ H Bách Khoa Tp.HCM Khoa Công nghệ Thông tin 3
Giải bài toán bằng phần mềm A C 1. Xác định bài toán CẤU TRÚC DỮ LIỆU VÀ B 2. Thiết kế phần mềm F GIẢI THUẬT (501040) D 3. Thiết kế dữ liệu E 4. Thiết kế và phân tích giải thuật 5. Lập trình và gỡ rối G Chương 1: Tổng quan K 6. Kiểm tra phần mềm H 7. Bảo trì 2 Chươ ng 1: Tổng quan Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Kiểu trừu tượng Lập trình hướng đối tượng (OOP) Kiểu trừu tượng (abstract type): định nghĩa Chương trì nh = tập các đối tượng tương tác nhau. interface (tập các entry) Đối tượng (object) = thuộc tí nh + tác vụ local data Entry of object đối tượng T ên method (object) Danh sách tham số hì nh thức Đặc tả chức năng Chưa có dữ liệu bên trong, chưa dùng được entry Chỉ dùng để thiết kế ý niệm local data of operation 3 4 Chươ ng 1: Tổng quan Chươ ng 1: Tổng quan Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Hiện thực và sử dụng Đặc điểm của OOP Class: hiện thực của abstract type Tính bao đóng: Định nghĩ a các dữ liệu Che dấu cấu trúc dữ liệu bên trong. Định nghĩ a các phương thức + hàm phụ trợ (nội bộ) Che dấu cách thức hiện thực đối tượng. Định nghĩ a các phương phức ‘constructor’ và Kế thừa: ‘destructor’ nếu cần Định nghĩ a thêm các dữ liệu và phương thức cần Đối tượng = một instance của một class thiết từ một class có sẵn. Thông điệp (message): Cho phép overwrite/overload. dùng tương tác lẫn nhau = lời gọi phương thức của Cho phép dùng thay thế và khả năng dynamic biding. các đối tượng Bao gộp: Student aStudent; aStudent.print(); Một đối tượng chứa nhiều đối tượng khác. 5 6 Chươ ng 1: Tổng quan Chươ ng 1: Tổng quan Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 1
Cấu trúc của đối tượng Khai báo một class trên C++ khai báo mộ t lớp mới class Student { private: khai báo dữ liệu bên trong int StudentID; Internal data string StudentName; constructor public: copy constructor Internal function Student(); Student(const Student &) destructor method ~Student() overload assignment operator void operator=(const Student &) Internal function phương thức (hành vi) void print(); }; method method void main() { khai báo mộ t đố i tượng Student aStudent; sStudent.print(); gọ i phương thức } 7 8 Chươ ng 1: Tổng quan Chươ ng 1: Tổng quan Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Dùng ghi chú làm rõ nghĩa Dùng ghi chú làm rõ nghĩa – Ví dụ void Life::update() /* Pre: grid đang chứa mộ t trạng thái của thực thể số ng Post: grid sẽ chứa trạng thái tiến hóa mới của thực thể số ng này * / 1. Ghi chú vào đầu mỗi hàm { int row, col; (a) Người lập trì nh, ngày, bản sao int new_grid[maxrow + 2][maxcol + 2]; //Chứa trạng thái mới vào đây for (row = 1; row
Trò chơi Life – Ví dụ Trò chơi Life – Thiết kế phương thức 13 14 Chươ ng 1: Tổng quan Chươ ng 1: Tổng quan Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Trò chơi Life – Đếm số tế bào sống Trò chơi Life – Thiết kế class lâ n c ậ n Mã C++: const int maxrow = 20 const maxcol = 60; count = 0 for (i = row − 1; i
Trò chơi Life – Mã C++ cập nhật Kết luận void Life::update() /* Pre: grid đang chứa mộ t trạng thái của thực thể số ng Post: grid sẽ chứa trạng thái tiến hóa mới của thực thể số ng này * / Sự liên quan giữa CTDL và giải thuật: { int row, col; Cấu trúc dữ liệu cụ thể: chọn giải thuật int new_grid[maxrow + 2][maxcol + 2]; //Chứa trạng thái mới vào đây for (row = 1; row
Mô tả stack A C Một stack là một cấu CẤU TRÚC DỮ LIỆU VÀ B trúc dữ liệu mà việc F GIẢI THUẬT (501040) thêm vào và loại bỏ D được thực hiện tại E một đầu (gọi là đỉnh – G Chương 2: Stack top của stack). K Là một dạng vào sau H ra trước – LIFO (Last In First Out) 2 Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Ví dụ về stack Ứng dụng: Đảo ngược danh sách Yêu cầu: Đảo ngược một danh sách nhập vào Stack rỗng: Giải thuật: Q Đẩy (push) Q vào: 1. Lặp lại n lần A 1.1. Nhập vào một giá trị Q 1.2. Đẩy nó vào stack Đẩy A vào: 2. Lặp khi stack chưa rỗng A 2.1. Lấy một giá trị từ stack Lấy (pop) ra m ột => được A: Q 2.2. In ra Lấy ra m ột => được Q và stack rỗng: Q 3 4 Chương 2: Stack Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đảo ngược danh sách – Ví dụ Đảo ngược danh sách – Mã C++ #include Cần nhập 4 số vào sử dụng STL using namespace std; Nh ập 1 Nh ập 5 Nh ập 7 Nh ập 3 Ban đầu (Standard Template Library) int main( ) { khai báo một stack có kiểu dữ liệu 3 int n; của các phân t ử bên trong là double 7 7 double item; 5 5 5 stack numbers; cout > n; đẩy một số vào trong stack for ( int i = 0; i < n; i++) { Stack đã rỗng Lấy ra => 3 Lấy ra => 7 cin >> item; Lấy ra => 5 Lấy ra => 1 Ngừng kiểm tra xem stack có khác rỗng không numbers.push(item); } 3 lấy giá trị trên đỉnh của stack ra, while (!numbers.empty( )) { stack không đổi 7 7 cout
Stack trừu tượng Kiểu trừu tượng (abstract data type) Một stack kiểu T: ĐN1: Một kiểu (type) một tập hợp Một dãy hữu hạn kiểu T mỗi thành phần của tập hợp này là các giá trị (value) Một số tác vụ: Ví dụ: int, float, char là các kiểu cơ bản 1. Khởi tạo stack rỗng (create) ĐN2: Một dãy của kiểu T 2. Kiểm tra rỗng (empty) có chiều dài bằng 0 là rỗng 3. Đẩy một giá trị vào trên đỉnh của stack (push ) có chiều dài n (n>=1): bộ thứ tự (Sn- 1, t) 4. Bỏ giá trị đang có trên đỉnh của stack (pop ) Sn- 1: dãy có chiều dài n- 1 thuộ c kiểu T 5. Lấy giá trị trên đỉnh của stack, stack không đổi (top ) t là mộ t giá trị thuộ c kiểu T. 7 8 Chương 2: Stack Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Thiết kế stack Thiết kế các phương thức template < class Entry> bool Stack::empty() const; enum Error_code {fail, success, overflow, underflow}; Pre: Không có Post: Tr ả về giá t r ị true nếu stack hiện t ại là rỗng, ngược lại thì t rả về false template < class Entry> template < class Entry> class Stack { Error_code Stack::push(const Entry &item); Pre: Không có public: Post: Nếu stack hiện t ại không đầy, item sẽ được thêm vào đỉnh của stack. Stack(); //constructor Ngược lại trả về giá t rị overflow của kiểu Error_code và stack không đổi. bool empty() const; //kiểm tra rỗng template < class Entry> Error_code push(const Entry &item); //đẩy item vào Error_code Stack::pop() const; Error_code pop(); //bỏ phần tử trên đỉnh Pre: Không có Error_code top(Entry &item); //lấy giá trị trên đỉnh Post: Nếu stack hiện t ại không rỗng, đỉnh của stack hiện t ại sẽ bị hủy bỏ. //khai báo một số phương thức cần thiết khác Ngược lại trả về giá t rị underflow của kiểu Error_code và stack không đổi. private: template < class Entry> //khai báo dữ liệu và hàm phụ trợ chỗ này Error_code Stack::top(Entry &item) const; }; Pre: Không có Post: Nếu stack hiện t ại không rỗng, đỉnh của stack hiện t ại sẽ được chép vào tham biến item. Ngược lại trả về giá t rị f ail của kiểu Error_code. 9 10 Chương 2: Stack Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Hiện thực stack liên tục Khai báo stack liên tục const int maxstack = 10; //small number for testing template < class Entry> class Stack { public: Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(Entry &item) const; Error_code push(const Entry &item); private: int count; Entry entry[maxstack]; }; 11 12 Chương 2: Stack Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 2
Đẩy một phần tử vào stack Bỏ phần tử trên đỉnh stack Giải thuật: Giải thuật: 1. Nếu còn phần tử trong stack 1. Nếu còn chỗ trống trong stack 1.1. Giảm vị trí đỉnh đi 1 1.1. Tăng vị trí đỉnh lên 1 1.2. Giảm số phần tử đi 1 1.2. Chứa giá trị vào vị trí đỉnh của stack 1.3. Tăng số phần tử lên 1 top 7 7 5 top 5 count=2 count=3 1 count=3 count=2 1 13 14 Chương 2: Stack Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Thêm/Bỏ phần tử - Mã C++ Lấy giá trị trên đỉnh stack template < class Entry> Error_code Stack:: push(const Entry &item) { Giải thuật: if (count >= maxstack) return overflow; 1. Nếu còn phần tử trong stack else 1.1. Trả về giá trị tại vị trí đỉnh entry[count++] = item; Mã C++: return success; } template < class Entry> Error_code Stack:: top(Entry &item) { template < class Entry> if (count == 0) Error_code Stack:: pop() { return underflow; if (count == 0) else return underflow; item = entry[count - 1]; else return success; count--; } return success; } 15 16 Chương 2: Stack Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Reverse Polish Calculator Reverse Polish Calculator – Thiết kế chức năng Mô tả bài toán: Tập lệnh: Các toán hạng được đọc vào trước và đẩy vào stack ‘?’: đọc một giá trị rồi đẩy vào stack Khi đọc vào toán tử, lấy hai toán hạng ra từ stack, Toán tử ‘+’, ‘- ’, ‘*’, ‘/’: lấy 2 giá trị trong stack, tí nh tí nh toán với toán tử này, rồi đẩy kết quả vào stack toán và đẩy kết quả vào stack Toán tử ‘=’: in đỉnh của stack ra Thiết kế phần mềm: ‘q’: kết thúc chương trì nh Cần một stack để chứa toán hạng Cần hàm get_command để nhận lệnh từ người dùng Cần hàm do_command để thực hiện lệnh 17 18 Chương 2: Stack Chương 2: Stack Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 3
Reverse Polish Calculator – Reverse Polish Calculator – Ví dụ Hàm get_command char get command( ) { T í nh toán biểu thức: 3 5 + 2 * = char command; bool waiting = true; cout > command; 8 3 3 3 command = tolower(command); if (command == ‘?’ || command == ‘=‘ || command == ‘+’ || Ban đầu Toán tử ? Toán tử ? Toán tử + Đẩy 8 vào command == ‘−’|| command == ‘*’ || command == ‘/’ || Nhập vào 3 Nhập vào 5 Lấy ra 5 và 3 command == ‘q’) waiting = false; Tính 3 + 5 => 8 else { cout
Mô tả queue A C Một queue là một cấu trúc dữ liệu mà việc thêm vào được thực CẤU TRÚC DỮ LIỆU VÀ B hiện ở một đầu (rear) và việc lấy ra được thực hiện ở đầu còn lại (front) F GIẢI THUẬT (501040) D Phần tử vào trước sẽ ra trước – FIFO (First In First Out) E G Chương 3: Queue K H 2 Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Queue trừu tượng Thiết kế queue enum Error_code {fail, success, overflow, underflow}; Một queue kiểu T: template < class Entry> Một dãy hữu hạn kiểu T class Queue { Một số tác vụ: public: Queue(); //constructor 1. Khởi tạo queue rỗng (create) bool empty() const; //kiểm tra rỗng 2. Kiểm tra rỗng (empty) Error_code append(const Entry &item); //đẩy item vào 3. Thêm một giá trị vào cuối của queue (append) Error_code serve(); //bỏ 1 phần tử ở đầu 4. Bỏ giá trị đang có ở đầu của queue (serve) Error_code retrieve(Entry &item); //lấy giá trị ở đầu //khai báo một số phương thức cần thiết khác 5. Lấy giá trị ở đầu của queue, queue không đổi (retrieve) private: //khai báo dữ liệu và hàm phụ trợ chỗ này }; 3 4 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Thiết kế các phương thức Mở rộng queue template < class Entry> bool Queue::empty() const; Pre: Không có Có thêm các tác vụ: Post: Tr ả về giá t r ị true nếu queue hiện tại là rỗng, ngược lại thì trả về false Kiểm tra đầy (full ) template < class Entry> Tính kích thước (size ) Error_code Queue::append(const Entry &item); Giải phóng queue (clear) Pre: Không có Lấy giá trị ở đầu và bỏ ra khỏi queue (serve_and_retrieve) Post: Nếu queue hiện t ại không đầy, item sẽ được thêm vào cuối của queue. Ngược lại trả về giá t rị overflow của kiểu Error_code và queue không đổi. Mã C++: template template < class Entry> Error_code Queue::serve() const; class Extended_queue: public Queue { Pre: Không có public: Post: Nếu queue hiện t ại không rỗng, đầu của queue hiện t ại sẽ bị hủy bỏ. bool full( ) const; Có các khả năng public, Ngược lại trả về giá t rị underflow của kiểu Error_code và queue không đổi. int size( ) const; protected, private template < class Entry> void clear( ); Error_code Queue::retrieve(Entry &item) const; Error_code serve_and_retrieve(Entry &item); Pre: Không có Post: Nếu queue hiện t ại không rỗng, đầu của queue hiện t ại sẽ được chép vào tham }; biến item. Ngược lại trả về giá t rị underflow của kiểu Error_code. 5 6 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 1
Tính thừa hưởng Queue liên tục Dùng một array: Có xu hướng dời về cuối array Dùng tí nh thừa hưởng: Hai cách hiện thực đầu tiên: Extended_queue có đầy đủ các thành phần của Queue Khi lấy một phần tử ra thì đồng thời dời hàng lên một vị trí. Thêm vào đó các thành phần riêng của mình A B C D B C D B C D E Ban đầu Lấy ra 1 phần tử: Thêm vào 1 phần tử dời tất cả về trước Chỉ dời hàng về đầu khi cuối hàng không còn chỗ A B C D B C D B C D E Ban đầu Lấy ra 1 phần tử Thêm vào 1 phần tử: dời tất cả về trước để trống chỗ thêm vào 7 8 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Array vòng với ngôn ngữ C++ Queue là array vòng (circular array) Xem array như là một vòng: phần tử cuối của array nối với phần tử đầu của array Tính toán vị trí kề: i = ((i + 1) == max) ? 0 : (i + 1); if ((i + 1) == max) i = 0; else i = i + 1; i = (i + 1)%max; 9 10 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Điều kiện biên của queue vòng Một số cách hiện thực queue liên tục Một array với front là phần tử đầu và tất cả các phần tử sẽ được dời lên khi lấy ra một phần tử. Một array có hai chỉ mục luôn tăng chỉ đến phần tử đầu và cuối. Một array vòng có chỉ mục front và rear và một ô luôn trống. Một array vòng có chỉ mục front và rear và một cờ (flag) cho biết queue là đầy (rỗng) chưa. Một array vòng với chỉ mục front và rear có các giá trị đặc biệt cho biết queue đang rỗng. Một array v òng v ới chỉ mục front v à rear v à một số chứa số phần tử của queue. 11 12 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 2
Hiện thực queue liên tục Khởi tạo và kiểm tra rỗng const int maxqueue = 10; // small value for testing Khởi tạo: template < class Entry> template < class Entry> class Queue { Queue::Queue( ) { public: count = 0; Queue( ); bool empty( ) const; rear = maxqueue − 1; Error_code serve( ); front = 0; Error_code append(const Entry &item); } Error_code retrieve(Entry &item) const; Kiểm tra rỗng: protected: Dùng biến count để int count; template biết số phần tử int front, rear; trong queue bool Queue::empty( ) const { Entry entry[maxqueue]; return count == 0; }; } 13 14 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Thêm một giá trị vào queue Loại một giá trị khỏi queue Giải thuật: Giải thuật: 1. Nếu hàng rỗng 1. Nếu hàng đầy 1.1. Báo lỗi underflow 1.1. Báo lỗi overflow 2. Tính toán vị trí đầu mới theo array vòng 2. Tính toán vị trí cuối mới theo array vòng 3. Giảm số phần tử đi 1 3. Gán giá trị vào vị trí cuối mới này 3. Báo success 4. Tăng số phần tử lên 1 4. Báo success front rear front rear D A B C D A B C 15 16 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Thêm/loại một giá trị – Mã C++ Ứng dụng: Giả lập phi trường template < class Entry> Error_code Queue::append(const Entry &item) { M ô tả: if (count >= maxqueue) return overflow; 1. Sử dụng hàng đợi runway cho việc cất và hạ cánh. count++; rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1); 2. Một máy bay có thể cất hoặc hạ cánh trong một entry[rear] = item; đơn vị thời gian. return success; } 3. T ại một thời điểm, số máy bay đến là ngẫu nhiên. 4. Máy bay hạ cánh được ưu tiên trước máy bay cất template < class Entry> cánh. Error_code Queue::serve() { if (count
Giả lập phi trường – Hàng đợi Giả lập phi trường – Hạ cánh enum Runway_activity {idle, land, takeoff}; Error_code Runway :: can_land(const Plane &current) { Error_code result; class Runway { if (landing.size( ) < queue_limit) public: result = landing.append(current); Runway(int limit); else Error_code can_land(const Plane &current); result = fail; Error_code can_depart(const Plane &current); num_land_requests++; Runway_activity activity(int time, Plane &moving); if (result != success) void shut_down(int time) const; num_land_refused++; private: else Extended queue landing; num_land_accepted++; Extended queue takeoff; return result; int queue_limit; } … }; 19 20 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Giả lập phi trường – Xử lý Giả lập phi trường – Giả lập for ( int current_time = 0; current_time < end_time; current_time++) { int number_arrivals = variable.poisson(arrival_rate); for ( int i = 0; i < number_arrivals; i++) { Runway_activity Runway::activity(int time, Plane &moving) { Plane current_plane(flight_number++, current_time, arriving); Runway_activity in_progress; if (small_airport.can_land(current_plane) != success) if (!landing.empty( )) { current_plane.refuse( ); landing.retrieve(moving); } in_progress = land; int number_departures = variable.poisson(departure_rate); landing.serve( ); for ( int j = 0; j < number_departures; j++) { } else if (!takeoff.empty( )) { Plane current_plane(flight_number++, current_time, departing); takeoff.retrieve(moving); if (small_airport.can_depart(current_plane) != success) in_progress = takeoff; current_plane.refuse( ); } takeoff.serve( ); Plane moving_plane; } else sw itch (small_airport.activity(current_time, moving_plane)) { in_progress = idle; case land: moving_plane.land(current_time); break; return in_progress; case takeoff: moving_plane.fly(current_time); break; } case idle: run_idle(current_time); } } 21 22 Chươ ng 3: Queue Chươ ng 3: Queue Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 4
Con trỏ A C CẤ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 2 Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Biểu diễn con trỏ bằng C++ Sử dụng con trỏ trong C++ Địa chỉ của biến: Khai báo biến: Item * item_ptr1, * item_ptr2; Biến: int_ptr = &x; T ạo m ới đối tượng: Array: arr_ptr = an_array; item_ptr1 = new Item; Dynamic array: Hủy bỏ đối tượng: Trong C++, array có thể được quản lý như m ột con delete item_ptr1; trỏ và ngược lại Sử dụng: Ví dụ: *item_ptr1 = 1378; int arr[3] = {0, 1, 2, 3}; cout StudentID; int *arr_ptr = arr; Con trỏ NULL: //in ra 0 – 1 – 2 item_ptr2 = NULL; cout
Thiết kế node liên kết bằng C++ Ví dụ với node liên kết template < class Entry> Node first_node(‘a’); struct Node { Entry entry; // data members Node *p0 = &first_node; Node *next; Node *p1 = new Node(‘b’); Node( ); // constructors p 0- >next = p1; Node(Entry item, Node *add on = NULL); Node *p2 = new Node(‘c’, p0); }; p1- >next = p2; p1 p2 first_node p0 a b c 7 8 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Stack liên kết Khai báo stack liên kết template < class Entry> 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 &copy); ~Stack(); void operator=(const Stack &copy); protected: Node *top_node; }; 9 10 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Thêm vào một stack liên kết Bỏ đỉnh của một stack liên kết Giải thuật Giải thuật: 1. Tạo ra một node mới với giá trị cần thêm vào 1. Gán một con trỏ để giữ đỉnh của stack 2. Trỏ nó đến đỉnh hiện tại của stack 2. Trỏ đỉnh của stack vào node ngay sau đỉnh hiện tại 3. Trỏ đỉnh của stack vào node mới 3. Xóa node cũ đi new_top top_node new node old top middle old last top_node old_top old top middle last 11 12 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 2
Thêm/Bỏ đỉnh của một stack liên kết Sự không an toàn con trỏ trong C++ – Mã C++ template < class Entry> Kết thúc biến stack nhưng bộ nhớ còn lại: Error_code push(const Entry &item) { delete stack0; Node *new_top = new Node(item, top_node); if (new_top == NULL) return overflow; stack0 top_node = new_top; top middle last } Gán hai stack: cả hai dùng chung một vùng dữ liệu template < class Entry> stack2 = stack1; Error_code pop( ) { stack2 Node *old_top = top_node; if (top_node == NULL) return underflow; top middle last top_node = old_top- >next; stack1 delete old_top; } top middle last 13 14 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Xóa vùng dữ liệu đang có Đảm bảo an toàn con trỏ trong C++ Destructor: Giải thuật: Sẽ được gọi ngay trước khi đối tượng kết thúc thời gian sống 1. Trong khi stack chưa rỗng Dùng xóa hết vùng dữ liệu 1.1. Bỏ đỉnh của stack Copy constructor: Mã C++: Sẽ được gọi khi khởi tạo biến lúc khai báo, hoặc truyền dữ liệu bằng tham trị while (!empty()) Sao chép nguồn thành một vùng dữ liệu mới pop(); Assignment operator: Sẽ được gọi khi gán đối tượng này vào đối tượng khác Xóa vùng dữ liệu của đích và đồng thời sao chép nguồn thành một vùng dữ liệu mới 15 16 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Sao chép vùng dữ liệu Sao chép vùng dữ liệu – Ví dụ copy.top_node Giải thuật: a b c 1. Tạo một đỉnh của danh sách mới với dữ liệu của đỉnh copy_node nguồn 2. Giữ một con trỏ đuôi chỉ vào cuối danh sách mới 2. Duyệt qua danh sách nguồn new_copy 2.1. Tạo một node mới với dữ liệu từ node nguồn hiện tại 2.2. Nối vào cuối danh sách mới 2.3. Con trỏ đuôi là node mới new_top a b c 17 18 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 3
Sao chép vùng dữ liệu – Mã C++ Queue liên kết Thiết kế: Node *new_top, *new_copy, *copy_node = copy.top_node; if (copy_node == NULL) new_top = NULL; Dùng hai con trỏ chỉ đến đầu và cuối của danh sách else { dữ liệu (front và rear) rear // Sao chép vùng dữ liệu thành danh sách mới front new_copy = new_top = new Node(copy_node- >entry); while (copy_node- >next != NULL) { copy_node = copy_node- >next; front middle last new_copy- >next = new Node(copy_node- >entry); new_copy = new_copy- >next; Khởi tạo rỗng: gán cả front và rear về NULL } } front rear clear(); //xóa rỗng dữ liệu hiện tại trước top_node = new_top; // thay thế dữ liệu bằng danh sách mới. 19 20 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Khai báo Queue liên kết Thêm phần tử vào một queue liên kết template < class Entry> class Queue { Giải thuật: public: 1. Tạo một node mới với dữ liệu cần thêm vào Queue( ); 2. Nếu queue đang rỗng bool empty( ) const; Error_code append(const Entry &item); 2.1. front và rear là node mới new_rear Error_code serve( ); 3. Ngược lại Error_code retrieve(Entry &item) const; 3.1. Nối node mới vào sau rear ~Queue( ); 3.2. rear chính là node mới Queue(const Queue &original); new_last void operator = (const Queue &original); rear protected: front Node *front, *rear; }; front middle last 21 22 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Thêm/Bỏ phần tử của một queue liên Bỏ phần tử khỏi một queue liên kết kết – Mã C++ template < class Entry> Error_code append(const Entry &item) { Node *new_rear = new Node(item); Giải thuật: if (new_rear == NULL) return overflow; 1. Dùng mộ t con trỏ để giữ lại front hiện tại if (rear == NULL) front = rear = new_rear; 2. Nếu queue có mộ t phần tử else { rear- >next = new_rear; rear = new_rear; } 2.1. Gán front và rear về NULL return success; 3. Ngược lại } 3.1. Trỏ f ront đến nút kế sau template < class Entry> 4. Xóa nút cũ đi rear Error_code serve() { if (front == NULL) return underflow; front Node *old_front = front; front = old_front- >next; front middle last if (front == NULL) rear = NULL; delete old_front; old_front return success; } 23 24 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 4
Ứng dụng: tính toán đa thức Kích thước của một queue liên kết Giải thuật: Dùng lại bài reverse Polish calculator Thiết kế cấu trúc dữ liệu cho đa thức: 1. Khởi tạo biến đếm là 0 M ộ t bản ghi có thành phần mũ và hệ số 2. Duyệt qua danh sách M ộ t danh sách các bản ghi theo thứ tự giảm của số mũ 2.1. Đếm tăng số phần tử lên 1 Có thể dùng queue Mã C++: Node *window = front; int count = 0; while (window != NULL) { window = window- >next; count++; } return count; 25 26 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Ví dụ cộng hai đa thức bằng giải Giải thuật cộng hai đa thức 1 thuật 1 Algorithm Equals_sum1 p = 3x6 – 2x4 + x3 + 4 Input: p,q là hai đa thức < - 2.0, 4> Output: đa thức tổng 1. Trong khi p và q chưa rỗng q = 5x5 + 2x4 + 4x2 + 2x 1.1. Lấy phần tử front của p và q thành p_term, q_term 1.2. Nếu bậc của p_term lớn (hoặc nhỏ) hơn bậc của q_term 1.2.1. Đẩy p_term (hoặc q_term) vào kết quả 1.2.2. Bỏ phần tử đầu trong p (hoăc trong q) 1.3. Ngược lại p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4 1.3.1. Tính hệ số mới cho số hạng này 1.3.2. Đẩy vào kết quả 2. Nếu p (hoặc q) chưa rỗng 2.1. Đẩy toàn bộ p (hoặc q) vào kết quả End Equals_sum1 27 28 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Mã C++ cộng hai đa thức 1 Giải thuật cộng hai đa thức 2 Algorithm Equals_sum2 Term p_term, q_term; Input: p,q là hai đa thức while (!p.empty( ) && !q.empty( )) { Output: đa thức tổng p.retrieve(p_term); q.retrieve(q_term); Algorithm Bac_da_thuc if (p_tem.degree > q_term.degree) { 1. Trong khi p hoặc q chưa rỗng Input: đa thức p.serve(); append(p_term); 1.1. Nếu bậc của p lớn hơn bậc của q Output: bậc của đa thức } else if (q_term.degree > p_term.degree) { 1.1.1. Lấy từ p thành term q.serve(); append(q_term); 1.1.2. Đẩy term vào kết quả 1. Nếu đa thức rỗng } else { 1.2. Nếu bậc của q lớn hơn bậc của p 1.1. Trả về - 1 p.serve(); q.serve(); 1.2.1. Lấy từ q thành term 2. Trả về bậc của phần tử đầu if (p_term.coefficient + q_term.coefficient != 0) { 1.2.2. Đẩy term vào kết quả Term answer_term(p_term.degree, 1.3. Ngược lại End Bac_da_thuc p_term.coefficient + q_term.coefficient); 1.3.1. Lấy p_term, q_term từ p và q append(answer_term); 1.3.2. Tính tổng hai hệ số }}} 1.3.3. Nếu hệ số kết quả khác không while (!p.empty()) { p.serve_and_retrieve(p_term); append(p_term); } 1.3.3.1. Đẩy vào kết quả while (!q.empty()) { q.serve_and_retrieve(q_term); append(q_term); } End Equals_sum2 29 30 Chươ ng 4: Stack và Q ueue liên kết Chươ ng 4: Stack và Q ueue liên kết Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin Đ H Bách Khoa Tp.HCM Khoa C ông nghệ Thông tin 5