›
›

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

pdf 41 trang Đức Chiến 04/01/2024 1970
Download
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à giải thuật - Chương 2: Các kiểu dữ liệu và giải thuật tìm kiếm", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_2_cac_kieu_du_lieu_va.pdf

Nội dung text: 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

  1. 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 Trường Cao đẳng Kinh tế Đối ngoại
  2. Nội dung 1 • Đị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 GV Thiều Quang Trung 2
  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 3
  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 4
  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 5
  6. Các kiểu dữ liệu cơ bản • 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 GV Thiều Quang Trung 6
  7. Các kiểu dữ liệu cơ bản • 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 GV Thiều Quang Trung 7
  8. Các kiểu dữ liệu cơ bản trong C 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 double 8 byte 10 số chính xác chính xác hơn float long double 10 byte 10 số chính xác GV Thiều Quang Trung 8
  9. 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 GV Thiều Quang Trung 9
  10. Các kiểu dữ liệu có cấu trúc • 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 GV Thiều Quang Trung 10
  11. Các kiểu dữ liệu có cấu trúc • Để 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 ; GV Thiều Quang Trung 11
  12. Các kiểu dữ liệu có cấu trúc • 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 ; GV Thiều Quang Trung 12
  13. Các kiểu dữ liệu có cấu trúc • 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. GV Thiều Quang Trung 13
  14. Kiểu chuỗi ký tự • 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 GV Thiều Quang Trung 14
  15. Kiểu chuỗi ký tự • 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”; GV Thiều Quang Trung 15
  16. Kiểu chuỗi ký tự • 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 GV Thiều Quang Trung 16
  17. Kiểu mảng • 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 : [ ]; GV Thiều Quang Trung 17
  18. Kiểu mảng • 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 ; GV Thiều Quang Trung 18
  19. Kiểu mảng • 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; GV Thiều Quang Trung 19
  20. Kiểu mẫu tin/bản ghi • 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 ; ;  [ ] ; GV Thiều Quang Trung 2020
  21. Kiểu mẫu tin/bản ghi • 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 ; GV Thiều Quang Trung 21
  22. Nhu cầu tìm kiếm dữ liệu GV Thiều Quang Trung 22
  23. 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 GV Thiều Quang Trung 23
  24. 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 GV Thiều Quang Trung 24
  25. 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) GV Thiều Quang Trung 25
  26. Tìm kiếm tuyến tính ▪ Ý 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. GV Thiều Quang Trung 26
  27. 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. GV Thiều Quang Trung 27
  28. 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 : GV Thiều Quang Trung 28
  29. Tìm kiếm tuyến tính i =0 : X = 8 12 2 8 5 1 6 4 15 i =1 : X = 8 12 2 8 5 1 6 4 15 X = 8 i =2 : 12 2 8 5 1 6 4 15 Tìm thấy tại i = 2. Dừng. GV Thiều Quang Trung 29
  30. Tìm kiếm tuyến tính 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 } GV Thiều Quang Trung 30
  31. Tìm kiếm tuyến tính 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; } GV Thiều Quang Trung 31
  32. 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ử GV Thiều Quang Trung 32
  33. Tìm kiếm nhị phân Ý 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. GV Thiều Quang Trung 33
  34. 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. GV Thiều Quang Trung 34
  35. Tìm kiếm nhị phân 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. GV Thiều Quang Trung 35
  36. 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 : 1 2 4 5 6 8 12 15 left = 1, right = 8, mid = 4 : X = 8 1 2 4 5 6 8 12 15 X = 8 left = 5, right = 8, mid = 6 : 1 2 4 5 6 8 12 15 Dừng. GV Thiều Quang Trung 36
  37. 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 } GV Thiều Quang Trung 37
  38. 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 2k k 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. GV Thiều Quang Trung 38
  39. 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 GV Thiều Quang Trung 39
  40. 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 GV Thiều Quang Trung 40
  41. GV: Thiều Quang Trung 41