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

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

1. ได้นำความรู้ไปประกอบอาชีพการงานในอนาคต
2. ได้เรียนรู้การทำงานอย่างมีระบบแบบแผน
3. ได้เรียนรู้การทำงานอย่างให้มีประสิทธิภาพมากขึ้น
4. มีความรอบคอบในการเเก้ไขปัญหามากขึ้น
5. ได้รู้จักการทำงานเป็นทีม
6. มีระเบียบวินัยมากขึ้น

DTS 12-15/09/2009

สรุปเรื่อง sorting (ต่อ)
การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะ สำหรับข้อมูลจำนวนมากที่ต้องการความรวดเร็วในการทำงาน การจัดเรียงลำดับแบบเร็วเป็นวิธีที่ซับซ้อน แต่ประสิทธิภาพการทำงานค่อนสูง กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งแล้วข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกัน กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับ อยู่แล้ว อาจจะเรียงจากน้อยไปมากหรือจากมากไปน้อย หรือค่าหลักที่เลือกในแต่ละครั้งเป็นค่าหลักที่น้อยที่สุดหรือมากที่สุด จำนวนครั้งของการ
การเรียงลำดับแบบแทรก (insertion sort)
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียง ลำดับจะ 1.เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้ถ้าเป็นการเรียงลำดับจากน้อยไปมาก 2.จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนขอมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยจะก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน กรณีที่ดีที่สุด คือ กรณีข้อมูลทั้งหมดจัดเรียงในตำแหน่งที่ต้องการเรียบร้อยแล้ว กรณีนี้ในแต่ละรอบ มีการเปรียบเทียบเพียงครั้งเดียว เพราะฉะนั้นจำนวนครั้ง กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับในตำแหน่งที่กลับกัน เช่น ต้องการเรียงลำดับจากน้อยไปมาก แต่ข้อมูลมีค่าเรียงลำดับจากมากไปน้อย จำนวนครั้งของการ
การเรียงลำดับแบบฐาน (radix sort)
เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก มีวิธีการที่ไม่ซับซ้อนแต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่องจากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม เช่นถ้ามีจำนวนข้อมูล n ตัว และในแต่ละกลุ่มใช้วิธีจัดเก็บข้อมูลในแถวลำดับ ต้องกำหนดให้แต่ละกลุ่มมีสมาชิกได้ n ตัวเท่ากับจำนวนข้อมูล เผื่อไว้กรณีที่ข้อมูลทั้งหมดมีค่าในหลักนั้น ๆหมือนกัน ถ้าเป็นเลขจำนวนใช้ทั้งหมด 10 กลุ่มกลุ่มละ n ตัวรวมทั้งหมดมีขนาดเท่ากับ (10 x n)

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

1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear) เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ
หลักการ คือ ให้นำข้อมูลที่จะหามาเปรียบเทียบกับข้อมูลตัวแรกในแถวลำดับถ้าไม่เท่ากันให้เปรียบเทียบกับข้อมูลตัวถัดไปถ้าเท่ากันให้หยุดการค้นหา
2.การค้นหาแบบเซนทินัล(Sentinel)เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแตประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนา มาจากอัลกอริทึมแบบเชิงเส้น หลักการ
1) เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก 1 ที่
2) นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือ ท้ายArray
3) ตรวจสอบผลลัพธ์จากการหาโดยตรวจสอบจากตำแหน่งที่พบ ถ้าตำแหน่งที่พบมีค่าเท่ากับ n-1แสดงว่าหาไม่พบ นอกนั้นถือว่าพบข้อมูลที่ค้นหา
3. การค้นหาแบบไบนารี (Binary Search)การค้นหาแบบไบนารีใช้กับข้อมูลที่ ถูกจัดเรียงแล้วเท่านั้น
หลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วแล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
1.หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้น
2. นำผลการเปรียบเทียบกรณีที่หาไม่พบมาใช้ในการค้นหารอบต่อไป
การค้นหาแบบไบนารี (Binary Search)
ถ้าข้อมูลมีการเรียงจากน้อยไปหามาก เมื่อเปรียบเทียบแล้วคีย์มีค่ามากกว่าค่ากลาง แสดงว่าต้องทำการค้นหาข้อมูลในครึ่งหลังต่อไป จากนั้นนำข้อมูลครึ่งหลังมาหาค่ากลางต่อ ทำอย่างนี้ไปเรื่อย ๆ จนกว่าจะได้ข้อมูลที่ต้องการ เช่นต้องการหาว่า 12 อยู่ในลิสต์ (1 4 6 8 10 12 18 19) หรือไม่
เริ่มการค้นหาแบบไบนารีด้วยการเปรียบเทียบกับค่ากลางในลิสต์ คือค่าa[4] ซึ่งเก็บค่า 8 ซึ่ง 12 > a[4] หมายความว่าค่า 12 ควรจะอยู่ในข้อมูลด้านขวาของ a[4] คือ ช่วง a[5] …a[8]โดยไม่สนใจช่วงข้อมูล a[1] …a[3] Searching

