โครงสร้างข้อมูลแบบรายการ (List)

Report
9. โครงสร้ างข้ อมูลแบบรายการ
Dense
List

Linked List

Applications
1
การสร้ างซอฟต์ แวร์
ประกอบด้วย
การเลือกโครงสร้างข้อมูล (Data Structure) ที่
เหมาะสม
การออกแบบขั้นตอนวิธี (Algorithm) อย่างมี
ประสิ ทธิภาพ
Program = Data Structure + Algorithm
created by Dararat Saelee , Computer Sciences Department, Faculty of Science, PSU-HatYai
2/92
Data Structure
 Linear
Array
Link
List
Stack
Queue
 Non-Linear
Tree
 Graph

created by Dararat Saelee , Computer Sciences Department, Faculty of Science, PSU-HatYai
3/92
List
เ ป็ น โ ค ร ง ส ร้ า ง ข้ อ มู ล ที่ จั ด เ ก็ บ ข้ อ มู ล
ต่อเนื่ องกันโดยที่สามารถทาการเพิ่มหรื อลบ
ข้อ มู ล ในลิ ส ต์ ต รงต าแหน่ ง ใดก็ ไ ด้ ต ามที่
ต้องการ
created by Dararat Saelee , Computer Sciences Department, Faculty of Science, PSU-HatYai
4/92
List
วิธีการสร้างลิสต์แบบง่ายมี 2 วิธี
1.
Array
count
4
2.
2
1
3
4
25 31 42 58
Link List
25
31
42
58
5/92
การสร้ างลิสต์ ด้วย Array
 การเพิม
่ ข้อมูลในลิสต์
void insert (datatype newdata)
{
position = search(newdata);
ptr = cur;
while (ptr >= position)
{
list[ptr+1] = list[ptr];
ptr--;
}
list[position] = newdata;
cur ++;
}
Ex. newdata = ‘d’
a
position
cur
cur
b
e d
g e
t g
t
6/92
การสร้ างลิสต์ ด้วย Array
 การลบข้อมูลในลิสต์
void delete(datatype olddata)
{
position = search(olddata);
ptr = position;
while (ptr < cur)
{
list[ptr] = list[ptr+1];
ptr++;
}
cur --;
}
Ex. olddata = ‘e’
a
position
cur
cur
b
e g
g t
t
7/92
ปั ญหาของตัวแปรแบบ Array
1.
2.
ตัวแปรแบบ Array มีการจองเนือ้ ที่ท่ อี ยู่ตดิ กันตามจานวนที่
ต้ องการไว้ ก่อน เช่ น ถ้ าต้ องการจัดเก็บข้ อมูลจานวน 10,000 ค่ า
แต่ ละค่ าใช้ เนือ้ ที่ 2 byte เนือ้ ที่ทงั ้ หมดที่ถูกจองจะเป็ น 20,000
byte ซึ่งบางครัง้ อาจจะไม่ มีเนือ้ ที่ว่างที่อยู่ตดิ กันเพียงพอสาหรับ
เก็บข้ อมูล 20,000 byte ทาให้ โปรแกรมไม่ สามารถทางานได้
บางกรณีจองเนือ้ ที่ไว้ สาหรับเก็บข้ อมูล 10,000 ค่ า เนื่องจากไม่
ทราบจานวนข้ อมูลที่ต้องการเก็บ แต่ เมื่อใช้ งานจริง เก็บข้ อมูล
เพียง 2,000 ค่ า ทาให้ เหลือเนือ้ ที่ท่ ยี ังไม่ ได้ ใช้ แต่ ไม่ สามารถ
นาไปใช้ งานอื่นได้
8
ปั ญหาของตัวแปรแบบ Array (ต่ อ)
3.
กรณีจองเนือ้ ที่ไว้ สาหรับเก็บข้ อมูล 10,000 ค่ า แต่ การใช้ งาน
จริงมีข้อมูลที่ต้องเก็บมากกว่ า 10,000 ค่ า ก็ไม่ สามารถเก็บ
ข้ อมูลส่ วนที่เหลือได้ เนื่องจากจองไว้ แค่ ไหน ก็ใช้ ได้ แค่ นัน้
Address
100
102
104
106
:
data1
data2
data3
data4
:
แสดงโครงสร้ างการเก็บข้ อมูลแบบ Array
9
ลักษณะของ Linked list
ไม่ มีการจองเนือ้ ที่ในหน่ วยความจาไว้ ก่อน เมื่อต้ องการจึงจะมี
การขอเนือ้ ที่ ต้ องการใช้ เท่ าไหร่ ขอเนือ้ ที่เท่ าที่ต้องการ
 เนือ
้ ที่สาหรับเก็บข้ อมูลไม่ จาเป็ นต้ องอยู่ตดิ กัน

Address
100
data5
102
104
data1
106
:
:
แสดงโครงสร้ างการเก็บข้ อมูลแบบ Linked list
10
Linked List

โครงสร้ างข้ อมูลแบบลิงค์ ลิสต์ ประกอบด้ วยโหนดต่ างๆต่ อกัน
โดยแต่ ละโหนดมีส่วนที่สาคัญ 2 ส่ วนคือ ส่ วนที่เก็บข้ อมูล
(Data) และ ส่ วนที่เก็บตัวชี ้ (Pointer)
data
data pointer
25
Andaman
X
45.5
pointer
38.75
X
1 โหนด
11
Linked List
ส่ วนที่เก็บข้ อมูล (Data) สามารถเก็บได้ มากกว่ า 1 ข้ อมูล ที่
สัมพันธ์ กัน
 ส่ วนที่เก็บตัวชี ้ (pointer) สาหรั บเก็บตาแหน่ ง (Address) ของ
โหนดก่ อนหน้ าหรือถัดไป
 ประเภทของลิงค์ ลิสต์
 Singly Linked List
 Doubly Linked List

12
Linked List

Singly Linked List จะประกอบด้วยโหนดที่มีพอยน์เตอร์ช้ ี
ไปในทิศทางเดียว คือชี้ไปยังโหนดถัดไป
data pointer
200
B
Address

100
data pointer
300
D
200
data pointer
G
300
หากไม่มีโหนดที่อยูถ่ ดั ไป ส่ วนที่เป็ นพอยน์เตอร์จะเก็บค่า NULL
แทนด้วยสัญลักษณ์
13
Linked List

Doubly Linked List ประกอบด้วยส่ วนของ Data และ
พอยน์เตอร์ที่ช้ ีไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนด
ก่อนหน้า ดังนั้นเราจึงสามารถทาการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไป
ข้างหน้า และอ่านไปทางข้างหลัง
pointer data pointer
B
100
200
pointer data pointer
100
200
D
300
pointer data pointer
200
G
300
Address
14
Linked List
 Operation
ของ Linked list
 เพิ่มข้ อมูล
(Insert) ใน list มี 2 คือ
การเพิ่มต่ อท้ าย list (Append)
เพิ่มโดยแทรกระหว่ าง node
 ลบ
(Delete) ข้ อมูลออกจาก list
15
Singly Linked List
 กาหนดให้ ตัวแปร
head เก็บ address ของโหนดแรกของ list
 last เก็บ address ของโหนดสุดท้ ายของ list
 newnode เก็บ address ของโหนดที่ต้องการเพิ่ม
 data เก็บข้ อมูล
 next เก็บ address ของโหนดถัดไป

 การอ้ างถึง
list ในโหนด เช่ น
newnode -> data เป็ นการอ้ างถึงข้ อมูลของโหนด newnode
 newnode -> next เป็ นการอ้ างถึง address ของโหนดถัดจาก newnode

16
Singly Linked List
 โครงสร้ างของโหนด
