วันพุธที่ 14 ตุลาคม พ.ศ. 2552

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

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

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

2.ได้ทราบว่าคุณธรรมคือสภาพคุณงามความดีและจริยธรรมคือธรรมที่แท้จริงมีคุณค่าภายในตัวมันทำให้ผู้ครอบครองความดีเป็นมนุษย์ที่สมบูรณ์


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

4.รู้จักการจัดเก็บเงินอย่างเป็นระบบว่าแต่ละวันควรจะใช้จ่ายเท่าไหร่และเก็บออมไว้เท่าไหร่จึงจะมีความพอดีในการใช้เงินในเดือนถัดไปทราบว่าผู้ที่มีรายได้ 0-150,000บาทไม่ต้องเสียภาษีแบบก้าวหน้าแต่ถ้าผู้ที่มีรายได้มากกว่า 150,000บาทขึ้นไปต้องเสียภาษีตามอัตราของรายได้


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

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


7.ได้ทราบว่าเส้นทางสู่ความสำเร็จจะต้องมีกระบวนการและมีการวางแผนที่ดีก่อนถึงจะประสบความสำเร็จอย่างที่คาดหวังเอาไว้ คือ จะต้องมีความฝัน(Dream) เป้าหมาย(Goals) การกระทำ(Action) ทัศนคติ(Attitude) และความเชื่อ(Believe) ว่าคุณจะต้องทำได้

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

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

วันเสาร์ที่ 19 กันยายน พ.ศ. 2552

สรุปเรืื่อง Summary (ต่อจากสัปดาห์ที่แล้ว)

DTS:11-16-09-2552

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


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

กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งแล้วข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกันจำนวนครั้งของการเปรียบเทียบเป็นดังนี้จำนวนครั้งของการเปรียบเทียบ = n log2 n ครั้ง

กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับอยู่แล้ว อาจจะเรียงจากน้อยไปมากหรือจากมากไปน้อย หรือค่าหลักที่เลือกในแต่ละครั้งเป็นค่าหลักที่น้อยที่สุดหรือมากที่สุด จำนวนครั้งของการเปรียบเทียบจะมากที่สุดดังนี้จำนวนครั้งของการเปรียบเทียบ
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง



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

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

วัตถุประสงค์ของการค้นหาโดยทั่วไป ได้แก่

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

การค้นหาแบ่งเป็น2ประเภทตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ

การค้นหาข้อมูลแบบภายใน(Internal Searching)
การค้นหาข้อมูลแบบภายนอก(External Searching)



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


2.การค้นหาแบบเซนทินัล(Sentinel)เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริทึมแบบเชิงเส้น
หลักการ
1) เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก1ที่
2) นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือท้ายArray
3)ตรวจสอบผลลัพธ์จากการหาโดยตรวจสอบจากตำแหน่งที่พบถ้าตำแหน่งที่พบมีค่าเท่ากับn-1แสดงว่าหาไม่พบ


3. การค้นหาแบบไบนารี(Binary Search)ใช้กับข้อมูลที่ถูกจัดเรียงแล้วเท่านั้นหลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วนแล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา
1.หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค่าที่ต้องการค้นตำแหน่งตัวแทนข้อมูลหาได้จากสูตร
mid = (low+high)/2
mid คือ ตำแหน่งกลาง ,

low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ


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

วันพฤหัสบดีที่ 10 กันยายน พ.ศ. 2552

สรุปเรื่อง Sorting และ เรื่อง Summary

DTS:10-09-09-2552


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

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

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

วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภทคือ

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

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

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

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



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

รอบที่ 1 เปรียบเทียบเท่ากับ n −1 ครั้ง
รอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง
รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้ง

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

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

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

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

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

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

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

เรื่อง Summary


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


การท่องไปในไบนารีทรี

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


วิธีการท่องเข้าไปไบนารีทรี:ที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา เท่านั้นคือ NLR LNR และ LR

ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบดังนี้


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


