โครงสร้างข้อมูลชนิดต่างๆ

โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked list)              

             โครงสร้างข้อมูลแบบนี้จะให้ความสะดวกแก่การจัดการข้อมูลมากอย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่องเมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวกเนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มากในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า    การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใดลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง

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

 

รูปการแทนโครงสร้างแบบลิงค์ลิสต์

               ข่าวสาร A อยู่ที่ตำแหน่ง 5000 ดูได้จากค่าที่ตำแหน่ง 6000 ผู้ใช้จะต้องรู้ว่า head node ของค่าชุดนี้อยู่ที่แอดเดรส 6000 ส่วนค่า A,B,C ผู้ใช้ไม่ทราบว่าอยู่ที่ใดยกเว้นแต่จะตามพอยน์เตอร์เข้าไป จากตำแหน่ง 6000 เรารู้ว่าค่าที่อยู่ที่ตำแหน่ง 5000 คือค่าแรก (ค่า A ) จากส่วนพอยน์เตอร์ของ A (ที่ตำแหน่ง 5001) เรารู้ว่าค่าถัดไป (ค่าB) อยู่ที่ตำแหน่ง 5600 เราตามพอยน์เตอร์ไปยังตำแหน่ง 5600 พบ B ค่าพอยน์เตอร์ของ B ที่ตำแหน่ง 5601 เป็นแอดเดรสของค่าถัดไป (ค่า C) ซึ่งอยู่ที่ตำแหน่ง 5508 จากค่า C เมื่อพิจารณาค่าพอยน์เตอร์ของ C พบว่าค่า - 1 ซึ่งหมายถึงว่าสิ้นสุดของค่าชุดนี้แล้ว อนึ่งผู้ใช้ไม่สามาร5นำค่า A หรือ B หรือ C มาใช้โดยตรงอย่าในอาร์เรย์ ผู้ใช้ต้องเดิน เข้าไปหาค่าเหล่านี้ลักษณะการหาค่าแบบนี้คล้าย ๆ กับการหาค่าในเทปซึ่งเรียกว่า การหาค่าแบบลำดับ (sequential access) ซึ่งในทางปฏิบัติสำหรับระบบโปรแกรมภาษาชั้นสูงเราอาจใช้อาร์เรย์เป็นตัวเก็บค่า A,B,C และใช้อีกหนึ่งอาร์เรย์เป็นตัวเก็บพอยน์เตอร์ดังรูปซึ่งผู้ใช้ต้องทราบว่าค่าแรกของข่าวสารชุดนี้อยู่ที่ตำแหน่งที่ 2 ในอาร์เรย์ INFO (3)

 

รูปการแทนลิงค์ลิสต์ด้วยอาร์เรย์ 2 ชุด

ลิงค์ลิสต์เดี่ยว (Singly Linked List)

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

              NODE(P) หมายถึงโหนดที่ระบุ(ถูกชี้) โดยพอยน์เตอร์P
              INFO(P) หมายถึงส่วนข่าวสารของโหนดที่ถูกชี้โดย P
              LINK(P) หมายถึงส่วนแอดเดรสของโหนดที่ถูกชี้P

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

  แนวความคิดเรื่อง storage pool นั้น ตีความได้ในงานจริง ๆ เช่น storage pool อาจประกอบด้วยเก้าอี้นั่งทั้งหมดในเครื่องบินโดยสารลำหนึ่งหรือเป็นจำนวนที่นั่งที่ยังไม่ได้จองของสายการบินหนึ่งในเวลาใด ๆ

               1.1การจัดสรรหน่วยเก็บข้อมูล(Storage Allocate) การจัดสรรหน่วยเก็บข้อมูลเป็นการนำโหนดออกจากหรือคืนโหนดสู่ storage pool ซึ่งจะสมมติว่ากระทำโดยฟังก์ชัน 2 ชุด คือ ALLOCATE P และ FREE P ซึ่งจะนิยามดังนี้
              ALLOCATE P :นำโหนดหนึ่งออกจาก ALLOCATE P แล้วให้พอยน์เตอร์P ชี้ไปยังโหนดนั้น
              FREE P : คืนโหนดที่ถูกชี้โดย P ไปยัง storage pool

             การทำงานของ ALLOCATE P ดูได้จากรูปที่ 6 ซึ่งสมมติว่า storage pool ประกอบด้วยโหนด5 โหนด หลังการประมวลผล storage pool จะประกอบด้วย 4 โหนดและโหนดP เป็นโหนดที่นำมาใช้ได้ ฟังก์ชัน ALLOCATE P สามารถเขียนเป็นชุดคำสั่งได้ดังนี้

             1.IF AVAIL = - 1 THEN แจ้งผู้ใช้ว่าไม่มีโหนดเหลือใน storage pool;
             2.P = AVAIL ; / * ให้ P ชี้ไปยังโหนดแรก * /
             3.AVAIL = LINK (AVAIL) ; / * ดูรูปที่ 4.7 * /

 


