ลูกแรดเตรียมพร้อมล่าเหยื่อ

สิ่งที่ได้รับจากการเรียนวิชาเตรียมฝึกประสบการณ์วิชาชีพ3

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

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

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

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

4.ความสามัคคี :ความพร้อมเพรียงเป็นน้ำหนึ่งใจเดียวกัน การร่วมมือกันทำกิจการให้สำเร็จลุล่วงด้วยดีความพร้อมเพรียง หรือความปรองดองกัน อย่างเช่น- รักหมู่คณะ มีใจหวังดี
- มองคนอื่นในแง่ดีเสมอ
- เข้ามีส่วนร่วมอย่างแข็งขันในกิจการของส่วนรวม
- เป็นผู้ประสานความสามัคคีในหมู่คณะ
- ปรับตนเองให้เข้ากับผู้อื่นได้

5. ความเคารพนับถือผู้อื่น : การแสดงออกซึ่งกาย วาจา ใจ อันสุภาพอ่อนโยน การรู้จักสำรวม รู้จักการให้เกียรติผู้อื่นและให้เกียรติสิ่งที่ควรเคารพอย่างถูกต้องเหมาะสมตามโอกาสและสถานการณ์ การเคารพในการแสดงออกทางความคิด คำพูดและการกระทำของผู้อื่น อันจะทำให้ตนเองมีใจที่เปิดกว้าง ไม่หมกมุ่นอยู่แต่ความติดของตนเอง เพราะในบางครั้งการที่ยึดติดอยู่เฉพาะแต่ความคิดของตนอย่างเดียวนั้นอาจจะผิดพลาด หรือมองปัญหาได้ไม่ทั่วถึง อย่างเช่น
- แสดงความสุภาพอ่อนโยน
- แสดงอากัปกิริยาสำรวมและสงบเสงี่ยม
- ยอมรับฟังคำแนะนำของผู้อื่นด้วยกิริยาอันสำรวม

DTS 10-16/09/2552

Sorting

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

(1)การเรียงลำดับแบบภายใน (internal sorting)
เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ใน
หน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะ
คำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อน
ข้อมูลภายในความจำหลัก

(2) การเรียงลำดับแบบภายนอก
(external sorting) เป็นการเรียงลำดับข้อมูลที่
เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการ
เรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ใน
การเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่าง
การถ่ายเทข้อมูลจากหน่วยความจำหลักและ
หน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้
ในการเรียงลำดับข้อมูลแบบภายใน

การเรียงลำดับแบบเลือก (selection sort)