(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์


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


(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์


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


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


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

การท่องไปในกราฟอัลกอริทึมแบบกว้าง มีดังนี้
1. นำโหนดเริ่มต้นไปเก็บในคิว และปรับค่า front และ rear=1
2. นำสมาชิกออกจากคิว 1 จำนวน และปรับค่า front ใหม่ดังนี้front =front+1
3. นำโหนดประชิดทั้งหมด ของโหนดที่ตำแหน่ง front ไปเก็บในคิว โดยโหนดที่จะเข้าคิวนั้นต้องไม่เคยนำไปเก็บในคิวมาก่อน และปรับค่า rear ใหม่ดังนี้rear=rear+จำนวนโหนดประชิดที่เก็บในคิว
4. ตรวจสอบคิดถ้ามีข้อมูล ให้ไปทำข้อ 2
5. เลิกงาน


การท่องไปในกราฟอัลกอริทึมแบบลึก มีดังนี้
1. push โหนดเริ่มต้นไปเก็บในสแตก และปรับ top ให้ชี้ที่ตำแหน่งโหนดเริ่มต้น
2. pop สมาชิกใหม่ออกจากสแตก 1 จำนวน ปรับค่า top ใหม่ดังนี้top=top-1
3. push โหนดประชิดทั้งหมด ของโหนดที่ pop ครั้งสุดท้ายลงสแตกกำหนดโหนดที่จะ push นั้นต้องไม่เคย pushไปเก็บในสแตกมาก่อนและปรับค่า top ใหม่ดังนี้top=top+จำนวนโหนดประชิดที่ push ลงในแสตก
4. ตรวจสอบสแตก ถ้ามีข้อมูล ให้ไปทำข้อ 2.
5. เลิกงาน

วันอังคารที่ 8 กันยายน พ.ศ. 2552

LECTURE9

DTS:09-02-09-2552

เรื่อง TREE (ต่อจากสัปดาห์ที่แล้ว)
และเรื่อง Graph

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

การท่องไปในกราฟ (graph traversal) คือ

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

1.การท่องแบบกว้าง(Breadth First Traversal)ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้นต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ

2.การท่องแบบลึก(Depth First Traversal)การทำงานคล้ายกับการท่องทีละระดับของทรีโดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้นจากนั้นย้อนกลับ (backtrack)ตามแนววิถีเดิมนั้นจนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่นๆเพื่อเยือนโหนดอื่นๆต่อไปจนครบทุกโหนด

วันพฤหัสบดีที่ 27 สิงหาคม พ.ศ. 2552

LECTURE8

DTS:08-26-08-2552
เรื่อง Tree

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


-โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่าโหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง (Branch)

นิยามของทรี

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

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) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ

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

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

มีวิธีการท่องเข้าไปในทรี 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) เยือนโหนดราก

วันอังคารที่ 4 สิงหาคม พ.ศ. 2552

LECTURE7

DTS:07-05-08-2552

เรื่อง Queue


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

-ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่เรียกว่าFIFO (First In First Out)


