DTS08 26/08/2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง ทรี(Tree)
ทรีเป็นกราฟแบบมีทิศทาง ที่มีโครงสร้างแบบลำดับชั้น ทิศทางของกราฟที่แทนทรีจะมีทิศทางจากบนลงล่าง ดังนั้นการกวาดทรี เราจึงไม่นิยมแสดงทิศทางของเส้นเชื่อม
การให้นิยามในรูปของการเรียกซ้ำซึ่งสอดคล้องกับลักษณะธรรมชาติ ของทรี ดังนี้ คือ ทรีประกอบด้วยโหนด R ซึ่งเรียกว่า โหนดราก (root) และ ทรีย่อย (subtree) จำนวนศูนย์ หรือมากกว่าศูนย์ ซึ่งแต่ละทรีย่อยจะเชื่อมกับโหนดราก (R)โดยตรงด้วยเส้นเชื่อม
การเรียกชื่อองค์ประกอบของทรี
โหนดที่อยู่ระดับบนสุดของทรี เรียกว่า โหนด R ,โหนดราก, พ่อ (father)
โหนดรากของทรีย่อยของ R เรียกว่า ลูก (child) ของ R
โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (leaf node)
เส้นเชื่อมโหนดทรี เรียกว่า กิ่ง (branch)
โหนดที่มีทั้งพ่อทั้งลูก เรียกว่า โหนดกิ่ง (branch node)
โหนดที่มีพ่อเดียวกัน เรียกว่า โหนดพี่น้อง (sibling) และยังอาจนิยามโหนดว่าเป็น โหนดปู่ (grandfather) หรือ โหนดหลาน (gtrandchild) ได้ในลักษณะเดียวกัน
เส้นทาง (path) จากโหนด n1 ไปยังโหนด nk ใดๆ จะเป็นลำดับของโหนด n1,n2,...,nk
ความยาว (length) ของเส้นทางจะเป็นจำนวนของเส้นเชื่อมที่อยู่ในเส้นทาง ซึ่งเท่ากับ k-1 เส้นทาง จากโหนดใดๆ ไปยังตัวเองจะมีความยาวเป็ยศูนย์ และในทรีแต่ละทรี จะมีเส้นทางหนึ่งเส้นเท่านั้นจากโหนดรากไปยัง โหนดใดๆ ความลึก (depth) เป็น ความยาวของเส้นทางจากโหนดรากไปยังโหนด n โซึ่งมีเส้นทางเดียวที่ไม่ซ้ำกัน) ความสูง (height) เป็น เส้นทางทีสุดจากโหนด n ไปยังโหนดใบถ้ามีเส้นทางจาดโหนด n1 ไปยังโหนด n2 จะเป็น บรรพบุรุษ (ancestor) ของ n2 และ n2 จะเป็น ลูกหลาน (descendant) ของ n1 ถ้า n1 != n2 ดังนั้น n1 จะเป็น บรรพบุรุษที่แท้จริง (proper ascestor) ของ n1 และ n2 ลูกหลานที่แท้จริง (proper descendant)
ทรีแบบลำดับ
ทรีแบบราก (rooted tree ) เป็นทรีที่สามารถวาดได้อิสระ โดยเชื่อมโหนดในระดับต่ำลงไป และมีโหนด ใบอยู่ในระดับล่าง มีโครงสร้างไม่เหมาะสมก่การใช้งาน เนื่องจากวิธีการเรียกชื่อโหนดจากลำดับซ้ายไปขวา "ทรีแบบลำดับ (ordered tree)" คือ ทรีแบบรากที่โหนดลูกของแต่ละโหนดถูกกำหนดลำดับดังรูป ถ้าต้องการจะใช้ทรีแบบลำดับเป็นโครงสร้างข้อมูล ในแต่ละโหนดจะต้องมีจำนวนเขตข้อมูลมากพอๆ กับจำนวน ของโหนดนั้น ดังนั้นถ้ามีบางโหนดในทรีมีจำนวนทรีมากกว่า 10 ทรีย่อย จะต้องมีเขตข้อมูลสำหรับลิงค์ของ แต่ละโหนดถึง 10 เขต ซึ่งแต่ละเขตลิงค์ต่างๆ เหล่านี้ส่วนใหญ่จะมีค่าเป็น NULL ซึ่งทำให้เนื้อที่จำนวนมาก ไม่ได้ใช้งาน
ไบนารีทรี
ไบนารีทรี เป็น ทรีว่าง หรือทรีที่ประกอบด้วยโหนดรากที่เรียกว่า ราก กับ ไบนารีทรี 2 ทรี เรียกว่า ทรีย่อยทางซ้าย (left subtree) และ ทรีย่อยทางขวา (right subtree) ของราก การสร้างไบนารีทรี ที่มีโหนดเดียว สามารถสร้างโหนดนั้นเป็นโหนดรากที่มีทรีย่อยทางซ้าย และทรีทางขวาเป็นทรีว่าง จะเห็นว่าไบนารีทรีแตก ต่างจากทรีทั่วไป เนื่องจากในไบนารีทรี ความหมายของคำว่า ซ้าย หรือ ขวา มีความสำคัญ ไบนารีทรี 2 โหนด ดังนั้นไบนารีทรีสามรถได้มาจากทรีแบบลำดับที่เหมาะสมกัน โดยการแยกกิ่งทางซ้ายออกจากกิ่งทางขวา
การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี
ไบนารีทรีเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพ แต่มีข้อจำกัดว่า แต่ละโหนดมีลูกได้ไม่เกิน 2 และในการประยุกต์ ใช้งานส่วนใหญ่ โครงสร้างข้อมูลเป็นจำนวนใดๆ ได้ตามใจ การเปลี่ยนทรีทั่วไปเป็นไบนารีทรี เริ่มต้นจะเชื่อมโหนด แต่ละโหนดกับโหนดลูกซ้ายสุดของโหนดนั้น ซึ่งเรียกว่าโหนดแรก ต่อมาเชื่อมแต่ละโหนดยกเว้นโหนดรากกับโหนดถัดไป ที่มีพ่อเดียวกัน(พี่น้อง) ซึ่งเรียกว่าเชื่อมโหนดลูกถัดไป
เพื่อให้โครงสร้างของไบนารีทรีที่ดีกว่านี้ จะต้องหมุนทรีเล็กน้อยตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมที่ชี้ลงล่าง ชี้ลงไปทางซ้าย และเส้นเชื่อมที่ชี้ตามแนวนอน ชี้ลงไปข้างล่างทางขวา
ป่าและสวน
ป่า (forest) หมายถึงของทรีที่เป็นทรีแบบรก และ สวน (orchard) หมายถึง ชุดของทรีแบบลำดับ แต่โดยทั่วไป แล้วป่ากับสวนมีความหมายเดียวกัน คือ ชุดของทรีทั่วไป
สามารถสร้างป่าหรือสวนได้ โดยการขจัดรากออกไปจากทรีแบบราก หรือแบบลำดับและทำนองเดียวกัน สามารถแปลง จากป่าแสวนไปเป็นไบนารีทรีได้มีขั้นตอนดังต่อไปนี้
1.ขจัดเส้นเชื่อมเดิมออก
2.แปลงทรีแต่ละต้นให้เป็นไบนารีทรี
3.เชื่อมโหนดรากของทรีเขาด้วยกัน ในแนวนอนโดยใช้ความสัมพันธ์พี่น้อง
4.หมุนทรีที่ได้ 45 องศาตามเข็มนาฬิกา ซึ่งจะทำให้เส้นเชื่อมในแนวตั้งกลายเป็นเส้นเชื่อมทางซ้าย และเส้นเชื่อมในแนวนอนกลายเป็นเส้นเชื่อมทางขวา
การท่องไบนารีทรี (traversal of binary tree)
เป็นการเคลื่อนที่ไปยังโหนดทุกโหนดของไบนารีของทรี หรือการเยี่ยมโหนดทุกโหนดของทรี ในข้อมูลแบบทรีโหนด ทุกโหนดที่จะท่องมีลำดับแตกต่างกัน ที่โหนดใด ไๆที่กำหนดให้จะต้องมีการกระทำ 3 อย่าง ในลำดับใดๆ คือ
1. เยี่ยมโหนดนั้น
2. ท่องไปยังทรีย่อยทางซ้ายของโหนดนั้น
3. ท่องไปยังทรีย่อยทางขวาของโหนดนั้น
จุดสำคัญของของการท่องไบนารีทรีคือ จะเยี่ยมททรีย่อยก่อนการท่องทรีย่อยที่มีอยู่ หรือจะเยี่ยมโหนดนั้นใน ระหว่างการท่องทรีย่อยของโหนดนั้น หรือจะเยี่ยมดหนดนั้นในระหว่างการท่องทรีย่อยภายหลังจากการท่องทรีย่อย ทั้งสองของโหนดนั้นเสร็จเรียบร้อยแล้ว

