DTS05/28-07-2552

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

DTS04/15-07-2009

สรุป set and string มีโครงสร้างอยู่ 2 แบบ คือ โครงสร้างข้อมูลแบบเซ็ตและโครงสร้างข้อมูลแบบสตริง
โครงสร้างข้อมูลแบบเซ็ต เป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน ในภาษาซีจะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้
โครงสร้างข้อมูลแบบสตริง สตริง (String) หรือ สตริงของอักขระ (Character String) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง การประยุกต์ใช้คอมพิวเตอร์ที่เกี่ยวกับข้อมูลที่เป็นสตริงมีการนำไปใช้สร้างโปรแกรมประเภทบรรณาการข้อความหรือโปรแกรมประเภทประมวลผล
การกำหนดสตริง
การกำหนดสตริงทำได้หลายแบบ คือ 1. กำหนดเป็นสตริงที่มีค่าคงตัว 2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์
การกำหนดค่าคงตัวสตริง
สามารถกำหนดได้ทั้งนอกและในฟังก์ชัน เมื่อกำหนดไว้นอกฟังก์ชัน ชื่อค่าคงตัวจะเป๋นพ้อยเตอร์ชี้ไปยังหน่วยความจำที่เก็บสตริงนั้น เมื่อกำหนดไว้ในฟังก์ชัน จะเป็นพอยเตอร์ไปยังหน่วยความจำที่เก็บตัวมันเอง
การกำหนดตัวแปรสตริง
ในการกำหนดตัวแปรของสตริง อาศัยหลักการของอะเรย์เพราะ สตริงคืออะเรยืของอักขระที่ปิดท้ายด้วย null character (\0) และมีฟังชันพิเศษสำหรับทำงานกับสตริงโดยเฉพาะ
อะเรย์ของสตริง
ถ้าหากมีสตริงจำนวนมาก ก็ควรจะทำให้เป็นอะเรย์ของสตริง เพื่อที่จะเขียนโปรแกรมได้สะดวก
การสร้างอะเรย์ของสตริง สามารถสร้างได้ทั้งแบบที่ให้ค่าเริ่มต้นและแบบที่กำหนดเป็นตัวแปร
ฟังก์ชัน puts () ใช้ในการพิมพ์สตริงออกทางจอภาพ โดยการผ่านค่าแอดเดรสของสตริงไปให้เท่านั้น ข้อสังเกต การกำหนดอะเรย์ของสตริงในลักษณะอย่างนี้ ไม่ใช่อะเรย์ที่แท้จริงตามหลักการของอะเรย์ เนื่องจากขนาดของช่องในอะเรย์ไม่เท่ากัน แต่อนุโลมให้ถือว่าเป็นอะเรย์
อะเรย์ของสตริงที่ยาวเท่ากัน
อะเรย์ในลักษณะนี้จะถือว่าเป็นอะเรย์ที่แท้จริงและสามารถกำหนดได้ทั้งเมื่อมีการให้ค่าเริ่มต้น และเมื่อกำหนดเป็นตัวแปร โดยดำเนินการตามแบบการกำหนดอะเรย์ 2 มิติ
การกำหนดตัวแปรในลักษณะนี้ จะแตกต่างจากการกำหนดตัวแปรแบบความยาวไม่เท่ากัน คือ ในแบบความยาวไม่เท่ากัน ท้ายของสตริงจะเติม null character ให้เพียงตัวเดียว แต่ในแบบความยาวเท่ากัน จะเติม null character ให้จนครบทุกช่อง
การดำเนินการเกี่ยวกับสตริง
ในการดำเนินการเกี่ยวกับสตริง จะมีฟังก์ชันที่อยู่ในแฟ้ม ข้อมูล stdio.h เก็บอยู่ใน C Libraly อยู่แล้วสามารถนำมาใช้ได้ โดยการใช้คำสั่ง #include ในการเรียกใช้ เช่น
- ฟังก์ชัน strlen(str) ใช้หาความยาวของสตริง
- ฟังก์ชัน strcpy(str1,str2) ใช้คัดลอกข้อมูลจาก string หนึ่งไปยังอีก string หนึ่ง
- ฟังก์ชัน strcat(str1,str2) ใช้เชื่อมต่อข้อความ 2 ข้อความเข้าด้วยกัน
- ฟังก์ชัน strcmp(str1,str2) ใช้เปรียบเทียบข้อความ 2 ข้อความว่ามีค่าเท่ากันหรือไม่ ถือหลักการเปรียบเทียบแบบพจนานุกรม