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

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

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

DTS 11-16-09-2552

การค้นหาข้อมูล (Searching)

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

การค้นหาข้อมูล searching แบ่งเป็น 2 ประเภท
1.การค้นหาข้อมูลแบบภายใน
2.การค้นหาข้อมูลแบบภายนอก

การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ (Linear)

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

การค้นหาแบบเซนทินัล (Sentinel)

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

การค้นหาแบบไบนารี (Binary Search)

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

DTS 10-09-09-2552

เรื่อง Graph (ต่อ) และ Sorting

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

แก้ปัญหาหลัก ๆ 2 ปัญหา คือ

1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด
(Minimum Spanning Trees :MST)
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่
หมดให้ไปทำข้อ 3

2. การหาเส้นทางที่สั้นที่สุด (Shortest path) Dijkstra’s Algorithm
หาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปโหนดใด ๆ ในกราฟ มีน้ำหนัก และน้ำหนักไม่เป็นลบ
ข้อกำหนด
ให้ เซต S เก็บโหนดที่ผ่านได้และมีระยะทางห่างจากจุดเริ่มต้นสั้นที่สุด
ให้ W แทนโหนด นอกเซต S
ให้ D แทนระยะทาง (distance) ที่สั้นที่สุดจากโหนดต้นทางไปโหนดใด ๆ ในกราฟ โดยวิถีนี้ประกอบด้วย โหนดในเชต
ให้ S ถ้าไม่มีวิถี ให้แทนด้วยค่าอินฟินีตี้ (Infinity) : ∞

Sorting

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

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

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

การเรียงลำดับแบบเลือก (selection sort)ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับ

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

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

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

DTS 09-02-09-2552

Tree(ทรี) (ต่อ) และ Graph (กราฟ)

เอ็กซ์เพรสชันทรี (Expression Tree)

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

- ฟังก์ชัน

- วงเล็บ

- ยกกำลัง

- เครื่องหมายหน้าเลขจำนวน (unary)

- คูณ หรือ หาร

- บวก หรือ ลบ

- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา

ไบนารีเซิร์ชทรีไบนารีเซิร์ชทรี (Binary Search Tree)

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

(1) การเพิ่มโหนดในไบนารีเซิร์ชทรี

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

(2) การดึงโหนดในไบนารีเซิร์ชทรี

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

กราฟ (Graph)

กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ

(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)

(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)

การแทนกราฟในหน่วยความจำ

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

การท่องไปในกราฟ

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

DTS 08-26-08-2552

ทรี (Tree)

ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่างๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมู

- โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก Root Node จากรูป คือ โหนด A
- โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่ระดับหนึ่ง เรียกว่า Child Node หรือ โหนดลูก จากรูป B , C , D และ E เป็น โหนดลูกของ A
- โหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลายๆ โหนด เรียกโหนดดังกล่าวว่า Parent Node หรือโหนดพ่อแม่ โหนด B ที่เป็นโหนดลูกของโหนด A ก็สามารถแตกออกเป็นโหนดย่อยๆ ได้แก่ F และ G ดังนั้น B จึงเป็นโหนดพ่อแม่ของ F และ G ในทำนองเดียวกัน A ก็เป็นโหนด พ่อแม่ของ B , C , D และ E
- เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่า กิ่ง (Branch or Edge) เป็นเส้นที่เชื่อมต่อระหว่างโหนดพ่อแม่กับโหนดลูก
- โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า Siblings หรือโหนดพี่น้อง คือ โหนดที่มีพ่อแม่เดียวกัน เช่น B , C , D , E เป็นโหนดพี่น้องกันเพราะมีโหนดพ่อแม่เดียวกัน คือ โหนด A และ F และ G เป็นโหนดพี่น้องกันโดยมี B เป็นโหนดพ่อแม่
- โหนดที่ไม่มีลูก เรียกว่า Leaf Node จากรูปโหนดที่ไม่มีโหนดลูก ได้แก่ F G H I J K L M

นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด loop ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรี ประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ เรียกว่านัลทรี (Null Tree) และถ้ามีโหนหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)

นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่างๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา ไปทางซ้าย เป็นต้น
3. ทรีคล้าย (Similar Tree) คือ ทรที่มีโครงสร้าเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนดนั้นๆ
6. ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1หน่วยซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหน ดใด ๆ บวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกวา ความสูง หรือความ ลึก

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

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

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

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

วิธีการท่องไปในทรีมี 6 วิธี แต่นิยมใช้กันมากคือ NLR , LNR , LRN

1. วิธี NLR ในลักษณะการเข้าถึงจะเริ่มต้นจากจุดแรกคือ N จากนั้นจึงเข้าไปทรีย่อยด้านซ้ายและเข้าถึงทรีย่อยด้านขวา
2. วิธี LNR สำหรับการเข้าถึงแบบอินออร์เดอร์จะดำเนินการเข้าเยี่ยมทรีย่อยด้านซ้ายก่อน จากนั้นจึงเข้าเยี่ยม N และสิ้นสุดการเข้าเยี่ยมที่ทรีย่อยด้านขวา
3. วิธี LRN การประมวลผลของโพสออร์เดอร์ จะเริ่มต้นด้วยทรีย่อยด้านซ้ายจานั้นมาประมวลผลต่อที่ทรีย่อยด้านขวาและสิ้น สุดการประมวลผลที่ N

DTS 07-05-08-2552

Queue

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

ลักษณะของคิว จะมีปลายสองข้าง ซึ่งข้างหนึ่งจะเป็นช่องทางสำหรับข้อมูลเข้าที่เรียกว่า REAR และอีกข้างหนึ่งซึ่งจะเป็นช่องทางสำหรับข้อมูลออก เรียกว่า FRONT

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

การเพิ่มข้อมูลเข้าไปในคิว

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

การนำข้อมูลออกจากคิว

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

คิวแบบวงกลม (Circular Queue)

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

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

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

DTS 06-29-07-2552

การแทนที่ข้อมูลของสแตกแบบอะเรย์

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสตจะประกอบไปด้วย 2 ส่วน คือ

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

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

การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์

รูปแบบนิพจน์ทางคณิตศาสตร์

• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C
• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+

ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์ (Operator Priority)
มีการลำดับความสำคัญของตัวดำเนินการจากลำดับสำคัญมากสุดไปน้อยสุด คือ ลำดับที่มีความสำคัญมากที่ต้องทำก่อน ไปจนถึงลำดับที่มีความสำคัญน้อยสุดที่ไว้ทำทีหลัง ดังนี้

เครื่องหมายบวก ( + ) , ลบ ( - )
เครื่องหมายคูณ ( * ) , หาร ( / )
เครื่องหมายวงเล็บเปิด (
เครื่องหมายวงเล็บปิด )

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

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

การบ้าน iostream.h และ stdio.h

<เขียนโปรแกรมโดยใช้ stdio.h >

#include
void main()
{
char name[20];
char student_id[12];
char subjectiveness[50];
int score;
printf("Input name:");
scanf("%s",&name);
printf("Input sutudent id:");
scanf("%s",&student_id);
printf("Input subjectiveness:");
scanf("%s",&subjectiveness);
printf("Input score:");
scanf("%d",&score);
if(score>=0&&score<=100) { if(score>=80)
printf("score grade 4(A)",score);
else if(score>=75)
printf("score grade 3.5(B+)",score);
else if(score>=70)
printf("score grade 3(B)",score);
else if(score>=65)
printf("score grade 2.5(C+)",score);
else if(score>=60)
printf("score grade 2(C)",score);
else if(score>=55)
printf("score grade 1.5(D+)",score);
else if(score>=50)printf
("score grade 1(D)",score);
elseprintf("score grade 0(F)",score);
}
elseprintf("error!!!",score);
}



