biiw: 2011

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

test 1

ขั้นแรกเลย
1.จะดูเรื่องอะไร ถ้ามีหนังที่อยากดูแล้ว เดินไปที่ ขายตั๋ว ถ้ายัง เดินไปดูที่ จอโปรแกรมหนังนะค่ะ มันจะมีชื่อหนัง เวลาฉายให้เราดู กล้าๆหน่อย ก็ถามเลยค่ะ พนักงานอ่ะค่ะ
2.พอได้เรื่องที่อยากดูแล้ว ก็ไปซื้อตั๋ว ที่เคาร์เตอร์ ที่จะมี เส้นสีแดงๆกั้น วนไปวนมา ให้เดินอ่ะค่ะ
3.พอไปถึง พนักงานก็จะถามเราว่าจะดูเรื่องไร เราก็ตอบไป ว่าอยากดูเรื่องไร
4.จากนั้น พนักงานก็จะให้เราเลือกที่นั่ง โดยให้เรา ดูที่จอคอมฯ
5.เราก็เลือกเอาว่าจะนั่งตรงไหน ชี้ไปเลยค่ะ หรือถ้าประหม่ามากๆ ก็สวมวิญญาณ อาทตัวแม่ บอกไปว่า "ตรงไหนก็ได้ค่ะ"
6.ทีนี้เค้าก็จะคิดเงิน เราก็จ่ายตังค์เค้าไป(ถ้าไม่จ่าย ก็อดดูนะ) เสร็จแล้วก็รับตั๋วมา
7.ที่นี้ พอรับตั๋วมาแล้ว อย่าเพิ่งไปไหนนะค่ะ ถามเค้าก่อนว่า โรงหนังที่เราได้เนี๊ยะอยู่ตรงไหน จะได้เดินไปถูก
(กรณีที่ เคาร์เตอร์กะโรงมันอยู๋คนละที่ ถามเอาดีสุด ไม่ต้องอาย ใครๆก็ถามทั้งนั้น)
8.พอรู้ที่อยู่โรงหนังแล้ว ก็เดินไปรอเลยค่ะ ดูเวลาในตั๋วนะว่ากี่โมง ค่อยฟังเวลาเค้าประกาศให้ดีนะค่ะ
9.ระหว่างรอ จะซื้อ อะไรกิน แบ้วๆก็ได้ค่ะ แต่ต้องซื้อที่หน้าโรงหนังนะ เด่วเค้าจะไม่ให้เอาเข้าซะ
10.พอได้ยินเค้าประกาศว่า หนังเรื่องที่คุณจะดูให้เข้าโรงหนังได้ ก็เดินไปเลยค่ะ ส่งตั๋วให้พนักงาน เค้าจะฉีกแล้วแบ่งให้เรา ครึ่งนึง (มีน้ำใจ อุสส่าแบ่งให้เรา อิอิ)
11.ดู เลขที่นั่งของคุณไว้ เพราะพอเข้าไปในโรงหนัง ทีนี้ก็จะมืดแล้วนะ (ถึงแม้จะมาดูกลางวัน ก็มืด) มองไม่เห็นล่ะ
12.จำเลขที่นั่งไว้ แล้วเดินเข้าโรงหนังไปหาเก้าอี้ สมมุติ คุณได้เลขที่นั่ง H15 ก็เดินไปทางเดินแล้วมองไปที่มันเป็นตัว H อ่ะค่ะ พอถึงก็หยุด แล้วเดินเข้าไปในแถวตัว H เลย เดินไปจนถึงเลข 15 ที่นี้ก็นั่งเลยค่ะ
13.นั่งเสร็จก็ เพลิดเพลินกะการดูหนัง ดูดน้ำ กินป๊อปคอน สบายใจ

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

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

test 1

วันจันทร์ที่ 8 สิงหาคม พ.ศ. 2554

โครงสร้างข้อมูลและอัลกอริทึม

โค้างสร้างและอัลกอริทึม

พื้นฐานโครงสร้างข้อมูล

วัตถุประสงค์เชิงพฤติกรรม (Behavioral Objectives)
หลังจากเรียนบทนี้แล้วนักศึกษาจะมีความสามารถดังนี้
1. ศึกษาขั้นตอนการพัฒนาซอฟต์แวร์
2. บอกลักษณะโครงสร้างข้อมูล + อัลกอริทึม = โปรแกรม
3. อธิบายความหมายโครงสร้างข้อมูล/ชนิดข้อมูล
4. เขียนโครงสร้างข้อมูลเบื้องต้นและโครงสร้างข้อมูลนามธรรม
5. เข้าใจโครงสร้างข้อมูลกับภาษาเขียนโปรแกรม
6. จัดบอร์ดเชิงปฏิบัติการ “พื้นฐานโครงสร้างข้อมูล”
7. สนทนาเชิงปฏิบัติการ “โครงสร้างข้อมูลเบื้องต้นและโครงสร้างข้อมูลนามธรรม”
8. อธิบายคำศัพท์ได้ 12 คำ

บทที่ 1
พื้นฐานโครงสร้างข้อมูล
คอมพิวเตอร์เป็นอุปกรณ์ที่สร้างขึ้นมาเพื่อใช้จัดการและเปลี่ยนแปลงข้อมูลข่าวสาร (Information) ดังนั้น จึงต้องมีการศึกษาถึงการควบคุมดูแลการทำงานของคอมพิวเตอร์ที่ยุ่งเกี่ยวกับข้อมูลข่าวสาร เมื่อมีการเปลี่ยนแปลงแก้ไขหรือเพื่ออำนวยประโยชน์ที่ต้องการการทำงานเพื่อนแก้ไขปัญหาต่าง ๆ ด้วยระบบคอมพิวเตอร์จะประกอบด้วยส่วนต่าง ๆ ทางด้านฮาร์ดแวร์ (Hardware) เช่น ซีพียู (CPU) หน่วยความจำ (Memory) อุปกรณ์รับส่งข้อมูล(Input/Output Device)และซอฟแวร์(Software)ที่นำมาใช้ควบคุมการทำงานของฮาร์ดแวร์ เพื่อแก้ไขปัญหานั้น ๆ ในการแก้ไขปัญหาจึงต้องมีกระบวนการพัฒนาซอฟต์แวร์ (Software Development) ที่เป็นขั้นตอนมาใช้ดังนี้
ขั้นตอนการพัฒนาซอฟแวร์
การแยกแยะและวิเคราะห์ปัญหา
ในขั้นตอนแรกเป็นการแก้ไขปัญหาโดยการวิเคราะห์และแยกแยะ สิ่งแรกที่ต้องพิจารณา คือ เอาต์พุต ที่ต้องการและมีข้อมูลข่าวสารอะไรบ้างที่ทำที่ทำให้สามารถแก้ไขปัญหาได้หลังจากพิจารณาเอ้าท์พุตก็คือพิจารณาอินพุต และมีข้อมูลข่าวสารอะไรบ้างที่ทำให้สามารถแกไขปัญหาได้ หลังจากแยกแยะเอ้าท์พุตและอินพุต รวมถึงข้อมูลข่าวสารที่ต้องการเสร็จสิ้นลงก้เป็นการพัฒนาเขียนอัลกอรึทึมและโปรแกรม
การออกแบบระบบ
เนื่องจากระบบคอมพิวเตอร์ไม่สามารถที่จะเข้าใจและแกไขปัญหาบางอย่างได้ จึงต้องมีวิธีการที่จะแก้ไขปัญหาโดยการออกแบบระบบ ซึ่งเป็นการวางแผนออกแบบที่แยกแยะออกเป็นปัญหาย่อย และพิจารณาสร้างชุดคำสั่งเพื่อแก้ไขปัญหาย่อยนั้น จากนั้นมารวมกันเป็นระบบที่สามารถแก้ไขปัญหาทั้งหมด มีลักษณะการวางแผนออกแบบจากบนลงล่าง (Top-down Design) ซึ่งประกอบด้วย 2 ส่วนหลัก ๆ คือ
1. โครงสร้างข้อมูล (Data Strutcure) ใช้ควบคุมและจัดการกับข้อมูลของปัญหานั้น ๆ หรือที่เรียกว่าชนิดข้อมูลมีโครงสร้าง เรียกสั้น ๆ ว่าชนิดข้อมูล เช่น ชนิดข้อมูลอาร์เรย์ ชนิดข้อมูลสแตก และชนิดข้อมูลลิ้งค์ ลิสต์ การออกแบบระบบต้องเลือกใช้โครงสร้างข้อมูลอย่างเหมาะสมเพื่อจัดการกับข้อมูลที่ใช้ในระบบ
2. การออกแบชุดคำสั่ง (Module Design) ในการแก้ไขปัญหาจะต้องมีกระบวนการทำงานเพื่อให้ได้มาซึ่งข้อมูลข่าวสารหรือเอ้าท์พุต ที่ต้องการโดยชุดคำสั่งเป็นส่วนประกอบของระบบ จึงต้องมีการออกแบบการทำงานที่เป็นชุดคำสั่งหรือโมดุลนั้นๆ และเรียกว่า อัลกอรึทึม ได้เป็น
โครงสร้างข้อมูล + อัลกอริทึม = โปรแกรม
การที่จะเลือกใช้โครงสร้างข้อมูลและอัลกอริทึมในการออกแบบให้การทำงานอย่สงมีประสิทธิภาพ ซึ่งถือว่าเป็นหัวใจสำคัญของการออกแบบซอฟต์แวร์จะพิจารณาได้จากลักษณะดังต่อไปนี้
1. ความถูกต้อง
2. ระยะเวลาการทำงาน
3. จำนวนพื้นที่ใช้งาน
4. ความเรียบง่าย
5. ความเหมาะสมที่สุด
การเขียนคำสั่งและรวมกัน
การเขียนคำสั่ง (Coding) คือ การเขียนคำสั่งต่าง ๆ ของโปรแกรมให้ทำงานเป็นไปตามโครงสร้างข้อมูลและอัลกอริทึมด้วยภาษาเขียนโปรแกรมภาหนึ่ง ถ้าโครงสร้างข้อมูลและอัลกอริทึมถูกออกแบบไว้เป็นอย่างดีทำให้กระบวนการแปลงคำสั่งจากภาษาเขียนให้เป็นภาษาเครื่องก็จะง่ายไม่ยุ่งยากลำบาก
การรวมกัน (Integration) เป็นกระบวนการนำคำสั่งต่าง ๆ ที่เขียนเป็นแต่ละชุดคำสั่งมารวมกันและให้มีการทำงานร่วมกันได้เป็นซอฟต์แวร์โปรแกรมขึ้นมา
การเขียนโปรแกรมที่ดีนั้นจะต้องมีความถูกต้องในการทำงาน สามารถอ่านคำสั่งและทำความเข้าใจได้ง่าย จึงต้องมีโครงสร้างการเขียนโปรแกรมที่ดี ซึ่งมีวิธีการเข้ามาช่วยเหลือในการเขียนโดยพิจารณาได้จากเรื่องต่อไปนี้
1. การเขียนโปรแกรมควรเป็นแบบบนลงล่าง (Top-Down) โดยเฉพาะกับปัญหาที่มีขนาดใหญ่หรือมีความซับซ้อน จึงควรแยกปัญหาใหญ่ออกเป็นปัญหาย่อย ๆ จากการเขียนคำสั่งทั้งหมดในโปรแกรม ก็แยกเป็นชุดคำสั่งย่อย ๆ
2. ใช้โครงสร้างควบคุมการทำงาน (Control Structure) ในการเขียนโปรแกรมหรือชุดคำสั่ง เช่น การใช้เงื่อนไข IF การใช้วนลูปแบบต่าง ๆ
3. ควรใช้ตัวแปรที่เป็นแบบโลคอล (Local Variable) และใช้กับชุดคำสั่งเพื่อแก้ปัญหาย่อย
4. ควรใช้ตัวแปรพารามิเตอร์ (Parameter) กับชุดคำสั่งเพื่อแก้ไขปัญหาย่อย หลีกเลี่ยงที่จะใช้ตัวแปรที่เป็นแบบโกลบอล และตัวพารามิเตอร์ควรมีการป้องกันหากมีการแก้ไขค่า
5. นำตัวแปรค่าคงที่ ( Constant Variable) มาใช้ จะช่วยให้การเขียนโปรแกรมมีความยืดหยุ่นมากขึ้นและอ่านเข้าใจง่าย
6. การเขียนโปรแกรมควรมีการจัดพื้นที่หรือบรรทัดว่างเพื่อให้อ่านสะดวก มีการย่อหน้าเพื่อจัดระดับของคำสั่งและมีลักษณะที่เป็นกรอบ
ทดสอบความถูกต้อง
1. การตรวจคำสั่ง (Validation) เป็นการตรวจสอบการเขียนโปรแกรมว่ามีความถูกต้องตามโครงสร้างของภาษาและทำงานตรงตามที่ต้องการหรือไม่
2. การตรวจสอบความจริง (Verification) เป็นการตรวจสอบขั้นตอนการทำงานของโปรแกรมว่ามีความถูกต้องและสอดคล้องกันหรือไม่
3. การทดสอบ (Testing) เป็นการทดสอบการทำงานว่าในแต่ละส่วนหรือชุดคำสั่งและการทำงานทั้งหมดในโปรแกรมมีความถูกต้องหรือไม่ มีการทดสอบแต่ละยูนิต ทดสอบการรวมกันของยูนิต
การดูแลระบบ
หลังจากการพัฒนาซอฟต์แวร์เสร็จสมบูรณ์และนำไปใช้งาน หากมีความต้องการที่จะเปลี่ยนแปลงแก้ไขเพื่อเติม หรือโปรแกรมมีปัญหาเกิดขึ้น จึงต้องมีการดูแลระบบ เพื่อนำกลับมาปรับปรุงแก้ไขใหม่ให้เป็นไปตามความต้องการ
ความหมายโครงสร้างข้อมูล/ชนิดข้อมูล
การทำงานของคอมพิวเตอร์จะมีการจัดการอย่างไรเพื่อให้ได้มาซึ่งข้อมูลข่าวสาร และสามารถนำมาใช้งานออกมาเป็นข้อมูลข่าวสารในรูปแบบต่าง ๆ ที่ทำความเข้าใจได้ แต่เนื่องจากคอมพิวเตอร์เป็นเพียงเครื่องจักรที่ไม่สามารถเข้าใจความหมายของข้อมูลข่าวสารได้เช่นเดียวกับคน จึงมีการกำหนดรูปแบบที่ใช้สื่อความหมายของข้อมูลข้าวสารให้คอมพิวเตอร์กับผู้ใช้งานเข้าในตรงกันเรียกว่า โครงสร้างข้อมูลหรือชนิดข้อมูล โดยแบ่งออกได้เป็นดังนี้

บิต (Bit)
เป็นหน่วยที่เล็กที่สุดในการทำงานของคอมพิวเตอร์ที่แสดงเป็นสถานะได้ 2 สถานะ คือ เปิดกับปิด จึงกำหนดเป็นการเก็บค่าได้ 2 ค่า คือ 0 กับ 1 เรียกว่าไบนารี่ดิจิต (Binary Digit)
ไบต์ (Byte)
เป็นการนำบิตหลาย ๆ บิตมาเรียงต่อรวมกันเพื่อกำหนดค่าได้มากขึ้น เช่น 3 บิต มาต่อเรียงกันจะทำให้เกิดสถานะที่ต่างกันคือ 000,001,010,100,011,010, และ 111 ก็จะได้เป็น 8 สถานะ เมื่อนำบิตมาเรียงต่อรวมกันเป็น 8 บิต เรียกว่าไบต์ มี 256 สถานะ และกำหนดเป็นโครงสร้างข้อมูลที่มีขนาดเล็กที่สุดที่ใช้งานได้ มีค่าตั้งแต่ 0 – 255 (00000000 – 11111111)
เลขจำนวนเต็ม (Integer)
เป็นการนำบิตหลาย ๆ บิตมาเรียงต่อรวมกันเพื่อกำหนดเป็นเลขจำนวนเต็ม ซึ่งได้เป็นระบบเลขฐานสอง โดยแต่ละบิตมีความหมายเป็นเลขยกกำลังสอง เช่น 20 = 1, 23 = 8 หรือ
21 + 22 +25 = 2+4+32 = 38 เลขที่ได้เป็นเลขจำนวนเต็มบวก ถ้าต้องการเป็นเลขจำนวนเต็มลบ จะต้องใช้วิธีการเรียกว่า One-complement Notation โดยการเปลี่ยนค่าของบิตที่เป็น 0 ให้เป็น 1 และค่าที่เป็น 1 ให้เป็น 0 เช่น 00100110 = 38 เมื่อสลับค่าจะได้บิต 11011001 = -38 ด้วยวิธีนี้ทำให้เก็บค่าได้ทั้งเลขจำนวนเต็มบวกและเต็มลบ ซึ่งมีบิตซ้ายสุดเป็นตัวกำหนดให้มีค่าบวกหรือลบเรียกว่า Sign Bit เมื่อนำบิตมาเรียงต่อกัน 16 บิตได้เป็นเลขจำนวนเต็มฐานสิบ มีอีกวิธีคือ Two-complement Notation โดยการบวกค่า 1 เข้าไปกับค่าของ One-complement Notation เช่นจาก 11011001 = -38 เมื่อบวก 1 จะได้ 11011010 = -38 เช่นกัน แต่วิธีนี้จำทำให้เก็บค่าได้มากกว่า คือ มีตั้งแต่ -2n-1 ถึง 2n-1 -1 ดังต่อไปนี้
1000000000000000 = -32768 0000000000000000 = 0
1000000000000001 = -32767 0000000000000001 = 1
1000000000000010 = -32766 0000000000000010 = 2
1111111111111101 = -3 0111111111111101 = 32765
1111111111111110 = -2 0111111111111110 = 32766
1111111111111111 = -1 0111111111111111 = 32767

