Định nghĩa kiểu dữ liệu
2 • Các kiểu dữ liệu cơ bản
3 • Các kiểu dữ liệu có cấu trúc
4 • Nhu cầu tìm kiếm dữ liệu
5 • Giải thuật tìm tuyến tính
6 • Giải thuật tìm nhị phân
41 trang |
Chia sẻ: phuongt97 | Lượt xem: 437 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Cấu trúc dữ liệu - Chương II: Các kiểu dữ liệu và giải thuật tìm kiếm - Thiều Quang Trung, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CHƯƠNG 2
CÁC KIỂU DỮ LIỆU VÀ GIẢI THUẬT TÌM KIẾM
GV Th.S. Thiều Quang Trung
Bộ môn Khoa học cơ bản
Trường Cao đẳng Kinh tế Đối ngoại
• Định nghĩa kiểu dữ liệu 1
• Các kiểu dữ liệu cơ bản 2
• Các kiểu dữ liệu có cấu trúc 3
• Nhu cầu tìm kiếm dữ liệu 4
• Giải thuật tìm tuyến tính 5
• Giải thuật tìm nhị phân 6
Nội dung
2 GV Thiều Quang Trung
3
Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu T được xác định bởi một bộ
V,O, 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.
GV Thiều Quang Trung
4
Định nghĩa kiểu dữ liệu
• Ví dụ 1: kiểu dữ liệu mẫu tự = Vc,Oc với
– Vc = a-z, A-Z
– Oc= lấy mã ASCII của ký tự, biến đổi ký tự
thường thành ký tự hoa
• Ví dụ 2: kiểu dữ liệu số nguyên = Vi,Oi với
– Vi = -32768 .. 32767
– Oi = +, -, *, /, %
GV Thiều Quang Trung
5
Định nghĩa kiểu dữ liệu
• Các thuộc tính của một kiểu dữ liệu bao
gồm:
– Tên kiểu dữ liệu
– Miền giá trị
– Kích thước lưu trữ
– Tập các toán tử tác động lên kiểu dữ liệu
• Có hai loại kiểu dữ liệu:
– Kiểu dữ liệu cơ bản
– Kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
6
• Các kiểu dữ liệu cơ bản là các loại dữ liệu đơn
giản không có cấu trúc
• Là các giá trị vô hướng như các số nguyên, số
thực, các ký tự, các giá trị logic
• Được các ngôn ngữ lập trình cấp cao xây
dựng sẵn như một thành phần của ngôn ngữ
để giảm nhẹ công việc cho người lập trình. Vì
vậy còn gọi là các kiểu dữ liệu định sẵn
Các kiểu dữ liệu cơ bản
GV Thiều Quang Trung
7
• Các kiểu dữ liệu cơ bản bao gồm:
– Kiểu có thứ tự rời rạc: số nguyên, ký tự, logic,
liệt kê, miền con
– Kiểu không rời rạc: số thực.
• Tùy ngôn ngữ lập trình các kiểu dữ liệu cơ
bản có thể khác nhau
• Kiểu dữ liệu cơ bản trong ngôn ngữ C gồm: số
nguyên, số thực, ký tự, logic
Các kiểu dữ liệu cơ bản
GV Thiều Quang Trung
8
Tên kiểu K thước Miền giá trị Ghi chú
char 1 byte -128 đến 127 Có thể dùng như số
nguyên 1 byte có dấu
hoặc kiểu ký tự
unsign char 1 byte 0 đến 255 Số nguyên 1 byte
không dấu
int 2 byte -32738 đến 32767
unsign int 2 byte 0 đến 65335 Có thể gọi tắt là
unsign
long 4 byte - 2.147.483.648 đến
2.147.483.647
unsign long 4 byte 0 đến 4.2 tỷ
float 4 byte 6 số chính xác Sử dụng số double
chính xác hơn float double 8 byte 10 số chính xác
long double 10 byte 10 số chính xác
Các kiểu dữ liệu cơ bản trong C
GV Thiều Quang Trung
Các kiểu dữ liệu cơ bản trong C
• Kiểu ký tự “char” có thể dùng theo 2 cách:
– số nguyên 1 byte, hoặc
– ký tự
• Không định nghĩa kiểu logic (boolean), thay thế
bằng:
– Giá trị số nguyên bằng 0 là FALSE
– Giá trị số nguyên khác 0 là TRUE
9 GV Thiều Quang Trung
10
• Kiểu dữ liệu có cấu trúc là kiểu dữ liệu được xây dựng
dựa trên các thành phần của kiểu dữ liệu cơ bản
• Một số kiểu có cấu trúc cơ bản như mảng, chuỗi,
• Ví dụ: Để mô tả một đối tượng sinh viên thì cần định
nghĩa các thông tin sau :
– Mã sinh viên : chuỗi ký tự
– Tên sinh viên : chuỗi ký tự
– Ngày sinh : kiểu ngày tháng
– Nơi sinh : chuỗi ký tự
– Điểm thi : số nguyên
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
11
• Để thể hiện thông tin về ngày tháng năm sinh cần
phải xây dựng một kiểu bản ghi :
typedef struct tagDate
char ngay ;
char thang ;
char nam ;
Date ;
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
12
• Kiểu dữ liệu thể hiện thông tin một sinh viên được
xây dựng như sau:
typedef struct tagSinhVien
char masv[15] ;
char tensv[15] ;
char noisinh[15] ;
Date namsinh;
int Diemthi ;
SinhVien ;
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
13
• Giả sử đã có cấu trúc phù hợp để lưu trữ
một sinh viên, nhưng thực tế lại cần quản lý
nhiều sinh viên, lúc đó nảy sinh nhu cầu xây
dựng kiểu dữ liệu mới
• Mục tiêu của việc nghiên cứu cấu trúc dữ
liệu chính là tìm những phương cách thích
hợp để tổ chức, liên kết dữ liệu, hình thành
các kiểu dữ liệu có cấu trúc từ những kiểu dữ
liệu đã được định nghĩa.
Các kiểu dữ liệu có cấu trúc
GV Thiều Quang Trung
14
• Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc
đơn giản nhất, được các ngôn ngữ lập trình định nghĩa
như một kiểu cơ bản
• Được cấu trúc như một chuỗi liên tiếp các ký tự kết
thúc bằng ký tự có mã ASCII bằng 0 (NULL character)
• Giới hạn chiều dài của một chuỗi ký tự trong C tối đa
65335 ký tự, ký tự đầu được đánh số là ký tự thứ 0
Kiểu chuỗi ký tự
GV Thiều Quang Trung
15
• Ta có thể khai báo một chuỗi ký tự theo một số cách
sau đây :
– Khai báo một chuỗi ký tự S có chiều dài tối đa 10
ký tự
char S10 ;
– Khai báo một chuỗi ký tự S có chiều dài bằng
chiều dài của chuỗi “ABC” và giá trị khởi đầu của S
là “ABC”
char S = “ABC”;
– Cách khai báo khác
char *S = “ABC”;
Kiểu chuỗi ký tự
GV Thiều Quang Trung
16
• Các thao tác trên chuỗi ký tự rất đa dạng và phong
phú được cài đặt trong thư viện string.lib của C
• Một số thao tác thông dụng :
– strcmp : So sánh 2 chuỗi
– strcpy : Sao chép 2 chuỗi
– strstr : Kiểm tra một chuỗi có nằm trong chuỗi kia
– strtok : Cắt 1 từ ra khỏi 1 chuỗi
– itoa : Đổi 1 số ra chuỗi
– atoi,atof, : Đổi 1 chuỗi ra số
– sprintf : Đổi 1 hay 1 số giá trị ra chuỗi
– gets : Nhập 1 chuỗi
– puts : Xuất 1 chuỗi
Kiểu chuỗi ký tự
GV Thiều Quang Trung
17
• 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ớ.
• Có hai dạng: mảng một chiều và mảng nhiều chiều.
• Một dãy số chính là hình tượng của mảng một chiều,
ma trận là hình tượng của mảng 2 chiều.
• Mảng 2 chiều có thể coi là là mảng một chiều trong đó
mỗi phần tử của nó là 1 mảng một chiều.
• Mảng 1 chiều được khai báo như sau :
[];
Kiểu mảng
GV Thiều Quang Trung
18
• Ví dụ mảng một chiều:
– Khai báo một mảng số nguyên có tối đa 100 phần
tử:
int a [100];
– Khai báo và gán giá trị ban đầu cho một mảng gồm
4 phần tử:
int a [4] = 1,7,-3,819 ;
– Cách khai báo khác:
int a [] = 1,7,-3,819 ;
Kiểu mảng
GV Thiều Quang Trung
19
• Mảng 2 chiều được khai báo như sau :
[][];
• Ví dụ :
– Khai báo mảng số nguyên có kích thước 3x5 :
int a [3][5];
– Khai báo và gán giá trị ban đầu cho mảng 2 chiều :
int a [][] = 1,7,-3,8,19,
4,5, 2,8,9,
21,7,45,-1,4;
Kiểu mảng
GV Thiều Quang Trung
• Mẫu tin là kiểu dữ liệu mà trong đó 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 cho phép mô tả các đối tượng có
cấu trúc phức tạp.
• Khai báo tổng quát của kiểu struct như sau :
typedef struct
;
;
[] ;
20
Kiểu mẫu tin/bản ghi
GV Thiều Quang Trung 20
• Ví dụ: khai báo kiểu dữ liệu mô tả các thông tin về
một con người
typedef struct tagNguoi
char HoTen [35];
int NamSinh;
char NoiSinh[40];
char GioiTinh; // 0 : Nữ, 1 : Nam
char DiaChi [50];
char Ttgd; // 0 : Ko có gia đình, 1 : Có gia đình
Nguoi ;
21
Kiểu mẫu tin/bản ghi
GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
22 GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
• Trong các hệ lưu trữ, quản lý dữ liệu, thao tác
tìm kiếm thường được thực hiện nhiều nhất
• Ví dụ: tra cứu từ điển, tìm sách trong thư
viện,
• Do hệ thống thông tin lưu trữ khối lượng dữ
liệu lớn => xây dựng phép toán tìm kiếm
nhanh có ý nghĩa rất quan trọng
23 GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
• Nếu dữ liệu trong hệ thống đã được sắp xếp
=> việc tìm kiếm sẽ thực hiện nhanh hơn
• Ví dụ: các từ trong từ điển đã được sắp xếp
theo vần,
• Xây dựng một hệ quản lý thông tin: cần quan
tâm giải thuật tìm kiếm và cả giải thuật sắp
xếp dữ liệu
• Mức độ hiệu quả của từng giải thuật phụ
thuộc vào tính chất của cấu trúc dữ liệu
24 GV Thiều Quang Trung
Nhu cầu tìm kiếm dữ liệu
• Để đánh giá thời gian thực hiện dựa vào 2 đại
lượng đặc trưng:
– Số lần so sánh
– Số phép gán
• Hai giải thuật tìm kiếm dữ liệu:
– Tìm Tuyến tính/Tuần tự (Linear/Sequential
Search)
– Tìm Nhị phân (Binary Search)
25 GV Thiều Quang Trung
Ý tưởng :
Thuật toán tiến hành so sánh khóa cần tìm
là X với lần lượt các phần tử thứ nhất, thứ
hai, của mảng A cho đến khi gặp được
phần tử chứa khóa, hoặc đã tìm hết mảng
mà không thấy X.
Tìm kiếm tuyến tính
26 GV Thiều Quang Trung
Tìm kiếm tuyến tính
Giải thuật vét cạn (Exhaustive):
Bước 1 : i = 0; //bắt đầu phần tử đầu tiên của dãy
Bước 2 : So sánh a[i] với X, có 2 khả năng :
a[i] = X : Tìm thấy => Dừng
a[i] X : Sang bước 3.
Bước 3 : i = i+1 ; //xét tiếp phần tử kế trong mảng
Nếu i >= N : Hết mảng, không tìm thấy => Dừng
Ngược lại : Lặp lại Bước 2.
27 GV Thiều Quang Trung
Tìm kiếm tuyến tính
Ví dụ :
Cho dãy số a :
12 2 8 5 1 6 4 15
Nếu giá trị cần tìm là 8, giải thuật được tiến
hành như sau :
28 GV Thiều Quang Trung
Tìm kiếm tuyến tính
12 2 8 5 1 6 4 15
X = 8 i =0 :
12 2 8 5 1 6 4 15
12 2 8 5 1 6 4 15
X = 8 i =1 :
i =2 :
X = 8
Tìm thấy tại i = 2. Dừng.
29 GV Thiều Quang Trung
Cài đặt giải thuật, cách 1:
int LinearSearch(int a[], int n, int x)
{
int i=0;
while(i<n && a[i]!=x) i++;
if (i<n) return i; //a[i] là phần tử có khoá x
return -1; //tìm hết mảng nhưng không có x
}
Tìm kiếm tuyến tính
30 GV Thiều Quang Trung
Cài đặt giải thuật, cách 2:
int LinearSearch (int a[], int n, int x)
{
for(int i=0;i<n;i++)
if (a[i]==x)
return i; //a[i] là phần tử có khóa x
return -1;
}
Tìm kiếm tuyến tính
31 GV Thiều Quang Trung
Tìm kiếm tuyến tính
Nhận xét:
• Trường hợp khóa X nằm ở 2 biên của mảng A
=> rất hiếm khi xuất hiện.
• Số phép so sánh trung bình = 2(1+2+ + n)/n
= n+1
=> Số phép so sánh tăng/giảm tuyến tính
theo số phần tử
32 GV Thiều Quang Trung
Ý tưởng:
• Đối với những dãy số đã có thứ tự thì các
phần tử trong dãy có quan hệ:
ai-1 ai ai+1
– Nếu X > ai thì X chỉ có thể xuất hiện trong đoạn
[ai+1, aN]
– Ngược lại, X chỉ có thể xuất hiện trong đoạn
[a1, ai-1] của dãy.
Tìm kiếm nhị phân
33 GV Thiều Quang Trung
Tìm kiếm nhị phân
• Ý tưởng của giải thuật tìm nhị phân là tìm
các giới hạn phạm vi của dãy sau mỗi lần so
sánh X với một phần tử trong dãy:
– Tại mỗi bước tiến hành so sánh X với phần tử
nằm ở vị trí giữa của dãy;
– Dựa vào kết quả so sánh này để quyết định giới
hạn dãy tìm kiếm ở bước kế tiếp là nửa trên
hay nửa dưới của dãy.
34 GV Thiều Quang Trung
Thuật toán:
B1: left = 0; right = n-1;
B2: while (left right)
B2.1: mid = (left+right)/2;
B2.2: if ( a[mid] = x) Dừng, vị trí xuất hiện: mid
B2.3: if (a[mid] > x) right = mid - 1;
else left = mid + 1;
B3: Dừng, không tìm thấy.
35 GV Thiều Quang Trung
Tìm kiếm nhị phân
Ví dụ: Cho dãy số a gồm 8 phần tử, nếu giá trị cần tìm là 8, giải
thuật được tiến hành như sau :
Tìm kiếm nhị phân
left = 1, right = 8, mid = 4 :
1 2 4 5 6 8 12 15
left = 5, right = 8, mid = 6 :
1 2 4 5 6 8 12 15
Dừng.
X = 8
X = 8
1 2 4 5 6 8 12 15
36 GV Thiều Quang Trung
Tìm kiếm nhị phân
Cài đặt:
int BinarySearch(int a[],int n,int x )
{
int left = 0, right = n-1, mid;
while (left <= right)
{
mid = (left + right)/2;
if (x == a[mid]) return mid;
if (x<a[mid]) right = mid -1;
else left = mid +1;
}
return -1; // trong dãy không có x
}
37 GV Thiều Quang Trung
Tìm kiếm nhị phân
Nhận xét :
• Mỗi lần lặp thì chiều dài của mảng con giảm
khoảng ½ so với mảng trước đó.
• n = 2k + m, với 0 <= m < 2
• => 2k < n < 2k+1
• => k <= log2 n < k+1
• => k = log2n
• Số lần thực hiện vòng while là khoảng k lần,
mỗi vòng lặp thực hiện 1 phép so sánh.
38 GV Thiều Quang Trung
Tìm kiếm nhị phân
Nhận xét:
• Trường hợp tốt nhất:
– k = 1 X là phần tử chính giữa của mảng.
• Trường hợp xấu nhất:
– k= log2n + 1 X không thuộc mảng hoặc X
là phần tử cuối cùng của mảng
– Số phép so sánh tăng theo hàm logarit
39 GV Thiều Quang Trung
Tìm kiếm nhị phân
So sánh trường hợp xấu nhất của 2 thuật toán
40 GV Thiều Quang Trung
GV: Thiều Quang Trung 41
Các file đính kèm theo tài liệu này:
- bai_giang_cau_truc_du_lieu_chuong_ii_cac_kieu_du_lieu_va_gia.pdf