การทำงานของคิวการใส่สมาชิกตัวใหม่ลงในคิวเรียกว่าEnqueueซึ่งมีรูปแบบคือenqueu(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 คือ จัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าเป็น null และจำนวนสมาชิกเป็น 0

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

3. Dequeue คือ การนำข้อมูลออกจากคิว

4. Queue Front คือ เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง

5. Queue Rear คือ เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง

6. Empty Queue คือเป็นการตรวจสอบว่าคิวว่างหรือไม่

7. Full Queue คือ เป็นการตรวจสอบว่าคิวเต็มหรือไม่

8. Queue Count คือ เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

9. Destroy Queue คือ เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว


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

-การนำข้อมูลออกจากคิวจะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ถ้าพยายามจะทำให้เกิดความผิดพลาดที่เรียกว่าunderflow

-ในกรณีที่เป็นคิวแบบวงกลมคิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อยๆจนกระทั่งrearมีค่าน้อกว่า front อยู่หนึ่งค่าคือ rear = front - 1

วันศุกร์ที่ 31 กรกฎาคม พ.ศ. 2552

LECTURE6

DTS:06-07-2552

เรื่อง Stack


การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ

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



การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย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เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก


การประยุกต์ใช้สแตก

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


การคำนวณนิพจน์ทางคณิตศาสตร์

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

1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2



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

1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว

2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix

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


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

5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix


ตัวอย่างการแปลงจากนิพจน์ Infix เป็นนิพจน์Postfix








ในการคำนวณค่า Postfix ที่แปลงมาแล้ว ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วยอีกเช่นกัน ขั้นตอนในการคำนวณ

1. อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร

2. ถ้าเป็นตัวถูกดำเนินการ ให้ทำการ push ตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา

3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่าโดย ตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่1
ตามลำดับ


4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูก ดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3

5. ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก

6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่

วันจันทร์ที่ 27 กรกฎาคม พ.ศ. 2552

การเขียนโปรแกรมแบบ iostream.h และ stdio.h

DTS:05-22-07-2552

โปรแกรมสำหรับคำนวณพื้นที่วงกลมตามที่เรากำหนดโดยเขียนออกมาในรูปแบบ iostream.h และ stdio.h


"iostream.h"




















"stdio.h"






























วันศุกร์ที่ 24 กรกฎาคม พ.ศ. 2552

ยกตัวอย่างสิ่งที่เจอในชีวิตประจำวันแบบ(LAST IN FIRST OUT)

DTS:05-22-07-2552

ยกตัวอย่างสิ่งที่เจอในชีวิตประจำวันแบบ(LAST IN FIRST OUT)

-ตั๋วรถเมล์

-ด้ายเย็บผ้า

- การถ่ายเอกสาร

-การหยิบหนังสือจากกองหนังสือ

-แก้วน้ำพลาสติกใน 7-11

- แก้วพลาสติกตามร้านขายชาไข่มุกที่วางซ้อนกัน

LECTURE5

DTS:05-22-07-2552

เรื่อง Linked List และ เรื่อง Stack

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


-กระบวนงาน Retrieve Node
หน้าที่ หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์
ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์


-ฟังก์ชั่น EmptyList
หน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์
ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่างเป็นเท็จ ถ้าลิสต์ไม่ว่าง


-ฟังก์ชั่น FullList

หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์

ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็มเป็นเท็จ ถ้าสามารถมีโหนดอื่น

-ฟังก์ชั่น list count

หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ข้อมูลนำเข้าลิสต์

ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์

-กระบวนงาน destroy list

หน้าที่ ทำลายลิสต์

ข้อมูลนำเข้า ลิสต์

ผลลัพธ์ ไม่มีลิสต์

Exam.

Algorithm destroyList (ref pList )

Pre pList is a pointer to a valid list head structure
Post All data and head structure deleted
Return null head pointer
1. Loop (pList->count not zero)
1 dltPtr = pList->head
2 pList->head = dltPtr->link
3 pList->count = pList->count-1
4 release (dltPrt)
2. release (pList)
3. Return null pointer
End destroyList


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

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

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


เรื่อง 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) แต่ถ้าไม่มีสมาชิกในสแตกแล้วทำการ popสแตกจะทำให้เกิดความผิดพลาดที่เรียกว่า Stack Underflow
3.Stack Topเป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก





LECTURE4

DTS:15-22-07-2552

เรื่อง Linked List

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

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


โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2 ส่วน คือ

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

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


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

-กระบวนงาน Create List

หน้าที่ สร้างลิสต์ว่าง

ผลลัพธ์ ลิสต์ว่าง



-กระบวนงาน Insert Node

หน้าที่เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการ

ข้อมูลนำเข้า ลิสต์ ข้อมูล และตำแหน่ง

ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง


-กระบวนงาน Delete Node

หน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ

ข้อมูลนำเข้า ข้อมูลและตำแหน่ง

ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง


-กระบวนงาน Search list

หน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์

ผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล

วันอังคารที่ 14 กรกฎาคม พ.ศ. 2552

แบบฝึกหัดท้ายบทที่2

DTS 03-01-07-52

แบบฝึกหัดท้ายบทที่2

1.ให้นักศึกษากำหนดค่าของ Array 1 มิติ และ Array 2 มิติ

ตอบ Array 1 มิติ คือ float nettotal[4];

Array 2 มิติ คือ int name[5][6];


2.ให้นักศึกษาหาค่าของ A[2] , A[6] จากค่าA={2,8,16,24,9,7,3,8,}

ตอบ A[2] คือ 16A[6] คือ 3


