CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

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

1

Nội dung

Chương 1. Tổng quan về giải thuật & cấu trúc dữ liệu

1.1. Vai trò của cấu trúc dữ liệu trong một đề án tin học

1.2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu

1.3. Kiểu dữ liệu

1.3.1. Định nghĩa kiểu dữ liệu

1.3.2. Các kiểu dữ liệu cơ bản

1.3.3. Các kiểu dữ liệu có cấu trúc

2

1.3.4. Một số kiểu dữ liệu có cấu trúc cơ bản

1.4. Đánh giá độ phức tạp giải thuật

Nội dung

Chương 2. Tìm kiếm và sắp xếp

2.1. Nhu cầu tìm kiếm, sắp xếp dữ liệu trong một hệ thống thông tin

2.2. Các giải thuật tìm kiếm nội

2.2.1. Tìm kiếm tuyến tính

2.2.2. Tìm kiếm nhị phân

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

2.3.1. Định nghĩa bài toán sắp xếp

3

2.3.2. Phương pháp chọn trực tiếp

Nội dung

1.

Các phương pháp sắp xếp do sinh viên tự nghiên cứu và thuyết trình

2.

Phương pháp Shaker sort

3.

Phương pháp sắp xếp cây (Heap sort)

4.

Phương pháp sắp xếp với độ dài bước giảm dần (Shell sort)

5.

Phương pháp sắp xếp theo phương pháp trộn trực tiếp (Merge sort)

6.

Phương pháp sắp xếp theo phương pháp cơ số (Radix sort)

4

Phương pháp sắp xếp đếm phân khối

Nội dung

Chương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiều

3.1. Ngăn xếp

3.1.1. Giới thiệu

3.1.2. Các thao tác trên ngăn xếp

3.1.3. Các ứng dụng

Tính các biểu thức đại số

Quản lý bộ nhớ khi thi hành chương trình

3.2. Hàng đợi

5

3.2.1. Giới thiệu

3.2.2. Các thao tác trên hàng đợi

Nội dung

• Tổ chức bộ đệm bàn phím

• Quản lý các tiến trình trong các hệ điều hành

• Vét cạn

3.2.3. Các ứng dụng

• Khử đệ quy

• Tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay

Nội dung sinh viên tự nghiên cứu và thuyết trình

6

lui

Nội dung

Chương 4. Cấu trúc dữ liệu động

4.1. Đặt vấn đề

4.2. Kiểu dữ liệu con trỏ

4.2.1. Biến không động

4.2.2. Kiểu con trỏ

4.2.3. Biến động

4.3. Danh sách liên kết

4.3.1. Định nghĩa

7

4.3.2. Các hình thức tổ chức danh sách

Nội dung

4.4. Danh sách đơn

4.4.1. Tổ chức danh sách đơn theo cấp phát liên kết

4.4.2. Các thao tác cơ bản trên danh sách đơn

4.4.3. Sắp xếp danh sách

4.4.4. Các cấu trúc đặc biệt của danh sách đơn

4.5. Một số cấu trúc dữ liệu dạng danh sách liên kết khác

4.5.1. Danh sách liên kết kép

4.5.2. Danh sách liên kết vòng

4.5.3. Danh sách có nhiều mối liên kết

8

4.5.4. Danh sách tổng quát

Nội dung

• Hàng đợi

• Ngăn xếp

9

Nội dung sinh viên tự nghiên cứu & thuyết trình

Nội dung

Chương 5. Cấu trúc cây

5.1. Cấu trúc cây

5.1.1. Một số khái niệm cơ bản

5.1.2. Một số ví dụ về đối tượng các cấu trúc dạng cây

5.2. Cây nhị phân

5.2.1. Một số tính chất của cây nhị phân

5.2.2. Biểu diễn cây nhị phân T

5.2.3. Duyệt cây nhị phân

5.2.4. Biểu diễn cây tổng quát bằng cây nhị phân

10

5.2.5. Một cách biểu diễn cây nhị phân khác

Nội dung

5.3. Cây nhị phân tìm kiếm. Các thao tác trên cây nhị phân tìm kiếm

5.4. Cây nhị phân cây cân bằng

5.4.1. Cây nhị phân cân bằng hoàn toàn

11

5.4.2. Cây nhị phân cân bằng

Nội dung

Chương 6: Bảng băm (Hash Table)

Nội dung sinh viên tự nghiên cứu & thuyết trình

6.1. Phương pháp băm

6.2. Các hàm băm

6.3. Phương pháp giải quyết đụng độ

6.4. Phân tích bảng băm

12

6.5. Kết luận so sánh các phương pháp

Chương 1 Tổng quan về giải thuật và cấu trúc dữ liệu

13

Mục tiêu

• Giới thiệu vai trò của tổ chức dữ liệu

• Mối quan hệ giữa GT & CTDL

• Các khái niệm và yêu cầu về CTDL

• Nhắc lại các kiểu dữ liệu trong C++

• Tổng quan về đánh giá độ phức tạp GT

14

Xét đoạn chương trình sau

void main()

{

int n;

cout<<"Nhap vao so nguyen n: ";

cin>>n;

if(n%2==0)

cout<<"La so chan";

else

cout<<"La so le";

15

}

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

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

• Phù hợp với thao tác

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

16

Khái niệm về kiểu dữ liệu

T = V = {Tập các giá trị} O = {Tập các thao tác xử lý}

Ví dụ: Kiểu dữ liệu số nguyên short trong ngôn ngữ C++

T = short V = {-32768, 32767} O = {+, -, *, /, %}

17

Khái niệm về kiểu dữ liệu

• Các thuộc tính của một kiểu dữ liệu gồm:

•

•

•

•

Tên Miền giá trị Kích thước lưu trữ Tập các thao tác tác động lên kiểu dữ liệu đó

• Các loại kiểu dữ liệu

•

•

Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản Kiểu dữ liệu có cấu trúc hướng giải quyết vấn đề: Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, …

18

Khái niệm về kiểu dữ liệu

Tĩnh

ở

ộ

ị •   Đ c  đ nh  nghĩa

ờ   th i

ượ ể

ị

Đ ngộ ớ ế ắ •   Đ c  g n  k t  v i  m t  ể ờ ạ i th i đi m biên

đi m biên d ch.

ượ con tr  ỏ (t ư ị d ch ch a có).

ự

ượ

ấ

ở

•  Phát sinh lúc th c thi.

•   Đ c  c p  phát

ờ   th i

ể

ị

ị

đi m liên k t. ể

ị •  Không xác đ nh giá tr  ban

ầ ữ ậ

ừ

đ u. ầ

ế

ỏ ộ i phóng kh i b

i  đ n  khi  k t  thúc

ượ •  Đ c gi ớ

ả ầ

nh  khi c n.

ế •   Có  th   có  giá  tr   ban  đ u  tùy theo t ng ngôn ng  l p  trình. ồ ạ ế •   T n  t ươ ng trình.

ch

19

Nhắc lại các kiểu dữ liệu C++

• Kiểu cơ sở: Số nguyên, số thực và kiểu logic

• Kiểu dãy (mảng), xâu ký tự

• Kiểu có cấu trúc

20

Kiểu số nguyên

Stt

Tên ki uể

Ghi chú

Kích th

cướ

1

char

1 byte 1 byte

2

unsigned char short

1 byte 2 bytes

3 4

unsigned short int

2 bytes 4 bytes

5 6

21

unsigned int long

4 bytes 4 bytes

7 8

Ky  t́ ự ́ Sô  nguyên ́ Sô  nguyên  ngươ d ́ Sô  nguyên ố S  nguyên  ngươ d ́ Sô  nguyên ́ Sô  nguyên  ngươ d ́ Sô  nguyên  ́ Sô  nguyên

unsigned long

d

ngươ

4 bytes

Kiểu số thực

Tên ki uể

Ghi chú

Kích th

cướ

Stt 1 2 3

float double long double

4 bytes 8 bytes 8 bytes

ể

ậ

Ki u lu n lý

Tên ki uể

cướ

Stt 1

bool

Ghi chú ồ G m 2 giá tr :

Kích th ị true ho c ặ false

22

Kiểu mảng 1 chiều

5

7

10 … 3

11

2

0

1

2 …

n-2 n-1

Giá trị Vị trí • Khai báo

[];

• Gán giá trị ban đầu

VD: int a[100];

VD1: int a[100] = {0};

VD2: int a[5] = {3, 6, 2, 10, 17};

23

hoặc: int a[] = {3, 6, 2, 10, 17};

Kiểu mảng 1 chiều

- Khởi tạo phát sinh ngẫu nhiên

Phát sinh ngẫu nhiên

- Phát sinh giá trị ngẫu nhiên

srand((unsigned int)time(NULL));

int x = rand()%k;

k: Số nguyên dương x (cid:0) [0..k-1]

VD: Phát sinh 1 số nguyên có giá trị từ 0 đến 50

srand((unsigned int)time(NULL));

24

int x = rand()%51;

Kiểu xâu ký tự

• Khai báo

char [] ;

• Xem lại các hàm

- cin.getline, cin.ignore

- strcpy, strcat, strlen

- strcmp, stricmp

- strchr, strstr

25

VD: char hoten[50];

Kiểu mảng/ xâu ký tự – Con trỏ

• Mảng 1 chiều

*;

• Xâu ký tự

VD: int *a;

char *;

26

VD: char *hoten;

Kiểu mảng/ xâu ký tự – Con trỏ

Lưu ý khi sử dụng phải cấp phát biến con trỏ bằng lệnh new, hủy bằng lệnh delete

VD:

int *a;

int n = 10;

a = new int[n];

…..

27

delete a;

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

struct tên_struct

{

khai báo các thuộc tính;

};

28

typedef struct tên_struct tên_kiểu;

Ví dụ kiểu dữ liệu có cấu trúc

struct ttDate

{

char thu[9];

unsigned char ngay;

unsigned char thang;

int nam;

};

29

typedef struct ttDate DATE;

Truy cập thành phần có cấu trúc

• Biến cấu trúc kiểu tĩnh

.thành phần cấu trúc

VD:

DATE d;

30

d.nam = 2012;

Truy cập thành phần có cấu trúc

• Biến cấu trúc kiểu con trỏ

->thành phần cấu trúc

VD:

DATE *d;

31

d->nam = 2012;

Vai trò của CTDL & GT

Giải thuật

Cấu trúc dữ liệu

Chương trình

32

Cấu trúc dữ liệu?

• Cách thức liên kết/ tổ chức các kiểu dữ liệu cơ sở/ kiễu dữ liệu

• Tập các thao tác để truy cập/ xử lý các thành phần dữ liệu

• Ví dụ:

• Danh sách liên kết (Linked List)

• Ngăn xếp (Stack)/ Hàng đợi (Queue)

• Cây (Tree)

33

có cấu trúc hợp lý để sử dụng một cách hiệu quả

Khái niệm về giải thuật

• Là một thủ tục tính toán xác định (well-defined) nhận các giá trị hoặc một tập các giá trị (input) và sinh ra một vài giá trị hoặc tập giá trị (output)

è Cách thức/ quy trình thực hiện hoàn thành một công việc xác

định cụ thể nào đó.

34

VD Cộng 2 số, tính tổng dãy Fibonaci, …

Các phương pháp biểu diễn giải thuật

• Lưu đồ

• Mã giả

• Mã tự nhiên

35

Các ký hiệu lưu đồ

Bắt đầu/ kết thúc

Rẽ nhánh

ị ả ề

Giá tr  tr  v

Điề u kiện

ể

ố Đi m n i

Luồng xử lý

Khối xử lý

36

Nhập/ Xuất

Ký hiệu mã giả

• IF <điều kiện> THEN …ENDIF

• IF <điều kiện> THEN ... ELSE ... ENDIF

• WHILE <điều kiện> DO … ENDWHILE

• DO … UNTIL <điều kiện>

• DISPLAY …

• RETURN …

37

Ví dụ mô tả giải thuật

• Đầu vào: 2 số nguyên dương a và b

• Đầu ra: ước số chung lớn nhất của a và b

38

Tìm ước số chung lớn nhất của 2 số nguyên dương a và b

Mô tả bằng mã tự nhiên

Bước 1: Nếu a = b thì kết luận a là ước số chung lớn nhất, kết

thúc

Bước 2: Nếu a > b thì a = a – b;

Ngược lại thì b = b – a;

39

Bước 3: Quay trở lại Bước 1

Mô tả bằng mã giả

WHILE a ≠ b DO

IF a>b THEN

a=a-b

ELSE

b=b-a

ENDIF

ENDWHILE

40

DISPLAY a

Mô tả bằng lưu đồ

41

Tiêu chuẩn đánh giá giải thuật

1. Tính đúng đắn

2. Tính đơn giản

3. Tính hiệu quả

Thông thường so sánh các thuật toán dựa vào độ

phức tạp về thời gian thực thi: độ phức tạp của

thuật toán (algorithm complexity)

42

 ước lượng số phép tính cần thực hiện

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

• Phụ thuộc vào ngôn ngữ lập trình

• Phụ thuộc vào người lập trình

• Phụ thuộc vào bộ dữ liệu thử

• Phụ thuộc vào phần cứng

43

Thời gian thực thi chương trình

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

• VD: Chương trình tính tổng của N số có thời gian thực hiện (số

• Thời gian thực thi chương trình là một hàm không âm, tức là

phép tính) là T(N) = c.N trong đó c là một hằng số

44

T(n) (cid:0) 0 (cid:0) n(cid:0) 0

Khái niệm độ phức tạp giải thuật

• Hàm T(N) có tỷ suất tăng (growth rate) là f(n) nếu tồn tại các

• VD: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(N) = (N+1)2. Đặt

hằng số c và N0 sao cho T(N) ≤ f(N) với mọi N ≥ N0

• VD: Tỷ suất tăng của hàm T(N) = 3N3 + 2N2 là N3. Đặt N0 = 0 và c = 5 ta dễ dàng chứng minh rằng với mọi N ≥ 0 thì 3N3 + 2N2 ≤ 5N3