สรุป ตารางแฮซ (Hash Table)
ตารางแฮช (Hash Tables) การเข้าถึงข้อมูลโดยตรง กำหนด ให้ k เป็นคีย์ ถูกจัดเก็บอยู่ใน ช่อง k ด้วยการทำแฮชด้วยพื้นฐาน การจัดเก็บในช่องที่ h(k) โดย ใช้ฟังก์ชัน h เพื่อคำนวณหาช่องของคีย์โดยการจับคู่กับเอกภพสัมพัทธ์U ในตาราง Th: U 􀃆 {0,1,…,m-1} ฟังก์ชัน แฮช จะทำงานแบบสุ่ม แนวคิดหลัก คือ ลด ขนาดอะเรย์ของดัชนี
การชนกันของข้อมูล (Collision)
การที่แทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกัน การเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง การแก้ไขปัญหาชนกันของข้อมูล แบบห่วงโซ่(Chaining)1. กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ o(1) 2. การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ o(1)ทางปฏิบัติ ใช้เทคนิค ฮิวริสติก (Heuristic) ในการสร้างฟังก์ชันแฮช แนวทางหนึ่งที่ดีคือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่ (วิธีการหาร:Division method) ฟังก์ชันแฮช คือการกำหนดค่าคีย์ที่เกิดขึ้นในเอก ภพสัมพัทธ์จากตัวเลขธรรมชาติ
วิธีการสร้างฟังก์ชันแฮช
1.วิธีการหาร (The Division Method)
2.วิธีการคูณ(The Multiplication Method)
3.วิธีทั่วไป (Universal hashing)
เทคนิคลำดับของการตรวจสอบ
1. การตรวจสอบเชิงเส้น (Linear Probing)
2.การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)
3. การสร้างฟังก์ชันแฮชแบบสองเท่า(Double Hashing)

DTS 11-08/09/2009

สรุป กราฟ (Graph) (ต่อ)

การท่องไปในกราฟ (Graph traversal)

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

เทคนิคการท่องไปในกราฟมี 2 แบบ

1.การท่องแบบกว้าง (Breadth First Traversal) (แบบคิว)

2.การท่องแบบลึก (Depth First Traversal) (แบบสแตก)

สรุป Sorting

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

การเรียงลำดับอย่างมีประสิทธิภาพ

หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับที่ดีและเหมาะสมกับระบบงานจะต้องคำนึงถึงสิ่งต่างๆดังนี้

1.เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม

2.เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน

3.จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่

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

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

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

การเรียงลำดับแบบฟอง (Bubble Sort)

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

1.ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน

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

DTS 10-01/09/2009

สรุป Tree(ต่อ)

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

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

สรุป กราฟ (Graph)

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

นิยามของกราฟ

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

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

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

DTS 09-11/08/2009

สรุป เรื่องทรี

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

นิยามทรี
จากรูปโครงสร้างทรี เราให้นิยามทรีในรูปแบบอื่นๆ ได้อีก เช่น การให้นิยามในรูปของการเรียกซ้ำซึ่งสอดคล้องกับลักษณะธรรมชาติ ของทรี ดังนี้ คือ ทรีประกอบด้วยโหนด R ซึ่งเรียกว่า โหนดราก (root) และ ทรีย่อย (subtree) จำนวนศูนย์ หรือมากกว่าศูนย์ ได้แก่ T1,T2,...,Tk ซึ่งแต่ละทรีย่อยจะเชื่อมกับโหนดราก (R)โดยตรงด้วยเส้นเชื่อม