3.จากค่าของ int a [2][3] = {{6,5,4},{3,2,1}}; ให้นักศึกษาหาค่าของ a[1][0]
และa[0][2]

ตอบ a[1][0] คือ 3a[0][2] คือ 4


4.ให้นักศึกษากำหนด structure ที่มีค่าของข้อมูลจากน้อย 6 Records

ตอบ struct student {


char name[30];


char surname[40];


int age;


char sex[10];


char address[50];


int month;


int year;


5. ให้นักศึกษาบอกความแตกต่างของการกำหนดตัวชนิด Array กับตัวแปร Pointer ในสภาพของการกำหนดที่อยู่ของข้อมูล

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

pointer หมายถึง ตัวเก็บตำแหน่งที่อยู่ของหน่วยความจำ(Address) หรือเรียกว่า ตัวชี้ ตำแหน่งที่อยู่ สัญลักษณ์ของ pointer จะแทนด้วยเครื่องหมาย *


วันเสาร์ที่ 4 กรกฎาคม พ.ศ. 2552

สรุป LECTURE3

DTS: 03-01-07-2552

เรื่อง Pointer

Pointer เป็นตัวแปรชนิดหนึ่งที่ทำหน้าที่เก็บตำแหน่งที่อยู่ (Address)
ของตัวแปรที่อยู่ในหน่วยความจำ

การประกาศชนิดของตัวแปรพอยน์เตอร์
รูปแบบ

type *variable-name
type
หมายถึง ชนิดของตัวแปร
* หมายถึง เป็นเครื่องหมายที่แสดงว่า ตัวแปรที่ตามหลังเครื่องหมายนี้เป็น ตัวแปรพอยน์เตอร์
variable-name
เป็นชื่อของตัวแปรที่ต้องการประกาศว่าเป็นชนิดพอยน์เตอร์

ตัวอย่าง
char *prt หมายความว่า ประกาศว่าตัวแปร prt เป็นตัวแปรพอยน์เตอร์

ที่ใช้เก็บตำแหน่งเริ่มต้นที่จะเก็บ char

เครื่องหมายที่ใช้ทำงานกับตัวแปรพอยน์เตอร์

1. เครื่องหมาย &
เป็นเครื่องหมายที่ใช้เมื่อต้องการให้เอาค่าตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำออกมาใช้
2. เครื่องหมาย * มีการใช้งาน 2
ลักษณะ คือ
- ใช้ในการประกาศ parameter
ว่าเป็นตัวแปรแบบพอยน์เตอร์
- ใช้เป็น dereferencing operator
จะใช้เมื่อต้องการนำค่าที่อยู่ในตำแหน่งที่ตัวแปรพอยน์เตอร์นั้นชี้อยู่ออกมาแสดง


เรื่อง Set and String

โครงสร้างข้อมูลแบบเซ็ต

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

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

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

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

สตริง คือ อะเรย์ของอักขระ
เช่น char a[6] อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ หรือ เป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character

เช่น
char a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};
char a[ ]=“HELLO”;

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

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

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


การกำหนดค่าคงตัวสตริง

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

เราจะใช้เครื่องหมายdouble quote (“ ”) เช่น “abc”
คือ ชุดของอักขระที่มีขนาด 4 (รวม \0 ด้วย)


Example

#define NME “Semi”
main ( ){
char *cpntr;
cpntr=NME;
printf(“con\n”);
printf(“%s, %u, %c\n”, “con”, “duc”,*“tor”);
printf(““%s, %u, %c\n”, NME, NME,*NME);
printf(““%s, %u, %c\n”, cpntr, cpntr,*cpntr);
}

ผลการรันโปรแกรม
con
con, 37, t
Semi, 16, S
Semi, 16, S






วันอังคารที่ 30 มิถุนายน พ.ศ. 2552

Stucture

DTS:02-24-06-2552

Stucture เกี่ยวกับประวัตินักศึกษาซึ่งจะระบุชื่อ นามสกุล

อายุ เพศ ที่อยู่ วันเดือนปีเกิด

