Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 3: Các cấu trúc dữ liệu cơ bản

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Cấu trúc dữ liệu và thuật toán

Nguyễn Khánh Phƣơng

Computer Science department

School of Information and Communication technology

E-mail: [email protected]n

Nội dung khóa học

Chương 1. Các khái niệm cơ bản

Chương 2. Các sơ đồ thuật toán

Chương 3. Các cấu trúc dữ liệu cơ bản

Chương 4. Cây

Chương 5. Sắp xếp

Chương 6. Tìm kiếm

Chương 7. Đồ thị

2

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Chương 3. Các cấu trúc dữ liệu cơ bản

Nguyễn Khánh Phƣơng

Computer Science department

School of Information and Communication technology

E-mail: [email protected]n

Kiểu dữ liệu (Data types)

• Kiểu dữ liệu (data type) được đặc trưng bởi:

– Tập các giá trị (a set of values);

– Cách biểu diễn dữ liệu (data representation) được sử dụng chung

cho tất cả các giá trị này và

– Tập các phép toán (set of operations) có thể thực hiện trên tất cả

các giá trị.

• Chú ý:

– Mỗi giá trị có một cách biểu diễn nào đó mà người sử dụng

không nhất thiết phải biết

– Mỗi phép toán được cài đặt theo một cách nào đó mà người sử

dụng cũng không cần phải biết

4

Các kiểu dữ liệu dựng sẵn

(Built-in data types)

• Trong các ngôn ngữ lập trình thường có một số kiểu dữ liệu

nguyên thuỷ đã được xây dựng sẵn. Ví dụ:

– Kiểu số nguyên (Integer numeric types)

• byte, char, short, int, long

– Kiểu số thực dấu phảy động (floating point numeric types)

• float, double

– Các kiểu nguyên thuỷ khác (Other primitive types)

• boolean

– Kiểu mảng (Array type)

• mảng các phần tử cùng kiểu

Dữ liệu đối với kiểu nguyên thuỷ

Trong ngôn ngữ lập trình C

Type Byte Minimum value

Maximum value

127

byte

short

char

int

1

2

4

8

4

-128

-32768

32767

0

65535

-2147483648 = -2³¹

2147483647 = 2³¹-1

long

float

-9223372036854775808 9223372036854775807

45

38

1 .40

10

3 .40

10

308

324

1 .80

10

4 .94

10

double 8

Có thể có kiểu boolean với hai giá trị true hoặc false

6

Phép toán đối với kiểu dữ liệu nguyên thuỷ

• Đối với kiểu: byte, char, short, int, long

 +, - , *, /, %, đổi thành xâu, ...

• Đối với kiểu: float, double

 +, -, *, /, round, ceil, floor, ...

• Đối với kiểu: boolean

 kiểm giá trị true, hay kiểm giá trị false

• Nhận thấy rằng: Các ngôn ngữ lập trình khác nhau có thể sử dụng mô tả

kiểu dữ liệu khác nhau. Chẳng hạn, PASCAL và C có những mô tả các

dữ liệu số khác nhau.

Nội dung

1. Mảng (Array)

2. Bản ghi (Record)

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

4. Ngăn xếp (Stack)

5. Hàng đợi (Queue)

8

Nội dung

1. Mảng (Array)

2. Bản ghi (Record)

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

4. Ngăn xếp (Stack)

5. Hàng đợi (Queue)

9

1. Mảng (Array)

• Giả sử có 100 tỉ số (scores) trong một giải đấu bóng chuyền. Chúng ta cần tiến hành

các thao tác: lấy thông tin của 100 tỉ số đó (read them), rồi đem xử lý các tỉ số này

(process them), và cuối cùng là in chúng (print/write them).

• Để làm được điều này, ta cần lưu trữ 100 tỉ số này vào bộ nhớ trong suốt quá trình

thực hiện chương trình. Do đó, ta sẽ sử dụng 100 biến, mỗi biến một tên tương ứng

với 1 tỉ số: (Xem hình 1)

Hình 1 Sử dụng 100 biến

Hình 2 Xử lý dữ liệu tỉ số trên 100 biến

• Sử dụng 100 biến dẫn đến vấn đề: ta cần phải viết lệnh đọc (read) 100 lần, lệnh xử

lý (process) 100 lần và lệnh in (write) 100 lần (xem Hình 2).

10

1. Mảng (Array)

• Thay vì khai báo biến một cách rời rạc 100 biến

score1, score2, …, score100, ta có thể khai báo một mảng các giá trị

như scores[1], scores[2] và … scores[100] để biểu diễn các giá trị

riêng biệt.

Hình 1 Sử dụng 100 biến

Hình 2 Sử dụng mảng scores gồm 100 phần tử

11

1. Mảng (Array)

Mảng là một kiểu dữ liệu chứa dãy các phần tử được đánh chỉ số, thông

thường các phần tử này có cùng kiểu dữ liệu.