เลขจำนวนจริง (Real Number)
เป็นรูปแบบของตัวเลขที่มีเลขทศนิยมเรียกว่า Floating – point Number โดยทำการแบ่งบิตออกเป็นสองส่วน โดยบิตที่อยู่ด้านซ้ายเก็บค่าเป็นตัวเลขจำนวนเต็ม เรียกว่า แมนทิสสา (Mantissa) การเก็บค่าเป็นแบบเดียวกับตัวเลขจำนวนเต็ม ส่วนบิตที่อยู่ด้านขวาเก็บค้าเป็นจำนวนหลักของ เลขทศนิยมเรียกว่า เอ็กซ์โพเนนท์ (Exponent) ในการเก็บจะใช้วิธี Two – complement Notation ซึ่งได้มาจากเลขยกกำลังของ 10 เช่น .01 = 10-2, 6.25 x 10-2 การเก็บค่าเลขทศนิยมจะใช้บิตจำนวน 32 บิต โดยแบ่งส่วนที่เป็นแมนทิสสาจำนวน 24 บิต และส่วนที่เป็นเอ็กซ์โพเนนท์จำนวน 8 บิต ดังนี้
00000000000000000000000000000000 = 0
00000000000000000000110000000011 = 12000
00000000000000000000010111111111 = 0.5
00000000000000000000010111111010 = 0.000005
11111111011010001001111111111110 = -387.53
ตัวอักษร (Character)
เป็นการเก็บค่าที่เป็นตัวอักษร แต่เนื่องจากคอมพิวเตอร์ไม่สามารถเข้าใจจึงใช้เลขจำนวนเต็มสื่อความหมายแทนโดยใช้บิตจำนวน 8 บิต เรียกว่า Bit String ซึ่งค่าตัวเลขที่ได้จะกำหนดเป็นตัวอกษรหนึ่งตัว ดังนั้นจะได้ตัวอักษรทั้งหมด 256 ตัวที่เรียกว่าเอ็บซีดิก (EBCDIC) เช่น
ตัวอักษรA จะมีค่า 01000001 = 65 หรือ B มีค่า 01000010 = 66 ประกอบด้วยอักษรตัวเล็ก ตัวใหญ่ ตัวเลข และตัวอักษรพิเศษ และที่ใช้เพียง 7 บิตเรียกว่าวหัสแอสกี (ASCII Code) ใช้ครึ่งเดียวของเอ็บซีดิกแต่การทำงานรวดเร็วกว่า เมื่อใดที่นำตัวอักษรหลาย ๆ ตัวมาเรียงต่อกันก็จะได้เป็นข้อความ เช่น AB จะได้เป็น 0100000101000010 หากต้องการเก็บจำนวนรูปแบบของตัวอักษรมากกว่านี้ก็สามารถทำได้โดยการเพิ่มจำนวนบิตเข้าไป ซึ่งขึ้นกับสถาปัตยกรรมของคอมพิวเตอร์จะรับได้หรือไม่ เช่นใช้ 10 บิตก็จะได้ตัวอักษร 1024 รูปแบบ
โครงสร้างข้อมูลเบื้องต้นและโครงสร้างข้อมูลนามธรรม
จากรูปแบบต่าง ๆ ของส่วนที่เป็นข้อมูลข่าวสาร คอมพิวเตอร์ไม่สามารถจะให้ความหมายได้ว่าคืออะไร แต่เมื่อนำการจัดการให้มีการทำงานที่เป็นรูปแบบตามที่กำหนดก็จะสามารถสื่อความหมายขึ้นมาได้ ด้วยกระบวนการจัดการแบบนี้จะเรียกว่าโครงสร้างข้อมูลหรือชนิดข้อมูลและด้วยวิธีการดังกล่าวจึงนำไปใช้ในการแก้ปัญหาต่าง ๆได้

โครงสร้างข้อมูลมีส่วนสำคัญในระบบคอมพิวเตอร์ ตัวแปรทุกตัวต้องมีการกำหนดชนิดข้อมูลซึ่งอาจเปิดเผยชัดเจน หรือปิดบังไว้ โครงสร้างข้อมูลเหล่านี้จึงมีลักษณะทางตรรกะ แต่ในทางกายภาพ อาจมีความแตกต่างกัน โครงสร้างข้อมูลสามารถแบ่งออกเป็นแต่ละประเภทดังในรูปที่ 1.1 ซึ่งแบ่งตามลักษณะวิธีการจัดเก็บข้อมูล
โครงสร้างข้อมูลเบื้องต้น โครงสร้างข้อมูล
เรียบง่าย โครงสร้างข้อมูลซับซ้อน การจัดการแฟ้มข้อมูล
เชิงเส้น ไม่เป็นเชิงเส้น
ไบนารี N-อาร์เรย์
เลขจำนวนเต็ม อาร์เรย์ สแตก ไบนารีทรี กราฟ แฟ้มข้อมูลลำดับ
เลขทศนิยม สตริง คิว ไบนารีเสิร์ชทรี ทรี แฟ้มข้อมูลโดยตรง
บูลีน เรคคอร์ด ลิ้งลิสต์ เสิร์ชทรี M-ทาง แฟ้มข้อมูลลำดับเชิงดัชนี
ตัวอักษร บีทรี แฟ้มข้อมูลหลายคีย์
บี*-ทรีมบีพลัว-ทรี
ทราย
รูปที่ 1.1 ประเภทของโครงสร้างข้อมูล
1. โครงสร้างข้อมูลเบื้องต้น (Primitive Data Structure) เป็นชนิดข้อมูลที่ไม่มีโครงสร้างข้อมูลอื่นมาเป็นส่วนประกอย เมื่อต้องการเก็บค่าสามารถเรียกใช้งานได้ทันที บางครั้งเรียกว่าชนิดข้อมูลพื้นฐาน (Base Type) หรือสร้างมาให้ใช้ด้วยภาษานั้น ๆ
ส่วนโครงสร้างข้อมูลแบบอื่น ๆ จะมีโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ เมื่อต้องการใช้จะต้องกำหนดรูปแบบรายละเอียดโครงสร้างขึ้นมาก่อนเรียกว่าข้อมูลชนิดผู้ใช้กำหนด
(Uses-defined Type) ดังนี้
2. โครงสร้างข้อมูลแบบเรียบง่าย (Simple Data Structure) จะมีสมาชิกที่เป็นโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ มีรูปแบบง่าย ๆ ไม่ซับซ้อน สามารถทำความเข้าใจและสร้างขึ้นมาใช้งานได้ง่าย
3. โครงสร้างข้อมูลเชิงเส้น (Linear Data Structure) เป็นโครงสร้างที่ความซับซ้อนมากขึ้น ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงต่อกันเป็นแนวเส้น

4. โครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) เป็นโครงสร้างที่มีความซับซ้อนเช่นกัน ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงกันในรูปแบบไบนารี่ ที่จัดเรียงสมาชิกมีการแยกออกเป็นสองทาง และแบบ N- อาร์เรย์ ที่จัดเรียงสมาชิกมีการแยกออกได้หลายทางหลายรูปแบบไม่แน่นอน
5. โครงสร้างการจัดการแฟ้มข้อมูล (File Organization) เป็นโครงสร้างสำหรับนำข้อมูลเก็บไว้ในหน่วยความจำสำรอง โดยข้อมูลจะอยู่ในรูปแบบโครงสร้างข้อมูลอื่น และมีวิธีการจัดการโดยการนำโครงสร้างข้อมูลอื่น ๆ มาช่วย
โครงสร้างข้อมูลต่าง ๆที่กล่าวมาอาจต้องมีการควบคุมการทำงานที่เกี่ยวข้องกับข้อมูลและส่วนที่มาเกี่ยวข้องให้เป็นไปตามที่ต้องการเรียกว่า โครงสร้างข้อมูลนามธรรม ลักษณะโครงสร้างจะแบ่งออกเป็น 2 ส่วน คือ ส่วนข้อมูลและส่วนปฏิบัติการ โดนภายในจะมีรายลเอียดการทำงานต่าง ๆ ประกอบด้วยโครงสร้างการจัดเก็บข้อมูลและอัลกอริทึม เมื่อใดที่เรียกใช้งานโครงสร้างนามธรรมในส่วนรายละเอียดการทำงานจะไม่ถูกเกี่ยวข้องหรือมีผลกระทบโดยถูกปิดบังไว้ จะเห็นว่าโครงสร้างข้อมูลซับซ้อนจะเป็นโครงสร้างข้อมูลนามธรรมที่ต้องมีส่วนการจัดเก็บข้อมูลและส่วนปฏิบัติการ
โครงสร้างข้อมูลกับภาษาเขียนโปรแกรม
ภาษาเขียนโปรแกรม (Programming Language) ช่วยให้ผู้เขียนโปรแกรมสามารถกำหนดโครงสร้างข้อมูลที่มีความหมายให้กับตำแปร เนื่องจากตัวแปรเหล่านี้ต้องเก็บค่าตามลักษณะของโครงสร้างข้อมูลที่ได้กำหนดมาและส่วนของการปฏิบัติการที่ช่วยให้การทำงานกับโครงสร้างข้อมูลมีความถูกต้อง ภาษาเขียนโปรแกรมหลายภาษาจะมีแนวทางที่แตกต่างกันในการกำหนดโครงสร้างข้อมูลมาให้ใช้ เช่น ภาษาซี(C) อนุญาตให้โครงสร้างข้อมูลตัวอักษรกับเลขจำนวนเต็มสามารถใช้ร่วมกันและคำนวณได้ ภาษาปาสคาล (Pascal) จะต้องประกาศตัวแปรอย่างชัดเจนว่ากำหนดโครงสร้างข้อมูลเป็นแบบใด ขณะที่ภาษาฟอร์แทรน(Fortran) เป็นการประกาศปิดบังไว้จึงไม่ต้องกำหนดโครงสร้างข้อมูลให้กับตัวแปร
1. อธิบายลักษณะของอาร์เรย์หนึ่งมิติเป็นอย่างไร และมีการใช้งานอย่างไร
ตอบ เป็นตารางที่มีเพียงแถวเดียว การใช้งานจะใช้อ้างไปยังตำแหน่งของแต่ละสมาชิกในอาร์เรย์ซึ่งมีค่าเป็นลำดับ
1. อธิบายลักษณะของอาร์เรย์สองมิติเป็นอย่างไร และมีการใช้งานอย่างไร
ตอบ เป็นตารางที่มีทั้งแถวและคอลัมน์ การใช้งาน นิยมใช้กับการวนลูปที่ซ้อนกัน 2 ลูป
1. อธิบายเหตุใดจึงต้องมีการกำหนดให้อาร์เรย์สามารถมีได้หลายมิติ
ตอบ เพราะมีการสร้างอาร์เรย์อาจเป็น 3 มิติ 4 มิติ หรือมากกว่านั้นเรียกว่า อาร์เรย์หลายมิติหรือ N- มิติ ดัชนีและช่วงจำนวนสมาชิกก็จะเพิ่มมากขึ้นตามจำนวนมิติอาร์เรย์
1. ยกตัวอย่างลักษณะการใช้อาร์เรย์ในภาษาซีและภาษาปาสคาลเป็นอย่างไร
ตอบ

5. ถ้าต้องการเก็บข้อมูลในแต่ละข้อต่อไปนี้โดยใช้เป็นอาร์เรย์จะต้องกำหนดการประกาศขึ้นมาใช้งานในภาษาซีอย่างไร
(a) เกรดที่ได้ของ นศ. จำนวน 50 คน
ตอบ

(b) เกรดที่ได้ในแต่ละวิชาเรียนจำนวน 6 วิชา ของ นศ. จำนวน 30 คน
ตอบ

(c) ยอดขายของสินค้า 10 ชนิด ของแต่ละเดือนใน 1 ปี
ตอบ

(d) จำนวนเงินซื้อสินค้าของลูกค้าจำนวน 5 คน จากแต่ละสินค้า 10 ชนิด ในแต่ละเดือน
ตอบ

