คิว

คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับสแตก (Stack) และมีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) เช่นกัน มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่าส่วนหน้า (Front) ซึ่งกำหนดคิวเป็นรูปแบบดังนี้

                     Q = [Q1, Q2, . . . , QT]

            โดย Front (Q) คือ Q1 และ Rear (Q) คือ QT มีจำนานสมาชิกในคิวเท่ากับ T ดังในรูปที่ 5.1 โดยลักษณะมีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ด้านท้ายอยู่ด้านขวา และอาจกลับด้านกันก็ได้ให้ตัวชี้ส่วนหน้าอยู่ด้านขวาและตัวชี้ส่วนท้ายอยู่ด้านซ้าย





          สมาชิก Q1 จะเข้ามาก่อนสมาชิก QJ สำหรับ I < J และ QI ซึ่งอยู่ในคิวนานที่สุดและถูกลบออกจากคิวก่อนสมาชิก
ที่เข้ามาหลัง
          ลักษณะของคิวถูกนำมาใช้แก้ไขปัญหาต่างๆในแอปพลิเคชั่นต่างๆ เช่น จำลอง (Simulation) การทำงานของระบบจริงในกิจกรรมแบบเข้าก่อนออกก่อน เช่น การเข้าแถวเพื่อนซื้อของหรือชำระเงินเพื่อตรวจสอบการให้บริการเพียงพอหรือไม่ การนำคิวไปใช้ในการสำรวจพิจารณา (Observation) ตามปริมาณรถติดเพื่อควบคุมไฟจราจรตามทางแยก การนำหลักการของคิว (Queuing Theory) มาใช้ เช่น การส่งข้อมูลข่าวสารในเครือข่าย การส่งแฟ้มข้อมูลไปยังพริ้นเตอร์เพื่อพิมพ์งานตามลำดับคิว หรือรูปแบบการสลับตู้รถไฟบนราง ดังในรูปที่ 5.2










          ปัญหาต่างๆเหล่านี้สามารถแก้ไขโดยใช้โครงสร้างคิวที่มีลักษณะการทำงานในรูปแบบที่เรียกว่าเข้าก่อนออกก่อน (First-In-First-Out, FIFO) หรือเข้ามาก่อนได้บริการก่อน (First-Come-First-Served, FCFS) เมื่อค่าใหม่เข้ามาก็จะไปต่อเป็นส่วนท้ายแทนค่าเดิมที่เก็บอยู่ส่วนท้ายก่อนหน้านี้ไปเรื่อยๆ ถ้าเป็นการดึงค่าออกจากคิวก็จะนำค่าแรกสุดที่อยู่ในคิวดึงออกมาให้ก่อนสมาชิกตัวถัดไปส่วนหน้าแทน


การปฏิบัติการของคิว 

          จากลักษณะของคิวจะมีการปฏิบัติการเข้ามาช่วยการทำงานและจัดการกับคิวให้มีความถูกต้อง โดยมีชุดปฏิบัติการพื้นฐาน ดังต่อไปนี้
          1. CreateQueue () ใช้สร้างคิวใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่างๆ
          2. Insert (value, queue) ใช้เพิ่มค่าใหม่เก็บลงในคิวที่ใช้งานอยู่ และขยับตำแหน่งใหม่ให้กับส่วนท้าย
          3. Remove (queue) ใช้ดึงค่าออกจากคิวที่ใช้งานอยู่และส่งค่า value กลับมาให้และขยับไปยังตำแหน่งถัดไปให้เป็นส่วนหน้า
          4. isEmpty(stack) ใช้ตรวจสอบว่าคิวที่ใช้งานอยู่ว่างหรือไม่ ถ้าไม่มีค่าเก็บไว้เลยจะส่งค่าจริงกลับมาให้

          การนำคิวมาใช้งานเป็นไปตามลำดับดังในรูป (a) ถึง (g) มีการทำงานโดยใช้ชุดปฏิบัติการดังนี้
          a. เริ่มต้นสร้างคิว Qขึ้นมาทำงาน Create Queue (Q) ได้เป็นคิวว่างไม่มีสมาชิกโดยตัวชี้ส่วนหน้าและส่วนท้ายยังไม่มีค่า


          b. นำค่า A เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert (A) ได้คิว Q = [A] ตัวชี้Front = A, Rear =A



          c. นำค่า B เก็บต่อโดยใช้ Insert (B) ได้คิว Q = [A,B] ตัวชี้ Front=A, Rear =B




          d. นำค่า C เก็บต่อโดยใช้ Insert (C) ได้คิว Q = [A, B, C] ตัวชี้ Front=A, Rear =C




          e. ต้องการดึงค่าออกมาโดยใช้ Remove () ได้คิว Q = [ B, C] ตัวชี้ Front=B, Rear =C





          f. นำค่า D, E เก็บต่อโดยใช้ Insert (D) และ Insert (E) ได้คิว Q = [B, C, D, E] ตัวชี้ Front=B, Rear = E




          g. ดึงค่าออกมา 3 ค่า โดยใช้ Remove () 3 ครั้งและเก็บค่า F โดยใช้ Insert (F) ได้คิว Q = [ E, F] ตัวชี้ Front=E, Rear =F



         การทำงานของคิวเมื่อมีค่าใดส่งเข้ามาเก็บเป็นตัวแรกก็จะอยู่ส่วนหน้า ค่าถัดมาก็จะต่อท้ายไปเรื่อยๆ จนตัวสุดท้ายคือส่วนหลัง หากมีการดึงค่าออกมาใช้ ค่าที่อยู่ส่วนหน้าจะถูกดึงออกมาก่อน ลักษณะที่ได้จึงเป็นลำดับการใช้งานทั่วไปและเรียกว่าเข้าก่อนออกก่อน
         ในการสร้างคิวมาใช้งานโดยพื้นฐานจะใช้อาร์เรย์เก็บค่าสมาชิก มีตัวแปร Front และ Rear เป็นตัวชี้ตำแหน่งส่วนหน้าและส่วนท้ายคิว จึงเกิดความลำบากเมื่อการเก็บค่าเข้ามาจนถึงสมาชิกตัวสุดท้ายของอาร์เรย์ ทำให้เพิ่มค่าใหม่เข้ามาอีกไม่ได้ ถ้าหากมีการเพิ่มเข้ามาอีกจะเกิดลักษณะการล้นของข้อมูลในคิว (Queue Overflow) และเมื่อใดมีการดึงค่าในส่วนหน้าออกมาก็ทำให้พื้นที่ส่วนหน้าของอาร์เรย์เกิดว่างและใช้งานไม่ได้ ทำให้ต้องปรับปรุงโดยย้ายค่าที่มีอยู่ส่วนท้ายกลับไปไว้ส่วนหน้าของอาร์เรย์เพื่อนำพื้นที่ว่างกลับมาใช้งานได้ แต่เป็นค่าใช้จ่ายที่ต้องทำงานเพิ่มโดยเฉพาะคิวที่มีขนาดใหญ่ ดังในรูปที่ 5.3 เป็นตัวอย่างคิวที่ใช้อาร์เรย์ขนาดเท่ากับ 5 โดยเพิ่มค่า Insert(70),Insert(80) และ Insert(50) ตามลำดับในรูป (a) จากนั้นดึงออกมา 2 ค่าโดยใช้ Remove() 2 ครั้งได้เป็นรูป (b) และเพิ่มค่า Insert(90) Insert(60) ในรูป (c) เนื่องจากไม่สามารถเพิ่มค่าใหม่ได้อีกจึงต้องขยับค่าที่เก็บอยู่ไปทางซ้ายในรูป (d) พร้อมกับกำหนดค่าตำแหน่งใหม่ให้กับ ตัวแปร Front และ Rear