<เขียนโปรแกรมโดยใช้ iostream.h >

#include
void main()
{
char name[20];
char student_id[12];
char subjectiveness[50];
int score;
cout<<"Input name:";
cin>>name;
cout<<"Input sutudent id:";
cin>>student_id;
cout<<"Input subjectiveness:";
cin>>subjectiveness;
cout<<"Input score:";
cin>>score;
if(score>=0&&score<=100) { if(score>=80)
cout<<"score grade 4(A)";
else if(score>=75)
cout<<"score grade 3.5(B+)";
else if(score>=70)
cout<<"score grade 3(B)";
else if(score>=65)
cout<<"score grade 2.5(C+)";
else if(score>=60)
cout<<"score grade 2(C)";
else if(score>=55)
cout<<"score grade 1.5(D+)";
else if(score>=50)
cout<<"score grade 1(D)";
elsecout<<"score grade 0(F)";
}
elsecout<<"error!!!";
}

DTS 05-22-07-2552

Linked List แบบซับซ้อน

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

2.Double Linked List หมายถึง ลิงค์ลิสต์ที่ทุกโหนดสามารถวกกลับมาที่โหนดก่อนหน้าของตนเองได้ ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง

สแตค (Stack)

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

เช่นเดียวกับการ Pop ข้อมูลออกก็ต้องตรวจสอบด้วยว่ามีข้อมูลอยู่ในสแตคหรือไม่ หากไม่มีข้อมูลอยู่ในสแตคหรือสแตคว่าง (empty stack) ก็ไม่สามารถ pop ได้การนำข้อมูลเข้า-ออก จากสแตค (push , pop) จะมีลักษณะแบบเข้าหลัง ออกก่อน (LIFO : Last In , First Out) คือ ข้อมูลที่เข้าไปในสแตคลำดับหลังสุด จะถูกนำข้อมูลออกจากสแตคเป็นลำดับแรก ยกตัวอย่างการทำงานแบบ LIFO เช่น การวางจานซ้อนกัน

รูปแสดงลักษณะของสแตค ที่ประกอบด้วยข้อมูล A , B , C , D และ E มี TOP ที่ชี้ที่สมาชิกตัวบนสุดของสแตค

การเพิ่มข้อมูลลงในสแตค (pushing stack)

การเพิ่มข้อมูลลงในสแตคการเพิ่มข้อมูลลงในสแตค คือ การนำเข้ามูลเข้าสู่สแตคโดยทับข้อมูลที่อยู่บนสุดของสแตค ข้อมูลจะสามารถนำเข้าได้เรื่อยๆ จนกว่าสแตคจะเต็ม สมมติว่าสแตคจองเนื้อที่ไว้ N ตัว ถ้าหากค่า TOP เป็น 0 แสดงว่าสแตคว่าง หากค่า TOP = N แสดงว่าสแตคเต็ม (Stack Overflow) ไม่สามารถเพิ่มข้อมูลลงในสแตคได้อีก

จากรูปแสดง การ Push ข้อมูล ABC ลงในสแตคที่มีการจองเนื้อที่ไว้ N ตัว โดยมี TOP ชี้ข้อมูลตัวที่เข้ามาล่าสุด โดยค่าของ TOP จะเพิ่มขึ้นทุกครั้งเมื่อมีข้อมูลเข้ามาในสแตค

การดึงข้อมูลออกจากสแตค (popping stack)

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

Stack Top

เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำข้อมูลนั้นออกจากสแตก

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

DTS 04-15-07-2552

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

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

โครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วย 2 ส่วน

1.Head Structure แบ่งเป็น 3 ส่วน

-count เป็นการนับจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น

-pos พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง

-head พอยเตอร์ที่ชี้ไปยังโหนดแรกของลิสต์

2.Data Node Structure จะประกอบด้วย ข้อมูลและพอยเตอร์ที่ชี้ไปโหนดถัดไป