6. อธิบายการจัดเก็บอาร์เรย์ในหน่วยความจำแบบลำดับแถวสำคัญมีลักษณะอย่างไร
ตอบ เก็บสมาชิกทุกตัวของแถวแรกก่อนจากนั้นเก็บแถวที่สองและสามไปเรื่อยๆ
1. สมมุติให้ชนิดข้อมูล Integer มีขนาด 2 ไบต์ ชนิดข้อมูล Char มีขนาด 1 ไบต์ และชนิข้อมูล Real ขนาด 4 ไบต์ จงบอกขนดพื้นที่หน่วยความจำของอาร์เรย์ในแต่ละข้อต่อไปนี้มีจำนวนกี่ไบต์
(a) Array[1:10] of Real
ตอบ 40 ไบต์
(b) Array[-5:5] of char
ตอบ 5 ไบต์
(c) Array [0:4,0:6] of Integer
ตอบ 32,128 ไบต์
(d) Array [0:3,1:2,0:6] of Integer
ตอบ 164,128 ไบต์
1. ถ้ากำหนดอาร์เรย์ A[0:5,1:8] โดยมีตำแหน่ง Address เริ่มต้นที่ 2000 และแต่ละสมาชิกเป็น 6 ไบต์
2. จงหาตำแหน่งแอดเดรสของสมาชิก A[3,5] เมื่อเก็บแบบลำดับแถวสำคัญและแบบลำดับคอลัมน์สำคัญ
ตอบ สูตร B+(I-L1)*(U2-1+1)*s+(J-1)*s
2000+(3-1)*(8-1+1)*6+(5-1)*6
2000+2*8*6+4*6
2000+186+4
2576
สูตร B+(J-1)*(U1-L1+1)*s+(I-L1)*s
2000+(5-1)*(5-1+1)*6+(3-1)*6
2000+4*5*6+2*6
2000+720+2
2156
(b) จงหาตำแหน่งแอดเดรสของสมาชิก A[6,2] เมื่อเก็บแบบลำดับแถวสำคัญ
ตอบ สูตร B+(I-L1)*(U2-1+1)*s+(J-1)*s
2000+(6-1)*(8-1+1)*6+(2-1)*6
2000+5*8*6+1*6
2000+240+6
2246
(c) จงหาตำแหน่งแอดเดรสของสมาชิก A[2,6] เมื่อเก็บแบบลำดับคอลัมน์สำคัญ
ตอบ สูตร B+(J-1)*(U1-L1+1)*s+(I-L1)*s
2000+(6-1)*(6-1+1)*6+(2-1)*6
2000+5*6*6+1*6
2000+180+6
2186
9. จากตัวอย่างโปรแกรมต่อไปนี้มีการแสดงผลข้อมูลในแบบลำดับแถวสำคัญ
for(i=0;i<5;i++){ for(j=0;j<8;j++) printf(“\n”); } ถ้าต้องการเปลี่ยนเป็นการแสดงผลข้อมูลในแบบลำดับคอลัมน์สำคัญจะต้องเขียนโปรแกรมเป็นอย่างไร ตอบ 10. เขียนโปรแกรมเพื่อเก็บค่าการแปลงอุณภูมิจากองศาเซลเซียสไปเป็นองศาฟาเรนไฮต์โดยใช้อาร์เรย์เก็บค่าที่ได้และมีสมาการแปลงค่าดังนี้ Celsius=5.0/9.0 (fahrenhiet-32) หลังจากคำนวรหาค่าเสร็จให้แสดงผลในรูปแบบตารางเปรียบเทียบค่าระหว่างเซลเซียสและฟาเรนไฮต์ดังต่อไปนี้ ตอบ ต้องกลับสูตรก่อน Celsius*9/5 +32= Fahrenheit 11. บ. แห่งหนึ่งมีการจ่ายค่าคอมมิชชั่นให้กับพนักงานชายโดยพนักงานแต่ละได้รับเงินเดือน 3,500 บาท รวมกับ 9% ของยอดขาย เช่น พนักงานคนหนึ่งมียอดขาย =30,000 บาท จะได้รับเงิน 3,500 + 9 % ของ 30,000 หรือ 6,200 บาท จงเขียนโปรแกรมเพื่อคำนวณหาว่ามีพนักงานขายกี่คนที่ได้รับเงินเดือนในแต่ละช่วงที่กำหนดไว้ดังนี้ 1) 3500 – 4499 5) 7500 – 8499 2) 4500 – 5499 6) 8500 – 9499 3) 5500 – 6499 7) 9500 และมากกว่า 4) 6500 – 7499 ตอบ ตอนที่ 2 1. Array ตอบ อาร์เรย์ โครงสร้างข้อมูลอาร์เรย์ 1. Random Access ตอบ การใช้งานอาร์เรย์เป็นการเข้าถึงแบบสุ่ม 1. Upper Bound ตอบ ค่าที่น้อยสุดและขอบเขตบน 1. Vector ตอบ ตารางที่มีเพียงแถวเดียว 1. Matrix ตอบ เป็นชื่อของอาร์เรย์ 2 มิติ 1. Two-dimension Away ตอบ อาร์เรย์ 2 มิติ 1. Multi- dimension Away ตอบ อาร์เรย์หลายมิติ 1. Base Location ตอบ ตำแหน่งเริ่มต้น 1. Row – major Order ตอบ ลำดับแถวสำคัญ 1. Programming language ตอบ ภาษาเขียนโปรแกรม 1. โครงสร้างข้อมูลสตริงมีชุดปฏิบัติการพื้นฐานอะไรบ้าง และมีขั้นตอนการทำงานอย่างไร ตอบ - ความยาวสตริง เป็นการบอกให้ทราบว่าสตริงตัวนั้นมีตัวอักษรหรือความยาวเท่าไหร่ จะกำหนดเป็นฟังก์ชัน Length - รวมสตริง เป็นการนำ 2 สตริงมารวมกันเป็นสตริงเดียว โดยนำตัวอักษรทั้งหมดของสตริงตัวหลังไปต่อท้ายสตริงตัวแรก - สตริงย่อย เป็นการคัดลอกตัวอักษรที่อยู่ติดกันบางส่วนของสตริงตัวที่สอง ให้กับสตริงตัวแรกขั้นตอนการทำงาน จะรับค่าเป็นข้อความเข้ามาทางคีย์บอร์ดและนำออกแสดงผลในรูปแบบต่างๆ 1. จงสร้างชุดปฏิบัติการเพื่อแปลงตัวอักษรทุกตัวให้เป็นอักษรตัวเล็กยกเว้นตัวอักษรตัวแรกให้เป็นตัวอักษรตัวใหญ่ ตอบ 1. จงสร้างชุดปฏิบัติการเพื่อเปรียบเทียบสองข้อความว่ามีตัวอักษรและลำดับเหมือนกันหรือไม่ ถ้าเหมือนกันให้ส่งค่ากลับมาเป็น 1 ถ้าไม่เป็นให้ส่งกลับเป็น 0 ตอบ 1. จงรวบรวมชุดปฏิบัติการทั้งหมดในภาษาซีที่ใช้จัดเก็บโครงสร้างข้อมูลสตริง ตอบ 1. อาร์เรย์ มีโครงสร้างข้อมูล char 2. การค้นหาตัวอักษรบางส่วนในสตริง 3. การแทรกตัวอักษรบางส่วนในสตริง 4. การลบข้อความบางส่วนออกจากสตริง 5. การเก็บข้อมูลโดยใช้โครงสร้างข้อมูลสตริงจะมีลักษณะรูปแบบและความหมายที่แตกต่างกัน เช่น ชื่อ นามสกุล จงยกตัวอย่างลักษณะรูปแบบของข้อมูลมา 5 แบบที่ใช้ในโครงสร้างข้อมูลสตริงในการเก็บค่าและเหตุใด ตอบ 6. โครงสร้างข้อมูลเรคคอร์ดเพื่อจัดเก็บข้อมูลต่อไปนี้ และกำหนดชนิดข้อมูลตามความเหมาะสม ตอบ อาร์เรย์ประกอบด้วยสมาชิกทุกตัวมีโครงสร้างข้อมูลชนิดเดียวกันส่วนเรคคอร์ดประกอบด้วยสมาชิกแต่ละตัวที่สามารถมีโครงสร้างข้อมูลชนิดใดก็ได้ไม่จำเป็นต้องเหมือนกัน 1. จงออกแบบโครงสร้างข้อมูลเรคคอร์ดเพื่อจัดเก็บข้อมูลดังต่อไปนี้ และกำหนดชนิดข้อมูลตามความเหมาะสม A รายการสมุดโทรศัพท์ B รายละเอียดของรถยนต์ เช่นผู้ผลิต รุ่นสี C รายละเอียดของหนังสือในห้องสมุดที่อยู่บนบัตรค้นหา เช่น ชื่อหนังสือ ชื่อผู้เขียน สำนักพิมพ์ D รายละเอียดของทีมฟุตบอลในลีก เช่น ชื่อทีม จำนวนที่แพ้ที่ชนะ ตอบ A) Strict Phone { Char Name [80]; Char Phone [80]; Char Address [80]; }; B) Strict Auto { Char Agent Name [80]; Char Model [80]; Char Curler [80]; }; C) Strict Library { Char Book Name [80]; Char Writer Name [80]; Char Pin [80]; }; D) Strict Football { Char Team Name [80]; Char Pea; Char china ; }; 1. จงออกแบบโครงสร้างข้อมูลเรคคอร์ดเมื่อต้องการเติมข้อมูลนักศึกษาประกอบด้วยรหัสนักศึกษาชื่อและนามสกุล ที่อยู่ เกรดเฉลี่ย (GPA) และเขียนโปรแกรมเพื่อใช้เก็บข้อมูล ตอบ Strut Student{ int ID_std char Name [80]; char Address [80]; float GPA; }; โปรแกรมเขียนได้ดังนี้ 1. จงออกแบบโครงสร้างข้อมูลเรคคอร์ดเมื่อต้องการเก็บข้อมูลการลงทะเบียนของนักศึกษาประกอบด้วยรหัสนักศึกษา รหัสวิชา เกรดที่ได้ และเขียนเป็นโปรแกรมเพื่อใช้เก็บข้อมูล struct Registration { int Id_std; Char subject [80]; float Grade; }; ตอบ เขียนโปรแกรมได้ดังนี้ ตอนที่ 2 1. Character ตอบ ตัวอักษรและสัญลักษณ์ 1. String Length ตอบ ความยาวสตริง 1. string Length ตอบ ความยาวสตริง 1. string Concatenation ตอบ ระเบียบที่เป็นโครงสร้างข้อมูล 1. fiord ตอบ เป็นสมาชิกในเรคคอร์ดเรียกว่าเขตข้อมูล 1. Qualification ตอบ แสดงคุณสมบัติ 1. stunt ตอบ โครงสร้างข้อมูลเรคคอร์ด ตามด้วยชื่อโครงสร้างข้อมูลตามด้วยชื่อสมาชิกแต่ละตัวพร้อมกำหนดโครงสร้างข้อมูลให้แต่ละตัว 1. Database ตอบ เรคคอร์ดหลายๆเรคคอร์ดท่เก็บข้อมูลที่มีลักษณะเดียวกันเป็นจำนวนมากๆ ตอนที่ 1 1.โครงสร้างข้อมูลคิวมีชุดปฏิบัติการอะไรบ้าง และมีขั้นตอนการทำงานอย่างไร ตอบ 1.CreateQueue() ใช้สร้างคิวใหม่ขึ้นมาใช้งาน 2.Insert(value,queue) ใช้เพิ่มค่าใหม่เก็บลงในคิวที่ใช้งานอยู่ 3.Remove (queue) ใช้ดึงค่าออกจากคิวที่ใช้งานอยู่และส่งค่า 4.isEmpty (queue) ใช้ตรวจสอบว่าคิวที่ใช้งานอยู่ว่างหรือไม่ การทำงานของคิว เมื่อมีค่าส่งมาเก็บเป็นตัวแรกก็จะอยู่ส่วนหน้า ค่าถัดมาก็จะต่อท้ายไปเรื่อยๆ จนตัวสุดท้ายคือ ส่วนหลัง หากมีการดึงค่าออกมาใช้ ค่าที่อยู่ส่วนหน้า จะถูกดึงออกมาก่อน ลักษณะที่ได้จึงเป็นลำดับการใช้งานทั่วไปและ เรียกว่า เข้าก่อนออกก่อน 2. จงแสดงภาพขั้นตอนการเก็บค่าลงในคิวเมื่อมีการใช้ชุดปฏิบัติการ Insert และ Remove ตามลำดับต่อไปนี้ Insert(‘A’) , Insert(‘B’) , Insert(‘C’) , Remove(), Insert(‘D’) , Remove() , Remove() , Insert(‘E’) , Insert(‘F’) ตอบ - เริ่มต้นสร้างคิว Q ขึ้นมาทำงาน CreateQueue(G) ได้เป็นคิวว่างไม่มีสมาชิก โดยตัวชี้ส่วนหน้าและท้ายยังไม่มีค่า -นำค่า A เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(A) ได้คิว Q=[A] ตัวชี้ Front=A,Rear=A A -นำค่า B เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(B) ได้คิว Q=[A,B] ตัวชี้ Front=A,Rear=B A B -นำค่า C เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(C) ได้คิว Q=[A,B,C] ตัวชี้ Front=A,Rear=C A B C -ต้องการดึงค่าออกมาโดยใช้ Remove() ได้คิว Q=[B,C] ตัวชี้ Front=B,Rear=C B C -นำค่า D เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(D) ได้คิว Q=[B,C,D] ตัวชี้ Front=B,Rear=D B C D -ต้องการดึงค่าออกมาโดยใช้ Remove() ได้คิว Q=[C,D] ตัวชี้ Front=C,Rear=D C D -ต้องการดึงค่าออกมาโดยใช้ Remove() ได้คิว Q=[D] ตัวชี้ Front=D,Rear=D D -นำค่า E,F เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert(E) , Insert(E) ได้คิว Q=[D,E,F] ตัวชี้ Front=D,Rear=F D E F 3.จงอธิบายลักษณะความแตกต่างระหว่างโครงสร้างข้อมูลคิวกับโครงสร้างข้อมูลสแตกเป็นอย่างไร ตอบ -โครงสร้างข้อมูลคิว มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าแทรกเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่า ส่วนหน้า - โครงสร้างข้อมูลสแตก มีข้อกำหนดให้ชุดปฏิบัติการ สามารถเพิ่มและลบรายการเพียงด้านเดียว ซึ่งเป็นด้านบนสุดของสแตก เรียกว่า ตัวชี้สแตก 4.จากปัญหาการสลับตู้รถไฟในรูปที่ 5.2 ถ้ากำหนดตู้รถไฟเป็น A , B , C ตามลำดับ อยากทราบว่าการสลับตู้รถไฟมีได้กี่รูปแบบที่เป็นไปได้จากทุกรูปแบบทั้งหมดในการสลับ(Permutation) และมีแบบใดบ้าง ตอบ มีรูปแบบเดียว คือ เข้าก่อนออกก่อนหรือเข้าก่อนได้บริการก่อน 5.ถ้าให้ Q เป็นคิวที่เก็บค่าเป็นตัวอักษรได้ไม่เกิน 5 ค่า หากมีการทำงานตามลำดับในแต่ละข้อต่อไปนี้ คิวจะมีลักษณะเป็นอย่างไรและมีข้อผิดพลาดเกินขึ้นอย่างไรหรือไม่ a) Insert(‘A’,Q); Insert(‘B’,Q); Insert(‘C’,Q); ch=Remove(Q); Insert(‘ch’,Q); a) ch= ‘M’; for(i=0; i<3; i++) { Insert(ch,Q); Insert(ch+1,Q); ch=Remove(Q); ตอบ 6.จงเขียนโปรแกรมสร้างคิว Q ที่เก็บค่าตัวเลขได้สูงสุด 5 ค่า พร้อมกับชุดปฏิบัติการต่าง ๆ และทดสอบการใช้งาน ตอบ 7.จงอธิบายคิววงกลมมีลักษณะและการใช้งานเป็นอย่างไร ตอบ มีลักษณะเป็นเชิงเส้นรูปวงแหวน การใช้งาน -อัลกอริทึมการเพิ่มค่าเก็บลงในคิว 1.กำหนดค่าให้กับ nuwRear เท่ากับ (Rear+1) mod maxSize 2.ถ้าค่าของ newRear ไม่เท่ากับค่าของ Front ทำดังนี้ 2.1 ทำการนำค่าเก็บลงในคิวยังตำแหน่งที่ Rear+1 2.2 กำหนดค่าของ Rear ให้เท่ากับค่าของ newRear ไม่เช่นนั้น จะแจ้งกลับมาว่าคิวว่าง -อัลกอริทึมการดึงค่าออกจากคิว 1.ถ้าคิวไม่ว่าง ทำดังนี้ 1.1 ทำการดึงค่าที่อยู่ในคิวยังตำแหน่งที่ Front ออกมาให้ 1.2 เพิ่มค่าให้กับ Front เท่ากับ (Front r+1) mod maxSize ไม่เช่นนั้น จะแจ้งกลับมาว่าคิวว่าง 8.จงอธิบายคิวลำดับความสำคัญมีลักษณะและการใช้งานเป็นอย่างไร ตอบ ได้มีการจัดลำดับ 2 แบบ คือ ให้ความสำคัญจากค่าน้อยไปหาค่ามาก และจากค่ามากไปหาค่าน้อย โดยส่วนใหญ่จะใช้ค่ามากกว่าในการเพิ่มสมาชิกเข้ามาในคิวไปจำเป็นต้องเข้ามาตามลำดับ แต่การนำออกจะต้องตามลำดับ ดังนั้น การลบสมาชิกจากคิวจะมีการทำงาน 2 เรื่อง คือ หาสมาชิกที่สำคัญมากสุด ต้องเข้าไปเรียกใช้งานสมาชิกทุกตัว และเมื่อลบสมาชิกออกจากคิวในช่วงกลาง จะต้องมีการขยับสมาชิกตัวถัดไปมาอยู่แทน 9.จากข้อ 2 หากใช้คิวลำดับความสำคัญจะมีขั้นตอนการเก็บค่าเป็นอย่างไร ตอบ ตอนที่ 2 1.Rear ตอบ ส่วนหลัง 2.Queuing Theory ตอบ การนำหลักการของคิวมาใช้ 3.First-In-First-Out ตอบ เข้าก่อนออกก่อน 4.Queue Overflow ตอบ การล้นของข้อมูลในคิว 5.Modulo ตอบ การหารเหลือเศษ 6.Priority Queue ตอบ คิวลำดับความสำคัญ 7.Descending ตอบ จากค่ามากไปหาค่าน้อย 8.Job Control Block ตอบ คิวลำดับความสำคัญเป็นตัวควบคุมงาน บทที่ 6 โครงสร้างข้อมูลลิงค์ลิสต์ 1.ชุดปฏิบัติการของลิงค์ลิสต์มีอะไรบ้าง และมีขั้นตอนการทำงานอย่างไร ตอบ 1.Node(p) ส่งโหนดที่ถูกชี้ด้วยต้วแปรพอยเตอร์ P กลับมาให้ 2.Info (P) ส่งค่าในส่วนเก็บข้อมูลของโหนดที่ถูกชี้ด้วยตัวแปรพอยเตอร์ p กลับมาให้ 3.Next(P) ส่งพอยเตอร์ในส่วนขอบการเชื่อมต่อโหนดที่ถูกชี้ด้วยตัวแปรพอยเตอร์ P กลับมาให้ 2.จงอธิบายและแสดงลำดับขั้นตอนารเพิ่มโหนดใหม่ไว้ที่ท้ายของลิ้งค์ลิสต์ ตอบ 1.สร้างโหนดใหม่โดยให้ New ชี้ไปยัง Node ใหม่ :Next(New)=Null 2.Info (New)=Data เช่นให้เท่ากับ 5 3.P= ชี้ไปยัง Node สุดท้าย 3.จงอธิบายและแสดงลำดับขั้นตอนการลบโหนดออกจากลิ้งค์ลิสต์ ตอบ 1. P=first คือ P มาชี้ที่ Node แรก 2.First=Net(First) ให้ First ไปชี้ที่ Node ที่ 2 3.Free(P) ทำการลบ Node ที่ P ชี้อยู่ 4.จงอธิบายลิงค์ลิสต์วงกลมมีลักษณะและการใช้งานเป็นอย่างไร ตอบ วิธารที่ทำให้สามารถวิ่งจากโหนดหนึ่งไปยังอีกโหนดอื่น ๆ ได้ในลิ้งค์ลิสต์โดยให้ตัวชี้ของโหนดสุดท้ายชื่อในค่า Null ที่ให้ชี้กลับไปยังโหนด แรกแทน การใช้งาน มีการเพิ่มหัวรายการเข้ามาในตอนต้นหรือท้ายลิ้งค์ลิสต์วงกลมการวิ่งไปแต่ละโหนดจะทราบได้ว่าจุดสิ้นสุดอยู่ตรงไหนโดยใช้โหนดหัวรายการ 5.จงอธิบายลิ้งลิสต์สองทางมีลักษณะและการใช้งานเป็นอย่างไร ตอบ เป็นลิ้งค์ลิสต์ที่มีตัวชี้สองทางทั้งซ้ายและขวา การทำงานของลิ้งค์ลิสต์อาจต้องวิ่งไปยังโหนดต่างๆ ในลิ้งค์ลิสต์โดยการถอยหลังกลับไปยังโหนดก่อนหน้าหรือลบแต่โหนด 6.จงสร้างลิ้งค์ลิสต์ทางเดียวทำหน้าที่เป็นสแตกพร้อมชุดปฏิบัติการ และมีลำดับขั้นการทำงานดังนี้ Push(‘X’), Push(‘L’), Push(‘R’), Pop(), Push(‘A’), Pop(), Pop(), Push(‘Q’) ตอบ 7.การใช้ลิ้งค์ลิสต์เป็นสแตกและคิวจะแตกต่างจากการใช้อาร์เรย์อย่างไร ตอบ โครงสร้างข้อมูลกับอาร์เรย์ จำกัดค่ายของสมาชิกที่ใส่ลงและจำกัดชนิดของข้อมูลส่วนโครงสร้างข้อมูลแบบลิงค์ลิสต์ที่เป็นสแตกและคิวจำนวนสมาชิกที่ใส่ลงไปไม่จำกัดจำนวน 8.จงเขียนชุดปฏิบัติการเพื่อนับจำนวนโหนดที่มีลิ้งค์ลิสต์ ตอบ 9.จงเขียนชุดปฏิบัติการเพื่อรวมสองลิ้งค์ลิสต์คือ A , B ไว้ที่ลิ้งลิสต์ คือ C โดยมีการสลับโหนดเป็นดังนี้ A={X1,X2,X3,..,Xn} และ {Y1 ,Y2 ,Y3,.., Yn}จะได้ C={X1,Y1,X2,Y2,X3,Y3,.., Xn, Yn} ตอบ ตอนที่ 2 อธิบายคำศัพท์ 1.Non-sequenial ตอบ รูปแบบไฟล์เรียงตามลำดับ 2.Node ตอบ สมาชิกแต่ละตัว 3.Homogenous ตอบ ชนิดเดียวกัน 4.Sequential Search ตอบ การค้นหาเรียงตามลำดับ 5.Memory Address ตอบ ตำแหน่งแอดเดรสในหน่วยความจำ 6.Predecessor ตอบ โหนดส่วนหน้า 7.Singly Linked List ตอบ ลิ้งค์ลิสต์ทางเดียว 8.Head Node ตอบ โหนดหัวรายการ 9.Josephus Problem ตอบ ปัญหาโจเซฟ 10.Symmetrically Liked List ตอบ ลิ้งค์ลิสต์สมมาตร 11.Circular Doubly Linked List ตอบ ลิ้งค์ลิสต์ 2 ทางวงกลม ตอนที่ 1 อธิบาย ข้อ 1 จงยกตัวอย่างฟังก์ชันที่ทำงานแบบรีเคอร์ซีฟ และลำดับการทำงานเป็นอย่างไร ตอบ power() ลำดับการทำงาน จะเริ่มเรียกตัวเองก่อน แล้วทำงานลงไปเรื่อยๆจนถึงกรณีพื้นฐาน จากนั้นถอยหลังกลับขึ้นมาตามทางเดิม ----------------------------------------------------------------------------------------- ข้อ 2 จากตารางที่ 7.5 เป็นตัวอย่างโปรแกรมการย้ายแผ่นจานจากเสา A ไปเก็บไว้ที่เสา B ในตอนสุดท้าย หากต้องการย้ายไว้ที่เสา C ในตอนสุดท้ายจะต้องแก้ไขโปรแกรมดังกล่าวอย่างไรและลำดับการย้ายแผ่นจานจะเป็นอย่างไร ตอบ ----------------------------------------------------------------------------------------------------- ข้อ 3 จงอธิบายรีเคอร์ซิฟโดยอ้อมมีลักษณะเป็นอย่างไร มีแบบใดบ้างและแตกต่างกันอย่างไร ตอบ มีการเรียกฟังก์ชันอื่นมาทำงานและเป็นการเรียกแบบลูกโซ่ที่ย้อนกลับมาเรียกฟังก์ชันแรก ซึ่งจะมี 2 ประเภท ได้แก่ 1. รีเคอร์ซิฟสองฝ่าย ซึ่งจะมีสองฟังก์ชันที่ต่างเรียกฟังก์ชันตรงข้ามมาทำงาน 2. รีเคอร์ซิฟอ้อมทั่วไป มีหลายฟังก์ชันเรียกต่อกับโดยฟังก์ชันสุดท้ายเรียกย้อนกลับมายังฟังก์ชันแรก ----------------------------------------------------------------------------------------------------- ข้อ 4 จงแสดงลำดับขั้นตอนี่เกิดขึ้นเมื่อมีการเรียกฟังก์ชันรีเคอร์ซิฟขึ้นมาทำงาน ตอบ การทำงานในคอมพิวเตอร์จะคอยดูเส้นทางการทำงานของโปรแกรมหรือโปรแกรมย่อยที่ถูกเรียกขึ้นมาทำงาน ดังนั้นก่อนโปรแกรมจะเริ่มทำงานจะมีการบันทึกเก็บข้อมูลข่าวสารเดิม ที่กำลังใช้งานอยู่ เมื่อจะนำกลับมาใช้ต่อไปหลังจากที่โปรแกรมทำงานสิ้นสุด โดยคอมพิวเตอร์มักจะจัดสรรพื้นที่หน่วยความจำ เมื่อมีโปรแกรมย่อยหนึ่งถูกขัดจังหวะจากโปรแกรมย่อยอื่น ก็จะมีการเก็บค่าของตัวแปรพารามิเตอร์ แอดเดรสถอยแล้ว และค่าอื่นๆของโปรแกรมที่ถูกขัดจังหวะหลังจากที่โปรแกรมย่อยทำงานเสร็จที่จะนำค่าต่างๆก่อนถูกขัดจังหวะกลับมาใช้งานต่อไป ----------------------------------------------------------------------------------------------------- ข้อที่ 5 จงอธิบายแอดติเวชั่นแรคคอร์ดคืออะไรมีความสำคัญอย่างไรต่อฟังก์ชั่นรีเคอร์ซิฟ ตอบ คือ การเก็บข้อมูลข่าวสาร มีความสำคัญคือ เก็บข้อมูลข่าวสารหรือค่าอื่นๆของโปรแกรมที่ถูกขัดจังหวะ เมื่อโปรแกรมย่อยทำงานเสร็จก็จะนำค่าต่างๆที่ก่อนที่จะถูกขัดจังหวะกลับมาใช้งานต่อไป ข้อที่ 6 พิจารณาจากฟังก์ชันรีเคอร์ซีฟต่อไปนี้ ข้อ 7. จากฟังก์ชันรีเคอร์ซีฟในข้อ 6 หากเปลี่ยนคำสั่งการเรียกฟังก์ชันRecur (ch-1);เป็น Recur (ch+1); แทนผลลัพธ์ได้จะเปลี่ยนไปจากเดิมเป็ฯอย่างไร ตอบ ข้อ 8 พิจารณาจากฟังก์ชันรีเคอร์ซีฟต่อไปนี้ ตอนที่ 2 1. Recursive Function ตอบ ฟังก์ชันรีเคอร์ซิฟ 1. Base Class ตอบ กรณีพื้นฐาน 1. Recursive Call ตอบ เรียกตัวเอง 1. Backtracking ตอบ การถอยกลับไปตามทางเดิน 1. Recursive Tree ตอบ ทรีรีเคอร์ซิฟ 1. Indirect Recursive ตอบ รีเคอร์ซิโดยอ้อม 1. Mutual Recursion ตอบ รีเคอร์ซิฟสองฝ่าย 1. Prototype ตอบ ล่วงหน้า 1. Permutation ตอบ การสับเปลี่ยนลำดับ 1. Activation Record ตอบ การเก็บข้อมูลข่าวสาร 1. การตรวจสอบความถูกต้องของอัลกอริทึมเพื่ออะไร และมีการตรวจสอบอย่างไร ตอบ เพื่อทดสอบกับข้อมูลที่หลากหลายยังไม่มีประสิทธิภาพเพียงพอเนื่องจากการทดสอบแสดงให้ทราบถึงข้อผิดพลาดที่ปรากฏอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่ปรากฏอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่ปรากฏจะไม่สามารถทราบได้ จึงนำการตรวจสอบแบบการอนุมาน ( Deductive) มาใช้เพื่อรับประกันว่าผลลัพธ์มีความถูกต้อง 1. การวัดผลประสิทธิภาพการทำงานของอัลกอริทึมมีแบบใดบ้าง ตอบ แบบแรก คือ การขอใช้พื้นที่ว่าง แบบที่สอง คือ ประสิทธิภาพเวลา 3. ปัจจัยที่มีผลกระทบต่อประสิทธิภาพการทำงานของอัลกอริทึมมีแบบใดบ้าง ตอบ 1.ขนาดข้อมูลที่รับเข้ามา 2.ชนิดของเครื่องคอมพิวเตอร์ 3.คุณภาพซอร์สโค้ดและคอมไพเลอร์ 4. กาวัดผลประสิทธิภาพการทำงานโดยพิจารณาจากการจัดการข้อมูลมีลักษณะการวัดผลอย่างไร ตอบ วัดประสิทธิภาพของอัลกอริทึมในกรณีแย่ที่สุด 1. การวัดผลประสิทธิภาพการทำงานโดยใช้เวลา จะมีวิธีใดบ้าง ตอบ 1.การคำนวณเชิงซ้อน 2.การจัดเรียงลำดับข้อมูล 6. จงอธิบายความหมายของเครื่องหมายบิ๊กโอ เครื่องหมายโอเมก้า และเครื่องหมายเตตตะ ตอบ เครื่องหมาย บิ๊กโอ จะหมายถึงเวลาการทำงานของ f (n) น้อยกว่าหรือเท่ากับ g (n) และได้ว่า g (n) เป็นขอบเขตด้านบนของ f (n) เครื่องหมายโอเมก้า จะหมายถึง เวลาการทำงานของ f (n) มากกว่าหรือเท่ากับ g (n) และได้ว่า g (n) เป็นขอบเขตด้านล่างของ f (n) เครื่องหมายเตตตะ จะหมายถึง เวลาการทำงานของ f (n) เท่ากับ g (n) 1. จงอธิบายบิ๊กโอของฟังก์ชันยกกำลังสองมีลักษณะเป็นอย่างไร ตอบ มีลักษณะก็ คือ หากต้องการให้เป็นเครื่องหมายบิ๊กโอต้องมีการแยก ออกเป็นหน่วย ๆ จากนั้นก็จะใช้หน่วยที่มากที่สุดเป็นลักษณะเชิงซ้อน 1. จากบางส่วนของอัลกอริทึมที่เขียนด้วยภาษาซีเป็นการบวกค่าของแมตทริก จงแสดงจำนวนการทำงานของแต่ละประโยคและบิ๊กโอเป็นอย่างไรในกรณีแย่ที่สุด for ( i = 0; i < n; i++); for( j = 0; j < n; j++); C [ i ] [ j ] = A[ i ] [ j ] + B[ i ] [ j ]; ตอบ 9. จากบางส่วนของอัลกอริทึมที่เขียนด้วยภาษาซีเป็นการคูณกันของแมตทริก จงแสดงจำนวนการทำงานของแต่ละประโยคและมีบิ๊กโอเป็นอย่างไรในกรณีแย่ที่สุด for ( i = 0; i < n; i++); for( j = 0; j < n; j++) { C [ i ] [ j ] = 0; for ( k = 0; k < n; k++) C [ i ] [ j ] = C [ i ] [ j ] + A[ i ] [ k ] + B[ k ] [ j ]; } ตอบ 10. จากบางส่วนของอัลกอริทึมที่เขียนด้วยภาษาซีเป็นการจัดเรียงลำดับข้อมูลแบบบับเบิลจงแสดงจำนวนการทำงานของแต่ละประโยคและมีบิ๊กโอเป็นอย่างไรในกรณีแย่ที่สุด for ( i = o; i < n - i; i ++) for (j = i; j < n - l; j ++) if ( x [ j ] > x [ j + l ] ){
temp = x [ j ];
x [ j + l = temp];
}
ตอบ
ตอนที่ 2
อธิบายคำศัพท์ ( หมายถึง การแปลคำศัพท์ ขยายความ อธิบายเพิ่มเติม ถ้ามีตัวอย่างให้ยกประกอบ ) ตอบแบบสั้น
1.Input Assertion
ตอบ ข้อมูลที่จะรับเข้ามาใช้งาน
2.Postcondition
ตอบ เงื่อนไขตอนท้าย

3.Intermediate Assertion
ตอบ การวินิจฉัยตอนกลาง
4.Loop Invariant
ตอบ การวนลูปสม่ำเสมอ
5.Sentinel–controlled Loop
ตอบ ตัวควบคุมจบการวนลูป
6.Euclid ’s Algorithm
ตอบ อัลกอริทึมของยูคลิด
7.Greatest Common Divisor
ตอบ เป็นค่าสูงสุดที่สามารถนำไปหารค่าสองค่าได้ลงตัว
8.Time Efficiency
ตอบ ประสิทธิภาพเวลา
9.Worst Case
ตอบ กรณีแย่ที่สุด
10.Step Count
ตอบ นับขั้นตอน
11.Asymptotic Complexity
ตอบ อัตราการเติบโตที่ไม่สิ้นสุด
12. Exponential Function
ตอบ ฟังชันก์เอ็กโปเนนเชียล
1.จงอธิบายลักษณะโครงสร้างเชิงแตกต่างจากโครงสร้างไม่เป็นเส้นอย่างไร
ตอบ โครงสร้างเชิงเส้นจะมีสมาชิกตัวถัดไปเพียงตัวเดียว แต่โครงสร้างเชิงเส้น จะมีสมาชิกตัวถัดไปหลายตัวโดยการแตกสาขา
2.จงอธิบายการสร้างไบนารีทรีโดยใช้อาร์เรย์เป็นอย่างไร
ตอบ การสร้างไบนารี่ทรีโดยใช้อาร์เรย์ จะได้ทรีที่มีจำนวนโหนดแน่นอน ตามขนาดของอาร์เรย์
3.ชุดปฏิบัตการของไบนารี่ทรีโดยใช้ลิ้งลิสต์มีอะไรบ้าง
ตอบ Info(p) เป็นการส่งค่าที่เก็บอยู่ในโหนดที่ p ชี้กลับมาให้
Left(p) เป็นการส่งโหนดลูกด้านซ้ายของโหนดที่ p ชี้กลับมาให้
Right(p) เป็นการส่งโหนดลูกด้านขวาของโหนดที่ p ชี้กลับมาให้
Father(p) เป็นการส่งโหนดพ่อของโหนดที่ p ชี้กลับมาให้

4.จงอธิบายการวิ่งตามเส้นทางในไบนารี่ทรีแบบพรี
ตอบ มีลักษณะการวิ่งในแนวลึกก่อน (Depth-first Order) มีอัลกิริทึมการทำงานในตาราง

5.จงอธิบายการวิ่งตามเส้นทางใน ทรีแบบโพสต์-ออเดอร์เป็นอย่างไร
ตอบ มีอัลกิริทึมการทำงานดังในตาราง

6.ในการวิ่งตามเส้นทางในทรีเมื่อผ่านโหนดไปแล้วไม่สามารถวิ่งถอยหลังกลับไปยังโหนดเหล่านั้นได้ ถ้าต้องการวิ่งถอยหลังกลับไปยังโหนดที่ผ่านมาได้ท่านคิดว่ามีวิธีการอย่างไรนำมาใช้
(วิธีเหล่านี้เรียกว่า Baktarcking)
ตอบ
7.พิจารณาจากไบนารี่ทรีต่อไปนี้

จงแสดงลำดับโหนดของทรีเมื่อมีการวิ่งตามเส้นทางในแบบพรี-ออเดอร์, แบบอิน-ออเดอร์
และแบบโพสต์-ออเดอร์
ตอบ

8. จงอธิบายยลักษณะไบนารี่เสิร์ชทรีเป็นอย่างไร
ตอบ ไบนารี่เสิร์ชทรี (Binary Search Tree, BST) เป็นไบนารี่ทรีที่รวบรวมค่าของ N เรคคอร์ดซึ่งเป็นคีย์ (Key) ตั้งแต่ K1 , K2 ,…….Kn โดยแต่ละโหนด Ri จะมี Ki เพียงคีย์เดียวสำหรับ i=1,2,….,N คีย์เป็นค่าสร้างความแตกต่าง (Identifier) ให้แต่ละโหนด
9. จากตัวอักษรในแต่ละข้อต่อไปนี้ เมื่อนำมาใส่ตามลำดับดังกล่าวจะเป็นไบนารีเสิร์ชทรี
ลักษณะอย่างไร
(a) A, C, R, E, S (b) R, A, C, E, S
(c) C, A, R, E, S (d) C, O, R, N, F, L, A, K, E, S
ตอบ
10. พิจารณาจากไบนารี่ทรีต่อไปนี้

จงสร้างไบนารี่ทรีขึ้นใหม่มีลักษณะเป็นอย่างไรหลังจากมีการทำงานในแต่ละข้อต่อนี้
(a) เพิ่ม 7 (b) เพิ่ม 7, 1, 55, 29 และ 19
(c) ลบ 8 (d) ลบ 8, 37 และ 62
(e) เพิ่ม 7, ลบ 8, เพิ่ม 59, ลบ 60, เพิ่ม 92, ลบ 50
ตอบ

ตอนที่ 2 อธิบายศัพท์
1. Nonlinear Data Structure
ตอบ โครงสร้างข้อมูลไม่เป็นเชิงเส้น
1. Branching Structure
ตอบ โครงสร้างข้อมูลแตกสาขา
1. General Tree
ตอบ ลักษณะพิเศษของทรีทั่วไป
1. In-degree
ตอบ จำนวนเอจหรือกิ่งเข้ามาหรือดีกรีเข้า
1. Parent Node
ตอบ โหนดพ่อ
1. Leaves Node
ตอบ โหนดปลาย
1. Complete Binary tree
ตอบ ไบนารี่ทรีสมบูรณ์
1. Tree Traversal
ตอบ การวิ่งตามเส้นในทางทรี
1. Depth-first Order
ตอบ การวิ่งในแนวลึกก่อน
10.Binary Search Tree
ตอบ ไบนารี่เสิร์ชทรี
11.Inorder Predecessor
ตอบ ค่าที่มากที่สุดในทรีย่อยด้านซ้าย
12.Successor Node
ตอบ โหนดซัดเซอร์เซส มาแทนในโหนดที่ต้องการลบ
ตอนที่ 1 อธิบาย
1. จงอธิบายความแตกต่างระหว่าง กราฟทั่วไปกับมัลติกราฟ เป็นอย่างไร
ตอบ กราฟทั่วไปจะเป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น แต่กราฟแบบมัลติลิสต์ ในโครงสร้างกราฟประกอบด้วยสองส่วยคือ ได้เร็กทอรี่ของโหนดและเซ็ตลิ้งค์สิสต์ของเอจ
2 .จงอธิบายลักษณะของกราฟทิศทางเป็นอย่างไร
ตอบ ลักษณะเฉพาะที่พิ่มเข้ามาในโครงสร้างข้อมุลกราฟทั่วไปได้เป็นกราฟทิศทาง ซ่งใช้หัวลูกศรกำหนดิศทางให้ต่เอจในกราฟ กราฟทิศทางจะมีดีกรีเข้า เป็นจำนวนเอจที่ชี้เข้ามาสิ้สสุดทีโหนดและมีดีกรีออก เป็จำนวนเอจที่ชี้ออกจากโหนด ดีกรีของโหนดในโหนดหนึ่ง
3.จงอธิบายการสร้างกราฟโดยใช้แมตทริกติดกันเป็นอย่างไร
ตอบ ให้กราฟ G มีเซ็ตของโหหนดเป็น VG และเซ็ตของเอจเป็น EG โดยกราฟมีออเดอร์เท่ากับ N ซึ่ง N >=1 แนวทางหนึ่งในการกำหนดเป็ฯกราฟโดยช้แมตทริกติดกัน เป็นอาร์เรย์ N-ต่อ –N เมื่อห้เป็นอาร์เรย์ A จะได้ว่า
1 if and only if edge (Vi,Vj)is in EG

0otherwise.
A(I,j)={

หมายความว่า หากมีเอจที่เชื่อมตจ่อกันระหว่างโหนด I กับ j ก็จะได้ A(I,j)=1ไม่เช่นนั้นมีค่าเป็น 0
4.จากกราฟทิศทาง ทั้งสองภาพต่อไปนี้จงสร้างภาพต่อไปนี้ จงสร้างอาร์เรย์ในรูปแบบแมตทริกติดกัน

ตอบ

1 2 3 4 5
4
1 0 1 1 1 1 1 1 1 0 1
2 1 1 1 0 0 2 1 1 1 0
3 1 0 0 1 0 3 0 1 1 1
4 1 1 0 1 1 4 1 0 1 1

5.จากอาร์เรย์ในรูแบบแมตทริกติดกันทั้งสองภาพต่อไปนี้ จงสร้างเป็กราฟทิศทาง

ตอบ

6.จากกราฟทิศทางในข้อ 4 จงสร้างกราฟแบบไดเร็กทอรี่โหนด
ตอบ

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

8.จากกราฟทิศทางต่อไปนี้ จงหาลำดับของโหนดจากการวิ่งผ่านในแต่ละข้อต่อไปนี้ (การ เลือกแต่ละครั้งอาจมีทางเลือกมากกว่าหนึ่งเส้นทาง)

a) วิ่งตามทางแนวกว้างก่อนโดยเริ่มต้นที่โหนด A
b)วิ่งตามทางแนวกว้างก่อนโดยเริ่มต้นที่โหนด F
c)วิ่งตามทางแนวลึกก่อนโดยเริ่มต้นที่โหนด A
d)วิ่งตามทางแนวลึกก่อนโดยเริ่มต้นที่โหนด F
ตอบ (a)
(b)
(c)
(d)

