TAILIEUCHUNG - Cấu trúc dữ liệu và giải thuật - chương 8

Chương 8 của bộ slide bài giảng đầy đủ (gồm 11 chương) về môn CTDL & GT của trường ĐHBK . Trình bày ngắn gọn dễ hiểu với những hiệu ứng minh họa sinh động. Hướng dẫn các bạn sắp xếp thứ tự trong một lập trình dễ dàng hơn. | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) Chương 8: Sắp thứ tự Khái niệm Sắp thứ tự: Đầu vào: một danh sách Đầu ra: danh sách có thứ tự tăng (hoặc giảm) trên khóa Phân loại: Sắp thứ tự ngoại (external sort): tập tin Sắp thứ tự nội (internal sort): bộ nhớ Giả thiết: Sắp thứ tự nội Sắp tăng dần Insertion sort Insertion sort - Danh sách liên tục Giải thuật insertion sort – Danh sách liên tục Algorithm Insertion_sort Input: danh sách cần sắp thứ tự Output: danh sách đã được sắp thứ tự 1. for first_unsorted = 1 to size //Tìm vị trí hợp lý để chèn giá trị đang có vào . current = list[first_unsorted] . position = first_unsorted . while (position>0 and list[position - 1] > current) //Dời chỗ các phần tử lớn về sau . list[position] = list[position - 1] . position = position - 1 //Chép phần tử trước đó vào đúng vị trí của nó . list[position - 1] = current End Insertion_sort Mã C++ Insertion sort – Danh sách liên tục template void Sortable_list :: insertion_sort( ) { int first_unsorted; // position of first unsorted entry int position; // searches sorted part of list Record current; // holds the entry temporarily removed from list for (first_unsorted = 1; first_unsorted 0 && entry[position − 1] > current); entry[position] = current; } } Insertion sort – DSLK Giải thuật Insertion sort - DSLK Algorithm Insertion_sort Input: danh sách cần sắp thứ tự và có ít nhất 1 phần tử Output: danh sách đã được sắp thứ tự 1. last_sorted = head //Đi dọc danh sách liên kết 2. while (last_sorted chưa là phần tử cuối) . first_unsorted là phần tử kế của last_sorted //Chèn vào đầu? . if (dữ liệu của first_unsorted 0 and list[position - 1] > current) //Dời chỗ các phần tử lớn về sau . list[position] = list[position - 1] . position = position - 1 //Chép phần tử trước đó vào đúng vị trí của nó . list[position - 1] = current End Insertion_sort Mã C++ Insertion sort – Danh sách liên tục template void Sortable_list :: .

• Kỹ thuật lập trình
• cấu trúc dữ liệu
• giải thuật
• stack vầ queue liên kết
• đệ qui
• danh sách và chuỗi
• sắp thứ tự
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp