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

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

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

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

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ật2

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

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

Nội dung

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

Phương pháp Shaker sort

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

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

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

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

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

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

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

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

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

Nội dung

• Hàng đợi

• Ngăn xếp

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

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

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

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

Mục tiêu

• Giới thiệu tổng quan

• 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

Phân tích thiết kế hướng đối tượng

• Nguyên tắc là chia nhỏ vấn đề

à Xây dựng các lớp phù hợp: cung cấp các đối tượng có hành vi

• Chương trình là một kịch bản gồm các lời gọi các hành vị của

được mong đợi

à Các lớp đóng vai trò trung tâm trong việc hiện thực giải thuật

đối tượng lúc cần thiết

Phân tích thiết kế hướng đối tượng

• Điểm mạnh: tính đóng gói và tính kế thừa

• Gồm các lớp: CTDL, lớp đồ hoạ, lớp điều khiển, …

• Đặc trưng của lớp CTDL: lưu trữ và trả về dữ liệu, gồm các

thao tác: thêm, xoá, tìm kiếm và truy xuất

Vai trò của CTDL & GT

Giải thuật

Cấu trúc dữ liệu

Phương thức

Quá trình phân tích hướng đối tượng

• Xác định các lớp với các chức năng mong đợi

• Xác định kịch bản/ giải thuật chính: sự tương tác giữa các đối

• Hiện thực các lớp

tượng

Xây dựng lớp CTDL

1. Từ mô hình/ nhu cầu thực tế à các chức năng cần có của lớp

• Kiểu dữ liệu trả về của phương thức

2. Đặc tả các phương thức giao tiếp với bên ngoài:

• Các thông số vào / ra

• Các tiền kiện (precondition)

• Các hậu kiện (postcondition)

• Các lớp, hàm có sử dụng trong phương thức (uses)

3. Tìm hiểu phương án hiện thực lớp: phụ thuộc cách thức tổ chức dữ liệu bên trong, các giải thuật liên quan

4. Chọn phương án hiện thực

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

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

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

Ví dụ: KDL số nguyên short trong ngôn ngữ C#

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

Khái niệm về KDL

• Một KDL là một tập hợp, các phần tử của tập hợp này được gọi là

• Các thuộc tính của một KDL 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 KDL đó

• Các loại KDL

•

KDL nguyên tố (atomic) : có trị đơn KDL có cấu trúc (structured type): chứa nhiều KDL nguyên tố/ lồng các KDL có cấu trúc

các trị của KDL

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

• KDL nguyên tố: Số nguyên, số thực và kiểu logic

• Kiểu mảng, xâu ký tự

• KDL có cấu trúc

Số nguyên

ề

ị

.NET

Mi n giá tr

Mô tả

Kích cướ Th (byte)

ố

ươ

byte

Byte

[0..255]

S nguyên d không d uấ

ố

sbyte

Sbyte

[128..127]

ấ S nguyên có d u

ấ

ố

short

Int16

[0..65.535]

S nguyên không d u

ố

int

Int32

ấ S nguyên có d u

ừ ế

T 2.147.483.647 đ n 2.147.483.646

ừ

ấ

ố

uint

ế Uint32 T 0 đ n 4.294.967.295

S nguyên không d u

ố

long

Int64

ấ S nguyên có d u

ừ ế

T 9.223.370.036.854.775.808 đ n 9.223.370.036.854.775.807

ừ

ế

ấ

ố

ulong

Uint64 T 0 đ n 0xffff ffff ffff ffff

S nguyên không d u

Ký tự và logic

ề

.NET

ị Mi n giá tr

Mô tả

Kích c ướ th (byte)

bool

Boolean

ặ true ho c false

ị Giá tr logic

ự

char

Char

Ký t

Unicode

Số thực

ề

ị .NET Mi n giá tr

Mô tả

Kích c ướ th (byte)

ấ

float

Single

ừ T 3,4E38 ế đ n 3,4E+38

ấ

double

Double

ừ T 1,7E308 đ n ế 1,7E+308

ấ ữ ố ộ

decimal

Decimal

ấ ể Ki u d u ch m ữ ố ớ ộ đ ng, v i 7 ch s có nghĩa ấ ể Ki u d u ch m ộ ộ đ ng có đ chính ớ xác g p đôi, v i 15 ch s có nghĩa Có đ chính xác ố ế đ n 28 con s , ả ậ ố “m” ph i có h u t ặ 26 ho c “M” theo sau giá trị