newnode
data
next
struct node {
int data;
struct node *next;
} *newnode;
17
Singly Linked List
 การเพิ่มข้ อมูลต่ อท้ าย

list (Append)
ตัวอย่าง
1. เพิ่มโหนดแรก : Insert 25
newnode
1.1 create newnode
1.2 newnode -> data = 25
1.3 newnode -> next = NULL
last
head
data next
25
100
1.4 head = newnode =last (=?)
18
Singly Linked List
 การเพิ่มข้ อมูลต่ อท้ าย

list (Append)
ตัวอย่าง
2. เพิ่มโหนดที่ 2 : Insert 30
last
head
2.3 newnode -> next = NULL
2.4 last- > next = newnode
next
100
2.1 create newnode
2.2 newnode -> data = 30
data
25
newnode
last
data
30
next
200
2.5 last = newnode (=?)
19
Singly Linked List
 การเพิ่มข้ อมูลต่ อท้ าย

list (Append)
ตัวอย่าง
head
3.1 create newnode
last
data
30
next
200
3.3 newnode -> next = NULL
newnode
3.4 last- > next = newnode
3.5 last = newnode (= ?)
next
100
3. เพิ่มโหนดที่ 3 : Insert 42
3.2 newnode -> data = 42
data
25
last
data
42
next
300
21
Singly Linked List
 การเพิ่มข้ อมูลโดยแทรกระหว่ างโหนด

(Insert)
ตัวอย่าง
4. Insert 38 ระหว่ างโหนดที่ 2 กับโหนดที่ 3
4.1 create newnode
4.2 newnode -> data = 38
newnode
data
38
next
400
23
Singly Linked List
 การเพิ่มข้ อมูลโดยแทรกระหว่ างโหนด

(Insert)
ตัวอย่าง
4. Insert 38 ระหว่ างโหนดที่ 2 กับโหนดที่ 3 (ต่ อ)
4.3 ให้
ptr เก็บ address ของโหนดที่ 2
4.4 newnode -> next = ptr -> next
4.5 ptr -> next = newnode
head
100
next
data
38
next
400
ptr
data
25
newnode
data
30
200
next
data
42
next
300
24
Singly Linked List
 การลบข้ อมูลใน

list (Delete)
ตัวอย่าง: Delete 25 ออกจาก list
1. ตรวจสอบ head -> data = 25 หรือไม่ ?
2.
ถาใช
้
่
head
ให้ head = head -> next (= ?)
head
data
25
100
next
data
30
200
next
data
38
400
next
data
42
next
300
25
Singly Linked List
 การลบข้ อมูลใน

list (Delete)
ตัวอย่าง: Delete 38 ออกจาก list
1. ให้ ptr = head
2. ptr -> next -> data = 38?
3.
ถ้าใช่ ให้
4.
ถ้าไม่ใช่ ให้
head
ptr -> next = ptr -> next -> next
ptr = ptr -> next แลววนไปท
าขอ
้
้ 2. ใหม่
ptr
data
25
100
next
data
30
200
next
data
38
400
next
data
42
next
300
26
Doubly Linked List
 กาหนดให้ ตัวแปร
 head เก็บ address ของโหนดแรกของ list
 last เก็บ address ของโหนดสุดท้ ายของ list
 newnode เก็บ address ของโหนดที่ต้องการเพิ่ม
 data เก็บข้ อมูล
 previous เก็บ address ของโหนดก่ อนหน้ า
 next เก็บ address ของโหนดถัดไป
27
Doubly Linked List
 การอ้ างถึง
list ในโหนด เช่ น
 newnode -> data เป็ นการอ้ างถึงข้ อมูลของโหนด newnode
 newnode -> previous เป็ นการอ้ างถึง address ของโหนดก่ อน
หน้ า newnode
 newnode -> next เป็ นการอ้ างถึง address ของโหนดถัดจาก
newnode
28
Doubly Linked List
 โครงสร้ างของโหนด
