Mô tả:
cấu trúc cơ sở dữ liệu
1
BÀI GIẢNG
MÔN: CẤU TRÚC DỮ LIỆU
2
Chƣơng 1:
TỔNG QUAN VỀ CẤU TRÚC
DỮ LIỆU VÀ GIẢI THUẬT
3
NỘI DUNG CHƢƠNG 1
1.1. Tầm quan trọng 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. Các kiểu dữ liệu
• Khái niệm kiểu dữ liệu
• Các kiểu dữ liệu cơ sở
• Các kiểu dữ liệu có cấu trúc
• Kiểu dữ liệu con trỏ
• Kiểu tập tin
4
1.1. Tầm quan trọng của CTDL & giải thuật
Thực hiện một đề án tin học là chuyển bài toán thực tế thành
bài toán có thể giải quyết trên máy tính.
•
Một bài toán thực tế bất kỳ đều bao gồm dữ liệu và các yêu
cầu xử lý trên dữ liệu đó để xây dựng một mô hình tin học phản
ánh đƣợc bài toán thực tế cần chú trọng đến hai vấn đề:
•
Tổ chức biểu diễn các đối tượng thực tế: Mô hình tin học
của bài toán, cần phải tổ chức sao cho
•
• vừa phản ánh chính xác dữ liệu thực tế,
• vừa dễ dàng dùng máy tính để xử lý.
xây dựng cấu trúc dữ liệu.
Xây dựng các thao tác xử lý dữ liệu : Từ những yêu cầu
thực tế, cần tìm ra các giải thuật tƣơng ứng để xác định trình tự
các thao tác máy tính phải thi hành để cho ra kết quả mong muốn
đây là bƣớc xây dựng giải thuật cho bài toán.
•
5
1.1. Tầm quan trọng của CTDL & giải thuật
* Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu + Giải thuật = Chương
trình
• Khi có cấu trúc dữ liệu tốt và giải thuật phù hợp thì xây
dựng chƣơng trình chỉ phụ thuộc thời gian.
• Một chƣơng trình máy tính chỉ hoàn thiện khi có đầy đủ
cấu trúc dữ liệu và giải thuật.
6
1.2. Các tiêu chuẩn đánh giá CTDL
Một cấu trúc dữ liệu tốt phải thỏa mãn:
• Phản ánh đúng thực tế: Cần xem xét kỹ lƣỡng cũng nhƣ
dự trù các trạng thái biến đổi của dữ liệu trong chu trình
sống để có thể chọn CTDL lƣu trữ thể hiện chính xác đối
tƣợng thực tế.
• Phù hợp với các thao tác trên đó: Tăng tính hiệu quả
của đề án, việc phát triển các thuật toán đơn giản, tự
nhiên hơn => chƣơng trình đạt hiệu quả cao hơn về tốc
độ xử lý.
• Tiết kiệm tài nguyên hệ thống: CTDL chỉ nên sử dụng
tài nguyên hệ thống vừa đủ để đảm nhiệm đƣợc chức
năng của nó. Loại tài nguyên cần quan tâm là : CPU và
bộ nhớ.
7
1.2. Các tiêu chuẩn đánh giá CTDL
Đánh giá độ phức tạp của thuật toán
• Là công việc ƣớc lƣợng thời gian thực hiện của thuật
toán để so sánh tƣơng đối các thuật toán với nhau
• Trong thực tế, thời gian thực hiện còn phụ thuộc cấu hình
máy, dữ liệu đƣa vào, …
• Để ƣớc lƣợng thời gian thực hiện thuật toán xem xét 2
trƣờng hợp
• Trƣờng hợp tốt nhất: Tmin
• Trƣờng hợp xấu nhất: Tmax
• Với Tmin và Tmax thời gian thực hiện trung bình của
thuật toán Tavg
8
1.3. Các kiểu dữ liệu
• Máy tính chỉ có thể lƣu trữ dữ liệu ở dạng nhị phân.
• Nếu muốn phản ánh đƣợc dữ liệu đa dạng, thì cần phải
xây dựng những phép ánh xạ, những qui tắc tổ chức
phức tạp che lên tầng dữ liệu nhị phân thô sơ.
• Nhằm đƣa ra những khái niệm logic về hình thức lƣu trữ
khác nhau đựoc gọi là kiêu dữ liệu.
• Các kiểu dữ liệu cơ sở
• Các kiểu dữ liệu có cấu trúc
• Kiểu dữ liệu con trỏ
• Kiểu tập tin
9
1.3. Các kiểu dữ liệu
Định nghĩa kiểu dữ liệu
Kiểu dữ liệu T đƣợc xác định bởi một bộ , với:
• V: tập các giá trị hợp lệ mà một đối tƣợng kiểu T có thể
lƣu trữ.
• O: Tập các thao tác xử lý có thể thi hành trên đối tƣợng
kiểu T.
Ví dụ : Giả sử có kiểu dữ liệu mẫu tự= với :
Vc={a-z,A-Z}
Oc={Lấy mã ASCII của ký tự, đổi ký tự thành ký tự
hoa}
• Dữ liệu lƣu trữ chiếm số bytes trong bộ nhớ gọi là kích
thƣớc của kiểu dữ liệu
10
1.3. Các kiểu dữ liệu
Các thuộc tính của một kiểu dữ liệu
• Tên kiểu dữ liệu
• Miền giá trị của dữ liệu
• Kích thƣớc dữ liệu
• Tập các toán tử tác động lên kiểu dữ liệu
11
1.3 Các kiểu dữ liệu
Các kiểu dữ liệu cơ sở
• Kiểu số nguyên
• Kiểu số thực
• Kiểu ký tự
• Kiểu luận lý
12
1.3. Các kiểu dữ liệu
Các kiểu dữ liệu có cấu trúc
Kiểu chuỗi ký tự: là kiểu dữ liệu có cấu trúc đơn giản nhất
và thƣờng các ngôn ngữ lập trình đều dịnh nghĩa nó nhƣ
một kiểu cơ bản.
Trong C các hàm xử lý chuỗi đƣợc đặt trong thƣ viện
string.lib.
VD: char S[10] ;// chuỗi ký tự S có chiều dài tối đa là 10
(kể cả ký tự kết thúc)
char S[] = ”ABCDEF” ;
char *S = “ABCDEF”;
13
1.3. Các kiểu dữ liệu
Các kiểu dữ liệu có cấu trúc (tt)
Kiểu mảng: là kiểu dữ liệu trong đó mỗi phần tử của nó là
một tập hợp có thứ tự các giá trị có cùng cấu trúc đƣợc
lƣu trữ liên tiếp nhau trong bộ nhớ.
Mảng một chiều :
[];
Mảng nhiều chiều :
[] []….;
14
1.3. Các kiểu dữ liệu
Các kiểu dữ liệu có cấu trúc (tt)
Kiểu mẫu tin: Kiểu mẫu tin cũng tƣơng tự nhƣ mảng nhƣng mỗi
phần tử của nó là tập hợp các giá trị có thể khác cấu trúc.
Kiểu mẫu tin thƣờng đƣợc dùng để mô tả những đối tƣợng có
cấu trúc phức tạp.
Ví dụ : struct PERSON
{
char Hoten[];
int NamSinh;
char NoiSinh[];
char GioiTinh; // 0:Nữ, 1: Nam
char DiaChi[];
}
15
1.3. Các kiểu dữ liệu
Kiểu dữ liệu con trỏ
Cho trƣớc kiểu T = . Kiểu con trỏ ký hiệu Tp chỉ đến các
phần tử có kiểu T đƣợc định nghĩa nhƣ sau:
Tp = Trong đó:
Tp = {{các địa chỉ có thể lƣu trữ những đối tƣợng kiểu T}, NULL}
Op = {các thao tác định địa chỉ của một đối tƣợng kiểu T khi biết
con trỏ chỉ đến đối tƣợng đó}
Kiểu con trỏ là kiểu dữ liệu cơ sở dùng lƣu địa chỉ của một đối
tƣợng dữ liệu khác.
Biến thuộc kiểu con trỏ Tp là biến mà giá trị của nó là địa chỉ của
một vùng nhớ ứng với một biến kiểu T, hoặc là giá trị NULL
16
1.3. Các kiểu dữ liệu
Kiểu dữ liệu con trỏ (tt)
• Kích thƣớc biến con trỏ tùy thuộc vào quy ƣớc số byte trong
từng mô hình bộ nhớ và từng ngôn ngữ lập trình cụ thể.
• Biến con trỏ trong C++ có kích thƣớc 2 hoặc 4 bytes tùy vào con
trỏ NEAR hay FAR
• Cú pháp định nghĩa dữ liệu kiểu con trỏ
typedef * ;
Các thao tác cơ bản trên kiểu con trỏ:
• Khi một biến con trỏ „p‟ lƣu trữ địa chỉ của đối tƣợng x ta nói “p
trỏ đến x”
• Gán địa chỉ của một vùng nhớ con trỏ p:
p = <địa chỉ>;
p = <địa chỉ> +
• Truy xuất (xem) nội dung của đối tƣợng p trỏ đến (*p)
17
1.3. Các kiểu dữ liệu
Kiểu dữ liệu tập tin
• Tập tin là kiểu dữ liệu đặc biệt, kích thƣớc tối đa của tập
tin phụ thuộc không gian đĩa
• Việc đọc, ghi dữ liệu trên tập tin là mất thời gian, không
an toàn dữ liệu
• Thông thƣờng chuyển dữ liệu trong tập tin (một phần hay
toàn bộ) vào bộ nhớ trong để xử lý.
18
Bài tập
• Xem lại việc sử dụng con trỏ trong C++
• Xem lại các thao tác với tập tin
• Xem lai việc sử dụng kiểu dữ liệu mẫu tin
• Bài tập trong giáo trình chƣơng 1
Chƣơng 2:
KỸ THUẬT TÌM KIẾM
(SEARCHING)
19
20
NỘI DUNG CHƢƠNG 2
2.1. Khái quát về tìm kiếm
2.2. Các giải thuật tìm kiếm nội (Tìm kiếm trên mảng)
• Tìm tuyến tính (Linear Search)
• Tìm nhị phân (Binary Search)
2.3. Các giải thuật tìm kiếm ngoại (Tìm kiếm trên tập
tin)
• Tìm tuyến tính (F Linear Search)
• Tìm nhị phân (Binary Search)
- Xem thêm -