• Mỗi phần tử của mảng có một chỉ số cố định duy nhất

– Chỉ số nhận giá trị trong khoảng từ một cận dưới đến một cận trên nào đó

Ví dụ: Trong ngôn ngữ C, mảng scores kích thước N = 9, mỗi phần tử được đánh

t i

n

0 <= i < N

t scores[i]

i

ng scores

(chỉ số)

(phần tử)

12

(tên

mảng)

Tên mảng vs. Tên phần tử của mảng

Trong 1 mảng, ta có 2 kiểu định danh:

• Tên của mảng

• Tên của các phần tử riêng biệt thuộc mảng.

Tên của mảng là tên của toàn bộ cấu trúc, còn tên của một phần tử cho phép ta truy cập

đến phần tử đó.

Ví dụ:

Tên của mảng: scores,

Tên mỗi phần tử của mảng: gồm tên của mảng theo sau là chỉ số của phần tử, ví dụ

scores[0], scores[1], …

13

1. Mảng (Array)

• Mảng (Array): tập các cặp (chỉ số (index) và giá trị (value))

– Cấu trúc dữ liệu: mỗi chỉ số, sẽ tương ứng với 1 giá trị.

– Lưu trữ trong bộ nhớ: mảng được lưu trữ ở các ô nhớ liền kề nhau

(cách lưu trữ này được gọi là lưu trữ kế tiếp). Địa chỉ thấp nhất tương

ứng với thành phần đầu tiền và địa chỉ cao nhất tương ứng với thành

phần cuối cùng của mảng.

14

Mảng trong các ngôn ngữ lập trình

• Các chỉ số có thể là số nguyên (C/C++, Java) hoặc là các giá

trị kiểu rời rạc (Pascal, Ada)

• Cận dưới là 0 (C/C++, Java), 1 (Fortran), hoặc tuỳ chọn bởi

người lập trình (Pascal, Ada)

• Trong hầu hết các ngôn ngữ, mảng là thuần nhất (nghĩa là

tất cả các phần tử của mảng có cùng một kiểu); trong một số

ngôn ngữ (như Lisp, Prolog) các thành phần có thể là không

thuần nhất (có các kiểu khác nhau)

15

Khai báo mảng 1 chiều (one-dimensional array)

Khi khai báo mảng, ta cần kiểu mảng (type), tên mảng (arrayName) và số phần tử

trong mảng (arraySize > 0) :

type arrayName [arraySize];

Ví dụ: khai báo int A[5];

tạo mảng A gồm 5 phần tử kiểu số nguyên (vì là kiểu nguyên, nên mỗi phần tử

chiếm 4 bytes trong bộ nhớ)

• Nếu kích thước mảng arraySize là hằng số thì cho ta mảng có độ dài cố định

(fixed length array), nếu là 1 biến (variable) thì cho ta mảng có độ dài thay đổi

(variable-length arrays)

Mảng A cố định gồm 10 phần tử

– Ví dụ:

double A[10];

int n;

double B[n];

Mảng B có độ dài thay đổi qua giá trị của biến n

• Chú ý: trước khi sử dụng một mảng, ta luôn phải khai báo và khởi tạo nó

16

Mảng trong ngôn ngữ C

Ngôn ngữ C hỗ trợ 2 kiểu mảng:

 Mảng có độ dài cố định (Fixed Length Arrays) : lập trình viên

“hard codes” (cố định) độ dài của mảng.

 Mảng có độ dài thay đổi (Variable-Length Arrays): lập trình viên

không biết độ dài của mảng cho đến khi chạy chương trình.

_{NGUYỄN KHÁNH PHƢƠNG}17

Bộ môn KHMT – ĐHBK HN

Ví dụ: Khai báo mảng có độ dài cố định (fixed length array)

(kiểu số nguyên: int)

(kiểu kí tự: char)

(kiểu số thực: float)

_{NGUYỄN KHÁNH PHƢƠNG}18

Bộ môn KHMT – ĐHBK HN

Khai báo mảng 1 chiều có độ dài cố định

• Ta có thể khởi tạo giá trị cho các phần tử của mảng cùng lúc với khai báo

mảng

• Nếu số giá trị dùng khởi tạo nhỏ hơn kích thước mảng, C sẽ tự động gán

cho các thành phần còn lại nhận giá trị 0

19

Truy cập phần tử của mảng

Để truy cập vào phần tử của một mảng, ta cần một giá trị

nguyên xác định chỉ số của phần tử mà ta muốn truy cập.

• Có thể dùng chỉ số là 1 hằng số: scores[0];

• Cũng có thể dùng chỉ số là 1 biến (variable):

for(i = 0; i < 9; i++)

scoresSum += scores[i];

_{NGUYỄN KHÁNH PHƢƠNG}20

Bộ môn KHMT – ĐHBK HN

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 3: Các cấu trúc dữ liệu cơ bản - Nguyễn Khánh Phương