9. จงเขียนโปรแกรมวิ่งตามเส้นทางตามแนวลึกก่อนในกราฟทิศทางโดยใช้อาร์เรย์แบบแมตทริกติดกัน
ตอบ

10 .จากกราฟทิศทางในข้อ 8 จงหาเส้นทางที่สั้นที่สุดในแต่ละขอต่อไปนี้
(a) เส้นทางที่สั้นที่สุดจากโหนด A ไป E
(b)เส้นทางที่สั้นที่สุดจากโหนด A ไป H
(c)เส้นทางที่สั้นที่สุดจากโหนด G ไป C
(d)เส้นทางที่สั้นที่สุดจากโหนด J ไป A
ตอบ (a) A=>D=>C=>F=>J=>K=>I=>G=>H=>E
1. A=>D=>C=>F=>J=>K=>I=>G=>H
2. G=>H=>E=>C
3. J=>K=>I=>G=>H=>A

ตอนที่ 2 อธิบายคำศัพ์
1Edge เอจ โหนดของกราฟและเส้น
2 Vertice เวอร์ทิค โหนดของกราฟและเส้น3Connectd Graph กราฟต่อกัน
4 Acyclec กราฟที่ไม่มีเส้น
5 Out-degree ดีกรีเข้า
6 Wieghtc Edge เอจมีน้ำหนัก
7 Graph Traversal การวิ่งตามเส้นทางในกราฟ
8. Breath-first Search การค้นหาตามแนวกว้างก่อน
9. Reachability กราฟสามารถวิ่งไปโหนดอื่น ๆได้หรือไม่
10. Shotest Path Algorithm การหาเนทางที่สั้นที่สุด
11 Dijkstra’s Algorithm อัลกอริทึมของ ดิจสตรา
12. Routing Problem การค้นหาเส้นทางที่สั้นที่สุด
แบบฝึกหัดบทที่ 11
การจัดเรียงลำดับข้อมูล
ตอนที่ 1 อธิบาย
1. จงอธิบายความแตกต่างระหว่างการเรียงลำดับภายในกับการเรียงลำดับภายนอกเป็นอย่างไร
ตอบ
การจัดเรียงลำดับภายใน เป็นหลักการที่นำมาใช้เมื่อข้อมูลทั้งหมดที่รวบรวมไว้ มีขนาดที่เล็กเพียงพอที่จะเก็บไว้ และทำการเรียงลำดับภายในหน่วยความจำหลัก เวลาที่มักใช้ในการอ่านและเขียนเรคคอร์ดจะนำใช้พิจารณาถึงประสิทธิ์ภาพการเรียงลำดับข้อมูล แต่จะใช้เวลาในการเปรียบเทียบค่าของคีย์มาพิจารณา ส่วนการเรียงลำดับภายนอกเป็นหลักการที่นำมาใช้กับข้อมูลที่รวบรวมไว้เป็นจำนวนมากๆ ไม่สามารถเก็บไว้ในหน่วยความจำหลักได้หมดในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วยความจำหลักได้หมด ในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วยสำรอง
2. จงอธิบายการเรียงลำดับที่มีการเปรียบเทียบ O(n2) มีวิธีการแบบใดบ้าง
ตอบ
1. การเรียงลำดับแบบดับเบิ้ล (Bubble Sort)
2. การเรียงลำดับแบเลือก (Selection Sort)
3. การเรียงลำดับแบแทรก (Insertion Sort)
4. การเรียงลำดับแบบเชล์ (Shell Sort)
3. จงอธิบายการเรียงลำดับที่ไม่มีการเปรียบเทียบมีวิธีแบบใดบ้าง
ตอบ
1. การเรียงลำดับแบบนับจำนวน(Countinq Sort)
2. การเรียงลำดับแบบเรดิกซ์(Radix Sort)
4. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 60, 50, 70, 10, 40, 20 ถ้าต้องการเรียงลำดับแบบบับเบิลจากค่า มากไปหาน้อย ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ จะต้องใช้การจัดเรียงลำดับกี่รอบ และมีการสลับตำแน่งกันทั้งหมดกี่ครั้ง
ตอบ

5. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 30, 50, 70, 10, 40, 60 ถ้าต้องการเรียงลำดับแบบเลือกจากค่า มากไปหาน้อย ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ จะต้องใช้การจัดเรียงลำดับกี่รอบ และมีการสลับตำแน่งกันทั้งหมดกี่ครั้ง
ตอบ

6. จงอธิบายและแสดงขั้นตอนการเรียงลำดับแบบเชลล์เป็นอย่างไร
ตอบ
การจัดเรียงลำดับแบบเซล์หรือจำนวนลำดับแบบจำนวนเพิ่มๆค่อยลดลง (Diminishing Incremeny Sort) จะใช้เรียงลำดับแบบแทรกกับกลุ่มย่อยของค่าตามลำดับ กลุ่มย่อยเหล่านี้จะถูกเลือกใช้ในทิศทางพยายามให้ค่าถูกเรียงมากสุดก่อนที่จะใช้ การเรียงลำดับแบบแทรก ก็จะได้เวลาการทำงานที่ใช้การเรียงลำดับแบบแทรกในแต่ละรอบเกือบเป็นเส้นตรง
7. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 45, 20, 50, 30, 80, 10, 60, 70, 40, 90 ถ้าต้องการเรียงลำดับแบบรวดเร็ว ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ
ตอบ

8. จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 20, 15, 31, 10, 67, 50, 3, 49, 26 ถ้าต้องการเรียงลำดับแบบ
ฮีพ ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ
ตอบ

9.จากอาร์เรย์ x ที่มีค่าของสมาชิกเป็น 322, 715, 931, 250, 176, 845, 463, 192, 526 ถ้าต้องการเรียงลำดับแบบเรดิกซ์ ค่าของสมาชิกจะเป็นอย่างไรในแต่ละรอบ
ตอบ

10. จงอธิบายการเรียงลำดับและผสานแฟ้มข้อมูลเป็นอย่างไร
ตอบ

11. จงอธิบายและแสดงขั้นตอนการเรียงลำดับและผสานหลายขั้นตอนเป็นอย่างไร
ตอบ

12.จากอาร์เรย์ x มีค่าของสมาชิกเป็น 84, 19, 31, 25, 12, 53, 99, 68, 49, 77, 43, 30, 62, 11, 97, 80, 21, 37, 79, 55, 15, 58, 71, 23, 94, 66, 29, 63, 57, 81 จงเรียงลำดับและผสานแฟ้มข้อมูลโดยใช้การเรียงลำดับและผสานสมดุล ให้หนึ่งรันมี 3 เรคคอร์ดและมี 4 ม้วนเทป
ตอบ

