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

รูปภาพของ bvs123456

โครงสร้างข้อมูลแบบลิงค์ลิสต์ (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)


 


 


 


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


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


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


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


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


สแตกประกอบด้วยส่วนสำคัญ ๆ 2 ส่วน คือ


1.             ตัวชี้สแตก หรือ Stack Pointer   ซึ่งเป็นตัวควบคุมการนำสมาชิกเข้า  หรือออกจากสแตก  เป็นตัวใช้บอกว่าสแตกนั้นเต็มหรือยัง


2.             ส่วนสมาชิกของสแตก หรือจะเรียกอีกอย่างว่า Stack Element สมาชิกของสแตกนี้จะเป็นข้อมูลชนิดเดียวกันทั้งหมด


 การสร้างสแตก


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


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


 การดำเนินงาน


ทำงานกับโครงสร้างข้อมูลแบบสแตกได้แก่ การ PUSH และการ POP


การ PUSH


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


ในกรณีที่ PUSH ข้อมูลลงสู่สแตก จนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว จะไม่สามารถทำการ PUSH ข้อมูลลงสแตกได้อีก เนื่องจากตัวชี้สแตกไม่สามารถที่จะขยับไปยังช่องต่อไปได้ จะเกิด Error ที่เรียกว่า  Stack Overflow


 การ  POP


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


การ POP ข้อมูลนี้จะทำการนำข้อมูลในส่วนบนสุดของสแตกออกไปทำงานตามต้องการ แต่การ POP ข้อมูลนี้จะไม่สามารถ POP ข้อมูลออกจากสแตกที่ว่างเปล่าหรือไม่มีข้อมูลได้ ถ้าเราพยายาม POP ข้อมูลออกจากสแตกที่ว่างเปล่า จะเกิด Error ที่เรียกว่า  Stack Underflow


 เปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วยอะเรย์และลิงค์ลิสต์


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


 การประยุกต์ใช้งานของสแตก


สแตกเป็นโครงสร้างที่มีประโยชน์มาก ถูกนำไปประยุกต์ใช้ในหลายๆ ด้าน เช่น


 1.  การจัดการหน่วยความจำ


โดยทั่วไปการจัดการหน่วยความจำจะเป็นดังนี้














Reserved


By


System


Programs


And


procedures


Dynamic


Varible


Heap


Local


Variable


stack


Operating


system


Low Memory


Available space


High Memory


ลองมาดูตัวอย่างของการจัดเก็บค่าของตัวแปรในหน่วยความจำในตัวอย่าง


1 ---->          main () {                                                                                                                                 // Start main ()


int          P, Q, R;                                                     // User defined


2 ---->           void  A (void) {                                                                         // Start function A


int          S;                                          // User defined


3 ---->                           B() ;


7 ---->          }                                                                                                      // End function A


 


3 ---->           void  B (void) {                                                                         // Start function B


struct list {


int           data;


struct list      *link;


} node;


struct list       *D ;


int   X, Y;                                            //User  defined


4 ---->                          new(D);


new(D);


5 ---->                          new (D);


6 ---->                   }                                                                                              // End function B


2 ---->           A;


8 ---->   }                                                                                                              // End main ()


 


 


ภาพของค่าของตัวแปรในหน่วยความจำเมื่อกำลังประมวลผลโปรแกรม ณ จุดต่างๆ เป็น ดังนี้


 


1. เมื่อเริ่มทำงานในส่วน main() เนื้อที่หน่วยความจำในสแตกจะถูกใช้สำหรับตัวแปร P, Q, R
















Reserved


By


System


Programs


And


procedures


 


 


P


Q


R


Operating


system


Low Memory


Top of heap


 