previous data next
newnode
struct node {
int data;
struct node *next, *previous;
} *newnode;
29
Doubly Linked List
 การเพิ่มข้ อมูลต่ อท้ าย

list (Append)
ตัวอย่าง
1. เพิ่มโหนดแรก : Insert 25
1.1 create newnode
1.2 newnode -> data = 25
1.3 newnode -> previous = NULL
newnode
last
previous data next
25
head
100
1.4 newnode -> next = NULL
1.5 head = newnode =last (= 100)
30
Doubly Linked List
 การเพิ่มข้ อมูลต่ อท้ าย

list (Append)
ตัวอย่าง
2. เพิ่มโหนดที่ 2 : Insert 30
2.1 create newnode
last
head
2.2 newnode -> data = 30
2.5 last- > next = newnode
2.6 last = newnode (=200)
25
100
2.3 newnode -> next = NULL
2.4 newnode -> previous = last
previous data next
newnode
last
previous data next
30
200
31
Doubly Linked List
 การเพิ่มข้ อมูลต่ อท้ าย

list (Append)
ตัวอย่าง
3. เพิ่มโหนดที่ 3 : Insert 42
head
previous data next
3.2 newnode -> data = 42
last
3.4 newnode -> previous = last
3.5 last- > next = newnode
3.6 last = newnode (=300)
25
100
3.1 create newnode
3.3 newnode -> next = NULL
previous data next
30
200
previous data next
newnode
last
42
300
32
Doubly Linked List
 การเพิ่มข้ อมูลโดยแทรกระหว่ างโหนด

(Insert)
ตัวอย่าง
4. Insert 38 ระหว่ างโหนดที่ 2 กับโหนดที่ 3
4.1 create newnode
4.2 newnode -> data = 38
previous data next
38
400
33
Doubly Linked List
 การเพิ่มข้ อมูลโดยแทรกระหว่ างโหนด

(Insert)
ตัวอย่าง 4. Insert 38 ระหว่ างโหนดที่ 2 กับโหนดที่ 3 (ต่ อ)
4.3 ให้
ptr เก็บ address ของโหนดที่ 2
4.4 newnode -> next = ptr-> next
newnode
4.5 newnode -> previous = ptr-> next -> previous
previous data next
4.6 ptr -> next = newnode
38
head
previous data next
previous data next
25
100
400
ptr
previous data next
42
30
200
300
34
Doubly Linked List
 การลบข้ อมูลใน

list (Delete)
ตัวอย่าง: Delete 25 ออกจาก list
1. ตรวจสอบ head -> data = 25 หรือไม่ ?
2.
ถ้าใช่
head
head
ให้ head = head -> next (= ?)
previous data next
30
42
200
previous data next
300
previous data next
25
100
previous data next
38
400
35
Singly Linked List
 การลบข้ อมูลใน

list (Delete)
ตัวอย่าง: Delete 38 ออกจาก list
1. ให้ ptr = head
2. ptr -> next -> data = 38?
3.
ถ้าใช่ ให้
4.
ถ้าไม่ใช่ ให้
ptr
head
ptr -> next = ptr -> next -> next
ptr = ptr -> pointer แลววนไปท
าขอ
้
้ 2. ใหม่
previous data next
30
42
200
previous data next
300
previous data next
25
100
previous data next
38
400
36
Array vs Linked List

Array
 Linked List
ข้ อมูลคงที่
ข้ อมูลไม่ คงที่
ไม่ ค่อยเปลีย่ นแปลง
เปลีย่ นแปลงบ่ อย
37
Motto Today
คนเราอย่ามุง่ แต่ความสาเร็จ ต้อง
รักษาความดีไว้ด้วย
อย่าเป็ นคนเก่งที่ไม่มีค่า
Practice makes Perfect !
created by Dararat Saelee , Computer Sciences Department, Faculty of Science, PSU-HatYai
38/92

similar documents