intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu 2

Chia sẻ: Trịnh Thị Hiền | Ngày: | Loại File: DOC | Số trang:59

Thêm vào BST
Báo xấu
54
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với kết cấu nội dung gồm 7 bài, bài giảng "Cấu trúc dữ liệu 2" trình bày những nội dung về bảng băm, cấu trúc cây và cây nhị phân, cây nhị phân tìm kiếm, cây nhị phân cân bằng, cây đỏ đen,... Với các bạn đang học chuyên ngành Công nghệ thông tin thì đây là tài liệu tham khảo hữu ích.

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 2

  1. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  Bài 1: Bảng băm Số tiết : 4 Nội dung 1.1) Bảng băm  1.2) Định nghĩa hàm băm  1.3) Một số phương pháp xây dựng hàm băm 1.4) Các phương pháp giải quyết đụng độ Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá (Key) của phần tử  cần tìm với các giá trị khoá trong tập các phần tử, thao tác này  Phụ thuộc kích thước của tập các phần tử Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể  không cần thiết ( O(n), O(logn), …) => Có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn  không ( độ phức tạp hằng số)? 1.1) Bảng băm (Hash Table) Ví dụ: Giả sử ta có một tập phần tử gồm các giá trị  khoá bất kỳ được tổ  chức lưu   trữ  dưới dạng bảng chỉ  mục m phần tử  như  sau gọi là bảng truy xuất trực tiếp   (Direct access table) Phần tử  có giá trị  khoá k được  lưu trữ tương ứng tại vị trí thứ k  trong bảng chỉ mục  Để tìm kiếm một phần tử nào đó  ta sẽ  dựa vào khoá của nó và tra  trong bảng chỉ mục, nếu tại vị trí  đó có phần tử  thì chính là phần  tử  cần tìm, nếu không có phần  tử  nào có nghĩa là phần tử  cần  tìm không có trong bảng chỉ mục Thời   gian   tìm   kiếm   là   hằng  số  Hình 1.1 O(1)  Đây là dạng bảng băm cơ bản a. Mô tả dữ liệu Giả sử  K: tập các khoá (set of keys) Hàm băm HF(k) A: tập các địa chỉ (set of addresses). PMT ­=Trang 1=­ Tập khóa K Tập địa chỉ  Hình 1.2 A
  2. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  HF(k):  hàm băm dùng để  ánh xạ  một khoá k từ  tập các khoá K thành một  địa chỉ tương ứng trong tập A.  b. Các phép toán trên bảng băm Khởi tạo (Initialize) Kiểm tra rỗng (Empty) Lấy kích thước của bảng băm (Size) Tìm kiếm (Search) Thêm mới phần tử (Insert) Loại bỏ (Remove) Sao chép (Copy) Duyệt (Traverse) c. Phân loại bảng băm Bảng băm đóng : mỗi khóa  ứng với một địa chỉ, thời gian truy xuất là hằng   số  Bảng băm mở : một số khóa có cùng địa chỉ, lúc này mỗi mục địa chỉ  sẽ  là   một danh sách liên kết các phần tử có cùng địa chỉ, thời gian truy xuất có thể  bị suy giảm đôi chút 1.2) Định nghĩa hàm băm Là hàm biến đổi giá trị khoá (số, chuỗi…) thành địa chỉ, chỉ mục trong bảng băm Giá trị khoá Hàm băm Địa chỉ, chỉ mục Ví dụ : hàm băm biến đổi khoá dạng chuỗi gồm n kí tự thành 1 địa chỉ (số nguyên) int hashfunc( char *s, int n ) { int sum = 0; while( n-- ) sum = sum + *s++; return sum % 256; } Tính địa chỉ của khoá “AB” : hashfunc(“AB”,2)  131 Tính địa chỉ của khoá “BA” : hashfunc(“BA”,2)  131  Khi hàm băm 2 khoá vào cùng 1 địa chỉ thì gọi là đụng độ (Collision)  Hàm băm tốt thỏa mãn các điều kiện sau: Tính toán nhanh. Các khoá được phân bố đều trong bảng. Ít xảy ra đụng độ . 1.3) Một số phương pháp xây dựng hàm băm a. Hàm băm dạng bảng tra: PMT ­=Trang 2=­
  3. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  Hàm băm có thể  tổ  chức  ở  dạng bảng tra (còn gọi là bảng truy xuất) hoặc   thông dụng nhất là ở dạng công thức. Ví dụ sau đây là bảng tra với khóa là bộ chữ cái, bảng băm có 26 địa chỉ từ 0   đến 25. Khóa a ứng với địa chỉ 0, khoá b ứng với địa chỉ 1,… , z ứng với địa   chỉ 25. Khoá Địa chỉ Khóa Địa chỉ Khóa Địa chỉ Khóa Địa chỉ a 0 h 7 o 14 v 21 b 1 I 8 p 15 w 22 c 2 j 9 q 16 x 23 d 3 k 10 r 17 y 24 e 4 l 11 s 18 z 25 f 5 m 12 t 19 / / g 6 n 13 u 20 / / Hình 1.3 Hàm băm dạng bảng tra được tổ chức dưới dạng danh sách kề. b. Hàm băm sử dụng phương pháp chia Dùng số dư: h(k) = k mod m k là khoá, m là kích thước của bảng.  vấn đề chọn giá trị m Nếu chọn m= 2n thông thường không tốt vì h(k) = k mod 2n  sẽ  chọn cùng n  bits thấp của k  nên chọn m là nguyên tố (tốt) gần với 2n Ví dụ: Ta có tập khoá là các giá trị  số gồm 3 chữ số, và vùng nhớ  cho bảng   địa chỉ có khoảng 100 mục, như  vậy ta sẽ lấy hai số cuối của khoá để  làm địa   chỉ theo phép chia lấy dư cho 100 : chẳng hạn 325 Mod 100 = 25 Tuy nhiên ta nhận thấy nếu hàm băm dùng công thức như trên thì địa chỉ của   khoá tính được chỉ căn cứ và 2 ký số cuối. Vì thế, để hàm băm có thể tính địa chỉ  khoá một cách “ngẫu nhiên” hơn ta nên chọn m=97 thay vì 100 M=100 M=97 (nguyên tố) Khoá Địa chỉ Khoá Địa chỉ 325 25 325 34 125 25 125 28 147 47 147 50   PMT ­=Trang 3=­
  4. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  c. Hàm băm sử dụng phương pháp nhân Sử dụng công thức h(k) = floor(m (k A mod 1))  k là khóa, m là kích thước bảng, A là hằng số: 0 
  5. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)   d. Dùng hàm  băm ph   ổ quát  Một tập các hàm băm H là phổ quát (universal ) nếu  h H và 2 khoá k, l ta có xác  suất: Pr{h(k) = h(l)} 
  6. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  struct nodes { int key; struct nodes *next }; //khai bao kieu con tro chi nut typedef struct nodes *NODEPTR; /* khai bao mang bucket chua M con tro dau cua M bucket  */ NODEPTR bucket[M]; b.Các phép toán: Hàm băm Giả sử chúng ta chọn hàm băm dạng %: f(key)=key % M. int hashfunc (int key) { return (key % M); } Phép toán initbuckets: void initbuckets( ) { int b; for (b=0;b
  7. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  { int b; NODEPTR q, p; b = hashfunc(k); p = hashbucket(k); q=p; while(p !=NULL && p->key !=k) { q=p; p=p->next; } if (p == NULL) printf("\n khong co nut co khoa %d" ,k); else if (p == bucket [b]) pop(b); //Tac vu pop cua danh sach lien ket else delafter(q); /*tac vu delafter cua danh sach lien ket*/ } Phép toán clearbucket: Xóa tất cả các phần tử trong bucket b. void clearbucket (int b) { NODEPTR p,q; //q la nut truoc,p la nut sau q = NULL; p = bucket[b]; while(p !=NULL) { q = p; p=p->next; freenode(q); } bucket[b] = NULL; //khoi dong lai butket b } Phép toán clear: Xóa tất cả các phần tử trong bảng băm. void clear( ) { int b; for (b = 0; bkey); p= p->next; } PMT ­=Trang 7=­
  8. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  } Phép toán traverse: Duyệt toàn bộ bảng băm. void traverse( ) { int b; for (b = 0;n p->key && p !=NULL) p=p->next; if (p == NULL | | k !=p->key)// khong tim thay return(NULL); else//tim thay // else //tim thay return(p); } Giải quyết sự đụng độ bằng phương pháp băm lại: Phương pháp dò tuyến tính (Linear Probe) Nếu băm lần đầu bị xung đột thì băm lại lần 1,  nếu bị  xung đột nữa thì băm lai lần 2,… Quá  trình   băm   lại  diễn   ra   cho   đến  khi   không  còn   xung   đột   nữa.   Các   phép   băm   lại   (rehash  function) thường sẽ  chọn địa chỉ  khác cho các  phần tử. hi(key)=(h(key)+i) %M với h(key) là hàm băm  chính của bảng băm Cài đặt bảng băm dùng phương pháp dò tuyến tính: a. Khai báo cấu trúc bảng băm: #define NULLKEY –1 #define M 100 /* M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam */ PMT ­=Trang 8=­
  9. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  //khai bao cau truc mot nnut cua bang bam struct node { int key; //khoa cua nut tren bang bam }; //Khai bao bang bam co M nut struct node hashtable[M]; int NODEPTR; /*bien toan cuc chi so nut hien co tren bang bam*/ PMT ­=Trang 9=­
  10. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  b. Các tác vụ: Hàm băm: int hashfunc(int key) { return(key% M) } Phép toán khởi tạo (initialize): Khởi tạo bảng băm. Gán biến toàn cục N=0. void initialize( ) { int i; for(i=0;i=M) i=i-M; } if(hashtable[i].key==k) //tim thay return(i); else //khong tim thay return(M); } Phép toán insert: PMT ­=Trang 10=­
  11. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  Thêm phần tử có khoá k vào bảng băm. int insert(int k) { int i, j; if(full( )) { printf("\n Bang bam bi day khong them nut co khoa %d duoc",k); return; } i=hashfunc(k); while(hashtable[i].key !=NULLKEY) { //Bam lai (theo phuong phap do tuyen tinh) i ++; if(i >M) i= i-M; } hashtable[i].key=k; N=N+1; return(i); } Bảng băm với phương pháp dò bậc hai (Quadratic Probing Method) ­ Hàm băm lại của phương pháp dò bậc hai là truy xuất các địa chỉ cách bậc 2. Hàm  băm lại hàm i được biểu diễn bằng công thức sau: hi(key)=( h(key) + i2 ) % M với h(key) là hàm băm chính của bảng băm. Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng. Bảng băm với phương pháp do bậc hai nên chọn số địa chỉ M là số nguyên tố. Cài đặt bảng băm dùng phương pháp dò bậc hai: a. Khai báo cấu trúc bảng băm: #define NULLKEY –1 #define M 101 /* M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam,chon M la so  nguyen to */ //Khai bao nut cua bang bam struct node { int key; //Khoa cua nut tren bang bam }; //Khai bao bang bam co M nut struct node hashtable[M]; int N; //Bien toan cuc chi so nut hien co tren bang bam b. Các tác vụ : Hàm băm: Giả sử chúng ta chọn hàm băm dạng%: f(key)=key %10. PMT ­=Trang 11=­
  12. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  int hashfunc(int key) { return(key% 10); } Phép toán initialize Khởi động hàm băm. Gán biến toàn cục N=0. void initialize() { int i; for(i=0; i
  13. Bài giảng Cấu trúc dữ liệu 2 Bài 1 : Bảng băm (Hash Table)  Tóm tắt Từ khoá Bảng băm (Hash Table) : là bảng cho phép thực hiện tìm kiếm các phần tử  với thời gian O(1) thông qua một hàm tính địa chỉ gọi là hàm băm Hàm băm (Hash Function) : là hàm chuyển đổi giá trị  khoá thành địa chỉ hay  chỉ mục trong bảng băm Sự  đụng độ (Collision) : xảy ra khi hàm băm 2 khoá khác nhau vào cùng 1   địa chỉ trên bảng băm Dò   tuyến   tính   (Linear   Probing   Method):  là   một   phương   pháp   băm   lại  (Rehash), để chọn một địa chỉ kế tiếp trong bảng băm khi xảy ra đụng độ về  địa chỉ, bằng cách cộng thêm một đơn vị  Dò bậc hai (Quadratic Probing Method) :là một phương pháp băm lại để  chọn một địa chỉ kế tiếp trong bảng băm khi xảy ra đụng độ về địa chỉ bằng   cách cộng thêm i2 đơn vị vào địa chỉ Phương pháp băm kép (Double hashing Method): là một phương pháp băm  lại dùng cùng lúc hai hàm băm PMT ­=Trang 13=­
  14. Bài giảng Cấu trúc dữ liệu 2 Bài 2 : Cấu trúc cây và cây nhị phân  Bài 2: Cấu trúc cây và cây nhị phân Số tiết : 4  Nội dung 2.1) Cấu trúc cây a) Một số ví dụ và định nghĩa cây b) Các thuật ngữ liên quan 2.2) Cây nhị phân  a) Định nghĩa cây nhị phân b) Tổ chức lưu trữ c) Các phương pháp duyệt cây 2.1) Một số ví dụ và định nghĩa cấu trúc cây a)   Một số ví dụ và định nghĩa cây Cây là một cấu trúc phân cấp trên một tập hợp các đối tượng nào đó, cấu trúc cây  có nhiều ứng dụng trong thực tế và tin học Ví dụ 1: cấu trúc cây thư mục trong Windows Ví dụ 2 : Cây gia phả của một dòng họ Ví dụ 3 : Cây biểu thức (a­b)*(c/d) PMT ­=Trang 14=­
  15. Bài giảng Cấu trúc dữ liệu 2 Bài 2 : Cấu trúc cây và cây nhị phân    Định nghĩa cấu trúc cây Một cây  (Tree) là: Một tập các phần tử, gọi là các nút (Node): p1,p2,…,pN Nếu N=0, cây  gọi là cây rỗng (NULL) Nếu N>0: o Tồn tại duy nhất 1 nút pk gọi là gốc của cây o Các nút còn lại được chia thành m tập không giao nhau: T1, T2, …, Tm o Mỗi  là 1 cây con của cây    Các tính chất của cây: Nút gốc không có nút cha Mỗi nút khác chỉ có 1 nút cha Mỗi nút có thể có nhiều nút con Không có chu trình b)   Một số thuật ngữ liên quan Nút (Node): là 1 phần tử trong cây. Mỗi nút có thể chứa 1 dữ liệu bất kỳ Nhánh (Branch): là đoạn nối giữa 2 nút Nút cha (Parent node) Nút con (Child node) Nút anh em (Sibling nodes): là những nút có cùng nút cha Bậc của 1 nút pi: là số nút con của pi Ví dụ trên : Bậc (a) = 4; Bậc (j) = 3; Bậc (g) = 2;   Bậc (k) = 1; Bậc (c) = 0 Nút gốc (Root node): nút không có nút cha Nút lá (Leaf node, hay nút ngoài – External node): là nút có bậc = 0 (không có  nút con) Nút nội (Internal node): là nút có nút cha và có nút con Cây con (Subtree) Bậc của cây: là bậc lớn nhất của các nút trong cây PMT ­=Trang 15=­
  16. Bài giảng Cấu trúc dữ liệu 2 Bài 2 : Cấu trúc cây và cây nhị phân  o Bậc () = max {bậc (pi) / pi   } o Bậc của cây  ? Đường đi (Path) giữa nút pi đến nút pj: là dãy các nút liên tiếp từ pi đến pj  sao cho giữa hai nút kề nhau đều có nhánh o Path(a, d) ? Mức (Level): o Mức (p) = 0 nếu p = root o Mức (p) = 1 + Mức (Cha (p)) nếu p!=root Chiều cao của cây (Height ­ hT): đường đi dài nhất từ nút gốc đến nút lá o hT = max {Path(root, pi) / pi là nút lá   } Cây hoàn chỉnh (Complete tree) với h mức: là 1 cây thoả các điều kiện o Những nút từ mức 0 đến mức h­1 đều đầy đủ o Những nút ở mức h được thêm vào cây từ trái sang phải Cây đầy đủ (Full tree): là 1 cây thoả o Tất cả các nút lá đều nằm trên cùng 1 mức o Tất cả những nút khác có cùng bậc với cây Mức h của cây đầy đủ bậc d có dh nút PMT ­=Trang 16=­
  17. Bài giảng Cấu trúc dữ liệu 2 Bài 2 : Cấu trúc cây và cây nhị phân  o VD. mức h=2 của cây bậc 3 có bao nhiêu nút ? h mức đầu tiên của cây đầy đủ bậc d có số nút là: o 1 + d + d2 + d3 + … + dh­1 = (dh ­ 1)/(d – 1) o 3 mức đầu tiên của cây đầy đủ bậc 3 có bao nhiêu nút ? 2.2) Cây nhị phân a)   Định nghĩa cây nhị phân Cây nhị phân là cây có bậc = 2 Độ cao của cây nhị phân có N nút:  hT(max) = N  hT(min) = [logN] + 1 b)   Tổ chức lưu trữ  Dùng mảng Định nghĩa các cấu trúc dữ liệu typedef struct tagBT_NODE  { int Data; int Left; // chỉ số nút con trái int Right; // chỉ số nút con phải } BT_NODE; // cấu trúc 1 node // cây nhị phân có N nút  BT_NODE tree[N];   Dùng con trỏ Định nghĩa các cấu trúc dữ liệu typedef struct tagBT_NODE  { int Data; tagBT_NODE *pLeft; // con trỏ đến nút con trái tagBT_NODE *pRight; // con trỏ đến nút con phải } BT_NODE; // binary tree node PMT ­=Trang 17=­
  18. Bài giảng Cấu trúc dữ liệu 2 Bài 2 : Cấu trúc cây và cây nhị phân  typedef struct BIN_TREE  { int Count; // Số nút trong cây BT_NODE *pRoot; // con trỏ đến nút gốc }; // binary tree c)   Các thao tác duyệt cây Có 3 cách duyệt cây: Duyệt gốc trước (Pre­Order) NLR Duyệt gốc giữa (In­Order) LNR Duyệt gốc sau (Post­Order) LRN Duyệt gốc trước (Pre­Order) NLR void NLR(const BT_NODE*pCurr) { if (pCurr==NULL) return; “Xử lý nút gốc pCurr” NLR(pCurr­>pLeft); NLR(pCurr­>pRight); }  PMT ­=Trang 18=­
  19. Bài giảng Cấu trúc dữ liệu 2 Bài 2 : Cấu trúc cây và cây nhị phân  Duyệt gốc giữa (In­Order) LNR void LNR(const BT_NODE*pCurr) { if (pCurr==NULL) return; LNR(pCurr­>pLeft); “Xử lý nút gốc pCurr” LNR(pCurr­>pRight); }  Duyệt gốc sau (Post­Order) LRN void LRN(const BT_NODE*pCurr) { if (pCurr==NULL) return; LRN(pCurr­>pLeft); LRN(pCurr­>pRight); “Xử lý nút gốc pCurr” }    PMT ­=Trang 19=­
  20. Bài giảng Cấu trúc dữ liệu 2 Bài 3 : Cây nhị phân tìm kiếm  Bài 3: Cây nhị phân tìm kiếm Số tiết : 4  Nội dung 3.1) Cây nhị phân tìm kiếm a) Định nghĩa  b) Tổ chức lưu trữ  3.2) Các thao tác trên cây nhị phân tìm kiếm a) Khởi tạo cây b) Kiểm tra cây rỗng c) Tìm kiếm phần tử d) Thêm phần tử e) Xoá phần tử 3.1) Cây nhị phân tìm kiếm (BST_Binary Search Tree) a)   Định nghĩa Cây nhị phân tìm kiếm là: Một cây nhị phân Mỗi nút p của cây đều thỏa: o Tất cả các nút thuộc cây con trái (p­>pLeft) đều có giá trị nhỏ hơn giá  trị của p:  q   p­>pLeft: q­>Data Data o Tất cả các nút thuộc cây con phải (p­>pRight) đều có giá trị lớn hơn  giá trị của p :  q   p­>pRight: q­>Data > p­>Data Ví dụ: một số cây nhị phân tìm kếm b)   Tổ chức lưu trữ Cách thức tổ chức lưu trữ cây nhị phân tìm kiếm tương tự cây nhị phân Tham khảo phần cài đặt cấu trúc cây nhị phân PMT ­=Trang 20=­
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2