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

รูปภาพของ 5504073805021

  



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



โครงสร้างสแตก
                โครงสร้างสแตกข้อมูลที่รู้จักและนำมาใช้งานชนิดหนึ่งก็คือ สแตก (Stack) มีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) รูปแบบหนึ่ง และมีข้อกำหนดให้ชุดปฏิบัติการ สามารถเพิ่มและลบรายการเพียงด้านเดียว ซึ่งเป็นด้านบนสุดของสแตก (Top of Stack)
เรียกว่าตัวชี้สแตก (Stack Pointer) มีรูปแบบเป็น (Top)(S)โดยสแตกมีการกำหนดเป็นรูปแบบดังนี้
  S = [s1 ,S2, … ,ST]
ด้านบนสุดของสแตกจะอยู่ที่ Top (S) =ST และมีจำนวนสมาชิกในสแตกเท่ากับ T
ดังในรูปที่ 4.1















 


ST



S2


S1



                                                        



 



 



 



รูปที่ 4.1 ตัวอย่างลักษณะสแตกที่มีสมาชิกเท่ากับ T มีตัวชี้สแตก Top



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



 



รูปที่ 4.2 ลักษณะที่วางจานหรือถาดที่เป็นแบบเดียวกับสแตก



 



ปัญหาที่ 1  เนื่องจากคอมพิวเตอร์ทำงานในรูปแบบของเลขฐาน 2 แต่ในส่วนของผู้ใช้งานจะเป็นเลขฐาน 10 จึงต้องแปลงค่าจากเลขฐาน 10 ไปเป็นเลขฐาน 2 เช่น เปลี่ยนจาก 26 เป็น 11010
ปัญหาที่ 2  คอมไพเลอร์ (Compiler) จะต้องคำนวณนิพจน์ (Expression) ทางคณิตศาสตร์ที่มีเครี่องหมายวงเล็บเปิดและปิดเข้ามาเกี่ยวข้อง
ปัญหาที่ 3  โปรแกรมเกมเล่นไพ่ (Card Game) จะมีที่วางกองไพ่และการแจกไพ่ได้เฉพาะใบที่อยู่บนสุด
ปัญหาที่ 4  รูปแบบปัญหาการทำงานบางอย่าง  เช่น  การทำงานของ  Switching Box ของเครือข่าย หรือรูปแบบการสลับตู้รถไฟบนราง  ดังในรูปที่ 4.3



 



รูปที่ 4.3 ตัวอย่างการใช้สแตกแก้ปัญหาการสลับตู้รถไฟบนราง



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



การปฏิบัติการของสแตก



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




  1. CreateStack( ) ใช้สร้างสแตกใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่าง ๆ

  2. Push(value,  stack)  ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่  มีอัลกอริทึมการทำงานเป็นดังในตารางที่ 4.1


ตารางที่ 4.1  อัลกอริทึมการเพิ่มค่าใหม่เก็บลงในสแตก







1.  ตรวจสอบสแตกว่าจะมีสมาชิกอยู่เต็มหรือไม่  โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์
2.  ถ้าสแตกไม่เต็ม
            2.1  เพิ่มค่าให้กับ Top โดยการบวก 1
            2.2  ทำการนำค่าที่ได้มาเก็บลงในสแตกในตำแหน่ง Top ไม่เช่นนั้นแจ้งกลับมาว่าสแตกเต็ม
3.  Pop(stack)  ใช้ดึงค่าออกจากสแตกที่ใช้งานอยู่และส่งค่า value กลับมาให้ มีอัลกอริทึมการ   ทำงานเป็นดังในตารางที่ 4.2



 



 



ตารางที่ 4.2  อัลกอริทึมดึงค่าออกจากสแตก








  1. ตรวจสอบว่าสแตกว่างหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดอาร์เรย์

  2. ถ้าสแตกไม่ว่าง

    1. ทำการดึงค่าในตำแหน่ง  Top ออกมาให้

    2. ลดค่าของ Top โดยการลบ 1 ไม่เช่นนั้นแจ้งกลับมาว่าสแตกว่าง

3.  isEmpty(stack)  ใช้ตรวจสอบว่าสแตกที่ใช้งานอยู่ว่างหรือไม่  ถ้าไม่มีค่าเก็บไว้เลยจะส่งค่าจริงกลับให้



                เมื่อนำสแตกมาใช้งานตามลำดับดังในรูป (a) ถึง (g) มีการทำงานโดยใช้ชุดปฏิบัติการ Push และ Pop ดังนี้




  1. เริ่มต้นสร้างสแตก  S ขึ้นมาทำงานจะได้เป็นสแตกว่าง  ไม่มีสมาชิกโดยตัวชึ้สแตก Top ยังไม่มีค่า


 




  1. นำค่า  A  เข้ามาเก็บเป็นตัวแรกโดยใช้  Push(A) สแตก S = [A] ตัวชี้สแตก Top = A


 




  1. นำค่า  B เก็บต่อโดยใช้ Push(B) สแตก S = [A,B] ตัวชี้สแตก Top = B


 



(d)นำค่า C เก็บต่อโดยใช้ Push(C) สแตก S = [A,B,C]ตัวชี้สแตก Top =C



 




  1. ต้องการดึงค่าออกมาโดยใช้ Pop( ) สแตก S = [A,B] ตัวชี้สแตกTop = B


 



(f) นำค่า D, E เก็บต่อโดยใช้ Push(D) และ Push(E) ตามลำดับ สแตก
     S = [A,B,D,E] ตัวชี้สแตก Top = E



(g) ดึงค่าออกมา 3 ค่าโดยใช้ Pop( )  3  ครั้งและเก็บค่า F โดยใช้ Push(F) สแตก S = [A,F] ตัวชี้สแตก Top = F



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



 



ตัวอย่างการใช้สแตก
                จากปัญหาในตอนต้นกล่าวถึงปัญหาการเปลี่ยนเลขฐาน  10  เป็นเลขฐาน  2   เนื่องจากการคำนวณเป็นการหารเลขฐาน  10  เศษที่เหลือจะได้เป็นเลขฐาน  2  เมื่อนำมาแสดงผลจะเป็นตัวเลขจากซ้ายไปขวา  แต่เลขฐาน  2  เป็นตัวเลขจากขวาไปซ้ายจึงเกิดการสลับด้านกัน  จึงนำสแตกมาช่วยแก้ปัญหานี้  ดังในตารางที่ 4.3 คือ โปรแกรม Stack.c
ตารางที่ 4.3 ตัวอย่างโปรแกรม Stack.c



 



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



 