DTS07-05/08/2552

สรุปเรื่อง Queue

Queue เป็น List แบบเชิงเส้น (Linear Data Structure) เช่นเดียวกับ Stack แต่มีความแตกต่างกันคือ Queue มีตัวชี้ 2 ตัว คือ
–หัว (Head)
–ท้าย (Tail)
คิวเป็นโครงสร้างข้อมูลแบบหนึ่งซึ่งมีลักษณะที่ว่า ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง ขึ้นอยู่กับลำดับการเก็บข้อมูล จะเรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO)
โครงสร้างข้อมูลแบบนี้เป็นโครงสร้างที่ปรากฏอยู่โดยทั่วๆ ไป โดยเฉพาะอย่างยิ่งในระบบปฏิบัติการคอมพิวเตอร์ ในระบบคมนาคม รวมทั้งในระบบการทดลองดาวเทียมด้วย
ลักษณะของโครงสร้างแบบคิวจะเหมือนกับการเข้าแถวรอคอย ไม่ว่าจะเป็นการรอคอยอะไรก็ตาม หรือจะเรียกสั้นๆ ว่า เข้าคิวก็ได้ ด้วยคุณสมบัติที่เด่นชัดของการทำงานของโครงสร้างข้อมูลแบบคิวนี้ ว่าสิ่งใดที่เข้าก่อนย่อมต้องได้รับการทำงานก่อน เช่น การสั่งพิมพ์งานพร้อมกันหลายๆ คน โดยใช้เครื่องพิมพ์เครื่องเดียวกัน ทำให้ระบบจะต้องมีการจัดระบบให้มีการเข้าคิวรอคอยการทำงาน ถ้าใครสั่งพิมพ์ก่อนก็จะเข้าคิวไปรอการพิมพ์ในลำดับแรก ใครสั่งเป็นคนต่อไปก็จะต้องเข้าคิวรอจนกว่างานแรกจะทำการพิมพ์เสร็จ จึงจะมาทำงานกับคิวที่รออยู่ต่อไปการสร้างคิว (Queue)
คิวที่อยู่ในคอมพิวเตอร์สามารถจัดเก็บได้หลายลักษณะ แต่โดยทั่วไปแล้วจะใช้การจัดเก็บแบบลิงค์ลิสท์เดี่ยวหรือจัดเก็บโดยใช้อาร์เรย์
ก่อนที่จะทำการสร้างคิวจะต้องทำความเข้าใจถึงโครงสร้างของคิว ซึ่งประกอบไปด้วย ตัวคิว ซึ่งในที่นี้ขอแทนด้วยอาร์เรย์ และจะต้องมีตัวชี้อีก 2 ตัว ได้แก่ ตัวชี้ F (Front Pointer) ชี้ไปที่สมาชิกตัวแรก และตัวชี้ R (Rear Pointer) ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวจะออกทาง F
เมื่อเริ่มต้นสร้างคิว คิวนั้นไม่มีค่าใดๆ ยังว่างเปล่า F และ R จะมีค่าเป็น 0 ทั้งคู่ คือไม่ได้ชี้ไปที่สมาชิกตัวใด การนำข้อมูลเข้าสู่คิวเรียกว่า การ Insertion ส่วนการนำข้อมูลออกจากคิวเรียกว่า การ Deletion

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

