โครงสร้างข้อมูลแบบ stack

เรื่อง Stack

เนื้อหา
- โครงสร้างข้อมูลแบบสแตก
- การดำเนินงานพื้นฐานของสแตก

- การแทนที่ข้อมูลของสแตก
- การประยุกต์ใช้สแตก

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบสแตกและการทำงาน
2. เพื่อให้นักศึกษาทราบการดำเนินงานพื้นฐานของสแตก
3. เพื่อให้นักศึกษาทราบการแทนที่ของข้อมูลแบบสแตก

4. เพื่อให้นักศึกษาทราบวิธีการประยุกต์ใช้สแตก

สแตก(Stack)เป็นโครงสร้างข้อมูลที่ ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่าการเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวกัน ซึ่งเรียกว่า Topของสแตก (Top Of Stack)และ ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)การดำเนินงานพื้นฐานของสแตกการทำงานต่าง ๆของสแตกจะกระทาที่ปลายข้างหนึ่งของสแตกเท่านั้นดั้งนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วยกระบวนการ 3กระบวนการที่สำคัญ คือ

1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล iในสแตกจะได้ push(s,i)คือ ใส่ข้อมูล i ลงไปที่ท็อปของสแตก sในการเพิ่มข้อมูลลงในสแตก จะต้องทำการ ตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม้เต็มก็ สามารถเพิ่มข้อมูลลงไปในสแตกได้แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow)ก็จะไม่สามารถเพิ่มข้อมูลเขาไปในสแตกได้อีก

2.Pop คือการนำข้อมูลออกจากส่วนบนสุดของสแตกเช่น ต้องการนำข้อมูลออกจากสแตกsไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนำข้อมูลออกจากสแตกถ้าสแตกมีสมาชิกเพียง 1ตัวแล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง(Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลยแต่ถ้าไม่มีสมาชิกในสแตกแล้วทำการ popสแตกจะทำให้เกิดความผิดพลาดที่เรียกว่าStack Underflow เพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบก่อนว่าสแตกว่างหรือเปล่าจึงจะนำข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำออกไป3.Stack Top ป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตกตัวอย่าง
การแทนที่ข้อมูลของสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที้ข้อมูลของสแตกแบบลิงค์ลิสต
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสตจะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data)และพอยเตอร์ ที่ชี้ไปยังข้อมูลการดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
2. Push Stack
3. Pop Stack
4. Stack Top
5. Empty Stack
6. Full Stack
7. Stack Count
8. Destroy Stack

แบบฝึกหัด

1.การนำข้อมูลเข้าสแต็กเรียกว่าอะไร

  ก. Push

  ข. Pop

  ค. Stack

  ง. Top

2. คุณสมบัติของสแต็กที่เรียกว่า LIFO เนื่องจากสาเหตุใด

  ก. มีบัฟเฟอร์สำรองและจัดสรรการเข้าออกของข้อมูล

  ข. ข้อมูลเข้าก่อนออกก่อนข้อมูลเข้าทีหลัง ออกทีหลัง

  ค. ข้อมูลเข้าก่อนออกทีหลัง ข้อมูลเข้าที่หลังออกก่อน

  ง. ข้อมูลเข้าก่อนมีสิทธิออกก่อน หรือทีหลังก็ได้

3. ข้อใดที่กล่าวถึง Operations เกี่ยวกับสแต็กไม่ถูกต้อง

  ก. Push A

  ข. Push 20

  ค. Pop A

  ง. Pop

4. ขณะที่สแต็กว่าง ถ้ามีการดำเนินการ Push W , Push D , Push x , Push Q , หลังจากนั้นทำการ Pop ค่าที่ออกจากแสต็กคือค่าใดบ้าง

  ก. W    D     X       Q

  ข. W    D     Q       X

  ค. Q     X     D      W

  ง. Q     X     W     D5. ข้อใดที่เป็นนิพจน์อินฟิกซ์

  ก. A+B-C

  ข. +AB-C

  ค. +-ABC

  ง. AB+C-