รูปการทำงานของ storage pool และคำสั่ง ALLOCATE P

                    LINK(AVAIL) หมายถึงส่วนพอยน์เตอร์ของโหนดแรกซึ่งบอกค่าตำแหน่งของโหนดถัดไปใน storage pool ดังนั้นค่า AVAIL ใหม่ คือแอดเดรสของโหนดที่สอง (อนึ่งเราจะได้ผลเหมือนกันถ้าเขียนว่า AVAIL = LINK (P) แทนคำสั่งที่ 3 ) ก็เพียงแต่โยงลูกศรไปยังโหนดถัดไปการทำความเข้าใจระบบการใช้งานของลิงค์ลิสต์ไม่มีทางใดดีกว่าวาดรูปการทำงานของแต่ละคำสั่ง ต่อไปนี้จะแสดงวิธีการทำความเข้าใจแบบนี้ตลอดหนังสือเล่มนี้ดังนั้นของให้ผู้อ่านฝึกหัดตามไปด้วย
                    ต่อจากคำสั่ง ALLOCATE P เป็นการทำความเข้าใจกับคำสั่ง FREE P ชุดคำสั่งแทน FREE P จะเป็นดังนี้

                     1.IF AVAIL = - 1 THEN DO ; AVAIL = P;
                     2. LINK(AVAIL) = - 1
                     3. END ;
                     4. ELSE DO ; LINK(P) = AVAIL ;
                     5. AVAIL = P; 6. END;

                   1.2 การนำข้อมูลเข้าสู่และออกจากลิงค์ลิสต์(Insertion and Deletion)

                   ก่อนอื่นขอให้พิจารณาดูการนำข่าวสาร 5 เข้าสู่อาร์เรย์A (ซึ่งมี 10 ช่อง) ที่ตำแหน่ง 3 ดังรูปที่ 10 เพื่อให้ค่าต่าง ๆ เรียงอยู่ในลำดับที่ถูกต้องจะเห็นได้ว่าในลักษณะนี้จะต้องมีการเลื่อนข่าวสารในอาร์เรย์อย่างมากเพื่อเปิดทางให้กับตัวที่เข้ามาใหม่กระบวนการเช่นนี้จะเสียเวลามากถ้าแต่ละข่าวสารเป็นเรคอร์ด (record) ขนาดใหญ่ในระบบที่มีการใช้ลิงค์ลิสต์ การนำข่าวสารเข้าหรือออกจะสะดวกมากเนื่องจากสามารถทำสำเร็จได้โดยคำสั่งไม่กี่คำสั่งเพื่อเปลี่ยนค่าพอยน์เตอร์อย่างมาก 2 ค่า เท่านั้น

                  1) การนำข้อมูลเข้า (Insertion) สมมติว่าเรามีลิงค์ลิสต์ H อยู่แล้ว (โหนดที่ถูกชี้โดย H คือ head node ของลิงค์ลิสต์นี้ ) และเราต้องการนำข่าวสารที่ถูกชี้โดยพอยน์เตอร์P (หรือโหนดP) ไปอยู่ต่อจากโหนดH1

INSERT : PROCEDURE (X,H1) /* ต้องการนำข่าวสาร X เข้าไปต่อท้ายโหนดที่ถูกชี้โดย H1 ในลิงค์ลิสต์ที่มี head node H */
/* ให้ Q เป็นพอยน์เตอร์ที่จะใช้ชั่วคราว */
/* เราจะนำ X มาใช้โดยตรงไม่ได้ ต้องสร้างโหนดเพื่อเก็บ X เสียก่อน */
ALLOCATE Q ;
INFO(Q) = X ;

/* ก่อนจะนำ X เข้า ต้องตรวจสอบกรณีพิเศษสองกรณีคือ (1) ตรวจสอบว่าลิงค์ลิสต์ H นี้ว่างเปล่าหรือไม่ (2) ตรวจสอบว่า H1 เป็นโหนดสุดท้ายหรือไม่ */
IF H = NULL / * สมมติว่าค่า NULL ทำงานเช่นเดียวกับ - 1 */ THEN /* แสดงว่าลิงค์ลิสต์ H ว่างเปล่า */ แจ้งให้ผู้ใช้ทราบและจบ ;
IF LINK(H1) = NULL
THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */
LINK (Q) = NULL;
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1);
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1);
LINK (H1) = Q;
/*ในที่สุดเราจะได้ลิงค์ลิสต์ใดแล้วแต่กรณี*/
หรือ

END

INSERT;

 

                     2)การนำข้อมูลออก (Deletion) ในการนี้เราต้องการนำข้อมูลในโหนดที่ต่อถัดจากโหนดH1 มาไว้ในตัวแปร X และให้คืนโหนดนั้นไปยัง storage pool

DELETE : PROCEDURE(X,H1)
/* ฟังก์ชันนี้จะนำข่าวสารในโหนดที่ถัดจาก H1 ไปเก็บไว้ใน X แล้วคืนโหนดนั้นไปยัง storage pool*/ /* มีกรณีพิเศษที่ต้องพิจารณาสามกรณีคือ
1)ลิงค์ลิสต์ H ว่างเปล่า
2)ลิงค์ลิสต์ H ประกอบด้วยโหนดเดียว
3)โหนดH1 เป็นโหนดสุดท้าย */

IF H = NULL
THEN /*แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */ แจ้งให้ผู้ใช้ทราบ ,จบ ;
IF LINK(H) = NULL THEN /* แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */แจ้งให้ผู้ใช้ทราบ , จบ;
IF LINK (H) =NULL และ LINK(H1) = NULL THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */ แจ้งให้ผู้ใช้ทราบ , จบ ;
/* เข้าสู่จุดนี้แสดงว่ามีโหนดต่อถัดจากโหนดH1 */
/* ให้ Q เป็นพอยน์เตอร์ชั่วคราว */

 

ขอให้สังเกตว่าเราไม่สามารถนำโหนดH1 ออกโดยตรงได้ทั้งนี้เนื่องจากว่าเราไม่ทราบว่าโหนดก่อนโหนดH1 อยู่ที่ใด ถ้าจะในโหนดH1 ออกเราต้องหาว่าโหนดก่อนโหนดH1 อยู่ที่ใด ซึ่งจะทำได้โดยเดินเข้าไปในลิงค์ลิสต์ตั้งต้นจาก H ตามพอยน์เตอร์ไปเรื่อย ๆ จนกว่าจะพบโหนดH1 การเดินเข้าไปในลิงค์ลิสต์จะมีความสำคัญซึ่งเราจะอธิบายถึงวิธีการดังกล่าวในหัวข้อต่อไป

                      3)การท่องไปในลิงค์ลิสต์สมมติว่ามีลิงค์ลิสต์ H อยู่แล้ว ถ้าจะหาว่าข่าวสาร X อยู่ในลิสต์นี้หรือไม่เราจะสามารถรู้ได้โดยการค้นหาแบบลำดับ (sequential search) ตามลำดับ ตั้งต้นจาก H การท่องไปในลิงค์ลิสต์ใหม่ไม่ได้ ดังนั้นเราจะใช้พอยน์เตอร์อีกตัวมาเป็นผู้ช่วย (auxiliary pointer) เพื่อดึงตัว H1 ไปยังโหนดถัดไ»

เมื่อเราเข้าใจถึงวิธีการท่องไปในลิงค์ลิสต์แล้ว อัลกอริทึม เพื่อหาค่า X จะเขียนได้ดังนี้

