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

 
โครงสร้างข้อมูลแบบสแตก(Stack)
 
   สแตก(Stack)เป็นโครงสร้างข้อมูล ที่ ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่าการเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวกัน
ซึ่งเรียกว่า Topของสแตก (Top Of Stack)และ ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด
เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)การดำเนินงานพื้นฐานของสแตกการทำงานต่าง ๆของสแตกจะกระทาที่ปลายข้างหนึ่งของสแตกเท่านั้นดั้งนั้นจะต้องมีตัวชี้ ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วยกระบวนการ 3กระบวนการที่สำคัญ คือ
1. Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล iในสแตกจะได้ push(s,i)คือ ใส่ข้อมูล i ลงไปที่ท็อปของสแตก sในการเพิ่มข้อมูลลงในสแตก
 
2. Pop คือการนำข้อมูลออกจากส่วนบนสุดของสแตกเช่น ต้องการนำข้อมูลออกจากสแตกsไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนำข้อมูลออกจากสแตกถ้าสแตกมีสมาชิกเพียง 1ตัวแล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง(Stack Empty) 
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก
 
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การประยุกต์ใช้สแตก
 
     การประยุกต์ใช้ สแตก จะใช้ในงานด้าน ปฏิบัตการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับ แรกสุดไว้ใช้ หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรม ย่อย การคำนวณนิพจน์ทาง คณิตศาสตร์ และรีเคอร์ชั่น (Recursion) 
 
 
 
โครงสร้างข้อมูลแบบคิว (Queue)
คิวQueue   เป็นโครงสร้างข้อมูลแบบหนึ่งซึ่งมีลักษณะที่ว่า ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง ขึ้นอยู่กับลำดับการเก็บข้อมูล จะเรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO)การสร้างคิว (Queue)
 
คิวที่อยู่ในคอมพิวเตอร์สามารถจัดเก็บได้หลายลักษณะ แต่โดยทั่วไปแล้วจะใช้การจัดเก็บแบบลิงค์ลิสท์เดี่ยวหรือจัดเก็บโดยใช้อาร์เรย์
 
 
การทำงานของคิว (Queue)
 
     การใส่ สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue ซึ่งมีรูปแบบคือenqueue (queue, newElement) หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์
 
การนำสมาชิกออกจากคิว เรียกว่า Dequeue ซึ่งมีรูปแบบคือdequeue (queue, element)
หมายถึง การนำออกจากส่วนหน้า ของคิวและให้ ข้อมูลนั้นกับ element
 
 
 
โครงสร้างข้อมูลแบบทรี(Tree)
ทรี (Tree)เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับ เช่น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน ต่าง ๆ อย่างแพร่หลาย สวนมากจะใช้สำหรับแสดง ความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ 
 
 
    การแทนที่ทรีในหน่วยความจำหลัก การ แทนที่โครงสร้างข้อมูลแบบทรีในความจำหลักจะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไป ยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั้นคือจำนวน ลิงคฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูกการแทนที่ทรี ซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากันทำให้ยากต่อการปฏิบัติการ วิธีการแทนที่ที่ง่ายที่สุดคือ ทำให้แต่ละโหนดมีจำนวนลิงคฟิลด์เท่ากันโดยอาจใช่วิธีการต่อไปนี้
 
1.โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูก ทุกโหนด การแทนที่ทรีด้วยวิธีนี้จะให้จำนวนฟิลด์ในแต่ละ โหนดเท่ากัน
 
 
2.แทน ทรีด้วยไบนารีทรีเป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือ กำหนดลิงค์ฟิลด์ใหม่จำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้น
 
 
 
 
โครงสร้างข้อมูลกราฟ (Graphs)
เป็นโครงสร้างที่ไม่เป็นแบบรายการเชิงเส้น (Non-linear) ประกอบด้วยเซต V ซึ่งเราเรียกว่า จุดของกราฟ (vertices of G) และเซต E ซึ่งแยกออกมาจากเซต V  เราเรียกว่า ด้านของกราฟ
 
กราฟจะเรียกว่า กราฟอย่างง่าย (Simple Graph)  ถ้ามีคุณลักษณะต่อไปนี้
1. กราฟต้องไม่มีลูป (Loops)
2. โหนดแต่ละคู่จะต้องมีด้านไม่เกิน 1 ด้าน
 
 
ประเภทของกราฟแบ่งออกเป็น 2 ประเภท ได้แก่
1. กราฟไม่มีทิศทาง (Undirected Graphs)
2. กราฟมีทิศทาง (Directed Graphs)
 