การเพิ่มข้อมูลลงไปในลิงค์ลิสต์

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

การลบข้อมูลในลิงค์ลิสต์

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

กระบวนงานและฟังกชั่นที่ใช้ดำเนินงานพื้นฐาน

1. กระบวนงาน Create List หน้าที่ สร้างลิสตว่าง ผลลัพธ์ ลิสต์ว่าง

2. กระบวนงาน Insert Nodeหน้าที่เพิ่มข้อมูลลงไปในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าลิสต์ ข้อมูล และตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

3. กระบวนงาน Delete Node หน้าที่ลบสมาชิกในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าข้อมูลและ ตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

DTS 03-1-07-2552

pointer

ความหมายของพอยน์เตอร์

พอยน์เตอร์ (pointer) เป็นตัวแปรชนิดหนึ่งใช้เก็บตำแหน่งของข้อมูลในหน่วยความจำ โดยการเก็บตำแหน่งจะเก็บเฉพาะตำแหน่งแรกของข้อมูล

พอยน์เตอร์ มี 2 ประเภท คือ

1. direct pointer เป็นตัวแปรที่เก็บตำแหน่ง(address) ในหน่วยความจำ ของข้อมูล ตัวอย่าง เช่น ตัวแปรชื่อ x มีข้อมูลเป็น 120 ซึ่งถูกเก็บไว้ในหน่วยความจำที่ตำแหน่ง 5000 พอยน์เตอร์ ชื่อ ptr มีค่าที่เก็บไว้เป็น 5000

2. indirect pointer เป็นตัวแปรที่เก็บตำแหน่ง (address) ของพอยน์เตอร์ซึ่งเก็บตำแหน่งของข้อมูลของตัวแปร เช่น ตัวแปรชื่อ x มีข้อมูลเป็น 120 ซึ่งถูกเก็บไว้ในหน่วยความจำที่ตำแหน่ง 5000 พอยน์เตอร์ ชื่อ ptr มีค่าที่เก็บไว้เป็น 5000 และ พอยน์เตอร์ ชื่อ pptr เก็บตำแหน่งหน่วยความจำของ ptr ซึ่งมีค่า 3000 พอยน์เตอร์ pptr นี้อาจเรียกว่า pointer to pointer

การประกาศตัวแปรพอยน์เตอร์ (Declaration of Pointer Variables)

type *variable_name ;
หรือ type *variable_name1, *variable_name2,... ,*variable_nameN ;
โดย type คือ ชนิดของตัวแปร เช่น int ,float ,char ฯลฯ โดยต้องเป็นชนิดเดียวกับของตัวแปรหรือข้อมูลที่พอยน์เตอร์นั้นเก็บตำแหน่งที่อยู่

* เป็นเครื่องหมายที่ระบุว่าเป็นตัวแปรพอยน์เตอร์
variable_name1, variable_name2,..., variable_nameN ชื่อตัวแปรพอยน์ตัวที่ 1 ถึง ตัวสุดท้ายที่ประกาศในการประกาศครั้งนี้

ตัวอย่าง int *ptr1, *prt2; char *word, *str1;

การกำหนดตำแหน่งของข้อมูลให้ตัวแปรพอยน์เตอร์

การกำหนดตำแหน่งที่เก็บข้อมูลในหน่วยความจำของตัวแปรทำได้โดยใช้เครื่องหมาย & (ampersand) นำหน้าชื่อตัวแปร นำมากำหนดให้เป็นค่าของพอยน์เตอร์เช่น

int num1 = 120; /* ประกาศและกำหนดค่าให้แก่ตัวแปร ในที่นี้เป็นตัวแปร ชื่อ num1 เป็นประเภท int โดยมีค่า เป็น 120 */
int *ptr1; /* ประกาศตัวแปรพอยน์เตอร์ ในที่นี้เป็นประเภท int เพราะใช้เก็บตำแหน่งของตัวแปรประเภท int */
ptr1 = &num1; /* กำหนดค่าตำแหน่งของตัวแปรให้เป็นค่าของพอยน์เตอร์ */