ตอนที่ 2 อธิบายคำศัพท์
1. Internal Sorting
ตอบ การเรียงลำดับภายใน
2. Inplace Sorting
ตอบ พื้นที่หน่วยความจำของตนเอง
3. Stable Sort
ตอบ
4. Comparison Sort
ตอบ การเรียงลำดับมีการเปรียบเทียบ
5. Insertion Sort
ตอบ การเรียงลำดับแบบแทรก
6. Merge Sort
ตอบ การเรียงลำดับแบบผสมผสาน
7. Average Case
ตอบ กรณีเฉลี่ย
8. Binary Insertion Sort
ตอบ การเรียงลำดับแบบแทรกโดยแบ่งครึ่ง
9. Divide-and-Conquer
ตอบ วีธีการแบ่งและยึดรวมกัน
10. Logarithmic Time
ตอบ การทำงานที่ใช้เวลาเป็นลอกการิทึม
11. Tally Sort
ตอบ การเรียงลำดับแบบยอดรวมสูงสุด
12. Tournament Sort
ตอบ
13. Sort/Merge
ตอบ
14. M-way Natural Merge
ตอบ การผสมผสานธรรมดา M ทาง
15. Polyphase Merge
ตอบ การผสมผสานหลายขั้นตอน
ตอนที่ 1
1. จงอธิบายและแสดงขั้นตอนการค้นหาข้อมูลแบบลำดับเป็นอย่างไร
การค้นหาแบบลำดับ เป็นการค้นหาแบบเชิงเส้น (Linear Search)
ถ้าเป็น Array ไปที่ Index ที่ 0 แล้วตรวจสอบว่าใช่ค่าที่ต้องการค้นหาหรือไม่?
ถ้าเป็น Linked-List ไปที่ Node แรก แล้วตรวจสอบว่าใช่ค่าที่ต้องการค้นหาหรือไม่?
1.ตั้งแต่ i=0 จนถึง i){
if(key[i]==value)
return i;
}
return -1;
}
ค่าประมาณโดยเฉลี่ยของการค้นหาโดยใช้ Sequential จะเท่ากับ O(n) = n/2
2. จงอธิบายวิธีการปรับปรุงประสิทธิภาพการค้นหาข้อมูลแลแบบลำดับมีแบบต่าง ๆ เป็นอย่างไร
การปรับปรุงประสิทธิภาพของ Algorithm นี้จะทำได้โดย
1.ถ้าค่าใดถูกค้นหาบ่อย ๆ ให้ย้ายไปไว้ค่าแรก ๆ (Move to the Front)
2.การสลับตำแหน่ง ตัวใดถูกค้นหาก็ให้ขยับตำแหน่งที่อยู่ก่อนหน้า (Transposition)
3.นับจำนวนการค้นหา (Count)
4.จัดเรียงลำดับ (Sort)
3. จงเขียนโปรแกรมค้นหาข้อมูลแบบลำดับและแจ้งว่าพบที่ลำดับเท่าไรหรือไม่พบโดยใช้การค้นหาค่าในแต่ละข้อต่อไปนี้ และทดสอบกับอาร์เรย์ X ที่มีค่าของสมาชิกเป็น61,29,84,33,79,67,24,37,99,58,31,81,12,49,53,77,19,97,67,15,57,84,43,23,94,21,54,72,67,12
(a) ถ้าการค้นหาไม่พบค่าที่ต้องการ
(b) ถ้าการค้นหาพบค่าที่ต้องการและมีค่าเดียวในอาร์เรย์
(c) ถ้าการค้นหาพบค่าซ้ำกันและค่าที่ต้องการค้นหาคือค่าแรก
(d) ถ้าการค้นหาพบค่าซ้ำกันและค่าที่ต้องการคือทุก ๆ ค่า
4. จงอธิบายความแตกต่างระหว่างการค้นหาข้อมูลแบแบ่งครึ่งกับการค้นหาข้อมูลแบบสอดแทรกเป็นอย่างไร
ข้อมูลจะอยู่ในลักษณะของ Binary Tree
การค้นหาก็ไปที่ Root ของ Tree แล้วตรวจสอบว่า Info ของ Root ใช่สิ่งที่ต้องการค้นหาหรือไม่
ถ้าใช่ก็นำค่าไปใช้แล้วหยุดการค้นหาทันที แต่ถ้าไม่ใช่ให้ตรวจสอบว่า "สิ่งที่ค้นหา น้อยหรือมากกว่า info ของ Root Node"
ถ้าน้อยกว่า ก็จะไปตรวจสอบทางซ้ายของ Root ต่อ (ซึ่งหมาความว่า ทางขวาก็ตัดทิ้ง) และถ้ามากกว่า ก็จะไปตรวจสอบทางขวา
ของ Rootต่อ (ซึ่งหมายความ ทางซ้ายก็ตัดทิ้ง)
ส่วนการค้นหาแบบสอดแทรก ซึ่งเป็นการค้นหาตำแหน่งโดยการประมาณ
5. จงแสดงขั้นตอนการค้นหาคำ Software ในข้อความต่อไปนี้โดยใช้การค้นหาของ Boyer-Moore A Complete Computer System’s four Parts: Hardware, Software, Users, and Data.
6. จงอธิบายการค้นหาภายนอกแบบลำดับและแบบการเข้าถึงโดยตรงมีความแตกต่างกันอย่างไร
การเข้าถึงแบบลำดับ เป็นการค้นหาเรคคอร์ดที่ต้องใช้วิธีการเข้าถึงอย่างเป็นลำดับและจัดเก็บเรคคอร์ดลงในแฟ้มข้อมูล และผ่านทีละเรครอร์ดถัดไปเรื่อย ๆ จนกระทั่งพบเรคคอร์ดที่ต้องการหรือไม่พบเมื่อไปถึงส่วนสุดท้ายของแฟ้มข้อมูล
ส่วนการเข้าถึงโดยตรงหรือการเข้าถึงโดยการสุ่ม จะค้นหาเรคคอร์ดที่อ้างโดยตรงไปยังตำแหน่งของเรคคอร์ดที่ต้องการในแฟ้มข้อมูล โดยใช้ดัชนี ซึ่งมีตัวชี้วัดเป็นแอดเดรสของเรคคอร์ดที่ต้องการ
7. จงอธิบายการใช้แฮชฟังก์ชันแบบการพับทบกันมีวิธีแบบใดบ้าง
การพับทบแบบแบ่งเขต ถ้าข้อมูลเป็น 123456789
1
2345
9876
การพับทบแบบเลื่อนลง ถ้าข้อมูลเป็น 123456789
1
2345
6789
8. การแก้ไขปัญหาชนกันหมายถึงอะไร และมีวิธีการแบบใดบ้าง
เนื่องจากแฮชฟังก์ชันทำการแมพค่าของคีย์จากพื้นที่ขนาดใหญ่ไปเป็นพื้นที่ตำแหน่งในตารางแฮชขนาดเล็กทำให้เกิดการชนกันที่มีค่ามากกว่าหนึ่งอ้างไปยังตำแหน่งเดียวกัน การแก้ไขอาจใช้แฮชฟังก์ชันที่สามารถกระจายค่าไม่ให้ชนกันหรือเพิ่มตารางแฮชให้มากขึ้น แต่ก็ช่วยให้ลดน้อยลงเท่านั้น มี 3 วิธีคือ
1. การเปิดแอดเดรส
2. การต่อเป็นลูกโซ่
3. การใช้พื้นที่บักเก็ต
9. จงสร้างตารางแฮชที่เก็บได้ 9 ค่า โดยใช้วิธีการหารเหลือเศษและแก้ไขปัญหาการชนกันด้วยวิธีการเปิดแอดเดรสจากค่าของคีย์ที่เพิ่มเข้ามาตามลำดับคือ 25,98,30,66,49,14,78,58
10. จงอธิบายวิธีการใช้บี-ทรีในการค้นหาข้อมูลเป็นอย่าไร
แต่ละโหนดเก็บค่าของคีย์ไม่น้อยกว่าครึ่งของทั้งหมด ความสูงของทรีมีระดับไม่มาก และบี-ทรีเป็นทรีสมดุล ต่างจากไบนารี่เสิร์ชทรีและทรีค้นหาหลายทางที่ไม่สมดุล ส่วนทรีเอวีแอล (AVL Tree) ก็เป็นการแก้ปัญหาความไม่สมดุลแบบบนลงล่าง (Top-Down) โดยการหมุนทรีให้ความสูงของทรีย่อยใกล้เคียงกันมากที่สุดและมีค่าใช้จ่ายสูง สำหรับบี-ทรีจะแก้ปัญหาแบบล่างขึ้นบน (Button-Up) โดยเริ่มที่โหนดปลายกลับขึ้นไปยังรูทโหนด
11. จากบี-ทรีในรูปที่ 12.20 ถ้ามีการเพิ่มคีย์คือ 31,57,44,28,40,96 เข้ามาตามลำดับจะได้ภาพของบี-ทรีมีการเปลี่ยนแปลงอย่างไรเมื่อเพิ่มทีละค่า
ตอนที่ 2
1. Binary Search
การค้นหาแบบแบ่งครึ่ง
1. Text Searching
การประมวลผลเพื่อค้นหาคำในข้อความ
1. Pattern Matching
การค้นหารูปแบบเหมือนกัน
1. External Searching
การค้นหาภายนอก
1. Index Sequential File
ดัชนีจัดการกับแฟ้มข้อมูลลำดับเชิงดัชนี
1. Multi-key File
แฟ้มข้อมูลหลายคีย์
1. Hashing Function
ฟังก์ชันแฮชชิ่ง
1. Division-remainder
การหารเหลือเศษ
1. Mid-square
ค่ากลาง-ยกกำลังสอง
1. Open Addressing
การเปิดแอดเดรส
1. Bucket Addressing
การใช้พื้นที่บักเก็ต
1. Multiway Search Tree
ทรีค้นหาหลายทาง
1. AVL Tree
ก็เป็นการแก้ปัญหาความไม่สมดุลแบบบนลงล่าง
1. B*-Tree
เป็นโครงสร้างข้อมูลที่กำหนดขึ้นมาโดย Donald Knuth

วันพุธที่ 13 กรกฎาคม พ.ศ. 2554

โค้างสร้างและอัลกอริทึม

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

คือ รูปแบบของการจัดระเบียบของข้อมูล ซึ่งมีอยู่หลายรูปแบบ เช่น เขตข้อมูล(Field), แถวลำดับ(Array), ระเบียน(Record), ต้นไม้(Tree), ลิงค์ลิสต์(Link List) เป็นต้น (ทักษิณา สวนานนท์, 2544, หน้า 161) [4]p.12

คือ รูปแบบวิธีการจัดระเบียบของข้อมูลที่ได้จากการดำเนินการทางคณิตศาสตร์(Operations) เพื่อให้สามารถจัดการกับข้อมูลที่ใช้กับระบบคอมพิวเตอร์ได้ [4]p.12

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

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

โอภาส เอี่ยมสิริวงศ์, "โครงสร้างข้อมูล (Data Structures)"
บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2549.

โครงสร้างข้อมูล (Data Structure)
- บิท (Bit) คือ ข้อมูลที่มีขนาดเล็กที่สุด เป็นข้อมูลที่เครื่องคอมพิวเตอร์เข้าใจ และใช้งานได้ ได้แก่ 0 หรือ 1
- ไบท์ (Byte) หรือ อักขระ (Character) คือ ตัวเลข หรือ ตัวอักษร หรือ สัญลักษณ์พิเศษ จำนวน 1 ตัว
- ฟิลด์ (Field) หรือ เขตข้อมูล คือ ไบท์ หรือ อักขระตั้งแต่ 1 ตัวขึ้นไปรวมกันเป็นฟิลด์ เช่น เลขประจำตัว หรือ ชื่อพนักงาน
- เรคคอร์ด (Record) หรือระเบียน คือ ฟิลด์ตั้งแต่ 1 ฟิลด์ขึ้นไป ที่มีความสัมพันธ์เกี่ยวข้องกันมารวมกัน
- ไฟล์ (File) หรือ แฟ้มข้อมูล คือ หลายเรคคอร์ดมารวมกัน เช่น ข้อมูลที่อยู่นักเรียนมารวมกัน
- ฐานข้อมูล (Database) คือ หลายไฟล์ข้อมูลมารวมกัน เช่น ไฟล์ข้อมูลนักเรียนมารวมกันในงานทะเบียน แล้วรวมกับไฟล์การเงิน

เว็บเพจที่เกี่ยวข้อง
+ แนะนำหนังสือ
+ ซูโดโค้ด (Pseudocode)
+ การเขียนโปรแกรม เรียงเลข 3 ตัว

ตัวอย่างข้อมูล
ภาษาปาสคาล

r : real;

i : integer;

c : char;

s : string;

s20 : array[1..20] of char;
ภาษาซี

bool b; b = true;

char c; c = 'a';

int ar1[30]; ar1[0]=555;

int ar2[3]={55,66,77};
ภาษาจาวา

// boolean, char

// byte, short, int, long

// float, double
ภาษาวีบี

' 17 type : boolean, byte, char, date

' decimal, double, integer, long, object

' sbyte, short, single, string, uinteger

' ulong, user-defined, ushort

' s คือ signed และ u คือ unsigned

ศัพท์เทคนิค (Technical Terms)

phrase "a picture is worth a thousand words" [2]p.1
โครงสร้างข้อมูลพื้นฐาน ประกอบด้วยแบบของข้อมูลเบื้องต้น คือ 1)บิท(Binary) 2)อักขระ(Character) 3)ฟิลด์(Field) 4)เรคอร์ด(Record) 5)ไฟล์(File) 6)ฐานข้อมูล(Database) [4]p.12
วิเคราะห์ปัญหา (Problem Analysis) คือ การแยกปัญหาใหญ่ออกเป็นส่วน เพื่อนำไปสู่การแก้ปัญหาแต่ละส่วน
อัลกอริทึม (Algorithm) (มีความเป็นนามธรรมอยู่ในตัวเป็นธรรมชาติ)
คือ กลุ่มของขั้นตอนหรือกฎเกณฑ์ที่จะนำพาไปสู่การแก้ปัญหา [3]p.37
คือ ขั้นตอนวิธีที่ประกอ้บด้วยชุดคำสั่งเป็นขั้นเป็นตอนที่ชัดเจน และรับประกันว่าเมื่อได้ปฏิบัติถูกต้องตามขั้นตอนจนครบก็จะได้ผลลัพธ์ที่ถูกต้องตามต้องการ [3]p.37
คือ รูปแบบของการกำหนดการทำงานอย่างเป็นขั้นตอน ซึ่งผ่านการวิเคราะห์และแยกแยะ เพื่อการแก้ปัญหาต่าง ๆ ตามลำดับขั้น อาจเลือกใช้ภาษาไทยหรือภาษาอังกฤษตามความถนัด เพื่อนำเสนอขั้นตอนของกิจกรรมก็ได้ [4]p.17

รหัสเทียม หรือซูโดโค้ด (Pseudo Code)
คือ รหัสจำลองที่ใช้เป็นตัวแทนของอัลกอริทึม โดยมีถ้อยคำหรือประโยคคำสั่งที่เขียนอยู่ในรูปแบบของภาษาอังกฤษที่ไม่ขึ้นกับภาษาคอมพิวเตอร์ใดภาษาหนึ่ง [3]p.37
คือ การแสดงขั้นตอนวิธีการที่ใช้ภาษาเขียนที่เข้าใจได้ง่าย อาจใช้ภาษาไทยหรือภาษาอังกฤษก็ได้ขึ้นอยู่กับความสะดวกของผู้เขียนและกิจกรรมที่จะนำเสนอ มักใช้รูปแบบคล้ายประโยคภาษาอังกฤษเพื่ออธิบายรายละเอียดของอัลกอริทึม

ผังงาน (Flowchart)
คือ การแสดงขั้นตอนวิธีการที่ใช้สัญลักษณ์ที่เข้าใจได้ง่าย แต่ให้รายละเอียดได้น้อยกว่า
คือ รูปภาพ (Image) หรือสัญลักษณ์(Symbol) ที่ใช้เขียนแทนขั้นตอน คำอธิบาย ข้อความ หรือคำพูด ที่ใช้ในอัลกอริทึม (Algorithm) เพราะการนำเสนอขั้นตอนของงานให้เข้าใจตรงกัน ระหว่างผู้เกี่ยวข้อง ด้วยคำพูด หรือข้อความ ทำได้ยากกว่า [#]

การโปรแกรมโครงสร้าง (Structured Programming) คือ การกำหนดขั้นตอนให้เครื่องคอมพิวเตอร์ทำงานโดยมีโครงสร้างการควบคุมพื้นฐาน 3 หลักการ ได้แก่ 1)การทำงานแบบตามลำดับ(Sequence) 2)การเลือกกระทำตามเงื่อนไข(Decision หรือ Selection) และ 3)การทำงานแบบทำงานซ้ำ (Repetition หรือ Iteration หรือ Loop) #

อาร์เรย์ (Array)
คือ ชุดของข้อมูลในชื่อเดียวกันที่มีได้หลายสมาชิก โดยสมาชิกถูกจัดเรียงเป็นลำดับ และมีรูปแบบเป็นแบบใดแบบหนึ่ง
คือ การรวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปรชื่อเดียวกันแทนข้อมูลสมาชิกได้หลาย ๆ ตัวในคราวเดียวกัน ด้วยการใช้เลขดรรชนี (Index) หรือซับสคริปต์ (Subscript) เป็นตัวอ้างอิงตำแหน่งสมาชิกบนแถวลำดับนั้น ๆ [3]p.80

โอเปอเรชั่น (Operation) คือ การกระทำที่สามารถทำกับโครงสร้างนั้น เช่น โอเปอเรชั่นของอาร์เรย์ ได้แก่ 1)การท่องเข้าไป (Traversal) 2)การค้นหาข้อมูลที่ต้องการ(Searching) 3)การแทรกข้อมูลใหม่(Insertion) 4)การลบข้อมูล (Deletion) 5)การเรียงกลับหลัง(Reversing) 6)การเรียงลำดับ(Sorting) [1]p.14

นามธรรม (Abstract) คือ เป็นแนวทางพื้นฐานของมนุษย์ที่ใช้จัดการกับความซับซ้อน (Grady Booch) [3]p.41 โดยเรื่องราวของนวนิยายเป็นจินตนาการในหัวของผู้เขียนถือเป็นนามธรรม เมื่อถ่ายทอดผ่านตัวแทน (Representation) ทางหนังสือด้วยภาษาต่าง ๆ ก็จะออกมาเป็นรูปธรรม ดังนั้นการเขียนโปรแกรมต้องเริ่มต้นด้วยนามธรรม หรือจินตนาการจัดการความซับซ้อนก่อนนำเสนอเป็นรูปธรรม เพื่อประมวลผล

ชนิดข้อมูลนามธรรม (Abstract Data Type) คือ เครื่องมือกำหนดโครงสร้างข้อมูลที่ประกอบด้วยชนิดของโครงสร้างข้อมูล รูปแบบการดำเนินการ หรือแยกได้ 3 ส่วนคือ รูปแบบข้อมูล (Element) โครงสร้าง (Structure) และ การดำเนินการ (Operations) [4]p.25

โปรแกรม (Program) คือ ตัวแทนของอัลกอริทึม

โปรเซส (Process) คือ กิจกรรมที่ประมวลผลตามขั้นตอนของอัลกอริทึม

ความรู้เบื้องต้นเกี่ยวกับการพัฒนาระบบ

การพัฒนาโปรแกรมประกอบด้วยขั้นตอนพื้นฐาน 7 ขั้นตอน [3]p.19
1. กำหนดปัญหา (Define the Problem)
2. ร่างรายละเอียดแนวทางแการแก้ไขปัญหา (Outline the Solution)
3. พัฒนาอัลกอริทึม (Develop Algorithm) อาจนำเสนอด้วย Flowchart, DFD, ER หรือ UML
4. ตรวจสอบความถูกต้องของอัลกอริทึม (Test the Algorithm for Correctness)
5. เขียนโปรแกรม (Programming)
6. ทดสอบโปรแกรม (Testing)
7. จัดทำเอกสารและบำรุงรักษาโปรแกรม (Document and Maintain the Program)

กรรมวิธีการออกแบบโปรแกรม (Program Design Methodology) [3]p.21 #
- การออกแบบโปรแกรมแบบ Procedure-Driven
- การออกแบบโปรแกรมแบบ Event-Driven
- การออกแบบโปรแกรมแบบ Data-Driven

การเขียนโปรแกรมแบบ Procedural และ Object-Oriented [3]p.22
- การเขียนโปรแกรมแบบบนลงล่าง (Top-Down Development)
- การออกแบบโปรแกรมในลักษณะโมดูล (Modular Design)
- การโปรแกรมเชิงวัตถุ (Object-Oriented Programming) 
คือการโปรแกรมที่ให้ความสำคัญกับการรวมวัตถุ และกระบวนการได้ด้วยกัน เพื่อสืบทอด (Inheritance) หรือนำกลับมาใช้ใหม่ได้ (reused)
โดยการนำทั้งวัตถุ และกระบวนการมารวมกัน มักเก็บไว้ใน Class ซึ่งหมายถึง ต้นแบบของวัตถุ
ต.ย. โปรแกรมแบบ Top-Down ด้วยภาษา Pascal
program p01;
begin
Writeln('burin');
Writeln('rujjanapan');
end. 