การเรียกชื่อองค์ประกอบของทรี
โหนดที่อยู่ระดับบนสุดของทรี เรียกว่า โหนด R ,โหนดราก, พ่อ (father)โหนดรากของทรีย่อยของ R เรียกว่า ลูก (child) ของ R โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (leaf node)เส้นเชื่อมโหนดทรี เรียกว่า กิ่ง (branch)โหนดที่มีทั้งพ่อทั้งลูก เรียกว่า โหนดกิ่ง (branch node)โหนดที่มีพ่อเดียวกัน เรียกว่า โหนดพี่น้อง (sibling) และยังอาจนิยามโหนดว่าเป็น โหนดปู่ (grandfather) หรือ โหนดหลาน (gtrandchild) ได้ในลักษณะเดียวกันเส้นทาง (path) จากโหนด n1 ไปยังโหนด nk ใดๆ จะเป็นลำดับของโหนด n1,n2,...,nkความยาว (length) ของเส้นทางจะเป็นจำนวนของเส้นเชื่อมที่อยู่ในเส้นทาง ซึ่งเท่ากับ k-1 เส้นทาง จากโหนดใดๆ ไปยังตัวเองจะมีความยาวเป็ยศูนย์ และในทรีแต่ละทรี จะมีเส้นทางหนึ่งเส้นเท่านั้นจากโหนดรากไปยัง โหนดใดๆ ความลึก (depth) เป็น ความยาวของเส้นทางจากโหนดรากไปยังโหนด n โซึ่งมีเส้นทางเดียวที่ไม่ซ้ำกัน) ความสูง (height) เป็น เส้นทางทีสุดจากโหนด n ไปยังโหนดใบถ้ามีเส้นทางจาดโหนด n1 ไปยังโหนด n2 จะเป็น บรรพบุรุษ (ancestor) ของ n2 และ n2 จะเป็น ลูกหลาน (descendant) ของ n1 ถ้า n1 != n2 ดังนั้น n1 จะเป็น บรรพบุรุษที่แท้จริง (proper ascestor) ของ n1 และ n2 ลูกหลานที่แท้จริง (proper descendant)
ทรีแบบลำดับ

ไบนารีทรี
นิยามว่า ไบนารีทรี เป็น ทรีว่าง หรือทรีที่ประกอบด้วยโหนดรากที่เรียกว่า ราก กับ ไบนารีทรี 2 ทรี เรียกว่า ทรีย่อยทางซ้าย (left subtree) และ ทรีย่อยทางขวา (right subtree) ของราก การสร้างไบนารีทรี ที่มีโหนดเดียว สามารถสร้างโหนดนั้นเป็นโหนดรากที่มีทรีย่อยทางซ้าย และทรีทางขวาเป็นทรีว่าง จะเห็นว่าไบนารีทรีแตก ต่างจากทรีทั่วไป เนื่องจากในไบนารีทรี ความหมายของคำว่า ซ้าย หรือ ขวา มีความสำคัญ ไบนารีทรี 2 โหนด ดังนั้นไบนารีทรีสามรถได้มาจากทรีแบบลำดับที่เหมาะสมกัน โดยการแยกกิ่งทางซ้ายออกจากกิ่งทางขวา

การท่องไบนารีทรี (traversal of binary tree)

ถ้าเรากำหนดให้การเยี่ยมโหนด เป็นงาน V การท่องทรีย่อยทางซ้ายเป็น L การท่องทรีย่อยทางขวาเป็น R จึงจะ ได้วิธีการท่องทรีทั้งหมด 6 วิธี
VLR LVR LRV VRL RVL RLV
การท่องทรีทั้ง 6 วิธีดังกล่าวเราจะลดเหลือ 3 วิธี ที่มีการท่องทรีย่อยทางซ้ายก่อนการท่องทรีย่อยทางขวา ส่วนอีก 3 วิธีที่เหลือ ก็เหมือนกับเป็นภาพกระจกเงาของ 3 วิธี ดังกล่าววิธีการท่องทรีย่อยทางซ้ายก่อนทรีย่อยทางขวา 3 วิธีดังกล่าว เรามีชื่อเรียกเฉพาะดังนี้
แบบ VLR เรียกว่า พรีออร์เดอร์ (preoder)
แบบ LVR เรียกว่า อินออร์เดอร์ (inorder)
แบบ LRV เรียกว่า โพสต์ออร์เดอร์(postorder)

DTS 08- 11/08/2009

สรุป คิว (queue)
คิวหรือแถวคอย (อังกฤษ: queue) เป็นประเภทข้อมูลอย่างย่อที่มีลักษณะการเรียงลำดับข้อมูล ในการเข้า-ออกในลักษณะเข้าก่อนออกก่อน FIFO (First In First Out) กล่าวคือข้อมูลที่เข้าแรกๆจะได้ออกก่อน คล้ายคนต่อคิวที่มาก่อนจะได้ซื้อของก่อน จึงเรียกว่า แถวคอย หรือ คิว

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

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