พอยน์เตอร์และอาร์เรย์

พอยเตอร์สามารถกำหนดให้เป็นอารฺเรย์ได้ โดยในอาร์เรย์จะมีตัวแปร พอยเตอร์เหมือนตัวแปรอาเรย์ทั่วไป อาเรย์พอยเตอร์จะเก็บแอดเดรสของตัวแปรตามชนิดข้อมูลของตัวแปร ในการกำหนดอาเรย์ของ พอยเตอร์มีรูปแบบดังนี้
data type *pointer name[size];

พอยน์เตอร์ของพอยเตอร์

ตัวแปรพอยน์เตอร์อาจใช้เก็บค่าแอดเดรสของตัว แปรพอยเตอร์อื่น ซึ่งเก็บค่าแอดเดรสของตัวแปรหรือพอยเตอร์ตัวที่ 1 ชี้ไป แอดเดรสของพอยเตอร์ตัวที่ 2 ซึ่งพอยเตอร์ตัวที่ 2 ชี้ไปแอดเดรสตัวแปร

Set

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

1.set intersection

2.set union

3.set difference String

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

Dts 02-24-06-2552

สรุปบทเรียน

Array and Record

Array

ตัวแปรอาเรย์สามารถเก็บข้อมูลหลายๆข้อมูลไว้ได้โดยไม่ต้องใช้ตัวแปรหลายตัว เช่นถ้าต้องการเก็บอายุของเพื่อนทั้ง 20 คน ถ้าเราใช้ตัวแปรแบบ int เราจะต้องประกาศตัวแปร age1, age2, age3,.....,age20 ให้เป็นแบบ int ซึ่งเป็นการประกาศตัวแปรถึง 20 ตัวด้วยกัน แต่ถ้าใช้อาเรย์เราประกาศตัวแปร age ให้เป็นอาเรย์แบบ int เพียงตัวเดียวก็สามารถเก็บค่าทั้ง 20 ค่าได้แล้ว