Xâu ký tự (string)

• Kiểu String có thể chứa nội dung không giới hạn, vì đây là KDL

• Khai báo:

đối tượng được chứa ở bộ nhớ heap.

string s = “Nguyen Van A”;

Kiểu mảng (Array)

• Mảng là một tập hợp các phần tử cùng một kiểu dữ liệu liên

• Chỉ số bắt đầu từ 0.

tiếp nhau và được truy xuất thông qua chỉ số.

Mảng 1 chiều

• Mảng một chiều

• VD: Khai báo mảng số nguyên arr gồm 5 phần tử

[]=new [Số phần tử];

int [] arr = new int [5];

Mảng 2 chiều

• Mảng hai chiều

• VD: Khai báo ma trận số nguyên mt gồm 5 dòng và 3 cột

[,]=new [Số dòng, số cột];

long [ ,] mt = new long [5, 3];

Kiểu có cấu trúc

• Struct dùng để nhóm các dữ liệu cùng liên quan đến một đối

• Khai báo :

tượng nào đó

struct

{

Danh sách các thuộc tính;

}

• Truy xuất: .thuộc tính

Kiểu có cấu trúc

struct SV { public string ten; public string maso; }

Console.WriteLine("Ten: "+a.ten+" Ma so: "+a.maso);

static void Main(string[] args) { SV a; a.ten = "Le Van Teo"; a.maso = "002"; Console.ReadLine();

}

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

• Rẽ nhánh : if…else

• Lựa chọn : switch…case

• Lặp : for, while, do…while, foreach

Cấu trúc rẽ nhánh

Ñuùng

Bieåu thöùc ñieàu kieän

́ if (biêu th c điê u kiên) {

̉ ̣

;

}

̉ ̣

́ ư Nê u biêu th c điê u kiên cho kê t qua kha c không ự (true) thi th c hiên khô i lênh.

Cấu trúc rẽ nhánh (tt)

if (biểu thức điều kiện) {

;

Sai

Ñuùng

Bieåu thöùc ñieàu kieän

} else {

;

}

Nếu biểu thức điều kiện cho kết quả khác không thì thực hiện khối lệnh 1, ngược lại thì cho thực hiện khối lệnh thứ 2.

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

switch (biểu thức)

case n1:

KQ phải là nguyên

các câu lệnh ;

break ;

case n2:

các câu lệnh ;

break ;

………

case nk:

;

break ;

[default: các câu lệnh]

break;

(cid:0)

Cấu trúc lặp

• while

• for

• do…while

• foreach

Cấu trúc lặp while và for

Khởi gán

Sai

Đúng

Biểu thức điều kiện

Lệnh

Cập nhật chỉ số lặp

Hoạt động cấu trúc lặp while và for

• Bước 1: Thực hiện khởi gán

• Bước 2: Kiểm tra biểu thức điều kiện

- Nếu kết quả là true thì cho thực hiện các lệnh của vòng lặp,

- Ngược lại kết thúc vòng lặp.

thực hiện biểu thức tăng/ giảm. Quay trở lại bước 2.

Cấu trúc lặp while

< Khởi gán>;

while ()

(cid:0)

lệnh/ khối lệnh;

;

(cid:0)

Cấu trúc lặp for

ứ

ể

ở

for (;;)

{

;

}

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

ở Kh i gán

{

ố ệ

L nh ệ / Kh i l nh

< khối lệnh> ;

} while (biểu thức ĐK);

ậ

ặ ậ C p nh t vòng l p

Thực hiện khối

lệnh

Yes

ề

ệ ặ Đi u ki n l p

cho đến khi biểu thức

điều kiện là false

Cấu trúc lặp foreach

• Sử dụng cho mảng

foreach ( in )

{

Khối lệnh;

}

Xét từng phần tử trong mảng

KDL trừu tượng

• Lớp CTDL ngoài khả năng chứa dữ liệu, nó còn có các hành vi

đặc trưng riêng (các thao tác cho phép cập nhập, truy xuất các

à KDL trừu tượng (abstract data type):

giá trị dữ liệu cho từng đối tượng)

- Chưa có dữ liệu bên trong, chưa dùng được

- Chỉ dùng để thiết kế ý niệm

Cấu trúc dữ liệu