SEARCHX : PROCEDURE (X) ;
/* อัลกอริทึมนี้จะหาว่า X อยู่ในลิงค์ลิสต์ H หรือไม่ */
/* ให้ H1 = เป็นพอยน์เตอร์ชั่วคราว */
IF H = NULL THEN แจ้งให้ผู้ใช้ทราบว่าลิงค์ลิสต์ H ว่างเปล่า , จบ ;
H1 = H ; /* H1 ชี้ไปยังโหนดที่อยู่หัวของลิงค์ลิสต์ */
DO WHILE (INFO(H1)นX)
IF LINK(H1) = NULL THEN GOTO OUT ;
H1 = LINK(H1);
END;
OUT:IF INFO(H1) = X THEN แจ้งให้ผู้ใช้ทราบ , จบ;
มิฉะนั้นแจ้งให้ผู้ใช้ทราบว่า X ไม่อยู่ในลิงค์ลิสต์ H ;
END SEARCHX;

                     1.3 ลิงค์ลิสต์แบบวงกลม (Circular linked list)  เมื่อเราให้พอยน์เตอร์ของโหนดสุดท้ายในลิงค์ลิสต์(ที่มีโหนดแรกคือโหนด H) ชี้ไปยังโหนดแรก เราจะได้โครงสร้างลิงค์ลิสต์แบบวงกลมดังรูปที่18 โครงสร้างแบบนี้สะดวกกว่าแบบลิงค์ลิสต์เดี่ยวธรรมดาในแง่ที่ว่าถัดจากโหนดสุดท้ายก็เป็นโหนดแรกเลยดังนั้นการไล่พอยเตอร์จึงมีความสะดวกในบางครั้งเพราะพอยน์เตอร์จะไม่มีโอกาสตกหายไประหว่างการท่องไปในลิงค์ลิสต์