กราฟไม่มีทิศทาง (Undirected Graphs)คือ กราฟที่มีด้าน (Edges) ของกราฟจะไม่มีลูกศรแสดงทิศทางความสัมพันธ์ที่เกิดขึ้น (มองความสัมพันธ์ได้ทั้งสองด้าน)
 
 
 กราฟมีทิศทาง (Directed Graphs)  คือ กราฟที่มีด้าน (Edges) ของกราฟมีลูกศรแสดงทิศทางความสัมพันธ์ที่เกิดขึ้น
 
 
 
 
โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked list)          
    โครงสร้างข้อมูลแบบนี้จะให้ความสะดวกแก่การจัดการข้อมูลมากอย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่องเมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวกเนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มากในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า    การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใดลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง
              สมมติว่าเราจะแทนชุดข่าวสารที่ประกอบด้วย A,B,C ลักษณะการแทนจะเป็นไปตามรูปซึ่งเป็นภาพแสดงแนวคิดการเก็บแบบหนึ่งส่วนการเก็บข่าวสาร A,B,C แท้จริงแล้วจะเป็นในรูปไหนก็ได้แต่ก็ต้องสอดคล้องกับแนวความคิดนี้ รูปที่ 3 แสดงถึงความเป็นไปได้อีกแบบหนึ่งเมื่อข่าวสาร A,B,C อยู่ในพื้นที่ความจำ
 
 
การแทนโครงสร้างข้อมูลลิงค์ลิสต์
โครงสร้างข้อมูลลิงค์ลิสต์ (Linked List) ประกอบด้วยส่วนสำคัญ 2 ส่วนรวมเป็นโครงสร้างเรียกว่า โหนด (Node) คือ
1 .Data Link ทำหน้าที่เก็บข้อมูล
2. Link Fieldทำหน้าที่เก็บตำแหน่งที่อยู่ของโครงสร้างสมาชิกตัวถัดไป
 
 
    ลักษณะของการเก็บข้อมูลและเชื่อมโยงโหนดอื่น ๆ ของลิงค์ลิสต์ เริ่มจากจุดเริ่มต้นของโครงสร้าง (Start Pointer) ซึ่งเป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งของข้อมูลที่อยู่โหนดแรกในโครงสร้างชี้ไปยังโครงสร้างข้อมูลชุดถัดไป และในโครงสร้างชุดดังกล่าวนี้ก็มี Pointer ชี้ไปยังโครงสร้างข้อมูลอื่น ๆ ต่อไปในลักษณะเดียว ส่วน Pointer ในโหนดสุดท้ายจะเก็บค่า NULL (ค่าว่าง) บางครั้งแทนตำแหน่งสุดท้ายในโครงสร้างด้วยสัญลักษณ์ทางไฟฟ้า เรียกว่า ground symbol)  เป็นการแสดงตำแหน่งสุดท้ายในโครงสร้าง
 
 
การแทนลิงค์ลิสต์ในพื้นที่หน่วยความจำแบบหนึ่ง
 
 
 
ขั้นตอนการเพิ่มโหนดข้อมูลมีดังนี้
1. ตรวจสอบว่า โหนด n เป็นโหนดว่างหรือไม่  (ถ้าโหนด n มีค่าเป็น NULL แสดงว่าเป็นโหนดว่าง) 
2. ถ้าโหนด n ไม่เป็นโหนดว่าง ให้กำหนดพอยน์เตอร์ของ n
n -> r  =  p -> r
n -> l = q -> l
3. กำหนดพอยน์เตอร์  p -> r ให้เป็นตำแหน่งของโหนด n
4. กำหนดพอยน์เตอร์  q -> l ให้เป็นตำแหน่งของโหนด n
5. ใส่ข้อมูลลงไปในโหนด n
ขั้นตอนการลบโหนดมีดังนี้
1. ตรวจสอบว่ามีข้อมูลหรือไม่  (ถ้าโหนด r และ l มีค่าเป็น start แสดงว่าไม่มีข้อมูล) 
2. ถ้ามีข้อมูล ให้กำหนดพอยน์เตอร์ของ p และ q
p -> r  =  d -> r
q -> l = d -> l
3. คืนโหนดที่ลบให้กับระบบ
 
 
 
 
รูปภาพของ ssspoonsak

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

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

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

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

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

ขอขอบคุณ

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

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

 


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

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

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

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

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

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

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

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

 

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

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