• Tổ chức & lưu trữ dữ liệu hợp lý để sử dụng một cách hiệu quả

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

• Ví dụ:

• Mảng (Array)

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

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

• Cây (Tree)

Hiện thực KDL trừu tượng

• Class: hiện thực của abstract data type

• Định nghĩa các dữ liệu

• Định nghĩa các phương thức + hàm phụ trợ (nội bộ)

• Định nghĩa các constructor và destructor

• Đối tượng = một thể hiện (instance) của một class

• Thông điệp (message): dùng tương tác lẫn nhau (gọi phương

thức của các đối tượng)

Định nghĩa lớp (class) C#

ừ

khóa truy xu t>

ấ class ớ

{

ừ

ấ

ộ

khóa truy xu t> các thu c tính;

ừ

ấ

ươ

khóa truy xu t> ph

ứ ng th c ()

{

ị

ươ

Đ nh nghĩa ph

ứ ng th c

}

Từ khóa truy xuất

ộ ớ

ặ

ấ

ộ

ị

§ private (m c đ nh): Truy xu t trong n i b l p

ườ

ử ụ

ộ

(th

ng s d ng cho thu c tính)

ộ ộ ớ

ấ

ớ

ượ

§ protected: Truy xu t trong n i b l p/ l p con (đ

ớ ơ ở ử ụ s d ng cho l p c s )

ấ

ọ

ườ

ử ụ

§ public: Truy xu t m i n i (th

ng s d ng cho

ươ

ứ

ng th c)

ở ạ

ố ượ

ấ

ầ

ủ

static: truy xu t không c n kh i t o đ i t

ng c a

l pớ

VD: Định nghĩa lớp CHocSinh gồm dữ liệu họ tên, điểm văn và điểm toán. Các thao tác nhập, tính điểm trung bình và in kết quả

public class CHocSinh {

private string hoten; private int toan, van; private float dtb; public void Nhap() { Console.Write("Nhap ho ten: "); hoten = Console.ReadLine();

Console.Write("Nhap diem van: "); van = int.Parse(Console.ReadLine());

Console.Write("Nhap diem toan: "); toan =

int.Parse(Console.ReadLine());

dtb = (float)(toan + van) / 2; } public void Xuat()

{

Console.WriteLine("Diem trung binh: {0:0.00}", dtb);

}

Tạo và sử dụng đối tượng

ố ượ

ạ

§ T o đ i t

ố ượ

ớ

TênĐ iT

ng =

new ();

VD: CHocSinh hsA = new CHocSinh();

ử ụ

ố ượ

§ S d ng đ i t

ố ượ

ươ

ứ

ố

TênĐ iT

ng.TênPh

ngTh c([tham s ]);

VD: hsA.Nhap();

hsA.Xuat();

Bài tập

Xây dựng lớp CMyArray dùng để biểu diễn cấu trúc mảng một

chiều số nguyên và các thao tác cần thiết.

Các phương pháp mô tả giải thuật

• Lưu đồ

• Mã giả

• Mã tự nhiên

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ý

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 …

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

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;

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

DISPLAY a

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

Các nguyên tắc xây dựng lớp CTDL

Định nghĩa CTDL và đặc tả các thao tác một cách rõ ràng

(KDL trả về, thông số vào/ ra, tiền kiện, hậu kiện, có sử dụng

hàm và lớp khác)

Dữ liệu chỉ nên được truy xuất thông qua phương thức khác,

àDữ liệu: private/ protected

dữ liệu lưu phải được kiểm tra hợp lệ

Nên được khởi tạo ban đầu là đối tượng rỗng

Kỹ thuật lập trình

Vấn đề cung cấp cơ chế xử lý lỗi khi sử dụng lớp trong

chương trình: dừng/ tiếp tục

Tính nhất quá trong các giá trị trả về của phương thức

Truyền nhận dữ liệu giữa các đối tượng

Vấn đề KDL: dùng template (C++) hay Genetic

Thao tác cho phép giao tiếp với bên ngoài dùng public,

những thao tác còn lại là private/ protected

Đá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

Q&A

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)

Chủ đề:

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

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

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

Mục tiêu

Vai trò của CTDL & GT

Giải thuật

Cấu trúc dữ liệu

Phương thức

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

struct

{

Danh sách các thuộc tính;

}

if (biểu thức điều kiện) {

;

} else {

;

}

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

?

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi