Bài giảng Cấu trúc dữ liệu - ThS. Nguyễn Thị thúy Loan

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST

Báo xấu

125
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu trình bày các nội dung: Độ phức tạp thuật toán, tìm kiếm và sắp xếp, danh sách liên kết, Stack & Queue, cây và các nội dung cụ thể khác. Mời bạn đọc tham khảo tài liệu để hiểu thêm về các nội dung trên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu - ThS. Nguyễn Thị thúy Loan

Cách đánh giá BÀI GIẢNG  Thực hành: 30% CẤU TRÚC DỮ LIỆU  Bài tập: 20%  Lý thuyết: 50% ThS. Nguyễn Thị Thúy Loan 6/8/2010 Nguyễn Thị Thúy Loan 2 Tài liệu tham khảo NỘI DUNG CHƯƠNG TRÌNH 1. Bài giảng: ThS. Nguyễn Hà Giang 2. Cấu trúc dữ liệu & giải thuật, Dương Anh Đức, Trần  Độ phức tạp thuật toán. Hạnh Nhi, NXB ĐHQG Tp.HCM, 2008.  Tìm kiếm và sắp xếp. 3. Cấu trúc dữ liệu, Nguyễn Trung Trực, ĐHBK, 1992. 4. Giải thuật & lập trình, Lê Minh Hoàng, ĐHSPHN,  Danh sách liên kết. 1999-2002. 5. Cấu trúc dữ liệu + giải thuật = chương trình, Nguyễn  Stack & Queue. Quốc Cường – Hoàng Đức Hải, NXB Giáo dục. 6. Fundamentals of Data Structures, Ellis Horowitz,  Cây. Sartaj Sahni. 6/8/2010 Nguyễn Thị Thúy Loan 3 6/8/2010 Nguyễn Thị Thúy Loan 4
Chương I NỘI DUNG ĐỘ PHỨC TẠP THUẬT I. ĐO THỜI GIAN TOÁN II. DỰA VÀO ĐỘ LỚN CỦA DỮ LIỆU III. MỘT SỐ CÔNG THỨC THƯỜNG DÙNG IV. CÁCH TÍNH ĐỘ PHỨC TẠP ThS. Nguyễn Thị Thúy Loan 6/8/2010 Nguyễn Thị Thúy Loan 6 Đo thời gian Dựa vào độ lớn của dữ liệu Gọi t(n) là thời gian thực hiện của thuật toán A (thông thường là chu kỳ của CPU), t(n) sẽ là một trong các loại: a. O(1): độ phức tạp là một hằng số. VD: for (int i=1; i
Dựa vào độ lớn của dữ liệu Dựa vào độ lớn của dữ liệu b. O(log2n): Tìm nhị phân. Nhận xét c. O(√n): Kiểm tra một số có phải là số  Trừ số 2, tất cả các số chẵn không phải nguyên tố? là số nguyên tố. VD: Kiểm tra số nguyên tố, xét i=2 → (n/2),  Các số lẻ không có ước số chẵn. nếu i là ước số của n  n không phải là  i là ước số của n → (n/i) là ước số của n. số nguyên tố, ngược lại n là nguyên tố. 6/8/2010 Nguyễn Thị Thúy Loan 9 6/8/2010 Nguyễn Thị Thúy Loan 10 Dựa vào độ lớn của dữ liệu Một số công thức thường dùng n d. O(n): Độ phức tạp tuyến tính (áp dụng a. 1 i 1 n b b a 1 duyệt mảng, dãy).  1  1  1  b  a  1 ( a  b  N ) i a i 1 i 1 e. O(nlog2n): “thuật toán Logarit” (áp dụng n n ( n  1) sắp xếp mảng). b.  i 1 i  2 n n( n  1)  (a  1)(a  1  1) f. O(nα) (α>1): đa thức.  i  i a 2 g. O(2n), O(n!): mũ (áp dụng liệt kê tất cả n2 n 2 ( n 2  1)  i các tập con của tập gồm n phần tử). i 1 2 6/8/2010 Nguyễn Thị Thúy Loan 11 6/8/2010 Nguyễn Thị Thúy Loan 12
Một số công thức thường dùng Cách tính độ phức tạp Ví dụ 1: Cho thuật toán tính tổng như sau: n n( n  1)(2n  1) long Tong (int n) c.  i2  i 1 6 { long s = 0; for (int i = 1 ; i
Cách tính độ phức tạp Cách tính độ phức tạp Vd3: Cho thuật toán sau: Vd2: Cho thuật toán sau: long Tong (int n) long Tong (int n) { long s = 0; { long s = 0; for (int i = 1 ; i
Tìm kiếm Tìm kiếm  Tìm kiếm là quá trình xác định một đối  Tìm kiếm là thao tác quan trọng & thường tượng nào đó trong một tập các đối tượng. được sử dụng trong tin học. Kết quả trả về là đối tượng tìm được (nếu o Tìm kiếm một nhân viên trong danh sách có) hoặc một chỉ số (nếu có) xác định vị trí nhân viên. của đối tượng trong tập đó. o Tìm một sinh viên trong danh sách sinh viên  Việc tìm kiếm dựa theo một trường nào đó của một lớp… của đối tượng, trường này là khóa (key) o Tìm kiếm một tên sách trong thư viện. của việc tìm kiếm. 6/8/2010 Nguyễn Thị Thúy Loan 21 6/8/2010 Nguyễn Thị Thúy Loan 22 Tìm kiếm Tìm kiếm Tìm kiếm kiế  VD: Muốn tìm sinh viên tên Nguyễn Văn A có trong lớp hay không? Tìm kiếm tuyến tính kiế tuyế tí Tìm kiếm nhị phân kiế nhị  Ta có hai cách tìm kiếm như sau: Tập dữ liệu dữ liệ Tập dữ liệu đã dữ liệ bất kỳ kỳ được sắp xếp đượ sắ xế 6/8/2010 Nguyễn Thị Thúy Loan 23 6/8/2010 Nguyễn Thị Thúy Loan 24
Tìm kiếm Tìm kiếm tuyến tính Bài toán được mô tả như sau:  Ý tưởng chính: duyệt tuần tự từ phần tử  Tập dữ liệu được lưu trữ là dãy a0, a2,.., đầu tiên, lần lượt so sánh khóa tìm kiếm an-1. Giả sử chọn cấu trúc dữ liệu mảng để với khoá tương ứng của các phần tử lưu trữ dãy số này trong bộ nhớ chính, có trong danh sách. Cho đến khi gặp phần khai báo: int a[MAX]; tử cần tìm hoặc đến khi duyệt hết danh  Khóa cần tìm là x, có kiểu nguyên: int x; sách. 6/8/2010 Nguyễn Thị Thúy Loan 25 6/8/2010 Nguyễn Thị Thúy Loan 26 Các bước thực hiện Tìm kiếm tuyến tính  Bước 1: i = 0; Ví dụ: Cho dãy số a, giá trị tìm x = 8:  Bước 2: So sánh a[i] với x, có hai t.hợp: 12 2 5 8 1 6 4 o a[i] = x: Tìm thấy  Trả về vị trí i Tìm được đượ o a[i]  x: Sang bước 3 x=8  Bước 3: i = i + 1// xét phần tử kế tiếp o Nếu i≥N:Hết mảng không thấyTrả về -1 12 2 5 8 1 6 4 o Nếu i  N: Quay lại bước 2 6/8/2010 Nguyễn Thị Thúy Loan 27 6/8/2010 Nguyễn Thị Thúy Loan 28
Tìm kiếm tuyến tính Tìm kiếm tuyến tính 1. Cài đặt bình thường. Nhận xét: 2. Cải tiến lại bằng cách sử dụng phần tử  Giải thuật tìm kiếm tuyến tính không phụ cầm canh. thuộc vào thứ tự của các phần tử trong mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy bất kỳ. 6/8/2010 Nguyễn Thị Thúy Loan 29 6/8/2010 Nguyễn Thị Thúy Loan 30 Tìm kiếm tuyến tính Tìm kiếm nhị phân Khái niệm:  Một thuật toán có thể được cài đặt theo  Phép tìm kiếm nhị phân được áp dụng trên dãy nhiều cách khác nhau, kỹ thuật cài đặt khóa đã có thứ tự: k[0]  k[0]... k[n-1]. ảnh hưởng nhiều đến tốc độ thực hiện.  Phương pháp này dựa trên ý tưởng sau: Ví dụ như thuật toán cải tiến sẽ chạy Giả sử ta cần tìm trong đoạn a[left..right] với khoá nhanh hơn thuật toán trước do vòng lặp tìm kiếm là x, trước hết ta xét phần tử giữa while chỉ so sánh một điều kiện... a[mid], với mid = (left + right)/2. 6/8/2010 Nguyễn Thị Thúy Loan 31 6/8/2010 Nguyễn Thị Thúy Loan 32
Tìm kiếm nhị phân Các bước thực hiện  Nếu a[mid] < x thì có nghĩa là đoạn a[left] đến  B1: left =0, right = n-1 a[mid] chỉ chứa khóa < x, ta tiến hành tìm kiếm  B2: mid = (left + right)/2// lấy mốc so sánh từ a[mid+1] đến a[right]. So sánh a[mid] với x, có 3 khả năng  Nếu a[mid] > x thì có nghĩa là đoạn a[mid] đến o a[mid] = x: Tìm thấy  Trả về vị trí mid o a[mid] >x: right = mid -1; a[right] chỉ chứa khoá > x, ta tiến hành tìm o a[mid] < x: left = mid +1 kiếm từ a[left] đến a[mid-1].  B3:  Nếu a[mid]=x thì việc tìm kiếm thành công. o Nếu left  right // còn phần tử  Lặp B2  Quá trình tìm kiếm thất bại nếu left > right. o Ngược lại: Trả về -1// đã xét hết các phần tử 6/8/2010 Nguyễn Thị Thúy Loan 33 6/8/2010 Nguyễn Thị Thúy Loan 34 Tìm kiếm nhị phân Tìm kiếm nhị phân Ví dụ: cho dãy số gồm 8 phần tử bên dưới và x = 8: Nhận xét: 1 2 4 5 6 8 12 15  Thuật giải nhị phân dựa vào quan hệ giá trị X=8 của các phần tử trong mảng để định hướng 1 2 4 5 6 8 12 15 trong quá trình tìm kiếm, do vậy chỉ áp dụng Left = 0 Mid = 3 Right = 7 Đoạn tìm kiếm được với dãy đã có thứ tự. X=8  Thuật giải nhị phân tìm kiếm nhanh hơn tìm = kiếm tuyến tính. 1 2 4 5 6 8 12 15 Left = 4 Mid = 5 Right = 7 Đoạn tìm kiếm 6/8/2010 Nguyễn Thị Thúy Loan 35 6/8/2010 Nguyễn Thị Thúy Loan 36
Tìm kiếm nhị phân Sắp xếp  Sắp xếp là quá trình bố trí lại các phần tử  Tuy nhiên khi áp dụng thuật giải nhị của một tập đối tượng theo một thứ tự phân thì cần phải quan tâm đến chi phí nhất định. cho việc sắp xếp mảng. Vì khi mảng  Ví dụ: {1, 2, 5, 7, 9, 12}, {14, 12, 7, 5, 2, 1} được sắp thứ tự rồi thì mới tìm kiếm nhị {“An” “Binh” “Dương” “Hương”} phân. 6/8/2010 Nguyễn Thị Thúy Loan 37 6/8/2010 Nguyễn Thị Thúy Loan 38 Sắp xếp Sắp xếp  Dữ liệu thường được tổ chức thành mảng  Việc sắp xếp là một bài toán phổ biến các mẫu tin. trong tin học. Do các yêu cầu tìm kiếm  Mỗi mẫu tin thường có một số các trường thuận lợi, sắp xếp kết xuất cho các bảng dữ liệu khác nhau. biểu...  Trường tham gia quá trình tìm kiếm gọi là khóa (key).  Việc sắp xếp sẽ được tiến hành dựa vào giá trị khoá này. 6/8/2010 Nguyễn Thị Thúy Loan 39 6/8/2010 Nguyễn Thị Thúy Loan 40
Các phương pháp sắp xếp Mô tả bài toán  Để tiện cho việc minh họa các thuật toán 1. Đổi chỗ trực tiếp (interchange Sort) sắp xếp ta mô tả bài toán như sau: 2. Chèn trực tiếp (insertion Sort) Cho một mảng a gồm các phần tử, mỗi 3. Chọn trực tiếp (Selection Sort) phần tử trong mảng có một thuộc tính 4. Nổi bọt (Bubble Sort ) khóa. Hãy sắp xếp tăng hoặc giảm các 5. Shell sort phần tử trong mảng theo giá trị khóa này. 6. Quick sort 6/8/2010 Nguyễn Thị Thúy Loan 41 6/8/2010 Nguyễn Thị Thúy Loan 42 Mô tả bài toán Interchange Sort Ý tưởng:  Do mỗi phần tử có giá trị khóa nên ta gọi  Xuất phát từ đầu dãy, lần lượt tìm những k[0..n-1] là mảng các khóa của các phần phần tử còn lại không thỏa thứ tự với tử trong e. phần tử đang xét. Với mỗi phần tử tìm  Yêu cầu: sắp xếp các giá trị này sao cho được mà không thoả thứ tự mảng k có thứ tự tăng hoặc giảm. • Thực hiện hoán vị để thỏa thứ tự  Lặp lại tương tự với các phần tử tiếp theo 6/8/2010 Nguyễn Thị Thúy Loan 43 6/8/2010 Nguyễn Thị Thúy Loan 44
Các bước thực hiện Ví dụ minh họa B1: i = 0; // đầu dãy B2: j = i +1; // duyệt qua các phần tử sau i j B3: while j < n do o if a[j] < a[i] then Swap(a[i], a[j]); 10 3 7 6 2 5 4 16 o j = j +1; i B4: i = i +1; o if i < n then B2; o else  Kết thúc! 6/8/2010 Nguyễn Thị Thúy Loan 45 6/8/2010 Nguyễn Thị Thúy Loan 46 Cài đặt Insertion Sort Ý tưởng:  Cho dãy ban đầu a[0], a[2],.., a[n-1], ta có thể xem dãy con gồm một phần tử a[0] đã được sắp.  Sau đó thêm a[1] vào đoạn a[0] sao cho a[0] a[1] được sắp. 6/8/2010 Nguyễn Thị Thúy Loan 47 6/8/2010 Nguyễn Thị Thúy Loan 48
Insertion Sort Các bước thực hiện B1: i = 1;//giả sử có đoạn a[0] đã được sắp  Tiếp tục thêm a[2] vào để có a[0] a[1] a[2] B2: x= a[i]; được sắp.... o Tìm được vị trí cần chèn x vào là pos  Cho đến khi thêm xong a[n-1] vào đoạn B3: Dời chỗ các phần tử từ a[pos]  a[i-1] a[0] a[1]...a[n-2]  đoạn a[0] a[1]...a[n-2] sang phải một vị trí để dành chỗ cho a[i]. B4: a[pos] = x;// có a[0]...a[i] được sắp. a[n-1] được sắp. B5: i = i +1; o Nếu i < n: Lặp lại B2 o Ngược lại: Dừng  Dãy đã được sắp 6/8/2010 Nguyễn Thị Thúy Loan 49 6/8/2010 Nguyễn Thị Thúy Loan 50 Selection Sort Các bước thực hiện Ý tưởng: B1: i = 0  Lượt thứ nhất, chọn trong dãy khoá k[0..n-1] ra B2: Tìm phần tử a[min] nhỏ nhất trong dãy khóa nhỏ nhất và đổi giá trị với k[0], khi đó k[0] hiện hành từ a[i] đến a[n-1] sẽ trở thành khoá nhỏ nhất. B3: Hoán vị a[i] và a[min]  Lượt thứ hai, chọn trong dãy khoá k[1..n-1] ra B4: Nếu i < n -1 thì i= i+1  Lặp B2 khóa nhỏ nhất và đổi giá trị với k[1]…. Ngược lại  Dừng  Lượt n-2, chọn giá trị nhỏ nhất trong k[n-2] và Ví dụ: Cho dãy số như sau: k[n-1] ra khoá nhỏ nhất và đổi giá trị với k[n-2]. 12 2 8 5 1 6 4 1 6/8/2010 Nguyễn Thị Thúy Loan 51 6/8/2010 Nguyễn Thị Thúy Loan 52
Bubble Sort Các bước thực hiện Ý tưởng: B1: i=0; // lần xử lý đầu tiên  Xuất phát từ cuối dãy, đổi chỗ các cặp phần B2: j=n-1; // duyệt từ cuối ngược về i tử kế cận để đưa phần tử nhỏ hơn về đầu. Trong khi (j>i) thực hiện:  Sau đó ở bước tiếp theo không xét phần tử o Nếu a[j] < a[j-1]: Hoán đổi a[j] và a[j-1] đó nữa. Do vậy lần xử lý thứ i sẽ có vị trí o j = j -1; đầu dãy là i. B3: i = i+1; // lần xử lý kế tiếp  Lặp lại xử lý trên cho đến khi không còn o Nếu i > n-1: Hết dãy  Dừng cặp phần tử nào được xét. o Ngược lại: quay lại B2 6/8/2010 Nguyễn Thị Thúy Loan 53 6/8/2010 Nguyễn Thị Thúy Loan 54 ShellSort ShellSort Ý tưởng:  Xét một dãy a[0]...a[n-1], cho một số  Cải tiến insertion sort nguyên h (1  h  n), chia dãy thành h dãy o Hạn chế phương pháp chèn: khi luôn con như sau: chèn 1 phần tử vào đầu dãy! o Dãy con 1: a[1], a[1+h], a[1+2h]...  ShellSort cải tiến bằng cách chia làm o Dãy con 2: a[2], a[2+h], a[2+2h]... nhiều dãy con và thực hiện phương pháp o Dãy con 3: a[3], a[3+h], a[3+2h]... chèn trên từng dãy con. o Dãy con h: a[h], a[2h], a[3h]... 6/8/2010 Nguyễn Thị Thúy Loan 55 6/8/2010 Nguyễn Thị Thúy Loan 56
Ví dụ minh họa Ý tưởng  VD: cho dãy n = 8, h = 3  Với mỗi bước h, áp dụng Insertion Sort 10 3 7 6 2 5 4 16 trên từng dãy con độc lập để làm mịn dần các phần tử trong dãy chính. Dãy chính 10 3 7 6 2 5 4 16  Tiếp tục làm tương tự đối với bước h div Dãy con 1 10 6 4 2... cho đến h = 1.  Khi h =1 thực hiện Insertion Sort trên 1 Dãy con 2 3 2 16 dãy duy nhất là dãy chính Dãy con 3 7 5  Kết quả được dãy phần tử được sắp. 6/8/2010 Nguyễn Thị Thúy Loan 57 6/8/2010 Nguyễn Thị Thúy Loan 58 Các bước thực hiện QuickSort B1: chọn k khoảng cách h[0], h[1],..,h[k-1], và  Thuật toán do Hoare đề xuất i = 0; o Tốc độ trung bình nhanh hơn thuật toán B2: Chia dãy ban đầu thành các dãy con có khác. bước nhảy là h[i]. o Do đó Hoare dùng “quick” để đặt tên o Thực hiện sắp xếp từng dãy con bằng  Ý tưởng chính: QS phân hoạch dãy ban insertion sort. đầu thành hai phần dựa vào một giá trị x. B3: i = i+1 o Nếu i ≥ k:  Dừng o Dãy 1: gồm các phần tử a[i] nhỏ hơn x o Ngược lại:  Bước 2. o Dãy 2: gồm các phần tử a[i] lớn hơn x 6/8/2010 Nguyễn Thị Thúy Loan 59 6/8/2010 Nguyễn Thị Thúy Loan 60
QuickSort Các bước thực hiện  B1: Phân hoạch dãy a[l]...a[r] thành các  Phân hoạch dãy cần sắp a[l] .. a[r] thành dãy con: ba phần: o Dãy con 1: a[l]...a[j] < x o a[k] < x, với k = 0...i o Dãy con 2: a[j+1]...a[i-1] = x o a[k] = x, với k = i..j o Dãy con 3: a[i]...a[r] > x o a[k] > x, với k = j..n-1  B2: Trong đó x là một giá trị nào đó trong o Nếu (l < j): Phân hoạch dãy a[l]..a[j] dãy a[k] < x a[k] = x a[k] > x o Nếu (i x  j--; ThS. Nguyễn Thị Thúy Loan o Nếu i
Nội dung DSLK đơn - Giới thiệu  Mảng 1 chiều  Danh sách liên kết đơn o Kích thước cố định o Giới thiệu o Chèn 1 phần tử vào mảng rất khó o Cài đặt o Các phần tử tuần tự theo chỉ số 0  n-1 o Thao tác o Truy cập ngẫu nhiên o Ứng dụng chèn  Danh sách vòng  Danh sách liên kết kép 0 1 2 3 4 n-2 n-1 6/8/2010 Nguyễn Thị Thúy Loan 65 6/8/2010 Nguyễn Thị Thúy Loan 66 Giới thiệu Giới thiệu Danh sách liên kết  Cấp phát động lúc chạy chương trình Insert,  Các phần tử nằm rải rác ở nhiều nơi trong bộ Delete nhớ  Kích thước danh sách chỉ bị giới hạn do RAM  Thao tác thêm Xóa đơn giản 6/8/2010 Nguyễn Thị Thúy Loan 67 6/8/2010 Nguyễn Thị Thúy Loan 68
Định nghĩa Ôn pointer  Danh sách liên kết đơn là chuỗi các Node,  Nhắc lại pointer 1FF0 1FF4 được tổ chức theo thứ tự tuyến tính int i, *pi; ? pi ? i  Mỗi Node gồm 2 phần: i 1FF0 1FF4 o Phần Data, information pi = &i; ? pi 1FF0 *pi o Phần link hay con trỏ trỏ đến Node kế tiếp i 1FF0 1FF4 i = 10 or *pi = 10 *pi 10 pi 1FF0 6/8/2010 Nguyễn Thị Thúy Loan 69 6/8/2010 Nguyễn Thị Thúy Loan 70 Minh họa Minh họa  Mô tả danh sách Data Link  Ví dụ: Địa chỉ pHead 700 500 A1 A2 A3 An ‘D’ 500 ‘S’ 600 600 300 null Node Tail Node ‘L’ 300 ‘D’ null Head Node 6/8/2010 Nguyễn Thị Thúy Loan 71 6/8/2010 Nguyễn Thị Thúy Loan 72
Khai báo phần data Khai báo phần data  Khai báo danh sáchLK typedef struct Node  Data { Cấu trúc Data info; Node o Kiểu dữ liệu định nghĩa trước Node * next; }; o Chứa dữ liệu, thông tin của từng Node Typedef struct Node { DATA info ; typedef struct Node typedef struct Node { { Node * next ; int info; SinhVien info; }; Node * next; Node * next; }; }; Data: int, long, float, SV, 6/8/2010 NV,…. Nguyễn Thị Thúy Loan 73 6/8/2010 Nguyễn Thị Thúy Loan 74 Khai báo và khởi tạo Thao tác cơ bản  Tạo một nút mới typedef struct Node  Thêm phần tử vào đầu danh sách {  Thêm phần tử vào cuối danh sách Data info;  Thêm phần tử vào sau q Phần minh Node * next;  Xóa phần tử đầu. họa sẽ dùng }; Data là int  Xóa phần tử sau q Node* h; h quản lý danh sách  Tìm kiếm. Node* h = NULL; Khởi tạo danh sách  Sắp xếp. 6/8/2010 Nguyễn Thị Thúy Loan 75 6/8/2010 Nguyễn Thị Thúy Loan 76
Tạo nút mới Thêm phần tử vào đầu DS Node * Getnode (Data x)  Thêm vào đầu danh sách p new h h { Node * p = new Node; if ( p == NULL ) return NULL; p  info = x; p  next = NULL; p p h h return p ; } 6/8/2010 Nguyễn Thị Thúy Loan 77 6/8/2010 Nguyễn Thị Thúy Loan 78 Thêm phần tử vào đầu DS Thêm phần tử vào cuối DS 6/8/2010 Nguyễn Thị Thúy Loan 79 6/8/2010 Nguyễn Thị Thúy Loan 80