Arreglo

ที่นั่ง 14C

• โรงหนังมีที่นั่ง 300 ที่ ระบบจองไม่ได้มีตัวแปร 300 ตัวชื่อว่า Seat1A, Seat1B, Seat1C มีเพียง อาเรย์ เดียว และตั๋วของคุณคือที่อยู่ภายในอาเรย์นั้น: แถว 14, ที่นั่ง C
• ชื่อเดียว, หลายร้อยค่า, แต่ละตัวหาได้จากตัวเลข เพิ่มแถวหนึ่งโค้ดก็ไม่ต้องเปลี่ยน;วนซ้ำตามตัวเลขและคุณตรวจสอบทุกที่นั่งแล้ว
• เกือบทุกอัลกอริทึมในกระดาษข้อสอบ 2 จะวนผ่านอาเรย์: ค้นหา, รวม, เรียงลำดับ, หาค่าสูงสุด
• บทนี้คือคำศัพท์, การประกาศ, และอัลกอริทึมสี่ชนิดที่กรรมการถามทั้งในรูปแบบ伪代码และคำพูด

คำศัพท์เฉพาะ

• อาเรย์ เป็นโครงสร้างข้อมูลเก็บจำนวนคงที่ของ องค์ประกอบ ของประเภทเดียวกันภายใต้ชื่อเดียว แต่ละองค์ประกอบเข้าถึงได้ด้วย ดัชนี
• ขอบเขตล่าง และ ขอบเขตบน คือดัชนีที่ถูกต้องตัวแรกและตัวสุดท้าย จำนวนองค์ประกอบคือ ขอบเขตบน − ขอบเขตล่าง + 1
• มิติ คือจำนวนดัชนีที่องค์ประกอบต้องการ: หนึ่งสำหรับรายการ, สองสำหรับตาราง
• ใน ThisArray[n] ← 42 อาเรย์มีหนึ่งมิติ, ดัชนีคือตัวแปร INTEGER n, และองค์ประกอบที่ดัชนียังรับค่า 42

ชื่อเดียว, ดัชนีสำหรับแต่ละองค์ประกอบ, ขอบเขตทั้งสองด้าน

ตัวอย่างที่แสดงวิธีทำ: การประกาศอาร์เรย์ที่งานหนึ่งต้องการใช้

ประมวลผล-array 1-D

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

• ลูป FOR จากขอบเขตล่างไปขอบเขตบนจะ访问ทุกองค์ประกอบครั้งละหนึ่ง
• สำหรับการรวม, นับ, สูงสุด หรือ ต่ำสุด ตั้งตัวแปรสะสมก่อนลูปและอัปเดตภายใน

อาร์เรย์ 2-D

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99      // row 2, column 3

• ดัชนีแรกคือ แถว, ดัชนีที่สองคือ คอลัมน์ ลูปซ้อน akan访问ทุกเซลล์: ลูปนอกวนแถว, ลูปในวนคอลัมน์
• ใช้ 1-D สำหรับลำดับเดียวและ 2-D เมื่อข้อมูลมีสองมิติตามธรรมชาติ เช่น กริดที่นั่งหรือตารางคะแนนตามนักเรียนและวิชา

Grid[row, column], ต้องเรียงตามนั้นเสมอ

ตัวอย่างที่แสดงวิธีทำ: การค้นหาแบบเชิงเส้นที่แจ้งได้ว่า "ไม่พบ"

FoundAt ← -1
FOR i ← 1 TO n
    IF A[i] = Target THEN
        FoundAt ← i
    ENDIF
NEXT i
IF FoundAt = -1 THEN
    OUTPUT "Not found"
ELSE
    OUTPUT "Found at ", FoundAt
ENDIF

ค่าที่ใหญ่ที่สุด และตำแหน่งของค่า tersebut

Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
    IF A[i] > Largest THEN
        Largest ← A[i]
        Position ← i
    ENDIF
NEXT i
OUTPUT Largest, " at ", Position

• เริ่ม Largest ที่องค์ประกอบแรก อย่าเริ่มที่ 0: อาร์เรย์อาจมีค่าติดลบทั้งหมด
• รูปทรงเดียวกันนับหรือแสดงค่าที่ไม่ว่าง: เปรียบเทียบแต่ละค่ากับเครื่องหมายของตำแหน่งที่ไม่ใช้, "" หรือ -1, แล้วนับเฉพาะค่าที่แตกต่างกันเท่านั้น

การเรียงลำดับแบบฟองอากาศ (Bubble sort)

• การเรียงลำดับแบบฟองอากาศ จะวนผ่านอาร์เรย์ซ้ำๆ โดยเปรียบเทียบคู่ที่อยู่ติดกันและสลับตำแหน่งของคู่ที่ผิดลำดับ จนกว่าจะมีการวนผ่านหนึ่งรอบโดยไม่มีการสลับ
• หลังจากการวนผ่านแต่ละรอบ ค่าที่ยังไม่เรียงลำดับและมีขนาดใหญ่ที่สุดจะถูกดันไปไว้ที่ท้ายอาร์เรย์แล้ว ดังนั้นการวนผ่านถัดไปจึงสามารถหยุดก่อนหน้าหนึ่งตำแหน่งได้

REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Limit - 1
        IF Data[Index] > Data[Index + 1] THEN
            Temp ← Data[Index]
            Data[Index] ← Data[Index + 1]
            Data[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Limit ← Limit - 1
UNTIL Swapped = FALSE

การวนผ่านแต่ละรอบจะดันค่าที่เหลืออยู่ที่มีขนาดใหญ่ที่สุดไปที่ท้าย

ตัวอย่างวิธีทำ: ตำแหน่งของเครื่องหมายการเรียงลำดับแบบฟองอากาศ

ตัวอย่างวิธีทำ: การลบและการแทรก

คะแนนที่หลุดหายไป

คุณเข้าใจแล้ว