สรุปบทเรียนวิชา โครงสร้างข้อมูลและขั้นตอนวิธี ครั้งที่ 6 วันที 26 กรกฎาคม 2554

สรุปบทเรียนวิชา โครงสร้างข้อมูลและขั้นตอนวิธี ครั้งที่ 5 วันที 17 กรกฎาคม 2554

Linked List  (ต่อ)

4. กระบวนงาน Search list

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

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

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

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

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

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

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

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

7. ฟังก์ชั่น EmptyList

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

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

8. ฟังก์ชั่น FullList

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

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

9. ฟังก์ชั่น list count

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

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

10. กระบวนงาน destroy list

       หน้าที่ ทำลายลิสต์   ข้อมูลนำเข้า ลิสต์

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

การสร้าง Linked List

คำถาม  อธิบายการเก็บข้อมูลและความสำคัญของโครงสร้างข้อมูลแบบลิงค์ลิสต์ 

Stack

สรุปบทเรียนวิชา โครงสร้างข้อมูลและขั้นตอนวิธี ครั้งที่ 4 วันที 5 กรกฎาคม 2554

Set and String (ต่อ)

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

สตริงกับอะเรย์
สตริง คือ อะเรย์ของอักขระ  เช่น char a[6]
อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ หรือ เป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character เช่น
                   char a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};
                   char a[ ]=“HELLO”;

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

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

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

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

อะเรย์ของสตริงที่ยาวไม่เท่ากัน
    ทำได้เฉพาะเมื่อมีการกำหนดค่าเริ่มต้นเท่านั้น
เช่น
         #define N 4
         main ( ) {
         char *contry[N]={“Thailand”, “United State of Ameica”,
         “England”, “Indonesia”};
         int a;
         for (a=0; a<N;a++)
         puts(contry[a]);
         }

ผลการรันโปรแกรม
         Thailand
         United State of America
         England
         Indonesia

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

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

การดำเนินการเกี่ยวกับสตริง
   ในการดำเนินการเกี่ยวกับสตริง จะมีฟังก์ชันที่อยู่ในแฟ้ม ข้อมูล stdio.h เก็บอยู่ใน C Library อยู่แล้ว
สามารถนำมาใช้ได้ โดยการใช้คำสั่ง #include ในการเรียกใช้ เช่น
- ฟังก์ชัน strlen(str) ใช้หาความยาวของสตริง
- ฟังก์ชัน strcpy (str1,str2) ใช้คัดลอกข้อมูลจาก string หนึ่งไปยังอีก string หนึ่ง

- ฟังก์ชัน strcat(str1,str2) ใช้เชื่อมต่อข้อความ 2 ข้อความเข้าด้วยกัน
- ฟังก์ชัน strcmp(str1,str2 ) ใช้เปรียบเทียบข้อความ 2 ข้อความว่ามีค่าเท่ากันหรือไม่ ถือหลักการ
เปรียบเทียบแบบพจนานุกรม เช่น abcda จะมีค่าน้อยกว่า abcde และ abcdf จะมีค่ามากกว่า abcde ค่าที่เท่ากัน คือ ค่าที่เหมือนกัน เช่น abcd กับ abcd สำหรับอักษรตัวเล็กตัวใหญ่ จะถือว่าอักษรตัวใหญ่มีค่าน้อยกว่าอักษรตัวเล็ก ตามลำดับรหัส ASCII


คำถาม   อธิบายหลักการที่ใช้ในการกำหนดตัวแปรของสตริง







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

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

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

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

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

โหนดที่เข้าถึง (Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ (Head)

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

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

1. กระบวนงาน Create List

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

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

2. กระบวนงาน Insert Node

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

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

3. กระบวนงาน Delete Node

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

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