6. ข้อใดที่เป็นนิพจน์โฟสต์ฟิกซ์

  ก. A+B-C

  ข. +AB-C

  ค. +-ABC

  ง. AB+C-

7. ข้อใดเป็น Operators ทั้งหมด

  ก. +   -   *   /    ^

  ข. +  ( )    =   >

  ค. A     Z     %    ( )   ^

 ง. +    %    ( )   ^

8. นิพจน์ AB+  เรียกว่านิพจน์อะไร

  ก. นิพจน์อินฟิกซ์

  ข. นิพจน์โพสต์ฟิกซ์

  ค. นิพจน์พรีฟิกซ์

  ง. ไม่มีข้อใดถูก

9. แปลงนิพจน์ A+B/C*D=E

  ก. ABC/D*+E-

  ข. ABC/D*E+ -

  ค. ABC/D+E* -

  ง. ABC/D*E+ -

10. แปลงนิพจน์พรีฟิกซ์ - 5 + 9 * 3 – 1 2 เป็นนิพจน์โพสต์ฟิกซ์ได้คำตอบตามข้อใด

  ก. 5    9     3    1     2     -      *     +     -

  ข. 5  -  9   +   3   *   1   -   2

  ค. 5   9   -  3   *  1   +   2    

  ง. -    +     *    -   5     9      3      1      2

โครงสร้างข้อมูลแบบทรี

โครงสร้างข้อมูลแบบทรี

เรื่อง Tree

เนื้อหา

- โครงสร้างข้อมูลแบบทรี

- นิยามของทรี

- นิยามที่เกี่ยวข้องกับทรี

- การแทนที่ทรีในหน่วยความจำหลัก

- การแปลงทรีทั่วไปให้เป็นไบนารีทรี

- การท่องไปในทรี

- เอกซเพรสชั่นทรี

- ไบนารีเซิร์ชทรี

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบทรี

2. เพื่อให้ทราบนิยามของทรี และที่เกี่ยวข้อง

3. เพื่อให้นักศึกษาทราบวิธีการแทนที่ทรีใน หน่วยความจำหลัก

4. เพื่อให้นักศึกษาทราบการแปลงทรีให้เป็นไบ นารีทรี

5. เพื่อให้นักศึกษาทราบวิธีการท่องไปในทรี

6. เพื่อให้นักศึกษาทราบกระบวนการเอกซเพรสชั่นทรี

7. เพื่อให้นักศึกษาทราบวิธีการไบนารีเซิร์ซทรี

ทรี (Tree)ป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่าง โหนดจะมัความสัมพันธ์ลดหลั่นกันเป็นลำดับ เช่น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน ต่าง ๆ อย่างแพร่หลาย สวนมากจะใชสำหรับแสดง ความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ เป็นต้นแต่ละโหนดจะมีความสัมพันธ์กับ โหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆโหนด เรียกโหนดดั้งกล่าวว่า โหนดแม่(Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหดราก (Root Node) Data Structure โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน รียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง โหนดสองโหนดเรียกว่า กิ่ง (Branch)

               

นิยามของทรี1. นิยามทรีด้วยนิยามของกราฟ ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop)ในโครงสร้าง โหนดสองโหนด ใดๆในทรีต้องมีทางตัดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง ทั้งหมด N-1 เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4

              

             

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า นัลทรี (Null Tree)และถามโหนดหนึ่งเป็นโหดราก ส่วนที่เหลือจะแบ่งเป็น ทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี

นิยามที่เกี่ยวข้องกับทรี1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือเซตของทรีทแยกจากกัน (Disjoint Trees  

3.ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกันหรือทรีที่มีรูปร่างของทรีเหมือนกันโดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด

4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน

5.กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ เช่น

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

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

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

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

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

โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสองหรือแต่ละโหนดมีจำนวน ทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)

ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree)สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ถ้ากำหนดให้ Lคือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า

ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ L มีจำนวนโหนด 2L - 1โหนด
นั้นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่ มี L ระดับ สามารถคำนวณได้จากสูตรดั้งนี้

การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลง ดั้งต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จบให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

