รายการ(List) [1]

อาจารย์สุวิชยะ รัตตะรมย์

สำนักวิชาเทคโนโลยีสารสนเทศและการสื่อสาร

หัวข้อวันนี้

• ADT of List
• Implementation of List (Static memory allocation)
• Link list
• การประกาศโครงสร้าง, ตัวแปร
• การกำหนดค่าให้กับข้อมูล
• วิธีการเชื่อมโยง node เข้าด้วยกัน
• Basic operation of Linked list
• traverse (การท่องไปในลิงค์ลิสต์)
• insert

2

ADT : Value Definition

• โครงสร้างข้อมูลแบบรายการเชิงเส้น (Linear Data Structure) เช่นเดียวกับ stack และ queue
• การเข้าถึงข้อมูลแต่ละตัว ( ไม่ใช่การเพิ่มหรือลบ ) ต้องเป็นการเข้าถึงแบบลำดับ (sequential access)
• เช่น การจะเข้าถึงข้อมูลตัวที่ (ตำแหน่งที่) 5 ในลิสต์ ต้องผ่านข้อมูลตัวที่ (ตำแหน่งที่) 1,2,3,4 ก่อน
• การนำข้อมูลเข้า, นำข้อมูลออก กระทำที่ตำแหน่งใดในโครงสร้างก็ได้

3

ADT : Operation Definition

• operation พื้นฐานสำหรับลิสต์มีดังนี้
• insert – การเพิ่มข้อมูลลงในลิสต์
• delete – การลบข้อมูลออกจากลิสต์
• traverse (การท่องไปในลิสต์) – การเข้าถึงสมาชิกตัวแรกของลิสต์ไปจนถึงตัวสุดท้าย (ตามลำดับ)
• ท่องเพื่อค้นหาข้อมูล, เพิ่มข้อมูล หรือลบข้อมูล ณ ตำแหน่งโหนดใดๆ ในลิสต์

4

Implementation of List�(Static memory allocation)

5

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

6

Example ให้ list1 เป็นลิสต์ของข้อมูลซึ่งเรียงจากน้อยไปหามากซึ่งสร้างจากอาร์เรย์ขนาด 8 ช่อง และมีข้อมูลในลิสต์ ดังนี้

• Insert(3,list1)

7

• delete(2,list1)

ลิงค์ลิสต์ (Linked List)

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

8

• แก้ปัญหาโดยใช้ตัวแปรชนิดชนิด pointer มาช่วย
• เรียกว่า dynamic programming
• เมื่อต้องการใส่ข้อมูลลงในโครงสร้าง
• จองหน่วยความจำเพื่อเก็บข้อมูลนั้น
• เชื่อมโยงกับข้อมูลตัวก่อนหน้าที่อยู่ในโครงสร้างนั้น (ใช้ตัวแปร pointer ช่วยในการโยง)
• การนำพอยน์เตอร์มาช่วยในการสร้างโครงสร้างข้อมูลแบบลิสต์ ซึ่งมีชื่อเรียกเฉพาะว่า ลิงค์ลิสต์

9

โครงสร้างของลิงค์ลิสต์

• ลิงค์ลิสต์ ประกอบด้วยกลุ่มของข้อมูลที่เรียงต่อกันเป็นสาย โดยข้อมูลแต่ละตัวจะเรียกว่า โหนด (node)
• ในแต่ละโหนดจะประกอบด้วยส่วนประกอบ 2 ส่วน คือ
• ส่วนเก็บข้อมูล (data, info) – เป็นส่วนที่ใช้ในการเก็บข้อมูล ซึ่งอาจมีข้อมูลมากกว่าหนึ่งชนิดก็ได้ เช่น ประวัตินิสิต เป็นต้น
• ส่วนที่ชี้ไปยังโหนดถัดไป (next, link) – เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดตัวถัดไป

10

11

ตัวแปร pointer ที่ชี้ตำแหน่ง node แรกในลิงค์ลิสต์

ณ โหนดสุดท้ายตัวชี้จะชี้ไปที่ NULL

12

