TimTaiLieu.vn - Tài liệu, ebook, giáo trình, đồ án, luận văn

Duyệt cây là một qui tắc cho phép đi qua lần lượt tất cả các nút của cây mỗi nút đúng một lần, danh sách liệt kê các nút (tên nút hoặc giá trị chứa bên trong nút) theo thứ tự đi qua gọi là danh sách duyệt cây. Có 3 cách duyệt cây quan trọng: Duyệt tiền tựû (preorder), duyệt trung tựû (inorder), duyệt hậu tự (posorder). Có thể định nghĩa các phép du...

15 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2368 | Lượt tải: 2

c. Phân tích thuật toán: - Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X: Số phép gán: Gmin = 1 Số phép so sánh: Smin = 2 + 1 = 3 - Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X: Số phép gán: Gmax = 1 Số phép so sánh: Smax = 2N+1 - Trung bình: Số phép gán: Gavg = 1 Số phép so sánh: Savg ...

29 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2372 | Lượt tải: 0

Bài toán: Nhân 2 ma trận vuông cùng cấp nxn C=A x B PP vẫn làm O(n3) Tiếp cận theo chia để trị: xem như nhân 2 x 2 2 mà mỗi phần tử của nó là một ma trận n/2 x n/2 để xác định được ma trận C ta phải mất 8 phép nhân ma trận n/2 x n/2, và 4 phép cộng

36 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2424 | Lượt tải: 1

Ngăn xếp đầy không liên quan đến cấu trúc dữ liệu (về mặt lý thuyết là kô có giới hạn) Bd bằng mảng → kô chính xác

34 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2923 | Lượt tải: 0

Nguyên tắc (playing card): 1 khóa luôn được sắp, xét thêm s2, so sánh với s1 để xác định chỗ để chèn s2 vào. Tương tự như đối với s3, s4, s5,.v.v. cuối cùng sau khi xét xong sn ta được dãy được sắp. Tìm vị trí để chèn phần tử Dịch chuyển các phần tử khác

52 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2385 | Lượt tải: 0

Một cây M - đường T là tập hữu hạn khóa hoặc là rỗng hoặc là tập của n cây con M-đường T0, T1, ., Tn-1 và n-1 khóa k1, k2, ., kn-1, với 2  n  M sao cho các khóa và các nút thỏa mãn tính chất sau: Các khóa trên mỗi nút khác nhau và được sắp: ki < ki+1 với 1  i  n-1 Tất cả các khóa trên cây con Ti-1 đều nhỏ hơn ki: kTi-1: k < ki với 1  i ...

27 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2066 | Lượt tải: 0

While p<> nil do Begin Attach(p^.Coef, p^.Exp, d); p:=p^.Link; End While q<> nil do Begin Attach(q^.Coef, q^.Exp, d); q:=q^.Link; End d^.link:=nil; T:=c; c:=c^.link; dispose(T); End {of procedure}

8 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2053 | Lượt tải: 0

Điều kiện để một danh sách liên kết rỗng là head = null Danh sách liên kết chỉ đầy khi không còn không gian nhớ để cấp phát cho các thành phần mới của danh sách. giả thiết điều này không xảy ra -> insert luôn luôn thực hiện được

31 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 2448 | Lượt tải: 0

b) Xoá một phần tử của mảng void Delete_Arr(*a:m, int p, int t); //p: vị trí của phần tử cần xoá; t: tổng số phần tử hiện có trong mảng { int i; for (i=p; i<=t-1; i++) a[i]=a[i+1]; t=t-1; }

9 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 1988 | Lượt tải: 0

Một thủ tục đệ qui gồm có hai phần chính Phần cố định (neo): gía trị khởi đầu cho hàm, thủ tục đệ qui. Phần hạ bậc (phần đệ qui): Tác động của hàm đệ qui được thực hiện thông qua tác động hay giá trị đã được định nghĩa trước. Phân tích giải thuật đệ qui tính giai thừa: f(3)->f(2)->f(1)->f(0)->1 -> như vậy để tính 3! Hàm f được gọi 4 lần. Ph...

15 trang | Chia sẻ: haohao89 | Ngày: 03/07/2013 | Lượt xem: 3230 | Lượt tải: 0