แบบฝึกหัด

1.โครงสร้างข้อมูลแบบต้นไม้เป็นโครงสร้างชนิดใด

  ก. ชนิดเชิงเส้น

  ข. ชนิดไม่เชิงเส้น

  ค. ชนิดตัดสินใจเลือก

  ง. ชนิดทำงานซ้ำ

2. โหนดพิเศษโหนดหนึ่งที่อยู่บนสุดแรกเรียกว่าอะไร

  ก. Father

  ข. Subtree

  ค. Leat Node

  ง. Root Node

3. Level มีความหมายตรงกับข้อใด

  ก. รูท

  ข. ดีกรีของโหนด

  ค. โหนดที่เป็นใบ

  ง. ระดับของโหนด

4. ดีกรีของโหนดคืออะไร

 ก. รูทโหนด

  ข. จำนวนต้นไม้ 1 ต้น

  ค. ต้นไม้แบบพรีออเดอร์

  ง. จำนวนต้นไม้ย่อยของโหนดนั้น

5. ป่าไม้ในโครงสร้างข้อมูลแบบต้นไม้ หมายถึงสิ่งใด

  ก. กลุ่มของต้นไม้

  ข. ต้นไม้ย่อยซ้าย

  ค. ต้นไม้ย่อยขวา

  ง. การดูแลต้นไม้6. โครงสร้างข้อมูลแบบต้นไม้ มีลักษณะคล้ายสิ่งใด

  ก. ใบไม้

  ข. รากของต้นไม้

  ค. ลำต้นของต้นไม้

  ง. กิ่งก้านของต้นไม้

7. ต้นไม้ธรรมชาติจะงอกจากล่างขึ้นบน ส่วนโครงสร้างข้อมูลแบบต้นไม้นั้นจะเจริญเติบโตอย่างไร

  ก.จากล่างไปบน

  ข. จากบนลงล่าง

  ค. จากซ้ายไปขวา

  ง. จากขวาไปซ้าย

8. ต้นไม้ Binary ที่แต่ละโหนดภายในจะมีโหนดย่อยซ้ายโหนดย่อยขวาและโหนดใบหมายถึงต้นไม้แบบใด

  ก. ต้นไม้ไบนารีคู่

  ข. ต้นไม้ไบนารีเดี่ยว

  ค. ต้นไม้ไบนารีแบบสมบูรณ์

  ง. ต้นไม้ไบนารีแบบไม่สมบูรณ์

9. ข้อใดไม่ใช่การแทนต้นไม้ไบนารีในหน่วยความจำ

  ก. การแทนโดยอาศัยพอยน์เตอร์

  ข การแทนโดยอาศัยแอดเดรสของโหนด

  ค. การแทนแบบวีแควนเชียล

  ง. การแทนแบบลำดับชั้น

10. LVR คือวิธีการเดินเข้าแบบใด

  ก. แบบพรีออร์เดอร์

  ข. แบบอินออร์เดอร์

  ค. แบบโพสต์ออร์เดอร์

  ง. ไม่มีข้อใดถูก

เฉลย

1.  ง. Root Node

2.  ง. Root Node

3.  ง. ระดับของโหนด

4.  ง. จำนวนต้นไม้ย่อยของโหนดนั้น

5. ก. กลุ่มของต้นไม้

6 .ง. กิ่งก้านของต้นไม้

7.  ข. จากบนลงล่าง

8.  ค. ต้ไนม้ไบนารีแบบสมบูรณ์

9.  ง. การแทนแบบลำดับชั้น

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

แบบทดสอบเรื่องอาเรย์

1.โปรแกรมใดที่จำเป็นต้องใช้ตัวแปรอาร์เรย์

  ก. โปรแกรมคำนวณหาพื้นที่รูปวงกลม

  ข. โปรแกรมคำนวณหาพื้นที่รูปวงกลม 20 วง

  ค. โปรแกรมคำนวณหาพื้นที่และเส้นรอบวงของวงกลม

  ง. โปรแกรมหาพื้นที่วงกลมใดที่มีค่ามากที่สุดจาก 20 วง