ตัวอย่างลักษณะการจัดเก็บลิงค์ลิสต์ในหน่วยความจำ

Header

NULL

NULL

การประกาศโครงสร้างข้อมูลชนิดลิงค์ลิสต์

• ในการประกาศโครงสร้างข้อมูลแบบลิงค์ลิสต์เรามักจะประกาศเป็นตัวแปรแบบ structure ที่ประกอบไปด้วยข้อมูล 2 ส่วน คือ data ( ซึ่งอาจประกอบด้วยข้อมูลหลายตัวก็ได้ ) และ next ดังตัวอย่างดังนี้

13

typedef struct list

{

char id[10] ;

int mark ;

struct list *next;

}node;

การประกาศตัวแปรเพื่อใช้งาน

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

14

1. typedef struct list

2. {

3. char id[10] ;

4. int mark ;

5. struct list *next;

6. }node;

7. node *head ;

8. head = (node *)malloc(sizeof(node));

• ที่จำเป็นต้องมีคำสั่งบรรทัดที่ 8 เนื่องจากในขั้นตอนการกำหนดตัวแปรแบบ pointer (บรรทัดที่ 7) ยังไม่มีการจองหน่วยความจำสำหรับให้ pointer นั้นชี้ไป
• ซึ่งถ้าเรานำตัวแปร pointer นี้มาใช้งานทันที เช่น กำหนดค่าให้กับตำแหน่งที่ pointer ชี้อยู่
• ค่าที่ pointer นั้นชี้ไป อาจเป็นส่วนของโปรแกรมอื่นๆ ก็ได้ --> ทำให้เกิดปัญหาขึ้น

15

16

1. typedef struct list

2. {

3. char id[10] ;

4. int mark ;

5. struct list *next;

6. }node;

7. node *head ;

8. if ((head = (node *)malloc(sizeof(node))) == NULL)

9. {

10. print(“Not enough memory”);

11. exit(1);

12. }

ตัวอย่างเพิ่มเติมเพื่อเช็คกรณีจองหน่วยความจำไม่สำเร็จ

17

1. node *newnode(void)
2. {
3. node *s ;
4. if ((s = (node *)malloc(sizeof(node))) == NULL)
5. {
6. print(“Not enough memory”);
7. exit(1);
8. }
9. s = NULL;
10. return s;
11. }

…

node *head ;

head = newnode() ;

*next

mark

id

head

การกำหนดค่าให้กับข้อมูล

18

วิธีการเชื่อมโยง node เข้าด้วยกัน

19

1. typedef struct list
2. {
3. int data ;
4. struct list *next;
5. }node;
6. node *head, *p , *q;
7. head = newnode() ; p = newnode(); q = newnode();
8. head->data = 1; p->data = 2 ; q->data = 3 ;

วิธีการเชื่อมโยง node เข้าด้วยกัน

20

9. head->next = p;
10. p->next = q;
11. q->next = NULL ;

• การแสดงวิธีการเชื่อมโยงลิงค์ลิสต์ที่ผ่านมาเป็นเพียงตัวอย่างง่ายๆ เท่านั้น
• ในการใช้งานจริง ไม่สามารถทำได้ เพราะจำนวนตัวแปรที่กำหนดให้โปรแกรมมีจำกัด ในขณะที่จำนวน node สามารถเพิ่มได้ไม่จำกัด
• จะใช้วิธีการเขียนเป็นฟังก์ชันเพื่อเพิ่มจำนวน node เข้าไปในลิงค์ลิสต์ทีละ 1 node ซึ่งเมื่อทำการเชื่อมโยงแล้ว node อื่นๆ นอกจาก head ไม่จำเป็นต้องมีตัวแปรกำกับ

21

Basic operation of linked list

• การเขียนโปรแกรมเพื่อจัดการกับลิงค์ลิสต์ มีฟังก์ชันหลักๆ ที่ต้องสนใจอยู่ 3 ส่วน คือ
• traverse (การท่องไปในลิงค์ลิสต์)
• insert
• delete
• ทั้งการ insert และ delete จำเป็นต้องอาศัยการท่องไปในลิสต์เพื่อค้นหาตำแหน่งที่จะทำการเพิ่มหรือลบข้อมูลออกจากลิสต์เสมอ

