Linked List

DTS 04-15-07-2552

ลิงค์ลิสต์
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
การแทรกโหนด และการลบโหนดของรายการโยงคู่ทำได้ง่ายกว่ารายการโยงเดี่ยว เพราะการค้นหาโหนดเป้าหมายไมจำเป็นต้องใช้ตัวชี้ 2 จำนวน ไว้คอยเก็บที่อยู่โหนดก่อนหน้า และโหนดเป้าหมาย ใช้เพียงตัวชี้เดียวก็ดำเนินการได้แล้ว การเยี่ยมโหนดของรายการ แบบวงกลม และรายการโยงคู่ สามารถย้อนกลับไปเยี่ยมโหนดที่เยี่ยมมาแล้วได้ รายการแบบวงกลมใช้วิธีการเยี่ยมโหนดแบบวนรอบ จะวนกี่รอบก็ได้เพราะไม่มีตัวชี้ของโหนดจะเก็บค่า NULL ส่วนรายการโยงคู่ นำตัวชี้ด้านซ้ายมาใช้ประโยชน์ทำให้ย้อนกลับไปหาโหนดที่ผ่านมาได้

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

2. การเพิ่มข้อมูล

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

3.การลบข้อมูล การลบข้มูล หรือลบโหนด มีหลายวิธี ดังต่อไปนี้

ต่ำแหน่งต้นลิสต์

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

และต่ำแหน่งกลางลิสต์

รายการแบบวงกลม ( Circular list )

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

รายการโยงคู่ ( Doubly Linked List )

-แต่ละโหนดจะมีสมาชิกอย่างน้อย 3 ฟิลด์ โดยจะมีฟิลด์ llink และ rlink ทำหน้าที่ชี้ไปยังตำแหน่งของโหนดถัดไป และโหนดก่อนหน้า ดังรูป

-ลิสต์เชื่อมโยงสองทางจะมีตัวแปร head เก็บตำแหน่งของโหนดแรกของลิสต์ โดย llink ของโหนดแรกจะเป็น NULL และ rlink ของโหนดสุดท้าย ก็จะเป็น NULL ด้วยเช่นกัน

การเพิ่มข้อมูล

เป็นการสร้างโหนดใหม่ระหว่างโหนด 2 โหนด

การลบข้อมูล

การลบข้อมูล ควรตรวจสอบสมาชิกก่อน เพื่อให้วางแผนการเขียนค่ำสั่งได้ถูกต้อง การเขียนคำสั่งลบข้อมูล มี 3 แบบ คือ

-แบบไม่มีสมาชิก

-แบบมีสมาชิก 1 จำนวน

-แบบมีสมาชิกมากกว่า 1 จำนวน

แบบฝึกหัดบทที่ 2

1. ให้นักศึกษากำหนดค่าของ Array 1 มิติ และ Array 2 มิติ
ตอบ

อาเรย์ คือชุดของตัวแปร ที่มีชื่อตัวแปรและชนิดตัวแปรเดียวกัน มักใช้กับตัวแปรชนิดเดียวกันหลายๆ ตัว ที่มีการทำงานเหมือนกัน เช่นคะแนนนักศึกษา 20 คน ชื่อทุกกระบวนวิชาที่เปิดสอนภายในภาควิชา (เช่นอาจมี 30 กระบวนวิชา ก็จะมีข้อมูล 30 ชื่อ) เป็นต้น
รูปแบบการประกาศอาเรย์
ชนิดข้อมูล ชื่อตัวแปร [ขนาดข้อมูล];
ตัวอย่าง ต้องการเก็บข้อมูลคะแนนสอบของนักศึกษา 10 คนไว้ในตัวแปร array จะต้องการประกาศตัวแปรอาเรย์ ดังนี้
float score[10];
อาเรย์ 2 มิติ
ข้อมูลในอาเรย์ 2 มิติ จะเป็นลักษณะของตาราง
ซึ่งมีแถวและคอลัมน์
แถว (row)
คอลัมน์ (column)
score[row][column] เช่น score[0][4]
_____________________________

2. ให้นักศึกษาหาค่าของ A[2], A[6] จากค่า A={2,8,16,24,9,7,3,8}
ตอบ A[2] คือ 16A[6] คือ 3

_____________________________

3. จากค่าของ int a[2][3] = {{6,5,4},{3,2,1}};
ให้นักศึกษา หาค่าของ a[1][0] และ a[0][2]
char a[2][3];
col1 col2 col3
row1 a[0][0] =6 a[0][1] =5 a[0][2] =4
row 2 a[1][0] =3 a[1][1] =2 a[1][2] =1

ตอบ ค่าของ a[1][0] = 3
a[0][2] = 4
______________________________
4. ให้นักศึกษากำหนด Structure ที่มีค่าของข้อมูลจากน้อย 6 Records

ตอบ struct Emp

#include
int main() {
struct date {
int day;
int month;
int year;
};
struct person {
char name[30];
int age;
float salary;
struct date bday;
};

______________________________
5. ให้นักศึกษาบอกความแตกต่างของการกำหนดตัวชนิด Array กับ
ตัวแปร Pointer ในสภาพของการกำหนดที่อยู่ของข้อมูล
ตอบ
array หมายถึง ตัวแปรชุดที่ใช้เก็บตัวแปรชนิดเดียวกันไว้ด้วยกัน เช่น เก็บ ข้อมูล char ไว้กับ char เก็บ int ไว้กับ int ไม่สามารถเก็บข้อมูลต่างชนิดกันได้ เช่น char กับ int เรียก array อีกอย่างว่าหน่วยความจำแบ่งเป็นช่อง การกำหนดสมาชิกชิกของ array จะเขียนภายในเครื่องหมาย [ ]
pointer หมายถึง ตัวเก็บตำแหน่งที่อยู่ของหน่วยความจำ (Address) หรือเรียกว่า ตัวชี้ ตำแหน่งที่อยู่ สัญลักษณ์ของ pointer จะแทนด้วยเครื่องหมาย *

array m3[ ] จะเก็บข้อมูลอยู่ใน array มีพื้นที่เก็บข้อมูลเป็นของตัวแปรนี้และชื่อ m3 จะมี ค่า address คงที่ไม่สามารถเปลี่ยนค่าได้ใช้ m3 + 1 ได้ แต่ใช้ m3++ ไม่ได้

pointer *m3 จะชี้ไปที่ที่เก็บข้อมูล จากตัวอย่างข้างต้นจะมีพื้นที่ส่วนหนึ่งที่ใช้ในการเก็บ string ชุดนี้ไว้แล้ว m3 จะชี้ไปที่ address ของพื้นที่นั้น ๆ เราสามารถที่จะทำการเปลี่ยนค่าของ m3 ได้โดยใช้ m3++

______________________________