Bài giảng Lập trình - Chương 3: Cấu trúc dữ liệu

Lập trình

Chương 3: Cấu trúc dữ liệu

2/10/2017

Nội dung bài giảng

3.1 Giới thiệu chung

3.2 Mảng và quản lý bộ nhớ động

3.4 Nội dung và mục đích của cấu trúc dữ liệu

3.4 Cài đặt một số cấu trúc với C++

2

Chương 3: Cấu trúc dữ liệu

3.1 Giới thiệu chung

. Phần lớn các bài toán trong thực tế liên quan tới các

dữ liệu phức hợp, những kiểu dữ liệu cơ bản trong

ngôn ngữ lập trình không đủ biểu diễn

. Ví dụ:

– Dữ liệu sinh viên: Họ tên, ngày sinh, quê quán, mã số SV,...

– Mô hình hàm truyền: Đa thức tử số, đa thức mẫu số

– Mô hình trạng thái: Các ma trận A, B, C, D

– Đối tượng đồ họa: Kích thước, màu sắc, đường nét, phông

chữ, ...

. Phương pháp biểu diễn dữ liệu: định nghĩa kiểu dữ

liệu mới sử dụng cấu trúc (struct, class, union, ...)

3

Chương 3: Cấu trúc dữ liệu

Vấn đề: Biểu diễn tập hợp dữ liệu

. Đa số những dữ liệu thuộc một ứng dụng có liên quan

với nhau => cần biểu diễn trong một tập hợp có cấu

trúc, ví dụ:

– Danh sách sinh viên: Các dữ liệu sinh viên được sắp xếp theo

thứ tự Alphabet

– Đối tượng đồ họa: Một cửa sổ bao gồm nhiều đối tượng đồ

họa, một bản vẽ cũng bao gồm nhiều đối tượng đồ họa

. Thông thường, các dữ liệu trong một tập hợp có cùng

kiểu, hoặc ít ra là tương thích kiểu với nhau

. Kiểu mảng không phải bao giờ cũng phù hợp!

4

Chương 3: Cấu trúc dữ liệu

Vấn đề: Quản lý dữ liệu

. Sử dụng kết hợp một cách khéo léo kiểu cấu trúc và

kiểu mảng đủ để biểu diễn các tập hợp dữ liệu bất kỳ

. Các giải thuật (hàm) thao tác với dữ liệu, nhằm quản

lý dữ liệu một cách hiệu quả:

– Bổ sung một mục dữ liệu mới vào một danh sách, một bảng,

một tập hợp, ...

– Xóa một mục dữ liệu trong một danh sách, bảng, tập hợp,..

– Tìm một mục dữ liệu trong một danh sách, bảng tập hợp,...

theo một tiêu chuẩn cụ thể

– Sắp xếp một danh sách theo một tiêu chuẩn nào đó

– ....

5

Chương 3: Cấu trúc dữ liệu

Quản lý DL thế nào là hiệu quả?

. Tiết kiệm bộ nhớ

. Truy nhập nhanh, thuận tiện: Thời gian cần cho bổ

sung, tìm kiếm và xóa bỏ các mục dữ liệu phải ngắn

. Linh hoạt: Số lượng các mục dữ liệu không (hoặc ít)

bị hạn chế cố định, không cần biết trước khi tạo cấu

trúc, phù hợp với cả bài toán nhỏ và lớn

. Hiệu quả quản lý dữ liệu phụ thuộc vào

– Cấu trúc dữ liệu được sử dụng

– Giải thuật được áp dụng cho bổ sung, tìm kiếm, sắp xếp, xóa

bỏ

6

Chương 3: Cấu trúc dữ liệu

Các cấu trúc dữ liệu thông dụng

. Mảng (nghĩa rộng): Tập hợp các dữ liệu có thể truy

nhập tùy ý theo chỉ số

. Danh sách (list): Tập hợp các dữ liệu được móc nối đôi

một với nhau và có thể truy nhập tuần tự

. Cây (tree): Tập hợp các dữ liệu được móc nối với nhau

theo cấu trúc cây, có thể truy nhập tuần tự từ gốc

. Hàng đợi (queue): Tập hợp các dữ liệu có sắp xếp tuần

tự, chỉ bổ sung vào từ một đầu và lấy ra từ đầu còn lại

. Ngăn xếp (stack): Tập hợp các dữ liệu được sắp xếp

tuần tự, chỉ truy nhập được từ một đầu

. Bộ nhớ vòng (ring buffer): Tương tự như hàng đợi,

nhưng dung lượng có hạn, nếu hết chỗ sẽ được ghi

quay vòng

7

Chương 3: Cấu trúc dữ liệu

3.2 Mảng và quản lý bộ nhớ động

. Mảng cho phép biểu diễn và quản lý dữ liệu một cách

khá hiệu quả:

– Đọc và ghi dữ liệu rất nhanh qua chỉ số hoặc qua địa chỉ

– Tiết kiệm bộ nhớ

. Các vấn đề của mảng tĩnh:

VD: Student student_list[100];

– Số phần tử phải là hằng số (biết trước khi biên dịch, người sử

dụng không thể nhập số phần tử, không thể cho số phần từ

là một biến) => kém linh hoạt