22

traverse �(การท่องไปในลิงค์ลิสต์)

23

การท่องไปในลิงค์ลิสต์ (traverse)

• ลักษณะของการท่องไปในลิงค์ลิสต์ ต้องอาศัยการสร้างตัวแปร pointer ขึ้นมา 1 ตัว เพื่อ “เดิน” ไปตามเส้นทางของลิงค์ลิสต์นั้น

24

p = head;

while( p->next != NULL)

{

p = p->next;

}

Insert �(การเพิ่มข้อมูลในลิงค์ลิสต์)

25

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

26

ลิงค์ลิสต์ที่ข้อมูลไม่มีการเรียงลำดับ : แทรกหน้าสุด

27

1. ฟังก์ชัน int_front ( head pointer )
2. สร้างโหนดใหม่ (s)
3. รับค่าข้อมูลไปเก็บไว้ใน s->data
4. กำหนดให้ s->next ชี้ไปที่ head
5. กำหนดให้ head ชี้ไปที่ s

ลิงค์ลิสต์ที่ข้อมูลไม่มีการเรียงลำดับ : แทรกหน้าสุด

28

1. void ins_front(node **h)
2. {
3. node *s;
4. if ((s = (node *)malloc(sizeof(node)))==NULL)
5. {
6. printf("!!! Not enough memory");
7. exit(1);
8. }
9. scanf("%d",&s->data);
10. s->next = *h;
11. *h = s;
12. }

...

head = NULL;

ins_front(&head);

ลิงค์ลิสต์ที่ข้อมูลไม่มีการเรียงลำดับ : แทรกหลังสุด

29

1. ฟังก์ชัน ins_end ( head pointer )
2. สร้างโหนดใหม่ (s)
3. รับค่าข้อมูลไปเก็บไว้ใน s->data
4. กำหนดให้ s->next ชี้ไปที่ NULL
5. ถ้าลิงค์ลิสต์ยังไม่มีข้อมูล
6. กำหนดให้ head ชี้ไปที่ s
7. กรณีอื่นๆ
8. ท่องไปจนถึงข้อมูลตัวสุดท้ายในลิงค์ลิสต์
9. นำโหนด s ไปต่อจากข้อมูลตัวสุดท้าย

ลิงค์ลิสต์ที่ข้อมูลไม่มีการเรียงลำดับ : แทรกหลังสุด

30

1. void ins_end(node **h)
2. {
3. node *s,*p;
4. if ((s = (node *)malloc(sizeof(node)))==NULL)
5. { printf("!!! Not enough memory"); exit(1); }
6. scanf("%d",&s->data);
7. s->next = NULL;
8. if (*h == NULL)
9. *h = s;
10. else
11. {
12. p = *h;
13. while (p->next != NULL)
14. p = p->next;
15. p->next = s;
16. }
17. }

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ

• ถ้าลิงค์ลิสต์ที่สร้างขึ้น มีการกำหนดลำดับของข้อมูลไว้ เช่น ถ้าข้อมูลเรียงจากน้อย->มาก

​

​

• โหนดที่จะ insert เข้าไปมีได้ 3 กรณี คือ
• โหนดใหม่มีค่ามากที่สุด
• โหนดใหม่มีค่าน้อยที่สุด
• โหนดใหม่มีค่าอยู่ระหว่างกลาง

31

1

9

3

6

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ

• ในการ insert โหนดใหม่ (มีข้อมูลแล้ว) ลงในลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ มีส่วนประกอบสำคัญ 2 ส่วน คือ
• สร้าง pointer ในการท่องไปในลิงค์ลิสต์จนถึงตำแหน่งที่จะใส่ข้อมูล
• ต้องสร้าง pointer 2 ตัวท่องตามกัน
• กรณีข้อมูลที่จะใส่อยู่ระหว่างโหนดใดๆ
• ใส่ข้อมูลลงไป โดยเขียนโปรแกรมตามกรณีการแทรกข้อมูลกรณีต่างๆ