บริการที่มักจะมีเอาข้อมูลใหม่เข้าท้ายคิว (enqueue)
เอาข้อมูลออกจากหัวคิว (dequeue)
ดูข้อมูลที่อยู่หัวคิว (peek) ทำคิวว่าง ตรวจสอบความว่างของคิว (empty)

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

วิธีการสร้างคิวการสร้างคิวทำได้โดยแถวลำดับประกอบกับจำนวนเต็ม ที่เก็บดัชนีของหัวคิวและท้ายคิว สองตัว หรือใช้ รายการโยงสองชั้นวน(circular doubly linked list)
คิวแถวลำดับสำหรับการใช้แถวลำดับในการทำคิวนั้น (array queue) ตอนเริ่มต้นเราจะให้ดัชนีของหัวคิวและท้ายคิวชี้ที่ศูนย์ เมื่อเข้าคิว (enqueue) ก็จะเก็บข้อมูลตรงดัชนีท้าย พร้อมทั้งเพิ่มค่าดัชนีท้ายคิวจะไปอีกหนึ่ง (increament) ในทางตรงกันข้ามหากเอาข้อมูลตัวแรกออกจากคิว (dequeue) ก็คืนค่าสมาชิกตัวที่ดัชนีหัวคิวชี้อยู่พร้อมทั้งเพิ่มค่าดัชนีหัวคิวไปอีกหนึ่ง (decrement) หากดัชนีหัวคิววิ่งไล่ทับดัชนีท้ายคิวแสดงว่า คิวนั้นเป็นคิวว่าง (empty queue) ไม่ควร dequeue อีกเพราะจะทำให้การทำงานรวนได้ (ควรตรวจสอบก่อน dequeue)
เนื่องจากแถวลำดับมีขนาดจำกัดในบางครั้งอาจมีการทำคิววนรอบ (circular array queue) กล่าวคือบางครั้งคิวอาจมีการ enqueue และ dequeue สลับกันทำให้ดัชนีหัวคิวเลื่อนๆออกไปจนจะตกขอบขวาของแถวลำดับ ทำให้มีเนื้อที่ของแถวลำดับด้านหน้าเหลือไม่ได้ใช้จึงมีการวนเอาหางคิว มาแทนส่วนหน้าของแถวลำดับ กล่าวคือเมื่อท้ายคิวตกขอบขวาของแถวลำดับ ก็จะมีการเริ่มดัชนีท้ายคิวที่ศูนย์ใหม่และต่อท้ายคิวมาเรื่อยๆ ข้อด้อยของวิธีนี้คือ เมื่อท้ายคิวมาทับหัวคิวอีกครั้งจะตีความไม่ได้ว่าคิวเต็มแถวลำดับ หรือคิวว่างกันแน่ จึงอาจใช้ตัวแปรขนาด (size) หรือตัวแปรอื่นๆช่วยในการบอกว่าคิวว่างหรือไม่
คิวรายการโยงสองชั้นวนสำหรับการใช้รายการโยงสองชั้นวน(circular doubly linked list) ในการทำนั้น โดยหัวคิวจะอยู่ที่ปมสุดท้ายนี้ (กล่าวคือเป็นปมก่อนที่จะชี้ปมหัว เพราะว่าเป็นรายการวน) ส่วนท้ายคิวอยู่ที่ปมแรก เมื่อเข้าคิว (enqueue) ก็เพิ่มปมใหม่หลังปมหัว เมื่อจะเอาข้อมูลแรกออกจากคิว (dequeue) ก็จะเอาข้อมูลก่อนปมหัวออก ก็คือข้อมูลที่เข้าแรกๆสุด เมื่อใดที่รายการหรือคิวว่าง ก็คือตอนที่ปมหัวชี้มาที่ตัวเองนั่นเอง

DTS 07- 4/08/2009

สรุป สแตก(Stack)
การเพิ่มข้อมูลในสแตก (pushing stack)
การเพิ่มข้อมูลเข้าสแตก หมายถึงการเพิ่มข้อมูลเข้าในสแตก โดยให้ทับบนข้อมูลสุดท้ายในสแตกจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าจะเต็มสแตก ความหมายของคำว่า สแตกเต็ม คือท๊อปของสแตกชี้ที่เนื้อที่สุดท้ายของสแตกแล้ว เช่น ถ้า สแตกนั้นจองเนื้อที่ไว้ N เนื้อที่โดยที่สามารถบรรจุสมาชิกในสแตกได้ N ตัว เมื่อสแตกว่างค่าท๊อปเป็นศูนย์ เมื่อสแตกเต็มค่าท๊อปเป็น N ดังนั้นเมื่อท๊อปชี้ที่ N ก็ไม่สามารถ Push ข้อมูลลงสแตกได้อีก

