HUTECH

TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHỆ ------------

CẤU TRÚC DỮ LIỆU & GT

CHƯƠNG 1

GV: ThS. NGUYỄN HÀ GIANG

TP. HCM – 1/2009

T G & L D T C

1

HUTECH

Nội dung

• Dự án tin học

• Chương trình máy tính • Cấu trúc dữ liệu & giải thuật • Tiêu chuẩn đánh giá CTDL • Giải thuật • Kiểu dữ liệu trong máy tính • Độ phức tạp của giải thuật

– Biểu diễn đối tượng – Xử lý dữ liệu

T G & L D T C

2

HUTECH

Dự án tin học

Bài toán giải quyết trong máy tính

Bài toán thực tế

Đối tượng dữ liệu

Xử lý trên đối tượng DL

T G & L D T C

3

HUTECH

Tổ chức biểu diễn đối tượng

• Dữ liệu thực tế:

thích hợp nhất – Phản ánh chính xác dữ liệu thực tế – Dễ dàng xử lý trong máy tính!

– Muôn hình vạn trạng, đa dạng, phong phú – Thường có chứa đựng quan hệ với nhau • Cần phải tổ chức biểu diễn thành cấu trúc

Xây dựng CTDL

T G & L D T C

4

HUTECH

Xây dựng thao tác xử lý DL

Dựa trên Y/C cụ thể, xác định các trình tự giải quyết vấn đề trên máy tính để đưa kết quả mong muốn

Đối tượng DL

Thao tác xử lý

Kết quả mong muốn

T G & L D T C

5

HUTECH

Chương trình máy tính

Quan hệ chặt chẽ

Cấu trúc dữ liệu

Giải thuật

Chương trình

T G & L D T C

6

HUTECH

CTDL & Giải thuật

• Có mối quan hệ mật thiết

– Giải thuật phản ánh phép xử lý, còn đối tượng xử

lý của giải thuật là dữ liệu.

– Với CTDL đã chọn sẽ có những giải thuật tương

ứng phù hợp.

– Khi CTDL thay đổi thì GT cũng thay đổi tránh xử lý gượng ép, thiếu tự nhiên trên cấu trúc ko thích hợp.

– CTDL tốt giúp giải thuật xử lý phát huy tốt đa

khả năng.

T G & L D T C

7

HUTECH

Ví dụ

Quản lý điểm học sinh: gồm có 4 điểm, và 3 học sinh Thao tác duy nhất là xuất điểm số từng môn học của học sinh!

Học sinh Tiên Tùng Thảo Toán 7 9 8 Lý 9 5 6 Hoá 5 8 9 Văn 6 7 5

T G & L D T C

8

HUTECH

Ví dụ

– int result[12] = { 7, 9, 5, 6, 9, 5, 8, 7, 8, 6, 9, 5 };

• Phương án A: dùng mảng 1 chiều

7 9 5 6 9 5 8 7 8 6 9 5

Tiên

Tùng

Thảo

T G & L D T C

9

HUTECH

Ví dụ

• Truy xuất điểm môn j của hs i là phần tử tại dòng i và cột j

– Bảng điểm(i, j)  result[((i-1)*số cột)+j]

• Ngược lại

– Result[i]  Bảng điểm(dòng((i/số cột)+1), cột((i-1) %số cột)+1)

• Thao tác xử lý như sau:

void XuatDiem() {

const int so_mon = 4; int sv, mon; for( int i=0; i < 12; i++) {

sv = i/so_mon; mon = i % so_mon; printf(“Diem mon %d của sv % d là %d”, mon, sv, result[i]);

}

}

T G & L D T C

10

HUTECH

Ví dụ

– Sử dụng mảng 2 chiều – int result[3][4] = { {7, 9, 5, 6}, {9, 5, 8, 7}, {8, 6, 9, 5} };

• Phương án B:

Cột 0 7 9 8 Cột 1 9 5 6 Cột 2 5 8 9 Cột 3 6 7 5 Dòng 0 Dòng 1 Dòng 2

T G & L D T C

11

HUTECH

Ví dụ

• Truy xuất điểm số môn j của học sinh i là phần tử dòng i và

cột j trong bảng – Bảng điểm(dòng i, cột j)  result[i][j]

• Theo phương án này thì phần xử lý như sau:

void XuatDiem() {

int so_mon = 4, so_sv=3; for(int i=0; i < so_sv; i++)

for(int j=0; j

{

printf(“Diem mon %d của sv %d là %d”, j, i, result[i][j]);

}

}

T G & L D T C

12

HUTECH

Ví dụ

• Nhận xét: về 2 phương án

– Phương án B cung cấp cấu trúc dữ liệu phù hợp

với thực tế hơn!

– Do đó giải thuật xây dựng trên CTDL B cũng

đơn giản và tự nhiên hơn.

T G & L D T C

13

HUTECH

Các tiêu chuẩn đánh giá CTDL

• Phản ánh đúng thực tế:

– Thể hiện được đầy đủ thông tin nhập/xuất của bài

• VD:

toán.

– Chọn kiểu dữ liệu nguyên lưu trữ tiền thưởng bán

hàng (TienThuong) • TienThuong = trị giá hàng * 5%

T G & L D T C

14

HUTECH

Các tiêu chuẩn đánh giá CTDL

• Phù hợp với thao tác xử lý:

– Tăng tính hiệu quả của chương trình  hiệu quả

• VD:

của dự án tin học.

– Dữ liệu được cập nhật thêm, xoá liên tục nên

dùng cấu trúc danh sách liên kết!

– Dữ liệu có kích thước cố định, không thêm xóa

thì dùng mảng (có thể tĩnh)

T G & L D T C

15

HUTECH

Các tiêu chuẩn đánh giá CTDL

• Tiết kiệm tài nguyên hệ thống:

– Sử dụng tài nguyên vừa đủ để thực hiện chức

• VD:

năng & nhiệm vụ.

T G & L D T C

16

HUTECH

Các tiêu chuẩn đánh giá CTDL

• Sự thích hợp giữa CTDL & NNLT:

– Dễ dàng cài đặt trên ngôn ngữ được chọn

T G & L D T C

17

HUTECH

Thuật toán - giải thuật

• Thuật toán: hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định dãy thao tác trên CTDL, sao cho – Một bộ dữ liệu vào – Sau một số hữu hạn bước thực hiện thao tác chỉ

ra.

– Kết quả đạt được theo mục tiêu đã định.

T G & L D T C

18

HUTECH

Thuật toán - giải thuật

•

Các đặc trưng của thuật toán 1. Tính đơn nghĩa: • Đơn định: • Ngẫu nhiên:

2. Tính dừng: 3. Tính đúng: 4. Tính phổ dụng:

T G & L D T C

19

HUTECH

Thuật toán - giải thuật

5. Tính khả thi:

1. Kích thước phải đủ nhỏ 2. Thuật toán phải chuyển được thành chương

trình

3. Thuật toán phải được máy tính thực hiện

trong thời gian cho phép

T G & L D T C

20

HUTECH

VD về giải thuật

• Input: hai số nguyên a và b khác 0 • Output: ước số chung lớn nhất của a và b • Các bước thực hiện như sau (Euclide)

– B1: nhập a và b: số tự nhiên – B2: nếu B ≠ 0 sang B3, ngược lại qua B4 – B3: đặt r = a mod b; a = b; b = r; quay lại B2 – B4: kết quả USCLN là giá trị a. Kết thúc thuật

toán

T G & L D T C

21

HUTECH

VD về giải thuật

Begin

Sinh viên cài đặt

Input a, b

no

b >0

Output a

yes

r := a mod b; a :=b; b :=r;

End

T G & L D T C

22

HUTECH

Bài toán  chương trình

• Bài toán thực tế

Làm ntn ?

Phải làm gì?

– Xác định bài toán

T G & L D T C

23

HUTECH

Các bước tiếp cận bài toán

1. Mô hình hoá bài toán 2. Tìm giải thuật trên mô hình đó 3. Hình thức hoá giải thuật thông qua các thủ tục hay

mã giả

4. Cài đặt giải thuật trên NNLT cụ thể

Mô hình toán học

Kiểu DL trừu tượng

CTDL

Giải thuật hình thức

Chương trình mã giả

CT Pascal, C, Java,C#...

T G & L D T C

24

HUTECH

Kiểu dữ liệu trừu tượng

– Làm đơn giản hóa, sáng sủa, dễ hiểu hơn. – Che đi phần chi tiết, làm nổi bật cái tổng thể

• Trừu tượng hoá:

• Trừu tượng hoá dữ liệu: đưa ra các kiểu dữ liệu trừu

tượng (Abstract Data Type)

– Mô tả dữ liệu – Tác vụ liên quan

• ADT: gồm

• VD: tập số nguyên với các phép toán hợp, giao,

hiệu là kiểu dữ liệu trừu tượng.

T G & L D T C

25

HUTECH Kiểu dữ liệu trừu tượng

T =

• V: là tập giá trị, miền giá trị mà kiểu T có thể

nhận

• O: là tập các thao tác cơ bản được định nghĩa

trên V

T G & L D T C

26

HUTECH Kiểu dữ liệu trừu tượng

• T: int • V: {-32768…32767} • O: {+,-,*,/, %,>,<,>=,<=…}

T G & L D T C

27

HUTECH Kiểu dữ liệu trừu tượng

• Cài đặt theo hướng cấu trúc

– Sử dụng trong lập trình thủ tục – Xây dựng thao tác dưới dạng thủ tục/hàm – Các thao tác & dữ liệu (V, O) tách rời nhau – Dữ liệu không được “bảo vệ”, do có thể truy xuất

ở bất cứ đâu trong phạm vi dữ liệu khai báo!

T G & L D T C

28

HUTECH Kiểu dữ liệu trừu tượng

• Cài đặt theo hướng đối tượng

– Dữ liệu và thao tác được tích hợp lại – Dữ liệu được ẩn và được bảo vệ, tránh những

truy xuất trực tiếp

– Chương trình chỉ truy xuất đến dữ liệu thông qua

các thao tác định nghĩa

– Che dấu những xử lý cục bộ, chỉ đưa ra thao tác

thật sự cần thiết!

– Nâng cao tính module hóa chương trình

T G & L D T C

29

HUTECH

Kiểu dữ liệu – CTDL - ADT

• Kiểu dữ liệu: một tập hợp các giá trị và một tập hợp

AND, OR, NOT…

– Kiểu Integer là tập hợp các số nguyên có giá trị từ -32768 đến 32767 với các phép toán cộng trừ nhân chia, mod…

các phép toán trên các giá trị đó – Kiểu boolean gồm 2 giá trị {true, false} và các phép toán

– Kiểu DL sơ cấp – Kiểu dữ liệu cấu trúc hay cấu trúc dữ liệu.

• Kiểu dữ liệu:

T G & L D T C

30

HUTECH

Kiểu dữ liệu cơ bản

• Thường đơn giản và ko có cấu trúc, được NNLT

xây dựng sẵn, nên còn gọi là kiểu dữ liệu dựng sẵn.

– số nguyên – số thực – ký tự – giá trị logic

• Thường là các trị vô hướng:

T G & L D T C

31

HUTECH

Kiểu dữ liệu cơ bản

Tên kiểu

KT

Miền giá trị

Ghi chú

-128 đến 127

char

01

Có thể dùng như số nguyên 1 byte có dấu hay kiểu ký tự

0 đến 255

Số nguyên 1 byte ko dấu

unsigned char

01

-32768 đến 32767

int

02

0 đến 65355

Gọi tắt là unsigned

unsigned int

02

-232 đến 231 -1

long

04

0 đến 232 -1

unsigned long

04

3.4E-38 … 3.4E38

float

04

Giới hạn chỉ trị tuyệt đối.Các giá trị <3.4E-38 được coi = 0. Tuy nhiên kiểu float chỉ có 7 chữ số có nghĩa.

1.7E-308 … 1.7E308

double

08

3.4E-4932 …1.1E4932

long double

10

T G & L D T C

32

HUTECH

Kiểu dữ liệu cấu trúc

• Kết hợp nhiều kiểu dữ liệu cơ bản để phản

ánh bản chất của đối tượng thực tế

• Đa số các NN đều cài đặt sẵn một số kiểu có cấu trúc cơ bản như mảng, chuỗi, tập tin, bản ghi…

• Ngoài ra cung cấp cơ chế cho người lập trình

cài đặt các dữ liệu cấu trúc khác.

T G & L D T C

33

HUTECH

Kiểu dữ liệu cấu trúc

• Cấu trúc dữ liệu SV

Mã SV: chuỗi kt / số nguyên

Tên SV: chuỗi kt

Ngày sinh: ngày tháng

Nơi sinh: chuỗi kt

Điểm thi: số nguyên

Sinh viên

T G & L D T C

34

HUTECH

Kiểu dữ liệu cấu trúc

• Hiện thực

– Kiểu dữ liệu cơ sở cho phép mô tả

thông tin:

typedef struct tagSV {

• int DiemThi

– Thông tin khác đòi hỏi kiểu dữ liệu

char MSSV[15];

cấu trúc:

char TenSV[30];

char NoiSinh[30];

• char MSSV[15]; • char TenSV[30]; • char NoiSinh[30];

Date NgaySinh;

– Thông tin ngày tháng năm sinh dùng

struct:

int DiemThi;

• typedef struct tagDate

{

} SinhVien;

char ngay; char thang; char nam;

} Date;

T G & L D T C

35

HUTECH

Độ phức tạp của giải thuật

• Sự cần thiết phân tích giải thuật

GT A

GT C

GT tốt

GT B

Vấn đề cần giải quyết

1. Giải thuật đúng 2. Giải thuật đơn giản 3. Giải thuật thực hiện nhanh

T G & L D T C

36

HUTECH

Thời gian thực hiện

• Thời gian thực hiện phụ thuộc vào

• Thời gian thực hiện một chương trình là một hàm theo kích thước dữ liệu vào: T(n), n là kích thước của dữ liệu vào.

– Giải thuật – Tập chỉ thị của máy tính – Cấu hình của máy tính (tốc độ) – Kỹ năng của người lập trình

T G & L D T C

37

HUTECH

Thời gian thực hiện

• Đơn vị của T(n) : theo số lệnh được thực hiện. • T(n) = Cn:  CT cần Cn chỉ thị thực thi • Thời gian thực hiện xấu nhất: do tính chất dữ

liệu cũng ảnh hưởng – Chương trình sắp xếp sẽ cho thời gian khác nhau

•  T(n) thường được xem là TG chương trình

thực hiện xấu nhất trên DL kích thước n.

với các bộ DL có thứ tự khác nhau!

T G & L D T C

38

HUTECH

Tỉ suất tăng

• Hàm ko âm T(n) có tỉ suất tăng f(n) nếu tồn tại

các hằng số C và N0 sao cho: – T(n) < Cf(n), với mọi n ≥ N0 – “cho hàm ko âm T(n) bất kỳ, ta luôn tìm được tỷ

• Giả sử T(0) =1, T(1) = 4, tổng quát T(n) = (n+1)2.

suất tăng f(n) của nó”

– Đặt N0 = 1, và C = 4, thì  n ≥ 1, chứng minh được rằng T(n) = (n+1)2 ≤ 4n2,  n ≥ 1, tỉ suất tăng khi đó n2

T G & L D T C

39

HUTECH

Độ phức tạp giải thuật

T2(n) = 5n3

T1(n) = 100n2

• Khi n đủ lớn: n > 20, thì T1(n) < T2(n) • Cách hợp lý nhất là xét tỷ suất tăng của hàm TG thực hiện CT thay vì chính bản thân thời gian thực hiện.

T G & L D T C

40

HUTECH

Độ phức tạp giải thuật

• Cho hàm T(n), T(n) có độ phức tạp f(n) nếu

tồn tại các hằng C, N0 sao cho: – T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỉ suất tăng là f(n) và ký hiệu T(n) là O(f(n))

– VD: T(n) = (n+1)2 có tỷ suất tăng là n2 nên T(n)

= (n+1)2 là O(n2).

– Lưu ý: O(Cf(n)) = O(f(n)) với C là hằng số.

• Nói cách khác độ phức tạp tính toán giải thuật là hàm chặn trên của hàm thời gian

O(C) = O(1).

T G & L D T C

41

HUTECH

Độ phức tạp giải thuật

• Các độ phức tạp thường gặp:

• Thông thường thuật giải có độ phức tạp đa

thức thì có thể cài đặt

• Còn phức tạp ở mức hàm mũ thì phải cải tiến

giải thuật!

– Log2n, n, nlog2n, n2, n3, 2n, n!, nn

T G & L D T C

42

HUTECH

Qui tắc tính độ phức tạp

• Thời gian thực hiện lệnh gán, đọc/ghi dữ liệu là O(1). • Thời gian thực hiện một chuỗi tuần tự các lệnh được

xác định bằng quy tắc cộng.

• Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện sau THEN hoặc ELSE và thời gian điều kiện. Thường thời gian điều kiện là O(1).

• Thời gian thực hiện vòng lặp là tổng thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp ko đổi thì tg thực hiện vòng lặp là tích số lần lặp với thời gian thực hiện thân vòng lặp

T G & L D T C

43

HUTECH

VD tính độ phức tạp

if (a[j-1] > a[j]){

• VD giải thuật sắp xếp nổi bọt – (1) for(i = 0; i < n-1; i++) for(j=n-1; j >i; j--) – (2) – (3) – (4) – (5) – (6) – (7)

temp = a[j-1]; a[j-1] = a[j]; a[j] = temp;

}

T G & L D T C

44

HUTECH

VD tính độ phức tạp

• VD hàm tìm kiếm tuần tự i=0; found = false; while ( i

found = true;

else

i++;

return found; – (1) – (2) – (3) – (4) – (5) – (6) – (7) – (8)

T G & L D T C

45

HUTECH

Tài liệu tham khảo

[1]. Cấu trúc dữ liệu & thuật toán, Dương Anh Đức, Trần Hạnh Nhi, ĐHKHTN, 2000.

[2]. Kỹ thuật lập trình, Học viện BCVT, 2002. [3]. Cấu trúc dữ liệu, Nguyễn Trung Trực,

ĐHBK, 1992.

[4]. Giải thuật & lập trình, Lê Minh Hoàng,

ĐHSPHN, 1999-2002.

[4]. Fundamentals of Data Structures, Ellis

Horowitz, Sartaj Sahni

[5]. Foundations of Algorithms Using C++

Pseudocode, Richard Neapolitan and Kumarss, Jones and Bartlett Publishers © 2004

[6]. Giải thuật, Nguyễn Văn Linh, ĐH Cần thơ, 2003

T G & L D T C

46