คิววงกลม 

          แทนที่จะใช้คิวเป็นเชิงเส้นแบบแนวตรงดังที่ผ่านมา ก็มาใช้เป็นคิววงกลม (Circular Queue) ในลักษณะของเส้นรูปวงแหวนเพื่อแก้ไขปัญหาดังกล่าว โดยสมมุติให้อาร์เรย์เป็นวงกลมที่สมาชิกตัวแรกต่อจากสมาชิกตัวสุดท้าย เมื่อเก็บค่าถึงสมาชิกตัวสุดท้ายก็จะเก็บวนต่อไปยังสมาชิกตัวแรก ดังนั้น ในการเพิ่มค่าให้กับ Front และ Rear จะอยู่ในขอบเขตขนาดของอาร์เรย์และให้สมาชิกที่เข้ามาต่อจากตำแหน่งสุดท้ายของอาร์เรย์วนกลับไปยังตำแหน่งแรกโดยการหารเหลือเศษ (Modulo) ด้วย maxSize ดังในรูปที่ 5.4 เป็นตัวอย่างจากรูปที่ 5.3 ที่เปลี่ยนเป็นคิววงกลม ทำให้เพิ่มค่าต่อไปได้และไม่ต้องขยับถอยกลับมา











         สิ่งที่ต้องพิจารณาเมื่อคิวว่างเปล่าสามารถทราบได้จาก Front กับ Rear มีค่าเท่ากัน เช่น เดียวกันเมื่อคิวเต็ม Rear จะวนกลับมาจนมีค่าเท่ากับ Front ทำให้เกิดความสับสนได้ว่าเมื่อ Front และ Rear มีค่าเท่ากันจะเป็นสถานะของคิวว่างหรือคิวเต็ม อย่างไรก็ตามก็สามารถหลีกเลี่ยงปัญหานี้ได้โดยให้สมาชิกที่อยู่ก่อนหน้าสมาชิกในตำแหน่ง Front เป็นตำแหน่งช่องว่างเสมอซึ่งทำให้ทราบว่าคิวเต็มก็ต่อเมื่อ (Rear+1) % maxSize = Front ดังใน รูปที่ 5.5 อย่างไรตามทำให้จำนวนสมาชิกที่เก็บค่าได้เหลือเพียง maxSize -1








          ดังนั้น ชุดปฏิบัติการของคิววงกลมจึงมีการปรับปรุงการทำงานได้เป็นอัลกอริทึมดังในตารางที่ 5.1 สำหรับการเพิ่มค่าลงในคิวด้วย Insert และตารางที่ 5.2 สำหรับการดึงค่าออกจากคิวด้วย Remove ในการตรวจสอบคิวว่างยังคงใช้ isEmpty เหมือนเดิมเมื่อคิวว่างก็ต่อเมื่อค่าของ Front และ Rear เท่ากัน
     