#include
struct student
{
char name[30];
char surname[40];
int age;
char sex[10];
char address[50];
}data;
struct birthday
{
int day;
int month;
int year;
}date;
void main()
{
printf("Student Data\n");
printf("name:");
scanf("%s",&data.name);
printf("surname:");
scanf("%s",&data.surname);
printf("age:");
scanf("%d",&data.age);
printf("sex:");
scanf("%s",&data.sex);
printf("address:");
scanf("%s",&data.address);
printf("Date of birth:");
printf("date is (dd/mm/yy): ");
scanf("%d/%d/%d",&date.day,&date.month,&date.year);
{
printf("Display Data of student \n");
printf("Name:%s\n",data.name);
printf("surname:%s\n",data.surname);
printf("Age:%d\n",data.age);
printf("sex:%s\n",data.sex);
printf("address:%s\n",data.address);
printf("date of birthday:%d/%d/%d\n",date.day,date.month,date.year);
}
}






วันอาทิตย์ที่ 28 มิถุนายน พ.ศ. 2552

สรุป LECTURE1

DTS :01-17-06-2552

เรื่อง Introduction

ข้อมูล (Data) คือ ข้อเท็จจริงต่าง ๆ ซึ่งอาจจะเป็นตัวเลขหรือไม่เป็นตัวเลขก็ได้
โครงสร้าง (Structure) คือ ความสัมพันธ์ของสมาชิกในกลุ่ม

โครงสร้างข้อมูล (Data Structure)

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


โครงสร้างข้อมูลในภาษาคอมพิวเตอร์ที่ใช้กันอยู่ในปัจจุบัน แบ่งออกเป็น 2 ประเภท คือ

1. โครงสร้างข้อมูลทางกายภาพ (Physical Data Structure)

2. โครงสร้างข้อมูลทางตรรกะ (Logical Data Structure)


ภาษาขั้นตอนวิธี (Algorithm Language) เป็นภาษาสำหรับเขียนขั้นตอนวิธี มีรูปแบบที่สั้น กระชับแลรัดกุม
และมีข้อกำหนด ดังต่อไปนี้


1. ตัวแปรจะต้องเขียนแทนด้วยตัวอักษร หรือตัวอักษรผสมตัวเลข
2.
การกำหนดค่าให้ตัวแปร ใช้เครื่องหมาย
3
. นิพจน์ที่เป็นการคำนวณจะมีลำดับขั้นของการคำนวณตามลำดับ คือวงเล็บ, ยกกำลัง , คูณหรือหาร, บวกหรือลบเครื่องหมายระดับความสำคัญเท่ากัน คำนวณจากซ้ายไปขวา
4. ข้อความไปยังขั้นตอน ใช้รูปแบบ คือgoto
เลขที่ขั้นตอน
5
. การเลือกทำตามเงื่อนไข จะต้องตรวจสอบเงื่อนไขก่อนทำงาน มีรูปแบบดังนี้
- แบบทางเลือกเดียว ใช้รูปแบบ คือif (condition) then statement1
- แบบสองทางเลือก ใช้รูปแบบ คือif (condition) then statement1

else statement 2
6
. การทำงานแบบซ้ำ
- แบบทดสอบเงื่อนไขที่ต้นวงรอบ มีรูปแบบ ดังนี้
while (condition) do
statement

- แบบทำซ้ำด้วยจำนวนครั้งของการทำซ้ำคงที่ มีรูปแบบ
for a=b to n by c do
statement

7. คำอธิบาย เป็นข้อความที่อธิบายรายละเอียดของขั้นตอนการทำงาน

จะอยู่ในเครื่องหมาย / และ /






วันเสาร์ที่ 27 มิถุนายน พ.ศ. 2552

LECTURE2

DTS : 02-24-06-2552

เรื่อง Array and Record

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

การกำหนด Array

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

การกำหนด subscript แต่ละตัวจะประกอบไปด้วย ค่าสูงสุดและ ค่าต่ำสุดของ subscript นั้น การประกาศค่าตัวแปรอะเรย์ ในภาษาคอมพิวเตอร์ บางภาษา เช่น

ภาษาปาสคาล var A: array[1..10] of real;

var K: array[1..5,1..10] of integer;

ภาษาซี float A[10];

int K[5] [10];

ข้อกำหนดของการกำหนดค่าต่ำสุดและค่าสูงสุดของ subscript คือ