คอมพิวเตอร์สามารถคำนวณได้ เครื่องหมายทางคณิตศาสตร์ เช่น + - * / ^ ( ) [3]p.164
x = 4 / 2 + 4 ^ 2 - 1 * 2 + 3 19 กด Ctrl + A = คำตอบ
y = 36 / (2 + 4) ^ 2 - 1 * 2 + 3 2
z = 4 / 2 + 4 ^ (2 - 1) * 2 + 3 13

ต.ย. โปรแกรมแบบ Modular ด้วยภาษา Pascal
program p02;
procedure xName;
begin
Writeln('burin');
end;
begin
xName;
end. 

ต.ย. โปรแกรมแบบ OOP ด้วยภาษา Java
class father {
String n;
private void pname () {
n = "burin"; 
return n;
}
}
class child extends father {
child() {
n = "rujjanapan";
System.out.println(pname()); // yonok
}
public static void main(String[] a) {
new child();
}
private void pname () {
n = "yonok"; 
return n;
}
}
 ภาพแสดง ความแตกต่างของ Stack กับ Heap และ pass by value กับ pass by reference

อัลกอริทึม (Algorithm) http://www.thaiall.com/datastructure/pseudocode.htm

การเขียนอัลกอริทึมมีประเด็นต้องพิจารณาหลายเรื่อง คือ 1)วัตถุประสงค์ 2)เหตุการณ์ก่อนประมวลผล 3)ค่าของพารามิเตอร์ทั้งก่อนและหลังประมวลผล 4)สิ่งที่ได้หลังประมวลผล 5)ลำดับเหตุการณ์ระหว่างประมวลผล

ต.ย. อัลกอริทึมที่ 1 : ต้มมาม่า [3]p.25
1. หามาม่าไว้ 1 ซอง
2. ฉีกซองมาม่าและเทลงถ้วยเปล่า
3. ฉีกซองเครื่องปรุง แล้วเทลงถ้วยเดิม
4. ต้มน้ำให้ร้อนได้ที่ แล้วเทลงถ้วย
5. ปิดฝาไว้ 3 นาที
6. เปิดฝา แล้วรับประทาน

คำถาม : ต้มมาม่า
1. มีขั้นตอนใดสลับกันได้
2. ถ้าเปลี่ยนข้อความ จะเปลี่ยนอย่างไร
3. ถ้าทำหลายถ้วยจะทำอย่างไร

? คน 3 คนใครอายุมากที่สุด และเป็นเท่าใด

ต.ย. อัลกอริทึมที่ 2 : หาค่าเฉลี่ย ใช้ Pseudo Code 
1. set variable
2. loop
1. read number into variable
2. add number to total
3. increase counter
3. end loop
4. set average = total / counter
5. print average

คำถาม : หาค่าเฉลี่ย
1. เขียนเป็นภาษาไทยอย่างไร
2. แต่ละบรรทัดในจาวาคืออะไร
3. สลับบรรทัดใดในจาวาได้บ้าง
4. ไม่มีตัวแปร avg จะได้หรือไม่

1.


2.



3.
4.
5.

ภาษาจาวา
byte x;
int i = 0;
int total = 0;
while (i < 5) {
  x = System.in.read();
  total = total + x;
  i++;
}
double avg = total/i;
System.out.println(avg);

ปฏิบัติการพื้นฐานของเครื่องคอมพิวเตอร์ [3]p.37

1. รับข้อมูล (input device)
2. แสดงผล (output device)
3. คำนวณ (limit and sequence)
4. กำหนดค่าตัวแปร (storage)
5. เปรียบเทียบ หรือเลือกทำงาน (compare or decision)
6. ทำซ้ำ (repeation or loop)

หน่วยความจำ (Memory)

โครงสร้างหน่วยความจำ (Memory Architecture)
การจัดสรรหน่วยความจำ (Memory Allocation)
- แบบคงที่ (Static)
- แบบเปลี่ยนแปลงได้ (Dynamic)
ตารางแฟท (FAT = File Allocatio Table)
- Directory Table
- Memory Pointer
File Attribute
- Archive file
- System file
- Readonly file
- Hidden file

ต.ย. แฟ้ม adisinit.exe มีขนาด 35.1 KB ใช้พื้นที่ 9 Block ๆ ละ 4 KB
เพราะเครื่องนี้แบ่ง 1 Cluster มีขนาด 8 Sectors

ชนิดข้อมูลนามธรรม (Abstract Data Type : ADT)

ชนิดข้อมูลนามธรรม (Abstract Data Type) คือ เครื่องมือกำหนดโครงสร้างข้อมูลที่ประกอบด้วยชนิดของโครงสร้างข้อมูล รูปแบบการดำเนินการ 
หรือแยกได้ 3 ส่วนคือ รูปแบบข้อมูล (Element) โครงสร้าง (Structure) และ การดำเนินการ (Operations) [4]p.25

แบบประเภทข้อมูลตามลักษณะความสัมพันธ์ในข้อมูล 1. ข้อมูลเชิงเดี่ยว (Atomic Data) 2. ข้อมูลเชิงประกอบ (Composite Data) ชนิดข้อมูลนามธรรม (ADT) มิใช้โครงสร้างข้อมูล [3]p.50 แต่เป็นรูปแบบระดับแนวคิดหรือรูปแบบข้อมูลเชิงลอจิคอล  1. รูปแบบข้อมูลเชิงลอจิคอล (Logical Form) เป็นการนิยามด้วย ADT 2. รูปแบบข้อมูลเชิงฟิสิคัล (Psysical Form) เป็นการนำ ADT มาใช้

ประสิทธิภาพของอัลกอริทึม (Algorithm Efficiency)

ประเด็นที่ใช้วัดประสิทธิภาพ [3]p.58

1. เวลาที่ใช้ประมวลผล (Running Time)

2. หน่วยความจำที่ใช้ (Memory Requirement)

3. เวลาที่ใช้แปลโปรแกรม (Compile Time)

4. เวลาที่ใช้ติดต่อสื่อสาร (Communication Time)

ปัจจัยที่ส่งผลต่อความเร็วในการประมวลผล

1. ความเร็วของเครื่องคอมพิวเตอร์ (CPU, Main Board)

2. อัลกอริทึมที่ออกแบบเพื่อใช้งาน

3. ประสิทธิภาพของตัวแปลภาษา

4. ชุดคำสั่งที่สั่งประมวลผลเครื่องคอมพิวเตอร์

5. ขนาดของหน่วยความจำในเครื่องคอมพิวเตอร์

6. ขนาดของข้อมูลนำเข้า และผลลัพธ์จากการประมวลผล

- การวัดประสิทธิภาพของอัลกอริทึม (Efficiency Algorihm)

คือ วัดจากพื้นที่ทำงาน และเวลา แต่กับคอมพิวเตอร์ในปัจจุบันที่มีศักยภาพสูง การวัดประสิทธิภาพจากเวลาอาจไม่เห็นความแตกต่าง
- การวิเคราะห์บิ๊กโอ (Big-O Analysis)

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

ปัจจุบันมีการเปลี่ยนจาก f() มาเป็น Big-O notaion เพื่อใช้ Big-O วัดประสิทธิภาพของอัลกอริทึม
- ขั้นตอนการเปลี่ยน f() เป็น Big-O Notation [4]p.23

1. ปรับฟังก์ชันให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย คือตัดตัวประกอบออก ให้เหลือเพียงค่าของโพลิโนเมียน (คือ n ยกกำลัง)

f(n) = n( (n + 1) / 2 )

= ((1/2)(n ^ 2)) + (1/2(n))

= (n ^ 2) + n

2. ตัดค่าของตัวประกอบออก

= n ^ 2

3. นำฟังก์ชันมาตรฐานมาเขียนในรูปของ Big-O Notation

O(f(n)) = O(n ^ 2)

ความหมายของลอการิทึม
- ลอการิทึม (อังกฤษ: logarithm) เป็นการดำเนินการทางคณิตศาสตร์ที่เป็นฟังก์ชันผกผันของฟังก์ชันเลขชี้กำลัง
- ค่าลอการิทึมของจำนวนหนึ่งโดยกำหนดฐานไว้ให้ จะมีค่าเทียบเท่ากับ การเอาฐานมายกกำลังค่าลอการิทึม ซึ่งจะให้คำตอบเป็นจำนวนนั้น

ลูปแบบเพิ่ม 2 เท่า
for(i=1;i<1000;i*=2){ echo i; }
เช่น 1 2 4 8 16 32 64

ลูปแบบลด 2 เท่า
for(i=1;i<1000;i/=2){ echo i; }
เช่น 1000 500 250 125 62.5 31.25

- ต.ย.1 จงหาผลบวกของการบวกจำนวนที่เริ่มต้นตั้งแต่ 1 - 10
ฟังก์ชัน คือ f(n) = n( (n + 1) / 2 )
= ((1/2)(n ^ 2)) + (1/2(n))
= (n ^ 2) + n
= n ^ 2
O(f(n)) = O(n ^ 2)
- ต.ย.2 จงแปลง  f(n) = a*n^k + a*n^k-1 +  .. a*n^0 เป็น Big-O Notation
ฟังก์ชัน คือ f(n) = a*n^k + a*n^k-1 +  .. a*n^0
= n^k + n^k-1 +  .. n^0 (ปรับให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย)
= n^k (ตัดค่าของตัวประกอบออก)
O(f(n)) = O(n ^ k) (เขียนในรูปของ Big-O Notation)
- ต.ย.3 จงแปลง  f(n) = 4n + 7 เป็น Big-O Notation [6]p.50
ฟังก์ชัน คือ f(n) = 4n + 7
= n + 7 (ปรับให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย)
= n (ตัดค่าของตัวประกอบออก)
O(f(n)) = O(n) (เขียนในรูปของ Big-O Notation)
- ต.ย.4 จงแปลง  f(n) = 1009 เป็น Big-O Notation [6]p.51
ฟังก์ชัน คือ f(n) = 1009
= 1009 (ปรับให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย)
= 1 (ตัดค่าของตัวประกอบออก)
O(f(n)) = O(1) (เขียนในรูปของ Big-O Notation)
ดร.บุญญฤทธิ์  อุยยานนวาระ

เปรียบเทียมประสิทธิภาพของ Big-O กับความเร็วของยวดยาน ดังนี้
+ O(1) เหมือนเครื่องว๊าบ หรือเครื่องย้ายมวลสาร คือ ไกลแค่ไหนไม่เกี่ยว 
+ O(log n) เหมือนเครื่องบินโดยสาร 
+ O(n) - เหมือนรถฟอร์มูล่าวัน ระยะทางไกลขึ้น ก็ขับนานขึ้น
+ O(n log n) - เหมือนรถยนตทั่วไป ยิ่งไกลยิ่งช้า
+ O(n^2) - เหมือนมอร์เตอร์ไซด์ 
+ O(n^3) - เหมือนจักรยาน 
+ O(2^n) - เหมือนคนเดิน

การทำซ้ำ หรือลูป มีหลายแบบ
- ลูปแบบเชิงเส้น (Linear Loops)
- ลูปแบบลอการิธมิค (Logarithmic Loops)
- ลูปแบบซ้อน (Nested Loops)

ลูปแบบเชิงเส้น (Linear Loops) [3]p.59
f(n) = n
for (i=0; i< n; i++)
application code
f(n) = n / 2
for (i=0; i< n; i+=2)
application code
ลูปแบบลอการิทึม (Logarithmic Loops)
f(n) = logn
for (i=0; i< n; i*=2)
application code
f(n) = log2n
for (i=0; i< n; i/=2)
application code
ลูปแบบซ้อน (Nest Loops)
ลูปแบบซ้อนชนิดกำลังสอง (Quadratic)
f(n) = n^2
for (i=0; i< n; i++)
for (j=0; j< n; j++)
application code
ลูปแบบซ้อนชนิดลอการิทึมเชิงเส้น (Linear Logarithmic)
f(n) = nlogn
for (i=0; i< n; i++)
for (j=0; j< n; j*=2)
application code
ลูปแบบซ้อนกำลังสองชนิดขึ้นต่อกัน (Dependent Quadratic)
f(n) = n( (n + 1) / 2 )
for (i=0; i< n; i++)
for (j=0; j< i; j++)
application code

อาร์เรย์ (Array)

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

คือ การรวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปรชื่อเดียวกันแทนข้อมูลสมาชิกได้หลาย ๆ ตัวในคราวเดียวกัน ด้วยการใช้เลขดรรชนี (Index) หรือซับสคริปต์ (Subscript) เป็นตัวอ้างอิงตำแหน่งสมาชิกบนแถวลำดับนั้น ๆ [3]p.80

- อาร์เรย์หนึ่งมิติ (One Dimension Array)
รูปแบบของอาร์เรย์ คือ arrayname[L:U]
arrayname คือ ชื่อของตัวแปรอาร์เรย์ เช่น x[5]
L คือ ขอบเขตล่างสุด (Lower Bound) 
U คือ ขอบเขตบนสุด (Upper Bound)
จำนวนสมาชิก = U - L + 1
- อาร์เรย์สองมิติ (Two Dimension Array)
จำนวนสมาชิก = (U1 - L1 + 1) * (U2 - L2 + 1)
ตัวอย่างอารย์เรย์ ภาษาเบสิก เช่น Dim x(7, 24) As Byte
ตัวอย่างอารย์เรย์ ภาษาซี เช่น int a[][] = new int[4][3]; 
ตัวแรกมักหมายถึง แถว (rows) ตัวที่สองหมายถึง หลัก (columns)
- เมทริกซ์ คล้ายกับอาร์เรย์ 2 มิติ
- ตำแหน่งในหน่วยความจำ
B คือ ตำแหน่ง หรือแอดเดรสเริ่มต้น (Base Address)
w คือ จำนวนช่องของหน่วยความจำที่จัดเก็บข้อมูลต่อหนึ่งสมาชิก
ตำแหน่งในหน่วยความจำ LOC( a[i] ) คือ B + w (i - L)

http://msdn.microsoft.com

เรคอร์ด (Record)

ระเบียนข้อมูล หรือเรคอร์ด


ตารางข้อมูลในฐานข้อมูล NorthWind ประกอบด้วย 8 ตาราง คือ
Categories, Customers, Shippers, Products, 
Orders, Order Details, Employees, Suppliers

แบบฝึกหัด : จงเขียนความสัมพันธ์ระหว่างตาราง

ลิงค์ลิสต์ (Linked List) [3]p.101

ลิสต์ (Lists) หรือรายการ ถือเป็นการจัดเก็บข้อมูลชนิดหนึ่ง ซึ่งข้อมูลเชื่อมต่อกันแบบเชิงเส้น แต่ละข้อมูลมักเรียกว่า อีลิเมนต์ (Element) หรือสมาชิก (Member) โดยแบ่งโดยพื้นฐานได้ 2 แบบคือแบบทั่วไป (General) และแบบจำกัด (Restricted) ซึ่งแนวคิดของลิงค์ลิสต์จะกำหนดให้แต่ละสมาชิกจะประกอบด้วย ข้อมูล (Data) และลิงก์ (Link) โดยข้อมูลอาจประกอบด้วยหลายฟิลด์ก็ได้
การดำเนินงานพื้นฐานของลิสต์ (Basic Operations of List)
1. การแทรก (Insertion)
2. การลบ (Deletion)
3. การปรับปรุง (Updation)
4. การท่องเข้าไปในลิสต์ (Traversal)