คิวลำดับความสำคัญ 

         คิวอาจมีการจัดลำดับความสำคัญของสมาชิกจึงมีการสร้างเป็นคิวลำดับความสำคัญ (Priority Queue) เช่น ในระบบปฏิบัติการจะให้โปรเซสที่มีความสำคัญที่สุดทำงานก่อน แต่เนื่องจากโปรเซสที่เข้ามาไม่ได้เรียงตามความสำคัญ ซึ่งการจัดลำดับมี 2 แบบ คือ ให้ความสำคัญ จากค่าน้อยไปหาค่ามาก (Ascending) และจากค่ามากไปหาค่าน้อย (Descending) โดยส่วนใหญ่ใช้ค่ามากมีความสำคัญมากกว่า ในการเพิ่มสมาชิกเข้ามาในคิวไม่จำเป็นต้องเข้ามาตามลำดับความสำคัญอาจสลับไปมาได้ แต่การนำออกมาจากคิวจะต้องตามลำดับความสำคัญ ดังนั้น ในการลบสมาชิกออกจากคิวจึงต้องมีการทำงาน 2 เรื่อง คือ ต้องหาสมาชิกที่มีความสำคัญมากที่สุด ทำให้ต้องเข้าไปเรียกใช้งานสมาชิกทุกตัว และเมื่อลบสมาชิกออกจากคิวในช่วงกลางจะต้องทำการขยับสมาชิกตัวถัดไปมาอยู่แทน
         ในการแก้ไขปัญหาทั้งสองเรื่องมีอยู่หลายวิธี เช่นกำหนดตัวแปรให้ชี้ไปยังตำแหน่งสมาชิกที่สำคัญที่สุด หลังจากที่ถูกลบออกไปก็เป็นตำแหน่งว่างทำให้ไม่ต้องขยับสมาชิกตัวอื่นเมื่อเพิ่มสมาชิกใหม่ก็เก็บไว้ตำแหน่งนี้แทน แต่มีข้อเสียก็คือต้องค้นหาสมาชิกที่สำคัญที่สุดทุกครั้งที่มีการลบเช่นเดิม การทำงานแบบนี้จะทำเมื่อมีการลบสมาชิกออกจากคิว แต่มีวิธีที่เหมาะสมกว่าคือการจัดให้สมาชิกทุกตัวเรียงในคิวตามลำดับ โดยสมาชิกในตำแหน่ง Front มีความสำคัญสูงที่สุดและลดหลั่นลงมาจนถึงตำแหน่ง Rear ที่มีความสำคัญน้อยที่สุดการทำงานจะทำเมื่อมีการเพิ่มสมาชิกใหม่เข้ามาในคิว ส่วนการลบสมาชิกในคิวไม่ต้องทำงานเพิ่มเติมดังที่ผ่านมาเพื่อหาสมาชิกที่สำคัญที่สุด เพราะสมาชิกที่ Front จะสำคัญที่สุดสามารถลบออกไปได้ทันที เมื่อใดที่มีสมาชิกใหม่เพิ่มเข้ามาจะทำการจัดเรียงตามลำดับโดยการหาตำแหน่งที่ถูกต้องให้กับสมาชิกใหม่


ตัวอย่างการใช้คิวลำดับความสำคัญ 

          สมมุติให้ระบบคอมพิวเตอร์มีการรับงานเข้ามาเพื่อให้ทำงานโดยมีการกำหนดลำดับความสำคัญ (Priority) ให้แต่ละงานซึ่งมีค่าตั้งแต่ 0 ถึง 10 งานที่มีความสำคัญสูงสุดคือ 10 จะถูกเรียกให้ทำงานก่อน ถ้างานที่มีความสำคัญเท่ากัน งานที่เข้ามาก่อนจะถูกทำงานก่อน (First – Come First – Served, FCFS) โดยระบบปฏิบัติการจะใช้คิวลำดับความสำคัญเป็นตัวควบคุมงาน
(Job Control Block) เมื่อเขียนเป็นโปรแกรมจะได้ดังในตารางที่ 5.3 คือโปรแกรม PrioQue.c
            ตารางที่ 5.3 คือโปรแกรม PrioQue.c 





















































































          การสร้างคิวลำดับความสำคัญในตัวอย่างเป็นการทำงานของงานที่เข้ามาโดยขึ้นกับความสำคัญ แต่ละงานที่ชื่อกำหนดเป็นตัวอักษรตัวเดียวมีค่าได้ตั้งแต่ A ถึง Z และค่าความสำคัญมีได้ตั้งแต่ 0 น้อยที่สุดจนถึง 10 มากที่สุด การเพิ่มงานเข้ามาในคิวไม่ต้องเรียนตามความสำคัญ แต่เมื่อเก็บในคิวจะมีการจัดเรียงลำดับที่ใช้วิธีการจัดเรียงลำดับความสำคัญ แต่เมื่อเก็บในคิวจะมีการจัดเรียงลำดับที่ใช้วิธีการจัดเรียงลำดับข้อมูล (Sorting) มาช่วย จะเห็นว่าการลบงานออกจากคิวยังคงเหมือนเดิม

บทที่

อะเรย์

โครงสร้างข้อมูลอาร์เรย์

จุดประสงค์เชิงพฤติกรรม (Behavioral Objectives)
หลังจากเรียนบทนี้แล้วนักศึกษาจะมีความสามารถดังนี้

1. ศึกษาโครงสร้างข้อมูลอาร์เรย์
2. แสดงตัวอย่างอาร์เรย์หนึ่งมิติ
3. แสดงตัวอย่างอาร์เรย์สองมิติ
4. แสดงตัวอย่างอาร์เรย์หลายมิติ
5. ยกตัวอย่างอาร์เรย์ในหน่วยความจำ
6. จัดบอร์ดเชิงปฏิบัติการ “โครงสร้างข้อมูลอาร์เรย์”
7. สนทนาเชิงปฏิบัติการ “อาร์เรย์ในหน่วยความจำ”
8. อธิบายคำศัพท์ได้ 10 คำ

บทที่ 2 
โครงสร้างข้อมูลอาร์เรย์

                ปกติการเก็บข้อมูลที่มีเพียงค่าเดียวก็สามารถใช้โครงสร้างข้อมูลเบื้องต้น แต่เมื่อลักษณะของข้อมูลเริ่มซับซ้อนและมีจำนวนมากขึ้นจึงไม่เพียงพอที่จะใช้ข้อมูลโครงสร้างข้อมูลเบื้องต้นได้จึงต้องนำโครงการข้อมูลแบบอื่น ๆ มาใช้แทน โดยจะกล่าวถึงโครงสร้างข้อมูลอาร์เรย์ก่อน ซึ่งสามารถเก็บข้อมูลได้เป็นจำนวนมาก ๆ เป็นชุดของข้อมูลที่เกี่ยวข้องกัน