นิยาม push(S,x)
ถ้าให้ S เป็นสแตก และ X เป็นข้อมูล ขบวนการ push (S,X) หมายถึง การ push ข้อมูล X ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า TOP เป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า Top จะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push

การดึงข้อมูลจากสแตก (Popping Stack)
การดึงข้อมูลออกจากสแตก หมายถึงการนำข้อมูลที่อยู่บนสุดในสแตกหรือที่ชี้ด้วยท๊อปออกจากสแตก จะสามารถ pop สแตกได้เรื่อย ๆ จนกว่าสแตกจะว่าง

นิยาม pop(S)
ถ้าให้ S เป็นสแตก ขบวนการ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้นถ้านำคำสั่ง X= pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกมา และใส่ค่าไว้ที่ X หรือการเซตค่า X ให้เท่ากับข้อมูลที่ดึงจากสแตก

การว่างของสแตก
นิยาม empty(s)
ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่าง

การแปลงนิพจน์ Infix ให้เป็น Postfix
ผู้เขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ Infix คือนิพจน์ที่มีโอเปอร์เรเตอร์ (Operator) อยู่ระหว่างโอเปอร์แรนด์ (Operand) ทั้งสอง เช่น A+B เครื่องหมาย + เป็นโอเปอร์เรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ข้อเสียของนิพจน์ infix ทีททำให้คอมไพเลอร์ยุ่งยาก คือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่นเครื่องหมายยกกำลัง (ใช้ ^ ในการเขียนโปรแกรม) มีความสำคัญมากกว่าเครื่องหมายคูณ และหาร และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวกและลบ
Operator คือเครื่องหมายกระทำ + - * / ^
Operand คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C

ลำดับความสำคัญ Operator
เครื่องหมายยกกำลัง ^
เครื่องหมายคูณกับหาร *,/
เครื่องหมายบวกกับลบ +,-
เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C

DTS 06-28/07/2009

#include<conio.h>
#include<iostream.h>
void main()
{
int num1,num2,Code,income;
clrscr();
cout<<"**************************************************"<<endl;
gotoxy(6,4);cout<<"Code"<<endl;
gotoxy(3,6);cout<<"1=number1+number2";
gotoxy(3,7);cout<<"2=number1-number2";
gotoxy(3,8);cout<<"3=number1*number2";
gotoxy(3,9);cout<<"4=number1/number2";
gotoxy(3,10);cout<<"5=Exit"<<endl;
cout<<"**************************************************"<<endl;
cout<<endl;
cout<<"Input number1 : ";
cin>>num1; cout<<"Input number2 : ";
cin>>num2; cout<<"Input Code : ";
cin>>Code; cout<&lt"Income : ";
switch(Code)
{
case 1:income=num1+num2;
cout<<income;
break;
case 2:income=num1-num2;
cout<<income;
break;
case 3:income=num1*num2;
cout<<income;
break;
case4:income=num1/num2;
cout<<income; break; default :cout<<"Exit";
}
cout<<endl;
cout<<"**************************************************";
getch();
}

DTS 05 -28/07/2009

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

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

กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create List หน้าที่ สร้างลิสต์ว่าง ผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Node
3. กระบวนงาน Delete Node
4. กระบวนงาน Search list
5. กระบวนงาน Traverse
6. กระบวนงาน Retrieve Node
7. ฟังก์ชั่น EmptyList
9. ฟังก์ชั่น list count
10. กระบวนงาน destroy list

Linked List แบบซับซ้อน
1. Circular Linked List เป็นลิงค์ลิสต์ที่สมาชิกตัวสุดท้ายมีตัวชี้ (list) ชี้ไปที่สมาชิกตัวแรกของ
ลิงค์ลิสต์ จะมีการทำงานไปในทิศทางเดียวเท่านั้นคือเป็นแบบวงกลม
2. Double Linked List เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2
ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูลก่อนหน้า (backward pointer) และตัวชี้ข้อมูลถัดไป
(forward pointer)

DTS04-15/07/2009