การใช้สแตกแก้ปัญหาการแปลงนิพจน์คณิตศาสตร์
                คอมไพเลอร์จะแปลงคำสั่งจากภาษาระดับสูง  (High-level  Language)  ไปเป็นภาษาเครื่อง (Machine Language) ส่วนหนึ่งที่ต้องแปลงคือนิพจน์คณิตศาสตร์ เช่น X = A * B + C ซึ่งมีลักษณะที่เรียกว่า  Infix  Notation  มีเครื่องหมายคำนวณอยู่ระหว่างโอเปอแร้น (Operand) โดยแปลงไปเป็นนิพจน์แบบ Postfix  Notation มีเครื่องหมายคำนวณนำหน้าโอเปอแร้น แต่เนื่องจากนิพจน์แบบ Infix มีการนำเครื่องหมายวงเล็บเข้ามาใช้ทำให้ทิศทางการคำนวณเปลี่ยนไป   ดังในตารางที่ 4.4 เป็นตัวอย่างของการคำนวณแบบเดียวกัน



 



ตารางที่ 4.4  ลักษณะนิพจน์แบบ Infix, Postfix, และ Prefix Notation













Infix

Postfix


Prefix


A+(B*C)
  (A+B)*C
A+B-C
   (A+B)*(C-D)
    (A+B)*C-(D-E) ) $ (F+G)


ABC*+
AB+C*
AB+C-
AB+CD-*
AB+C*DE—FG+$


+A*BC
*+ABC
-+ABC
*+AB-CD
$-*+ABC-DE+FG



การแปลงนิพจน์แบบ Infix เป็นแบบ  Postfix
          เมื่อพิจารณาการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix เป็นขั้นตอนการแปลงโดยเริ่มต้นจากสแกนนิพจน์ Infix ทีละตัว  หากพบวงเล็บก็จะทำส่วนที่อยู่ในวงเล็บให้เสร็จก่อนเป็นนิพจน์ย่อย (Subexpression) ซึ่งจะได้เป็นอัลกอริทึมดังในตารางที่ 4.5



ตารางที่ 4.5  อัลกอริทึมการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix








  1. สร้างสแตกที่ว่างเปล่ายังไม่มีการเก็บค่า

  2. ถ้าค่าในนิพจน์ Infix ยังไม่หมด หรือเกิดข้อผิดพลาด ให้ทำดังนี้



    1. รับค่า  (Token) ตัวถัดไปในนิพจน์  Infix (ประกอบด้วย ค่าคงที่ ตัวแปร เครื่องหมายคำนวณ วงเล็บเปิดและปิด

    2. ค่าที่รับเข้ามา ถ้าเป็น

b.1  โอเปอแร้น (ค่าคงที่,ตัวแปร)                                  นำไปแสดงทางจอภาพ
b.2  วงเล็บเปิด                                                               ให้นำใส่ลงในสแตก (Push)
b.3  วงเล็บปิด                                                                 ดึงค่าออกจากสแตก (Pop) และนำไปแสดงทาง                      จอภาพ  ทำจนกว่าจะพบวงเล็บเปิด
b.4  เครื่องหมายคำนวณ                                                 ถ้าสแตกว่าง  หรือค่าที่รับมามี Precedence สูงกว่าค่าบนสแตกให้นำใส่ลงในสแตก (Push) ถ้าหากค่าที่รับมามี Precedence น้อยกว่าค่าบนสแตกให้ดึงค่าออกจากสแตก (Pop)
            3.  เมื่อทำจนค่าในนิพจน์ Infix หมด ให้ดึงค่าออกจากสแตก (Pop) แสดงทางจอภาพตามลำดับ จนกว่าสแตกว่าง



                จากอัลกอริทึมดังกล่าวเมื่อนำมาใช้กับตัวอย่างนิพจน์ 7*8-(2+3) จะได้เป็นลำดับขั้นตอนดังในรูปที่ 4.4 หรือเขียนเป็นแบบตารางได้ดังในตารางที่ 4.6



 



 



 



ตารางที่ 4.6 การแปลงนิพจน์ 7*8-(2+3) เป็นนิพจน์ Postfix













นิพจน์ Infix

สแตก


นิพจน์ Postfix


7*8-(2+3)
*8-(2+3)
8-(2+3)
-(2+3)
(2+3)
2+3)
+3)
3)
)


 


*