โครงสร้างข้อมูลอาร์เรย์
                อาร์เรย์เป็นโครงสร้างข้อมูลแบบหนึ่งที่ผู้ใช้ต้องกำหนดคุณสมบัติขึ้นมาก่อน  โดยที่อาร์เรย์ประกอบด้วยสมาชิกจำนวนหนึ่งที่เรียกต่อรวมกันตามลำดับที่ถูกมองเป็นตาราง สมาชิกทุกตัวจะมีชนิดข้อมูลที่เป็นแบบเดียวกัน  ในการใช้อาร์เรย์เป็นการเข้าถึงแบบสุ่ม หรือโดยตรง เป็นการอ้างไปยังแต่ละสมาชิกที่ต้องการได้โดยตรง ซึ่งมีตัวชี้ใช้อ้างไปยังแต่ละสมาชิกเรียกว่าดัชนี หรือ Subscript และต้องเป็นเลขจำนวนเต็ม การกำหนดช่วงหรือจำนวนของสมาชิกจะใช้ขอบเขตล่าง ซึ่งมีค่าน้อยที่สุด และขอบเขตบน ซึ่งมีค่ามากที่สุดอาร์เรย์เป็นโครงสร้างข้อมูลที่คงที่ เปลี่ยนแปลงจำนวนสมาชิกไม่ได้ขณะทำงาน และเนื่องจากข้อมูลอาร์เรย์ถูกมองเป็นตารางในการใช้งาน จึงมีการกำหนดลักษณะของอาร์เรย์ออกเป็นมิติต่าง ๆ ได้ดังนี้
อาร์เรย์หนึ่งมิติ
                อาร์เรย์หนึ่งมิติ (One-dimension Array) มีลักษณะที่ง่ายที่สุดเป็นตารางที่มีเพียงแถวเดียว บางครั้งก็เรียกว่าเว็กเตอร์ ดังในรูปที่ 2.1 เป็นอาร์เรย์หนึ่งมิติชื่อ Vec ที่ประกอบด้วยสมาชิก N ตัว

Vec(1)

Vec(2)

…

Vec(I)

…

Vec(N)

รูปที่ 2.1 ตัวอย่างเป็นอาร์เรย์หนึ่งมิติชื่อ Vec มีสมาชิก N ตัว

                อาร์เรย์หนึ่งมิติจะมีดัชนีเพียงตัวเดียวใช้อ้างไปยังตำแหน่งของแต่ละสมาชิกในอาร์เรย์ซึ่งมีค่าเป็นลำดับ สมาชิกแต่ละตัวจะถูกแยกแยะตัวชื่ออาร์เรย์ตามด้วยดัชนีที่อยู่ในวงเล็บดังในรูป  ดังนั้น เมื่อต้องการใช้อาร์เรย์ก็เพียงแต่กำหนดชื่อและใช้ดัชนีอ้างไปยังแต่ละสมาชิก การเขียนอัลกอริทึมจึงใช้โครงสร้างควบคุมการทำงานแบบวนลูปเพื่อใช้ควบคุมสมาชิกแต่ละตัว
การกำหนดอาร์เรย์หนึ่งมิติ 
การกำหนดอาร์เรย์หนึ่งมิติจะมีรูปแบบที่กำหนดไว้เป็นดังนี้
                                V(L:U) = { V(I) }
                สำหรับ I = L,L+1,…,U-1,U ซึ่งสมาชิกแต่ละตัว V(I) จะมีโครงสร้างข้อมูล T หมายความว่าอาร์เรย์ V มีสมาชิกที่มีโครงสร้างข้อมูล T และมีดัชนีมีค่าเริ่มจาก L ไปสิ้นสุดที่ U จะได้ช่วงดัชนีจาก L ไป U เท่ากับ U-L+1 ถ้าหากให้อาร์เรย์ V(1:N) จะได้ช่วงดัชนีเท่ากับ N ในการกำหนดค่าให้กับ L อาจเป็น 0 หรือเป็นค่าติดลบได้ เช่น V(-5:5) และมีช่วงดัชนีเท่ากับ 5-(-5)+1 = 11
ตัวอย่างการใช้อาร์เรย์หนึ่งมิติ
                การนอาร์เรย์หนึ่งมิติมาใช้งานทำได้หลายหลายและมักนำไปใช้ร่วมกับโครงสร้างข้อมูลชนิดอื่น ๆ ดังตัวอย่างต่อไปนี้เป็นการบันทึกอุณหภูมิแต่ละชั่วโมงภายในหนึ่งวันหรือ 24 ชั่วโมง จะเห็นว่าสมาชิกถูกจัดลำดับตามช่วงระยะเวลาของวันสมาชิกเหล่านี้เป็นชนิดเดียวกัน คือ อุณหภูมิ ดังในตารางที่ 2.1 เป็นตัวอย่างโปรแกรม Temp1.c ที่ทำการบันทึกอุณหภูมิและแสดงผล






จากโปรแกรมในตารางที่ 2.1











ผลลัพธ์ที่ได้
                อาร์เรย์ที่สร้างขึ้นมาบันทึกอุณหภูมิมีชื่อว่า Temp โดยดัชนีจะมีค่าที่ขอบเขตล่างเท่ากับ 1 มีค่าที่ขอบเขตบนเท่ากับ 24 จะได้ว่า Temp(I) เป็นอุณหภูมิในช่วงโมงที่ I โดย 1≤ I ≥ 24 และการประกาศตัวแปร Temp ดังนี้
                int Temp [24];
      เนื่องจากต้องมีดัชนีใช้กับอาร์เรย์จึงประกาศป็นตัวแปร I ดังนี้
                Int i;
      การทำงานกับสมาชิกในอาร์เรย์จะใช้การวนลูปเพื่อเก็บค่า ดังนี้
                rand ( time(NULL) );
           for ( i = 0; i < 24; i++ )
           Temp[i] = rand( ) %20+20;
    เป็นการกำหนดค่าให้แต่ละสมาชิกโดยการสุ่มค่าให้ หลังจากนั้นทำการแสดงผลบนหน้าจอ ดังนี้
