›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Phạm Thị Hà

pdf 140 trang phuongnguyen 3170
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 - Phạm Thị Hà", để 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_pham_thi_ha.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Phạm Thị Hà

  1. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT TS.Phan Thị Hà Học Viện CNBCVT Phan Thị Hà
  2. BT kiểm tra kiến thức LT  Viết chƣơng trình tính tổng các số nguyên tố của 1 ma trận các số nguyên. Biết rằng ct gồm có ít nhất các hàm sau:  Void Nhập( int a, int n); nhập ma trận  Voi nhap( int a[][10], int n)  int ngt( int so): Xác định so có phải ng tố k?  Int Tong( int a, int n): Tính tổng các số nguyên tố theo yêu cầu đầu bài  Int Tong( int a[][10], int n)  Int Main() Phan Thị Hà
  3. Danh sách nhóm trƣởng  Nhóm 4: Bùi Thành Lộc 01663177081 mrkasa1201@gmail.com  Phan Văn Quang 0988806405 buinhulac110i@gmail.com  Nhóm 5: Trần Quang Hoàn 0919963616 Tranhoanhq@gmail.com  Đặng thị Ngọc Trâm0915365653 ngoctramnd2013@gmail.com  Nhóm 7: Phan Văn Trung 0943241608 trungphanptit@gmail.com  Phạm Quang Sơn 0964535086 quángon137@gmail.com  Nhóm 8: Bùi Văn Công 0978776096 conghcl2010@gmail.com  Nguyễn Mạnh Toàn 01677535717 nguyenmanhtoan1501@gmail.com  Nhóm 9: Nghuyễn Thanh Tuấn 01685155229 thanh.tuan.1995.0411@gmail.com.vn  Đào Bá Huỳnh 0974021385 boy.sl.pro.1994@gmail.com  Nhóm 10: Nguyễn Văn Tiến 0966626212 nvtien94@gmail.com  Trần Lƣơng Bằng 0975453108 Phan Thị Hà
  4. Nội dung  Chƣơng 1: Phân tích – Thiết kế giải thuật  Chƣơng 2: Đệ Quy  Chƣơng 3: Mảng và Danh sách liên kết  Chƣơng 4: Ngăn xếp và Hàng đợi  Chƣơng 5: Cấu trúc dữ liệu kiểu cây  Chƣơng 6: Đồ thị  Chƣơng 7: Sắp xếp và tìm kiếm Phan Thị Hà
  5. CHƢƠNG 1: PHÂN TÍCH – THIẾT KẾ GIẢI THUẬT Phan Thị Hà
  6. Giải thuật là gì?  Giải thuật – hay thuật toán  Thuật toán là một chuỗi hữu hạn các lệnh. Mỗi lệnh có một ngữ nghĩa rõ ràng và có thể được thực hiện với một lượng hữu hạn tài nguyên trong một khoảng hữu hạn thời gian.  Tính chất của thuật toán:  Xác định rõ đầu vào, đầu ra  Hữu hạn  Chính xác  Tổng quát Phan Thị Hà
  7. Ngôn ngữ diễn đạt giải thuật  Ngôn ngữ tự nhiện  Sơ đồ khối  Giả mã  Vd Phan Thị Hà
  8. Phân tích thuật toán  Nhiệm vụ: Phân tích – tính toán thời gian thực hiện của chƣơng trình Phan Thị Hà
  9. Phân tích thuật toán  Định nghĩa. Cho 2 hàm f và g là các hàm thực không âm có miền xác định trong tập số tự nhiên. Ta viết f(n)=O(g(n)) (đọc là f(n) là O lớn của g(n)) nếu tồn tại hằng số C>0 và số tự nhiên n0 sao cho f(n) n0 .  Nếu một thuật toán có thời gian thực hiện T(n)=O(g(n)) ta nói rằng thuật toán có thời gian thực hiện cấp cao nhất là g(n) Đôi khi ta cũng nói đơn giản là thuật toán có thời gian thực hiện cấp g(n) hay độ phức tạp tính toán của thuật toán là g(n). Ngƣời ta cũng thƣờng nói đến độ phức tạp tính toán của thuật toán trong trƣờng hợp xấu nhất, trƣờng hợp tốt nhất, độ phức tạp trung bình. Phan Thị Hà
  10. Các quy tắc để đánh giá thời gian thực hiện thuật toán  Nếu T1(n) = O(f(n)), T2(n) = O(g(n)), khi đó  Qui tắc tổng: T1(n)+ T2(n) = O(max(f(n),g(n)))  Quy tắc nhân: T1(n)T2(n) = O(f(n)g(n)) Phan Thị Hà
  11. Một số quy tắc chung:  Thời gian thực hiện các lệnh gán, đọc, ghi .v.v, luôn là O(1).  Thời gian thực hiện chuỗi tuần tự các lệnh đƣợc xác định theo quy tắc cộng cấp độ tăng.  Có nghĩa là thời gian thực hiện của cả nhóm lệnh tuần tự được tính là thời gian thực hiện của lệnh lớn nhất.  Thời gian thực hiện lệnh rẽ nhánh (If) đƣợc tính bằng thời gian thực hiện các lệnh khi điều kiện kiểm tra đƣợc thoả mãn và thời gian thực hiện việc kiểm tra điều kiện.  Trong đó thời gian thực hiện việc kiểm tra điều kiện luôn là O(1).  Thời gian thực hiện 1 vòng lặp đƣợc tính là tổng thời gian thực hiện các lệnh ở thân vòng lặp qua tất cả các bƣớc lặp và thời gian để kiểm tra điều kiện dừng.  Thời gian thực hiện này thường được tính theo quy tắc nhân cấp độ tăng số lần thực hiện bước lặp và thời gian thực hiện các lệnh ở thân vòng lặp. Phan Thị Hà
  12. Ví dụ 1  Giả sử ta cần đánh giá độ phức tạp tính toán của các câu lệnh sau đây:  (a) for(i=0;i< n;i++)  {x=0;  for(j=0;j<n;j++) x++;  };  (b) for(i=0;i< n;i++) y++;  Câu lệnh x++ đƣợc đánh giá là O(1), do đó câu lệnh (a) có thời gian thực hiện là n(n+1) do đó đƣợc đánh giá O(n2+n)) = n2 , câu lệnh (b) đƣợc đánh giá là O(n). Do đó thời gian thực hiện cả 2 thuật toán trên đƣợc đánh giá là: 2  O(n(n+1)+n) = O(max(n(n+1),n)=O(n(n+1)) = n . Phan Thị Hà
  13.  Thuật toán nổi bọt nhƣ sau :  void buble (int a[n]){  int i, j, temp;  1. for (i = 0; i = i+1; j )  3. if (a[j-1] > a[j]{  // Đổi chỗ cho a[j] và a[j-1]  4. temp = a[j-1];  5. a[j-1] = a[j];  6. a[j] = temp;  }  }  Kích thƣớc dữ liệu vào chính là số phần tử đƣợc sắp, n. Mỗi lệnh gán sẽ có thời gian thực hiện cố định, không phụ thuộc vào n, do vậy, các lệnh 4, 5, 6 sẽ có thời gian thực hiện là O(1), tức thời gian thực hiện là hằng số. Theo quy tắc cộng cấp độ tăng thì tổng thời gian thực hiện cả 3 lệnh là O(max(1, 1, 1)) = O(1).  If sẽ có thời gian thực hiện là O(1).  Vòng lặp j. mỗi bƣớc lặp có thời gian thực hiện là O(1). Số bƣớc lặp là n-i, do đó theo quy tắc nhân cấp độ tăng thì tổng thời gian thực hiện của vòng lặp này là O((n-i)x1) = O(n-i).  Vòng lặp i, đƣợc thực hiện (n-1) lần: O(n-1)  Do đó, tổng thời gian thực hiện của chƣơng trình là: 2 2  ∑ (n-i) = n(n-1)/2 = n /2- n/2 = O(n ) Phan Thị Hà
  14. CHƢƠNG 2: ĐỆ QUY Phan Thị Hà
  15.  Định nghĩa đệ qui  Hàm trình đệ qui  Các ƣu điểm của hàm đệ qui  Một số thuật toán đệ qui Phan Thị Hà
  16. Đệ quy là gì(PPđịnh nghĩa bằngĐQ)  Khái niệm  Một đối tƣợng đƣợc gọi là đệ qui nếu nó hoặc một phần của nó đƣợc định nghĩa thông qua khái niệm về chính nó.  Ví dụ  Định nghĩa số tự nhiên:  0 là số tự nhiên.  Nếu k là số tự nhiên thì k+1 cũng là số tự nhiên.  Định nghĩa hàm giai thừa, n!.  Khi n=0, định nghĩa 0!=1  Khi n>0, định nghĩa n!=(n-1)! x n Như vậy, khi n=1, ta có 1!=0!x1 = 1x1=1. Khi n=2, ta có 2!=1!x2=1x2=2, v.v. Phan Thị Hà
  17. Giải thuật đệ qui  Nếu lời giải của bài toán P đƣợc thực hiện bằng lời giải của bài toán P‟ giống nhƣ P thì lời giải này đƣợc gọi là lời giải đệ qui. Giải thuật tƣơng ứng với lời giải bài toán P đƣợc gọi là giải thuật đệ qui. Phan Thị Hà
  18. Hàm đệ qui  Hàm này có thể gọi chính nó nhƣng nhỏ hơn Khi hàm gọi chính nó, mục đích là để giải quyết 1 vấn đề tƣơng tự, nhƣng nhỏ hơn.Vấn đề nhỏ hơn này, cho tới 1 lúc nào đó, sẽ đơn giản tới mức hàm có thể tự giải quyết đƣợc mà không cần gọi tới chính nó nữa. Phan Thị Hà
  19. Quá trình hoạt động của giải thuật ĐQ  Bƣớc phân tích  Bƣớc thay thế ngƣợc lại VD:tính f(n)= n! +f(n)=n*f(n-1) . f(1)=1*f(0) f(0)=0!=1 +f(0)=1 f(1)=1*f(0) . f(n)=n*f(n-1) Phan Thị Hà
  20. Đặc điểm của hàm đệ qui Chỉ ra trƣờng hợp dừng đệ quy Chỉ ra việc đệ quy Phan Thị Hà
  21. Khi nào sử dụng đệ qui  Vấn đề cần xử lý phải đƣợc giải quyết có đặc điểm đệ quy  Ngôn ngữ dùng để viết chƣơng trình phải hỗ trợ đệ qui. Để có thể viết chƣơng trình đệ qui chỉ cần sử dụng ngôn ngữ lập trình có hỗ trợ hàm hoặc thủ tục, nhờ đó một thủ tục hoặc hàm có thể có lời gọi đến chính thủ tục hoặc hàm đó Phan Thị Hà
  22. Một số thuật toán đệ qui  Thuật toán cột cờ ( sách)  Thuật toán quay lui Thuật toán sinh xâu ( hoặc sinh hoán vị) Mã đi tuần Bài toán 8 quân hậu (sách) Phan Thị Hà
  23. Bài toán cột cờ Phan Thị Hà
  24. Bài toán cột cờ Phan Thị Hà
  25. Phân tích bài toán CC  T/C Chia để trị: Chuyển hàm với dl lớn (bài toán lớn) thành hàm với dl nhỏ hơn (bài toán nhỏ hơn), ., cứ tiếp tục nhƣ thế cho đến khi gặp ĐK dừng  Chỉ ra việc đệ quy: Bài toán chuyển n cọc đã đƣợc chuyển về bài toán đơn giản hơn là chuyển n-1 cọc.  Điểm dừng của thuật toán đệ qui là khi n=1 và ta chuyển thẳng cọc này từ cọc ban đầu sang cọc đích. Phan Thị Hà
  26. Thiết kế một số giải thuật đệ quy  Giải thuật đệ quy CHIA ĐỂ TRỊ - Bài toán tháp Hà Nội void chuyen(int n, char a, char c){ printf(„Chuyen dia thu %d tu coc %c sang coc %c \n”,n,a,c); return; } void thaphanoi(int n, char a, char c, char b){ if (n==1) chuyen(1, a, c); else{ thaphanoi(n-1, a, b, c); chuyen(n, a, c); thaphanoi(n-1, b, c,a); } return; } Phan Thị Hà
  27. Phan Thị Hà
  28. Thuật toán quay lui  Xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả sử cần phải tìm một cấu hình của bài toán x = (x1, x2, . ., xn) mà i- 1 thành phần x1, x2, . ., xi-1 đã đƣợc xác định.  Bây giờ ta xác định thành phần thứ i của cấu hình bằng cách duyệt tất cả các khả năng có thể có và đánh số các khả năng từ 1 . .ni.  Với mỗi khả năng j, kiểm tra xem j có chấp nhận đƣợc hay không. Khi đó có thể xảy ra hai trƣờng hợp: Phan Thị Hà
  29.  Nếu chấp nhận j thì xác định xi theo j, nếu i=n thì ta đƣợc một cấu hình cần tìm, ngƣợc lại xác định tiếp thành phần xi+1.  Nếu thử tất cả các khả năng mà không có khả năng nào đƣợc chấp nhận thì quay lại bƣớc trƣớc đó để xác định lại xi-1. Phan Thị Hà
  30. Phân tích đặc điểm của bài toán quay lui  Toàn bộ vấn đề đƣợc thực hiện dần từng bƣớc.Tại mỗi bƣớc có ghi lại kết quả để sau này có thể quay lại và hủy kết quả đó nếu phát hiện ra rằng hƣớng giải quyết theo bƣớc đó đi vào ngõ cụt và không đem lại giải pháp tổng thể cho vấn đề. =>Do đó, thuật toán đƣợc gọi là thuật toán quay lui  Đệ quy: Bƣớc thứ sau làm giống hệt bƣớc trƣớc, nhƣng dl khác  Điều kiện dừng: Sau khi duyệt tất cả các khả nămg có thể có của dữ liệu ở mỗi bƣớc  Quay lui, nếu hƣớng giải quyết vào ngõ cụt (xóa vết Phan Thị Hà hoặc không xóa vết)
  31. Thuật toán  void Try( int i ) {  int j;  for ( j = ; j ) {   if (i==n)  ;  else Try(i+1); }  } Phan Thị Hà
  32. Thuật toán sinh xâu nhị phân( sử dụng quay lui)  Void Try ( int i ) {  for (int j =0; j<=1; j++){  X[i] = j;  if ( i ==n) Result();  else Try (i+1);  }  } Phan Thị Hà
  33. Hoán vị  Void Try ( int i ) {  for (int j =1; j<=N; j++){  if (chuaxet[j] ) {  X[i] = j;chuaxet[j] = 0;  if ( i ==N) Result();  else Try (i+1);  Chuaxet[j] = 1;  }  }  } Phan Thị Hà
  34. Danh sách 8 vị trí bước đi kế tiếp : (x+2, y-1); (x+1, y-2); (x-1, y-2); (x-2, y-1); (x- 2, y+1); (x-1, y+2); (x+1; y+2); (x+2, y+1) Banco[x][y] = 0: ô (x,y) chưa được quân Mã đi tuần mã đi qua Banco[x][y] = i: ô (x,y) đã được quân mã đi qua tại nước thứ i. 3 2 Bước đi kế tiếp (u,v) 4 1 u = x + dx[i] v = y + dy[i] (u,v)chấp nhận được nếu: +Banco[u][v] = 0 - ĐK 1 để chấp nhận. 5 8 +0 u, v < n – đk 2 để chấp nhận 6 7 ĐK dừng : Kiểm tra xem bàn cờ còn ô trống không bằng cách kiểm tra xem i đã bằng n2 chưa và đã đi hết các nước đi chưa (nhiều nhất là 8) Phan Thị Hà
  35. Bài toán Mã đi tuần-Thuật toán quay lui  void ThuNuocTiepTheo;  {  Khởi tạo danh sách các nước đi kế tiếp;  do{  Lựa chọn 1 nước đi kế tiếp từ danh sách;  if Chấp nhận được  {  Ghi lại nước đi;  if Bàn cờ còn ô trống  {  ThuNuocTiepTheo;  if Nước đi không thành công  Hủy bỏ nước đi đã lưu ở bước trước  }  }  }while (nước đi không thành công) && (vẫn còn nước đi)  } Phan Thị Hà
  36.  void ThuNuocTiepTheo(int i, int x, int y, int *q)  {  int k, u, v, *q1;  k=0;  do{  *q1=0;  u=x+dx[k];  v=y+dy[k];  if ((0 <= u) && (u<n) && (0 <= v) && (v<n) && (Banco[u][v]==0))  {  Banco[u][v]=i;  if (i<n*n) {  ThuNuocTiepTheo(i+1, u, v, q1)  if (*q1==0) Banco[u][v]=0; }  else *q1=1;  }  k=k+1;  }while ((*q1==0) && (k<8));  *q=*q1; Phan Thị Hà  }
  37. int dx[8]={2,1,-1,-2,-2,-1,1,2}; int dy[8]={-1,-2,-2,-1,1,2,2,1}; int n=8; Có 3 chiếc cọc và một bộ n chiếc đĩa. Các đĩa này có kích thước khác nhau và mỗi đĩa đều có 1 lỗ ở giữa để có thể xuyên chúng vào các cọc. Ban đầu, tất cả các đĩa đều nằm trên 1 cọc, trong đó, đĩa nhỏ hơn bao giờ cùng nằm trên đĩa lớn hơn. Phan Thị Hà
  38. Thiết kế một số giải thuật đệ quy Bài toán 8 quân hậu void DatHau(int i) { Khởi tạo danh sách các vị trí có thể đặt quân hậu tiếp theo; do{ Lựa chọn vị trí đặt quân hậu tiếp theo; if Vị trí đặt là an toàn { Đặt hậu; if i<8 { DatHau(i+1); if Không thành công Bỏ hậu đã đặt ra khỏi vị trí } } }while (Không thành công) && (Vẫn còn lựa chọn) } Phan Thị Hà
  39. CHƢƠNG 3: MẢNG VÀ DANH SÁCH LIÊN KẾT Phan Thị Hà
  40. Mảng  Một mảng là 1 tập hợp cố định các thành phần có cùng 1 kiểu dữ liệu, đƣợc lƣu trữ kế tiếp nhau và có thể đƣợc truy cập thông qua một chỉ số.  Ví dụ, để truy cập tới phần tử thứ i của mảng a, ta viết a[i]. Mảng có thể có nhiều hơn 1 chiều. Khi đó, số các chỉ số của mảng sẽ tương ứng với số chiều. Chẳng hạn, trong mảng 2 chiều a, thành phần thuộc cột i, hàng j được viết là a[i][j]. Mảng 2 chiều còn được gọi là ma trận (matrix). Phan Thị Hà
  41. Nhƣợc:  Kích thƣớc (số phần tử) của mảng là cố định Phan Thị Hà
  42. Ôn lại thao tác với mảng  Khai báo mảng  Mảng tĩnh  Mảng động  Truy nhập 1 phần tử của mảng Phan Thị Hà
  43. Ôn lại CẤP PHÁT BỘ NHỚ ĐỘNG  Cấp phát bộ nhớ động  Giải phóng bộ nhớ động = new ; con trỏ>; VD:  VD: int *pa = new int(12); int *pa; delete pa; pa = new int; VD:  Hoặc  int *pa = new int(12); int *pa;  int *pb = pa; pa = new int(12);  *pb += 5;  delete pa; Phan Thị Hà
  44. Ôn lại CẤP PHÁT BỘ NHỚ ĐỘNG  Cấp phát bộ nhớ cho mảng động một chiều = new [ ]; VD: int *A = new int[5];  Giải phóng bộ nhớ của mảng động một chiều delete [] ; VD: int *A = new int[5]; delete [] A; Phan Thị Hà
  45. Danh sách liên kết  Khái niệm  Danh sách liên kết là 1 cấu trúc dữ liệu bao gồm 1 tập các phần tử , trong đó mỗi phần tử là 1 phần của 1 nút có chứa một liên kết tới nút kế tiếp.  Biểu diễn Đầu Cuối  Điểm khác biệt giữa DSLK và Mảng  Mảng có thể đƣợc truy cập ngẫu nhiên thông qua chỉ số, còn danh sách chỉ có thể truy cập tuần tự.  Việc bố trí, sắp đặt lại các phần tử trong 1 danh sách liên kết đơn giản hơn nhiều so với mảng.  Do bản chất động của danh sách liên kết, kích thƣớc của danh sách liên kết có thể linh hoạt hơn nhiều so với mảng. Phan Thị Hà
  46. Khai báo danh sách trong C,C++  Đơn giản struct node { int item; struct node *next; }; typedef struct node *listnode;  Phức tạp struct node { itemstruct item; struct node *next; }; typedef struct node *listnode; Phan Thị Hà
  47. Các thao tác trên DSLK  Tập các thao tác:  Tạo, cấp phát, và giải phóng bộ nhớ cho 1 nút  Chèn một nút vào đầu danh sách  Chèn một nút vào cuối danh sách  Chèn một nút vào trước nút r trong danh sách  Xóa một nút ở đầu danh sách  Xóa một nút ở cuối danh sách  Xóa một nút ở trước nút r trong danh sách  Duyệt toàn bộ danh sách  Cài đặt các thao tác: SGK Phan Thị Hà
  48. Tạo, cấp phát, và giải phóng bộ nhớ cho 1 nút  listnode p; // Khai báo biến p  p = new (node);//cấp phát bộ nhớ cho p  delete(p); //giải phóng bộ nhớ đã cấp phát cho nút p; Phan Thị Hà
  49. Chèn thêm 1 nút vào đầu danh sách Phan Thị Hà
  50. Phan Thị Hà
  51. Chèn thêm 1 nút vào đầu danh sách  void Insert_Begin(listnode *p, int x){  listnode q;  q = new node  q-> item = x;  q-> next = *p;  *p = q;  } Phan Thị Hà
  52. Chèn thêm 1 nút vào cuối ds Phan Thị Hà
  53. Chèn một nút vào cuối danh sách void Insert_End(listnode *p, int x){ listnode q, r; q = new node; q-> item = x; q->next = NULL; if (*p==NULL) *p = q; else{ r = *p; while (r->next != NULL) r = r->next; r->next = q; } } Phan Thị Hà
  54. Chèn một nút vào trước nút r trong danh sách void Insert_Middle(listnode *p, int position, int x){ int count=1, found=0; listnode q, r; r = *p; while ((r != NULL)&&(found==0)) { if (count == position){ q = new node; q-> item = x; q-> next = r-> next; r-> next = q; found = 1; } count ++; r = r-> next; } if (found==0) cout(“Khong tim thay vi tri can chen !”); } Phan Thị Hà
  55. Xóa một nút ở đầu danh sách void Remove_Begin(listnode *p){ listnode q; if (*p == NULL) return; q = *p; *p = (*p)-> next; q-> next = NULL; free(q); } Phan Thị Hà
  56. Xóa nút ở cuối danh sách  void Remove_End(listnode *p){  listnode q, r;  if (*p == NULL) return;  if ((*p)-> next == NULL){  Remove_Begin(*p);  return;  }  r = *p;  while (r-> next != NULL){  q = r;  r = r-> next;  }  q-> next = NULL;  free(r);  } Phan Thị Hà
  57. Xóa đi 1 nút trƣớc nút r trong ds Phan Thị Hà
  58. Phan Thị Hà
  59. Xóa một nút ở trước nút r trong danh sách  void Remove_Middle(listnode *p, int position){  int count=1, found=0;  listnode q, r;  r = *p;  while ((r != NULL)&&(found==0)){  if (count == position){  q = r-> next;  r-> next = q-> next;  q-> next = NULL;  free (q);  found = 1;  }  count ++;  r = r-> next;  }  if (found==0)  cout <<“Khong tim thay vi tri can xoa !”;  } Phan Thị Hà
  60. Duyệt toàn bộ danh sách r = p; while (r-> next != null){ //thực hiện các thao tác cần thiết r = r-> next; } Phan Thị Hà
  61. Một số dạng khác của DSLK  Danh sách liên kết vòng  Danh sách liên kết kép Phan Thị Hà
  62. CHƢƠNG 4 NGĂN XẾP VÀ HÀNG ĐỢI Phan Thị Hà
  63. Ngăn xếp (Stack)  Khái niệm  Ngăn xếp là một dạng đặc biệt của danh sách mà việc bổ sung hay loại bỏ một phần tử đều đƣợc thực hiện ở 1 đầu của danh sách gọi là đỉnh.  Nói cách khác, ngăn xếp là 1 cấu trúc dữ liệu có 2 thao tác cơ bản:  bổ sung (push) và  loại bỏ phần tử (pop),  Trong đó việc loại bỏ sẽ tiến hành loại phần tử mới nhất đƣợc đƣa vào danh sách.  Chính vì tính chất này mà ngăn xếp còn đƣợc gọi là kiểu dữ liệu có nguyên tắc LIFO (Last In First Out - Vào sau ra trƣớc). Phan Thị Hà
  64. Stack  Ví dụ Phan Thị Hà
  65. Cài Stack xếp bằng mảng Phan Thị Hà
  66. Khai báo bằng mảng cho 1 ngăn xếp chứa các số nguyên với tối đa 100 phần tử  #define MAX 100  typedef struct {  int top;  int nut[MAX];  } stack; Phan Thị Hà
  67. Cài đặt Stack bằng mảng Thao tác khởi tạo ngăn xếp void StackInitialize(stack *s){ s-> top = -1; return; } Thao tác kiểm tra ngăn xếp rỗng int StackEmpty(stack s){ return (s.top = = -1); } Thao tác kiểm tra ngăn xếp đầy int StackFull(stack s){ return (s.top = = MAX-1); } Phan Thị Hà
  68. Cài đặt Stack bằng mảng Thao tác bổsung 1 phần tử vào ngăn xếp void Push(stack *s, int x){ if (StackFull(*s)){ printf(“Ngan xep day !”); return; }else{ s-> top ++; s-> nut[s-> top] = x; return; } } Thao tác lấy 1 phần tử ra khỏi ngăn xếp int Pop(stack *s){ if (StackEmpty(*s)){ printf(“Ngan xep rong !”); }else{ return s-> nut[s-> top ]; } } Phan Thị Hà
  69. Cài đặt Stack bằng DSLK Khai báo 1 ngăn xếp bằng danh sách liên kết như sau: struct node { int item; struct node *next; }; typedef struct node *stacknode; typedef struct { stacknode top; }stack; Phan Thị Hà
  70. Cài đặt Stack bằng DSLK  Thao tác khởi tạo ngăn xếp void StackInitialize(stack *s){ s-> top = NULL; return; }  Thao tác kiểm tra ngăn xếp rỗng int StackEmpty(stack s){ return (s.top == NULL); } Phan Thị Hà
  71. Cài đặt Stack bằng DSLK  Thao tác bổsung 1 phần tử vào ngăn xếp void Push(stack *s, int x){ stacknode p; p = new node; p-> item = x; p-> next = s->top; s->top = p; return; } Phan Thị Hà
  72. Cài đặt Stack bằng DSLK  Thao tác lấy 1 phần tử ra khỏi ngăn xếp int Pop(stack *s){ stacknode p; if (StackEmpty(*s)){ cout top; s-> top = s-> top-> next; return p->item; } } Phan Thị Hà
  73. Một số ứng dụng của Stack  Một số ví dụ:  Đảo ngƣợc xâu ký tự.  Tính giá trị một biểu thức dạng hậu tố (postfix).  Chuyển một biểu thức dạng trung tố sang hậu tố (infix to postfix).  Cài đặt: SGK Phan Thị Hà
  74. Hàng đợi  Khái niệm  Hàng đợi là một cấu trúc dữ liệu gần giống với ngăn xếp, nhƣng khác với ngăn xếp ở nguyên tắc chọn phần tử cần lấy ra khỏi tập phần tử. Trái ngƣợc với ngăn xếp, phần tử đƣợc lấy ra khỏi hàng đợi không phải là phần tử mới nhất đƣợc đƣa vào mà là phần tử đã đƣợc lƣu trong hàng đợi lâu nhất.  Quy luật này của hàng đợi còn đƣợc gọi là Vào trƣớc ra trƣớc (FIFO - First In First Out). Phan Thị Hà
  75. Hàng đợi Phan Thị Hà
  76. Cài đặt hàng đợi bằng mảng  Khai báo bằng mảng cho 1 hàng đợi chứa các số nguyên với tối đa 100 phần tử nhƣ sau:  #define MAX 100  typedef struct {  int head, tail, count;  int node[MAX];  } queue; Phan Thị Hà
  77. Cài đặt hàng đợi bằng mảng  Thao tác khởi tạo hàng đợi  Thao tác này thực hiện việc gán giá trị 0 cho biến head, giá trị MAX -1 cho biến tail, và giá trị 0 cho biến count, cho biết hàng đợi đang ở trạng thái rỗng. void QueueInitialize(queue *q){ q-> head = 0; q-> tail = MAX-1; q-> count = 0; return; }  Thao tác kiểm tra hàng đợi rỗng  Hàng đợi rỗng nếu có số phần tử nhỏ hơn hoặc bằng 0. int QueueEmpty(queue q){ return (q.count <= 0); } Phan Thị Hà
  78. Cài đặt hàng đợi bằng mảng  Thao tác thêm 1 phần tử vào hàng đợi void Put(queue *q, int x){ if (q-> count == MAX) cout tail == MAX-1 ) q->tail=0; else (q->tail)++; q->node[q->tail]=x; q-> count++; } return; } Phan Thị Hà
  79. Cài đặt hàng đợi bằng mảng  Lấy phần tử ra khỏi hàng đợi int Get(queue *q){ int x; if (QueueEmpty(*q)) cout node[q-> head]; if (q->head == MAX-1 ) q->head=0; else (q->head)++; q-> count ; } return x; } Phan Thị Hà
  80. Cài đặt hàng đợi bằng DSLK  Khai báo 1 hàng đợi bằng danh sách liên kết nhƣ sau: struct node { int item; struct node *next; }; typedef struct node *queuenode; typedef struct { queuenode head; queuenode tail; }queue; Phan Thị Hà
  81. Cài đặt hàng đợi bằng DSLK  Thao tác khởi tạo hàng đợi  Thao tác này thực hiện việc gán giá trị null cho nút đầu và cuối của hàng đợi, cho biết hàng đợi đang ở trạng thái rỗng. void QueueInitialize(queue *q){ q-> head = q-> tail = NULL; return; }  Thao tác kiểm tra hàng đợi rỗng  Hàng đợi rỗng nếu nút đầu trỏ đến NULL. int QueueEmpty(queue q){ return (q.head == NULL); } Phan Thị Hà
  82. Cài đặt hàng đợi bằng DSLK  Thao tác thêm 1 phần tử vào hàng đợi void Put(queue *q, int x){ queuenode p; p = new node; p-> item = x; p-> next = NULL; q-> tail-> next = p; q-> tail = q-> tail-> next; if (q-> head == NULL) q-> head = q-> tail; return; } Phan Thị Hà
  83. Cài đặt hàng đợi bằng DSLK  Lấy phần tử ra khỏi hàng đợi int Get(queue *q){ queuenode p; if (QueueEmpty(*q)){ printf("Ngan xep rong !"); return 0; }else{ p = q-> head; q-> head = q-> head-> next; return p->item; } } Phan Thị Hà
  84. CHƢƠNG 5: CẤU TRÚC DỮ LIỆU KIỂU CÂY Phan Thị Hà
  85. Cây là gì  Khái niệm cây  Cây là một tập hợp các nút (các đỉnh) và các cạnh, thỏa mãn một số yêu cầu nào đó. Mỗi nút của cây đều có 1 định danh và có thể mang thông tin nào đó. Các cạnh dùng để liên kết các nút với nhau. Một đƣờng đi trong cây là một danh sách các đỉnh phân biệt mà đỉnh trƣớc có liên kết với đỉnh sau.  Một tính chất rất quan trọng hình thành nên cây, đó là có đúng một đƣờng đi nối 2 nút bất kỳ trong cây.  Định nghĩa cây dƣới dạng đệ quy  Một nút đứng riêng lẻ (và nó chính là gốc của cây này).  Hoặc một nút kết hợp với một số cây con bên dƣới.  Một số khái niệm khác  Mỗi nút trong cây (trừ nút gốc) có đúng 1 nút nằm trên nó, gọi là nút cha (parent). Các nút nằm ngay dƣới nút đó đƣợc gọi là các nút con (subnode). Các nút nằm cùng cấp đƣợc gọi là các nút anh em (sibling). Nút không có nút con nào đƣợc gọi là nút lá (leaf) hoặc nút tận cùng.  Chiều cao của nút là đƣờng đi dài nhất từ nút tới một lá. Chiều cao của cây chính là chiều cao của nút gốc. Độ sâu của 1 nút là độ dài đƣờng đi duy nhất giữa nút gốc và nút đó. Phan Thị Hà
  86. Cài đặt cây  Cài đặt cây bằng mảng các nút cha Phan Thị Hà
  87. Cài đặt cây  Cài đặt cây thông qua danh sách các nút con Phan Thị Hà
  88. Cài đặt cây  Mã nguồn C cho cài đặt cây (bằng danh sách node con): #define max = 100; struct node { int item; struct node *next; }; typedef struct node *listnode; typedef struct { int root; listnode subnode[max]; } tree; Phan Thị Hà
  89. Duyệt cây  Duyệt là gì:  Duyệt cây là hành động duyệt qua tất cả các nút của một cây theo một trình tự nào đó. Trong quá trình duyệt, tại mỗi nút ta có thể tiến hành một thao tác xử lý nào đó. Đối với các danh sách liên kết, việc duyệt qua danh sách đơn giản là đi từ nút đầu, qua các liên kết và tới nút cuối cùng.  Ba trình tự duyệt cây phổ biến:  Duyệt cây theo thứ tự trƣớc.  Duyệt cây theo thứ tự giữa.  Duyệt cây theo thứ tự sau. Phan Thị Hà
  90. Duyệt cây theo thứ tự trƣớc Gốc Quá trình duyệt: n 1. Thăm nút gốc n. 2. Thăm cây con T1 theo phương pháp thứ tự trước. 3. Thăm cây con T2 theo phương T1 T2 Tk pháp thứ tự trước. 4. 5. Thăm cây con Tk theo phương pháp thứ tự trước. Gốc 1 2 6 7 8 3 9 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 5 4 Phan Thị Hà
  91. Duyệt cây theo thứ tự giữa Gốc n Quá trình duyệt: 1. Thăm cây con T1 theo phương pháp thứ tự giữa. 2. Thăm nút gốc n. 3. Thăm cây con T2 theo phương T T T 1 2 k pháp thứ tự giữa. 4. 5. Thăm cây con Tk theo phương pháp thứ tự giữa. Gốc 1 2 6 7 3 8 9 4 -> 3 -> 5 -> 2 -> 1 -> 6 5 -> 8 -> 7 -> 9 4 Phan Thị Hà
  92. Duyệt cây theo thứ tự sau Gốc Quá trình duyệt: n •Thăm cây con T1 theo phương pháp thứ tự sau. •Thăm cây con T2 theo phương pháp thứ tự sau. T1 T2 Tk • •Thăm cây con Tk theo phương pháp thứ tự sau. •Thăm nút gốc n. Gốc 1 2 6 7 3 8 9 4 -> 5 -> 3 -> 2 -> 6 -> 8 5 -> 9 -> 7 -> 1 4 Phan Thị Hà
  93. Cây nhị phân  Khái niệm  Cây nhị phân là một loại cây đặc biệt mà mỗi nút của nó chỉ có nhiều nhất là 2 nút con. Khi đó, 2 cây con của mỗi nút đƣợc gọi là cây con trái và cây con phải.  Ví dụ 1 2 3 4 5 6 7 Phan Thị Hà
  94. Cây nhị phân  Một số dạng cây nhị phân đặc biệt: 10  Cây nhị phân đầy đủ:  Là cây nhị phân mà mỗi nút 23 31 không phải lá đều có đúng 2 nút con và các nút lá phải có cùng độ sâu. 9 15 87 22 20  Cây nhị phân tìm kiếm:  Là cây nhị phân có tính chất khóa của nút con bên trái bao giờ cũng nhỏ hơn khóa của nút cha, còn 12 30 khóa của cây con bên phải bao giờ cũng lớn hơn hoặc bằng khóa 8 của nút 15 25 37 Phan Thị Hà
  95. Cài đặt cây nhị phân bằng mảng  Đối với cây nhị phân không cân bằng, cần sử dụng cấu trúc sau: typedef struct { int item; int leftchild; int rightchild; } node; node tree[max]; Phan Thị Hà
  96. Cài đặt cây nhị phân sử dụng DSLK  Mỗi nút của cây nhị phân khi cài đặt bằng DSLK sẽ có 3 thành phần:  Thành phần item chứ thông tin về nút.  Con trỏ left trỏ đến nút con bên trái.  Con trỏ right trỏ đến nút con bên phải. Phan Thị Hà
  97. Cài đặt cây nhị phân sử dụng DSLK  Mã nguồn: struct node { int item; struct node *left; struct node *right; } typedef struct node *treenode; treenode root; Phan Thị Hà
  98. Cài đặt các phƣơng pháp duyệt cây nhị phân  Duyệt thứ tự trƣớc void PreOrder (treenode root ) { if (root !=NULL) { printf(“%d”, root.item); PreOrder(root.left); PreOrder(root.right); } }  Duyệt thứ tự giữa void InOrder (treenode root ) { if (root !=NULL) { PreOrder(root.left); printf(“%d”, root.item); PreOrder(root.right); } }  Duyệt thứ tự sau void PostOrder (treenode root ) { if (root !=NULL) { PreOrder(root.left); PreOrder(root.right); printf(“%d”, root.item); } } Phan Thị Hà
  99. CHƢƠNG 6: ĐỒ THỊ Phan Thị Hà
  100. Các khái niệm cơ bản  Đồ thị có hƣớng  Đồ thị có hƣớng G = bao gồm:  V là một tập hữu hạn các đỉnh.  E là một tập hữu hạn, có thứ tự các cặp đỉnh của V, gọi là các cạnh.  Ví dụ:  Đồ thị có hƣớng G1 = , với V1 và E1 đƣợc xác định nhƣ sau:  V1 = {a, b, c, d}  E1 = {(a, b); (a, c}; (b, d); (c, b), (d, d)}  Khi đó, biểu diễn hình học của đồ thị này nhƣ sau: a b d c Phan Thị Hà
  101. Các khái niệm cơ bản (tiếp)  Một cạnh (u, v) của đồ thị có hƣớng có thể đƣợc biểu thị dạng u v. Đỉnh u khi đó đƣợc gọi là đỉnh kề của v. Cạnh (u, v) đƣợc gọi là cạnh xuất phát từ u. Ta ký hiệu A(u) là tập các cạnh xuất phát từ u.  Bậc ngoài của 1 đỉnh là số các cạnh xuất phát từ đỉnh đó. Do đó, bậc ngoài của u = | A(u) |.  Bậc trong của 1 đỉnh là số các cạnh đi tới đỉnh đó. Do đó, bậc trong của v = | I(v) |.  Một đƣờng đi trong đồ thị có hƣớng G(V, E) là một chuỗi các đỉnh P = {v1, v2, , vk} Trong đó, vi V (i = 1 k), và (vi, vi+1) E (i = 1 k-1).  Độ dài của đƣờng đi trong trƣờng hợp này là k - 1.  Chu trình là một đƣờng đi mà đỉnh đầu và đỉnh cuối trùng nhau. Đồ thị liên thông là một đồ thị mà luôn tồn tại đƣờng đi giữa 2 đỉnh bất kì. Phan Thị Hà
  102. Các khái niệm cơ bản (tiếp)  Đồ thị vô hƣớng  Đồ thị vô hƣớng là đồ thị có các cạnh không có hƣớng. Hai nút ở hai đầu của cạnh có vai trò nhƣ nhau. Định nghĩa về đồ thị vô hƣớng nhƣ sau:  Đồ thị vô hƣớng G = bao gồm:  V là một tập hữu hạn các đỉnh.  E là một tập hữu hạn các cặp đỉnh phân biệt của V, gọi là các cạnh.  Ví dụ, đồ thị có hƣớng G2 = , với V2 và E2 đƣợc xác định nhƣ sau:  V2 = {a, b, c, d} a b  E2 = {(a, b); (a, c}; (b, d); (c, b) } d c Phan Thị Hà
  103. Các khái niệm cơ bản (tiếp)  Đồ thị có trọng số 40km Bắc Ninh Hà Nội 96km Ninh Bình 115km 45km Thái Bình Phan Thị Hà
  104. Biểu diễn đồ thị - Ma trận kề Đồ thị có hướng Đồ thị vô hướng Đồ thị có trọng số Phan Thị Hà
  105. Biểu diễn đồ thị - Danh sách kề  Đồ thị có hƣớng  Đồ thị vô hƣớng Phan Thị Hà
  106. Duyệt đồ thị  Duyệt theo chiều sâu: void DeepFirstSearch(int v){ Thăm đỉnh v; daxet[v] = 1; for mỗi đỉnh u kề với v { if (daxet[u]=0 ) DeepFirstSearch(v); } }  Nếu có nhiều thành phần liên thông for( i=1; i n; i++) daxet[i] = 0; for( i:=1;i n; i++) if (daxet[i]=0) DeepFirstSearch(i); Phan Thị Hà
  107. Duyệt đồ thị  Duyệt theo chiều rộng void BreadthFirstSearch(int v){ queue = ; Đƣa v vào hàng đợi; daxet[v] = 1; while (queue  ){ Lấy phần tử ra khỏi hàng đợi, đƣa vào biến u; Thăm đỉnh u; for mỗi đỉnh w kề với u { if (daxet[w]=0 ) { Đƣa w vào hàng đợi; daxet[w] = 1; } } } Phan Thị Hà
  108. Ứng dụng duyệt đồ thị để kiểm tra tính liên thông  Ví dụ sử dụng duyệt theo chiều rộng: int lt=0; for( v=1; v n; v++) daxet[v] = 0; for(v=1; v n; v++) if (daxet[v]=0){ BreadthFirstSearch(u); lt++; } if (lt ==1) printf(“Do thi lien thong!”); else printf(“Do thi khong lien thong, so thanh phan lien thong la %d”, lt); Phan Thị Hà
  109. CHƢƠNG 7 SẮP XẾP VÀ TÌM KIẾM Phan Thị Hà
  110. Bài toán sắp xếp  Khái niệm  Sắp xếp là quá trình bố trí lại các phần tử của 1 tập hợp theo thứ tự nào đó. Mục đích chính của sắp xếp là làm cho thao tác tìm kiếm phần tử trên tập đó đƣợc dễ dàng hơn.  Ví dụ về tập các đối tƣợng đƣợc sắp phổ biến trong thực tế là: danh bạ điện thoại đƣợc sắp theo tên, các từ trong từ điển đƣợc sắp theo vần, sách trong thƣ viện đƣợc sắp theo mã số, theo tên, .v.v.  Các giải thuật sắp xếp đƣợc chia làm 2 loại.  Loại thứ nhất là các giải thuật đƣợc cài đặt đơn giản, nhƣng không hiệu quả (phải sử dụng nhiều thao tác).  Loại thứ hai là các giải thuật đƣợc cài đặt phức tạp, nhƣng hiệu quả hơn về mặt tốc độ (dùng ít thao tác hơn).  Đối với các tập dữ liệu ít phần tử, tốt nhất là nên lựa chọn loại thứ nhất. Đối với tập có nhiều phần tử, loại thứ hai sẽ mang lại hiệu quả hơn. Phan Thị Hà
  111. Sắp xếp lựa chọn Lựa chọn phần tử có giá trị nhỏ nhất, đổi chỗ cho phần tử đầu tiên. Tiếp theo, lựa chọn phần tử có giá trị nhỏ thứ nhì, đổi chỗ cho phần tử thứ 2. Quá trình tiếp tục cho tới khi toàn bộ dãy được sắp. 7 bước Phan Thị Hà
  112. Sắp xếp lựa chọn void selection_sort(){ int i, j, k, temp; for (i = 0; i< N; i++){ k = i; for (j = i+1; j < N; j++){ if (a[j] < a[k]) k = j; } temp = a[i]; a[i] =a [k]; a[k] = temp; } }  Độ phức tạp trung bình của thuật toán là 2 2  O(N * N/2) = O(N /2) = O(N ). Phan Thị Hà
  113. Vd: 8,1,2,5,4,3  i=0:k=0=>k=1: 1,8,2,5,4,3  i=1;k=1=>k=2: 1,2,8,5,4,3  i=2;k=2=>k=3: 1,2,5,8,4,3 k=4: 1,2,4,8,5,3 k=5: 1,2,3,8,5,4  i=3; k=3=>k=4: 1,2,3,5,8,4 k=5: 1,2,3,4,8,5  i=4;k=4=>k=5: 1,2,3,4,5,8  i=5;k=5; Phan Thị Hà
  114. Sắp xếp chèn  Phần đầu là các phần tử đã đƣợc sắp. Từ phần tử tiếp theo, chèn nó vào vị trí thích hợp tại nửa đã sắp sao cho nó vẫn đƣợc sắp.  Để chèn phần tử vào nửa đã sắp, chỉ cần dịch chuyển các phần tử lớn hơn nó sang phải 1 vị trí và đƣa phần tử này vào vị trí trống trong dãy. Phan Thị Hà
  115. .8 bƣớc Phan Thị Hà
  116. Sắp xếp chèn void insertion_sort(){ int i, j, k, temp; for (i = 1; i temp)&&(j>=0)) { a[j+1]=a[j]; j ; } a[j+1]=temp; } }  Độ phức tạp trung bình của thuật toán là 2 2  O(N /4) = O(N ). Phan Thị Hà
  117. Vd: 8,1,2,3,4,5 i=1;j=0; 1,8,2,3,4,5 i=2; temp=2;j=1; 1,2,8,3,4,5 i=3; temp=3;j=2; 1,2,3,8,4,5 i=4; temp=4;j=3; 1,2,3,4,8,5 i=5; temp=5;j=4; 1,2,3,4,5,8 Phan Thị Hà
  118. Sắp xếp nổi bọt  Duyệt nhiều lần từ cuối lên đầu dãy, tiến hành đổi chỗ 2 phần tử liên tiếp nếu chúng ngƣợc thứ tự. Đến một bƣớc nào đó, khi không có phép đổi chỗ nào xảy ra thì toàn bộ dãy đã đƣợc sắp. Phan Thị Hà
  119. Phan Thị Hà
  120. Phan Thị Hà
  121. Sắp xếp nổi bọt  Thủ tục thực hiện sắp xếp nổi bọt trong C nhƣ sau: void bubble_sort(){ int i, j, temp, no_exchange; i = 1; do{ no_exchange = 1; for (j=n-1; j >= i; j ){ if (a[j-1] > a[j]){ temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; no_exchange = 0; } } i++; } until (no_exchange || (i == n-1)); }  Tổng cộng, số phép so sánh cần thực hiện là: (N-1) + (N-2) + + 2 + 1 = N(N-1)/2. Nhƣ vậy, độ phức tạp cũng giải thuật sắp xếp nổi bọt cũng là O(N2). Phan Thị Hà
  122. QUICK SORT  Ý tƣởng dựa trên phƣơng pháp chia để trị .  Giải thuật chia dãy cần sắp thành 2 phần, sau đó thực hiện việc sắp xếp cho mỗi phần độc lập với nhau.  Để thực hiện điều này, đầu tiên chọn ngẫu nhiên 1 phần tử nào đó của dãy làm khóa. Trong bƣớc tiếp theo, các phần tử nhỏ hơn khoá phải đƣợc xếp vào phía trƣớc khoá và các phần tử lớn hơn đƣợc xếp vào phía sau khoá. Để có đƣợc sự phân loại này, các phần tử sẽ đƣợc so sánh với khoá và hoán đổi vị trí cho nhau hoặc cho khoá nếu nó lớn hơn khóa mà lại nằm trƣớc hoặc nhỏ hơn khoá mà lại nằm sau. Khi lƣợt hoán đổi đầu tiên thực hiện xong thì dãy đƣợc chia thành 2 đoạn: 1 đoạn bao gồm các phần tử nhỏ hơn khoá, đoạn còn lại bao gồm các phần tử lớn hơn khoá. Phan Thị Hà
  123. Phan Thị Hà
  124. Phan Thị Hà
  125. QUICK SORT  Mã nguồn giải thuật: void quick(int left, int right) { int i,j; int x,y; i=left; j=right; x= a[left]; do { while(a[i] x && j>left) j ; if(i<=j){ y=a[i];a[i]=a[j];a[j]=y; i++;j ; } }while (i<=j); if (left<j) quick(left,j); if (i<right) quick(i,right); }  Hàm chính: void quick_sort(){ quick(0, n-1); } Phan Thị Hà
  126. QUICK SORT  Độ phức tạp tính toán:  Thời gian thực hiện thuật toán trong trƣờng hợp xấu nhất này là khoảng N2/2, có nghĩa là O(N2).  Trong trƣờng hợp tốt nhất, mỗi lần phân chia sẽ đƣợc 2 nửa dãy bằng nhau, khi đó thời gian thực hiện thuật toán T(N) sẽ đƣợc tính là:  T(N) = 2T(N/2) + N  Khi đó, T(N) ≈ NlogN.  Trong trƣờng hợp trung bình, thuật toán cũng có độ phức tạp khoảng 2NlogN = O(NlogN). Phan Thị Hà
  127. HEAP SORT  Heap sort là một giải thuật đảm bảo kể cả trong trƣờng hợp xấu nhất thì thời gian thực hiện thuật toán cũng chỉ là O(NlogN).  Ý tƣởng cơ bản của giải thuật này là thực hiện sắp xếp thông qua việc tạo các heap, trong đó heap là 1 cây nhị phân hoàn chỉnh có tính chất là khóa ở nút cha bao giờ cũng lớn hơn khóa ở các nút con. Việc thực hiện giải thuật này đƣợc chia làm 2 giai đoạn.  GĐ1: Tạo heap từ dãy ban đầu. Theo định nghĩa của heap thì nút cha bao giờ cũng lớn hơn các nút con=> nút gốc của heap bao giờ cũng là phần tử lớn nhất.  GĐ2 : Sắp dãy dựa trên heap tạo đƣợc. Do nút gốc là nút lớn nhất nên nó sẽ đƣợc chuyển về vị trí cuối cùng của dãy và phần tử cuối cùng sẽ đƣợc thay vào gốc của heap. Khi đó ta có 1 cây mới, không phải heap, với số nút đƣợc bớt đi 1. Lại chuyển cây này về heap và lặp lại quá trình cho tới khi heap chỉ còn 1 nút. Đó chính là phần tử bé nhất của dãy và đƣợc đặt lên đầu. Phan Thị Hà
  128.  Với heap ban đầu chỉ có 1 phần tử là phần tử đầu tiên của dãy, ta lần lƣợt lấy các phần tử tiếp theo của dãy chèn vào heap sẽ tạo đƣợc 1 heap gồm toàn bộ n phần tử. Phan Thị Hà
  129. Phan Thị Hà
  130. Phan Thị Hà
  131. Chèn một phần tử x vào 1 heap đã có k phần tử, ta gán phần tử thứ k +1, a[k], bằng x, rồi gọi thủ tục upheap(k).  void upheap(int m){  int x;  x=a[m];  while ((a[(m-1)/2] 0)){  a[m]=a[(m-1)/2];  m=(m-1)/2;  }  a[m]=x;  }   void insert_heap(int x){  a[m]=x;  upheap(m);  m++; Phan Thị Hà  }
  132.  Ta có thủ tục downheap để chỉnh lại heap khi nút k không thoả mãn định nghĩa heap :   void downheap(int k){  int j, x;  x=a[k];  while (k =a[j]) break;  a[k]=a[j]; k=j;  }  a[k]=x; Phan Thị Hà  }
  133.  Cuối cùng, thủ tục heap sort thực hiện việc sắp xếp trên heap đã tạo nhƣ sau:  int remove_node(){  int temp;  temp=a[0];  a[0]=a[m];  m ;  downheap(0);  return temp;  }  void heap_sort(){  int i;  m=0;  for (i=0; i =0; i ) a[i]=remove_node();  } Phan Thị Hà
  134. MERGE SORT  Thủ tục tiến hành trộn 2 dãy đã sắp nhƣ sau: void merge(int *a, int al, int am, int ar){ int i=al, j=am+1, k; for (k=al; k am){ c[k]=a[j++]; continue; } if (j>ar){ c[k]=a[i++]; continue; } if (a[i]<a[j]) c[k]=a[i++]; else c[k]=a[j++]; } for (k=al; k<=ar; k++) a[k]=c[k]; } Phan Thị Hà
  135. MERGE SORT  Cài đặt cho thuật toán merge_sort bằng đệ qui nhƣ sau : void merge_sort(int *a, int left, int right){ int middle; if (right<=left) return; middle=(right+left)/2; merge_sort(a, left, middle); merge_sort(a, middle+1, right); merge(a, left, middle ,right); } Phan Thị Hà
  136. Bài toán tìm kiếm  Khái niệm  Tìm kiếm có thể định nghĩa là việc thu thập một số thông tin nào đó từ một khối thông tin lớn đã đƣợc lƣu trữ trƣớc đó. Thông tin khi lƣu trữ thƣờng đƣợc chia thành các bản ghi, mỗi bản ghi có một giá trị khoá để phục vụ cho mục đích tìm kiếm.  Mục tiêu của việc tìm kiếm là tìm tất cả các bản ghi có giá trị khoá trùng với một giá trị cho trƣớc. Khi tìm đƣợc bản ghi này, các thông tin đi kèm trong bản ghi sẽ đƣợc thu thập và xử lý.  Ví dụ:  Từ điển máy tính Phan Thị Hà
  137. Tìm kiếm tuần tự  Thủ tục tìm kiếm tuần tự trên một mảng các số nguyên nhƣ sau: int sequential_search(int *a, int x, int n){ int i; for (i=0; i<n ; i ++){ if (a[i] == X) return(i); } return(-1); }  Thuật toán tìm kiếm tuần tự có thời gian thực hiện là O(n). Trong trƣờng hợp xấu nhất, thuật toán mất n lần thực hiện so sánh và mất khoảng n/2 lần so sánh trong trƣờng hợp trung bình. Phan Thị Hà
  138. Tìm kiếm nhị phân  Hàm tìm kiếm nhị phân đƣợc cài đặt nhƣ sau (giả sử dãy a đã đƣợc sắp): int binary_search(int *a, int x){ int k, left =0, right=n-1; do{ k=(left+right)/2; if (x<a[k]) right=k-1; else l=k+1; }while ((x!=a[k]) && (left<=right)) if (x=a[k]) return k; else return -1; }  Thuật toán tìm kiếm nhị phân có thời gian thực hiện là lgN. Phan Thị Hà
  139. Tìm kiếm trên cây nhị phân tìm kiếm  Mã nguồn: struct node { int item; struct node *left; struct node *right; } typedef struct node *treenode; treenode tree_search(int x, treenode root){ int found=0; treenode temp=root; while (temp!=NULL){ if (x temp.item)temp=temp.right; else break; } return temp; } Phan Thị Hà
  140.  Các nhóm tự tìm hiểu về cây AVL và làm báo cáo Phan Thị Hà