32

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ : วิธีการท่อง

สร้าง pointer (travel), (previous) ใช้ในการท่องลิงค์ลิสต์

กำหนดให้ travel ชี้ไปที่เดียวกับ head

while (travel->data < s->data) && (travel->next != NULL)

กำหนดให้ previous ชี้ไปที่เดียวกับ travel

travel = travel->next

33

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ : การใส่ข้อมูล

1. กรณีโหนดใหม่มีค่ามากสุด (ต่อท้ายสุด)

• ตรวจสอบได้จากเงื่อนไข
• if (travel->data < s->data)
• นำโหนดใหม่มาต่อที่โหนดท้ายสุด
• travel->next = s
• s->next = NULL

34

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ : การใส่ข้อมูล

2. กรณีโหนดใหม่มีค่าน้อยสุด (ต่อหน้าสุด)

• ตรวจสอบได้จากเงื่อนไข
• if (travel == head)
• นำโหนดใหม่มาต่อที่ด้านหน้าสุด
• s->next = head
• head = s

35

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ : การใส่ข้อมูล

3. กรณีโหนดใหม่แทรกระหว่างโหนดใดๆ

• ตรวจสอบได้จากเงื่อนไข
• if (previous->data < s->data)&&(travel->data > s->data)
• จริงๆ ไม่ต้องตรวจสอบ เพราะถ้าไม่เข้ากรณี 1,2 ก็ต้องเป็นกรณีที่ 3 เท่านั้น
• นำโหนดใหม่มาต่อแทรกระหว่าง previous และ travel
• previous->next = s
• s->next = travel

36

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ

37

1. ฟังก์ชัน ins ( head pointer )
2. สร้างโหนดใหม่ (s)
3. รับค่าข้อมูลไปเก็บไว้ใน s->data
4. ถ้าลิงค์ลิสต์ยังไม่มีข้อมูล
5. กำหนดให้ head ชี้ไปที่ s
6. กรณีอื่นๆ
7. สร้าง pointer (travel), (previous) ใช้ในการท่องลิงค์ลิสต์
8. กำหนดให้ travel ชี้ไปที่เดียวกับ head
9. while (travel->data < s->data) && (travel->next != NULL)
10. กำหนดให้ previous ชี้ไปที่เดียวกับ travel
11. travel = travel->next

ลิงค์ลิสต์ที่ข้อมูลมีการเรียงลำดับ

38

12. ถ้าข้อมูลในโหนด s ซ้ำกับข้อมูลในลิงค์ลิสต์
13. ...
14. กรณีอื่นๆ
15. ถ้า travel->data < s->data // กรณีต่อด้านหลังสุด
16. นำโหนด s ไปต่อจากข้อมูลตัวสุดท้าย
17. ถ้า travel == head // กรณีต่อด้านหน้าสุด
18. กำหนดให้ s->next ชี้ไปที่ head
19. กำหนดให้ head ชี้ไปที่ s
20. กรณีที่เหลือ // กรณีต่อแทรกระหว่างกลาง
21. กำหนด s->next ชี้ที่ travel
22. กำหนด previous->next ชี้ไปที่ s

39

1. void ins(node **h)
2. {
3. node *s,*previous,*travel;
4. if ((s = (node *)malloc(sizeof(node)))==NULL)
5. { printf("!!! Not enough memory"); exit(1); }
6. scanf("%d",&s->data);
7. if (*h == NULL)
8. { s->next = NULL; *h = s; }
9. else
10. {
11. travel = *h;
12. while ((travel->data < s->data) && (travel->next != NULL))
13. { previous = travel; travel = travel->next; }
14. if (travel->data == s->data)
15. printf("\nRecord already exit\n");
16. else
17. if (travel->data < s->data) // insert after last node
18. { travel->next = s; s->next = NULL; }
19. else
20. if (travel == *h) // insert behind first node
21. { s->next = *h; *h = s; }
22. else // insert between two node
23. { previous->next = s; s->next = travel; }
24. }
25. }