Loại dữ liệu trừu tượng — ngăn xếp, hàng đợi, danh sách liên kết
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| queue/kjuː/ | hàng đợi |
| push/pʊʃ/ | nén |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | kiểu dữ liệu trừu tượng |
| stack/stæk/ | Ngăn xếp |
| linked list/lɪŋkt lɪst/ | danh sách liên kết |
| LIFO/ˈlaɪfəʊ/ | lỗi ngược (LIFO) |
| pop/pɒp/ | giải nén |
| pointer/ˈpɔɪntə/ | con trỏ |
| FIFO/ˈfaɪfəʊ/ | lỗi ngược (FIFO) |
| enqueue/enˈkjuː/ | enqueue |
| dequeue/diːˈkjuː/ | dequeue |
| node/nəʊd/ | nút |
| traverse/trəˈvɜːs/ | duyệt |
Nút Back và hàng đợi máy in
- Mỗi trang bạn truy cập đều được đẩy lên một đống; nút Back lấy trang trên cùng xuống. Trang bạn rời đi gần đây nhất sẽ là trang đầu tiên bạn quay lại.
- Dọc hành lang, một máy in xử lý các công việc theo thứ tự chúng đến. Tài liệu gửi đầu tiên sẽ được in ra đầu tiên, dù những tài liệu phía sau nhỏ hơn nhiều.
- Hai cấu trúc, quy tắc ngược nhau, và bạn sử dụng cả hai trước giờ nghỉ. Không cái nào nói cách chúng được lưu trữ; mỗi cái chỉ nói các thao tác của nó làm gì.
- Đó là một kiểu dữ liệu trừu tượng. Bài học này là ba loại mà chương trình học đặt tên, các thao tác trên mỗi loại, và cách biện minh cho một loại trong một tình huống cụ thể.
Kiểu dữ liệu trừu tượng là gì
- Một kiểu dữ liệu trừu tượng (ADT) là một tập hợp dữ liệu cùng với một tập hợp các thao tác trên dữ liệu đó. Câu đơn giản này chính là định nghĩa một điểm.
- Nó được xác định bởi những gì các thao tác làm, chứ không phải cách dữ liệu được lưu trữ. Phần thực hiện bị ẩn đi, nên nó có thể thay đổi mà không ảnh hưởng đến mã sử dụng nó.
- Ngăn xếp, hàng đợi, danh sách liên kết, cây nhị phân và mảng đều là các ADT.
Một Kiểu Dữ Liệu Trừu Tụ (ADT) được xác định bởi:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Một ADT quy định các thao tác (giao diện); phần triển khai được ẩn đi và có thể thay đổi tự do.
Ngăn xếp
- Một ngăn xếp là một danh sách nơi các mục được thêm vào và lấy ra từ cùng một đầu, gọi là đỉnh, vì vậy mục được thêm vào sau cùng sẽ là mục đầu tiên được lấy ra: LIFO.
- Các thao tác: push thêm vào đỉnh, pop lấy ra khỏi đỉnh, peek xem đỉnh, và kiểm tra trạng thái trống hay đầy.
- Ứng dụng: lịch sử hoàn tác, nút Back, địa chỉ trả về của các cuộc gọi hàm, kiểm tra ngoặc, truy hồi.
Mọi hoạt động đều diễn ra ở đỉnh
Ngăn xếp hoạt động theo thứ tự nào?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Ngăn xếp là LIFO: phần tử được đẩy vào gần đây nhất sẽ là phần tử đầu tiên được rút ra.
Ví dụ minh họa: theo dõi ngăn xếp
- Ngăn xếp chứa, từ dưới lên trên,
'P' 'N' 'Z' 'X' 'Y' 'W'; con trỏ đỉnh nằm ở'W'. Các thao tácPOP,POP,PUSH 'A',PUSH 'B',POPđược thực hiện. Ngăn xếp chứa những gì và con trỏ nằm ở đâu? - Hai phép pop loại bỏ
'W'rồi đến'Y'. Các phép push đặt'A'sau đó là'B'vào đúng vị trí. Phép pop cuối cùng loại bỏ'B'. - Ngăn xếp chứa
'P' 'N' 'Z' 'X' 'A', với con trỏ tại'A'. Phần tử dài nhất trong ngăn xếp là phần tử dưới cùng,'P'; năm phép pop nữa là khả thi, và phép pop thứ sáu sẽ gây lỗi, đó là lý do tại sao phép pop cần kiểm tra xem ngăn xếp có trống hay không trước khi thực hiện.
Ngăn xếp chứa P N Z X Y W (W nằm trên đỉnh). Sau khi thực hiện POP, POP, PUSH 'A', PUSH 'B', POP, phần tử nào đang nằm trên đỉnh?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
W và Y được rút ra, A rồi B được đẩy vào, B sau đó được rút ra. Phần tử trên cùng là A, nằm ngay phía trên X.
Hàng đợi
- Một hàng đợi là một danh sách nơi các mục được thêm vào ở cuối và lấy ra từ đầu, vì vậy mục được thêm vào đầu tiên sẽ là mục đầu tiên được lấy ra: FIFO.
- Các thao tác: enqueue thêm vào cuối, dequeue lấy ra khỏi đầu, và kiểm tra trạng thái trống hay đầy.
- Ứng dụng: spool in, bộ đệm bàn phím, lập lịch, khách hàng trong cửa hàng, duyệt rộng.
Nối vào phía sau, rời khỏi phía trước
Ngăn xếp, hàng đợi & danh sách liên kết
LIFO so với FIFO
Một ngăn xếp hoạt động theo nguyên tắc cuối vào trước ra (LIFO); các thao tác đẩy và rút đều diễn ra ở cùng một đầu (đỉnh).
Hàng đợi hoạt động theo nguyên tắc đầu vào - đầu ra: phần tử được lấy ra từ ______ và được thêm vào ở phía sau.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
FIFO: rút phần tử từ phía trước, thêm phần tử vào phía sau — giống như hàng người đứng chờ.
Ví dụ minh họa: mô tả việc thêm vào và lấy ra khỏi hàng đợi
- Thêm: kiểm tra xem hàng đợi có đầy không; lưu mục vào vị trí do con trỏ cuối chỉ định; di chuyển con trỏ cuối (và tăng biến đếm lên 1).
- Lấy ra: kiểm tra xem hàng đợi có trống không; đọc mục tại con trỏ đầu; di chuyển con trỏ đầu (và giảm biến đếm đi 1).
- Phát biểu quy ước bạn sử dụng: nếu con trỏ cuối đánh dấu ô trống tiếp theo, thì lưu trước rồi mới di chuyển; nếu nó đánh dấu mục cuối cùng, thì di chuyển trước rồi mới lưu. Cả hai đều nhận điểm, miễn là bạn nhất quán.
Sắp xếp lại các bước để thêm một phần tử vào hàng đợi (con trỏ "rear" đánh dấu vị trí trống tiếp theo).
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Theo quy ước này, việc kiểm tra diễn ra trước, sau đó mới lưu, rồi di chuyển. Hãy nêu rõ quy ước bạn đang áp dụng.
Danh sách liên kết
- Danh sách liên kết là một danh sách mà trong đó mỗi nút chứa một mục dữ liệu và một con trỏ trỏ đến nút tiếp theo, kèm theo một con trỏ bắt đầu trỏ đến nút đầu tiên. Con trỏ của nút cuối cùng là một giá trịsentinel như
NULL. - Các thao tác: chèn, xóa, tìm kiếm và duy duyệt, theo các con trỏ từ đầu danh sách để truy cập từng nút theo thứ tự.
- Ưu điểm so với mảng: việc chèn hoặc xóa có chi phí thấp, chỉ cần nối lại các con trỏ, và danh sách sẽ mở rộng khi cần thiết. Nhược điểm: không truy cập ngẫu nhiên; để đến nút thứ mười, phải đi qua chín con trỏ.
Một giá trị và một mũi tên, lặp lại
Danh sách liên kết: các nơ-đơ được nối với nhau bằng con trỏ.
Mỗi nơ-đơ lưu trữ một giá trị và một con trỏ đến nơ-đơ tiếp theo. Việc chèn hoặc xóa chỉ cần thay đổi các con trỏ — không có phần tử nào bị dịch chuyển, khác với mảng.
Mỗi nơ-đơ của danh sách liên kết chứa:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Một nơ-đơ lưu trữ giá trị của nó cộng với một con trỏ (tham chiếu) đến nơ-đơ tiếp theo; "head" đánh dấu điểm bắt đầu, NULL đánh dấu điểm kết thúc.
Danh sách liên kết giúp việc chèn/xóa trở nên tốn ít tài nguyên (chỉ cần điều chỉnh lại con trỏ) nhưng truy cập ngẫu nhiên lại chậm (bắt buộc phải lần lượt theo dõi các con trỏ từ "head").
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Đó chính là sự đánh đổi giữa mảng và danh sách: mảng cho phép truy cập theo chỉ số với độ phức tạp O(1); danh sách cho phép chèn/xóa dễ dàng.
Ví dụ minh họa: thêm một nút theo thứ tự
- Mô tả cách chèn một giá trị mới vào danh sách liên kết được giữ ở thứ tự tăng dần. [4]
- Duyệt danh sách từ đầu, theo các con trỏ, cho đến khi tìm thấy nút trước vị trí cần chèn: đó là nút cuối cùng có giá trị nhỏ hơn giá trị mới.
- Lấy một nút trống và lưu giá trị mới vào đó. Đặt con trỏ của nút mới vào địa chỉ mà nút trước đó hiện đang trỏ tới.
- Sau đó đặt con trỏ của nút trước đó trỏ sang nút mới. Nếu giá trị mới thuộc về vị trí đầu tiên, thì chính con trỏ đầu danh sách sẽ bị thay đổi.
Sắp xếp lại các bước để chèn một giá trị vào danh sách liên kết đã được sắp xếp.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Tìm, điền, trỏ về phía trước cho nơ-đơ mới, sau đó điều chỉnh lại con trỏ của nơ-đơ trước. Nếu đảo ngược hai bước cuối cùng sẽ làm mất phần còn lại của danh sách.
Giải thích sự lựa chọn
- Các mục phải được xử lý theo thứ tự chúng xuất hiện, công việc in ấn, phím nhấn, khách hàng: một hàng đợi, vì nó hoạt động theo nguyên tắc vào trước ra trước.
- Mục gần nhất phải được xử lý trước, hoàn tác, quay lại, gọi hàm lồng nhau: một ngăn xếp, vì nó hoạt động theo nguyên tắc vào sau ra trước.
- Các mục thường xuyên được chèn hoặc xóa ở giữa một tập hợp đã sắp xếp, và kích thước không biết trước: một danh sách liên kết, vì chỉ có con trỏ thay đổi và không có phần tử nào bị dịch chuyển.
- Tên cấu trúc, tên quy tắc, gắn quy tắc với tình huống.
Nối mỗi ADT với quy tắc và một ứng dụng điển hình của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Ngăn xếp = cuối vào - đầu ra; hàng đợi = đầu vào - đầu ra; danh sách liên kết nối các nơ-đơ bằng các con trỏ.
Các yêu cầu in phải được in theo đúng thứ tự chúng được gửi đến. ADT nào phù hợp và tại sao?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Thứ tự đến là quy tắc FIFO. Một ngăn xếp sẽ in yêu cầu gần đây nhất ra trước.
ADT so với triển khai
- ADT là hành vi: push và pop, enqueue và dequeue, chèn và duy duyệt.
- Triển khai là lưu trữ: trong khóa học này, là một mảng cộng với vài biến con trỏ (bài học sau).
- Một câu hỏi về ADT muốn biết các thao tác và quy tắc; một câu hỏi về triển khai muốn biết mảng, con trỏ và các kiểm tra.
Điểm số dễ mất
- Push và enqueue kiểm tra trạng thái đầy trước; pop và dequeue kiểm tra trạng thái trống trước. Viết phép kiểm tra vào mô tả.
- Chèn vào danh sách liên kết: đặt con trỏ của nút mới trước khi thay đổi con trỏ của nút trước, nếu không phần còn lại của danh sách sẽ bị mất.
- Ngăn xếp thay đổi ở một đầu, hàng đợi ở cả hai đầu. "Xóa từ trên cùng của hàng đợi" là câu trả lời đúng cho ngăn xếp.
- Mở rộng các chữ viết tắt một lần: LIFO, last in first out; FIFO, first in first out.
Bạn đã nắm vững
- một ADT là một tập hợp dữ liệu kèm theo một bộ các thao tác trên nó; hành vi, không phải lưu trữ
- ngăn xếp: thêm và xóa ở trên cùng, LIFO, push và pop · hàng đợi: thêm ở đuôi, xóa ở đầu, FIFO, enqueue và dequeue
- danh sách liên kết: các nút chứa giá trị + con trỏ từ con trỏ đầu; chèn và xóa nhanh, truy cập ngẫu nhiên chậm; duy duyệt bằng cách theo dõi con trỏ
- giải thích bằng quy tắc: thứ tự xuất hiện → hàng đợi; gần nhất ra trước → ngăn xếp; chèn thường xuyên ở giữa → danh sách liên kết