สรุปครั้งที่8 โครงสร้างข้อมูลและขั้นตอนวิธี

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


นิยามของทรี 
1.นิยามทรีด้วยนิยามของกราฟ
            ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (Loop) ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
            การเขียนรูปแบบทรี เขียนได้ 4 แบบ คือ แบบที่มีรากอยู่ข้างบน,แบบที่มีรากอยู่ข้างล่าง,แบบที่มีรากอยู่ด้านซ้าย,แบบที่มีรากอยู่ด้านขวา
2.นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
            ทรี ประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆเรียกว่า Null Tree และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)

นิยามที่เกี่ยวข้องกับทรี
1.Forest คือ เซตของทรีที่แยกจากกัน
2.Ordered Tree คือ ทรีโหนดต่างๆในทรีนั้นมีความสัมพันธ์ที่แน่นอน
3.ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน (แต่ Data ต่าง)
4.ทรีเหมือน คือ ทรีที่เหมือนกันโดนสมบูรณ์ (Order และ Data เหมือนกัน)
5.Degree คือ จำนวนทรีย่อยของโหนดนั้นๆ
6.Level of Node คือ ระยะทางในแนวดึงของโหนดนั้นๆ ที่อยู่ห่างจากโหนดราก ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใดๆบวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใดๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง หรือ ความลึก

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

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

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

สรุปครั้งที่7โครงสร้างข้อมูลและขั้นตอนวิธี

Queue
         คิว เป็นโครงสร้างข้อมูลแบบเชิงเส้น ซึ่งการเพิ่มข้อมูลจะกระทำที่ส่วนท้าย (rear) และการนำข้อมูลออกจะกระทำที่ปลายส่วนหน้า(front) ลักษณะการทำงานของคิวเป็นลักษณะเข้าก่อนออกก่อน (FIFO : First In First Out)

การดำเนินการเกี่ยวกับคิว
1. Create Queue จัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า Pointer ทั้ง2 ตัวมีค่าเป็น Null และจำนวนสมาชิกเป็น0
2. Enqueue การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue การนำข้อมูลออกจากคิว
4. Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว

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

สรุปครั้งที่6 โครงสร้างข้อมูลและขั้นตอนวิธี

Stack (ต่อ)


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


การคำนวณนิพจน์ทางคณิตศาสตร์ สามารถเขียนได้ 3รูปแบบ
      1.นิพจน์ Infix (Operator จะอยู่ตรงกลางระหว่าง Operand)
      2.นิพจน์ Postfix (จะต้องเขียน Operand ตัวที่1 และตัวที่2 ก่อน แล้วตามด้วย Operator) 
      3.นิพจน์ Prefix(จะต้องเขียน Operator ก่อนแล้วตามด้วย Operand ตัวที่1 และตัวที่2)


ค่าลำดับความสำคัญของตัวดำเนินการ

Operator	ค่าเมื่ออ่านเข้ามา	ค่าในสแตก
+,-	1	2
*,/	3	4
(	5	0
)	0	-

ขั้นตอนการแปลงจากนิพจน์Infix เป็นนิพจน์Postfix
      1.อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
      2.ถ้าเป็นOperand จะถูกย้ายไปเป็นตัวอักษรในนิพจน์Postfix
      3.ถ้าเป็นOperator จำนำค่าลำดับความสำคัญของOperatorที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของOperatorที่อยู่บนสุดของสแตก
   - ถ้ามีความสำคัญมากกว่า จะถูกPushลงไปในสแตก
   - ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้องPop Operator ที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์Postfix
               4. Operatorที่เป็น")" จะไม่Push ลงในสแตก แต่มีผลให้Operatorตัวอื่นๆถูกPop ออกจากสแตกนำไปเรียงต่อกันในนิพจน์Postfix จนกว่าจะเจอ "(" จะPop "(" ออกจากสแตกแต่ไม่นำไปเรียงต่อ
               5. เมื่อทำการอ่านตัวอักษรในนิพจน์Infix หมดแล้ว ให้ทำการPop Operator ทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix


ขั้นตอนในการคำนวณจากนิพจน์Postfix
      1.อ่านตัวอักษรในนิพจน์Postfix จากซ้ายไปขาทีละตัวอักษร
      2.ถ้าเป็นOperand ให้ทำการPush Operandนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
      3.ถ้าเป็นOperator ให้ทำการPop ค่าออกจากสแตก 2 ค่า โดยตัวแรกเป็นOperand ตัวที่1 และตัวที่2 ตามลำดับ
      4.ทำการคำนวณ
      5.ทำการPush ผลลัพธ์ที่ได้จากการคำนวณ
      6.ถ้าตัวอักษรในนิพจน์Postfix ยังไม่หมดให้กลับไปทำข้อ1ใหม่

สรุปครั้งที่5 โครงสร้างข้อมูลและขั้นตอนวิธี

Linked List (ต่อ)
       กระบวนงาน Delete Node
             หน้าที่    ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ
             ข้อมูลนำเข้า  ข้อมูลและตำแหน่ง
             ผลลัพธ์  ลิสต์ที่มีการเปลี่ยนแปลง

       กระบวนงาน Search list

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

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

             ผลลัพธ์  ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พอข้อมูล
     *ค่าที่ได้ต้องเป็นค่าเดียวเท่านั้น ไม่ถูกก็ผิด

       กระบวนการทำงาน Traverse

             หน้าที่    ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์

             ผลลัพธ์  ขี้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน Node,รวมฟิลด์ในลิสต์,คำนวณค่าเฉลี่ยนของฟิลด์ เป็นต้น

       กระบวนการทำงาน Retrieve Node

             หน้าที่     หาตำแหน่งข้อมูลจากลิสต์

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

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

       ฟังก์ัชั่น  Empty List

             หน้าที่     ทดสอบว่าลิสต์ว่าง

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

             ผลลัพธ์  เป็นจริง ถ้าลิสต์ว่าง เป็นเท็จ ถ้าลิสต์ไม่ว่าง

       ฟังก์ัชั่น  Full List

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

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

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

       ฟังก์ัชั่น  List Count

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

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

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

        *ถ้าเป็นใน Array จะหาได้ใน int count อยู่ใน Head structure

       กระบวนงาน Destroy List

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

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

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

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

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

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

_______________________________________________________________________

Stack

          Stack เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวกัน เรียกว่า Top Of Stack ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จาดสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO

การดำเนินงานพื้นฐานของสแตก ประกอบไปด้วยกระบวนการ 3 กระบวนการที่สำคัญ คือ

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

       2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก ถ้าสแตกมีสมาชิกเพียง 1 ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง คือ ไม่มีสมาชิกอยู่ในอตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จำทำให้เกิดความผิดพลาดที่เรียกว่า Stack Underflow

       3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ จะประกอบไปด้วย 2 ส่วน คือ

       1. Head Node จะประกอบไปด้วย 2 ส่วน คือ Top pointer และ Count

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

การดำเนินการเกี่ยวกับสแตก 

1. Create Stack (การสร้างสแตก)

2. Push Stack (การเพิ่มข้อมูลลงในสแตก)

3. Pop Stack (การนำข้อมูลออกจากสแตก)

4. Stack Top (การคัดลอกสแตก)

5. Empty Stack (เช็คStackว่าง)

6. Full Stack (เช๊คStackเต็ม)

7. Stack Count (นับจำนวนสมาชิกที่อยู่ใน data node นับแล้วเอามาไว้ที่ Head Nod)

8. Destroy Stack (การทำลายสแตก)

สรุปครั้งที่4 โครงสร้างข้อมูลและขั้นตอนวิธี

Linked List
          ลิงค์ลิสต์ เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของelementต่างๆ โดยมี Pointerเป็นตัวเชื่อมต่อ
          แต่ละ element เรียกว่า Node ซึ่งในแต่ล่ะโหนดจะประกอบไปด้วย 2 ส่วน คือ Data จะเก็บข้อมูลของ element และส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์
          ในส่วนของ data อาจจะเป็นรายการเดี่ยว หรือเป็นเรคคอร์ดก็ได้
          ในส่วนของ Link จะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไปในโหนดสุดท้ายจะเก็บค่า Null ซุ่งไม่ได้ชี้ไปยังตำแหน่งใดๆ เป็นตัวบอกการสิ้นสุดของลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์  จะแบ่งเป็น 2 ส่วน คือ
          1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่ จำนวนโหนดในลิสต์ (Count) Pointerที่ชี้ไปยังโหนดที่เข้าถึง (Pos) และPointer ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ (Head)
          2. Data Node Structure จะประกอบไปด้วยข้อมูล และ Pointerที่ชี้ไปยังข้อมูลถัดไป
กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน
          1. กระบวนงาน Create List
                    หน้าที่     สร้างลิสต์ว่าง
                    ผลลัพธ์  ลิสต์ว่าง
          2. กระบวนงาน Insert Node
                    หน้าที่            เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการ
                    ข้อมูลนำเข้า ลิสต์ ข้อมูล และตำแหน่ง
                    ผลลัพธ์         ลิสต์ที่มีการเปลี่ยนแปลง

สรุปครั้งที่3 โครงสร้างข้อมูลและขั้นตอนวิธี

Array and Record

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

ที่มีขนาดเท่ากัน เรียงต่อเนื่องในหน่วยความจำหลัก

การกำหนด Array

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

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

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

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

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

อะเรย์ 1 มิติ

รูปแบบ

data-type array-name[expression]

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

array-name คือ ชื่อของอะเรย์

expression คือ นิพจน์จำนวนเต็มซึ่งระบุจำนวนสมาชิกของอะเรย์

การส่งอะเรย์ให้ฟังก์ชัน

สามารถกำหนดอะเรย์เป็นพารามิเตอร์ส่งให้กับฟังก์ชันได้ 2 ลักษณะ

1. การกำหนด array element เป็นพารามิเตอร์ส่งค่าให้กับฟังก์ชัน ทำได้โดยอ้างถึงชื่ออะเรย์พร้อมระบุSubscript

2. ส่งอะเรย์ทั้งชุดให้ฟังก์ชันทำได้โดยอ้างถึงชื่ออะเรย์โดยไม่มีSubscript

การประกาศอาร์กิวเมนต์ในฟังก์ชันเป็นอะเรย์

ถ้าเป็นอะเรย์มิติเดียว สามารถทำได้ทั้งหมด 3 วิธี

1. มีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า

2. ไม่ต้องมีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า

3. ตัวแปรที่ทำหน้าที่รับค่าถูกกำหนดเป็นพอยน์เตอร์

อะเรย์ 2 มิติ

รูปแบบ

type array-name[n] [m];

type หมายถึง ชนิดของตัวแปรที่ต้องการประกาศเป็นอะเรย์

array-name หมายถึง ชื่อของตัวแปรที่ต้องการประกาศเป็นอะเรย์

n หมายถึง ตัวเลขที่แสดงตำแหน่งของแถว

m หมายถึง ตัวเลขที่แสดงตำแหน่งของคอลัมน์

Record or Structure

เป็นโครงสร้างข้อมูลที่ประกอบขึ้นมาจากข้อมูลพื้นฐานต่างประเภทกัน รวมเป็น 1 ชุดข้อมูล คือจะประกอบด้วย data element หรือ field ต่างประเภทกันอยู่รวมกัน ในภาษา C ก็คือการกำหนดข้อมูลเป็นรูปแบบของ Structure

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

การนิยาม structure

รูปแบบ struct   struc-name {

 type name-1;

 type name-2;

 ………

 type name-n;

 } struc-variable;

struct เป็นคำหลักที่ต้องมีเสมอ

struc-name ชื่อกลุ่ม structure

type ชนิดของตัวแปรที่อยู่ในกลุ่ม structure

name-n ชื่อของตัวแปรที่อยู่ในกลุ่ม structure

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

การอ้างถึงตัวแปรที่อยู่ในตัวแปรชนิดโครงสร้าง

สามารถอ้างถึงตัวแปรที่อยู่ในตัวแปรชนิดโครงสร้างได้

รูปแบบ

struct-variable.element-name

struct-variable ชื่อตัวแปรชนิดโครงสร้าง

element-name ชื่อตัวแปรที่อยู่ภายใน structure

Structure กับ pointer

เราสามารถที่จะอ้างถึงที่อยู่เริ่มต้นของ structure ได้เหมือนกับตัวแปรอื่น ๆ โดยใช้ตัวดำเนินการ & ดังนั้น ถ้า variable เป็นตัวแปรประเภท structure &variable จะเป็นเลขที่อยู่เริ่มต้นของตัวแปร นอกจากนี้ยังสามารถประกาศตัวแปรพอยน์เตอร์สำหรับ structure ดังนี้

type *ptvar

type คือ ประเภทข้อมูลที่เป็น structure

ptvar คือ ชื่อของตัวแปรพอยน์เตอร์

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

ptvar = &variable

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

รูปแบบ

type *variable-name

