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
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: phuongnk@soict.hust.edu.vn
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: phuongnk@soict.hust.edu.vn
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
2
4
8
4
-128
-32768
32767
0
65535
-2147483648 = -231
2147483647 = 231-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ƢƠNG17
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ƢƠNG18
Bộ môn KHMT – ĐHBK HN
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ƢƠNG20
Bộ môn KHMT – ĐHBK HN
Tải về để xem bản đầy đủ
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_3_cac_cau_tr.pdf