- รู้จักการทำงานร่วมกันเป็นหมู่คณะ
- ฝึกฝนให้เป็นนตรงต่อเวลา
- ไดเผชิญหน้ากันปัญหาจริง และแก้ไขปัญหาได้จริง
- ฝึกฝนบุคลิกภาพ ทำให้เป็นคนมีบุคลิกภาพดี ในสายตาของบุคคลภายนอกที่มองเข้ามา
- ฝนให้เป็นคนมีความรับผิดชอบ
- ทำให้รู้ว่าเวลาทุกวินาทีมีความสำคัญ ถ้าเราทำพลาดไปแม้แต่วินาทีเดียว ก็อาจทำให้เราพลาดโอกาสดีๆที่จะเข้ามาในชีวิตของเราได้
- ทำให้รู้และเข้าใจความหมายของคำว่าสามัคคีมากขึ้น
- รู้จักปรับตัวให้เข้ากับสิ่งแวดล้อมรอบๆตัวเรา
วันพุธที่ 14 ตุลาคม พ.ศ. 2552
ลูกแรดเตรียมพร้อมล่าเหยื่อ
DTS11-16-09-2552
การค้นหาข้อมูล searching แบ่งเป็น 2 ประเภท
การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ (Linear)
การค้นหาแบบเซนทินัล (Sentinel)
การค้นหาแบบไบนารี (Binary Search)
DTS10-09-09-2552
การ จัดเรียงข้อมูลนับเป็นสิ่งสำคัญที่ใช้ในการดำเนินการกับข้อมูลเพื่อประโยชน์ ในการจัดการกับข้อมูล การค้นหา หรือการดำเนินการอย่างอื่นได้สะดวกและรวดเร็ว มากกว่าข้อมูลที่ไม่มีการจัดเรียง เช่น การจัดเรียงหนังสือในห้องสมุด การจัดเรียงคำศัพท์ในพจนานุกรม ระบบการจัดเรียงจะมีรูปแบบของการจัดเรียงที่แตกต่างกันไปตามความเหมาะสม และสำหรับรูปแบบของการจัดเรียงข้อมูลในคอมพิวเตอร์ก็มีหลากหลายรูปแบบที่ใช้ ในการจัดเรียงข้อมูล ซึ่งรูปแบบที่กำหนดขึ้นมานั้นก็มีทั้งข้อดีและข้อเสียแตกต่างกันไปขึ้นอยู่ กับการเลือกให้เหมาะสมกับข้อมูลแต่ละชนิด
การเรียลำดับอย่างมีประสิทธิภาพต้องคำนึงถึง
- เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม
วิธีการเรียงลำดับ
วิธีการเรียงลำดับสามารถแบ่งออกได้ 2 วิธี
การเรียงลำดับแบบเลือก
เป็น วิธีที่ง่าย แต่เสียเวลาในการจัดเรียงนาน โดยจะทำการเลือกข้อมูลมาเก็บไว้ตามตำแหน่งที่กำหนด คือ กำหนดให้เรียงข้อมูลจากค่าน้อยไปหาค่ามาก ก็จะทำการเลือกข้อมูลตัวที่มีค่าน้อยที่สุดมาอยู่ที่ตำแหน่งแรกสุด และค่าที่อยู่ตำแหน่งแรกก็จะมาอยู่แทนที่ค่าน้อยสุด แล้วทำการเลือกไปเรื่อยๆ จนครบทุกค่า ค่าที่ได้ก็จะเรียงจากน้อยไปหามาก
ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละ
ตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับ
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มค่าน้อยที่สุดมาเก็บ
ไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่
ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทงครบทุกคำ
ในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการ
เป็น การเรียงลำดับโดยเปรียบเทียบข้อมูลที่อยู่ติดกัน โดยจะทำการเปรียบเทียบคู่ไหนก่อนก็ได้ คือ ถ้าข้อมูลอยู่ในตำแหน่งที่ไม่ถูกต้องก็จะทำการสลับตำแหน่งกัน การเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมากนัก นิยมใช้เนื่องจากเข้าใจง่าย
การเรียงลำดับแบบเร็ว
เป็น วิธีที่ใช้เวลาน้อย เหมาะกับข้อมูลที่มีจำนวนมาก โดยจะเลือกข้อมูลมาหนึ่งค่ามาเป็นค่าหลัก ถ้าเป็นการเรียงจากค่าน้อยไปหาค่ามาก แล้วให้ตำแหน่งที่ 1 เป็นค่าหลัก ทำการเปรียบเทียบจากตำแหน่งท้ายไปเรื่อยๆ จนเจอค่าที่น้อยกว่าค่าหลัก แล้วทำการสลับตำแหน่งกัน หลังจากสลับตำแหน่งให้นำค่าหลักเปรียบเทียบกับข้อมูลตำแหน่งที่ 2,3 จนพบข้อมูลที่มีค่ามากกว่าค่าหลักแล้วทำการสลับตำแหน่งกัน ทำลักษณะนี้เรื่อยๆจนข้อมูลเรียงถูกต้อง
การเรียงลำดับแบบแทรก
เป็น วิธีที่พิจารณาเลขที่ละหลัก โดยจะพิจารณาเลขหลักหน่วยก่อน แล้วทำการจัดเรียงข้อมูลทีละตัวตามกลุ่มหมายเลข จากนั้นนำข้อมูลที่จัดเรียงในหลักหน่วยมาจัดเรียงในหลักสิยต่อไปเรื่อยๆจน ครบทุกหลัก ก็จะได้ข้อมูลที่ต้องการ การเรียงลำดับแบบฐานไม่ซับซ้อน แต่ใช้เนื้อที่ในหน่วยความจำมาก
วันอังคารที่ 8 กันยายน พ.ศ. 2552
DTS09-02-09-2552
EXPRESSION TREE
เป็น การนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งตและโหนดเก็บ Operator และ Operand ของนิพจน์คณิตศาสตร์ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ เมื่อแทนนิพจน์ต่างลงในทรีต้องคำนึงถึงลำดับขั้นตอนในการคำนวณตามความสำคัญ ของเครื่องหมายด้วย โดยมีความสำคัญ คือ ฟังก์ชัน วงเล็บ ยกกำลัง เครื่องหมายหน้าเลขจำนวน(unary) คูณหรือหาร บวกหรือลบ ตามลำดับ และถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
ในการแทนนิพจน์ใน expression tree นั้น operand จะเก็บอยู่ที่โหนดใบ ส่วน operator จะเก็บในโหนดกิ่ง หรือโหนดที่ไม่ใช่โหนดใบ
BINARY SEARCH TREE
เป็น ไบนารีทรีที่ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อย ก็จะมีคุณสมบัติเช่นเดียวกัน
ปฏิบัติการเพิ่มโหนดหรือดึงโหนดออกจาก Binary Search Tree ค่อนข้างยุ่งยาก เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้วต้องคำนึงถึงความเป็น Binary Search Tree ของทรีนั้นด้วย ซึ่งสามารถทำได้ดังนี้
1. การเพิ่มโหนด ถ้าทรีว่างโหนดที่เพิ่มเข้าไปก็จะเป็นโหนดรากของทรี แต่ถ้าทรีไม่ว่างต้องทำการตรวจสอบก่อนว่าโหนดใหม่ที่เพิ่มเข้าไปมีค่า มากกว่าหรือน้อยกว่าโหนดราก ให้เปรียบเทียบตามคุณสมบัติที่กล่าวไว้ข้างต้น
2. การดึงโหนดออก ซึ่งหลังจากที่ดึงออกแล้วนั้นต้องคงความเป็น Binary Search Tree ไว้ ก่อนที่จะทำการดึงโหนดต้องค้นหาก่อนว่าโหนดที่ต้องการจะดึงออกอยู่ที่ ตำแหน่งไหนภายในทรี สามารถพิจารณาได้เป็น 3 กรณีคือ
ก.) กรณี่เป็นโหนดใบ สามารถดึงออกได้เลยทันที โดยให้ค่าในลิงค์ฟิลด์ของโหนดแม่ซึ่งเก็บที่อยู่ของโหนดที่ต้องการดึงออกให้ มีค่าเป็น Null
ข.) กรณีที่มีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง โดยใช้วิธีเดียวกับการดึงโหนดออกจากลิงค์ลิสต์ โดยให้โหนดแม่ของโหนดที่จะดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
ค.) กรณีที่มีทั้งทรีย่อยทางซ้ายและทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูกดึงออก โดยถ้าโหนดที่มาแทนที่เป็นหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือกโหนดที่มี ค่ามากที่สุดในทรีย่อยทางซ้ายนั้น แต่ถ้าเลือกโหนดจากทรีย่อยทางขวาต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อย ทางขวานั้น
กราฟ (Graph)
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหา ที่ค่อนข้างซับซ้อนเช่น การวางข่าย งานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
นิยามของกราฟกราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟ ที่มีเอ็จเชื่อมระหว่างโหนดสองโหนดถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่ากราฟแบบไม่มีทิศทาง (Undirected Graphs)และถ้ากราฟนั้นมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วย เรียกกราฟนั้นว่า กราฟแบบมีทิศทาง(Directed Graphs)บางครั้งเรียกว่า ไดกราฟ (Digraph)ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้
การแทนกราฟในหน่วยความจำ สิ่ง ที่ต้องการจัดเก็บก็คือ เอ็จ ซึ่งเป็นเส้นเชื่อมระหว่างโหนดสองโหนด วิธีที่ง่ายคือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะเป็นการเปลืองเนื้อที่เพราะบางเอ็จมีการเก็บซ้ำ แต่สามารถแก้ปัญหานี้ได้โดยมิติแรกเก็บโหนดต่างๆ แล้วใช้พอยเตอร์ชี้ไปยังความสัมพันธ์กับโหนดในมิติ 2 แต่เป็นวิธีที่ยุ่งยาก ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา
การท่องไปในกราฟ (graph traversal) คือกระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ
ทำ งานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียวแต่ในกราฟระ หว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่อง หมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal)วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด
อื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
2. การท่องแบบลึก (Depth First Traversal)การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไป สู่ปลายวิถีนั้น จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด
วันพุธที่ 2 กันยายน พ.ศ. 2552
DTS08-26-08-2552
โดยทั่วไปแต่ละโหนดในทรีจะมีความ สัมพันธ์กับโหนดในระดับที่ต่ำลงมาหนึ่งระดับได้หลาย ๆ โหนด หรืออาจกล่าวได้ว่าแต่ละโหนดของทรีเป็น "โหนดแม่" (parent or mother node) ของ "โหนดลูก" (child or son node) ซึ่งเป็นโหนดที่อยู่ในระดับต่ำลงมาหนึ่งระดับโดยสามารถมีโหนดลูกได้หลาย ๆ โหนด และโหนดต่าง ๆ ที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า "โหนดพี่น้อง" (siblings) ทุก ๆ โหนดต้องมีโหนดแม่เสมอยกเว้นโหนดในระดับสูงสุดไม่มีโหนดแม่เรียกโหนดนี้ว่า "โหนดราก" (root node) โหนดที่ไม่มีโหนดลูกเลยเรียกว่า "โหนดใบ" (leave node) และเส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า "กิ่ง" (branch) สังเกตได้จากตัวอย่าง แสดงระดับของทรีและส่วนต่าง ๆ ของทรี
ทรี คือ กราฟที่ต่อเนื่องกันโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น ทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น การเขียนรูปแบบทรีอาจเขียนได้ 4 แบบ คือ
(2) "ทรีที่มีแบบแผน" (ordered tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน
(3) "ทรีคล้าย" (similar tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกันนั่นเองโดยไม่คำนึงถึงข้อมูลที่อยู่ใน แต่ละโหนด
(4) "ทรีเหมือน" (equivalent tree) หมายถึง ทรีที่เหมือนกันโดยสมบูรณ์ (equivalence) โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
(5) "กำลัง" (degree) หมายถึง จำนวนทรีย่อยของโหนดนั้น ๆ
(6) "ระดับของโหนด" (level of node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความ จำหลักสามารถแทนที่แบบสแตติก หรือแบบไดนามิกก็ได้ โดยมีพอยน์เตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์หลายลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ จำนวนลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรีซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการเป็นอย่างยิ่ง มีวิธีการแทนที่ทรีในหน่วยความจำหลายวิธี วิธีที่ง่ายที่สุดคือทำให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์เท่ากัน
(1) ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
(2) ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
(3) จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี
ปฏิบัติ การที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (traversing binary tree) เพื่อเข้าไปเยือนทุก ๆ โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้ง วิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการ เยือนอย่างไรในการเยือนแต่ละครั้ง โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L) หรือทรีย่อยทางขวา (แทนด้วย R) มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นซึ่งลักษณะการนิยามเป็นนิยามแบบรีเคอร์ซีฟ (recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. "การท่องไปแบบพรีออร์เดอร์" (preorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี NLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์
2. "การท่องไปแบบอินออร์เดอร์" (inorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์
3. "การท่องไปแบบโพสออร์เดอร์" (postorder traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรี ด้วยวิธี LRN ซึ่งมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสออร์เดอร์
(3) เยือนโหนดราก
วันอังคารที่ 11 สิงหาคม พ.ศ. 2552
DTS07-06-08-2552
เป็น โครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ ซึ่งมีลักษณะที่ว่า ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง ขึ้นอยู่กับลำดับการเก็บข้อมูล จะ
การดำเนินการพื้นฐานของ Queue ได้แก่
- การนำข้อมูลเข้าสู่ Queue เรียกว่า enqueue
- การนำข้อมูลออกจาก Queue เรียกว่า dequeue
- การนำข้อมูลที่อยู่ตอนต้นของ Queue มาแสดง เรียกว่า queue front
ข้อควรคำนึงถึง คือ ในขณะที่คิวเต็ม (Full Queues) หรือไม่มีช่องว่างเหลืออยู่ จะไม่สามารถนำข้อมูลเข้าไปเก็บในโครงสร้างคิวได้อีก ซึ่งจะทำให้เกิดปัญหา “Overflow” ขึ้น
1. เมื่อมีข้อมูลเข้าสู่คิว ให้ตรวจสอบว่าคิวเต็มหรือไม่ ถ้าคิวเต็มไม่ให้มีการรับข้อมูล
2. ถ้าคิวไม่เต็มให้เลื่อนตำแหน่งพอยน์เตอร์ R แล้วนำข้อมูลเข้าสู่คิว
3. ตรวจสอบเงื่อนไขว่าถ้าเป็นข้อมูลตัวแรกในคิว ให้เปลี่ยนพอยน์เตอร์ F ให้ชี้ค่าแรก
การนำข้อมูลออกจากโครงสร้างคิว (dequeue)
เป็นการลบ ข้อมูลออกจากโครงสร้างคิวทางด้านหน้า ของโครงสร้างคิว โดยมีพอยน์เตอร์ F เป็นพอยน์เตอร์ชี้บอกตำแหน่งที่ข้อมูลอยู่ เมื่อมีการลบข้อมูล ออกจากโครงสร้างคิวเรียบร้อยแล้ว พอยน์เตอร์ F จะเลื่อนตำแหน่ง ไปยังตำแหน่งถัดไป
ข้อควรคำนึงถึง คือ เมื่อคิวว่าง (Empty queue) หรือไม่มีข้อมูลเหลืออยู่ จะไม่สามารถนำข้อมูลออกจากคิวได้อีก ซึ่ง จะทำให้เกิดปัญหา “underflow” ขึ้น
1. ตรวจสอบว่าเป็นคิวว่าง (Empty Queues) หรือไม่
2. ถ้าคิวไม่ว่างให้นำข้อข้อมูลออกจากคิว ณ ตำแหน่งที่ F ชี้อยู่ จากนั้นก็ทำการเลื่อนตำแหน่งพอยน์เตอร์ F ไปยังตำแหน่งถัดไป
3. ถ้ามีข้อมูลอยู่เพียงตัวเดียว ให้กำหนดให้พอยน์เตอร์ F และ R เป็นศูนย์ (0)
การแสดงข้อมูลตอนต้นของคิว (Queue Front)เป็น การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง แต่จะไม่มีการเอาข้อมูลออกจากคิว ซึ่งประโยชน์ของมันก็คือ สามารถทำให้เรารู้ว่า คิวถัดไป (next queue)
ในกรณีที่เป็นคิวแบบวงกลม คิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อยๆ จนกระทั่ง rear มีค่าน้อยกว่า front อยู่ 1 ค่า คือ rear = front - 1
วันอังคารที่ 4 สิงหาคม พ.ศ. 2552
DTS06-29-07-2552
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก นั้นคือ หน่วยความจำจะถูกจัดสรรเมื่อมีการขอใช้จริง ๆ ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด pointer
2. การแทนที่ของมูลของสแตกแบบอะเรย์ ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบสแตติก นั้นคือ จะมีการกำหนดขนาดของสแตกล่วงหน้าว่าจะมีขนาดเท่าใดและจะมีการจัดสรรเนื้อที่หน่วยความจำให้เลย
การดำเนินการเกี่ยวกับสแตก
1. Create stack จัดสรรหน่วยความจำให้แก่ head node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push stack โดยทั่วไปจะกระทำที่ต้นลิสต์ซึ่งถือว่าเป็นตำแหน่งโหนดบนสุดของสแตกหรือเป็นตำแหน่งที่พุชโหนดเข้าไปในสแตกหลังสุด เมื่อมีการพุชโหนดใหม่ลงในสแตกก็จะต้องปรับค่าพอยน์เตอร์ของโหนดใหม่ชี้ไปที่โหนดบนสุดในขณะนั้น และถ้า top เป็นพอยน์เตอร์ชี้ที่ตำแหน่งโหนดบนสุดในสแตก ให้ทำการปรับพอยน์เตอร์ top ชี้ไปที่โหนดใหม่ที่ทำการพุชลงไปแทน
3. Pop stack โหนดแรกที่จะถูกพ็อปออกมาคือโหนดที่อยู่บนสุดหรือโหนดแรกของลิงค์ลิสต์นั่นเอง ก่อนที่จะทำการพ็อปโหนดต้องตรวจสอบก่อนว่าสแตกว่างหรือไม่ โดยตรวจสอบจากค่าพอยน์เตอร์ที่ชี้ตำแหน่งโหนดบนสุดของสแตก ถ้ามีค่าเป็นนัลแสดงว่า สแตกว่าง และถ้าสแตกไม่ว่างก็สามารถทำการพ็อปโหนดออกจากสแตกได้
4. Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack (เป็นการคัดลอกโดยไม่มีการลบข้อมูลออกจากสแตก)
5. Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่ ถ้าไม่มีข้อมูลสแตกเหลืออยู่ เราก็ไม่สามารถทำการ Pop สแตกได้ ในกรณีเช่นนี้เรียกว่า "สแตกว่าง" (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่าสแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้
6. Full stack ตรวจสอบว่า stack เต็มหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ Push สแตกได้ ในกรณีเช่นนี้เราเรียกว่า "สแตกเต็ม" (Stack Overflow) โดยการตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของสแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูลอีก
7. Stack count ส่งค่าจำนวนรายการในสแตก หรือเป็นการนับจำนวนสมาชิกในสแตก
8. Destroy stack คืนหน่วยความจำของทุก node ในสแตกให้ระบบ หรือเป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การแทนที่ข้อมูลของสแตกแบบอะเรย์ เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่แน่นอน (static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการ นำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกัน ไปตามพื้นที่ที่กำหนด
การดำเนินการเกี่ยวกับสแตก
1. Create stack สร้าง stack head node
2. Push stack เพิ่มรายการใน stack
3. Pop stack ลบรายการใน stack
4. Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack
5. Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่
6. Full stack ตรวจสอบว่า stack เต็มหรือไม่
7. Stack count ส่งค่าจำนวนรายการใน stack
8. Destroy stack คืนหน่วยความจำของทุก node ใน stack ให้ระบบ
การประยุกต์ใช้สแตก
สแตกเป็นโครงสร้างข้อมูลที่มีประโยชน์มาก ใช้มากในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด และข่าวสารที่เก็บเป็นอันดับล่าสุดและรอง ๆ ลงมาใช้ก่อน เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการทำงานของโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์คณิตศาสตร์ และรีเคอร์ชัน (recursion) เป็นต้น
1. การทำงานของโปรแกรมที่มีโปรแกรมย่อย
การทำงานของโปแกรมหลักที่เรียกใช้โปรแกรมย่อย และในแต่ละโปรแกรมย่อยมีการเรียกใช้โปรแกรมย่อยต่อไปอีก ลักษณะของปฏิบัติการแบบนี้ โครงสร้างข้อมูลแบบสแตกสามารถช่วยทำงานได้ โดยที่แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บเลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยนั้นแล้ว จะทำการ popค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อยนั้น จนกระทั่งโหนดในสแตกว่าง
2. การคำนวณนิพจน์ทางคณิตศาสตร์การเขียนนิพจน์คณิตศาสตร์เพื่อการคำนวณจะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วย โดยทั่วไปนิพจน์คณิตศาสตร์สามารถเขียนได้ 3 รูปแบบดังนี้
1. นิพจน์อินฟิกซ์ (infix expression) การเขียนนิพจน์ด้วยรูปแบบนี้ ตัวดำเนินการ (operator) อยู่ตรงกลางระหว่างตัวถูกดำเนินการ (operand) 2 ตัว
2. นิพจน์โพสฟิกซ์ (postfix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ก่อน ตามด้วยตัวดำเนินการ
3. นิพจน์พรีฟิกซ์ (prefix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวดำเนินการก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ตามลำดับ
วันจันทร์ที่ 27 กรกฎาคม พ.ศ. 2552
DTS05-22-07-52
- โครงสร้างข้อมลแบบลิงค์ลิสต์
- กระบวนงานและฟังกชันทที่ใช้ดำเนินงานพื้นฐาน
- การสร้างลิงค์ลิสต์
- ลิงค์ลิสต์แบบซับซ้อน
ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่าง ๆ โดยมพอยเตอร์เป็นตัวเชื่อมต่อ
แต่ละอิลลเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คอ Data จะเก็บข้อมูลของอิลิเมนท์
และส่วนที่สอง คอ Link Field จะทำหน้าที่เก็บตฎแหน่งของโนดต่อไปในลิสต์
การดำเนินการเกี่ยวกับสตริง จะใช้คำสั่ง #include ในการเรียกใช้ เช่น
- ฟังก์ชัน strlen(str) ใช้หาความยาว
- ฟังก์ชัน strcpy(str1, str2) ใช้คัดลอกข้อมูล จากตัวที่ 2 ไปให้ตัวที่ 1
- ฟังก์ชัน strcat(str1, str2) ใช้เชื่อมต่อข้อความ เช่น ตัวแปร 1 เก็บ ชื่อ ตัวแปร 2 เก็บ นามสกุล แล้วนำตัวแปรทั้ง2 มาต่อกัน
- ฟังก์ชัน stecmp(str1, str2) ใช้ปรียบเทียบข้อความ 2 ข้อความว่ามีค่าเท่ากันหรือไม่ ยึดตามหลักพจนานุกรม
โครงสร้างข้อมูลแบบลิงค์ลิสต์
จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure ประกอบด้วย Count, Pos และ head แสดงได้ดังภาพ
2. Data Node Structure ประกอบด้วย Data และ Pointer ที่ชี้ไปยังข้อมูลตัวถัดไป แสดงได้ดังภาพ
กระบวนงานและฟังก์ชันที่ใช้ดำเนินงานพื้นฐาน
1. Create List มีหน้าที่สร้างลิสต์ว่าง ผลลัพธ์ที่ได้คือ ลิสต์ว่าง และ count จะมีค่าป็น 0
2. Insert Node มีหน้าที่เพิ่มข้อมูลลงไปในลิสต์ในตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ลิสต์ ข้อมูล และตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะมีค่าเป็น 1 หรือ 2.....n ตามจำนวนของการ insert
3. Delete Node มีหน้าที่ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ข้อมูลและตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะลดจำนวนจากเดิมลงเรื่อย ตามจำนวนลิสต์ที่ลบไป
4. Search list มีหน้าที่ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ ผลลัพธ์ที่ได้ จะเป็นค่าจริงถ้าพบข้อมูล และจะเป็นค่าเท็จถ้าไม่พบข้อมูล
5. Traverse ทำหน้าที่ท่องหรือเยือนไปในลิสต์เพื่อเข้าถึงและประมวลผลนำเข้า ผลลัพธ์ที่ได้จะขึ้นอยู่กับการประมวลผล อย่างเช่น การรวมฟิลด์ในลิสต์ การเปลี่ยนแปลงค่าในโนด การคำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น
6. Retrieve Node ทำหน้าที่หาตำแหน่งของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้ก็คือ ตำแหน่งข้อมูลที่อยู่ในลิสต์ และเมื่อรู้ตำแหน่งก็ดึงค่าที่ได้มาแสดงในโปรแกรม
7. EmptyList ทำหน้าที่ทดสอบดูว่า ลิสต์ว่างหรือไม่ ผลลัพธ์ที่ได้คือ เป็นจริงและเป็นเท็จ กล่าวคือ จะเป็นจริงก็ต่อเมื่อลิสต์ว่าง และจะเป็นเท็จก็ต่อเมื่อลิสต์ไม่ว่าง
8. FullList ทำหน้าที่ในการทดสอบว่าลิสต์เต็มหรือไม่ ผลลัพธ์ที่ได้คือ เป็นจริงและเป็นเท็จ กล่าวคือ จะเป็นจริงก็ต่อเมื่อหน่วยความจำเต็ม และจะเป็เท็จก็ต่อเมื่อลิสต์นั้นสามารถมีโนดอื่น
9. List Count ทำหน้าที่นับจำนวนของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้คือ จำนวนข้อมูลที่อยู่ในลิสต์นั้นๆ ซึ่งจะใช้ค่า count ที่อยู่ใน Head Node ออกมาแสดง
10. Destroy List ทำหน้าที่ในการลำลายลิสต์ หรือหยุดใช้ลิสต์นี้แล้ว
Linked List แบบซับซ้อน มี 2 แบบ
สแตก stack
สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทําที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) และ ลักษณะที่สําคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนําออกมา จากสแตกเป็นลําดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
การดําเนินงานพื้นฐานของสแตกการทํางานต่าง ๆ ของสแตกจะกระทําที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตําแหน่งข้อมูลบนสุดของสแตกด้วยการทํางานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สําคัญ
คือ1.Push คือ การนําข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก
ในการเพิ่มข้อมูลลงในสแตก จะต้องทําการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตําแหน่งให้ไปชี้ที่ตําแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม้สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก
2. Pop คือ การนําข้อมูลออกจากส่วนบนสุดของสแตก เช่น ต้องการนําข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนําข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1 ตัว แล้วนําสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทําการ pop สแตก จะทําให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow เพราะฉะนั้นก่อนนําข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนําข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตําแหน่งให้ไปชี้ตําแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนํา ออกไป
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นําเอาข้อมูลนั้นออกจากสแตก
ตัวอย่างการทำงานแบบโครงสร้างข้อมูลแบบสแตกที่สามารถเห็นได้ในชีวิตประจำวันทั่วไป ได้แก่
- การใส่เสื้อผ้าเราจะต้องเริ่มใส่เสื้อผ้าที่อยู่ด้านในสุดก่อน และเมื่อเราจะถอดเสื้อผ้าเราก้อจะต้องเริ่มถอดจากชิ้นนอกก่อนเสมอถอดไล่จากชิ้นนอกไปจนถึงชิ้นในสุดเพราะเราไม่สามารถที่จะถอดชิ้นที่อยู่ด้านในออกก่อนได้
- การหยิบน้ำดื่มจากตู้แช่ตามร้านสะดวกซื้อต่างๆ ซึ่งผู้ซื้อจะต้องหยิบน้ำดืมขวดที่อยู่ด้านนอกสุด ซึ่งเป็นขวดสุดท้านในการนำเข้าในตู้แซ่
- การหยิบรถเข็นในห้างสรรพสินค้า
วันอังคารที่ 21 กรกฎาคม พ.ศ. 2552
DTS04-15-07-52
เซ็ตเป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน ในภาษาซีจะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้ตัวดำเนินการของเซ็ต (Set operators)ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้นสตริง (String) หรือ สตริงของอักขระ (Character String) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง การประยุกต์ใช้คอมพิวเตอร์ที่เกี่ยวกับข้อมูลที่เป็นสตริง มีการนําไปใช้สร้างโปรแกรมประเภทบรรณาธิการข้อความ(text editor) หรือโปรแกรมประเภทประมวลผลคํา (wordprocessing) ซึ่งมีการทํางานที่อํานวยความสะดวกหลายอย่าง เช่น การตรวจสอบข้อความ การจัดแนวข้อความในแต่ละย่อหน้าและการค้นหาคํา เป็นต้นสตริงกับอะเรย์สตริง คือ อะเรย์ของอักขระ เช่น char a[6]อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ หรือเป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character เช่นchar a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};char a[ ]=“HELLO”;
ความยาวของสตริง จะถูกกำหนดโดยขนาดของสตริง การกำหนดขนาดของสตริงนั้นต้องจองเนื้อที่ในหน่วยความจำให้กับ \0ด้วย เช่น“This is String !”
จะเป็นข้อมูลแบบสตริงยาว 16 อักขระ
การกำหนดสตริงการกำหนดสตริงทำได้หลายแบบ คือ
1. กำหนดเป็นสตริงที่มีค่าคงตัว(String Constants)
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์
การกำหนดค่าคงตัวสตริงสามารถกำหนดได้ทั้งนอกและในฟังก์ชัน เมื่อกำหนดไว้นอกฟังก์ชัน ชื่อค่าคงตัวจะเป็นพอยเตอร์ชี้ไปยังหน่วยความจำที่เก็บสตริงนั้น เมื่อกำหนดไว้ในฟังก์ชัน จะเป็นพอยเตอร์ไปยังหน่วยความจำที่เก็บตัวมันเองการกำหนดค่าให้กับสตริงนั้น เราจะใช้เครื่องหมาย double quote (“ ”) เช่น “abc” คือ ชุดของอักขระที่มีขนาด 4(รวม \0 ด้วย)
วันอังคารที่ 30 มิถุนายน พ.ศ. 2552
DTS03-01-07-2552
เรื่อง Set and String
Pointer ตัวแปร pointer เป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งที่อยู่ของตัวแปร
สามารถอ้างอิงกลับไปกลับมาได้ มีขนาด 2 ไบต์เท่ากันหมด ไม่ว่าจะเป็น
char,int,floatหรืออื่นๆในการประกาศตัวแปร pointer จะต้องนำหน้าด้วย
เครื่องหมาย * เช่น int*x เป็นตัวแปร pointer
เครื่องหมาย & เป็นเครื่องหมายที่บอกตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำ
ในกรณีที่ตัวแปรใดมีเครื่องหมาย & นำหน้าจะไม่สามารถนำมาคำนวณได้
ตัวอย่าง
int *ptr,count เป็นการประกาศตัวแปร ptr เป็นตัวแปร pointer
และประกาศตัวแปร count
count = 100 เป็นการกำหนดค่าให้กับ count มีค่าเท่ากับ 1
00ptr = &count เป็นการกำหนดค่าให้กับ ptr มีค่าเท่ากับตำแหน่งที่อยู่ของ count
ถ้าต้องการทราบว่า *ptr มีค่าเท่าไหร่หาได้จาก ณ ตำแหน่งที่ ptr เก็บอยู่
คือตำแหน่งที่เท่าไหร่แล้วดูว่าที่ตำแหน่งนั้นมีค่าเท่ากับเท่าไหร่
Set
เป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย ตัวดำเนินการของเซ็ต ประกอบด้วย
1.set intersection
2.set union
3.set difference
String
เป็นข้อมูลที่ประกอบด้วย ตัวอักษร ตัวเลข หรือเครื่องหมายที่เรียงติดต่อกัน
ความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง ในการจองเนื้อที่นั้น ต้องทำการจองเนื้อที่ให้กับ \0 ด้วย
วันเสาร์ที่ 27 มิถุนายน พ.ศ. 2552
DTS02-24-06-2552
เรื่อง Array and Record
-การดําเนินการเกี่ยวข้องกับอะเรย์ 1 มิติ หลายมิติ
-การส่งค่าของอะเรย์ ในโปรแกรม และฟังก์ชัน
-การดําเนินการที่เกี่ยวข้องกับ เรคคอร์ด
-ความสัมพันธ์ระหว่าง เรคคอร์ด กับอะเรย์ และอะเรย์ชนิดโครงสร้าง
อะเรย์เป็นโครงสร้างข้อมูลที่เรียกว่า Linear List มีลักษณะคล้ายเซ็ตในคณิตศาสตร์ คือ อะเรย์จะประกอบด้วยสมาชิกที่มีจํานวนคงที่ มีรูปแบบข้อมูลเป็นแบบเดียวกัน สมาชิกแต่ละตัวใช้เนื้อที่จัดเก็บที่มีขนาดเท่ากัน เรียงต่อเนื่องในหน่วยความจําหลัก
การกำหนด Array
อะเรย์จะต้องกําหนดชื่ออะเรย์ พร้อม subscript ซึ่งเป็นตัวกําหนดขอบเขตของอะเรย์ มีได่มากกว่า 1 ตัว จํานวน subscript จะเป็น ตัวบอกมิติของอะเรย์นั้น อะเรย์ที่มี subscript มากกว่า 1 ตัวขึ้นไป จะเรียกว่า อะเรย์หลายมิติ การกําหนด subscript แต่ละตัวจะประกอบไปด้วย ค่าสูงสุดและ ค่าต่ําสุดของ subscript นั้น
ข้อกําหนดของการกําหนดค่าต่ำสุดและค่าสูงสุดของ subscript คือ
1.ค่าต่ำสุดต้องมีค่าน้อยกว่าหรือเท่ากับค่าสูงสุดเสมอ
2.ค่าต่ำสุด เรียกว่า ขอบเขตล่าง (lower bound)
3.ค่าสูงสุด เรียกว่า ขอบเขตบน (upper bound)
ขนาดของ index แต่ละตัว ของ Array หาได้จาก
(ขนาดของ subscript = upper bound – lower bound + 1)
จํานวนสมาชิกหรือขนาดของอะเรย์ n มิติ หาได้จาก
(ขนาดของอะเรย์ = ผลคูณของขนาดของsubscript แต่ละตัว)
อะเรย์ 1 มิติ
อะเรย์ 2 มิติ
รูปแบบของอะเรย์ 1มิติ
data-type array-name[expression]
data-type คือ ประเภทของข้อมูลอะเรย์ เช่น inchar float
array-name คือ ชื่อของอะเรย์
expression คือ นิพจน์จำนวนเต็มซึ่งระบุจำนวนสมาชิกของอะเรย์
ตัวอย่าง char a[4]; int num[10];
การประกาศอาร์กิวเมนต์ในฟังก์ชันเป็นอะเรย์
1. มีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า
2. ไม่ต้องมีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า
3. ตัวแปรที่ทำหน้าที่รับค่าถูกกำหนดเป็นพอยน์เตอร์
รูปแบบของอะเรย์ 2 มิติ
type array-name[n] [m];
type หมายถึง ชนิดของตัวแปรที่ต้องการประกาศเป็นอะเรย์
array-name หมายถึง ชื่อของตัวแปรที่ต้องการประกาศเป็นอะเรย์
n หมายถึง ตัวเลขที่แสดงตำแหน่งของแถว
m หมายถึง ตัวเลขที่แสดงตำแหน่งของคอลัมน์
ตัวอย่าง
หมายถึง คอมพิวเตอร์จะจองเนื้อที่ในหน่วยความจำ จำนวน 6 ที่สำหรับตัวแปร a กำหนดค่าเริ่มต้นได้หลายลักษณะ
ตัวอย่าง
กำหนดค่าเริ่มต้นให้ int a[2][3]
int a[2][3] = {1,2,3,4,5,6}; หรือ
int a[2][3] = {{1,2,3},{4,5,6}}; หรือ
int a[][3] = {{1,2,3},{4,5,6}};
Record or Structure
Structure คือ โครงสร้างที่สมาชิกแต่ละตัวมีประเภทข้อมูลแตกต่างกันได้ โดยที่ใน structure อาจมีสมาชิกเป็นจํานวนเต็ม ทศนิยม อักขระ อะเรย์หรือพอยเตอร์ หรือแม้แต่ structure ด้วยกันก็ได้
struct เป็นคําหลักที่ต้องมีเสมอ
struc-nameชื่อกลุ่ม structure
type ชนิดของตัวแปรที่อยู่ในกลุ่ม structure
name-n ชื่อของตัวแปรที่อยู่ในกลุ่ม structure
struc-variable ชื่อตัวแปรชนิดโครงสร้าง
คือ ตัวแปรที่มีโครงสร้าง เหมือนกับที่ประกาศไว้ในชื่อของกลุ่ม structure อาจมีหรือไม่มีก็ได้ถ้ามีมากกว่า 1 ชื่อ แยกกันด้วยเครื่องหมายคอมม่า (,)
การผ่าน structure ให้ฟังก์ชัน ประเภทของการส่งผ่าน structure ให้ฟังก์ชันนั้น มี่ 2 ประเภท คือ
1. ส่งสมาชิกแต่ละตัวของ structure
2. ส่งทั้ง structure
1. ส่งสมาชิกแต่ละตัวของ structureสมาชิกแต่ละตัวของ structure สามารถส่งเป็นอาร์กิวเมนต์ ของฟังก์ชันและส่งกลับจากฟังก์ชันได้โดยใช้ค่าส่ง return ซึ่งมีทั้งการส่งค่าของตัวแปรที่อยู่ในตัวแปรstructure และก็ส่งตำแหน่งที่อยู่ของตัวแปรนั้น ๆ ไปยังฟังก์ชัน
2. ส่งผ่านทั้ง structure ให้กับฟังก์ชันจะส่งผ่านในลักษณะของพอยน์เตอร์ไปยัง structure โดยหลักการจะเหมือนกับการส่งผ่านอะเรย์ไปให้ฟังก์ชัน ซึ่งเป็นลักษณะที่เรียกว่า Pass by reference
ส่งงาน
struct notebook
{
char brand[30];
char series[20];
int price;
char cpu[30];
char ram[30];
float lcd;
int hdd;
char cd[10];
}product={"Acer","4935G-742G32Mn/C011",27900, "CORE 2 Duo 2.13 GHz.","2048/667",14.1,320,"DVD-RW"};
จากด้านบนกำหนดให้ notebook เป็นชื่อ structureโดยมีตัวแปร char brand[30] , char series[20] , int price , char cpu[30] , char ram[30] , float lcd , int hdd , char cd[10] โดยมี product เป็นตัวแปรชนิดโครงสร้างข้อมูล ชนิดเดียวกับ notebook
brand[30] = Acer
series[20] = 4935G-742G32Mn/C011
price = 27900
cpu[30] = CORE 2 Duo 2.13 GHz .
ram[30] = 2048/667
lcd = 14.1
hdd = 320
cd[10] = DVD-RW