สรุป เรื่องSet and String
โครงสร้างข้อมูลแบบเซ็ต
เป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน ในภาษาซีจะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้
ตัวดำเนินการของเซ็ต (Set operators)
ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้น

สมมติว่า ต้องการจัดตารางเรียน 4 วิชา ได้แก่ Math, English,Physics และ Chemistry ให้กับผู้ลงทะเบียนเรียนวิธีการแก้ปัญหาเบื้องต้น
- จะต้องกำหนดเซ็ตของผู้เรียนที่ลงทะเบียนเรียนในแต่ละวิชา
- นำเซ็ตดังกล่าวที่ได้มาทำการ intersection กัน หากมีเซ็ตใดที่
ทำการ intersect กันแล้ว มีข้อมูลสมาชิกในเซ็ตที่ซ้ำกันอยู่ จะไม่สามารถจัดให้วิชาดังกล่าวอยู่ในวันเวลาเดียวกันได้ตัวอย่างดังกล่าว เป็นการนำแนวความคิดเรื่องการจัดการแบบเซ็ตมาประยุกต์ใช้งาน

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

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

DTS 03 - 30/06/2009

...สรุปเรื่อง Array and Record...

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

pointer หมายถึง ตัวเก็บตำแหน่งที่อยู่ของหน่วยความจำ (Address) หรือเรียกว่า ตัวชี้ ตำแหน่งที่อยู่ สัญลักษณ์ของ pointer จะแทนด้วยเครื่องหมาย *ถ้าเก็บข้อมูลเลขจำนวนเต็ม (ชนิด int จะใช้พื้นที่หน่วยความจำเครื่อง 2 byte ) ฉะนั้นตำแหน่ง address จะห่างกันไปทีละ 2 ช่อง ตัวอย่างเช่น fff0 àfff2 ถ้าเป็นข้อมูลชนิด char จะใช้พื้นที่ memory 1 byte ก็จะห่างกัน 1 ช่อง เช่น fffo àfff1pointer จะใช้พื้นที่มากกว่า array เพราะต้องเพิ่มพื้นที่ส่วนหนึ่งสำหรับเก็บตำแหน่งที่อยู่ของข้อมูลตัวถัดไป

ตัวโครงสร้าง (Structure)
จะเป็นการรวบรวมตัวแปรชนิดต่าง ๆ ไว้ด้วยกันเป็นกลุ่มหรือ Entrities สามารถเก็บตัวแปรต่างชนิดกันไว้ด้วยกันได้ ซึ่งจะแตกต่างจาก array ที่จะเก็บได้เฉพาะตัวแปรที่ใช้ข้อมูลชนิดเดียวกันเท่านั้น ถ้าเปรียบเทียบ
array จะเหมือนกับข้อมูลที่เรียกว่า field
Struct จะเหมือนกับข้อมูลที่เรียกว่า record
รูปแบบการประกาศ Struct
struct ชื่อตัวโครงสร้าง
{
ประกาศตัวแปรที่เป็นสมาชิกของ struct ;
}ชื่อตัวแปรที่ใช้เข้าถึงสมาชิกของ struct;

การประกาศ struct จะประกาศก่อนเริ่มต้น function main() หรือประกาศภายใน Function main() ก็ได้

DTS 02 - 23/06/2009

#include<stdio.h>
#include<string.h>
int main(void) {
struct detail_book{
char name[50];
char author[50];
int price;
int year;
int print_time_at;
int telephone;
char mail[50];
char distributor[50];

}book;
strcpy(book.name,"Business ethics");
strcpy(book.author,"Chintana Bunbongkan");
book.price=100;
book.year=2552;
book.print_time_at=11;
book.telephone=8312;
strcpy(book.mail,"Chulapress@chula.ac.th");
strcpy(book.distributor,"zero Jurarongkron university book ");

printf("name:%s\n\n",book.name);
printf("author:%s\n\n",book.author);
printf("price:%d\n\n",book.price);
printf("year:%d\n\n",book.year);
printf("print time at:%d\n\n",book.print_time_at);
printf("telephone:%d\n\n",book.telephone);
printf("mail:%s\n\n",book.mail);
printf("distributor:%s\n\n",book.distributor);
}

DTS 02 - 23/06/2009

.::สรุป Data Structure Introduction::.

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

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

DTS 01 - 23/06/2009

.::Profile::.

ชื่อ :: นางสาวเฉลิมขวัญ เปิ่นใจช่วย

MISS.Chalermkwun Pernjaichouy

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

มหาวิทยาลัยราชภัฏสวนดุสิต

E-mail :: u50132792006@gmali.com