Triển khai các ADT bằng mảng.
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | Vượt quá |
| underflow/ˌʌndəˈfləʊ/ | tràn dưới |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | mảng vòng |
| free list/friː lɪst/ | danh sách trống |
Không có khái niệm ngăn xếp thực tế trong bộ nhớ
- Mở một chiếc máy tính và tìm kiếm ngăn xếp. Bạn sẽ không tìm thấy nó. Bộ nhớ là một mảng khổng lồ gồm các ô được đánh số, và chỉ có thế thôi.
- Mỗi ngăn xếp, mỗi hàng đợi, mỗi danh sách liên kết đều là mảng đó cộng với hai hoặc ba biến số nguyên ghi nhớ vị trí của các thứ. Push là "cộng một vào một số và lưu trữ"; dequeue là "đọc một ô và cộng một vào một số khác".
- Toàn bộ bài học này là việc quản lý sổ sách: những con trỏ nào, những phép kiểm tra nào, và những gì xảy ra ở các biên.
- Đề thi yêu cầu bạn mô tả các khai báo, đi qua các con trỏ qua vài thao tác, và giải thích tại sao có các phép kiểm tra đó.
Ngăn xếp trong mảng
- Giữ các mục trong
Stack[1:MaxSize]với một số nguyênTop, bằng 0 khi ngăn xếp trống. - Push(x): nếu
Top = MaxSizengăn xếp đầy, xảy ra tràn; ngược lạiTop ← Top + 1vàStack[Top] ← x. - Pop(): nếu
Top = 0ngăn xếp trống, xảy ra thiếu; ngược lại trả vềStack[Top]vàTop ← Top − 1.
Mảng không bao giờ di chuyển; chỉ có Top là di chuyển
Việc đẩy một phần tử vào một ngăn xếp đã đầy sẽ gây ra lỗi ________ cho ngăn xếp.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Overflow (tràn) xảy ra khi thực hiện push trong khi Top = MaxSize; việc rút phần tử khỏi một ngăn xếp rỗng (Top = 0) gọi là underflow (rỗng).
Nối mỗi điều kiện của ngăn xếp dựa trên mảng với ý nghĩa tương ứng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Top đếm số lượng phần tử: 0 = rỗng, MaxSize = đầy; hai trường hợp lỗi là underflow và overflow.
Ví dụ minh họa: khai báo và khởi tạo ngăn xếp
- Mô tả các khai báo và khởi tạo cần thiết để triển khai một ngăn xếp chứa tối đa 50 số nguyên sử dụng mảng. [5]
- Một mảng gồm 50 phần tử loại
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, để chứa các mục. - Một hằng số hoặc biến
MaxSizeđược đặt bằng 50, để push có thể kiểm tra xem có đầy hay không. - Một con trỏ đỉnh ngăn xếp
INTEGER,Top, được khởi tạo bằng 0 để chỉ thị rằng ngăn xếp trống; pop kiểm tra nó để tránh thiếu, và push so sánh nó vớiMaxSizeđể tránh tràn.
Những mục nào thuộc về phần khai báo và khởi tạo của một ngăn xếp dựa trên mảng? Chọn tất cả các đáp án đúng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Ngăn xếp chỉ cần một con trỏ Top. Con trỏ front thuộc về hàng đợi.
Hàng đợi trong mảng thuần túy
- Hai con trỏ:
Frontcho mục tiếp theo sẽ rời đi,Rearcho khoảng trống tiếp theo. Enqueue lưu tạiRearvà di chuyển nó đi; dequeue đọc tạiFrontvà di chuyển nó đi. - Cả hai con trỏ chỉ bao giờ di chuyển tiến, nên sau vài thao tác chúng sẽ chạy ra khỏi cuối mảng trong khi các ô ở đầu vẫn trống và không thể sử dụng.
- Cách khắc phục là cho phép các con trỏ vòng quanh.
Mảng vòng tròn
- Một mảng vòng tròn đưa con trỏ quay trở về ô đầu tiên khi nó vượt quá ô cuối cùng: với chỉ số bắt đầu từ 1,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): kiểm tra không đầy;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): kiểm tra không trống; trả vềQueue[Front];Front ← (Front MOD MaxSize) + 1. - Giữ một biến đếm riêng biệt: khi hàng đợi đầy hoàn toàn và khi nó trống hoàn toàn, hai con trỏ sẽ ở cùng vị trí tương đối, do đó chỉ riêng các con trỏ không thể phân biệt được hai trường hợp này.
Sau ô cuối cùng là ô đầu tiên
Triển khai các ADT sử dụng mảng.
FIFO.
Một hàng đợi hoạt động theo nguyên tắc đầu vào - đầu ra — thêm vào phía sau, lấy ra từ phía trước.
Tại sao nên sử dụng mảng vòng tròn cho hàng đợi?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hàng đợi tuyến tính lãng phí các ô bộ nhớ ở đầu khi Front tiến lên; việc quay vòng với MOD giúp tái sử dụng chúng.
Hàng đợi vòng tròn sử dụng toán tử MOD để các con trỏ front/rear quay vòng và tái sử dụng các ô bộ nhớ được giải phóng ở đầu mảng.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
(pointer MOD MaxSize) + 1 giúp quay chỉ số trở về ô đầu tiên, do đó hàng đợi tuyến tính không còn lãng phí các ô bộ nhớ mà Front đã vượt qua.
Ví dụ minh họa: di chuyển các con trỏ
- Với
MaxSize = 6: nếuRear = 5, thì(5 MOD 6) + 1 = 6, nên mục tiếp theo sẽ được đưa vào ô 6. NếuRear = 6, thì(6 MOD 6) + 1 = 1: con trỏ quay về ô 1. - Một hàng đợi tròn được lưu trữ trong mảng có kích thước 5, chỉ số từ 0 đến 4, với
Front = 3,Rear = 3và một mục đã được lưu. Hai mục được thêm vào, sau đó hai mục bị loại bỏ. Với chỉ số bắt đầu từ 0, mỗi bước di chuyển đều(pointer + 1) MOD 5. - Thêm hai lần làm di chuyển
Rear: 3 → 4, sau đó 4 → 0, vì (4 + 1) MOD 5 = 0. Loại bỏ hai lần làm di chuyểnFront: 3 → 4 → 0. Còn lại một mục, tại chỉ số 0, và hàng đợi đã tái sử dụng các ô được giải phóng ở đầu mảng.
Một hàng đợi vòng tròn sử dụng các ô từ 1 đến 6 và Rear = 6. Sau khi thực hiện Rear ← (Rear MOD 6) + 1, phần tử tiếp theo sẽ được đặt vào đâu?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
6 MOD 6 = 0, cộng thêm 1 ta được 1. Con trỏ quay về đầu của mảng.
Ví dụ minh họa: thuật toán enqueue bằng lời
- Mô tả thuật toán để thêm một mục vào hàng đợi tròn. [4]
- Nếu count bằng size, báo rằng hàng đợi đầy và dừng lại.
- Ngược lại, tăng rear pointer lên 1; nếu nó vượt quá chỉ số cuối cùng, hãy đặt nó về chỉ số đầu tiên.
- Lưu mục vào vị trí rear pointer và tăng count lên 1.
Sắp xếp lại các bước để thêm vào hàng đợi vòng tròn.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Kiểm tra, di chuyển, quay vòng, lưu, tăng biến đếm. Chính việc quay vòng mới làm cho mảng trở thành dạng vòng tròn.
Danh sách liên kết trong mảng
- Sử dụng mảng bản ghi nút, mỗi nút có chỉ mục
Next;-1đánh dấu cuối cùng. Chỉ mụcHeadđánh dấu nút đầu tiên,-1nếu danh sách rỗng. - Các ô trống chưa sử dụng được nối thành một danh sách tự do (free list) từ
FreeListHead, đúng như cách danh sách dữ liệu nối các ô đang dùng.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Chèn: lấy slot tại
FreeListHead, thiết lậpValuevàNextcủa nó, sau đó nối lạiNexthoặcHeadcủa node trước đó. Xóa: tách node ra khỏi danh sách và trả slot của nó về đầu free list.
Hai danh sách chia sẻ chung một mảng: danh sách dữ liệu và danh sách tự do
Trong danh sách liên kết dựa trên mảng, danh sách trống (free list):
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Danh sách trống liên kết các ô dự phòng, do đó một phép chèn có thể lấy một ô và một phép xóa có thể trả lại một ô — giống như một danh sách liên kết thứ hai chứa các ô rỗng.
Ví dụ minh họa: chèn vào danh sách lưu trong mảng
DatavàPointermảng chứa danh sách 1 → 3 → 4, vớiStart = 1; chỉ số 1 chứaD40, chỉ số 3 chứaD32, chỉ số 4 chứaD11với con trỏ null. Danh sách tự do bắt đầu từ chỉ số 2 và tiếp tục 2 → 5. ChènD6giữaD32vàD11.- Lấy nút rỗng đầu tiên, chỉ số 2, và gán
FreeStartcho con trỏ của nó, 5. Lưu trữD6vàoData[2]. - Gán
Pointer[2]cho giá trịPointer[3]được lưu trữ, tức là 4. Sau đó gánPointer[3]thành 2. - Danh sách hiện đọc là 1 → 3 → 2 → 4 và danh sách tự do là 5 → null. Giải pháp thực thi, nếu được hỏi: một mảng cho dữ liệu, một mảng song song (hoặc trường bản ghi) cho các con trỏ, một con trỏ bắt đầu, và một con trỏ free-list.
Trong ví dụ đã giải, sau khi chèn D6, danh sách trống bắt đầu từ chỉ mục ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Chỉ mục 2 đã được lấy khỏi danh sách trống, nên FreeStart di chuyển đến chỉ mục mà 2 trỏ tới, đó là 5.
Khi chèn vào danh sách, con trỏ của nút trước phải được thay đổi trước khi thiết lập con trỏ của nút mới.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Thiết lập con trỏ của nút mới trỏ tới nút tiếp theo cũ trước. Thay đổi con trỏ của nút trước sẽ làm mất địa chỉ phần còn lại của danh sách.
Điểm số dễ mất
- Các kiểm tra diễn ra trước: đầy trước khi push hoặc enqueue, rỗng trước khi pop hoặc dequeue. Mô tả chúng; chúng là điểm đánh giá.
- Công thức vòng lặp phụ thuộc vào chỉ số:
(Rear MOD MaxSize) + 1cho chỉ số bắt đầu từ 1,(Rear + 1) MOD Sizecho chỉ số bắt đầu từ 0. Phù hợp với giới hạn của câu hỏi. - Count là thứ cho biết hàng đợi tròn đang đầy hay rỗng. Chỉ riêng con trỏ thì không thể phân biệt được.
- Gán cho nút mới ⟨
Nexttrước khi đi dây lại nút trước đó, và trả slot của nút đã xóa về danh sách trống, nếu không mảng sẽ dần đầy các ô không thể truy cập.
Bạn đã nắm vững
- Ngăn xếp trong mảng: ⟨
Stack[1:MaxSize]và một con trỏ ⟨Topbắt đầu từ ⟨0; ⟨Top = MaxSizelà tràn (overflow), ⟨Top = 0là thiếu (underflow). - hàng đợi vòng tròn:
FrontvàRearquấn quanh vớiMOD; một biến đếm riêng biệt phân biệt trạng thái đầy và trống - danh sách liên kết trong mảng: các bản ghi node có chỉ số
Next, mộtHead, và một danh sách trống nối các ô dự phòng - Mọi thao tác đều là: kiểm tra, sau đó tính toán số học trên con trỏ, rồi lưu hoặc đọc; hành vi ADT không thay đổi tùy cách lưu trữ