อาเรย์ 1 มิติ(One-Dimensional Array)
เราสามารถสร้างตัวแปรอาเรย์ของข้อมูลชนิดต่างๆได้ไม่ว่าจะเป็นอาเรย์แบบ int, char, float ดังตัวอย่างต่อไปนี้void main(){int age [5];double grade [5];char s [5];....}จากตัวอย่างเป็นการประกาศตัวแปรชื่อ age ให้เป็นอาเรย์ของข้อมูลชนิด int ที่มีขนาดเท่ากับ 5 ดังนั้นตัวแปร age จะสามารถเก็บเลขจำนวนเต็มได้ถึง 5 จำนวน สำหรับตัวแปร grade ถูกประกาศเป็นอาเรย์ของข้อมูลชนิด double และมีขนาดเท่ากับ 5 เช่นเดียวกัน เราจึงสามารถเก็บเลขทศนิยมไว้ในตัวแปร grade ได้ 5 จำนวน และการประกาศตัวแปร s ให้เป็นอาเรย์ของข้อมูลชนิด char ที่มีขนาด 5 ตัวอักษร จึงเก็บตัวอักษรได้ 5 ตัวเมื่อเราประกาศตัวแปรอาเรย์ทั้ง 3 ตัวคือ age, grade และ s แล้ว ในหน่วยความจำจะมีการจองพื้นที่เอาไว้ตามจำนวนที่กำหนด โดยตัวแปร age และ grade นั้นจะมีการเตรียมพื้นที่ว่างในหน่วยความจำสำหรับเก็บค่าตัวแปรละ 5 ค่า และตัวแปร s ก็มีการเตรียมพื้นที่เอาไว้เก็บตัวอักษร 5 ตัวการนำค่าใส่ลงไปในตัวแปรอาเรย์ตัวแปรอาเรย์นั้นสามารถเก็บค่าได้หลายๆค่า โดยแต่ละค่าก็จะเหมือนกับเป็นตัวแปร 1 ตัว เช่นถ้าเราประกาศตัวแปร int age [5] ก็เหมือนกับว่าเรามีตัวแปร age ถึง 5 ตัว ซึ่งแต่ละตัวนี้เราเรียกว่าสมาชิกของอาเรย์ การอ้างถึงสมาชิกของอาเรย์จะต้องใช้หมายเลขลำดับ โดยเริ่มจาก 0,1,2,...ไปเรื่อยๆจนถึง” ขนาดของอาเรย์ลบด้วย 1” เช่นถ้าเราสร้างอาเรย์ int age [5] การอ้างถึงสมาชิกของอาเรย์จะใช้หมายเลข 0 ถึง 4 ถ้าเรานำเอาค่า 20, 21, 23, และ 26 มากำหนดให้กับสมาชิกลำดับที่ 0, 1, 2 และ 3 ของอาเรย์ age ตามลำดับ เราจะเขียนโปรแกรมดังนี้int age [5];age [0] = 20;age [1] = 21;age [2] = 23;age [3] = 26;จะเห็นว่าตัวแปร age เป็นอาเรย์แบบ int ซึ่งเก็บเลขจำนวนเต็มได้ 5 ค่า แต่จากตัวอย่างเรากำหนดค่าให้กับสมาชิกลำดับที่ 0 ถึง 3 โดยไม่ได้กำหนดค่าให้กับสมาชิกลำดับที่ 4 เพราะว่าการใส่ข้อมูลลงในอาเรย์นั้นไม่จำเป็นจะต้องใส่ทุกๆช่องให้ครบจึงจะ ใช้งานได้ ช่องใดไม่ได้ใส่ค่าลงไป มันก็ไม่เก็บค่าอะไรไว้จะเป็นช่องว่างๆไปโดยอัตโนมัติอาเรย์ของข้อมูลชนิด char คือตัวแปรสตริงตัวแปรอาเรย์ของข้อมูลชนิด char อีกนัยหนึ่งก็คือตัวแปรแบบข้อความหรือตัวแปรสตริง(String) ตัวแปรสตริงคือการนำเอาตัวแปรแบบ char มาเรียงต่อๆกัน ซึ่งตัวแปร char ที่เรียงต่อกันก็เรียกได้ว่าเป็นตัวแปรอาเรย์ของข้อมูลชนิด char นั่นเอง จึงสรุปได้ว่า ”สตริง” กับ “อาเรย์ของ ข้อมูลชนิด char” คือสิ่งเดียวกันตัวแปรอาเรย์ของข้อมูลชนิด char จะแตกต่างจากอาเรย์ของ int, double หรือแบบอื่นๆ เพราะว่าสมาชิกตัวสุดท้ายของอาเรย์แบบ char จะใช้เก็บรหัสสิ้นสุดข้อความ ด้วยเหตุนี้ถ้าเราประกาศตัวแปรอาเรย์แบบ char เพื่อเก็บข้อความ เราจะต้องประกาศอาเรย์ให้มีขนาดมากกว่าจำนวนตัวอักษรของข้อความที่ต้องการ เก็บอย่างน้อย 1 ตัวอักษรสมมติว่าเราประกาศตัวแปรอาเรย์แบบ char เพื่อที่จะเก็บคำว่า “Computer” ซึ่งมีทั้งหมด 8 ตัวอักษร เราจะต้องประกาศตัวแปรอาเรย์แบบ char ที่มีขนาด 9 ตัวอักษร นอกจากนี้การกำหนดค่าให้กับตัวแปรอาเรย์แบบ char หรือตัวแปรสตริงนี้ยังสามารถทำไปพร้อมกับการประกาศตัวแปรได้เลย ดังนี้char s[5] = “GIRL”;หรือchar s[5] = { ‘G’, ‘I’, ‘R’, ‘L’ }