for ( i = 0; i < 24; i++ )
            printf ( “%d”, Temp [i] );
                การสร้างอาร์เรย์มาใช้งานจะมีโครงสร้างข้อมูลที่มาเกี่ยวข้อง 2 ชนิด เพื่อกำหนดให้สมาชิกในอาร์เรย์และกำหนดให้กับดัชนี นอกจากนี้การใช้ดัชนีอ้างไปยังสมาชิกเพียงบางตัวในอาร์เรย์อาจไม่จำเป็นต้องใช้การวนลูปมาช่วย
อาร์เรย์สองมิติ
                อาร์เรย์สองมิติ (Tow-dimension Array) เป็นอาร์เรย์ที่สมาชิกมีโครงสร้างข้อมูลอาร์เรย์ ลักษณะเป็นตารางที่มีทั้งแถว และคอลัมน์ หรือเรียกว่าแมตทริก ดังในรูปที่ 2.1 เป็นอาร์เรย์สองมิติชื่อ Matrix ที่ประกอบด้วยสมาชิกใยแถว M ตัว แต่ละสมาชิกจะมีสมาชิกในคอลัมน์ N ตัว ก็จะได้เป็นตารางขนาด M ต่อ N

รูปที่ 2.2 ตัวอย่างอาร์เรย์สองมิติชื่อ Matrix มีสมาชิก M*N ตัว
                อาร์เรย์สองมิติจะใช้ดัชนีสองตัวเพื่ออ้างไปยังตำแหน่งของแต่ละสมาชิกแยกกัน โดยดัชนีตัวแรกใช้กับสมาชิกในแถว ส่วนตัวที่สองใช้กับสมาชิกในคอลัมน์ ดังนั้นสมาชิกอาร์เรย์ Matrix(I,J) จึงอยู่ในตำแหน่งแถวที่ I ตำแหน่งคอลัมน์ที่ J อาร์เรย์ Matrix จะเรียกว่าอาร์เรย์มิติ M ต่อ N แต่ละแถวมีสมาชิกเท่ากับ N แต่ละคอลัมน์มีสมาชิกเท่ากับ M จะได้สมาชิกทั้งหมดเท่ากับ M*N
                การเขียนอัลกอริทึมเพื่อใช้อาร์เรย์สองมิติจะนำโครงสร้างควบคุมการทำงานแบบวนลูปมาใช้ 2 ลูป โดยส่วนใหญ่จะให้ลูปแรกอยู่ด้านนอกใช้ควบคุมสมาชิกในแถว ส่วนลูปที่สองซ้อนอยู่ภายในลูปแรกใช้ควบคุมสมาชิกในคอลัมน์

การกำหนดอาร์เรย์สองมิติ
                การกำหนดอาร์เรย์สองมิติจะมีรูปแบบคล้ายกับอาร์เรย์หนึ่งมิติ ซึ่งการกำหนดจะเป็นดังนี้
                                M(L1:U1,L2:U2) = { M(I,J) }
                สำหรับ L1 ≤ I ≤ U1 และ L2 ≤ I ≤ U2 ซึ่งสมาชิกแต่ละตัว M(I,J) จะมีโครงสร้างข้อมูล T
                อาร์เรย์ M มีสมาชิกที่มีโครงสร้างข้อมูล T มีสมาชิกในแถวเท่ากับ U2 – L2 + 1 และมีสมาชิกในคอลัมน์เท่ากับ U1 – L1 + 1 ดังนั้นสมาชิกทั้งหมดจะเท่ากับ (U2 – L2 +1)*(U1 – L1 +1)

ตัวอย่างการใช้อาร์เรย์สองมิติ
                ตัวอย่างที่จะกล่าวถึงเป็นการบันทึกอุณหภูมิแต่ละชั่วโมงภายในหนึ่งวันเช่นเดียวกับตัวอย่างอาร์เรย์หนึ่งมิติ แต่ต้องการจะเก็บอุณหภูมิทุกวันในหนึ่งสัปดาห์ จะเห็นว่าสมาชิกจะถูกจัดลำดับตามช่วงระยะเวลาชั่วโมงของวันและตามช่วงแต่ละวันในหนึ่งสัปดาห์ สำหรับตัวอย่างโปรแกรม คือ Temp2.C ดังในตารางที่ 2.2
ตารางที่ 2.2 ตัวอย่างโปรแกรม Temp2.c




จากโปรแกรมในตารางที่ 2.2
ผลลัพธ์ที่ได้

                อาร์เรย์ที่สร้างขึ้นมาชื่อ Temp มีดัชนีตัวแรกมีค่าที่ขอบเขตล่างเท่ากับ 1 มีค่าที่ขอบเขตบนเท่ากับ 7 ส่วนดัชนีตัวที่สองมีค่าที่ขอบเขตล่างเท่ากับ 1 มีค่าที่ขอบเขตบนเท่ากับ 24 จะได้ว่า Temp(I,J) เป็นอุณหภูมิในชั่วโมงที่ J ของวันที่ I โดย 1 ≤ I ≤ 7, 1 ≤ J ≤ 24 และการประกาศตัวแปร Temp ดังนี้
                int Temp[4] [7] [24];
ดัชนีที่นำมาใช้มีตัวแปร i ใช้กับแถวละตัวแปร j ใช้กับคอลัมน์ ดังนี้
                int i,j;
