;docx

16/08/57
305214
Fundamental of Data Structures and
Algorithms
Lecture03: Linked Lists
• ถ้ าประกาศตัวแปร เช่น
double x = 8.5;
จะมีการจองพื นทีหน่วยความจําทีมีขนาดเท่ากับขนาดของเลขจํานวนจริ ง
ให้ กบั ตัวแปร x แล้ วใส่คา่ 8.5 เข้ าไปในพื นทีหน่วยความจํานี 1
16/08/57
Pointer
• พอยน์ เตอร์ (pointer) เป็ นตัวแปรชนิดหนึงทีใช้ เก็บตําแหน่ ง
ของข้ อมูลในหน่ วยความจํา
• ถ้ าประกาศตัวแปร pointer เช่น
double *ptr;
• จะมีการจองพื นทีหน่วยความจําและเก็บทีอยูส่ ําหรับตัวแปร pointer
ซึง จะเก็บค่าทีอยูส่ ําหรับอ้ างถึงพื นทีหน่วยความจําทีมีขนาดเท่ากับ
ขนาดของเลขจํานวนจริ ง
• ถ้ ามีการกําหนดค่าให้ กบั พื นทีหน่วยความจําทีตวั แปร pointer อ้ าง
ถึง เช่น
*ptr = 23.5; จะได้
2
16/08/57
• คําสัง “new” เป็ นคําสัง ทีใช้ ในการสร้ าง memory cell
ขึ นมาเพือเตรี ยมเก็บข้ อมูล ซึง memory cell นี จะเข้ าถึงได้
ด้ วยตัวแปร pointer เท่านัน
เช่น เริ มต้ นมี pointer 2 ตัวคือ ptr และ pp
ptr = new double;
สร้ าง memory cell ขึ นมาเพือเตรี ยมเก็บข้ อมูลชนิด
จํานวนจริ ง
3
16/08/57
Linked lists
• อาจจะนิยามได้ เป็ น โครงสร้ างของข้ อมูลทีเก็บข้ อมูลไว้
ใน node เป็ นลําดับ แต่ ละ node จะประกอบไปด้ วย
ข้ อมูล (data) และ link (หรื อ pointer) ซึงทํา
หน้ าทีเชื อมโยงกับ node อืน
• Linked Lists อาจจะแบ่งเป็ น 2 ชนิด คือ
• Singly linked lists
• Doubly linked lists
4
16/08/57
Singly linked lists
• อาจจะนิยาม Singly linked list ได้ เป็ น โครงสร้ างของข้ อมูลทีเก็บ
ข้ อมูลไว้ ใน node เป็ นลําดับ โดยแต่ ละ node จะประกอบไปด้ วย
ข้ อมูลและ pointer 2 ตัว ชีไ* ปยัง node ถัดไป ยกเว้ น node สุดท้ าย
ที pointer ของ node นัน* ชีไ* ปที NULL
• ภาพแสดง node ของ singly linked list
• ถ้ านํา node มาเรี ยงต่อ ๆ กันเป็ นลําดับจะได้ singly
linked list ของข้ อมูล n ตัว โดยจะกําหนดให้ มี
pointer อย่างน้ อยหนึง ตัวทีชี ไปยัง node แรกของ
singly linked list เสมอ เพือประโยชน์ในการเข้ าถึง
ข้ อมูล ดังแผนภาพ
5
16/08/57
• จะเห็นได้ ว่าลักษณะของ singly linked list เหมือน
ขบวนรถไฟ ในทีซงึ
– ตู้ของรถไฟก็เปรี ยบได้ กบั node
– ขอเกียวแต่ละตู้ก็เปรี ยบได้ กบั pointer
• ในการเขียนโปรแกรม เช่น การเขียนด้ วยภาษา C++
จะต้ องมีการประกาศโครงสร้ างของ node ของ singly
linked list จึงจะนํา node มาใช้ ได้ เช่น
สมมติวา่ ข้ อมูลทีต้องการเก็บเป็ นชนิดจํานวนเต็ม อาจจะ
เขียนส่วนทีใช้ ในการประกาศโครงสร้ างชนิด node ได้ เป็ น
struct node
//ตังชื
อของโครงสร้ างข้ อมูลว่า node
{
int data; //ประกาศให้ ตวั แปรชือ data เก็บข้ อมูลจํานวน
เต็ม
struct node * next; //ประกาศให้ next เป็ น
pointer ชี ไปยัง node
};
6
16/08/57
• ก่อนอืนต้ องมีการประกาศ pointer เพือให้ ชี ไปยัง
โครงสร้ างข้ อมูล node
เช่น node * first ; // ให้ pointer first ชี ไป
ยังโครงสร้ างข้ อมูล node
จากนันใช้
คําสัง
first = new node ; // สร้ าง node ใหม่ขึ นมาด้ วย
pointer first
7
16/08/57
• การเข้ าถึงข้ อมูลใน node จะทําได้ โดยใช้ เครื องหมาย
เช่น กําหนดค่าให้ data เท่ากับ 5
->
first -> data = 5 ;
• ถ้ าต้ องการเชือมโยง node เข้ าด้ วยกัน ก็ทําได้ ด้วยการใช้
pointer
• เช่น ให้ มีข้อมูลเรี ยงกันเป็ น 10 และ 20 จะต้ องเชือมทั งสอง
node ต่อกัน
8
16/08/57
p -> next = q;
ถ้ า node ทีมีข้อมูล 20 เป็ น node สุดท้ ายก็จะให้
pointer next ของ node นั นชี ไปที NULL
จะเขียนได้ เป็ น
q -> next = NULL;
จากการต่อ node ทั งสอง จะพบว่าเป็ น singly linked list
9
16/08/57
Create list
• การสร้ าง list (create) อาจจะใช้ แนวทางเดียวกับทีกล่าวไว้ ข้างต้ น
กล่าวคือ
– ประกาศให้ pointer ชี ไปยังโครงสร้ างข้ อมูล node เช่น อาจจะใช้ pointer
ชือ first
– สร้ าง node ใหม่ขึ นมาด้ วย pointer first
– ประกาศ pointer อีกหนึง ตัวสําหรับช่วยในการใส่ข้อมูลเข้ าไปใน node เช่น
node *ptr;
– ให้ pointer อีกหนึง ตัวข้ างต้ นชี ไปทีเดียวกับ pointer first เช่น ptr =
first
– ดําเนินการเพิมข้ อมูลด้ วย pointer ptr คล้ ายกับทีกล่าวถึงข้ างต้ น ซึง ถ้ าข้ อมูล
มีจํานวนมาก ก็อาจจะใช้ การวนลูปเข้ ามาช่วย
การเพิมข้ อมูล (insert)
• insert(k, x)
k : ตําแหน่ง
x : ข้ อมูล
• ในการเพิมข้ อมูล ก็ทําได้ โดยการสร้ าง node ใหม่ขึ นมาหนึง node โดยใช้
pointer ตัวใดตัวหนึง เช่น ใช้ pointer p
• อาจจะเขียนได้ เป็ น
node *p;
p = new node;
p -> data = x;
p -> next = NULL;
10
16/08/57
ตัวอย่ าง กําหนดให้ ตําแหน่งเริ มที 1 ให้ insert (3, 10) ใน linked
list ต่อไปนี จะเห็นได้ วา่
k = 3 และ x = 10
โจทย์ต้องการให้ เพิม node ทีมีข้อมูล 10 แทรกระหว่าง node ทีมี
ข้ อมูล 7 และ 2
ทําการสร้ าง node ทีมีข้อมูล 10 ก่อน โดยอาจจะใช้ pointer เช่น
pointer p สร้ าง node ใหม่ขึ นมา
11
16/08/57
เมือจะเพิมข้ อมูลทีตําแหน่งใด ก็อาจจะมี pointer อีกหนึง ตัวมาช่วยใน
การเพิมข้ อมูล เช่น ptr จากตัวอย่างอาจจะให้ ptr ชี ไปยัง node ทีมี
ข้ อมูล 7 ซึง เป็ น node ก่อนหน้ าของ node ทีต้องการเพิมเข้ าไป
แนวความคิดก็คือ นํา pointer next ของ node ใหม่ที
ต้ องการเพิมมาต่อ node ทีจะเป็ น node ถัดไป แล้ วนํา
pointer next ของ node ก่อนหน้ ามาต่อกับ node ใหม่
อาจจะเขียนได้ เป็ น
p -> next = ptr -> next;
ptr -> next = p;
12
16/08/57
จะได้ ดงั แผนภาพ ซึง เมือเพิมข้ อมูลไปแล้ วก็ยงั มีคณ
ุ ลักษณะของ singly
linked list อยู่
การลบข้ อมูล (delete)
del (x)
x : ข้ อมูลทีต้องการลบ
ตัวอย่ าง del (2) จาก linked list ต่อไปนี 13
16/08/57
เมือต้ องการลบข้ อมูล ก็จะต้ องทําการหาข้ อมูลก่อน (search(x)) เมือ
พบว่าอยูต่ ําแหน่งใดแล้ วก็อาจจะมี pointer มาช่วย 2 ตัว โดยให้ ชี ไป
ยัง node ของข้ อมูลทีต้องการลบ และชี ไปยัง node ของข้ อมูลก่อน
หน้ า
ทําการลบข้ อมูลโดยให้ pointer next ของ node ก่อนหน้ าชี ข้ ามไป
ยัง node ถัดไป
p -> next = ptr -> next;
14
16/08/57
ทําการลบ node ที pointer ptr ชี อยู่ โดยใช้ คําสัง
delete ptr;
Doubly linked lists
• อาจจะนิยาม doubly linked list ได้ เป็ น โครงสร้ างของ
ข้ อมูลทีเก็บข้ อมูลไว้ ใน node เป็ นลําดับ โดยแต่ ละ node จะ
ประกอบไปด้ วยข้ อมูลและ pointer 2 ตัว ชีไ* ปยัง node
ถัดไป และอีกหนึงตัวชีไ* ปยัง node ก่ อนหน้ า ยกเว้ น node
แรกที pointer สําหรั บชีไ* ป node ก่ อนหน้ าจะชีไ* ปที NULL
และ node สุดท้ ายที pointer สําหรั บชีไ* ป node ถัดไปจะชี *
ไปที NULL
15
16/08/57
• ภาพแสดง node ของ doubly linked list
data คือ ข้ อมูลทีเก็บไว้ ใน node
next คือ pointer ทีชี ไปยัง node ถัดไป
prev คือ pointer ทีชี ไปยัง node ก่อนหน้ า
• ถ้ านํา node มาเรี ยงต่อ ๆ กันเป็ นลําดับจะได้ doubly
linked list ของข้ อมูล n ตัว โดยจะกําหนดให้ มี
pointer อย่างน้ อยหนึง ตัวทีชี ไปยัง node แรกของ
doubly linked list เสมอ เพือประโยชน์ในการเข้ าถึง
ข้ อมูล ดังแผนภาพ
16
16/08/57
ในการเขียนโปรแกรม เช่น การเขียนด้ วยภาษา C++ จะต้ องมีการประกาศ
โครงสร้ างของ node ของ singly linked list จึงจะนํา node มา
ใช้ ได้
สมมติวา่ ข้ อมูลทีต้องการเก็บเป็ นชนิดจํานวนเต็ม อาจจะเขียนส่วนที
ใช้ ในการประกาศโครงสร้ างชนิด node ได้ เป็ น
struct node //ตังชื
อของโครงสร้ างข้ อมูลว่า node
{
int data; //ประกาศให้ ตวั แปรชือ data เก็บข้ อมูลจํานวนเต็ม
struct node *next,*prev; //ประกาศให้ next เป็ น
pointer ชี ไปยัง node ถัดไป และ prev เป็ น pointer ชี ไปยัง node
ก่อนหน้ า
};
Create List
• การสร้ าง list (create) อาจจะใช้ แนวทางเดียวกับทีกล่าวไว้ ใน singly
linked list กล่าวคือ
– ประกาศให้ pointer ชี ไปยังโครงสร้ างข้ อมูล node เช่น อาจจะใช้ pointer ชือ
first
– สร้ าง node ใหม่ขึ นมาด้ วย pointer first
– ประกาศ pointer อีกหนึงตัวสําหรับช่วยในการใส่ข้อมูลเข้ าไปใน node เช่น node
*ptr;
– ให้ pointer อีกหนึงตัวข้ างต้ นชี ไปทีเดียวกับ pointer first เช่น ptr = first
– ดําเนินการเพิมข้ อมูลด้ วย pointer ptr คล้ ายกับทีกล่าวถึงข้ างต้ น ซึง ถ้ าข้ อมูลมี
จํานวนมาก ก็อาจจะใช้ การวนลูปเข้ ามาช่วย
Note: อย่ าลืม pointer prev และ next
17
16/08/57
การเพิมข้ อมูล (insert)
• insert(k, x)
k : ตําแหน่ง
x : ข้ อมูล
• ในการเพิมข้ อมูล ก็ทําได้ โดยการสร้ าง node ใหม่ขึ นมาหนึง node โดยใช้
pointer ตัวใดตัวหนึง เช่น ใช้ pointer p
• อาจจะเขียนได้ เป็ น
node *p;
p = new node;
p -> data = x;
p -> next = NULL;
p -> prev = NULL;
ตัวอย่ าง กําหนดให้ ตําแหน่งเริ มที 1 ให้ insert (3, 10) ใน linked
list ต่อไปนี จะเห็นได้ วา่
k = 3 และ x = 10
โจทย์ต้องการให้ เพิม node ทีมีข้อมูล 10 แทรกระหว่าง node ทีมี
ข้ อมูล 7 และ 2
18
16/08/57
ทําการสร้ าง node ทีมีข้อมูล 10 ก่อน โดยอาจจะใช้ pointer เช่น
pointer p สร้ าง node ใหม่ขึ นมา
เมือจะเพิมข้ อมูลทีตําแหน่งใด ก็อาจจะมี pointer อีกหนึง ตัวมาช่วยใน
การเพิมข้ อมูล เช่น ptr จากตัวอย่างอาจจะให้ ptr ชี ไปยัง node ที
ตําแหน่งทีต้องการเพิมเข้ าไป
19
16/08/57
อาจจะทําได้ หลายแนวทาง แนวทางหนึง อาจจะเขียนได้ เป็ น
p -> next = ptr;
p -> prev = ptr -> prev;
p -> prev -> next = p;
ptr -> prev = p;
จะได้ ดงั แผนภาพ ซึง เมือเพิมข้ อมูลไปแล้ วก็ยงั มีคณ
ุ ลักษณะของ
doubly linked list อยู่
20
16/08/57
การลบข้ อมูล (delete)
del (x)
x : ข้ อมูลทีต้องการลบ
ตัวอย่ าง del (2) จาก linked list ต่อไปนี เมือต้ องการลบข้ อมูล ก็จะต้ องทําการหาข้ อมูลก่อน (search(x)) เมือ
พบว่าอยูต่ ําแหน่งใดแล้ วก็อาจจะมี pointer มาช่วย 1 ตัว โดยให้ ชี ไป
ยัง node ของข้ อมูลทีต้องการลบ
21
16/08/57
อาจจะทําการลบข้ อมูลได้ ดงั นี ptr -> prev -> next = ptr -> next;
ptr -> next -> prev = ptr -> prev;
ทําการลบ node ที pointer ptr ชี อยู่ โดยใช้ คําสัง
delete ptr;
22