Top of stack


 


                                    โครงสร้างข้อมูลแบบคิว (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


6


0


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


154


254


854


621


854


265


168


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


78


48


54


68


11


99


14


67


89


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


 


                F (Front Pointer)                                                            R (Rear Pointer)


                เมื่อเริ่มต้นสร้างคิว คิวนั้นไม่มีค่าใดๆ ยังว่างเปล่า F และ R จะมีค่าเป็น 0 ทั้งคู่ คือไม่ได้ชี้ไปที่สมาชิกตัวใด การนำข้อมูลเข้าสู่คิวเรียกว่า การ Insertion ส่วนการนำข้อมูลออกจากคิวเรียกว่า การ Deletion


การ Insertion


                เป็นการนำข้อมูลเข้าสู่คิว โดยการที่จะนำข้อมูลเข้าสู่คิวนั้นจะแบ่งออกเป็น 2 กรณี คือ


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


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


                จากการ Insertion ข้อมูลเข้าไปในคิวแล้ว ถ้าหากทำการ Insertion ข้อมูลจนพอยน์เตอร์ R อยู่ที่ช่องสุดท้ายแล้ว จะไม่สามารถทำการ Insertion ข้อมูลลงคิวได้อีก เนื่องจากตัวที่เก็บข้อมูลคิวเต็มทำให้ไม่สามารถที่จะรับข้อมูลอื่นๆ อีกได้ ฉะนั้นจะเกิด Error ขึ้น ซึ่ง Error นี้เรียกว่า Overflow ขึ้น เช่น ถ้าจอง Array ขนาด 3 ช่องชื่อ Q


                1.    เมื่อคิวว่าง (Empty Queue)







0    1          2         3


                                                               








 


 


 


                                                F = 0      R = 0







0    1          2         3


                2.    INSERT (Q , A)


                                                                   








A


 


 


                                         F = 1   R = 1


                3.    INSERT (Q , A)







0    1          2         3


                                                                   








A


B


 


                                  F = 1    R = 2


 







0    1          2         3


                4.    INSERT (Q , C)


                                                                   


โครงสร้างข้อมูลต้นไม้ (Tree)


ความหมาย


โครงสร้างข้อมูลแบบต้นไม้ (Tree) เป็นโครงสร้างที่ไม่เป็นแบบรายการเชิงเส้น (Non-linear) มีลักษณะโครงสร้างข้อมูลเหมือนต้นไม้ตามธรรมชาติ  คือ ลักษณะคล้ายกิ่งก้านของต้นไม้


            ประกอบด้วยจุดยอดของต้นไม้เรียกว่า ราก (Root)  , จุดที่มีการแตกกิ่งก้านสาขาออกไปเรียกว่า โหนด (Node) และกิ่งก้านสาขาที่ต่อระหว่างโหนดว่า ลิงค์ (Link)


 


โครงสร้างข้อมูลต้นไม้ (Tree)


 


 


 


 


ลักษณะของโครงสร้างข้อมูลแบบต้นไม้


 โครงสร้างข้อมูลแบบต้นไม้


แบ่งออกมาได้ 3 แบบ คือ


1. ต้นไม้อิสระ (Free Tree) คือ กราฟอย่างง่าย (Simple Graph) มีทางเดิน    


    เพียงชุดเดียวระหว่างจุดยอดคู่ใด ๆ


2. ต้นไม้ที่มีราก (Rooted Tree) คือ ต้นไม้ที่มีการกำหนดจุดยอดจุดหนึ่งให้


    เป็นราก (Root)


3. ต้นไม้ที่มีลำดับ (Ordered Tree) คือ ต้นไม้ที่มีการจัดลำดับของสาขาแต่ละ


    สาขา


ความสัมพันธ์ของโครงสร้างต้นไม้


1. ราก (Root) เป็นโหนดบนสุด


2. ใต้โหนดรากและในระดับเดียวกันจะใส่จุดยอดซึ่งทางเดินห่างจากราก


    (Root) เป็นระยะทาง 1 หน่วย


3. ใต้จุดยอดเหล่านี้และในระดับเดียวกันจะใส่จุดยอดที่ทางเดินห่างจากราก


     (Root) เป็นระยะทาง 2 หน่วย


4. ทำเช่นนี้เรื่อยไปจนหมดโครงสร้าง


ความสัมพันธ์ของโครงสร้างต้นไม้


1. ระดับ (Level) ของจุดยอด v คือ ระยะทางตามแนวดิ่งของโหนดนั้น (Vn)ว่า


    อยู่ห่างจากโหนดราก (Root) เท่าไร


2. ความสูง (Height) ของโครงสร้างต้นไม้ คือ ระดับสูงสุด (Heightest Level)


    ที่เกิดขึ้น


3. ดีกรีของโหนด (Level Degree) คือ จำนวนของต้นไม้ย่อย ในแต่ละโหนดว่า


    มีจำนวนเท่าไร


ความสัมพันธ์ของโครงสร้างต้นไม้


กำหนดให้โหนดราก (Root) คือ จุดยอด V0 และ x, y, z  เป็นจุดยอดในต้นไม้ และ (V0 , V1 , ….,Vn )  เป็นทางเดินในต้นไม้จะกล่าวว่า


1) Vn-1 เป็น บิดามารดา (Parent) ของ Vn


