Cấu trúc Dữ Liệu Và Thuật Giải 1

- 5 1.1.2 Thuật giải (algorithms.
- 15 1.3 PHÂN TÍCH THUẬT GIẢI.
- 16 1.3.1 Thuật giải và các vấn đề liên quan.
- 16 1.3.2 Tính hiệu quả của thuật giải.
- 20 1.3.4 Đánh giá thời gian chạy của thuật giải.
- 37 2.2.1 Thuật giải sắp xếp chọn (Selection Sort.
- 38 2.2.2 Thuật giải sắp xếp chèn (Insertion Sort.
- 41 2.2.3 Thuật giải sắp xếp đổi chỗ trực tiếp (Interchange Sort.
- 44 2.2.4 Thuật giải sắp xếp nổi bọt (Bubble Sort.
- 46 2.2.5 Thuật giải shaker (Shaker Sort.
- 48 2.2.6 Thuật giải Shell (Shell Sort.
- 49 2.2.7 Thuật giải vun đống (Heap Sort.
- 51 2.2.8 Thuật giải sắp xếp nhanh (Quick Sort.
- 55 2.2.9 Thuật giải sắp xếp trộn (Merge Sort.
- 75 2 Cấu trúc dữ liệu và thuật giải 1 3.2.2 Tổ chức danh sách liên kết.
- 112TÀI LIỆU THAM KHẢO 3 Cấu trúc dữ liệu và thuật giải 1LỜI NÓI ĐẦU Cấu trúc dữ liệu và thuật giải là kiến thức nền tảng của chương trình đào tạo ngành công nghệ thông tin.
- Chương 1 trình bày tổng quan về cấu trúc dữ liệu và thuật giải.
- o Các bước trong lập trình để giải quyết cho một bài toán, o Các khái niệm kiểu dữ liệu, kiểu dữ liệu trừu tượng, o Tiếp cận phân tích thuật giải.
- Chương 3 trình bày cấu trúc dữ liệu danh sách liên kết.
- Các tác giả 4 Cấu trúc dữ liệu và thuật giải 1 Chương 1: Giới Thiệu Cấu Trúc Dữ Liệu Và Phân Tích Thuật GiảiMục tiêu Sau khi học xong chương này, sinh viên sẽ.
- Để giảm bớt sự phức 5 Cấu trúc dữ liệu và thuật giải 1tạp của bài toán thực tế, ta phải hình thức hóa nó, nghĩa là phát biểu lại bài toán thực tếthành một bài toán hình thức (hay còn gọi là mô hình toán).
- 6 Cấu trúc dữ liệu và thuật giải 1Trước hết ta nhận thấy rằng tại ngã năm này có 13 lối đi: AB, AC, AD, BA, BC, BD,DA, DB, DC, EA, EB, EC, ED.
- Số nhóm là ít nhất: ta phải tính toán sao cho số màu được dùng là ít nhất.Tóm lại, ta phải giải quyết bài toán sau: 7 Cấu trúc dữ liệu và thuật giải 1 "Tô màu cho đồ thị ở hình I.2 sao cho.
- Knuth (1973) định nghĩa thuật giải là một chuỗi hữu hạn các thao tác để giải một bài toán nào đó.
- Các tính chất quan trọng của thuật giải là.
- 8 Cấu trúc dữ liệu và thuật giải 1 - Xác định (definiteness): mỗi bước của thuật giải phải được xác định rõ ràng và phải được thực hiện chính xác, nhất quán.
- Có nhiều cách để thểhiện thuật giải: dùng lời, dùng lưu đồ.
- HEURISTIC cho bài toán tô màu đồ thị, thường gọi là thuật giải "háu ăn"(GREEDY) là: 9 Cấu trúc dữ liệu và thuật giải 1 - Chọn một đỉnh chưa tô màu và tô nó bằng một màu mới C nào đó.
- 11 Cấu trúc dữ liệu và thuật giải 1Từ những thảo luận trên chúng ta có thể tóm tắt các bước tiếp cận với một bài toán baogồm: 1.
- Tìm thuật giải trên mô hình này.
- Cài đặt thuật giải trong một ngôn ngữ lập trình cụ thể (Pascal,C.
- để thể hiện các kiểu dữ liệu trừu tượng, các bước của thuật giải được thể hiện bằng các lệnh và các cấu trúc điều khiển trong ngôn ngữ lập trình được dùng để cài đặt thuật giải.
- Tóm tắt các bước như sau: 12 Cấu trúc dữ liệu và thuật giải 11.2 Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT)1.2.1 Khái niệm trừu tượng hóa Trong tin học, trừu tượng hóa nghĩa là đơn giản hóa, làm cho nó sáng sủa hơn và dễ hiểu hơn.
- 14 Cấu trúc dữ liệu và thuật giải 11.2.4 Kiểu dữ liệu, cấu trúc dữ liệu và kiểu dữ liệu trừu tượng (Data Types, Data Structures, Abstract Data Types) Mặc dù các thuật ngữ kiểu dữ liệu (hay kiểu - data type), cấu trúc dữ liệu (data structure), kiểu dữ liệu trừu tượng (abstract data type) nghe như nhau, nhưng chúng có ý nghĩa rất khác nhau.
- 15 Cấu trúc dữ liệu và thuật giải 11.3 PHÂN TÍCH THUẬT GIẢI Với một vấn đề đặt ra có thể có nhiều thuật giải giải, chẳng hạn người ta đã tìm ra rất nhiều thuật giải sắp xếp một mảng dữ liệu.
- Như vậy chúng ta cần đánh giá thời gian thực hiện thuật giải.
- Cần nhấn mạnh rằng, mỗi thuật giải có một dữ liệu vào (Input) và một dữ liệu ra (Output).
- khi thực hiện thuật giải (thực hiện các bước đã mô tả), thuật giải cần cho ra các dữ liệu ra tương ứng với các dữ liệu vào.
- Biểu diễn thuật giải.
- Tính đúng đắn (correctness) của thuật giải.
- Chẳng hạn nếu thuật giải được thiết kế để tìm ước chung lớn 16 Cấu trúc dữ liệu và thuật giải 1 nhất của 2 số nguyên dương, thì khi đưa vào 2 số nguyên dương (dữ liệu vào) và thực hiện thuật giải phải cho ra một số nguyên dương (dữ liệu ra) là ước chung lớn nhất của 2 số nguyên đó.
- Chứng minh một cách chặt chẽ (bằng toán học) tính đúng đắn của thuật giải là một công việc rất khó khăn.
- Thuật giải đơn giản, dễ hiểu.
- Thuật giải dễ cài đặt (dễ viết chương trình.
- Hai tiêu chí này được nói tới như là tính hiệu quả của thuật giải.
- Dung lượng bộ nhớ gồm bộ nhớ dùng để lưu dữ liệu vào, dữ liệu ra, và các kết quả trung gian khi thực hiện thuật giải.
- Thời gian 17 Cấu trúc dữ liệu và thuật giải 1thực hiện thuật giải được nói tới như là thời gian chạy (running time) hoặc độ phức tạpthời gian của thuật giải.Sau này chúng ta chỉ quan tâm tới đánh giá thời gian chạy của thuật giải.
- Chẳng hạn câu nói “thời gian chạy của thuật giải là 30giây” là không thể chấp nhận được.
- Cỡcủa dữ liệu vào được xác định phụ thuộc vào từng thuật giải.
- Ví dụ, trong thuật giải tínhđịnh thức của ma trận vuông cấp n, ta có thể chọn cỡ của dữ liệu vào là cấp n của matrận.
- còn đối với thuật giải sắp xếp mảng cỡ n thì cỡ của dữ liệu vào chính là cỡ n củamảng.
- 18 Cấu trúc dữ liệu và thuật giải 1Nói chung, cỡ của dữ liệu càng lớn thì thời gian thực hiện thuật giải càng lớn.
- Nhưngthời gian thực hiện thuật giải không chỉ phụ thuộc vào cỡ của dữ liệu vào mà còn phụthuộc vào chính dữ liệu vào.
- Sau này khi nói tới thời gian chạy của thuật giải chúng ta cần hiểu đó làthời gian chạy trong trường hợp xấu nhất.
- Sử dụng thời gian chạy trong trường hợp xấunhất để biểu thị thời gian chạy của thuật giải có nhiều ưu điểm.
- Trước hết, nó đảm bảorằng, thuật giải không khi nào tiêu tốn nhiều thời gian hơn thời gian chạy đó.
- Thời gian chạy trung bình của thuật giải sẽ được ký hiệu là Ttb(n).
- Như vậy chúng ta xác định thời gian chạy T(n) là số phép toán sơ cấp mà thuật giải đòi hỏi, khi thực hiện thuật giải trên dữ liệu vào cỡ n.
- Ví dụ, giả sử thời gian chạy của thuật giải là T(n.
- 5n3+ 2n2+ 13n + 6 , 20 Cấu trúc dữ liệu và thuật giải 1 ta có: f(n.
- Biểu diễn thời gian chạy của thuật giải Thời gian chạy của thuật giải là một hàm của cỡ dữ liệu vào: hàm T(n).
- Chúng ta sẽ biểu diễn thời gian chạy của thuật giải bởi ký hiệu ô lớn: T(n.
- Trong số các cận trên của thời gian chạy, chúng ta sẽ lấy cận trên chặt (tight bound) để biểu diễn thời gian chạy của thuật giải.
- 21 Cấu trúc dữ liệu và thuật giải 1Định nghĩa.
- O(g(n)).Nói một cách khác, f(n) là cận trên chặt của T(n) nếu nó là cận trên của T(n) và takhông thể tìm được một hàm g(n) là cận trên của T(n) mà lại tăng chậm hơn hàm f(n).Sau này khi nói thời gian chạy của thuật giải là O(f(n.
- Trong bảng trên, chúng ta đã sắp xếp các cấp độ thời 22 Cấu trúc dữ liệu và thuật giải 1gian chạy theo thứ tự tăng dần, chẳng hạn thuật giải có thời gian chạy là O(logn) chạynhanh hơn thuật giải có thời gian chạy là O(n.
- Các thuật giải có thời gian chạy làO(nk), với k = 1,2,3.
- Đối với các thuật giải thời gian mũ, ta thấy rằng thời gian chạycủa thuật giải là chấp nhận được chỉ với các dữ liệu vào có cỡ rất khiêm tốn, n < 30.
- Chúng ta không hy vọng có thể áp dụng các thuật giải có thời gian chạy mũtrong tương lai nhờ tăng tốc độ máy tính, bởi vì không thể tăng tốc độ máy tính lên mãi 23 Cấu trúc dữ liệu và thuật giải 1 được, do sự hạn chế của các quy luật vật lý.
- Cần lưu ý rằng, đánh giá thời gian chạy của thuật giải là công việc rất khó khăn, đặc biệt là đối với các thuật giải đệ quy.
- Luật tổng Giả sử thuật giải gồm hai phần (hoặc nhiều phần), thời gian chạy của phần đầu là T1(n), phần sau là T2(n).
- Khi đó thời gian chạy của thuật giải là T1(n.
- 30 Cấu trúc dữ liệu và thuật giải 1 i.
- 32 Cấu trúc dữ liệu và thuật giải 1Chương 2: Tìm kiếm và sắp xếp trong2.1 Các phương pháp tìm kiếm trong Phương pháp tìm kiếm trong thường xuyên sử dụng trong đời sống hàng ngày cũng như trong xử lý tin học.
- 100 Cấu trúc dữ liệu và thuật giải 1 - struct tagNode.
- 101 Cấu trúc dữ liệu và thuật giải 1 - if (new_ele ==NULL) exit(1).
- 102 Cấu trúc dữ liệu và thuật giải 1 - return x.
- Giá trị này là một giá trịnằm ngoài miền xác định củadữ liệu trong hàng đợi.Trạng thái hàng đợi lúc bình thường 104 Cấu trúc dữ liệu và thuật giải 1Trạng thái hàng đợi lúc xoay vòng b.
- }Kiểm tra hàng đợi đầy hay chưa 105 Cấu trúc dữ liệu và thuật giải 1 - char IsFull.
- Dùng danh sách liên kết 106 Cấu trúc dữ liệu và thuật giải 1 a.
- if (IsEmpty(Q)) 107 Cấu trúc dữ liệu và thuật giải 1 - return NULLDATA.
- Biểu diễn danh sách liên kết vòng 108 Cấu trúc dữ liệu và thuật giải 12.
- 109 Cấu trúc dữ liệu và thuật giải 1 - else.
- 110 Cấu trúc dữ liệu và thuật giải 1 - l.pTail->pNext = l.pHead.
- 111 Cấu trúc dữ liệu và thuật giải 1 - if(q.
- 112 Cấu trúc dữ liệu và thuật giải 1 - tagDNode* pPre.
- Chèn đầu danh sách - Chèn cuối danh sách - Chèn nút vào sau một phần tử p 113 Cấu trúc dữ liệu và thuật giải 1- Chèn nút vào trước phần tử pChèn đầu danh sách - void AddFirst(DLIST &l, DNODE* new_ele.
- }Chèn phần tử vào cuối danh sách liên kết 114 Cấu trúc dữ liệu và thuật giải 1 - void AddTail(DLIST &l, DNODE *new_ele.
- //(4) 115 Cấu trúc dữ liệu và thuật giải 1 - if(q.
- 117 Cấu trúc dữ liệu và thuật giải 1 - p = l.pTail.
- 118 Cấu trúc dữ liệu và thuật giải 1 - DNODE *p.
- NULL) 119 Cấu trúc dữ liệu và thuật giải 1.
- l.pTail) return;//đã có thứ tự 120 Cấu trúc dữ liệu và thuật giải 1 - l1.pHead.
- }Nhận xét 121 Cấu trúc dữ liệu và thuật giải 1 Xâu kép về co bản có tính chất giống như xâu đơn, tuy nhiên nó cómột số tính chất khác như sau.
- 122 Cấu trúc dữ liệu và thuật giải 1 char CMND[15].
- Yêu cầu của chương trình là : 123 Cấu trúc dữ liệu và thuật giải 1 - In ra màn hình menu có các chức năng sau:1.
- Yêu cầu của chương trình là : 124 Cấu trúc dữ liệu và thuật giải 1 - In ra màn hình menu có các chức năng sau :1.
- Đếm số nút của Queue 125 Cấu trúc dữ liệu và thuật giải 17.
- 126Cấu trúc dữ liệu và thuật giải 1 127 Cấu trúc dữ liệu và thuật giải 1 TÀI LIỆU THAM KHẢO [1] ALFRED V.
- TRƯƠNG CHÍ TÍN (2000), “Cấu trúc dữ liệu và thuật giải 1”, Đại học Đà Lạt []ĐỖ XUÂN LÔI (1995), “Cấu trúc dữ liệu và giải thuật”, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt