Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Các kiểu dữ liệu và giải thuật tìm kiếm - Thiều Quang Trung

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 S10 ; – 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