อาเรย์ 2 มิติ (Two-Dimensional Array)
อาเรย์ 2 มิติจะเก็บข้อมูลไว้ในลักษณะของตาราง การสร้างอาเรย์ 2 มิตินั้นเราจะเขียนโค้ดภาษาซีดังนี้int a[3][3];int b[2][3];การนำค่าที่ต้องการเก็บในอาเรย์เราจะต้องอ้างถึงลำดับของสมาชิกช่องนั้นๆ ทั้งลำดับในแนวนอนและลำดับในแนวตั้ง หรือจะมองในลักษณะของคู่ลำดับก็ได้ดังรูปต่อไปนี้int a[3][3];a[0][0] a[1][0] a[2][0]a[0][1] a[1][1] a[2][1]a[0][2] a[1][2] a[2][2]จะเห็นว่าหมายเลขลำดับของอาเรย์ในแต่ละแนวเริ่มต้นจาก 0 จนถึง “ขนาดในแนวนั้นลบด้วย 1” เช่น ถ้าประกาศอาเรย์ 2 มิติขนาด 3x3 ลำดับในแนวนอนก็จะเริ่มจาก 0 ถึง 2 รวมทั้งหมด 3 ช่อง และในแนวตั้งก็จะเริ่มจาก 0 ถึง 2 รวมทั้งหมด 3 ช่องเช่นกัน

Structure

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

เราสามารถประกาศ Structure หนึ่งเป็นสมาชิกของอีก Structure ก็ได้แต่ต้องประกาศตัวที่จะนำไปใส่ไปไว้อีก Structure ก่อน

การบ้าน

#include
struct date{
int day;
int month;
int year;
};
struct ticket{
char name[20];
char last_name[20];
char telephone[15];
char place[30];
int seat;
float time[5];
float price;
struct date date1;
}ticket1;
void input_data()
{
printf("ticket data\n");
printf("day dd=");
scanf("%d",&ticket1.date1.day);
printf("month mm=");
scanf("%d",&ticket1.date1.month);
printf("year yyyy=");
scanf("%d",&ticket1.date1.year);
printf("Name =");
scanf("%s",&ticket1.name);
printf("Last name =");
scanf("%s",&ticket1.last_name);
printf("telephone=");
scanf("%s",&ticket1.telephone);
printf("place =");
scanf("%s",&ticket1.place);
printf("seat=");
scanf("%d",&ticket1.seat);
printf("time =");
scanf("%f",&ticket1.time);
printf("Price =");
scanf("%f",&ticket1.price);
}
void show_data()
{
printf("Display Data of ticket\n");
printf("Day=%d-%d-%d\n",ticket1.date1.day,ticket1.date1.month,ticket1.date1.year);
printf("name= %s Last Name= %s\n",ticket1.name,ticket1.last_name);
printf("telephone=%s\n",ticket1.telephone);
printf("place= %s\n",ticket1.place);
printf("seat=%d\n",ticket1.seat);
printf("time= %f\n",ticket1.time);
printf("price=%f\n",ticket1.price);
}
main()
{
input_data();
show_data();
}

VDO แนะนำตัว

ประวัติ

นางสาว จาริยา พิมพ์สอาด

Miss Jariya Pimsa-art

รหัสประจำตัว 50152792030

ชื่อเล่น น้ำ

งานอดิเรก : เล่น Internet , ฟังเพลง , ดูหนัง

วันเดือนปีเกิด : 11 พฤศจิกายน 2531

สถานภาพ : โสด

ศาสนา : พุทธ

ภูมิลำเนา : จังหวัดประจวบคีรีขันธ์

คติประจำใจ : อย่าคิดว่าทำไม่ได้ ถ้ายังไม่ได้ลองทำ

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

e-mail address : u50152792030@gmail.com