– Chiếm chỗ cứng trong ngăn xếp (đối với biến cục bộ) hoặc

trong bộ nhớ dữ liệu chương trình (đối với biến toàn cục) =>

sử dụng bộ nhớ kém hiệu quả, kém linh hoạt

8

Chương 3: Cấu trúc dữ liệu

Mảng động

. Mảng động là một mảng được cấp phát bộ nhớ theo

yêu cầu, trong khi chương trình chạy

#include <stdlib.h>

int n = 50;

...

/* C */

float* p1= (float*) malloc(n*sizeof(float)); /* C */

double* p2= new double[n]; // C++

. Sử dụng con trỏ để quản lý mảng động: Cách sử dụng

không khác so với mảng tĩnh

p1[0] = 1.0;

p2[0] = 2.0;

. Sau khi sử dụng xong => giải phóng bộ nhớ:

free(p1);

delete [] p2;

/* C */

// C++

9

Chương 3: Cấu trúc dữ liệu

Cấp phát và giải phóng bộ nhớ động

. C:

– Hàm malloc()yêu cầu tham số là số byte, trả về con trỏ

không kiểu (void*) mang địa chỉ vùng nhớ mới được cấp

phát (nằm trong heap), trả về 0 nếu không thành công.

– Hàm free()yêu cầu tham số là con trỏ không kiểu (void*),

giải phóng vùng nhớ có địa chỉ đưa vào

. C++:

– Toán tử newchấp nhận kiểu dữ liệu phần tử kèm theo số

lượng phần tử của mảng cần cấp phát bộ nhớ (trong vùng

heap), trả về con trỏ có kiểu, trả về 0 nếu không thành công.

– Toán tử delete[]yêu cầu tham số là con trỏ có kiểu.

– Toán tử newvà deletecòn có thể áp dụng cho cấp phát và

giải phóng bộ nhớ cho một biến đơn, một đối tượng chứ

không nhất thiết phải một mảng.

10

Chương 3: Cấu trúc dữ liệu

Một số điều cần lưu ý

. Con trỏ có vai trò quản lý mảng (động), chứ con trỏ không phải

là mảng (động)

. Cấp phát bộ nhớ và giải phóng bộ nhớ chứ không phải cấp phát

con trỏ và giải phóng con trỏ

. Chỉ giải phóng bộ nhớ một lần

. Ví dụ:

int* p;

p[0] = 1;

// ??

new(p);

// ??

p = new int[100];

p[0] = 1;

// OK

int* p2=p;

// OK

delete[] p2;

p[0] = 1;

// OK

//??

delete[] p;

p = new int[50];

//??

// OK, new array

...

11

Chương 3: Cấu trúc dữ liệu

Cấp phát bộ nhớ động cho biến đơn

. Ý nghĩa: Các đối tượng có thể được tạo ra động, trong khi

chương trình chạy (bổ sung sinh viên vào danh sách, vẽ thêm

một hình trong bản vẽ, bổ sung một khâu trong hệ thống,...)

. Cú pháp

int* p = new int;

*p = 1;

p[0]= 2;

p[1]= 1;

// giong nhu tren

// ??

int* p2 = new int(1); // có khởi tạo

delete p;

delete p2;

Student* ps = new Student;

ps->code = 1000;

...

delete ps;

12

Chương 3: Cấu trúc dữ liệu

Ý nghĩa của sử dụng bộ nhớ động

. Hiệu suất:

– Bộ nhớ được cấp phát đủ dung lượng theo yêu cầu và khi

được yêu cầu trong khi chương trình đã chạy

– Bộ nhớ được cấp phát nằm trong vùng nhớ tự do còn lại của

máy tính (heap), chỉ phụ thuộc vào dung lượng bộ nhớ của

máy tính

– Bộ nhớ có thể được giải phóng khi không sử dụng tiếp.

. Linh hoạt:

– Thời gian "sống" của bộ nhớ được cấp phát động có thể kéo

dài hơn thời gian "sống" của thực thể cấp phát nó.

– Có thể một hàm gọi lệnh cấp phát bộ nhớ, nhưng một hàm

khác giải phóng bộ nhớ.

– Sự linh hoạt cũng dễ dẫn đến những lỗi "rò rỉ bộ nhớ".

13

Chương 3: Cấu trúc dữ liệu

Ví dụ sử dụng bộ nhớ động trong hàm

Date* createDateList(int n) {

Date* p = new Date[n];

return p;

}

void main() {

int n;

cout << "Enter the number of your national

holidays:";

cin >> n;

Date* date_list = createDateList(n);

for (int i=0; i < n; ++i) {

...

}

for (....) { cout << ....}

delete [] date_list;

}

14

Chương 3: Cấu trúc dữ liệu

Các thuật toán trên mảng

. Các thuật toán sắp xếp

. Thuật toán tìm kiếm chia đôi (tìm kiếm nhị phân)

15

Chương 3: Cấu trúc dữ liệu

Các thuật toán sꢀp xếp trên mảng

. Các giải thuật sắp xếp cơ bản

– Sắp xếp chọn (selection-sort)