1. ค่าต่ำสุดต้องมีค่าน้อยกว่าหรือเท่ากับค่าสูงสุดเสมอ

2. ค่าต่ำสุด เรียกว่า ขอบเขตล่าง (lower bound)

3. ค่าสูงสุด เรียกว่า ขอบเขตบน (upper bound)


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

ตัวอย่าง

จำนวนสมาชิกหรือขนาดของอะเรย์ nมิติ หาได้จากขนาดของอะเรย์ = ผลคูณของขนาดของsubscript แต่ละตัวเช่นขนาดของอะเรย์

A = Upper bound – lower bound+1

= 10-1+1 = 10


อะเรย์ 1 มิติ

รูปแบบ
data-type array-name[expression]

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

array-name คือ ชื่อของอะเรย์expression คือ นิพจน์จำนวนเต็มซึ่งระบุจำนวนสมาชิกของอะเรย์ตัวอย่าง char[4]; int num[10];

Example


#include
#define N 5
int main(void) {
int i;
float score[N];
float total=0;
printf("Number of student [%d]\n",N);
for(i=0; i

การส่งอะเรย์ให้ฟังก์ชั่น
สามารถกำหนดอะเรย์เป็นพารามิเตอร์ส่งให้กับฟังก์ชันได้ 2 ลักษณะ
1. การกำหนด array element เป็นพารามิเตอร์ส่งค่าให้กับฟังก์ชัน ทำได้โดยอ้างถึงชื่ออะเรย์พร้อมระบุsubscript
ตัวอย่าง
swap(num[2],num[3]);
draw_house(color[i],x[i],y[i]);


2. ส่งอะเรย์ทั้งชุดให้ฟังก์ชันทำได้โดยอ้างถึงชื่ออะเรย์โดยไม่มีsubscript
ตัวอย่าง
#define N 10
float a[N]; float avg;
avg = average(N,a);

อะเรย์2มิติ
รูปแบบ
type array-name[n] [m];
type หมายถึง ชนิดของตัวแปรที่ต้องการประกาศเป็นอะเรย์
array-name หมายถึง ชื่อของตัวแปรที่ต้องการประกาศเป็นอะเรย์
n หมายถึง ตัวเลขที่แสดงตำแหน่งของแถว
m หมายถึง ตัวเลขที่แสดงตำแหน่งของคอลัมน์

ตัวอย่าง
char a[2][3];
col1 col2 col3
row1 a[0][0] a[0][1] a[0][2]
row 2 a[1][0] a[1][1] a[1][2]
หมายถึง คอมพิวเตอร์จะจองเนื้อที่ในหน่วยความจำ จำนวน 6 ที่สำหรับตัวแปร a


Example
#include
int main(void)
{
int a[3][4],r,c;
for(r=0; r<=2; r++) for(c=0;c<=3;c++) { printf(" Entry Number "); scanf("%d",&a[r][c]); } for(r=0; r<=2; r++) for(c=0;c<=3;c++) { printf("\n Display"); printf("%4d",a[r][c]); } return 0;


การนิยาม structure
รูปแบบ
struct struc-name {
type name-1;
type name-2;
………
type name-n;
} struc-variable;


struct เป็นคำหลักที่ต้องมีเสมอ
struc-name ชื่อกลุ่ม structure
type ชนิดของตัวแปรที่อยู่ในกลุ่ม structure
name-n ชื่อของตัวแปรที่อยู่ในกลุ่ม structure
struc-variable ชื่อตัวแปรชนิดโครงสร้างคือ ตัวแปรที่มีโครงสร้าง เหมือนกับที่ประกาศไว้ใน ชื่อของกลุ่ม structureอาจมีหรือไม่มีก็ได้
ถ้ามีมากกว่า
1 ชื่อ แยกกันด้วยเครื่องหมายคอมม่า (,)


การประกาศสมาชิกแต่ละตัวของ structure

สมาชิกแต่ละตัวของ structure จะเป็นตัวแปรธรรมดา พอยน์เตอร์ อะเรย์หรือ structure ตัวอื่นก็ได้ โดยชื่อของสมาชิกแต่ละตัวต้องแตกต่างกัน

ตัวอย่าง
struct employee {
char name[30];
int age;
float salary;
} personel;