การประยุกต์ใช้คิว
การทำงานของระบบคอมพิวเตอร์ในโลกยุคปัจจุบันจะเป็นการทำงานในลักษณะเครือข่าย และมีการใช้ทรัพยากรร่วมกัน การที่ระบบปฏิบัติการจะจัดสรรทรัพยากรเพื่อให้บริการแก่ผู้ใช้ หรืองานต่าง ๆ อย่างมีประสิทธิภาพ สมดุล และยุติธรรม ชนิดข้อมูลแบบคิวมีความสำคัญมากในการดำเนินงานของระบบปฏิบัติการ ตัวอย่างเช่น ในการใช้ทรัพยากร CPU จากเครื่อง Server หรือการใช้ทรัพยากร System Printer สำหรับผู้ใช้หลายคน ระบบปฏิบัติการจะใช้ชนิดข้อมูลแบบคิวในการจัดระเบียบผู้ใช้

DTS06-28/07/2552

สรุปเรื่อง สแตก (ต่อ)

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

การแปลงจาก infix เป็น postfix Stack มีการทำงานแบบ LIFO ถูกนำมาอธิบายการทำงานของการแปลงจาก infix เป็น postfix อยู่เสมอ โดยพิจารณาน้ำหนักของเครื่องหมายในนิพจน์ และเครื่องหมายที่ถูกกระทำก่อนไปหลังคือ
1. วงเล็บ Parenthesis ()
2. ยกกำลัง Exponentiation ^ (Left to Right)
3. คูณและหาร Multiplication *, Division / (Left to Right)
4. บวกและลบ Addition +, Subtraction - (Left to Right)

