- Chương 1: Giới thiệu cấu trúc dữ liệu và thuật tốn. - Chương2: Tìm kiếm và sắp xếp. - Bài thực hành số 3: Các phương pháp sắp xếp. - Ơn lại kiểu dữ liệu cĩ cấu trúc (kiểu định nghĩa bằng từ khĩa struct). - Kiểu dữ liệu số char – c. - Kiểu dữ liệu luận lý. - Kiểu dữ liệu mảng. - Kiểu dữ liệu chuỗi. - Kiểu dữ liệu con trỏ. - Chương 2: TÌM KIẾM VÀ SẮP XẾP. - So sánh x lần lượt với phần tử thứ 1, thứ 2,…của dãy a cho đến khi gặp phần tử cĩ khĩa cần tìm, hoặc đã tìm hết dãy mà khơng thấy x.. - bắt đầu từ phần tử đầu tiên của dãy Bước 2: So sánh a[i] với x.. - xét tiếp phần tử kế trong dãy Nếu i ≤ N : lặp lại Bước 2.. - Đặt một phần tử cĩ giá trị x vào cuối dãy, gọi đây là phần tử “lính canh”.. - phần tử “lính canh”. - Đối với những dãy số đã cĩ thứ tự (tăng dần), các phần tử đã cĩ quan hệ a i-1 ≤ a i ≤ a i+1 . - Giải thuật áp dụng nhận xét trên để giới hạn phạm vi tìm kiếm 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, so sánh x với phần tử nằm giữa dãy tìm kiếm hiện hành, dựa vào kết quả so sánh để quyết định giới hạn của 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 hiện hành.. - tìm kiếm trên tất cả các phần tử Bước 2: mid = (left + right)/2. - cịn phần tử chưa xét Ngược lại: Khơng tìm thấy x trong dãy. - a) Phần tử lớn nhất (hay nhỏ nhất).. - c) Tìm phần tử đầu tiên trên dãy mà thỏa một tính chất TC nào đĩ.. - d) Dãy con (là một dãy các phần tử liên tiếp của dãy) tăng dài nhất trong một dãy các phần tử cho trước được cài đặt bằng mảng.. - BÀI THỰC HÀNH SỐ 3 Các phương pháp sắp xếp. - Xét một dãy a gồm N phần tử. - Cần sắp xếp các phần tử của dãy để thu được một dãy cĩ thứ tự (ví dụ tăng dần/giảm dần theo một khĩa được chỉ định). - PHƯƠNG PHÁP SẮP XẾP CHỌN Ý tưởng:. - Chọn phần tử nhỏ nhất x trong N phần tử ban đầu, đảo vị trí của x với phần tử đầu dãy để đưa x về đầu dãy.. - Ta khơng quan tâm đến phần tử đầu dãy nữa, xem dãy bây giờ chỉ cịn N-1 phần tử, bắt đầu từ vị trí thứ 2.. - Lặp lại xử lí trên cho đến khi dãy hiện hành chỉ cịn một phần tử.. - Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy a[i..N].. - N-1 phần tử đã nằm đúng vị trí.. - a n , trong đĩ i-1 phần tử đầu tiên a 1 , a 2 ,…,a n đã cĩ thứ tự. - trí thích hợp để chèn phần tử a i vào vị trí thích hợp trong i-1 phần tử đã sắp để cĩ dãy mới a 1 , a 2 ,…,a i trở nên cĩ thứ tự. - Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i].. - Phân chia dãy ban đầu thành những dãy con gồm các phần tử cách nhau h vị trí.. - Sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối (so với tồn bộ các phần tử trong dãy ban đầu cĩ thể chưa đúng). - Thuật tốn dừng khi h = 1, lúc này bảo đảm tất cả các phần tử trong dãy ban đầu đã được so sánh với nhau để xác định trật tự đúng cuối cùng.. - Xét dãy gồm N phần tử. - Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đĩ về vị trí đầu dãy hiện hành.. - Lặp lại xử lí trên cho đến khi khơng cịn cặp phần tử nào để xét.. - xét cặp phần tử kế cận j = j - 1;. - ο Lượt đi: đẩy phần tử nhỏ về đầu mảng ο Lượt về: đẩy phần tử lớn về cuối mảng. - đẩy phần tử nhỏ về đầu mảng Trong khi (j >. - loại các phần tử đã cĩ thứ tự ở đầu dãy Bước 2b: j = l. - đẩy phần tử lớn về cuối mảng Trong khi (j <. - loại các phần tử đã cĩ thứ tự ở cuối dãy Bước 3: Nếu l <. - Cài đặt các phương pháp sắp xếp trên.. - BÀI THỰC HÀNH SỐ 4 Các phương pháp sắp xếp (tt). - Chọn x là giá trị của một phần tử tùy ý trong dãy ban đầu. - Vị trí phần tử thường được chọn là k = (l + r)/2.. - Nếu dãy con 1 và 3 chỉ cĩ một phần tử thì chúng đã cĩ thứ tự, ngược lại, ta lần lượt tiến hành phân hoạch từng dãy con theo phương pháp phân hoạch như trên.. - Bước 1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, l ≤ k ≤ r Bước 2: Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ:. - dãy con 1 cĩ nhiều hơn một phần tử Phân hoạch dãy a 1 ..a j. - dãy con 3 cĩ nhiều hơn một phần tử Phân hoạch dãy a i ..a r. - Đảo vị trí của phần tử đầu dãy với phần tử cuối dãy để đưa phần tử lớn nhất về cuối dãy.. - Ta khơng quan tâm đến phần tử cuối dãy nữa, xem như dãy hiện hành chỉ gồm N-1 phần tử, tính từ 1.. - Bước 1: Đưa phần tử lớn nhất về vị trí đúng ở cuối dãy:. - Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r – 1;. - a n , lần lượt thêm vào các phần tử a n/2 , a n/2-1. - a n thành 2 dãy b, c theo nguyên tắc luân phiên từng nhĩm k phần tử:. - Bước 3: Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a.. - Nĩ khơng quan tâm đến việc so sánh giá trị của phần tử và bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử.. - Trước tiên, ta giả sử mỗi phần tử a i trong dãy a 1 , a 2. - Phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm…. - Tạo các lơ chứa các loại phần tử khác nhau.. - Cài đặt các phương pháp sắp xếp trên. - Áp dụng Các phương pháp Sắp xếp và Tìm Kiếm (4 tiết). - Sắp xếp. - a) Khai báo cấu trúc dữ liệu phù hợp.. - CẤU TRÚC DỮ LIỆU CỦA DANH SÁCH LIÊN KẾT. - //Trường dữ liệu. - b) Thêm một phần tử vào danh sách (chèn đầu, chèn cuối, chèn vào sau một nút).. - d) Tìm một phần tử trên danh sách.. - e) Xĩa phần tử khỏi danh sách.. - f) Sắp xếp trên danh sách.. - Sắp xếp danh sách.. - a) Khai báo cấu trúc dữ liệu phù hợp cho danh sách liên kết.. - b) Xĩa đi tất cả các phần tử trùng nhau (giữ lại một phần tử trong số đĩ, phần tử nào cũng được).. - e) Thực hiện lần lượt thêm vào danh sách m phần tử sao cho phần tử được thêm vào vị trí sao cho nhỏ hơn hoặc bằng phần tử trước nĩ và lớn hơn hoặc bằng phần tử sau nĩ. - Như vậy, phần tử nào thêm vào sau sẽ bị loại bỏ trước, nên ngăn xếp cịn được gọi là danh sách LIFO ( Last In First Out list) hoặc Pushdown list.. - Cấu trúc dữ liệu của Stack. - a) Thao tác Push đẩy một mục dữ liệu x vào đỉnh ngăn xếp b) Thao tác Pop lấy ra một phần tử ở đỉnh ngăn xếp. - c) Thao tác Top xem một phần tử ở đỉnh ngăn xếp 2. - Như vậy, phần tử nào vào trước sẽ được loại bỏ trước, phần tử nào vào sau sẽ được loại bỏ sau, nên hàng đợi cịn được gọi là danh sách FIFO (First In First Out list).. - Cấu trúc dữ liệu. - Trả về trị của phần tử ở đầu hàng đợi mà khơng loại nĩ khỏi hàng đợi, nếu hàng đợi rỗng sẽ gặp lỗi.. - Dấu * tượng trưng cho thao tác lấy nội dung một phần tử ra khỏi stack/queue.. - Thực hiện chuỗi thao tác này trên stack/queue theo thứ tự từ trái sang phải.Sau khi hồn tất, tiến hành lấy lần lượt tất cả các phần tử cịn lại trong stack/queue, hãy cho biết nội dung lấy được.. - Pop và hiển thị các phần tử của stack đến khi gặp ngoặc trái (pop ngoặc trái nhưng khơng hiển thị ngoặc trái).. - Tốn tử: Nếu stack rỗng hay Token được ưu tiên hơn phần tử ở đỉnh stack thì Push vào Stack .Ngược lại (ưu tiên bằng hoặc ít ưu tiên hơn) pop và hiển thị 1 phần tử ở đỉnh stack .Lặp lại việc so sánh Token với 1 phần tử ở đỉnh stack.. - CẤU TRÚC DỮ LIỆU CỦA CÂY NHỊ PHÂN. - CÁC THAO TÁC CƠ BẢN a) Tạo một nút của cây b) Chèn một phần tử vào cây c) Duyệt cây: NLR, LNR, LRN d) Tìm một phần tử cĩ trên cây e) Xĩa phần tử của cây.. - Xuất các phần tử trên cây BST trên theo thứ tự: đầu, giữa, cuối.. - Tìm và xĩa (nếu cĩ thể) phần tử trên cây Root cĩ dữ liệu trùng với một mục dữ liệu Item cho trước được nhập từ bàn phím.. - Sắp xếp n mục dữ liệu (được cài đặt bằng mảng hay DSLK) bằng phương pháp cây nhị phân tìm kiếm BSTSort.. - Nếu node cĩ hai cây con thì cho phép chọn phần tử thế chỗ thuộc:. - ο Kiểu dữ liệu cĩ cấu trúc. - [4] ĐINH MẠNH TƯỜNG: Cấu trúc dữ liệu và thuật tốn. - [7] NGUYỄN TRUNG TRỰC: Cấu trúc dữ liệu
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt