Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4.1

Chương 4. Danh sách liên kết (Phần 1 – 3 tiết)

ầ

Tr n Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn

Cập nhật: ngày 10 tháng 10 năm 2016

Mục tiêu

• Nắm vững khái niệm về kiểu dữ liệu tĩnh và động

• Nắm vững cách tổ chức dữ liệu động bằng danh sách liên

kết và minh họa được các thao tác xử lý trên danh sách liên

kết đơn

• Cài đặt minh họa được các thao tác của danh sách đơn

bằng ngôn ngữ C#

Vấn đề kiểu dữ liệu tĩnh

6

15

10

9

7

5 3 4

1

2

3

5 2 6

7 1 8

? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng

Vấn đề kiểu dữ liệu tĩnh

6 Giả sử cần thêm tiếp 1 phần tử

15

10

9

7 ? 5

1

2

3 3 4

5 2 6

1 8

7

9 Bổ sung thêm

Bài tập

Hãy cài phương thức (bằng ngôn ngữ C#) chèn một phần tử có giá trị x vào vị trí vt trong mảng số nguyên arr, theo mẫu như sau:

class CMyIntArray{

int []arr;

public void InsertX(int x, int vt){}

}

Vấn đề kiểu dữ liệu tĩnh

15

10

9

7

5

1

2

3 3 4

5 2 6

7 1 8

? Làm sao để xóa phần tử 9

Vấn đề kiểu dữ liệu tĩnh

15

10

9

7

5

1

2

3 3 4

5

7 1 8

2 6

Bài tập

Hãy cài đặt hàm (bằng ngôn ngữ C#) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên arr, theo mẫu sau:

class CMyIntArray{

int []arr;

public void DeleteX(int x){}

}

Vấn đề kiểu dữ liệu tĩnh

Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n)

i

Vấn đề kiểu dữ liệu tĩnh

• Giải quyết vấn đề phức tạp khi chèn/ xóa?

• Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa?

• Giải quyết vấn đề vùng nhớ không liên tục?

• Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến?

DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG

Danh sách liên kết (DSLK)

1

Các phần tử kết dính với nhau bằng “sợi dây liên kết”

7 2 6

3 10 8 5 9 4

1 7 2 6

Để đơn giản hơn trong việc minh họa

3 10 8 5 9 4

Đặc điểm DSLK

• Một dãy tuần tự các nút (Node)

• Giữa hai nút có con trỏ liên kết

• Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ

• Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ)

Đặc điểm DSLK

• Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ

cần thay đổi mối liên kết

• Quản lý phần tử đầu tiên bằng con trỏ pHead

• Có thể truy xuất đến các phần tử khác thông qua con trỏ liên

kết

Cấu tạo của DSLK

Node

List

pHead pTail

Cấu tạo của nút

• Tạo lập bằng cách cấp phát bộ nhớ động

• Mỗi nút có 2 thông tin:

• Dữ liệu (data)

• Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link)

• Nếu không trỏ đến phần tử nào thì con trỏ Next = null

Thao tác chèn thêm node vào DSLK

• “Kết nối” lại sợi dây liên kết theo trình tự

List

pHead pTail

Thao tác xóa node khỏi DSLK

Cần xóa

List

pHead pTail

Các loại hình DSLK

DSLK đơn: Các phần tử kết nối với nhau theo hướng “chiều đi tới”

Các loại hình DSLK

DSLK đôi: Các phần tử kết nối với nhau theo hướng “chiều đi tới và và đi lui”

Các loại hình DSLK

Danh sách liên kết vòng: Các phần tử kết nối với nhau theo hướng “chiều đi tới” và phần tử cuối cùng có “đường đi vòng trở lại tới” phần tử đầu danh sách

ả So sánh M ng và DSLK

M ngả

Danh sách liên k tế ố

ầ ử

ổ thay đ i tùy

ướ ố ị

Kích th

c c đ nh

S ph n t ý

ầ

ử

ế

liên k t

ớ

ỏ

Các ph n t ằ v i nhau b ng con tr

ầ ữ ử ư Các ph n t l u tr ỉ ị ự ầ tu n t (đ a ch tăng ớ ộ ầ d n) trong b nh

ỉ ầ

ể

ổ ế k t

ị ả Ph i d ch chuy n các ầ ử khi Thêm/Xóa ph n t

ấ

ẫ

ầ ự22

Truy xu t ng u nhiên

Ch c n thay đ i con ỏ tr khi liên Thêm/Xóa ấ Truy xu t tu n t

DSLK đơn

pNext

Data

Cấu trúc 1 node

List

pHead pTail

Data : Dữ liệu của node pNext : Con trỏ đến node kế tiếp pHead: Con trỏ đến node đầu pTail: Con trỏ đến node cuối

Cấu tạo của DSLK

• Quản lý toàn bộ danh sách liên kết thông qua con trỏ đầu

pHead

• pHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút”

• Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con

trỏ cuối (pTail)

• pTail không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút”

Cấu tạo của nút

• Tạo lập bằng cách cấp phát bộ nhớ động

• Mỗi nút có 2 thông tin:

• Dữ liệu (data)

• Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link)

• Nếu không trỏ đến phần tử nào thì con trỏ Next = null

pNext

Khai báo node

data

public class Node { private T data; private Node pNext = null; public T Data { get { return data; } set { data = value; } } public Node PNext { get { return pNext; } set { pNext = value; } } }

pNext

Khai báo node lưu số nguyên

20

public class IntNode {

private int data; private IntNode pNext = null;

public int Data {

get { return data; } set { data = value; }

} public IntNode PNext

{

get { return pNext; } set { pNext = value; }

} }

Tạo lập danh sách rỗng

pHead và pTail chưa xác định

pHead và pTail trỏ vào null (rỗng)

List

? pHead

? pTail

pHead pTail

Sau khi tạo lập

Trước khi tạo lập

Khai báo DSLK đơn

List

pHead pTail

class CMyLinkedList {

private Node pHead = null; private Node pTail = null; //Các phương thức

}

Khai báo DSLK đơn số nguyên

20 32 9 1 7

List

pHead pTail

public class CMyIntLinkedList {

private IntNode pHead = null; private IntNode pTail = null; //Các phương thức

}

Các thao tác trên DSLK đơn

• Kiểm tra danh sách rỗng

• Thêm 1 nút vào danh sách

• Duyệt danh sách

• Xóa 1 nút

• Tìm 1 phần tử

• Sắp xếp danh sách

Kiểm tra danh sách rỗng

List

pHead pTail

Danh sách rỗng

public bool IsEmpty() {

return pHead == null;

}

Thêm một nút vào danh sách

TH danh sách rỗng

30 list

pHead pTail

pNew

pHead = pTail = pNew;

Thêm một nút vào danh sách

TH danh sách đã có phần tử

30

25 list

pHead pTail

pNew

Có 2 trường hợp để thêm pNew 1. Thêm pNew vào đầu (AddHead) 2. Thêm pNew vào cuối (AddTail)

TH Thêm một nút vào đầu danh sách

2

1

30

25 list

pHead pTail

pNew

TH Thêm một nút vào đầu danh sách

30

25 list

pHead pTail

Vẽ lại

25

30 list

pHead pTail

TH Thêm một nút vào đầu danh sách

?

Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew vào đầu danh sách

25

30

42 list

pHead pTail

pNew

TH Thêm một nút vào đầu danh sách

1. pNew.PNext = pHead; 2. pHead = pNew;

TH Thêm một nút vào đầu danh sách

Hãy viết phương thức thêm phần tử vào đầu danh sách (C#), theo mẫu sau:

?

public void AddHead(Node pNew)

TH Thêm một nút vào cuối danh sách

30

25

1 list

pHead pTail

pNew

2

1

pTail.PNext = pNew

2

pTail = pNew

TH Thêm một nút vào cuối danh sách

?

Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew vào cuối danh sách

30

25

42 list

pHead pTail

pNew

TH Thêm một nút vào cuối danh sách

Hãy viết phương thức thêm phần tử pNew vào cuối danh sách (C#), theo mẫu:

?

public void AddTail(Node pNew)

Nhập dữ liệu vào DSLK

Nhập dữ liệu cho node

Tạo con trỏ node

Thêm node vào danh sách

Nhập dữ liệu vào danh sách

Để tạo node mới từ dữ liệu x có sẵn

• Đưa dữ liệu có giá trị x vào phần data

• Con trỏ pNext trỏ đến null

pNew.data = x

Data

x

pNew.pNext = null

pNew

VD nhập dữ liệu vào DSLK số nguyên

Tạo và trả về Node có chứa giá trị x

public class IntNode {

private int data; private IntNode pNext = null;

public IntNode(int x) {

data = x; pNext = null;

} }

Nhập dữ liệu vào DSLK

VD nhập dữ liệu cho DSLK số nguyên dương và đưa vào đầu danh sách

public void Input() { int x; do { Console.Write("Nhap vao so nguyen duong (nhap -1 ket thuc): "); int.TryParse(Console.ReadLine(), out x); if (x < 0) break; else { IntNode pNew = new IntNode(x); AddHead(pNew); } } while (true); }

Xuất dslk

p

List

pHead pTail

Xuất DSLK số nguyên

public void Output() {

IntNode p = pHead; while (p != null)

{

Console.Write(p.Data + "->"); p = p.PNext;

} }

Bài tập

phương

thức

cho

lớp

nghĩa

các

Định CMyIntLinkedList:

1. Đếm số lượng node

int DemSL();

2. Tìm node có giá trị lớn nhất

Node TimMax();

3. Tìm node có giá trị x

Node TimX(int x);

4. In những node có giá trị chẵn

void InChan();

5. Tính giá trị trung bình cộng các node có giá trị lẻ

double TBLe();

Chương trình mẫu

Minh hoạ thao tác nhập vào đầu và xuất DSLK số nguyên. Chương trình gồm 3 lớp:

1. Lớp IntNode: cấu trúc dữ liệu Node

2. Lớp CMyIntLinkedList: cấu trúc DSLK đơn

3. Lớp Program: gọi thử nghiệm

Lớp IntNode

public class IntNode { private int data; private IntNode pNext = null;

public int Data { get { return data; } set { data = value; } } public IntNode PNext { get { return pNext; } set { pNext = value; } } public IntNode(int x) { data = x; pNext=null; } }

Lớp CMyIntLinkedList

public class CMyIntLinkedList { private IntNode pHead = null; private IntNode pTail = null; public bool IsEmpty() { return pHead == null; } public void AddHead(IntNode pNew) { if (IsEmpty()) { pHead = pTail = pNew; } else { pNew.PNext = pHead; pHead = pNew; } }

Lớp CMyIntLinkedList (tt…)

public void Input() { int x; do {

Console.Write("Nhap vao so nguyen duong (nhap -1 ket thuc): "); int.TryParse(Console.ReadLine(), out x); if (x < 0) break;

else

{

IntNode pNew = new IntNode(x); AddHead(pNew);

}

} while (true); }

Lớp CMyIntLinkedList (tt…)

public void Output()

{ IntNode p = pHead; while (p != null) { Console.Write(p.Data + "->"); p = p.PNext; } Console.WriteLine("."); } }

Lớp Program