กฎเกี่ยวกับการแปลง
1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)
2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค
2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค
2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ push ลงสแตค
2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator ที่เข้ามานั้นลงสแตค
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป
5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง

DTS05-22/07/2552

สรุปบทเรียน Linked ListและStack

Linked List (ต่อ)
กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create Listหน้าที่ สร้างลิสต์ว่างผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Nodeหน้าที่เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการข้อมูลนำเข้า ลิสต์ ข้อมูล และตำแหน่งผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Nodeหน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการข้อมูลนำเข้า ข้อมูลและตำแหน่งผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search listหน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
5. กระบวนงาน Traverseหน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์ผลลัพธ์ ขึ้นกับการประมวลผล เช่นเปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต์ ,คำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Nodeหน้าที่ หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์
7. ฟังก์ชั่น EmptyListหน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่างเป็นเท็จ ถ้าลิสต์ไม่ว่าง
8. ฟังก์ชั่น FullListหน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็มเป็นเท็จ ถ้าสามารถมีโหนดอื่น
9. ฟังก์ชั่น list countหน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน destroy listหน้าที่ ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ผลลัพธ์ ไม่มีลิสต์

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

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

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

การบ้านการใช้ iosteam.h และ stdio.h

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

#include
void main()
{
int N1;
int N2;
int Sum;
printf("Input frist integer number : ");
scanf("%d",&N1);
printf("Input second integer number : ");
scanf("%d",&N2);
Sum = N1 + N2;
printf("So %d + %d = %d",N1,N2,Sum);

}

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

#include
void main()
{
int N1;
int N2;
int Sum;
cout<<"Input frist integer number : "; cin>>N1;
cout<<"Input second integer number : "; cin>>N2;
Sum = N1 + N2;
cout<<"Sum ="<}

DTS04-15/07/2552

สรุปบทเรียน Set and String , Linked List

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

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

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


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


โครงสร้างของโหนด (Node Structure)
เราสามารถนิยามโครงสร้างของโหนดด้วยแบบข้อมูลโครงสร้างซึ่งประกอบด้วยฟิลด์ข้อมูลและฟิลด์พอยเตอร์ดังเช่น
struct Node { char Info;
struct Node *Next;
};
โครงสร้าง Node ประกอบด้วยฟิลด์ Info ซึ่งมีแบบข้อมูล char และฟิลด์ Next ซึ่งเป็นพอยเตอร์ชี้ไปที่ Node จะพบได้ว่าการนิยามโครงสร้าง Node อยู่ในรูปของรีเคอร์สีฟ โดยที่ฟิลด์ Next เป็นพอยเตอร์ที่ชี้ไปยังโครงสร้างของตัวเอง

DTS 03-01/07/2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Pointer ,Set and String


pointer

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

จะคล้ายกับการกำหนดตัวแปรชนิดต่างๆ เพียงแต่ต้องมีเครื่องหมาย * หน้าชื่อตัวแปร ดังนี้

int *pt_X; สร้างตัวแปรพอร์ยเตอร์ชนิดintทำให้pt_xใช้เก็บตำแหน่งที่อยู่ขอตัวแปรชนิดintเท่านั้น
float*pt_num; สร้างตัวแปรพอร์ยเตอร์ชนิดfloatทำให้pt_numใช้เก็บตำแหน่งที่อยู่ของตัวแปรชนิดfloatเท่านั้น
char*pt_ch;สร้างตัวแปรพอร์ยเตอร์ชนิดcharทำให้pt_chใช้เก็บตำแหน่งที่อยู่ของตัวแปรชนิดcharเท่านั้น

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

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

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