– Sắp xếp nổi bọt (bubble, exchange-sort)

– Sắp xếp chèn (insertion-sort)

. Các giải thuật sắp xếp nâng cao-Sắp xếp nhanh

– Sắp xếp nhanh (quick-sort)

– Sắp xếp vun đống (heap-sort)

– Sắp xếp hòa trộn (merge-sort)

. Quy ước:

– Giả sử các phần tử khóa cần sắp xếp là các số

– Sắp xếp thực hiện theo thứ tự từ nhỏ đến lớn

16

Chương 3: Cấu trúc dữ liệu

Sꢀp xếp chꢁn ( selection-sort )

. Nguyên tắc

– Lượt 1: tìm khóa nhỏ nhất trong n khóa đưa lên vị trí thứ

nhất (đổi chỗ với khóa đầu tiên)

– Lượt 2: tìm khóa nhỏ nhất trong n-1 khoá còn lại đưa lên vị

trí thứ 2 (đổi chỗ với khóa thứ 2)

– ...

– Lượt i: tìm khóa nhỏ nhất trong (n-i+1) khoá còn lại đưa lên

vị trí thứ i (đổi chỗ với khóa thứ i)

. Ví dụ:

– Sắp xếp:

25, 36, 31, 49, 16, 70, 88, 60

16, 36, 31, 49, 25, 70, 88, 60

16, 25, 31, 49, 36, 70, 88, 60

...

17

Chương 3: Cấu trúc dữ liệu

Sꢀp xếp chꢂn ( Insertion-sort )

. Nguyên tắc

– Giả sử đoạn đầu đã được sắp xếp, thêm một khóa mới => tìm vị trí

thích hợp cho khóa mới. Cứ làm như vậy từ 2 đến n khóa.

– So sánh và sắp xếp dần từ đằng sau danh sách khóa.

. Phân biệt hai trường hợp

– Trường hợp cần đưa lần lượt các khóa vào: nhập các khóa lần lượt

vào các ô nhớ. Dãy khóa: 25, 36, 31, 49, 16, 70, 88, 60

1: 25

2: 25, 36

3: 25, 31, 36

4: 25, 31, 36, 49

5: 16, 25, 31, 36, 49

6: ...

– Trường hợp các khóa đã có và cần sắp xếp lại: dùng ô nhớ phụ

(biến) X để lưu tạm các giá trị cần dịch chuyển. Hướng dịch chuyển:

dần về đầu.

– 1: 25, 36, 31, 49, 16, 70, 88, 60

– 2: 25, 36, 31, 49, 16, 70, 88, 60

– 3: 25, 31, 36, 49, 16, 70, 88, 60

4: 25, 31, 36, 49, 16, 70, 88, 60

5: 16, 25, 31, 36, 49, 70, 88, 60

6: ...

18

Chương 3: Cấu trúc dữ liệu

Sꢀp xếp nꢃi bꢁt (Bubble-sort)

. Nguyên tắc

– Duyệt bảng khoá (danh sách khoá) từ đáy lên đỉnh

– Dọc đường nếu thứ tự 2 khoá liền kế không đúng => đổi chỗ

. Ví dụ:

– 1: 25, 36, 31, 60, 16, 88, 49, 70

– 2: 16, 25, 36, 31, 60, 49, 88, 70

– 3: 16, 25, 31, 36, 49, 60, 70, 88

. Nhận xét

– Khoá nhỏ sẽ nổi dần lên sau mỗi lần duyệt => “nổi bọt”

– Sau một vài lần (không cần chạy n bước), danh sách khoá đã

có thể được sắp xếp => Có thể cải tiến thuật toán, dùng 1

biến lưu trạng thái, nếu không còn gì thay đổi (không cần đổi

chỗ) => ngừng

19

Chương 3: Cấu trúc dữ liệu

Sꢀp xếp nhanh (quick-sort) hay Sꢀp xếp phân đoạn

. Nguyên tắc

– Chiến lược chia để trị

– Chọn mốc (bất kỳ) để phân thành từng đoạn (partition) (2 đoạn)

– Khoá của mốc sẽ đứng giữa: Left Keys <= key(mốc) <= Right Keys

. Thuật toán

– 1: Quy ước: luôn chọn phần tử đầu tiên làm mốc.

– 2: Tìm vị trí thực của khóa mốc để phân thành 2 đoạn:

 1: Dùng 2 chỉ số: i, j chạy từ hai đầu DS. Chạy i từ đầu

DS trong khi khóa còn nhỏ hơn khóa mốc

 2: Nếu khóa >= khóa mốc: chạy j. Lưu phần tử hiện tại =

X

 3: Chạy j trong khi khóa lớn hơn khóa mốc

 4: Nếu khóa <= khóa mốc: dừng và đổi chỗ phần tử hiện

tại cho X

 5: Tiếp tục thực hiện như vậy cho đến khi i>=j thì đổi chỗ

Kj cho khóa mốc. Lúc đó khóa mốc sẽ nằm đúng vị trí.

– 3: Làm giống như vậy cho các đoạn tiếp theo

20

Chương 3: Cấu trúc dữ liệu