-
- (



  1. ( +

 


-


7


7 8
7 8 *
 
7 8 *2


7 8 *2 3
/ 8 *2 3 +
7 8 * 2 3 + -



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



ตารางที่ 4.7  อัลกอริทึมการหาค่าคำตอบจากนิพจน์ Postfix








  1. สร้างสแตกที่ว่างเปล่ายังไม่มีการเก็บค่า

  2. ทำงานต่อไปนี้ซ้ำจนกว่าถึงจุดสิ้นสุดของนิพจน์

    1. รับค่า (Token) ตัวถัดไปในนิพจน์ RPN (ประกอยด้วย  ค่าคงที่  ตัวแปร  เครื่องหมายคำนวณ)

    2. ค่าที่รับเข้ามา  ถ้าเป็นโอเปอแร้น ให้นำใส่ลงในสแตก (Push) แต่ถ้าเป็นเครื่องหมายคำนวณให้ทำดังนี้

b.1  ดึงค่าออกจากสแตก (Pop) สองค่า ถ้าไม่ครบให้แจ้งเกิดข้อผิดพลาด
b.2  นำเครื่องหมายคำนวณทำการประมวลผลกับค่าทั้งสอง
b.3  นำผลลัพธ์ที่ได้ใส่กลับลงในสแตก (Push)
     3.  เมื่อถึงจุดสิ้นสุดของนิพจน์ ค่าที่เป็นคำตอบจะอยู่บนสแตก ซึ่งมีเพียงค่าเดียวเท่านั้น



                จากอัลกอริทึมดังกล่างเมื่อนำมาใช้กับตัวอย่างนิพจน์ 2 4 *9 5 + -จะเป็นตามลำดับขั้นตอนดังในรูปที่ 4.5 หรือเขียนเป็ฯแบบตารางได้ดังในตารางที่ 4.8



 



 



ตารางที่ 4.8 การหาค่าคำตอบจากนิพจน์













นิพจน์ Postfix

ค่าที่ได้


สแตก


2 4 * 9 5 + -
4 + 9 5 + -
* 9 5 + -
9 5 + -
5 + -
+ -
-


 


2 * 4 = 8


 


9 + 5 = 14
8 – 14 = -6


2
2 4
8
8 9
8 9 5
8 14
-6
-6





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



วัตถุประสงค์เชิงพฤติกรรม (Behavioral Objectives)
หลังจากศึกษาจบบทเรียนนี้แล้ว นักศึกษาจะมีความสามารถดังนี้
(After studying this chapter, you will be able to)




  1. ศึกษาข้อมูลลิงค์ลิสต์

  2. แสดงตัวอย่างการปฏิบัติการพื้นฐานของลิงค์ลิสต์

  3. แสดงตัวอย่างลิงค์ลิสต์ทาเดียว

  4. แสดงตัวอย่างลิงค์ลิสต์วงกลม

  5. ปฏิบัติการลิงค์ลิสต์สองทาง

  6. ปฏิบัติการลิงค์ลิสต์หลายทาง

  7. จัดบอร์ดเชิงปฏิบัติการ “โครงสร้างข้อมูลลิงค์ลิสต์”

  8. สนทนาเชิงปฏิบัติการ “ลิงค์ลิสต์วงกลม”

  9. อธิบายคำศัพท์ได้ 12 คำ


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



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


 


การปฏิบัติการพื้นฐานของลิงค์ลิสต์
                สิ่งสำคัญอย่างหนึ่งในการใช้โครงสร้างข้อมูลลิงค์ลิสต์ คือ ตัวแปรพอยน์เตอร์ (Pointer Variable) ซึ่งเก็บค่าเป็นตำแหน่งแอดเดรสในหน่วยความจำ (Memory Address) ในการปฏิบัติการกับลิ้งค์ลิสต์และให้มีความถูกต้องจะใช้ตัวแปรพอยน์เตอร์ในการจัดการเรื่องต่อไปนี้
1.ใช้ทดสอบกับค่า NULL
2.ใช้ทดสอบว่ามีค่าเท่ากับตัวแปรพอยน์เตอร์อื่น
3.กำหนดให้มีค่าเป็น NULL
4.กำหนดให้ชี้ไปยังโหนด
                ชุดปฏิบัติการของลิ้งค์ลิสต์ที่ทกวานร่วมกับตัวแปรพอยน์เตอร์ มีดังนี้
1.Node(P)  ส่งโหนดที่ถูกชี้ด้วยต้วแปรพอยน์เตอร์ P กลับมาให้
2.INFO(P) ส่งค่าในส่วนเก็บข้อมูลของโหนดที่ถูกชี้ด้วยตัวแปรพอยน์เตอร์ P กลับมาให้
3.Next(P)  ส่งพอยน์เตอร์ในส่วนการเชื่อมต่อขยองโหนดที่ถูกชี้ด้วยตัวแปรพอยน์เตอร์ P กลับมาให้
 
การแทรกโหนดไว้ในลิ้งค์ลิสต์
                อัลกอลิทึมในการแทรกโหนดใหม่เข้าไปไว้ในลิ้งค์ลิสต์ดังในตารางที่6.1

ตารางที่ 6.1 อัลกอริทึมการแทรกโหนดใหม่ลงในลิ้งค์ลิสสต์



ตัวอย่างการแทรกโหนดใหม่ไว้ในลิ้งค์ลิสต์ โดยเริ่มต้นสร้างเป็นโหนด I ในหน่วยความจำกำหนดส่วนเก็บข้อมูลมีค่า L ส่วนการเชื่อมต่อมี่ค่าเป็น NULL ซึ่งมีตัวแปรพอยน์เตอร์ New  ชี้อยู่ ดังในรูปที่ 6.2 และมีลิงค์ลิสต์ที่ต้องการแทรกโหนดใหม่เข้ามาระหว่างโหนด 2 เป็นโหนดก่อนหน้า (Predecessor) และโหนด 3 เป็นโหนดถัดไป (Successor) ดังนั้นจึงกำหนดให้ตัวแปรพอยน์เตอร์ P ชี้ไปยังโหนด 2 และขั้นตอนในการแทรกประกอบด้วย




  1. Next(New) =Next (P) กำหนดให้ตัวชี้ของโหนด I เปลี่ยนไปชี้ยังโหนด 3 ซึ่งเป็นส่วนหลังของการแทรกโหนดใหม่ ในรูปที่ 6.3



  1. Next(P) =New กำหนดให้ตัวชี้ของโหนด 2 ที่มีตัวแปรพอยน์เตอร์ P ชี้อยู่เปลี่ยนไปชี้ยังโหนด I ที่มีตัวแปรพอยน์เตอร์ New ชี้อยู่ ในรูปที่ 6.4


กล่าวจะมีเพียง 2 โหนดที่เดี่ยวขอ้งคือโหนดใหม่ I และโหนดที่ตัวแปรพอยน์เตอร์ P ชี้อยู่ ส่วนโหนดอื่นๆ ไม่ถูกเรียกใช้งานเรือเปลี่ยนแปลง


การลบโหนดออกจากลิ้งค์ลิสต์
            อัลกอริทึมในการลบโหนดออกจากลิ้งค์ลิสต์ดังในตารางที่ 6.2


ตารางที่ 6.2 อัลกอริทึมการลบโหนดออกจากลิ้งค์ลิสต์



ลิ้งค์ลิสต์ทางเดียว
   โดยทั่งไปลิ้งค์ลิสต์จะมีโหนดที่มีส่วนการเชื่อมต่อชี้ไปยังโหนดถัดไปเพียงทางเดียว (Unidirectional)         ดังที่ผ่านมา เรียกว่าลิ้งค์ลิสต์ทางเดียว (Singly Linked List ) ซึ่งนอกจากจะมีชุดปฏิบัติการแทรกและลบโหนดแล้วยังมีอัลกอรึทึมในการจัดการลิงค์แบบอื่น ๆ ดังนี้
                1.การค้นหาแต่ละโหนด เป็นการเริ่มต้นที่โหนดแรกจากนั้นหาไปทีละโหนดตามลำดับที่เชื่อมต่อกันจนกว่าจะพบโหนดในลิงค์ลิสต์ดังในตารางที่ 6.3


ตารางที่ 6.3 อัลกอริทึมการวิ่งไปยังแต่ละโหนดในลิ้งค์ลิสต์



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



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



4.การสลับด้านของรายการในลิ้งค์ลิสต์ เป็นการสร้างลิงค์ลิสต์ใหม่ให้รายการสลับด้านกับลิ้งค์ลิสต์ตัวเก่า โดยให้โหนดสุดท้ายเปลี่ยนป็นโหนดแรก และให้โหนดแรกกลายเป็นโหนดสุดท้าย


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



ลิ้งค์ลิสต์สองทาง
                ในบางครั้งการทำงานกับลิงค์ลิสต์อาจต้องการวิ่งไปยังโหนดต่าง ๆ ในลิงค์ลิสต์โดยการถอยกลับไปยังโหนดก่อนหน้าหรือลบแต่ละโหนด เพื่อห้เกิดประสิทธิภาพจึงนำลิงค์ลิสต์สองทาง (Doubly Linked List) มาใช้แทนลิงค์ลิสต์ทางเดียว ดังในรูปที่ 6.15 ซึ่งแต่ละโหนดประกอบด้วย 3 ส่วน คือ
                1.ส่วนเก็บข้อมูล (Info) ใช้เก็บข้อมูลข่าวสารที่มีโครงสร้างข้อมูลเบื้องต้นหรือเรียบง่าย
                2.ส่วนการเชื่อมต่อถัดไป (Next) เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างไปยังโหนดถัดไปในหน่วยความจำ
                3.ส่วนการเชื่อมต่อก่อนหน้า เป็นตัวชี้หรือพอยน์เตอร์เก็บค่าแอดเดรสใช้อ้างกลับไปยังโหนดก่อนหน้าในหน่วยความจำ



ลิ้งค์ลิสต์หลายทาง
                มีอยู่หลายกรณีที่นำลิงค์ลิสต์มาใช้งานตามความเหมาะสมซึ่งแต่ละโหนดจะถูกกำหนดให้ส่วนการเชื่อมต่อมีมากกว่าสองทางเรียกว่าลิงค์ลิสต์หลายทาง (Multi-linked List) อย่างเช่นในรูปที่ 6.25 ที่แต่ละโหนดในลิงค์ลิสต์จะมีตัวชี้สามทางโดยมีพื้นฐานเป็นลิงค์ลิสต์สองทางซึ่งมีส่วนเก็บข้อมูลคือ NameLength เก็บค่าความยาวของสตริง กับส่วนเชื่อมต่อที่เป็นตัวชี้ Right และ Left และส่วนที่เชื่อมต่อที่สาม คือ ตัวชี้ NamePtr ใช้ชี้ไปยังข้อมูลจริงอีกทีซึ่งมีโครงสร้างข้อมูลสตริงเก็บไว้ในหน่วยความจำที่ขอมาแทนการเก็บไว้ภายในโหนด



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


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









 


 


 


 


Front                                                                                                 Rear
รูปที่ 5.1 ตัวอย่างลักษณะของคิวที่มีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ส่วนท้ายอยู่ด้านขวา


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



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



คิวลำดับความสำคัญ
                คิวอาจมีการจัดลำดับความสำคัญของสมาชิกจึงมีการสร้างเป็นคิวลำดับความสำคัญ (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



#include <stdio.h>


#include <stdlib.h>


#include <conio.h>


#define TRUE 1


#define FALSE 0


struct queue {


            int Priority[50];


            char Item[50];


            int maxSize;


            int front;


            int rear;


};


typedef struct queue Queue;


typedef Queue* priorityQueues;


priorityQueues createPriorityQueue(){


            priorityQueues newQueue = malloc(sizeof(Queue));


            newQueue->maxSize = 50;


            newQueue->front = 0;


            newQueue->rear = -1;


            return newQueue;


}


int isEmpty(priorityQueue q){


            if (q->rear < q->front)


                        return TRUE;


            return FALSE;


}


void Insert(char val,int pr,priorityQueues q){


            int i;


            if (q->rear+1 < q->maxSize)


                        if (isEmpty(q)){


                                    q->front = 0;


                                    q->rear = 0;


                                    q->Priority[q->rear] = pr;


                                    q->Item[q->rear] = val;


                        }


                        else{


                                    q->rear++;


                                    for (i=q->rear; (i>q->front)&&(q->Priority[i-1]<pr);i--){


                                                q->Item[i]=q->Item[i-1];


                                                q->Priority[i] = q->Priority[i-1];


                                    }


                                    q->Item[i] = val;


                                    q->Priority[i] = pr;


                        }


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


          โครงสร้างข้อมูลในบทต่าง  ๆ  ที่ดังกล่าวผ่านมาเป็นโครงสร้างเชิงเส้น  (Linear  Data  Structure)  แต่ละสมาชิกจะมีสมาชิกตัวถัดไปเพียงตัวเดียว  สำหรับในบทนี้จะกล่าวถึงโครงสร้างข้อมูลไม่เป็นเชิงเส้น  (Nonlinear  Data  Structure)  ซึ่งแต่ละสมาชิกสามารถมีสมาชิกตัวถัดไปได้หลายตัว  โดยมีแนวความคิดของโครงสร้างแตกสาขา  (Branching  Structure)  และเป็นที่รู้จักคือ  โครงสร้างข้อมูลทรี  (Tree)  ซึ่งกล่าวถึงในบทนี้กับโครงสร้างข้อมูลกราฟ  (Graph)  จะกล่าวถึงในบทหน้าถัดไป
   ทรีทั่วไป
                จากลักษณะของทรีทั่วไป  (General  Tree)  มีการกำหนดเป็นระดับซึ่งมีตัวแรก  คือรูททรี  (Rooted  Tree)    ซึ่งมีเพียงโหนกเดียวทำหน้าที่เป็นรูท  (Root)  และมีความแตกต่างจากโหนดอื่น   ๆ  รูทของทรี  T  จะกำหนดเป็น  Root(T)  โดยทรี  T  เป็นเซตจำนวนที่แน่นอน  (Finite  Set)  ตั้งแต่  0  หรือมากกว่าของโหนด(V1,V2,….,Vn)  ดังนั้น



  1. จะมีเพียงโหนอเดียว(V1)  ที่ออกแบบเป็นพิเศษ  เรียกว่า  Root(T)

  2. โหนดที่เหลือ  (V2,….,Vn)  จะถูกแบ่งออกเป็นส่วน  ๆ  เท่ากับ  m≥ 0  ที่ต่อกันเป็นเซตชื่อ  T1, T2,…..,Tmจะได้ว่าแต่ละ  Ti  คือ  ทรีและเป็นทรีย่อย

  3. หากทรีใด  ๆ  ไม่มีโหนดเลยเรียกว่านัลทรี  (Null  Tree)

 


รูปที่9.1 ตัวอย่างทรีทั่วไป


                จากรูปที่  9.1  เป็นตัวอย่างทรีที่แสดงแต่ละโหนด  โดยใช้ตัวอักษรอยู่ภายในวงกลมและมีรูทของทรี  Root(T)  = A  ทรีย่อยของรูท A ประกอบด้วยรูท B,C,D  ซึ่งจะได้  B  เป็นรูทของทรีที่มีหนึ่งทรีย่อยของรูท  E  ที่ไม่มีทรีย่อย  ทรีที่มีรูท  C  จะมีสองทรีย่อยคือที่รูท  F  และรูท  G  ตามลำดับ
                บางครั้งอาจมีการกำหนดลักษณะให้กับเอจ  (Edge)  ของทรีมีทิศทาง  โดยเอจจะเริ่มจากรูทโหนดไปยังรูทของทรีย่อย  ดังในรูปที่  9.2  เป็นทรีคว่ำในลักษณะของโครงสร้างทรีที่นิยมใช้กันโดยรูทอยู่ด้านบนสุด  (Top)  ดังที่กล่าวมาโหนดที่ออกแบบเป็นพิเศษ  คือ  รูท  มีความแตกต่างจากโหนดอื่น  ๆ  ด้วยคุณสมบัติที่ว่า
                In-degree(v) = 0 for v = Root(T)


 


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


 


การวิ่งแบบพรี-ออเดอร์ (Pre-order)
            มีลักษณะการวิ่งในแนวลึกก่อน (Depth-first Order) มีอัลกิริทึมการทำงานในตารางที่  9.1
           
ตารางที่ 9.1 อัลกอริทึมการวิ่งแบบพรี-ออเดอร์



ตัวอย่างการวิ่งแบบพรี-ออเดอร์ดังในรูปที่ 9.13 (a)และการวิ่งผ่านโหนดตามลำดับได้เป็น A,B,D,E,C,F


การวิ่งแบบอิน-ออเดอร์ (In-Order)
            มีการวิ่งลักษณะแบบสมดุล (Symmetric Order) มีอัลกิริทึมการทำงานดังในตารางที่ 9.2


ตารางที่ 9.2 อัลกิริทึมการวิ่งแบบอิน-ออเดอร์


 


การวิ่งแบบโพสต์-ออเดอร์(Post-Oder)
                มีอัลกิริทึมการทำงานดังในตารางที่ 9.3


ตารางที่ 9.3 อัลกิริทึมการวิ่งแบบโพสต์-ออเดอร์



การลบโหนดออกจากไบนารี่ทรี
          การปฏิบัติการลบโหนดออกจากไบนารี่ทรีจะมีความซับซ้อนกว่าการแทรก เนื่องจากต้องมีการแก้ไขโครงสร้างไบนารี่ทรีให้ถูกต้องโดยการย้ายทรีย่อยขึ้นมาแทนโหนดที่ถูกลบไป ซึ่งการลบโหนจะพิจารณาได้เป็น 3 กรณี คือ
                1.เมื่อโหนดที่ต้องการลบเป็นโหนดปลาย  การลบจะไม่ยุ่งยาก เพียงแต่เปลี่ยนตัวชี้ของโหนดพ่อให้มีค่าเป็น Null ดังในรูปที่ 9.18 (a) ต้องการลบโหนดปลาย D  หลังจากค้นหาโหนดที่ต้องการลบ ก็จะกำหนดตัวชี้ด้านขวาของโหนด C ซึ่งเป็นโหนดพ่อให้มีค่าเป็น Null แทน โหนดปลาย D ก็ถุกปล่อยทิ้งไปได้เป็นรูป (b)  ซึ่งตัวชี้ที่ถูกเปลี่ยนเป็น Null นี้จะขึ้นกับโหนดลูกที่จะลบเป็นด้านซ้ายหรือด้านขวา




.เมื่อโหนดที่ต้องการลบมีดหนดลูกหนึ่งโหนด    การลบจะไม่ยุ่งยากเช่นกันเพียงเปลี่ยนตัวชี้ของโหนดพ่อให้ชี้ไปยังโหนดลูกของโหนดที่ต้องการลบแทน ดังในรูปที่ 9.19 (a) ต้องการลบโหนด E หลังจากต้นหาพบโหนดที่ต้องการบลบ ก็จะกำหนดตัวชี้ด้านขวาของโหนด A  ซึ่งเป็นโหนดพ่อชี้ไปยังโหนด C  ที่เป็นโหนดลูกแทน ส่วนโหนด E ก็ถูกปล่อยทิ้งไปเป็นรูป (b)




3. เมื่อโหนดที่ต้องการลบมีโหนดลูกสองโหนด  การลบโหนดจะกระทำได้สองแบบ คือ
                3.1 นำค่าที่มากที่สึดในทรีย่อยด้านซ้าย (Inorder Predecessor) จากโหนดพรีดีเซสเซอร์ (Predecessor Node) มาแทนค่าในโหนดที่ต้องการลบ และโหนดพรีดีเซสเซอร์
                3.2 นำค่าที่น้อยที่สุดในทรีย่อยด้านขวา (Inorder Successor) จากโหนดซัคเซสเซอร์ (Successor Node)  มาแทนค่าในโหนดลูกสองโหนดแบบที่สองดังในรูปที่ 9.20 (a) ที่ต้องการลบ J หลังจากค้นพบโหนดที่ต้องการลบ จากนั้นทำการหาค่าที่น้อยที่สุดในทรีย่อยด้านขวาโดยการวิ่งลงมาตามเส้นทางจากโหนดลูกด้านขวาได้เป็นรูป (b) ซึ่งพบที่โหนดซัคเซคเซอร์ K และนำค่า K ไปเก็บไว้แทนค่า J ได้เป็นรูป (c) หลังจากนั้นทำการลบโหนดซัคเซสเซอร์ K ออกไปโดยให้ฌหนด M ซึ่งเป็นโหนดพ่อชี้ไปยัวโหนด C ที่เป็นโหนดลูกแทน


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

       กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
       กราฟมีลักษณะเป็นเซ็ตของจุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้าที่เชื่อมต่อจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟและเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะเรียกว่าอาร์ค (Arc) และโหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG  เช่นในรูปที่ 10.1 VG ={a,b,c,d} และ EG = {1,2,3,4,5,6,7,8} จำนวนสมาชิกที่มีใน VG  เรียกว่าออเดอร์ (Order) ของกราฟ ถ้าออเดอร์เท่ากับ 0 คือ กราฟไม่มีสมาชิกเรียกว่านัลกราฟ (Null Graph)



รูปที่ 10.1 ตัวอย่างกราฟที่มีจำนวนสมาชิกออเดอร์เท่ากับ 4


       เอาของแต่ละโหนดจะพิจารณาจากการเชื่อมต่อกัน เช่น เอจ 4 เชื่อมโหนด c กับ d และกำหนดเป็น Path (c,d) โดยตำแหน่งของสมาชิกไม่มีความสำคัญ ดังนั้น กราฟในรูปที่ 10.1 จึงเท่ากับกราฟในรูปที่ 10.2 ต่อไปนี้



เส้นทาง
       เส้นทางในกราฟ (Path) เป็นการจัดลำดับของเอจที่มีตั้งแต่หนึ่งหรือมากกว่าทำการเชื่อมต่อระหว่างสองโหนด ซึ่งกำหนดเป็น P(Vi,Vj) คือ เส้นทางการเชื่อมระหว่างโหนด Vi กับ Vj และถ้า P(Vi,Vj) มีในกราฟก็จะต้องอยู่ใน EG  ดังนั้น ลำดับของเอจจะอยู่ในรูปแบบต่อไปนี้
                               P(Vi,Vj) = (Vi,X1) (X1,X2) . . . (Xn-1,Xn) (Xn,Vj)
       และจะได้ความยาวของเส้นทางเป็นจำนวนเอจที่ประกอบรวมกัน จากกราฟเรียบง่ายในรูปที่ 10.3 จะได้เส้นทางระหว่างโหนด b กับ d ดังนี้
เส้นทาง 1 P(b,d) = (b,c)(c,d)                                   ความยาวเท่ากับ 2
เส้นทาง 2 P(b,d) = (b,c)(c,b)(b,c)(c,d)                    ความยาวเท่ากับ 4
เส้นทาง 3 P(b,d) = (b,d)                                          ความยาวเท่ากับ 1
เส้นทาง 4 P(b,d) = (b,c)(c,b)(b,d)                           ความยาวเท่ากับ 3
       โดยทั่วไปเส้นทางที่ต้องการและสนใจเลือกใช้คือ เส้นทางที่วิ่งผ่านโหนดเพียงครั้งเดียวเท่านั้น ก็จะได้เฉพาะเส้นทาง 1 กับ 3 ส่วนเส้นทาง 2 มีการวิ่งผ่านโหนด b และ c สองครั้งและเส้นทาง 4 วิ่งผ่านโหนด b สองครั้ง นอกจากนี้ยังสนใจเฉพาะเอจที่ถูกวิ่งผ่านเพียงครั้งเดียวเช่นกัน เนื่องจากช่วยให้อัลกอริทึมไม้ต้องล่าช้าที่ต้องกลับไปทำงานในเส้นทางเดิม
ไซเคิล
       เส้นทางที่เป็นไซเคิล (Cycle) หรือการวนกลับจะมีลักษณะที่เป็นไปตามเงื่อนไขต่อไปนี้



  1. จะต้องไม่เอจมากกว่าหนึ่งอยู่ในลำดับของเอจในเส้นทางนั้น

  2. โหนดเริ่มต้นของเส้นทางจะต้องเป็นโหนดสุดท้ายของเส้นทางนั้นด้วย คือ P(V,V)

       เส้นทางที่เป็นไซเคิลจะต้องกลับมายังจุดที่เริ่มต้นเสมอ จากกราฟในรูปที่ 10.2 จะมีเส้นทางที่เป็นไซเคิล ดังนี้
เส้นทาง 1 P(a,a) = (a,a)
เส้นทาง 2 P(b,b) = (b,c)(c,b)
เส้นทาง 3 P(b,b) = (b,c)(c,d)(d,b)
เส้นทาง 4 P(d,d) = (d,b)(b,c)(c,d)
เส้นทาง 5 P(d,d) = (d,b)(b,d)
เมื่อใดที่กราฟไม่มีเส้นทางที่เป็นไซเคิลเรียกว่าอะไซคลิก (Acyclic) ดังรูปที่ 10.5 ซึ่งเป็นกราฟอะไซคลิกรูป (a) และรูป (b)




กราฟทิศทาง
       ลักษณะเฉพาะที่เพิ่มเข้ามาในโครงสร้างข้อมูลกราฟทั่วไปได้เป็นกราฟทิศทาง
(Directed Graph) ซึ่งใช้หัวลูกศรเป็นตัวกำหนดทิศทางให้แต่ละเอจในกราฟ


กราฟทิศทางจะมีดีกรีเข้า (In-Degree) เป็นจำนวนเอจที่ชี้เข้ามาสิ้นสุดที่โหนดและมีดีกรีออก (Out-Degree) เป็นจำนวนเอจที่ชี้ออกจากโหนด ดีกรีของโหนดใดโหนดหนึ่ง คือ ผลรวมของดีกรีเข้ากับดีกรีออก จากรูปที่ 10.6 จะได้ดีกรีของแต่ละโหนดดังนี้


 


In-Degree (a) = 1    Out-Degree (a) = 2    Degree (a) = 3
In-Degree (b) = 4    Out-Degree (b) = 2    Degree (b) = 6
In-Degree (c) = 1    Out-Degree (c) = 2    Degree (c) = 3
In-Degree (d) = 2    Out-Degree (d) = 2    Degree (d) = 4
การสร้างกราฟใช้งาน
       โดยปกติภาษาเขียนโปรแกรมมีการสร้างโครงสร้างข้อมูลให้ใช้งานได้ทันที (Build-in Type) แต่ไม่มีกราฟรวมอยู่ด้วย ดังนั้น ผู้เขียนโปรแกรมที่ต้องการสร้างกราฟขึ้นมาใช้งานจะมีการนำโครงสร้างข้อมูลอื่นมาใช้เป็นกราฟ โดยมีอยู่ 3 แนวทางที่นำมาใช้ คือ



  1. ใช้แมตทริกติดกัน (Adjacency Matrix)  หรืออาร์เรย์สองมิติกำหนดเป็นกราฟ

  2. ใช้ลิสต์แบบไดเร็กทอรี่โหนด (Node Directory) กำหนดเป็นกราฟ

  3. ใช้มัลติลิสต์ (Multi-List) กำหนดเป็นกราฟ

 กราฟแบบแมตทริกติดกัน
       ให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG โดยกราฟมีออเดอร์เท่ากับ N ซึ่ง
 N  >= 1 แนวทางหนึ่งในการกำหนดเป็นกราฟโดยใช้แมตทริกติดกัน (Adjacency  Matrix) เป็นอาร์เรย์ N-ต่อ-N เมื่อให้เป็นอาร์เรย์ A จะได้ว่า


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


 


     ดังนั้น ในแมตทริกติดกันแทนที่จะใช้ค่า 1 กับ 0 หรือบิตแมตทริก (Bit Matrix) เหมือนที่ผ่านมา ก็เปลี่ยนมาใช้เป็นเอจมีน้ำหนักแทนได้เป็นรูปที่ 10.10 และแต่ละโหนดหรือเมืองจะใช้หมายเลขแทน


1 = ABQ 2 = CVG 3 = DFW 4 = DNV 5 = ELP 6 = HST 7 = KNC 8 = LAX
9 = NSH 10 = NOR 11 = ORD 12 = PHX 13 = SEA 14 = SFO 15 = SLC 16 = SPK
รูปที่ 10.10 แมตทริกติดกันที่ใช้แทนกราฟในรูปที่ 10.9
       เอจมีน้ำหนักจะถูกนำมาใช้งานบ่อย เช่น แอปพลิเคชั่นการขนส่ง (Transportation Application) ซึ่งน้ำหนักของเอจ หมายถึง ระยะทาง (Distance) ดังที่ผ่านมา แอปพลิเคชั่นการไหล (Flow Application) ซึ่งน้ำหนัก หมายถึง ปริมาณความจุ (Capacity) โดยให้โหนดของกราฟ คือ แกลลอน (Gallon) ที่มีท่อส่งในปริมาณความจุต่อวินาทีระหว่างโหนด หรือในระบบสื่อสารข้อมูลที่มีปริมาณการส่งเป็นบิตต่อวินาทีระหว่างสถานี หรือในระบบเครือข่าย (Network) ที่ให้น้ำหนัก หมายถึง เวลาที่ต้องใช้ในการทำงานกิจกรรมคือเอจให้เสร็จสิ้น แต่ละโหนดจะเป็นเหตุการณ์ (Event) ให้ทำกิจกรรม เมื่อเสร็จสิ้นลงก็ไปยังโหนดถัดไป ลักษณะดังกล่าวนำมาใช้กับระบบการบริหารจัดการโครงการ (Project Management System)


กราฟแบบไดเร็กทอรี่โหนด
       เทคนิคการใช้แมตทริกติดกันเป็นกราฟมีความต้องการเก็บข้อมูลเกี่ยวกับเอจครบทุกรูปแบบระหว่างโหนดที่เป็นไปได้ เมื่อกราฟมี N โหนดความเป็นไปได้จะมีเอจเชื่อมกันเท่ากับ N2  ซึ่งทำให้มีค่า 0 เป็นจำนวนมาก ดังนั้น การนำลิ้งค์ลิสต์มาใช้เป็นกราฟจึงมีความเหมาะสมกว่า ซึ่งจะมีเฉพาะเอจที่เชื่อมต่อกันเท่านั้น กานใช้โครงสร้างลิ้งค์ลิสต์เป็นกราฟจะมี 2 รูปแบบ คือ แบบไดเร็กทอรี่โหนด (Node Directory) และแบบมัลติลิสต์ (Multi-List) ในหัวข้อถัดไป
       กราฟแบบไดเร็กทอรี่โหนดประกอบด้วยสองส่วน คือ ไดเร็กทอรี่ (Directory) และเซ็ตของลิ้งค์ลิสต์ แต่ละค่าในไดเร็กทอรี่มีสำหรับแต่ละโหนดที่อยู่ในกราฟ ค่าในไดเร็กทอรี่สำหรับโหนด i  จะชี้ไปยังลิ้งค์ลิสต์ที่เชื่อมต่อไปยังโหนดที่เชื่อมต่อกับโหนด i  ลิ้งค์ลิสต์เป็นเรคคอร์ดประกอบด้วยสองเขตข้อมูล คือ ค่าความแตกต่างของแต่ละโหนด (Node Identifier) เป็นหมายเลขโหนดและตัวเชื่อมชี้ไปยังสมาชิกถัดไปในลิสต์ ดังนั้น ไดเร็กทอรี่จะหมายถึงโหนดส่วนลิ้งค์ลิสต์หมายถึงเอจ


 


       จากรูปที่ 10.7 ซึ่งเป็นกราฟไม่มีทิศทางเมื่อนำมาเขียนเป็นแบบไดเร็กทอรี่โหนดจะได้เป็นรูปที่ 10.11



รูปที่ 10.11 กราฟแบบไดเร็กทอรี่โหนดที่ได้จากกราฟไม่มีทิศทางในรูปที่ 10.7
       จะได้ว่ากราฟไม่มีทิศทางที่มีออเดอร์เท่ากับ N และมีเอจเท่ากับ E ค่าที่มีในไดเร็กทอรี่เท่ากับ N และค่าในลิ้งค์ลิสต์เท่ากับ 2*E
       เมื่อใช้เป็นกราฟทิศทาง จากรูปที่ 10.8 นำมาเขียนเป็นแบบไดเร็กทอรี่โหนดก็จะได้เป็นรูปที่ 10.12 ซึ่งกราฟทิศทางที่มีออเดอร์เท่ากับ N และเอจเท่ากับ E ค่าที่มีในไดเร็กทอรี่เท่ากับ N และค่าในลิ้งค์ลิสต์เท่ากับ E



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



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



การวิ่งตามเส้นทางในกราฟ
       แอปพลิเคชั่นที่เขียนขึ้นมาเมื่อใช้งานกราฟส่วนใหญ่ต้องเข้าไปเรียกใช้งานในแต่ละโหนด เช่น การพิมพ์รายการกิจกรรมในระบบการบริหารจัดการโครงการ การแสดงผลระยะทางระหว่างเมือง เทคนิคพื้นฐานการวิ่งตามเส้นทางในกราฟ (Graph Traversal) ที่จะกล่าวถึง คือ การวิ่งตามแนวกว้างก่อน (Breadth – first) และการวิ่งตามแนวลึกก่อน (Depth – first)
        การวิ่งตามเส้นทางมีสิ่งที่ต้องระวัง คือ การวิ่งไปถึงแต่ละโหนดควรมีเพียงครั้งเดียว การวิ่งซ้ำโหนดเดิมทำให้การทำงานและผลที่ได้เกิดขึ้นซ้ำจากการวิ่งย้อนตามเส้นทางที่เคยผ่านมาแล้ว และมีหลายเส้นทางที่เชื่อมต่อระหว่างสองโหนด การเขียนอัลกอริทึมการวิ่งตามเส้นทางในกราฟจะใช้เครื่องหมายหรือตัวมาร์ก (Mark) บอกให้ทราบว่ามีการวิ่งมายังโหนดนี้แล้ว โดยก่อนหน้านี้จะถูกมาร์กว่ายังไม่วิ่งมา หรือเปลี่ยนมาใช้ตัวมาร์กกับเอจแทน ดังนั้น เอจที่ผ่านไปแล้วจะไม่ถูกรวมกับเอจอื่น ๆ ที่เหลือ เครื่องหมายหรือตัวมาร์กจะใช้เป็นมาร์กบิต (Mark Bit) เก็บไว้ในแต่ละโหนดหรือเอจ


การวิ่งตามแนวกว้างก่อน
       การวิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน (Breath – first Traversal) หรือการค้นหาตามแนวกว้างก่อน (Breath – first Traversal) เริ่มด้วยการเลือกมาหนึ่งโหนดเป็นตำแหน่งเริ่มต้นและทำเครื่องหมายว่าวิ่งผ่านมาแล้ว จากนั้นวิ่งไปยังโหนดทุกโหนดที่ติดกับโหนดนี้และยังไม่วิ่งผ่านและทำเครื่องหมาย ทำเช่นนี้จะกระทั่งวิ่งผ่านทุก ๆ โหนดที่มีอยู่ในกราฟ การวิ่งตามแนวกว้างในกราฟจากรูปที่ 10.13 ผลจากการวิ่งไปยังแต่ละโหนดจะมีลำดับเป็น 1,2,3,4,5,6,7,8 หรือมีลำดับเป็น 1,3,2,6,5,4,7,8 ก็ได้ ขึ้นอยู่กับการเลือกโหนดที่จะวิ่งผ่านทางด้านซ้ายหรือขวาก่อน
       อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างก่อนจะใช้โครงสร้างข้อมูลคิวเพื่อเก็บโหนดที่วิ่งผ่านไปแล้วในแต่ละระดับของกราฟ แต่ละโหนดที่เก็บในคิวจะใช้สำหรับวิ่งไปยังโหนดติดกันที่ยังไม่ได้วิ่งไป ทำจนวิ่งผ่านทุกโหนดในกราฟและสิ้นสุดลงเมื่อคิวว่าง อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างก่อนดังในตารางที่ 10.1


ตารางที่ 10.1 อัลอกอริทึมการวิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน



จากตัวอย่างเป็นการหาเส้นทางที่สั้นที่สุดโดยการเริ่มที่โหนด V  ไปหาโหนดใด ๆ ในกราฟระยะทางทราบได้จากอาร์เรย์ distance ส่วนเส้นทางทราบได้จากอาร์เรย์ Path เช่น ต้องการทราบเส้นทางที่สั้นที่สุดระหว่างโหนด V กับ V พบว่าระยะทางที่สั้นที่สุด คือ 11 และมีเส้นทาง คือ V à V à V à V และมื่อเขียนเป็นโปรแกรมจะได้ดังในตารางที่ 10.4 คือ


 


ตารางที่ 10.4 ตัวอย่างโปรแกรม Graph.c
#include <stdio.h>
#include <stdilib.h>
#include <conio.h>
#include “prioritQ.h”
#define NODES 6
Main () {
              priorityQueues pque;
               int adjMatrix[NODES] [NODES] = {  {0,  2,  0,  0,  0,  9},
                                                                             {0,  0,  8,  15,  0,  6},
                                                                                          {0,  0,  0,  1,  0,  0},
                                                                                         {0,  0,  0,  0,  0,  0},
                                            {0,  0,  7,  3,  0,  9},
                                                                                                {0,  0,  0,  0,  3,  0}
                                                                                };
                     int distance [NODES] = {0,  100,  100,  100,  100,  100};
                     int path [NODES] = {0,  9,  9,  9,  9,  9};
                     int visited [NODES] = {1,  0,  0,  0,  0,  0};
                     pque = createPriorityQueue (  )  ;
                     Insert (  0 ,  0  ,  pque  );
                     While (! isEmpty (pque) ) {
                                  node = Remove (pque);
                                  for (I = 0; i< NODES, i++)
                                    if(adjMatrix[node] [i] > (distance [node]+adjMatrix[node] [i] )){
                                     distance[i] = distance[node]+adjMatrix[node][i];
                                       path[i] = node;
                                        }
                                        If(visited[i] = = 0) {
                                                  Insert(I, distance[i], pque);
                                                  Visited[i] = 1;
                                        }
                             }
             }
             For(I = 1; i< NODES; i++){
                           node  = i;
                           printf(“From node %d”, node);
                            while(node ! = 0) {
                                      node = path[node];
                                      printf(“- ->%d”,node);
                              }
                              Printf(“Distance = %d\n”,distance[i]);
                     }
                   free(pque);
                   getch();
             }


       จากตัวอย่างโปรแกรมจะใช้กราฟทิศทางในรูปที่ 10.18 สร้างเป็นแมตทริกติดกันชื่อ adjMatrix เก็บค่าระยะทางโหนดที่เชื่อมติดกัน สร้างอาร์เรย์ distance, Path, visited ไว้เก็บค่าระยะทาง เส้นทางที่สั้นที่สุด และถูกวิ่งผ่านตามลำดับ เมื่อมีการวิ่งผ่านไปยังโหนดใดจะมีการเก็บระยะทางที่สั้นที่สุดโดยเปรียบเทียบค่าเดิมที่ได้จากเส้นทางอื่น


ก่อนพร้อมกับเปลี่ยนเส้นทางให้ถูกต้อง ดังนี้


          If(distance[i]>(distance[node]+adjMatrix[node][i])){
              distance[i]=distance[node]+adjMatrix[node][i];
               path[i]=node;
           }
      ในขั้นตอนท้ายเป็นการแสดงเส้นทางที่มีระยะทางที่สั้นที่สุดของแต่ละโหนดไปหาโหนดเริ่มต้น ในอัลกอริทึมนี้มีการใช้คิวลำดับความสำคัญที่ให้ค่าน้อยกว่าสำคัญกว่า จึงเขียนเป็น prioritQ.h ดังในตารางที่ 10.5 และเรียกมาใช้งานดังนี้


ตารางที่ 10.5 ตัวอย่างโปรแกรม priortQ.h
#define True 1
#define False 0
Struct queue{
                                int Priority[50];
                                int Item[50]
                                int maxsize;
                                int front;
                                int rear;
};
typedef struct queue Queue;
typedefr Queue*priorityQueues;
priorityQueues createPriorityQueue(){
                priorityQueues newQueue=malloc(sixeof(Queue));
                newQueue->maxsixe=50;
                newQueue->front=0;
                newQueue->rear=-1;
                return newQueue;


}
int isEmpty(priorityQueues q){
                it(q->rear < q->front)
                                return True;
                return False;
}
void Insert(int val, int pr, priorittyQueues q){
                int i;
                if(q->rear+1 < q->maxsize)
                                if(isempty(q)){
                                q->front=0;
                                q->rear=0;
                                q->Priority[q->reare]=pr;
                                q->Item[q->rear]=val;
                }
                else {
                                q->rear++;
                                for(i=q->rear; (i>q->front)&&(q->priority[i-1]>pr); i--){
                                                q->Item[i]=q->Item[i-1];
                                                q->priority[i]=q->Priority[i-1];
                                }
                                q->Item[i]=val;
                                q->Priority[i]=pr;
                }
                                else
                                                printf("Queue is full !!!\n");
}
int Remove(priorityQueues q){
                int val;
                if(isWmpty (q)){
                                printf("Queue is empty !!!\n";
                                return -1;
                }
                val= q->Item[q->front]);
                q->front++;
                return val;


 


{


 


 


 

รูปภาพของ ssspoonsak

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

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

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

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

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

ขอขอบคุณ

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

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

 


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

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

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

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

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

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

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

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

 

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

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