ลิงค์ลิสต์คู่ (Doubly Linked List)

                    ลิงค์ลิสต์คู่ (Doubly Linked List) ลิงค์ลิสต์แบบนี้เป็นลิงค์ลิสต์ที่แต่ละโหนดมีสองพอยน์เตอร์คือ LLINK และ RLINK ซึ่งจะชี้ไปยังโหนดข้างซ้ายและข้างขวาของโหนดนั้นตามลำดับ ตัวอย่างเช่นถ้าต้องการจะเก็บค่า A,B,C,D ในลิงค์ลิสต์ชนิดนี้จะได้โครงสร้างซึ่งปลายทั้งสองข้างของลิงค์ลิสต์ชนิดนี้จะมีพอยน์เตอร์ F และ R แสดงถึงโหนดแรกในทิศนั้น ถ้าใช้อาร์เรย์สร้างลิงค์ลิสต์ตามรูปที่ 19 จะต้องใช้อาร์เรย์ 3 ชุดคือ อาร์เรย์สำหรับช่องข่าวสาร (INFO) , อาร์เรย์สำหรับพอยน์เตอร์ทางซ้าย (LLINK) และอาร์เรย์สำหรับพอยน์เตอร์ทางขวา (RLINK
                    เมื่อเปรียบเทียบลิงค์ลิสต์คู่กับลิงค์ลิสต์เดี่ยวจะเห็นได้ชัดว่าลิงค์ลิสต์คู่ต้องใช้เนื้อที่มากกว่า เนื่องจากต้องใช้ 2 พอยน์เตอรืสำหรับแต่ละโหนดแน่นอนที่เสียไปนั้นก็เพื่อที่จะได้สิ่งบางอย่างเพิ่มเติม นั่นคือความสะดวกในการนำข่าวสารเข้าหรือออกจากลิงค์ลิสต์ ในกรณีลิงค์ลิสต์คู่เราสามารถนำโหนดใหม่เข้าทาง ด้านหน้า หรือ ด้านหลังโหนดH1 ในลิงค์ลิสต์นั้นได้นอกจากนี้เรายังสามารถคืนโหนดH1 ไปสู่ storage pool โดยตรงได้อีกด้วยอย่าลืมว่าเราไม่สามารถคืนโหนดH1 ไปสู่ storage pool ในกรณีลิงค์ลิสต์เดี่ยว

                    2.1 การนำข่าวสารเข้าสู่ลิงค์สิสต์คู๋สมมติว่าแต่ละโหนดใน storage pool ดังนั้นคำสั่ง ALLOCATE P จะก่อกำเนิดโหนด

                   เราจะสมมติว่ามีลิงค์ลิสต์คู่อย่าแล้ว และจะนำโหนดP ซึ่งเก็บข่าวสาร X เข้าสู่ลิงค์ลิสต์นี้ ที่ตำแหน่งถัดจากโหนดH1 ซึ่งจะเห้นได้ว่ากระบวนการนี้สำเร็จได้โดยการเปลี่ยนค่าพอยน์เตอร์4 ค่าอย่างไรกีดีลำดับการเปลี่ยนค่าพอยน์เตอร์มีความสำคัญมาก ถ้าเราทำตามลำดับ (1),(2),(3),(4) จะไม่สำเร็จ ส่วนรูปที่ 23

 

ลิงค์ลิสต์ (Linked List)

 ลิสต์ (Lists) หรือรายการ ถือเป็นการจัดเก็บข้อมูลชนิดหนึ่งซึ่งข้อมูลเชื่อมต่อกันแบบเชิงเส้น แต่ละข้อมูลมักเรียกว่า อีลิเมนต์ (Element) หรือสมาชิก (Member) โดยแบ่งโดยพื้นฐานได้ 2 แบบคือแบบทั่วไป (General) และแบบจำกัด (Restricted) ซึ่งแนวคิดของลิงค์ลิสต์จะกำหนดให้แต่ละสมาชิกจะประกอบด้วย ข้อมูล (Data) และลิงก์ (Link) โดยข้อมูลอาจประกอบด้วยหลายฟิลด์ก็ได้

การดำเนินงานพื้นฐานของลิสต์ (Basic Operations of List)
1. การแทรก (Insertion)
2. การลบ (Deletion)
3. การปรับปรุง (Updation)
4. การท่องเข้าไปในลิสต์ (Traversal)                    

 

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

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

การเข้าถึงข้อมูลใน Array (อาร์เรย์ 1 มิติ) 
          อาร์เรย์มี 2 แบบ คือ อาร์เรย์ 1 มิติ และอาร์เรย์หลายมิติ
          โครงสร้างข้อมูลอาร์เรย์ 1 มิติ (One-Dimensional Array)
          คือโครงสร้าง ข้อมูลแถวลำดับที่มีการจัดเก็บข้อมูลต่อเนื่องกันไปเป็นตารางแถวเดียว มีดัชนีอ้างอิงเพียง 1 ตัว
          การกำหนดอาร์เรย์ จะต้องกำหนดชื่ออาร์เรย์ พร้อม subscript ซึ่งเป็นตัวกำหนดขอบเขตของอาร์เรย์
          ข้อกำหนดของการกำหนดค่าต่ำสุดและค่าสูงสุดของ subscript คือ
          1. ค่าต่ำสุดต้องมีค่าน้อยกว่าหรือเท่ากับค่าสูงสุดเสมอ
          2. ค่าต่ำสุดเรียกว่าขอบเขตล่าง (lower  bound)
          3. ค่าสูงสุดเรียกว่าขอบเขตบน (upper  bound)
          จากตัวอย่าง A[1:5]
          A เป็นชื่อโครงสร้าง
          1 เป็นขอบเขตล่าง (lower  bound)
          5 เป็นขอบเขตบน (upper  bound)
         ตัวอย่างการประกาศค่า อาร์เรย์ 1 มิติเช่นint a[5], int a[5]={2,4,6,8,10} 
          การหาขนาดจำนวนช่องของอาร์เรย์
          สูตร(u-l)+1โดยที่ u คือ ค่า upper และ l คือ ค่า lower ตัวอย่าง
          ถ้าจะเก็บคะแนนของนักศึกษารหัส 1741-1750 ซึ่งได้คะแนน 50, 60, 70, 60, 55, 71, 62, 59, 41, 70 จะใช้อาร์เรย์กี่ช่องในการจัดเก็บ
          วิธีทำ ค่าสูงสุด (u) = 1750
                  ค่าต่ำสุด (l)  = 1741
          จากสูตรจำนวนช่องตาราง = (u-l)+1
                                           =  (1750 - 1741)+1
                                           = 9+1
                                           = 10
          Array ชุดนี้มีช่องตาราง 10 ช่อง
          การหาตำแหน่งข้อมูลที่ i
          สูตร Loc(A[i]) = L+(i-l)C โดยที่ L เป็น ค่าในตำแหน่งของอาร์เรย์, i เป็น ค่าตำแหน่งที่โจทย์บอกต้องการให้หา, l เป็น ค่า lower และ C เป็น ค่าเนื้อที่ในหน่วยความจำ(byte)  ตัวอย่าง
          กำหนดnum[1932..1984] โดยสมาชิกแต่ละตัวใช้เนื้อที่ในหน่วยความจำ 4 ไบต์ และตำแหน่งแรกของ Array numคือnum[1932] = 200 จงหาที่อยู่ของnum[1980]
          วิธีทำ Loc (num[1980]) = 200 + 4(1980 - 1932)
                                          = 200 + 4(48)
                                          = 200+192
                                          = 392
          ขนาดของ Array num    = 4 * ((1984 - 1932)+1)
                                          = 212 

Initialization
          Initialization คือ การกำหนดค่าเริ่มต้นให้กับอาร์เรย์
          1.การกำหนดค่าให้กับตัวแปรชุดที่มีค่าเป็นตัวเลข
          รูปแบบ data-type array-name[n] = {value1,value2,...,value n};
          ตัวอย่าง      
          intnum[5] = {1,2,3,4,5}; หรือ
          intnum[] = {2,4,6,8,10}; หรือ
          float x[6] = {0,0.05,0,0,0.1,0.25};
          2. การกำหนดค่าให้กับตัวแปรชุด ชนิด Character
          รูปแบบ char array-name[n] = "string";
        

  ตัวอย่าง
          char ch[9] = "SAWASDEE"; หรือ
          char ch[5] = {'a', 'e', 'i', 'o', 'u'};  

โครงสร้างข้อมูลอาร์เรย์ 2 มิติ (Two-Dimensional  Array)
          คือโครงสร้างข้อมูลที่มีการจัดเก็บข้อมูลแบบตารางสองทาง ข้อมูลมีการจัดเรียงกันตามแนวแถว (Row) และแนวหลัก (Column)  โดยการอ้างถึงข้อมูลต้องระบุตำแหน่งแถว และตำแหน่งหลักที่ข้อมูลนั้นอยู่
          รูปแบบ type array-name[n][m]; ซึ่ง n แสดงตำแหน่งแถว และ m แสดงตำแหน่งของหลัก
          ตัวอย่าง
          int a[2][3];
          int a[2][3] = {1,2,3,4,5,6}; หรือ
          int a[2][3] = {{1,2,3},{4,5,6}}; หรือ
          int a[][3] = {{1,2,3},{4,5,6}};
          สูตรการคำนวณหาจำนวนสมาชิกของอาร์เรย์ 2 มิติ
          A [l1..u1,l2..u2] = (u1-l1+1) x (u2-l2+1)เมื่อ
          A  คือ ชื่อโครงสร้างข้อมูลอาร์เรย์
          l1  คือ ค่าขอบเขตต่ำสุด (lower bound)  ของแถว
          u1 คือ ค่าขอบเขตสูงสุด (upper bound) ของแถว
          l2  คือ ค่าขอบเขตต่ำสุด (lower bound)  ของหลัก
          u2 คือ ค่าขอบเขตสูงสุด (upper bound) ของหลัก
          ตัวอย่าง
          จงหาจำนวนสมาชิก ของ Array test[-3:2,-2:1]
          วิธีทำ แยกหาจำนวนช่องของ Array แต่ละมิติ
                  มิติที่ 1 test[-3:2]   =   (2-(-3))+1
                                            =   (2+3)+1
                                            =   6
                  มิติที่ 2 test[-2:1]   =   (1-(-2))+1
                                            =   (1+2)+1
                                            =   4
                  จำนวนสมาชิกของ Array test  =  6x4
                                                          =  24 

Operation ใน Array
          คือ การที่เราสามารถกระทำกับโครงสร้างนั้น ๆ ได้ เช่น การแทรก ลบ การท่องไปในสมาชิกของอาร์เรย์ เป็นต้น มี
          1.การท่องในอาร์เรย์ (Traversal)
          2. การค้นหาข้อมูลที่ต้องการ (Searching)
          3. การแทรกข้อมูลใหม่ (Insertion)
          4. การลบข้อมูล (Deletion)
          5. การเรียงกลับข้อมูล (Reversing) 

ตัวอย่างโปรแกรม
          อาเรย์ 1 มิติ
         #include<stdio.h>
         #include<conio.h>
         void main()
         {
             clrscr();
             int n[5] = {2,4,6,8,10}, i;
             printf ("Element \t Value");
             for (i=0;i<=4;i++)
                printf("%d \t %d \n" ,i,n[i]);
             getch();
         } 

โครงสร้างข้อมูลแบบสแตก(Stack)

สแตก(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จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack การยำข้อมูลบนสุดออกจากสแตก
4. Stack Topเป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกโดยไม่มีการลบข้อมูลออกจากสแตก
5. Empty Stack เป็นการตรวจสอบการวางของสแตกเพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6.Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก

 การประยุกต์ใช้สแตก

การประยุกต์ใช้สแตก จะใช้ในงานด้านปฏิบัตการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้ หลังสุด เช่นการทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทาง คณิตศาสตร์ และรีเคอร์ชั่น (Recursion)

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

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

1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator 3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2

ตัวอย่างนิพจน์คณิตศาสตร์ในรูปแบบต่าง ๆ
นิพจน์ Postfix นิพจน์ Prefix
AB+C- - +ABC
ABC*+DE/- - +A*BC/DE
AB*C+DE/- - +*ABC/DE

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

      ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์

1. อ่านอักขระในนิพจน์ Infix เข้ามาที่ละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัวดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถามความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถามความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4.ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก popออกจากสแตก นำไปเรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5.เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุก ตัวในสแตกนำมาเรียงต่อในนิพจน์
ตัวอย่าง
การแปลงนิพจน์ Infix เป็นนิพจน์ Postfix นิพจน์ A-B/C+D*Eตัวที่อ่านเข้ามา ผลลัพธ์ในสแตก นิพจน์ Postfix
A ว่าง A
- - A
B - AB
/ -/ AB
C -/ ABC
+ + ABC/-
D + ABC/-D
* +* ABC/-D
E +* ABC/-DE
ABC/-DE*+
นิพจน์ A*(B+C-D)/E

โครงสร้างข้อมูลแบบคิว (Queue)

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

            โครงสร้างข้อมูลแบบนี้เป็นโครงสร้างที่ปรากฏอยู่โดยทั่วๆไปโดยเฉพาะอย่างยิ่งในระบบปฏิบัติการคอมพิวเตอร์ในระบบคมนาคม รวมทั้งในระบบการทดลองดาวเทียมด้วย

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

                การนำข้อมูลสู่คิว จะเหมือนกับการยืนต่อแถวคอยอยู่

 

5

4

8

9

1

2

3

6

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

154

254

854

621

854

265

168

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

78

48

54

68

11

99

14

67

89

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 การสร้างคิว (Queue)

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

            ก่อนที่จะทำการสร้างคิวจะต้องทำความเข้าใจถึงโครงสร้างของคิว ซึ่งประกอบไปด้วย ตัวคิว ซึ่งในที่นี้ขอแทนด้วยอาร์เรย์และจะต้องมีตัวชี้อีก 2 ตัว ได้แก่ ตัวชี้ F (Front Pointer) ชี้ไปที่สมาชิกตัวแรก และตัวชี้ R (Rear Pointer)  ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวจะออกทาง F  

 

5

4

8

9

1

2

3

 การทำงานของคิว

การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueueซึ่งมีรูปแบบคือenqueue (queue, newElement) หมายถึง การใส่ข้อมูลnewElementลงไปที่ส่วนเรียร์

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

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

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

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

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

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

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

เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรีซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้

- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนนิพจน์ในเอ็กซ์เพรสชันทรีตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบส่วนตัวดำเนินการจะเก็บในโหนดกิ่งหรือโหนดที่ไม่ใช่โหนดใบเช่น นิพจน์ A + B สามารถแทนในเอ็กซ์เพรสชันทรี

โครงสร้างข้อมูลกราฟ (Graphs)

            โครงสร้างข้อมูลกราฟ (Graphs)เป็นโครงสร้างที่ไม่เป็นแบบรายการเชิงเส้น (Non-linear) ประกอบด้วยเซต V ซึ่งเราเรียกว่า จุดของกราฟ (vertices of G) และเซต E ซึ่งแยกออกมาจากเซต V  เราเรียกว่า ด้านของกราฟ (edges of G)

            หรือกล่าวอีกลักษณะหนึ่งว่า กราฟคือ  เซตของจุด  (points)  และเซตของเส้น (lines) ซึ่งเส้นจะเป็นตัวเชื่อมโยงจากจุดหนึ่งไปยังอีกจุดหนึ่ง โดยเรียกจุดเหล่านี้ว่าโหนดของกราฟ   (nodes of graph)  และเรียกเส้นว่าด้าน (edges)

กำหนดให้   VG   คือ  เซตของโหนดในกราฟ  G

              EG   คือ  เซตของด้านในกราฟG

สามารถเขียนแทนความหมายของกราฟได้ดังนี้

             VG       =        {  a,  b,  c,  d }

             EG       =        { 1, 2, 3, 4, 5, 6, 7, 8 }

                         

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

ประเภทของกราฟแบ่งออกเป็น 2 ประเภท ได้แก่

1. กราฟไม่มีทิศทาง (Undirected Graphs)

2. กราฟมีทิศทาง (Directed Graphs)

กราฟไม่มีทิศทาง (Undirected Graphs) คือ กราฟที่มีด้าน (Edges) ของกราฟจะไม่มีลูกศรแสดงทิศทางความสัมพันธ์ที่เกิดขึ้น (มองความสัมพันธ์ได้ทั้งสองด้าน)

กราฟมีทิศทาง (Directed Graphs)คือ กราฟที่มีด้าน (Edges) ของกราฟมีลูกศรแสดงทิศทางความสัมพันธ์ที่เกิดขึ้น

การแทนโครงสร้างข้อมูลกราฟคือ การแทนความสัมพันธ์ที่เกิดขึ้นจากรูปกราฟด้วยรูปที่สามารถประมวลผลด้วยคอมพิวเตอร์  ซึ่งแบ่งออกเป็น 2 วิธี  ได้แก่

                    1. การแทนด้วย Adjacency Matrix

                    2. การแทนด้วย Node Directory

การแทนด้วย Adjacency Matrix

 

 แหล่งที่มาข้อมูล:

1. http://www.l3nr.org/posts/355077

2. http://www.l3nr.org/u/oleyza#/posts

รูปภาพของ ssspoonsak

เนื่องจากมีข้อมูลบางส่วนหรือทั้งหมดได้ทำการคัดลอกมาแล้วไม่อ้างอิงแหล่งที่มาของข้อมูล

กรุณาอ้างอิงแหล่งที่มาของข้อมูลด้วย มิฉะนั้นทางเว็บ thaigoodview.com จำเป็นต้องลบข้อมูลทั้งหมดออก

ขอขอบคุณ

ครูพูนศักดิ์ สักกทัตติยกุล

ผู้ดูแลเว็บไซต์ไทยกู๊ดวิว

 


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

ช่วยกันนะครับ 
ไทยกู๊ดวิวจะได้อยู่นานๆ ไม่ถูกปิดเสียก่อน
ขอขอบคุณในความร่วมมือครับ

งาน

มหาวิทยาลัยศรีปทุม ผู้ใหญ่ใจดี
 
 

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

ช่วยกันนะครับ 
ไทยกู๊ดวิวจะได้อยู่นานๆ 
ไม่ถูกปิดเสียก่อน

ขอขอบคุณในความร่วมมือครับ

อ่านรายละเอียด

ด่วน...... ขณะนี้
พระราชบัญญัติลิขสิทธิ์ (ฉบับที่ 2) พ.ศ. 2558 
มีผลบังคับใช้แล้ว 
ขอให้นักเรียนและคุณครูที่ใช้งาน
เว็บ thaigoodview ในการส่งการบ้าน
ระมัดระวังการละเมิดลิขสิทธิ์ด้วย
อ่านรายละเอียดที่นี่ครับ

 

สมาชิกที่ออนไลน์

ขณะนี้มี สมาชิก 0 คน และ ผู้เยี่ยมชม 86 คน กำลังออนไลน์