Record pointer and Linked List

ปัญหาของอะเรย์

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

ตัวอย่าง การประกาศตัวแปรแบบอะเรย์ของจำนวนเต็มในภาษาซี

int a[10]; หมายถึงขอใช้พื้นที่ในหน่วยความจำบริเวณที่เป็น static ขนาดเท่ากับ 20 byte (เนื่องจาก int 1 ตัว จะใช้พื้นที่ 2 byte) และการขอใช้พื้นที่นี้ จะขอใช้ในขณะที่ compile โปรแกรม โดยที่ compiler จะทำการจัดสรรพื้นที่ว่างติดต่อกันขนาด 20 byte ไว้ให้ หลังจากนี้พื้นที่ส่วนนี้จะไม่สามารถนำไปให้ตัวแปรอื่นใช้ได้อีก (ในกรณีที่เราใช้พื้นที่ของอะเรย์ไม่หมด) และเราไม่สามารถขอพื้นที่เพิ่มเติมได้ในกรณีที่ต้องการเพิ่มข้อมูลเข้าไปในอะเรย์ที่มีสมาชิกเต็มทุกเซลล์แล้ว

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

3. ปฏิบัติการที่เกี่ยวข้อง

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

สมมติอะเรย์ a มีข้อมูลในอะเรย์ดังนี้

แล้วเราต้องการเพิ่มข้อมูล B เข้าไปในอะเรย์ โดยให้ B อยู่ในตำแหน่งที่ถูกต้อง เราจะต้องคัดลอกข้อมูลตั้งแต่ D จนถึง K ไปไว้ยัง เซลล์ถัดไปก่อน ดังนี้

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

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

โครงสร้างข้อมูลแบบเรคคอร์ด (Record)

โครงสร้างแบบเรคคอร์ดเป็นโครงสร้างที่ยอมให้มีชนิดของข้อมูลหลายชนิดได้ใน 1 เรคคอร์ด ดังตัวอย่าง

รหัสนักศึกษา ชื่อนักศึกษา คะแนนเก็บครั้งที่1 คะแนนเก็บครั้งที่2 คะแนนเก็บครั้งที่3

char[8]

char[20]

short int

แต่ละช่องของข้อมูลเรียกว่า เขตข้อมูลหรือฟิลด์ (field) ในเรคคอร์ดจะมีกี่ฟิลด์ก็ได้ และแต่ละฟิลด์จะมีชนิดของข้อมูลเป็นชนิดอะไรก็ได้ ทำให้มีความยืดหยุ่นในการจัดเก็บข้อมูล เหมาะที่จะนำไปประยุกต์ใช้งาน ยกตัวอย่างเช่น การจัดเก็บข้อมูลคะแนนของนักศึกษา ที่ต้องการเก็บข้อมูลรหัสนักศึกษาและชื่อนักศึกษาเป็นชุดของตัวอักษร ในขณะที่ข้อมูลคะแนนจะจัดเก็บในรูปแบบของตัวเลข

การเข้าถึงข้อมูลในเรคคอร์ด จะอ้างอิงโดยผ่านชื่อเรคคอร์ดตามด้วยชื่อฟิลด์

การประกาศตัวแปรให้มีโครงสร้างแบบเรคคอร์ด ในภาษาซี ใช้รูปแบบดังนี้

ให้ประกาศชนิดของข้อมูลในส่วนของการประกาศตัวแปรแบบทั่วไป (ใต้ include )

struct type-name { data-type field-name1;

data-type field-name2;

};

หลังจากนั้นใช้ชื่อ type-name ในการประกาศตัวแปรแบบเรคคอร์ด ดังตัวอย่าง

struct stdrec { char id[8];

char name[20];

short int mark1;

short int mark2;

short int mark3; };

main()

{

stdrec student; // หมายถึงประกาศตัวแปรชื่อ student ให้มีชิดเป็น

// stdrec ซึ่งเป็นโครงสร้างแบบเรคคอร์ดที่มี 5 ฟิลด์

scanf(“%s”,&student.id); // การเข้าถึงข้อมูลในเรคคอร์ด

}

ให้นักศึกษาพิจารณาว่าโครงสร้างข้อมูลแบบเรคคอร์ดมีข้อดีเหนืออะเรย์หรือไม่ อย่างไร

โครงสร้างข้อมูลแบบ พอยน์เตอร์ (Pointer)

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

การประกาศตัวแปรให้เป็นแบบพอยน์เตอร์ ในภาษาซี จะใช้รูปแบบดังนี้

data-type *var-name;

ตัวอย่าง

int b;

int *a; // ประกาศให้ตัวแปร a เป็นตัวแปรแบบพอยน์เตอร์ที่เก็บ

// ตำแหน่งของข้อมูลแบบ int

b=50; // ตัวแปร b มีค่า 50

a=&b; // ตัวแปร a เก็บตำแหน่งของตัวแปร b

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

รายการเชื่อมโยง (Linked List)

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

ลักษณะของรายการเชื่อมโยง

แต่ละหน่วยข้อมูลของลิงค์ลิสต์จะถูกเรียกว่าโหนด (node) ซึ่งในแต่ละโหนดจะประกอบไปด้วยอย่างน้อย 2 ฟิลด์ ดังรูป

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

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

ประเภทของรายการเชื่อมโยง

1. รายการเชื่อมโยงทางเดียว (Singly Linked List )

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

ตัวแปร head ใช้สำหรับเก็บตำแหน่งแรก(โหนดแรก)ของลิสต์ และที่โหนดสุดท้ายจะมี Link เป็น NULL หมายถึงไม่ชี้ไปที่ใดเลย

2. รายการเชื่อมโยงสองทาง (Doubly Linked List)

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

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

การเข้าถึงโหนดในรายการเชื่อมโยง (ท่องไปในลิสต์)

การนำข้อมูลจากลิสต์มาใช้งาน ทำได้โดยการเข้าไปที่ head ก่อน จึงจะสามารถ access ข้อมูลของโหนดแรกได้ หากต้องการข้อมูลในโหนดถัดไปก็จะไปตาม link ของโหนดปัจจุบันเรื่อยไป จึงกล่าวได้ว่า การเข้าถึงข้อมูลในโครงสร้างแบบลิสต์เชื่อมโยงนั้นเป็นการเข้าถึงแบบตามลำดับ เช่น ต้องการข้อมูลในโหนดที่ 5 จำเป็นจะต้องเข้าถึงข้อมูลที่โหนด head ก่อน แล้วจึง link ไปยังโหนดที่ 2, 3, 4 แล้วจึงจะไปถึงโหนดที่ 5 ได้

ปฏิบัติการที่เกี่ยวข้องกับรายการเชื่อมโยง

1. รายการเชื่อมโยงทางเดียว

1.1 การเพิ่มโหนดหลังโหนดที่ระบุ (ในที่นี้คือ เพิ่มโหนด n หลังโหนด p)

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

1. link(n) = link(p)

2. link(p) = n

1.2 การลบโหนดหลังโหนดที่ระบุ (ในที่นี้คือ ลบโหนดหลังโหนด n)

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

link(n) = link(link(n))

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

2. รายการเชื่อมโยงสองทาง

2.1 การเพิ่มโหนดหลังโหนดที่ระบุ (ในที่นี้คือ เพิ่มโหนด n หลังโหนด p)

1. rlink(n) = rlink(p)

2. llink(n) = p

3. rlink(p) = n

4. llink(rlink(n))=n

นักศึกษาสามารถทดสอบการเพิ่มโหนดด้วยตนเอง เช่น หากต้องการเพิ่มโหนดหน้าโหนดที่ระบุ (เพิ่มโหนด n หน้าโหนด p) และตรวจสอบผลลัพธ์ได้ที่นี่

2.2 การลบโหนดหลังโหนดที่ระบุ (ในที่นี้คือ ลบโหนดหลังโหนด n)

link(n) = link(link(n))

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