Mục lục bài họcĐang ở d05-b1
Recursion, Stacks, Queues and Linked Lists
Recursion. A recursive sub-program calls itself on a smaller version of the same problem. Every correct recursion needs two parts: a base case that returns without recursing, and a recursive case that moves strictly towards the base case. Omitting either produces infinite recursion. Recursion is implemented using the call stack: each call places a new frame holding its parameters, local variables and return address, and the frames are removed in reverse order as the calls return. This is why very deep recursion causes a stack overflow, and why an equivalent iterative solution generally uses less memory. Recursion is chosen when the problem itself is defined recursively — tree traversal, divide and conquer, backtracking — because the code then mirrors the definition.
Static and dynamic structures. A static structure such as an array has its size fixed when it is created: memory is allocated once, elements are contiguous, and any element can be reached directly from its index. A dynamic structure such as a linked list grows and shrinks at run time, with each node allocated as needed. The trade-off is fundamental: arrays give constant-time access by index but cannot grow and waste space if over-allocated; linked lists grow freely and allow insertion in constant time once the position is known, but require extra memory for pointers and can only be reached by following the chain from the start.
Stacks. A stack adds and removes at the same end, so it is last in, first out. Its operations are push, pop, isEmpty and often peek. It is the correct structure whenever a program must return to where it just came from: the call stack itself, undo functionality, checking balanced brackets, evaluating expressions in reverse Polish notation, and backtracking through a maze.
Queues. A queue adds at one end and removes at the other, so it is first in, first out. Its operations are enqueue, dequeue, isEmpty. It is the correct structure whenever items must be served in the order they arrived: print spooling, process scheduling, buffering between a fast producer and a slow consumer, and breadth-first traversal. A circular queue lets the pointers wrap around to the start of the array so that positions freed at the front can be reused, which prevents the queue reporting itself full while space remains.
Linked lists. Each node holds data and a pointer to the next node; the last pointer is null. A doubly linked list also points backwards, allowing traversal in both directions at the cost of an extra pointer per node. A circular linked list has the last node point back to the first.
Đệ quy. Một chương trình con đệ quy gọi lại chính nó trên một phiên bản nhỏ hơn của cùng bài toán. Mọi đệ quy đúng đều cần hai phần: một trường hợp cơ sở trả về mà không gọi tiếp, và một trường hợp đệ quy tiến một cách chắc chắn về phía trường hợp cơ sở. Thiếu một trong hai sẽ gây đệ quy vô hạn. Đệ quy được cài đặt bằng ngăn xếp lời gọi: mỗi lời gọi đặt lên đó một khung mới chứa tham số, biến cục bộ và địa chỉ trở về, và các khung được gỡ theo thứ tự ngược lại khi các lời gọi trả về. Đây là lý do đệ quy quá sâu gây tràn ngăn xếp, và cũng là lý do một lời giải lặp tương đương thường tốn ít bộ nhớ hơn. Đệ quy được chọn khi bản thân bài toán được định nghĩa một cách đệ quy — duyệt cây, chia để trị, quay lui — vì khi đó đoạn mã phản chiếu đúng định nghĩa.
Cấu trúc tĩnh và cấu trúc động. Cấu trúc tĩnh như mảng có kích thước cố định ngay khi tạo: bộ nhớ được cấp một lần, các phần tử nằm liền kề, và truy cập trực tiếp được tới bất kỳ phần tử nào từ chỉ số. Cấu trúc động như danh sách liên kết lớn lên và co lại lúc chạy, mỗi nút được cấp phát khi cần. Sự đánh đổi ở đây là căn bản: mảng cho truy cập theo chỉ số trong thời gian hằng số nhưng không lớn lên được và lãng phí bộ nhớ nếu cấp phát dư; danh sách liên kết lớn lên tự do và cho phép chèn trong thời gian hằng số một khi đã biết vị trí, nhưng tốn thêm bộ nhớ cho các con trỏ và chỉ tới được phần tử bằng cách đi lần theo chuỗi từ đầu.
Ngăn xếp. Ngăn xếp thêm và lấy ở cùng một đầu, nên nó theo nguyên tắc vào sau ra trước. Các thao tác của nó là đẩy vào, lấy ra, kiểm tra rỗng và thường có thêm xem đỉnh. Đây là cấu trúc đúng mỗi khi chương trình phải quay lại đúng chỗ vừa rời đi: chính ngăn xếp lời gọi, chức năng hoàn tác, kiểm tra dấu ngoặc cân đối, tính biểu thức dạng hậu tố, và quay lui khi tìm đường trong mê cung.
Hàng đợi. Hàng đợi thêm ở một đầu và lấy ở đầu kia, nên nó theo nguyên tắc vào trước ra trước. Các thao tác của nó là đưa vào, lấy ra và kiểm tra rỗng. Đây là cấu trúc đúng mỗi khi các phần tử phải được phục vụ theo thứ tự tới: hàng chờ in, lập lịch tiến trình, làm bộ đệm giữa một bên sản xuất nhanh và một bên tiêu thụ chậm, và duyệt theo chiều rộng. Hàng đợi vòng cho các con trỏ quay về đầu mảng khi chạm cuối, nhờ đó dùng lại được các ô đã trống ở phía đầu và tránh việc hàng đợi tự báo đầy trong khi vẫn còn chỗ.
Danh sách liên kết. Mỗi nút chứa dữ liệu và một con trỏ tới nút kế tiếp; con trỏ của nút cuối là rỗng. Danh sách liên kết đôi có thêm con trỏ ngược, cho phép duyệt theo cả hai chiều với cái giá là một con trỏ phụ trên mỗi nút. Danh sách liên kết vòng có nút cuối trỏ ngược về nút đầu.
Một hàm đệ quy tính tổng các số từ 1 tới N. Với N bằng 10 nó chạy tốt; với N bằng 500 000 chương trình dừng với lỗi tràn ngăn xếp. Giải thích, viết phiên bản lặp, và nêu khi nào vẫn nên dùng đệ quy.
Vì sao tràn ngăn xếp. Mỗi lời gọi hàm đặt lên ngăn xếp lời gọi một khung chứa tham số N của lời gọi đó, các biến cục bộ, và địa chỉ để trở về sau khi hoàn thành. Với đệ quy tính tổng, lời gọi cho N không thể trả về trước khi lời gọi cho N trừ một trả về, nên tại thời điểm sâu nhất có đồng thời N khung nằm trên ngăn xếp. Với N bằng 10 thì có 10 khung, không đáng kể. Với N bằng 500 000 thì cần 500 000 khung cùng lúc, và vùng nhớ dành cho ngăn xếp lời gọi thường chỉ vài megabyte nên nó bị vượt — đó chính là lỗi tràn ngăn xếp.
Điểm cần nhận ra. Bộ nhớ mà đệ quy tiêu tốn tỷ lệ với độ sâu của chuỗi lời gọi, chứ không tỷ lệ với lượng dữ liệu. Đây là chi phí ẩn mà phiên bản lặp không có.
Phiên bản lặp. TONG bằng 0 ; K bằng 1 ; loop while K nhiều nhất bằng N ; TONG bằng TONG cộng K ; K bằng K cộng 1 ; end loop ; output TONG. Phiên bản này dùng đúng hai biến bất kể N lớn tới đâu, tức bộ nhớ ở bậc hằng số. Nó chạy được với N bằng 500 000 hay 500 triệu mà không gặp vấn đề gì.
Nhưng đừng kết luận rằng lặp luôn tốt hơn. Đệ quy vượt trội khi bản thân bài toán được định nghĩa một cách đệ quy, vì khi đó đoạn mã phản chiếu đúng định nghĩa và ngắn hơn hẳn. Ba nhóm điển hình. Thứ nhất là duyệt cây: một cây được định nghĩa là một nút cùng hai cây con, nên duyệt cây viết đệ quy chỉ tốn ba dòng trong khi viết lặp phải tự quản lý một ngăn xếp bằng tay — tức chỉ chuyển ngăn xếp từ chỗ hệ thống lo sang chỗ mình lo, mà lại dễ sai hơn. Thứ hai là chia để trị như tìm kiếm nhị phân hay sắp xếp trộn. Thứ ba là quay lui khi phải thử một hướng rồi trở lại ngã rẽ trước.
Nguyên tắc quyết định. Hãy hỏi độ sâu đệ quy tối đa là bao nhiêu. Nếu độ sâu tỷ lệ với KÍCH THƯỚC dữ liệu — như đệ quy tính tổng ở đây — thì chuyển sang lặp. Nếu độ sâu tỷ lệ với lôgarit của kích thước dữ liệu hoặc với chiều cao của một cây cân bằng, thì độ sâu chỉ vài chục và đệ quy hoàn toàn an toàn, khi đó nên chọn nó vì mã rõ ràng hơn.
Chọn cấu trúc dữ liệu cho từng tình huống và giải thích: (a) bảng tra cứu 26 phần tử ứng với 26 chữ cái, tra rất nhiều lần; (b) danh sách công việc mà người dùng liên tục chèn thêm và xoá ở giữa, số lượng không biết trước; (c) hàng đợi các tệp chờ in.
(a) Bảng tra cứu 26 phần tử — dùng mảng. Hai đặc điểm quyết định. Kích thước cố định và biết trước, nên ưu điểm lớn lên của danh sách liên kết là vô dụng. Và thao tác chính là truy cập trực tiếp theo vị trí: từ một chữ cái tính ngay ra chỉ số rồi lấy phần tử trong thời gian hằng số. Với danh sách liên kết, việc tới phần tử thứ 20 đòi phải đi qua 19 nút trước đó, tức thời gian tuyến tính — chậm hơn hẳn cho một thao tác được lặp rất nhiều lần.
(b) Danh sách công việc chèn và xoá ở giữa — dùng danh sách liên kết. Hai lý do. Thứ nhất, số lượng không biết trước, nên mảng buộc phải cấp phát dư — lãng phí nếu ít việc, và tràn nếu nhiều việc. Thứ hai và quan trọng hơn, chèn hoặc xoá ở GIỮA một mảng đòi phải dịch chuyển toàn bộ các phần tử phía sau, tức thời gian tuyến tính cho mỗi thao tác. Với danh sách liên kết, chèn hay xoá chỉ là việc đổi lại vài con trỏ, tức thời gian hằng số một khi đã ở đúng vị trí.
Nhưng phải nêu điều kiện, vì đây là chỗ mất điểm. Câu "chèn vào danh sách liên kết là thời gian hằng số" chỉ đúng khi đã đứng ở đúng vị trí. Nếu phải tìm vị trí đó từ đầu danh sách thì việc tìm vẫn tốn thời gian tuyến tính. Lợi thế thật xuất hiện khi chương trình đã giữ sẵn con trỏ tới vị trí đó, chẳng hạn đang duyệt qua danh sách và xoá các phần tử thoả điều kiện.
(c) Hàng đợi in — dùng hàng đợi cài bằng mảng vòng. Thao tác chỉ gồm thêm vào cuối và lấy ra ở đầu, không bao giờ chèn hay xoá ở giữa, và không bao giờ truy cập theo chỉ số. Mảng vòng cho cả hai thao tác trong thời gian hằng số, có tính cục bộ truy cập tốt vì các phần tử nằm liền kề trong bộ nhớ, và không tốn bộ nhớ cho con trỏ. Nếu số tệp chờ có thể vượt xa mọi dự đoán thì mới nên chuyển sang cài bằng danh sách liên kết, đổi lấy chi phí con trỏ để được kích thước không giới hạn.
Khung quyết định chung để trả lời mọi câu hỏi dạng này. Hỏi ba câu. Có cần truy cập theo chỉ số không — nếu có thì gần như luôn là mảng. Kích thước có biết trước không — nếu không thì nghiêng về cấu trúc động. Thao tác thường xuyên nhất là gì — chèn và xoá ở giữa nghiêng về danh sách liên kết, còn duyệt và truy cập theo vị trí nghiêng về mảng.
Bẫy 2 — nói chèn vào danh sách liên kết luôn là thời gian hằng số. Chỉ đúng KHI ĐÃ ở đúng vị trí; việc tìm vị trí đó vẫn tốn thời gian tuyến tính vì phải đi lần từ đầu.
Bẫy 3 — quên rằng hàng đợi cài bằng mảng thẳng sẽ báo đầy dù còn chỗ. Sau nhiều lần lấy ra, phần đầu mảng bỏ trống nhưng con trỏ cuối đã chạm biên. Hàng đợi VÒNG giải quyết điều này, và khi đó phải có biến đếm để phân biệt rỗng với đầy.
Đọc xong rồi — làm thử ngay
Bài tập của chương Abstract Data Structures (HL) gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.