การเรียงลำดับแบบฟอง (Bubble Sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลใน
ตำแหน่งที่อยู่ติดกัน

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

การเรียงลำดับแบบแทรก (insertion sort)
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปใน
เซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่
ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย

การเรียงลำดับแบบฐาน (radix sort)
เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละ
หลัก

DTS-09-02/09/2552

Graph

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

กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น
ที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์
(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด
ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า
กราฟแบบไม่มีทิศทาง (Undirected Graphs)
และถ้ากราฟนั้นมีเอ็จที่มีลำดับ
ความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟ
นั้นว่า กราฟแบบมีทิศทาง
(Directed Graphs)
บางครั้งเรียกว่า ไดกราฟ (Digraph)
ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถ
เขียนชื่อเอ็จกำกับไว้ก็ได้
การเขียนกราฟแสดงโหนดและเส้นเชื่อม
ความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัว
การลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็
ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนด
ได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใด ๆ สามารถ
วนเข้าหาตัวมันเองได้

กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัด
ของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนด
หรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)
แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือ
เชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการ
เชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็น
โหนดแรก (First Node) หรือไม่มีโหนด
เริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด

กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนด
และเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็น
กราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อม
ระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดง
ลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น
(Source Node) และ โหนดสิ้นสุด (Target Node)
รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับ
รูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟ
แบบนี้จะมีทิศทางกำกับด้วยเท่านั้น

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

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

การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ
กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ
ทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับ
การท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว
แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น
เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำ
เครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว
เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป
ในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด
อื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุก
โหนดในกราฟ
ผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9
2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดย
กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม
แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น
ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง
สามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน
โหนดอื่น ๆ ต่อไปจนครบทุกโหนด

DTS-08-26/08/2552

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

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

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

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

2. ทรีที่มีแบบแผน (Ordered Tree)
หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี
ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา
ไปทางซ้าย เป็นต้น

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

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

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

6. ระดับของโหนด (Level of Node) คือ
ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนด
ราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1
และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1
หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุด
จากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1
และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่าง
จากโหนดราก เรียกว่า ความสูง (Height) หรือความ
ลึก (Depth)


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


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


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


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


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


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


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


การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปใน
ไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆ
โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบ
แผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง
วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับ
ขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือน
อาจเป็นโหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย (แทนด้วย L)
หรือทรีย่อยทางขวา (แทนด้วย R)


มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR
LNR LRN NRL RNL และ RLN แต่
วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้
กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรก
เท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะ
การนิยามเป็นนิยามแบบ รีเคอร์ซีฟ
(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละ
แบบมีดังนี้


1. การท่องไปแบบพรีออร์เดอร์
(Preorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี
NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์


2.การท่องไปแบบอินออร์เดอร์
(Inorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LNR
มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์


3. การท่องไปแบบโพสออร์เดอร์
(Postorder Traversal)
เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ
ในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
(3) เยือนโหนดราก


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

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

ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)
เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนด
ในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุก
โหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่า
หรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวา
และในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน


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


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


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

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


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


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

DTS 07-05/08/2552

Queue

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

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

การนำข้อมูลที่อยู่ตอนท้าย
ของคิวมาแสดงจะ เรียกว่า
Queue Rear แต่จะไม่ทำ
การเพิ่มข้อมูลเข้าไปในคิว

การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node
จะประกอบไปด้วย 3 ส่วนคือ
พอยเตอร์จำนวน 2 ตัว คือ Front และ rear
กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย
ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue 6. Empty Queue
2. Enqueue 7. Full Queue
3. Dequeue 8. Queue Count
4. Queue Front 9. Destroy Queue
5. Queue Rear

การประยุกต์ใช้คิว
คิวถูกประยุกต์ใช้มากในการจำลองระบบงาน
ธุรกิจ เช่น การให้บริการลูกค้า ต้องวิเคราะห์จำนวน
ลูกค้าในคิวที่เหมาะสม
ว่าควรเป็นจำนวนเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อย
ที่สุด ในด้านคอมพิวเตอร์ ได้นำคิวเข้ามาใช้ คือ
ในระบบปฏิบัติการ (Operation System) ในเรื่อง
ของคิวของงานที่เข้ามาทำงาน (ขอใช้ทรัพยากร
ระบบของ CPU) จะจัดให้งานที่เข้ามาได้ทำงาน

DTS-06-29/07/2552

5.Empty Stack

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

6. Full Stack
เป็นการตรวจสอบว่าสแตกเต็ม
หรือไม่ เพื่อไม่ให้เกิดความ
ผิดพลาดในการนำข้อมูลเข้าสแตกที่
เรียกว่า Stack Overflow

7. Stack Count
เป็นการนับจำนวนสมาชิกในสแตก

8. Destroy Stack
เป็นการลบข้อมูลทั้งหมดที่อยู่ใน
สแตก

การดำเนินการเกี่ยวกับสแตก
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack 5. Empty Stack
2. Push Stack 6. Full Stack
3. Pop Stack 7. Stack Count
4. Stack Top 8. Destroy Stack

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

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

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

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

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

DTS 05- 22/07/2552

Stack:

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

การดำเนินงานพื้นฐานของสแตก

การทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวน
การที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก
เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้
push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุด
ของสแตก
เช่น ต้องการนำข้อมูลออกจากสแตก s
ไปไว้ที่ตัวแปร i
จะได้ i = pop (s)
การนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1
ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตก
ว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย
3. Stack Top เป็นการคัดลอกข้อมูลที่
อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้น
ออกจากสแตก

การบ้าน

1. การหยิบลูกปิงปองออกจากกล่อง
2. การหยิบหนังสือที่อยู่ในกล่อง

DTS 04-15/07/2552

Set and String , Linked List

อาเรย์ของสตริงนั้นสามารถแบ่งได้เป็น 2 ประเภทคือแบบยาวเท่ากันและยาวไม่เท่ากันกรณียาวไม่เท่ากันนั้นทำได้ดังนี้
char *name[4]={“Thatchapol”, “John”, “Somchai”, “Ratchawee”};
แต่จะทำได้ก็ต่อเมื่อมีการกำหนดค่าเริ่มต้นเท่านั้น

กรณียาวเท่ากันนั้นเราจะทำการกำหนดอาเรย์ของสตริงเป็น 2 มิติ


Linked List

ลิงค์ลิสต์เป็นรูปแบบหนึ่งของโครงสร้างเหมือนกับพอยน์เตอร์คือมีการจัดการข้อมูลแบบไม่ตายตัว (Dynamic Structure) โครงสร้างของลิงค์ลิสต์จะประกอบด้วยโหนดหลาย ๆ โหนดภายใน 1 โหนดจะแบ่งออกเป็น 2 ส่วนคือส่วน data กับ link โดยการเชื่อมโยงไปยังโหนดต่อ ๆ นั้นจะใช้รูปแบบของพอยน์เตอร์เป็นตัวชี้ไปยังโหนดต่อ ๆ ไปประเภทของลิงค์ลิสต์นั้นมีหลายประเภทเช่น

1. ลิงค์ลิสต์แบบทิศทางเดียว
2. ลิงค์ลิสต์แบบวงกลม
3. ลิงค์ลิสต์แบบ 2 ทิศทาง
4. ลิงค์ลิสต์แบบหลายทิศทาง

โดยปกติครงสร้งของลิงค์ลิสต์มี 2 ส่วนใหญ่ ๆ คือ

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

ทฤษฏีการดำเนินการ

1. การสร้างลิสต์เนื่องจากลิงค์ลิสต์มีโครงสร้างที่ไม่ตายตัวดังนั้นจะต้องมีการจองพื้นที่บนหน่วยความจำให้กับพอยน์เตอร์ด้วยซึ่งก็คือการสร้างลิสต์ขึ้นมาหลักการทำงาน : จองพื้นที่หน่วยความจำให้กับลิงค์ลิสต์ก่อนดำเนินการ : ไม่มีการกำหนดค่าหลังการดำเนินการ : พอยน์เตอร์เริ่มต้นมีการจองพื้นที่บนหน่วยความจำการคืนค่า : เนื่องจากหน่วยความจำไม่มีที่ว่าง
2. การแทรกโหนดกำหนดค่าเริ่มต้น : pList = Head nodeกำหนดค่าเริ่มต้น : pPre = Node pointerกำหนดค่าเริ่มต้น : dataIn = ค่าข้อมูลในโหนดหลักการทำงาน : ทำการแทกรโหนดที่มีค่าข้อมูลลงในลิงค์ลิสต์ก่อนการทำงาน : กำหนดพอยน์เตอร์ของลิสต์ชี้ไปยังโหนดต้นลิสต์หลังการทำงาน : แทรกโหนดที่จัดเก็บข้อมูลเข้าไปยังลิสต์การคืนค่า : จริง คือแทรกโหนดเรียบร้อยการคืนค่า : เท็จ ถ้าหน่วยความจำเต็ม overflow

DTS 03-01/07/2552

สรุปเนื้อหาโครงสร้างข้อมูลแบบเซ็ต

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

ตัวดำเนินการของเซ็ต (Set operators)
ประกอบด้วย
- Set intersection
- Set union
- Set difference เป็นต้น

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

สตริง (String) หรือสตริงของอักขระ(Character String) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง

ความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง การกำหนดขนาดของสตริงนั้นต้องจองเนื้อที่ในหน่อยความจำให้กับ \0 ด้วย

สตริงกับอะเรย์

สตริง คือ อะเรย์ของอักขระ

การกำหนดสตริง

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

2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์

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

ฟังก์ชัน gets( ) เป็นฟังก์ชันที่อ่านค่าจากแป้นพิมพ์มาเก็บไว้ในหน่วยความจำ ซึ่งก็คืออะเรย์ที่ตัวแปร name ชี้อยู่ รวมทั้งช่องว่าง จนกว่าผู้ใช้จะกด Enter จะเติม null character ให้

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

การกำหนดตัวแปร country จะแตกต่างกับการกำหนดอะเรย์ เพราะเป็นการกำหนดตัวแปรพอยเตอร์ขึ้น 4 โดยที่ contry [0] จะชี้ที่ข้อมูลแรก contry [1] จะชี้ข้อมูลที่สอง contry [2] จะชี้ชี้ข้อมูลที่สาม และ contry [3] จะชี้ข้อมูลตัวสุดท้าย

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

#include
#include
main(){
struct profile
{
char name [40];
int age; char sex[10];
char address[30];
char work[10];
int weight;
int high;
char future[20];
}profile_1;
strcpy(profile_1.name,"Nathasa");
profile_1.age = 22;strcpy(profile_1.sex,"female");
strcpy(profile_1.address,"123/32 Bangkok");
strcpy(profile_1.work,"Office");
profile_1.weight = 52;profile_1.high = 165;
strcpy(profile_1.future,"Work");
printf("Name %s\n",profile_1.name);
printf("Age %d\n",profile_1.age);
printf("Sex %s\n",profile_1.sex);
printf("Address %s\n",profile_1.address);
printf("Work %s\n",profile_1.work);
printf("Weight %d\n",profile_1.weight);
printf("High %d\n",profile_1.high);
printf("Futur %s\n",profile_1.future);
}

DTS 02-26/06/2552

สรุปเนื้อหา Array and record

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

การกำหนด Array การกำหนดอะเรย์จะต้องกำหนดชื่ออะเรย์ พร้อม subscript ซึ่งเป็นตัวกำหนดขอบเขตของอะเรย์ มีได้มากกว่า 1 ตัวจำนวน

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

ข้อกำหนดของการกำหนดค่าต่ำและค่าสูงสุดของ subscript
1. ค่าต่ำสุดต้องมีค่าน้อยกว่าหรือเท่ากับค่าสูงสุดเสมอ
2. ค่าต่ำสุด เรียกว่า ขอบเขตล่าง ( lower bound )
3. ค่าสูงงสุด เรียกว่า ขอบเขตบน (upper bound)

อะเรย์ 1 มิติ data-type-array-name{expression}

data-type คือ ประเภทของข้อมูลอะเรย์ เช่น int char float

array-name คือ ชื่อของอะเรย์

expression คือ นิพจย์จำนวนเต็มซึ่งระบุจำยวยสมาชิกของอะเรย์

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

การกำหนดค่าให้กับตัวแปรชุดชนิด character

รูปแบบ

char array - namme{n}="string"

การส่งอะเรย์ให้ฟังก์ชัน สามารถกำหนดอะเรย์เป็นพารามิเตอร์ส่งให้กับฟังก์ชันได้ 2 ลักษณะ
1. การกำหนด array element เป็นพารามิเตอร์ส่งค่าให้กับฟังกืชัน ทำได้โดยอ้างถึงชื่ออะเรยืพร้อมระบุ subscript

การส่งอะเรย์ให้ฟังก์ชัน (cont.)
2. ส่งอะเรย์ทั้งชุดให้ฟังก์ชันทำได้โดยอ้างถึงชื่ออะเรย์ดดยไม่มี subscript

การประกาศอาร์กิวเมนต์ในฟังก์ชันเป็นอะเรย์

ถ้าเป็นอะเรย์มิติเดียว สามารถทำได้ทั้งหมด 3 วิธี
1. มีการประกาศขนาดอะเรย์ที่ทำหน้าที่ในการรับค่า
2. ไม่ต้องมีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า
3. ตัวแปรที่ทำหน้าท่รับค่าถุกค่าถุกกำหนดเป้นพอยน์เตอร์

อะเรย์ 2 มิติ
รูปแบบ tupe array-name[n][m];

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

ประวัติส่วนตัว

ชื่อ นางสาวว ณธษา แดงละอุ่น

Miss nathasa danglaun

ชื่อเล่น เอ้

เกิด 11 มีนาคม พ.ศ. 2530

รหัสนักศึกษา 50152792039

หลักสูตรบริหารธุรกิจ (คอมพิวเตอร์ธุรกิจ) คณะวิทยาการจัดการ

E-mail u50152792039@gmail.com

ที่อยู่ 55/220 แขวง คลองสามวาตะวันตก เขต คลองสามวา กทม 10510
Tel.083-5016430

นิสัย ร่าเิริง รักเสียงเพลง ใจอ่อน ขี้สงสาร เอาแต่ใจ

ยามว่าง ฟังเพลง ร้องเพลง ท่องเที่ยว

คติ ท้อได้แต่อย่าถอย , ทำวันนี้เพื่อวันพรุ่งนี้