2) V0,…,Vn-1 เป็น บรรพบุรุษ (Ancestor) ของ Vn


3) Vn เป็น ลูก (Child) ของ Vn-1


4)  ถ้า x เป็นบรรพบุรุษของ y จะได้ว่า y เป็น ผู้มาทีหลัง (Descendant)  x


5) ถ้า x และ y เป็นลูกของ z จะได้ x และ y เป็น พี่น้องกัน (Siblings)


6) ถ้า x ไม่มีลูก x จะเป็น จุดยอดที่สิ้นสุด (Leaf  Node) หรือใบไม้    


7) ถ้า x ไม่ใช่จุดยอดที่สิ้นสุด x จะเป็น จุดยอดภายใน (Internal vertex)


    หรือ กิ่ง


8) กราฟย่อยของ T ประกอบด้วยจุดยอด x และโหนดที่มาทีหลังนับจากบรรพ


     บุรุษของมันทั้งหมด โดยมีโหนด  x เป็นราก และเรียกว่า ต้นไม้ย่อยของ


     ต้นไม้ที่มีราก x


 โครงสร้างต้นไม้ทวิภาค (Binary Tree) คือ ต้นไม้ที่มีโหนดราก (Root) และทุกจุดยอดอาจมีลูก (Child) ทางซ้าย, ลูกทางขวา, ลูกทางซ้ายและลูกทางขวา หรือไม่มีลูกเลย


                โครงสร้างต้นไม้ทวิภาคแบบสมบูรณ์ (Complete Binary Tree) คือ  โครงสร้างต้นไม้ทวิภาคที่ทุกจุดยอดมีลูกทั้งสองด้านหรือไม่มีลูกเลย


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


ความหมาย


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


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


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


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


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


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


VG     =      {  a,  b,  c,  d }


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


 


ในบางครั้งการเชื่อมต่อระหว่างโหนดสองโหนดใด ๆ อาจมีด้านเชื่อม


ต่อได้หลาย ๆ  ด้าน ซึ่งต่างก็ทำให้เกิดการเชื่อมโยงต่อระหว่างโหนดสองโหนด


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


โหนดเดิม ซึ่งจะเรียกด้านที่เกิดขึ้นในลักษณะนี้ว่าลูป  (loops)


 กราฟจะเรียกว่า กราฟอย่างง่าย(Simple Graph) ถ้ามีคุณลักษณะ


ต่อไปนี้


1. กราฟต้องไม่มีลูป (Loops)


2. โหนดแต่ละคู่จะต้องมีด้านไม่เกิน 1 ด้าน


 ประเภทของกราฟ


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


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


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


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


คือ กราฟที่มีด้าน (Edges) ของกราฟจะไม่มีลูกศรแสดงทิศทางความ


สัมพันธ์ที่เกิดขึ้น (มองความสัมพันธ์ได้ทั้งสองด้าน)


 การแทนโครงสร้างข้อมูลกราฟ


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


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


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


การแทนโครงสร้างข้อมูลกราฟด้วย Linked List


การแทนด้วย Linked List จะเก็บข้อมูลเฉพาะโหนดที่มีความสัมพันธ์กัน (โหนดที่ไม่เป็นศูนย์) เท่านั้น ซึ่งทำให้ประหยัดเนื้อที่ได้มากกว่าการแทนกราฟด้วยอาร์เรย์


การแทนกราฟด้วย Linked List  แบ่งออกเป็น  2 รูปแบบ ได้แก่


1. การแทนด้วย Node Directory  ประกอบด้วย  2  ส่วน  คือ


- Node Directory


- Edge Information


2. การแทนกราฟแสดงด้วยวิธี  Multi-List


 กราฟที่มี Weighted Edges


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


 

รูปภาพของ ssspoonsak

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

กรุณาอ้างอิงแหล่งที่มาของข้อมูลให้ชัดเจนด้วย ดูรูปแบบการทำเอกสารอ้างอิงได้ที่

http://www.thaigoodview.com/node/99177 

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

อ่านรายละเอียด http://www.thaigoodview.com/node/159116

ขอขอบคุณ

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

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

 


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

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

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

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

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

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

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

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

 

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

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