การทำงานกับสมาชิกในอาร์เรย์จะใช้การวนลูป 2 ลูปเพื่อเก็บค่า ดังนี้
                srand ( time(NULL) );
              for ( i = 0; i < 7; i++ )
                for( j = 0; j < 24; j++ )
                   Temp[i] [j]= rand( ) %20+20;
กำหนดค่าให้สมาชิกโดยการสุ่มค่าให้ จากนั้นแสดงผลบนหน้าจอ ดังนี้
                for ( i = 0; i < 7; i++ ){
                  printf ( "%d", Temp [i] [j] );
                  printf( "\n" );
}

                การสร้างอาร์เรย์สองมอตอมาใช้งานนิยมใช้กับการวนลูปที่ซ้อนกัน 2 ลูป ดังนั้นสิ่งที่ควรพิจารณา คือ การใช้ลูปควบคุมสมาชิกในแถวกับคอลัมน์ควรเป็นอย่างไร จากตัวอย่างการเก็บอุณหภูมิจะเห็นว่าเวลาแต่ละชั่วโมงเป็นส่วนย่อยในแต่ละวัน แต่ละวันเป็นส่วนย่อยของสัปดาห์ การสร้างอาร์เรย์จึงใช้ส่วนหลักกำหนดเป็นแถวคือวัน ส่วนย่อยกำหนดเป็นคอลัมน์คือชั่วโมง เมื่อเขียนโปรแกรมก็จะใช้ลูปข้างนอกเป็นแถว ส่วนลูปข้างในเป็นคอลัมน์ ในกรณีที่เห็นว่าส่วนของแถวและคอลัมน์มีความสำคัญเท่ากัน อาจมีการเปลี่ยนสลับตำแหน่ง โดยการสลับดัชนีระหว่างของแถวและคอลัมน์จากอาร์เรย์ M ต่อ N ไปเป็นอาร์เรย์ N ต่อ M
อาร์เรย์หลายมิติ
                การสร้างอาร์เรย์อาจเป็น สามมิติ สี่มิติ หรือมากกว่านั้นเรียกว่าอาร์เรย์หลายมิติหรือ N- มิติ ดัชนีและช่วงจำนวนสมาชิกก็จะเพิ่มมากขึ้นตามจำนวนมิติ อาร์เรย์ N-มิติจะใช้ค่าดัชนี N ตัวอ้างไปยังตำแหน่งสมาชิกแต่ละตัว การกำหนดอาร์เรย์ N-มิติจะเป็นดังนี้
                M (L1:U1,L2:U2, …,Ln :Un)
                แต่ละสมาชิกของอาร์เรย์จะถูกอ้างถึงโดยกำหนดเป็น M(I1,I2,…,In) ซึ่งแต่ละดัชนีที่
Ik ≤ Ik ≤ Uk สำหรับ k = 1,2,…,N จำนวนสมาชิกทั้งในอาร์เรย์ M เท่ากับ
                (U1 – L1 +1) * (U2 – L2 +1) * … * (Un – Ln +1)
ตัวอย่างการใช้อาร์เรย์หลายมิติ
                ตัวอย่างที่จะกล่าวถึงจะใช้อาร์เรย์สามมิติเพื่อบันทึกอุณหภูมิแต่ละชั่วโมงภายในแต่ละวันของสัปดาห์ และแต่ละสัปดาห์ภายในหนึ่งเดือน ดังนั้น สมาชิกของอาร์เรย์จะถูกจัดลำดับตามชั่วระยะเวลาชั่วโมงของวันและตามช่วงแต่ละวันในหนึ่งสัปดาห์ ช่วงแต่ละสัปดาห์ในหนึ่งเดือนได้เป็นตัวอย่างโปรแกรม คือ Temp3.c ดังในตารางที่ 2.3




ตารางที่ 2.3 ตัวอย่างโปรแกรม Temp3.c
จากโปรแกรมในตารางที่ 2.3
ผลลัพธ์ที่ได้

                อาร์เรย์ Temp มีดัชนีตัวแรกอยู่ในช่วง 1 ถึง 4 ตัวที่สองอยู่ในช่วง 1 ถึง 7 และตัวที่สามอยู่ในช่วง 1 ถึง 24 ซึ่งเป็นจำนวนสัปดาห์ วัน และชั่วโมงตามลำดับ จะได้ว่า Temp(I,J,K) เป็นอุณหภูมิในชั่วโมงที่ K ของวันที่ J ในสัปดาห์ที่ I การประกาศตัวแปร Temp ได้เป็นดังนี้
                int Temp [7] [24];
 เนื่องจากดัชนีหลายตัวอาจสับสนได้ง่าย จึงตั้งชื่อที่มีความหมายให้เข้าใจง่ายดังนี้
                int week,day,hour;
และเป็นอาร์เรย์สามมิติการทำงานกับสมาชิกจึงต้องใช้การวนลูป 3 ลูปเพื่อเก็บค่าดังนี้
                srand (time(NULL) );
           for(week=0;week<4;week++)
                   for(day=0;day<7; day++)
                           for (hour=0;hour<24;hour++)
                                  Temp[week] [day] [hour] = rand( ) %20+20;



