การนำไปใช้ ADT โดยใช้อาร์เรย์
แนะนำใหม่| English | ความหมาย |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | การล้น |
| underflow/ˌʌndəˈfləʊ/ | เดอร์โฟลว์ |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | วงจรรายชื่อ |
| free list/friː lɪst/ | ฟรีลิสต์ |
ไม่มี stack อะไรอยู่ในหน่วยความจำ
- เปิดคอมพิวเตอร์แล้วมองหา stack คุณจะหาไม่เจอ หน่วยความจำคือ arrayขนาดใหญ่หนึ่งแห่งที่มีเซลล์編號, นั่นทุกอย่างที่มีอยู่
- ทุก stack, ทุก queue, ทุก linked list คือ array plus two or three ตัวแปรจำนวนเต็มที่จดจำว่าสิ่งต่างๆ อยู่ที่ไหน Push คือ "เพิ่มหนึ่งกับตัวเลขแล้วเก็บ"; dequeue คือ "อ่านเซลล์และเพิ่มหนึ่งกับตัวเลขอื่น"
- บทเรียนทั้งหมดนี้คือการบันทึกบัญชี: ตัวชี้ไหน, การตรวจสอบไหน, และเกิดอะไรขึ้นที่ขอบเขต
- การสอบถามให้คุณอธิบายการประกาศ, เดินตัวชี้ผ่านหลาย操作简单说, และบอกwhyการตรวจสอบมีอยู่
Stack ใน array
- เก็บรายการใน
Stack[1:MaxSize]ด้วยจำนวนเต็มTop, 0 เมื่อสแตกว่าง - Push(x): ถ้า
Top = MaxSizestack เต็ม, overflow; มิฉะนั้นTop ← Top + 1และStack[Top] ← x - Pop(): ถ้า
Top = 0stack ว่าง, underflow; มิฉะนั้นคืนค่าStack[Top]และTop ← Top − 1
Array ไม่เคยเคลื่อน; เฉพาะ Top เท่านั้น
การ push รายการลงในสแต็กที่เต็มอยู่แล้วจะทำให้เกิดสแต็ก ______
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Overflow = push เมื่อ Top = MaxSize; pop จากสแต็กที่ว่างเปล่า (Top = 0) คือ underflow
จับคู่เงื่อนไขสแต็กแบบอาร์เรย์แต่ละชนิดกับความหมาย
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Top นับจำนวนรายการ: 0 = ว่าง, MaxSize = เต็ม; กรณีข้อผิดพลาดทั้งสองคือ underflow และ overflow
ตัวอย่างทำข้อ: ประกาศและเริ่มต้น stack
- อธิบายการประกาศและการเริ่มต้นที่ต้องการเพื่อimplement stack of up to 50 integers using an array. [5]
- Array of 50 elements of type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, เพื่อเก็บitems - Constant หรือตัวแปร
MaxSizeตั้งค่าเป็น 50, เพื่อให้pushทดสอบว่าเต็ม - An
INTEGERtop-of-stack pointer,Top, เริ่มต้นที่ 0 เพื่อแสดงว่า stack ว่าง; pop ทดสอบ它为underflow, และpush เปรียบเทียบกับMaxSizeสำหรับ overflow
สิ่งใดบ้างที่ควรอยู่ใน declaration และ initialisation ของสแต็กแบบอาร์เรย์? เลือก ทั้งหมด ที่ถูกต้อง
Difficulty 2/5 · 140 coins + a small bonus on first completion today
สแต็กต้องการพอยเตอร์หนึ่งตัวคือ Top. พอยเตอร์หน้าเป็นของคิว
Queue ใน array ปกติ
- พอยเตอร์สองตัว:
Frontสำหรับรายการถัดไปที่จะออก,Rearสำหรับพื้นที่ว่างถัดไป Enqueue จัดเก็บที่Rearและย้ายไปข้างหน้า; Dequeue อ่านที่Frontและย้ายไปข้างหน้า - ทั้งสองตัวชี้เคลื่อน ไปข้างหน้า เท่านั้น ดังนั้นหลังจากหลาย操作简单说พวกมันเดินออกจากปลายarrayในขณะที่เซลล์ที่เริ่มต้นว่างและใช้ไม่ได้
- ทางแก้คือให้ตัวชี้วนรอบ
Array แบบวงกลม
- A circular arrayวนตัวชี้กลับไปยังเซลล์แรกเมื่อผ่าน آخرین: With 1-based indices,
Rear ← (Rear MOD MaxSize) + 1 - Enqueue(x): ตรวจสอบว่าไม่เต็ม;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): ตรวจสอบว่าไม่ว่าง; คืนค่าQueue[Front];Front ← (Front MOD MaxSize) + 1 - เก็บ count แยกต่างหาก: เมื่อqueue เต็มสนิทและเมื่อว่างสนิท ตัวชี้ทั้งสองอยู่ในตำแหน่งสัมพัทธ์เดียวกัน ดังนั้นตัวชี้เพียงอย่างเดียวไม่สามารถแยกสองกรณีนี้ออกจากกันได้
หลังจากเซลล์สุดท้ายคือเซลล์แรก
การนำไปใช้ ADT ด้วยอาร์เรย์
FIFO
คิว (queue) เป็นแบบเข้าหน้าออกหน้า — enqueue ด้านหลัง, dequeue ด้านหน้า
ทำไมต้องใช้ circular array สำหรับคิว?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
คิวแบบเส้นตรงเสียCELLS ที่ต้นเมื่อ Front ย้ายไป; การวนรอบด้วย MOD ใช้ซ้ำเซลล์เหล่านั้น
คิวแบบวงกลมใช้ MOD เพื่อให้พอยเตอร์ front/rear แวนรอบและใช้ซ้ำเซลล์ที่ถูกปล่อยทิ้งไว้ที่ต้นของอาร์เรย์
Difficulty 1/5 · 100 coins + a small bonus on first completion today
(pointer MOD MaxSize) + 1 ทำให้ดัชนีวนกลับไปยังเซลล์แรก ดังนั้นคิวแบบเส้นตรงจึงไม่เสียเซลล์ที่ Front ผ่านไปแล้วอีกต่อไป
ตัวอย่างวิธีทำ: การเดินตัวชี้
- ด้วย
MaxSize = 6: ถ้าRear = 5, แล้ว(5 MOD 6) + 1 = 6, ดังนั้นรายการถัดไปจะอยู่ในเซลล์ที่ 6. ถ้าRear = 6, แล้ว(6 MOD 6) + 1 = 1: ตัวชี้จะวนกลับไปที่เซลล์ที่ 1. - 队列วงกลมจัดเก็บในอาร์เรย์ขนาด 5, ดัชนี 0 ถึง 4, มี
Front = 3,Rear = 3และรายการหนึ่งถูกจัดเก็บ. เพิ่มสองรายการแล้วลบออกสองรายการ. โดยใช้ดัชนีแบบเริ่มที่ 0 การเคลื่อนย้ายแต่ละครั้งคือ(pointer + 1) MOD 5. - การเพิ่มสองครั้งทำให้
Rearเคลื่อน: 3 → 4, จากนั้น 4 → 0, เนื่องจาก (4 + 1) MOD 5 = 0. การลบสองครั้งทำให้Frontเคลื่อน: 3 → 4 → 0. เหลือรายการหนึ่งอยู่ที่ดัชนี 0, และ队列วงกลมได้ใช้เซลล์ที่ถูกปลดปล่อยที่ส่วนต้นของอาร์เรย์อีกครั้ง.
คิวแบบวงกลมใช้เซลล์ 1 ถึง 6 และ Rear = 6. หลังจาก Rear ← (Rear MOD 6) + 1 รายการถัดไปจะไปอยู่ที่ไหน?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
6 MOD 6 = 0, บวก 1 ได้ 1. พอยเตอร์วนกลับไปที่ต้นของอาร์เรย์
ตัวอย่างวิธีทำ: อัลกอริทึมการเพิ่มรายการเป็นคำพูด
- อธิบายอัลกอริทึมสำหรับการเพิ่มรายการลงใน队列วงกลม. [4]
- ถ้าจำนวนรายการเท่ากับขนาด ให้รายงานว่า队列เต็มและหยุดทำงาน.
- มิฉะนั้นให้บวก 1 เข้ากับตัวชี้ท้าย; ถ้ามันเลยดัชนียก最后一个แล้ว ให้ตั้งค่าให้เป็นดัชนีแรก.
- จัดเก็บรายการที่ตัวชี้ท้ายและบวก 1 เข้ากับจำนวนรายการ.
เรียงขั้นตอนการเพิ่มลงในคิวแบบวงกลม
Difficulty 3/5 · 200 coins + a small bonus on first completion today
ตรวจสอบ, เลื่อน, วนรอบ, เก็บ, นับ. การวนรอบคือสิ่งที่ทำให้อาร์เรย์เป็นแบบวงกลม
รายการเชื่อมโยงในอาร์เรย์
- ใช้อาร์เรย์ของบันทึกโหนด แต่ละอันมี
Nextดัชนี;-1แสดงถึงจุดสิ้นสุด.Headดัชนีแสดงโหนดแรก,-1ถ้ารายการว่างเปล่า. - ช่องว่างที่ไม่ได้ใช้จะถูกเชื่อมต่อกันเป็น รายการว่าง จาก
FreeListHead, เหมือนกับการที่รายการข้อมูลเชื่อมต่อโหนดที่ใช้ไว้.
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
- การแทรก: นำช่องที่
FreeListHeadมาใช้, ตั้งค่าValueและNextของมัน, จากนั้นเปลี่ยนสายการเชื่อมต่อNextหรือHeadของโหนดก่อนหน้า. การลบ: ถอดโหนดออกจากสายและคืนช่องนั้นกลับไปที่หัวของรายการว่าง.
รายการสองรายการแบ่งปันอาร์เรย์เดียวกัน: รายการข้อมูลและรายการว่าง
ในลิสต์ลิงค์ที่จัดเก็บด้วยอาร์เรย์ ลิสต์ว่าง (free list) จะ:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ลิสต์ว่างเชื่อมโยงช่องสำรองไว้ ดังนั้นเมื่อต้องการแทรกสามารถดึงมาใช้ได้ และเมื่อต้องการลบสามารถนำกลับมาใส่ได้ — เหมือนกับลิสต์ลิงค์ที่สองที่เก็บช่องว่าง
ตัวอย่างวิธีทำ: การแทรกในรายการที่จัดเก็บด้วยอาร์เรย์
DataและPointerอาร์เรย์เก็บรายการ 1 → 3 → 4, โดยมีStart = 1; ดัชนี 1 เก็บD40, ดัชนี 3 เก็บD32, ดัชนี 4 เก็บD11พร้อมตัวชี้ null. รายการว่างเริ่มที่ดัชนี 2 และต่อเนื่อง 2 → 5. แทรกD6ระหว่างD32และD11.- นำโหนดว่างแรกมาคือดัชนี 2, และตั้ง
FreeStartเป็นตัวชี้ของมัน, คือ 5. เก็บD6ลงในData[2]. - ตั้งค่า
Pointer[2]เป็นค่าPointer[3]ที่เก็บอยู่, ซึ่งคือ 4. จากนั้นตั้งPointer[3]เป็น 2. - รายการตอนนี้อ่านได้เป็น 1 → 3 → 2 → 4 และรายการว่างคือ 5 → null. การนำไปใช้, หากถาม: อาร์เรย์สำหรับข้อมูล, อาร์เรย์คู่ขนาน (หรือฟิลด์บันทึก) สำหรับตัวชี้, ตัวชี้เริ่มต้น, และตัวชี้รายการว่าง.
ในตัวอย่างที่แสดงขั้นตอน เมื่อเพิ่ม D6 แล้ว ลิสต์ว่างจะเริ่มที่ดัชนี ____
Difficulty 1/5 · 100 coins + a small bonus on first completion today
索引 2 ถูกดึงจากลิสต์ว่าง ดังนั้น FreeStart จึงย้ายไปยังสิ่งที่索引 2 ชี้ไป ซึ่งคือ 5
เมื่อแทรกเข้าสู่ลิสต์ พอยเตอร์ของโหนดก่อนหน้าควรเปลี่ยนก่อนจะตั้งค่าพอยเตอร์ของโหนดใหม่
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ตั้งค่าพอยเตอร์ของโหนดใหม่ไปยังโหนดถัดไปเดิมก่อน การต่อสายโหนดก่อนหน้าเสียก่อนจะทำให้สูญเสียที่อยู่ของส่วนที่เหลือของลิสต์
คะแนนที่หลุดหายไป
- การตรวจสอบมาก่อนเสมอ: ตรวจสอบความเต็มก่อน push หรือ enqueue, ความว่างเปล่าก่อน pop หรือ dequeue. อธิบายการตรวจสอบ;它们是得分点.
- สูตรการวนกลับขึ้นอยู่กับดัชนี:
(Rear MOD MaxSize) + 1สำหรับแบบเริ่มที่ 1,(Rear + 1) MOD Sizeสำหรับแบบเริ่มที่ 0. ตรงกับขอบเขตของคำถาม. - จำนวนรายการ คือสิ่งที่บอกความแตกต่างระหว่าง队列วงกลมเต็มกับว่างเปล่า. ตัวชี้เพียงอย่างเดียวไม่สามารถทำได้.
- ตั้งค่า
Nextของโหนดใหม่ ก่อน เปลี่ยนสายการเชื่อมต่อของโหนดก่อนหน้า, และคืนช่องของโหนดที่ถูก ลบ กลับสู่รายการว่าง, มิฉะนั้นอาร์เรย์จะค่อยๆ เต็มไปด้วยเซลล์ที่เข้าถึงไม่ได้.
คุณเข้าใจแล้ว
- สแต็กใน array:
Stack[1:MaxSize]และชี้ชี้Topเริ่มต้นที่ 0;Top = MaxSizeคือล้นบน,Top = 0คือล้นล่าง - 队列วงกลม:
FrontและRearวนกลับด้วยMOD; count แยกต่างหากเพื่อแยกความแตกต่างระหว่างเต็มกับว่าง - รายการเชื่อมโยงในอาร์เรย์: บันทึกโหนดที่มี
Nextดัชนี,Head, และ รายการว่าง เชื่อมต่อช่องสำรอง - ทุกการดำเนินการคือการตรวจสอบ, ตามด้วยการคำนวณทางคณิตศาสตร์บนตัวชี้, แล้วจึงจัดเก็บหรืออ่าน; พฤติกรรมของ ADT ไม่เปลี่ยนแปลงโดยวิธีการจัดเก็บ