2. ถ้าตัวแปร A เป็นตัวแปรแบบอาร์เรย์แล้ว กลุ่มข้อมูลใดสามารถจัดเก็บตัวแปร A ได้

  ก. 25 ,    60  ,    boy ,    T

  ข. A ,   B ,   C ,    D

  ค. Dog ,   cat  2.50

  ง. True ,   Somsri ,   10.25

3. จากโปรแกรมต่อไปนี้  Data  มีผลลัพธ์เป็นเท่าไร

         Program  Test  1

         Var Data : integer

         Begin

            Data : = 60;

            Data : = 20;

            Writeln (Data);

          End

  ก. 60

  ข. 20

  ค. 80

  ง. 40

4. ข้อใดต่อไปนี้ที่ผู้เขียนโปรแกรมควรกำหนดเป็นตัวแปรอาร์เรย์

  ก. I  เก็บค่านับรอบของลูป จำนวน 20 รอบ

  ข. Score เก็บค่าคะแนนนักศึกษา 20  คน

  ค. Mean เก็บคะแนนเฉลี่ยนักศึกษา 20 คน

  ง. Max เก็บคะแนนนักศึกษาที่มีคะแนนสูงสุดจาก 20 คน

5. ตัวแปรอาร์เรย์ต่างกับตัวแปรเดี่ยวอย่างไร

  ก. ตัวแปรอาร์เรย์เก็บค่าในฮาร์ดดิสก์ตัวแปรเดี่ยวเก็บค่าใน RAM

  ข. ตัวแปรอาร์เรย์เก็บค่าแบบ Numeric ตัวแปรเดี่ยวเก็บค่าแบบ String

  ค. ตัวแปรอาร์เรย์เก็บค่าคงที่ ตัวแปรเดี่ยวเก็บค่าเปลี่ยนแปลงได้

  ง. ตัวแปรอาร์เรย์เก็บค่าได้หลายค่า  ตัวแปรข้อมูลเดี่ยวเก็บค่าได้เพียงค่าเดี่ยว

6. ประกาศตัวแปร A:array[1..20] of integer; ตัวแปรอาร์เรย์ชุดที่ประกาศนี้สามารถเก็บค่าได้ทั้งหมดกี่ค่า

  ก. 1 ค่า

  ข. 19 ค่า

  ค. 20 ค่า

  ง. 21 ค่า

7. J : Array [1..100, 1..5] of integer; ตัวแปรอาร์เรย์ J ประกอบด้วยสมาชิกกี่ค่า

  ก. 5

  ข. 100

  ค. 50

  ง. 500

8. ข้อใดคือความหมายของโครงสร้างข้อมูลแบบอาร์เรย์

  ก. กลุ่มข้อมูลที่มีค่าชนิดเดียวกัน

  ข. กลุ่มข้อมูลที่เป็นตัวเลขเท่านั้น

  ค. กลุ่มข้อมูลที่มีความสัมพันธ์กัน

  ง. กลุ่มข้อมูลที่มีการลดความซ้ำซ้อน

9. ถ้าประกาศตัวแปรอาร์เรย์ดังนี้ Data : array [1…5] of integer; ข้อมูลใดไม่สามารถเก็บในอาร์เรย์ชุดนี้ได้

  ก. 500         20             40            25            2.5

  ข. 601         2                0             13           100

  ค. 1            0                0               0              1

  ง. 0            0                0                0              0

10. การประกาศตัวแปรอาร์เรย์เพื่อใช้งานต้องประกอบด้วยอะไรบ้าง

  ก. ชื่ออาร์เรย์    ชนิดข้อมูล

  ข. ชื่ออาร์เรย์    ค่าสูงสุดและค่าต่ำสุด     ชนิดข้อมูล

  ค. ชื่ออาร์เรย์    ค่าสูงสุดและค่าต่ำสุด     มิติของอาร์เรย์     ชนิดข้อมูล

  ง. ชื่ออาร์เรย์    ค่าสูงสุดและค่าต่ำสุด     มิติของอาร์เรย์     ชนิดข้อมูล     จำนวนสมาชิก