ตัวชี้ข้อมูลด้วยภาษาปาสคาล [2]p.220 Binary Tree type nodeptr = ^trnode; trnode = record data : integer; leftptr : nodeptr; rightptr : nodeptr; end;	ตัวชี้ข้อมูลด้วยภาษาซี [3]p.193 Abstract Data Type ของ คิว typedef struct node { void* dataptr; struct node* next; } QUEUE_NODE; typedef struct { QUEUE_NODE* front; QUEUE_NODE* rear; int count; } QUEUE; QUEUE* createQueue (void); bool enqueue (QUEUE* q, void* itemptr);
สร้างคิว [2]p.221 var root : nodeptr; begin maket(root); procedure maket(var t:nodeptr); begin new(t); t^.data := 123; t^.leftptr := nil; t^.rightptr := nil; end;	สร้างคิว QUEUE* createQueue (void) { QUEUE* q; q = (QUEUE*) malloc (sizeof (QUEUE)); if (q) { q->front = NULL; // node ชี้ตัวแรก q->rear = NULL; // node ชี้ตัวสุดท้าย q->count = 0; } }
เพิ่มข้อมูลในคิว [2]p.224 new(n); inserted := false; o := t; while not inserted do begin if num <= o^.data then if o^.leftptr <> nil then o := o^.leftptr; else begin o^.leftptr := n; inserted := true; end else if o^.rightptr <> nil then o := o^.rightptr; else begin o^.rightptr := n; inserted := true; end; end; n^.data := num; n^.leftptr := nil; n^.rightptr := nil;	เพิ่มข้อมูลในคิว bool enqueue (QUEUE* q, void* itemptr) { QUEUE_NODE* newptr; if (!(newptr = (QUEUE*) malloc (sizeof(QUEUE)))) return false; newptr->dataptr = itemptr; newptr->next = NULL; if (q->count == 0) q->front = newptr; else q->rear->next = newptr; (q->count)++; q->rear = newptr; return true; }

// Test of Linked List #1/2
class BlankNode {
  public Object data;
  public BlankNode next;
  public BlankNode(Object data) {
    this.data = data;
    this.next = null;
  }
  public String toString() { 
    return data.toString(); 
  }
}

สแต็ก (Stack)

- Push คือ เพิ่มข้อมูลลงสแต็ก [3]p.137
- Pop คือ นำข้อมูลบนสุดไปใช้ และลบออกจากสแต็ก
- Stack Top คือ นำข้อมูลบนสุดไปใช้ แต่ไม่ลบออกจากสแต็ก
- Infix คือ นิพจน์ทางคณิตศาสตร์ทั่วไปที่เราใช้กัน [3]p.159
- Postfix คือ นิพจน์ที่โอเปอเรเตอร์อยู่หลังโอเปอแรนต์ เช่น AB+
- Prefix คือ นิพจน์ที่โอเปอเรเตอร์อยู่หน้าโอเปอแรนต์ เช่น +AB

อาจกล่าวอีกอย่างได้ว่า
- ตัวดำเนินการ คือ เครื่องหมายทางคณิตศาสตร์ (Operator)
- ตัวถูกดำเนินการ คือ สัญลักษณ์หรือตัวแปร (Operand)
- Infix คือ ตัวดำเนินการอยู่ระหว่างตัวถูกดำเนินการ
- Postfix คือ ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ
- Prefix คือ ัวดำเนินการอยู่ก่อนตัวถูกดำเนินการ


กฎเกณฑ์สำหรับการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix [3]p.160
ขั้นตอนที่ 1. ใส่เครื่องหมายวงเล็บให้ทุกนิพจน์ แยกลำดับการคำนวณ เช่น คูณ หาร มาก่อน บวก ลบ
ขั้นตอนที่ 2. เปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix โดยเริ่มจากวงเล็บในสุดก่อน
ขั้นตอนที่ 3. ถอดวงเล็บออก

ฟังก์ชันที่เกี่ยวกับสแต็ก [3]p.143
1. Create Stack คือ สร้างหัวสแต็ก
2. Push Stack คือ เพิ่ม
3. Pop Stack คือ ดึงออก
4. Stack Top คือ อ่านบนสุด
5. Empty Stack คือ ตรวจการว่าง
6. Full Stack คือ ตรวจการเต็ม
7. Stack Count คือ นับสมาชิก
8. Destroy Stack คือ ลบข้อมูลและหัวสแต็ก

infix	postfix	prefix ?
A * B + C / D	A B * C D / +	+ * A B / C D
A * (B + C) / D	A B C + * D /	/ * A + B C D
A * (B + C / D)	A B C D / + *	* A + B / C D

กฎเกี่ยวกับการแปลง infix เป็น postfix
1. ถ้า input เป็น operand ให้ออกเป็น postfix
2. ถ้า input เป็น operator แล้ว stack ว่างให้ลง stack
3. ถ้า input มีลำดับสำคัญกว่าใน stack ให้ลง stack
4. ถ้า input สำคัญน้อยกว่าใน stack ย้ายใน stack ไปเป็น postfix

ต.ย. 1 แปลง A - B / C เป็น Postfix

ขั้นตอนที่ 1 :

A - (B / C)

ขั้นตอนที่ 2 :

A - (BC /)

A(BC/)-

ขั้นตอนที่ 3 :

ABC/-

โจทย์ให้ฝึกแปลงจาก infix เป็น postfix
1. a + b - c * d / e - f + g * h
2. a * b - c * d + e - f + g * h
3. a + b * c * d / (e * f) * g + h
4. a + b - (c * d) - e - f + g - h
5. a + (b + c) * d / e + f / g * h
6. a / b * c * d * (e - f) + g ^ h
7. (a ^ b) / c * d / e - f + g + h
8. a * b ^ c * ((d - e) - f) * g - h
9. a + b - c ^ ((d - e) - f) * (g - h)
10. a / (b + c) * (d + (e + f)) ^ g + h
+ stack_cal_postfix

คิว (Queue) : คิว ใน wikipedia.org

- คิว (Queue)

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

ฟังก์ชันที่เกี่ยวกับคิว ประกอบด้วย enqueue, dequeue, queue front, queue rear

ทรี (Tree) :

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

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

คือ ทรีที่คิดค้นโดย G.M.Adelson-Velskii และ E.M.Landis โดยทรีแบบนี้จะมี ความสูงของซับทรี มาหักลบกันแล้วต้องมีค่าไม่มากกว่า 1
- ฮีพทรี (Heap Tree)

คือ ไบนารีทรีแบบสมบูรณ์หรือเกือบสมบูรณ์ ซึ่งโหนดพ่อจะมีค่ามากกว่าหรือเท่ากบับซับทรีด้านซ้าย และด้านขวา
แนวคิดพื้นฐานของทรี [3]p.211
- โหนดราก (Root Node) คือ โหนดแรก เริ่มต้นที่อยู่บนสุด
- โหนดพ่อ (Parents) คือ โหนดที่มีลูก
- โหนดลูก (Children) คือ โหนดที่มีพ่อ
- โหนดพี่น้อง (Siblings) คือ โหนดเป็นพี่่น้อง และนับแยกครอบครัว
- โหนดใบ (Leaf Node) คือ โหนดที่่อยู่ปลายสุด
- ดีกรีทั้หมดของทรี คือ ที่มีฐานะเป็นลูกทั้งหมด
- ดีกรีทั้หมดของพ่อ A คือ ที่มีฐานะเป็นลูกทั้งหมดของ A
- ระดับความสูง (Level) คือ จำนวนชั้นของทรี

Binary Serch Tree

Heap Tree

กราฟ (Graph)

การจัดเก็บข้อมูลในกราฟ
1. เมทริกซ์ประชิด (Adjacency Matrix)
2. ลิสต์ประชิด (Adjacency List)

- ดีกรี (Degree) คือ จำนวนของเวอร์เท็กซ์ประชิด
- เอาต์ดีกรี คือ เส้นที่ออกจากเวอร์เท็กซ์
- อินดีกรี คือ เส้นที่เข้ามายังเวอร์เท็กซ์
- เส้นทาง (Path) คือลำดับของเวอร์เท็กซ์ที่ประชิดต่อกันไปยังตัวถัดไป
- เอดจ์ (Edges) คือ เส้นที่เชื่อมระหว่างเวอร์เท็กซ์ แบบไม่มีทิศทาง
- อาร์ค (Arcs) คือ เส้นที่เชื่อมระหว่างเวอร์เท็กซ์ แบบมีทิศทาง
- เวอร์เท็กซ์ (Vertex) คือ โหนด

V = {A,B,C,D,E}

การเรียงลำดับข้อมูล (Sorting)

สำหรับอธิบายการจัดเรียงแบบน้อยไปมาก เป็นการเริ่มต้น
- แบบเลือก (Selection Sort) O(n2)

คือ การสแกนหาค่าน้อยที่สุด แล้วสลับตำแหน่งกับตัวแรก
- แบบฮิพ (Heap Sort)

คือ การย้าย root note ไปอยู่ตำแหน่งสุดท้าย แล้วทำการ reheap ใหม่
- แบบแทรก (Insertion Sort)

คือ การเปรียบเทียบค่ากับตำแหน่งถัดไป หากพบค่าใหม่ก็จะนำมาแทรกในตำแหน่งที่เหมาะสม เหมือนการเรียงไพ่
- แบบฟองสบู่ (Bubble Sort)

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

- แบบควิค (Quick Sort)

คือ การจัดเรียงคล้าย Bubble Sort ที่มีการ exchange แต่แบบนี้จะแบ่งส่วนเป็น Partition โดยข้อมูลแบ่งได้ 3 ส่วนคือ 1)ค่า pivot สำหรับแบ่งส่วน 2)ค่าที่น้อยกว่า pivot 3)ค่าที่มากกว่า pivot
1)ก่อนดำเนินการจะนำค่า Pivot Key ตัวแรก และค่าแรก และค่าสุดท้ายมาเรียกให้ถูกต้องก่อน
2)หลังจากนั้น จะย้าย Pivot Key ตัวแรก สลับกับค่าแรก และให้ตัวที่อยู่ถัดค่าแรกเรียกว่า sort left และตัวสุดท้ายเรียกว่า sort right
3)ย้าย sort left ไปทางขวา แล้วย้าย sort right มาทางซ้าย จะหยุดเมื่อ sort left มากกว่า pivot key และ sort right น้อยกว่า pivot key แล้วสลับทั้ง 2 ค่า พร้อมเลื่อนต่อด้วยหลักการเดิม
4)ก่อนเสร็จสิ้นการแบ่ง ให้ย้ายค่าที่เคยเป็นค่าแรก กับ pivot key
5)การดำเนินการหลังแบ่งส่วนแล้ว ให้เริ่มจากด้านซ้าย แล้วค่อยทำทางขวา ในขณะจัดเรียงทางซ้ายก็จะแบ่งส่วนด้วย pivot key ของด้านซ้าย และแบ่งย่อยลงไปอีก ในขณะจัดเรียงทางขวาก็จะแบ่งส่วนด้วย pivot key ของด้านขวา และแบ่งย่อยลงไปอีก ทำเรื่อยไปจนแบ่งส่วนไม่ได้ ก็จะได้ผลการจัดเรียง

การเรียงแบบนี้ปรับปรุงโดย R.C.Singleton ปีค.ศ.1969 ให้เลือกค่า Pivot Key จากค่ากลาง Median Value คือตำแหน่งที่อยู่ตรงกลาง (ตำแหน่งแรก + ตำแหน่งสุดท้าย/2 แล้วปัดเศษทิ้ง)

- แบบผสาน (Merge Sort)

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

สำหรับการจัดเรียงจะทำการแบ่งข้อมูลจนเหลือเพียง 2 ส่วน แล้วจัดเรียงกลุ่มเล็กทุกกลุ่มจนหมด แล้วนำทั้งหมดมารวมกัน ก็จะได้ผลการจัดเรียง

เรคคอร์ด

โครงสร้างข้อมูลเรคคอร์ด

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

11,0500.00

24/6 Sukumvit…

Chanrung

Wilaiporn

110211

รูปที่ 3.2 ตัวอย่างโครงสร้างข้อมูลเรคคอร์ดที่แต่ละเขตข้อมูลมีโครงสร้างข้อมูลต่างกัน

การกำหนดเรคคอร์ด
เรคคอร์ดมีการกำหนดรูปแบบเป็น ดังนี้

Rec (Field1, Field2, . . . , FieldN)

โดย Fieldi เป็นสมาชิกของเรคคอร์ด และ 1≤ i ≤ N
เป็นการสร้างเรคคอร์ดชื่อ Rec ที่มีสมาชิก N ตัว การใช้งานเรคคอร์ดเมื่อต้องการอ้างถึงสมาชิกจะใช้เครื่องหมายมหัพภาค (จุด) แสดงคุณสมบัติ (Qualification) คั่นระหว่างชื่อเรคคอร์ดกับชื่อเขตข้อมูลดังนี้

Rec . Fieldi

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

ตารางที่ 3.2 ตัวอย่างโปรแกรม Record1.c

#include<stdio.h>
#include<coio.h>
#include<string.h>

struct Enployee {
          int ID;
          char Name[80];
          char Phone[80];
          float Salary;
};

void printRecord( struct Employee e ) {
printf( “ID-number Number Phone Salary\n” );
printf( “%-10d %-20s %-12s %-8.2f\n”, e.ID, e.Name, e.Phone, e.Salary );
}

main() {
          struct Employee emp1;
          int id;
          char name[80];
          char phone[80];
          float salary;

          printf( “Employee Records: \n” );
          printf( “Enter ID-number: “ );
          scanf( “%d” , &id );
          emp1.ID = id;
          getchar();

          printf( “Enter name: “);
          gets( name );
          strcpy(emp1.Name,name);

          printf( “Enter phone: “);
          scanf( “%s”, phone );
          strcpy( emp1.Phone,phone );

          printf( “Enter salary: “);
          scanf( “%f”, &salary );
          emp1.Salary = salary;

printf( “\nValue in record is\n” );
printRecord( emp1 );

getch();

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

                                Struct Employee   {
                             Int ID;
                             char Name[80];
                             char Phone[80];
                             float Salary;
                   };

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

Struct Employee emp1;

เมื่อใดที่ต้องการเก็บข้อมูลหรือดึงข้อมูลมาใช้งานจะเป็นดังนี้

                                emp1.ID
                   emp1.Name
                   emp1.Phone
                   emp1.Salary

จากตัวอย่างมีการเขียนฟังก์ชัน printRecord เป็นตัวปฏิบัติการของเรคคอร์ด ทำหน้าที่ในการแสดงผลทางจอภาพเป็นแบบตาราง เมื่อใดที่มีการประกาศตัวแปรเรคคอร์ดใหม่มาใช้งาน ตัวแปรทุกตัวก็สามารถใช้ตัวปฏิบัติการร่วมกันได้
โดยทั่วไปการใช้โครงสร้างข้อมูลเรคคอร์ดจะไม่ใช้เพียงเรคคอร์ดเดียว แต่จะใช้หลาย ๆ เรคคอร์ดเพื่อเก็บข้อมูลที่มีลักษณะแบบเดียวกันเป็นจำนวนมาก ๆ ที่เรียกว่าฐานข้อมูล (Database) วิธีการหนึ่งที่นำมาใช้คือ กำหนดเป็นอาร์เรย์ให้แต่ละสมาชิกมีโครงสร้างข้อมูลเรคคอร์ด แต่มีข้อจำกัดี่จำนนสมาชิกคงที่เปลี่ยนแปลงไม่ได้ มีอีกวิธีการหนึ่ง คือ กำหนดเป็นแบบไดนามิก (Dynamic) โดยการขอพื้นที่ในหน่วยความจำให้กับโครงสร้างข้อมูลเรคคอร์ดเมื่อต้องการใช้งาน และไม่จำกัดจำนวนเรคคอร์ดจนกว่าหน่วยความจำเต็ม แต่การเขียนโปรแกรมก็จะซับซ้อนมากขึ้น ดังตารางที่ 3.3 เป็นตัวอย่างโปรแกรม Record2.c

ตารางที่ 3.3 ตัวอย่างโปรแกรม Record2.c

#include<stdio.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>

struct employee {
          int ID;
          char Name[80];
          char Phone[80];
          floar Salary;
};

typedef struct employee Employee;
typedef Employee* Employees;

Employees createEmployee()   {
          Employees e = malloc( sizeof (Employee) );
          Return e;
}

void printEmployee( Employees e ) {
printf( “%-10d %-20s %-12s %-8.2f\n”, e-›ID, e-›Name, e-›Phone, e-›Salary );
}

main() {
Employees emp1 = createEmployee();
Employees emp2 = createEmployee();

          emp1 -›ID = 1101;
          strcpy( emp1-›Name, “Sinsamut” );
          strcpy( emp1-›Phone, “123456789” );
          emp1 -›Salary = 12345.00;

          emp2 -›ID = 2041;
          strcpy( emp2-›Name, “Sudsakorn” );
          strcpu( emp2-›Phone, “987654321”);
          emp2-›Salary = (float)54321.975;

          printf( “Employee Records\n” );
          printf( “ID – number Name     Phone       Salary\n” );
          printEmployee( emp1 );
          printEmployee( emp2 );

getch();
}

จากตัวอย่าเป็นการกำหนดโครงสร้างข้อมูลชื่อใหม่ (Alias) คือ Employee และ Employees ที่เป็นพอยน์เตอร์โดยมีลักษณะเป็นโครงสร้างข้อมูลเรคคอร์ด ดังนี้

typedef struct employee Employee;
typedef struct Employee* Employees;

เมื่อต้องการใช้งานจะต้องขอพื้นที่หน่วยความจำใช้งานให้กับแต่ละเรคคอร์ดในฟังก์ชัน createEmployee ดังนี้

Eployees e = malloc ( sizeof (Employees) );

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

                   emp1 -› ID
                   emp1 -› Name
                   emp1 -› Phone
                   emp1 -› Salary

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