45

N0 = 1 và c = 4 thì với mọi N ≥ 1 chúng ta dễ dàng chứng minh rằng T(N) = (N+1)2 ≤ 4N2 với mọi N ≥ 1, tức là tỷ suất tăng của T(N) là N2

Khái niệm độ phức tạp giải thuật

Hàm mũ

46

Quy tắc tính độ phức tạp giải thuật

• Quy tắc cộng

Nếu T1(N) và T2(N) là thời gian thực hiện của hai đoạn chương

trình P1 và P2; và T1(N)=O(f(N)), T2(N)=O(g(N)

 thời gian thực hiện của đoạn hai chương trình đó nối tiếp

47

nhau là T(N)=O(max(f(N), g(N)))

Quy tắc tính độ phức tạp giải thuật

• Quy tắc nhân

Nếu T1(N) và T2(N) là thời gian thực hiện của hai đoạn chương

 thời gian thực hiện của đoạn hai đoạn chương trình đó lồng

trình P1và P2 và T1(N) = O(f(N)), T2(N) = O(g(N)

48

nhau là T(N) = O(f(N).g(N))

Bài tập 1

Bước 1: i = 1;

Bước 2:

j = N;

Trong khi (j > i) thực hiện:

Nếu a[j]

tạm = a[i];

a[i]=a[j];

a[j]=tạm;

j = j-1;

49

Bước 3:

i = i+1;

Nếu i = N: Dừng

Ngược lại: Lặp lại Bước 2.

Tính độ phức tạp của giải thuật trên?

Cấu trúc điều khiển trong C++

TUẦN TỰ

Lệnh 1; Lệnh 2; Lệnh 3; ….

if if … else

RẼ NHÁNH CÓ ĐIỀU KIỆN

switch … case

LỰA CHỌN

LẶP

for while do … while

50

Cấu trúc rẽ nhánh

Cấu trúc rẽ nhánh chỉ cho phép thực hiện một dãy lệnh nào đó dựa vào kết quả của biểu thức điều kiện

Chỉ xét trường hợp đúng

if (biểu thức điều kiện)

{

;

}

Nếu biểu thức điều kiện cho kết quả true thì thực hiện khối lệnh bên trong if.

51

Cấu trúc rẽ nhánh

if (biểu thức điều kiện)

{

;

}

else

{

;

}

52

Nếu biểu thức điều kiện cho kết quả true thì thực hiện khối lệnh 1, ngược lại thì cho thực hiện khối Có thể lồng các cấu trúc if…else vào bên trong if/ else lệnh thứ 2

Cấu trúc lựa chọn

Có giá trị là hằng ký tự/ số nguyên

switch (biểu thức)

(cid:0)

ườ

ị ể

Tr

ợ ứ ằ

ng h p giá tr  bi u  th c b ng n1

case n1:

các câu lệnh ;

ườ

ị ể

Tr

break ;

ợ ứ ằ

ng h p giá tr  bi u  th c b ng n2

case n2:

các câu lệnh ;

break ;

………

ườ

ạ

Các tr

i

case nk:

ợ ng h p còn l ế

(n u có)

53

;

break ;

[default: các câu lệnh]

(cid:0)

Cấu trúc lặp

ở Kh i gán

ề

ệ ặ Đi u ki n l p

Yes

ố ệ

L nh ệ / Kh i l nh

ậ

ặ ậ C p nh t vòng l p

54

Cấu trúc lặp while

< Khởi gán>;

while (<điều kiện lặp>)

(cid:0)

lệnh/ khối lệnh;

;

55

(cid:0)

Cấu trúc lặp for

for (;<điều kiện lặp>;)

{

;

56

}

Cấu trúc lặp do…while

ở Kh i gán

ố ệ

L nh ệ / Kh i l nh

; do {

; ;

ậ

ặ ậ C p nh t vòng l p

} while (điều kiện);

Yes

ề

ệ ặ Đi u ki n l p

57

Bài tập 2

1.

2.

Cài đặt hàm nhập mảng số nguyên, n phần tử

Cài đặt hàm phát sinh n phần tử ngẫu nhiên cho mảng số

3.

nguyên

Cài đặt hàm phát sinh n phần tử ngẫu nhiên có giá trị tăng

58

dần cho mảng số nguyên

Bài tập 3

59

Viết lại các hàm trong Bài tập 2 dùng khai báo kiểu con trỏ

Bài tập 4

- Mã số

- Họ tên

- Điểm trung bình

60

Viết hàm nhập và hàm xuất thông tin của một sinh viên gồm các thông tin:

Bài tập 5

Viết lại các hàm trong Bài tập 4 sử dụng khai báo biến kiểu con

61

trỏ cấu trúc

Q&A

?

62