type หมายถึง ชนิดของตัวแปร

* หมายถึง เป็นเครื่องหมายที่แสดงว่า ตัวแปรที่ตามหลังเครื่องหมายนี้เป็นตัวแปรพอยน์เตอร์

variable-name เป็นชื่อของตัวแปรที่ต้องการประกาศว่าเป็นชนิดพอยน์เตอร์

Set and String

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

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

- set intersection

- set union

- set difference เป็นต้น

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

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

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

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

ความยาวของสตริง จะถูกกำหนดโดยขนาดของสตริง การกำหนดขนาดของสตริงนั้นต้องจองเนื้อที่ในหน่วยความจำให้กับ \0 ด้วย เช่น “This is String !” จะเป็นข้อมูลแบบสตริงยาว 16 อักขระ

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

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

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

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

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

สามารถกำหนดค่าคงตัวสตริงให้พอยเตอร์หรืออะเรย์ได้ในฐานะค่าเริ่มต้น เช่น

            main ( ) {

           char ary [ ] = “This is the house.”;

           char *cpntr= “This is the door.” ;

          printf(“%s %s”,ary,cpntr);

          }

 ผลการรันโปรแกรม

This is the house. This is the door. จะเห็นได้ว่าการใช้งานดูไม่ต่างกันแต่ ary เป็นตัวแปรอะเรย์ ค่าที่ให้จะต้องเป็นค่าข้อมูลในอะเรย์ ส่วน cpntr เป็นพอยเตอร์ ค่าที่ให้นั้นไม่ใช่ค่าข้อมูล แต่เป็นค่าแอดเครสเริ่มต้นของสตริง (ค่าคงตัวสตริงเป็นทั้งข้อมูลสตริงและพอยเตอร์ ) นอกจานี้ ยังสามารถเพิ่มลดค่าตัวแปรพอยเตอร์ได้ แต่สำหรับ อะเรย์ทำไม่ได้

การกำหนดตัวแปรสตริง

ในการกำหนดตัวแปรของสตริง อาศัยหลักการของอะเรย์ เพราะ สตริงก็คืออะเรย์ของอักขระที่ปิดท้ายด้วย null character (\0) และมีฟังก์ชันพิเศษสำหรับทำงานกับสตริงโดยเฉพาะ

การกำหนดตัวแปรสตริง

            อาศัยหลักการของอะเรย์  เพราะ สตริงก็คืออะเรย์ของอักขระที่ปิดท้ายด้วย null character (\0) และมีฟังก์ชันพิเศษสำหรับทำงานกับสตริงโดยเฉพาะ เช่น ต้องการสตริงสำหรับเก็บชื่อบุคคลยาวไม่เกิน 30 อักขระ ต้องกำหนดเป็นอะเรย์ขนาด 31 ช่อง เพื่อเก็บ null character อีก 1 ช่อง

ฟังก์ชัน gets ( ) เป็นฟังก์ชันที่อ่านค่าจากแป้นพิมพ์มาเก็บไว้ในหน่วยความจำ

อะเรย์ของสตริง

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

อะเรย์ของสตริงที่ยาวไม่เท่ากัน  : ทำได้เฉพาะเมื่อมีการกำหนดค่าเริ่มต้นเท่านั้น

ฟังก์ชัน puts ( ) ใช้ในการพิมพ์สตริงออกทางจอภาพ โดยการผ่านค่าแอดเดรส ของสตริงไปให้เท่านั้น

ข้อสังเกต

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

อะเรย์ของสตริงที่ยาวเท่ากัน

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

สรุปครั้งที่2 โครงสร้างข้อมูลและขั้นตอนวิธี

ในการเขียนโปรแกรมคอมพิวเตอร์ จะมีการแทนที่ข้อมูลในหน่วยความจำหลักอยู่ 2 วิธี คือ

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

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

คำถาม: ภาษาขั้นตอนวิธีกับภาษาธรรมชาตินิยมใช้ภาษาใดมากกว่ากัน?

สรุปครั้งที่1. โครงสร้างข้อมูลและขั้นตอนวิธี

โปรแกรมที่สำคัญในวิชาโครงสร้างข้อมูลและขั้นตอนวิธี
1. Microsoft Visual Basic V.6
2. Turbo C++

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

คำถาม : ภาษาVisual Basic มีความสำคัญอย่างไร ?

My Computer ^^

My suggestion

I think we should have WiFi faster than.