หลังจากกำหนดค่าให้แต่ละสมาชิกจะแสดงผลบนหน้าจอดังนี้
                  for (week =0;week<4;week++){
                   printf ("Temperator of week %d \n", week+1);
                   for (day = 0; day<7; day++){
                           printf("Day %d \n", day+1);
                   for (hour =0; hour <24;hour++)
                          printf("%d",Temp[week] [day] [hour] );
                   printf("\n");
                   }
                ตัวอย่างการเก็บอุณหภูมินี้อาจสร้างอาร์เรย์สี่มิติได้โดยเพิ่มการเก็บข้อมูลในช่วงระยะเวลาหนึ่งปี การสร้างอาร์เรย์หลายมิติเริ่มมีความซับซ้อนมากขึ้นและทำความเข้าใจยากจึงนำมาใช้งานน้อย จะมีที่ใช้คือ อาร์เรย์สามมิติดังในตัวอย่างซึ่งมีลักษณะเป็นกล่อง หรือลูกบาศก์ ดังแสดงในรูป 2.3 ที่ยังทำความเข้าใจได้ เป็นอาร์เรย์สามมิติชื่อ Triangle โดยมิติแรกมีช่วงระยะเท่ากับ 2 มิติที่สองมีช่วงระยะเท่ากับ 3 และมิติที่สามมีช่วงระยะเท่ากับ 5 จะมีสมาชิกทั้งหมดเท่ากับ 30 (M*N*P)

รูปที่ 2.3 ตัวอย่างการใช้อาร์เรย์สามมิติชื่อ Triangle มีสมาชิก 30 ตัว (M*N*P)

อาร์เรย์ในหน่วยความจำ
                เช่นเดียวกับโครงสร้างข้อมูลอื่น ๆ ที่ต้องมีแนวทางในการเก็บลงในหน่วยความจำ ซึ่งอาร์เรย์มีได้หลายแนวทาง แบบแผนที่ต้องนำมาพิจารณาประกอบด้วย 4 ลักษณะพื้นฐาน คือ

1. การเข้าถึงเรียกใช้สมาชิกต้องมีความเรียบง่าย
2. ง่ายต่อการเข้าไปหาแต่ละสมาชิกที่มีหลายเส้นทาง
3. ประสิทธิภาพของการจัดเก็บที่ง่ายต่อการเข้าถึงแต่ละสมาชิก
4. ง่ายต่อการเพิ่มขนาดอาร์เรย์ให้มากขึ้น

การเก็บอาร์เรย์หนึ่งมิติในหน่วยความจำ
                เมื่อพิจารณาพื้นที่ในหน่วยความจำที่จะเก็บอาร์เรย์หนึ่งมิติ เช่น อาร์เรย์ Vec ในรูปที่ 2.1 ซึ่งมีดัชนีที่ขอบเขตล่างเท่ากับ 1 ส่วนขอบเขตบนเท่ากับ N วิธีที่จะเก็บอาร์เรย์หนึ่งมิติในหน่วยความจำก็คือ ลำดับของสมาชิกในทางกายภาพ เรียงเป็นแบบเดียวกับลำดับของสมาชิกในทางตรรกะ ดังนั้น พื้นที่จัดเก็บสมาชิก Vec(I+1) จะอยู่ต่อเนื่องจากพื้นที่ จัดเก็บสมาชิก Vec(I) สำหรับ
I = 1,…,N-1 ในการคำนวณหาแอดเดรสเริ่มต้นของสมาชิก Vec(I) จำเป็นต้องทราบในเรื่องต่อไปนี้
                1. ตำแหน่งแอดเดรสเริ่มต้นของพื้นที่หน่วยความจำที่จะเก็บอาร์เรย์ เรียกว่าตำแหน่งเริ่มต้น (Base Location)
                2. ขนาดพื้นที่เก็บแต่ละสมาชิกของอาร์เรย์ กำหนดให้มีขนาด S ไบต์
                    การหาตำแหน่งแอดเดรสของสมาชิกอาร์เรย์ Vec ตัวที่ I จะได้ ดังนี้
                    B + (I – 1)*S
                    หรือกรณีที่ใช้ขอบเขตล่าง L เป็นดังนี้
                    B + (I – L)*S
                เช่น มีอาร์เรย์ Vec(4:10) และต้องการหาตำแหน่งแอดเดรสของสมาชิก Ves(6) โดยตำแหน่งเริ่มต้นอยู่ที่แอดเดรส 2500 และแต่ละสมาชิกมีขนาด 80 ไบต์ ก็จะได้ตำแหน่งแอดเดรสอยู่ที่ 250 + (6 – 4) * 80 = 2660
การเก็บอาร์เรย์หลายมิติในหน่วยความจำ
                เนื่องจากหน่วยความจำของเครื่องคอมพิวเตอร์มีลักษณะเป็นเชิงเส้น ดังนั้น อาร์เรย์หลายมิติ ตั้งแต่สองมิติขึ้นไป เมื่อนำไปจัดเก็บลงในหน่วยความจำจะต้องมีลักษณะแบบเชิงเส้นเช่นกัน
                ลำดับแถวสำคัญ   (Row-Major Order) ทางเลือกหนึ่งที่นำมาใช้คือเก็บสมาชิกทุกตัวของแถวแรกก่อน จากนั้นเก็บแถวที่สอง และสามไปเรื่อย ๆ ดังในรูปที่ 2.4 คือ อาร์เรย์ Mem(1:4,1:6) ซึ่งมีลักษณะรูปแบบตารางในทางตรรกะ

รูปที่ 2.4 อาร์เรย์ Mem (4,6) แสดงเป็นตารางในทางตรรกะ
               



เมื่อนำไปเก็บไว้ในหน่วยความจำซึ่งมีลักษณะเชิงเส้น ลักษณะอาร์เรย์ทางกายภาพก็จะเป็นเชิงเส้นเหมือนกัน ดังในรูปที่ 2.5
รูปที่ 2.5 ลักษณะอาร์เรย์ Mem (1:4,1:6) ในลักษณะแบบลำดับแถวสำคัญ
               
                แบบแผนการจัดเก็บแบบลำดับแถวสำคัญนำมาใช้กับอาร์เรย์ในภาษาเขียนโปรแกรมหลายภาษา เช่น ภาษาโคบอล  ภาษาปาสคาล และภาษาซี ถ้าต้องการทราบแอดเดรสเริ่มต้นของแต่ละสมาชิกในอาร์เรย์สองมิติจะมีวิธีการคำนวณ เช่นหาแอดเดรสเริ่มต้นของสมาชิก Mem(I,J) ในอาร์เรย์ Mem(L1:U1,L2:U2) จะได้ดังนี้
                                                B + (I – L1) * (U2 – L2 + 1) *S + (J – L2) *S
สมมุติต้องการทราบแอดเดรสสมาชิก Mem(2,5) โดยตำแหน่งเริ่มต้นอาร์เรย์คือแอดเดรส 1000 และแต่ละสมาชิกในอาร์เรย์มีขนาด 8 ไบต์ ก็จะได้ 1000+(2-1)*(6-1+1)*8+(5-1)*8 = 1080



ลำดับคอลัมน์สำคัญ (Column – Major Order) เป็นอีกทางเลือกหนึ่งที่เก็บสมาชิกอาร์เรย์ในแนวเชิงเส้นโดยเก็บสมาชิกทุกตัวของคอลัมน์แรกก่อน จากนั้นเก็บคอลัมน์ที่สองและสามไปเรื่อย ๆ อาร์เรย์ Mem ในรูปที่ 2.4 เมื่อเก็บไว้ในหน่วยความจำแบบเชิงเส้นได้เป็นในรูปที่ 2.6

รูปที่ 2.6 ลักษณะอาร์เรย์ Men(4,6) ในลักษณะแบบลำดับคอลัมน์สำคัญ

                แบบแผนการจัดเก็บแบบลำดับคอลัมน์สำคัญมีการใช้ภาษาเขียนโปรแกรม  เช่น
ภาษาฟอร์แทรน ถ้าต้องการทราบแอดเดรสเริ่มต้นของแต่ละสมาชิกในอาร์เรย์สองมอตอจะมีวิธี การคำนวณหาของสมาชิก Men(I,J) จะได้ดังนี้
                                                B + (J – L2) * (U1 – L1 + 1) *S + (I – L1) *S
                ถ้าต้องการทราบแอดเดรสสมาชิก Men(2,5) แบบลำดับคอลัมน์ก็จะได้
1000+(5-1)*(4-1+1)*8+(2-1)*8 = 1136

Link

โครงสร้างข้อมูลลิ้งค์ลิสต์

โครงสร้างข้อมูลลิ้งค์ลิสต์ 

วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ(Sequential)เปลี่ยนมาใช้รูปแบบไม่เรียงตามลำดับ (Non-sequential)ซึ่งรูปแบบการเรียงตามลำดับจะมีสมาชิกเรียงต่อเนื่องติดกันในทางตรรกะ (Logical) และทางกายภาพ(Physical) เป็นแบบเดียวกัน แต่รูปแบบไม่เรียงตามลำดับสมาชิกต่อเนื่องติดกันในทางตรรกะ ส่วนทางกายภาพไม่จำเป็นต้องเหมือนกัน โดยในทางตรรกะจะแสดงด้วยแต่ละสมาชิกมีการชี้ (Point) ต้อไปยังสมาชิกตัวถัดไป สมาชิกทุกตัวในรายการจึงถูกเชื่อมต่อ (Link) เข้าด้วยกัน ดังรูปที่ 6.1 เป็นรายการเชื่อมต่อหรือเรียกว่าลิ้งค์ลิสต์ (Linked List) มีสมาชิก N ตัว แต่ละสมาชิกเรียกว่าโหนด (Node)
จากรูปที่ 6.1 มีตัวแปรพอยน์เตอร์ First ชี้ไปยังโหนดแรกของรายการ แต่ละโหมดมีตัวเชื่อมเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไปโดยโหนดสุดท้ายมีค่าเป็น NULL แสดงให้ทราบว่าไม่ได้ชี้ไปยังโหมดถัดไป แต่ละโหนดเป็นโครงสร้างข้อมูลเรคคอร์ด ประกอบด้วยสองส่วน คือ1.ส่วนเก็บข้อมูล (Info) ใช้เก็บข้อมูลข่าวสารที่มีโครงสร้างข้อมูลเบื้องต้นหรือเรียบง่าย2.ส่วนการเชื่อมต่อ (Next) เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างไปยังโหนดถัดไปในหน่วยความจำ

สำหรับในทางกายภาพของลิ้งค์ลิสต์ แต่ละดหนดไม่จำเป็นต้องอยู่ติดกัน อาจกระจัดกระจายไปยู่ส่วนไหนก็ได้ในหน่วยความจำโดยมีตัวเชื่อมชี้ไปยังตัวตำแหน่งของโหนดถัดไป

ดังที่กล่าวในตอนต้นโครงสร้างสแตกและคิวมีการใช้อาร์เรย์ในการเก็บค่า สมาชิกทุกตัวจึงถูกจำกัดให้เป็นชนิดเดียวกัน(Homogenous) ซึ่งแก้ไขโดยเปลี่ยนมาใช้ลิ้งค์ลิสต์ที่มีโครงสร้างข้อมูลต่างกันได้ นอกจากนี้ยังมีผลดีในการปฏิบัติการแทรกข้อมูลหรือลบข้อมูล เพียงแต่ย้ายการชี้ของตัวแปรพอยน์เตอร์เท่านั้น ทำให้สมาชิกอื่นไม่มีผลกระทบ แต่ในกรณีค่าใช้จ่ายแล้วลิงค์ลิสต์จะสูงกว่าที่ต้องใช้พื้นที่เผิ่มมากขึ้นสำหรับส่วนการเชื่อมต่อเพื่อชี้ไปยังโหนดถัดไป และการค้นหาโหนดที่ต้องการใช้เวลามากเนื่องจากเป็นการค้นหาเรียงตามลำดับ (Sequential Search) ได้โหนดเดียวโดยเริ่มต้นที่โหนดแรกเสมอ