- Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg33 CHƢƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢITHUẬT 1.1. - Mối quan hệ giữa cấu trúc dữ liệu và giải thuật Thực hiện một đề án tin học là chuyển bài toán thực tế thành bài toán cóthể giải quyết trên máy tính. - Một bài toán thực tế bất kỳ đều bao gồm các đốitượng dữ liệu và các yêu cầu xử lý trên các đối tượng đó. - Tổ chức biểu diễn các đối tƣợng thực tế Các thành phần dữ liệu thực tế đa dạng, phong phú và thường chứa đựngnhững mối quan hệ nào đó với nhau. - Do đó cần phải tổ chức, xây dựng cácCTDL thích hợp nhất sao cho vừa có thể phản ánh chính xác các dữ liệu thựctế này, vùa có thể dễ dàng dùng máy tính để xử lý. - Công việc này gọi là xâydựng cấu trúc dữ liệu cho bài toán. - Xây dựng các thao tác xử lý dữ liệu Giải thuật phản ánh các phép xử lý, còn đối tượng xử lý của giải thuật lạilà dữ liệu. - Chính dữ liệu chứa đựng các thông tin cần thiết để thực hiện giảithuật.Để xác định được GT phù hợp cần phải biết nó tác động đến loại CTDL nào. - Ví dụ: Để thực hiện tìm kiếm trên dãy số tăng dần, ta dùng GT tìm kiếmnhị phân thay vì tìm kiếm tuần tự. - Ví dụ: Để biểu diễn các điểm số của sinh viên ta dùng số thực Real thay vìxâu ký tự String vì còn phải thực hiện thao tác tính điểm trung bình từ nhữngđiểm số đó.. - Như vậy trong một đề án tin học, cấu trúc dữ liệu và giải thuật có mốiquan hệ chặt chẽ với nhau, được thể hiện qua công thứcCấu trúc dữ liệu + Giải thuật = Chương trình Với một cấu trúc dữ liệu đã chọn, sẽ có những giải thuật tương ứng, phùhợp. - Khi cấu trúc dữ liệu thay đổi thường giải thuật cũng phải thay đổi theođể tránh việc xử lý gượng ép, thiếu tự nhiên trên một cấu trúc không phù hợp.Hơn nữa, một cấu trúc dữ liệu tốt sẽ giúp giải thuật xử lý trên đó có thể pháthuy tác dụng tốt hơn, vừa nhanh vừa tiết kiêm vật tư, giải thuật cũng đơn giảnvà dễ hiểu hơn. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg44 11..22..CCááccttiiêêuucchhuu ẩẩ nn đđ áánnhhggiiáácc ấấ uuttrrúúccdd ữ ữ llii ệệ uu Do tầm quan trọng của cấu trúc dữ liệu đã được trình bày trong phần trên,nên nhất thiết phải chú trọng đến việc lựa chọn một phương án tổ chức dữliệu thích hợp cho đề án. - Một cấu trúc dữ liệu tốt phải thoả mãn ba tiêu chuẩn sau . - Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi củadữ liệu trong chu trình sống để có thể lựa chọn cấu trúc dữ liệu lưu trữ thểhiện chính xác đối tượng thực tế. - Ví dụ: Một số tình huống chọn cấu trúc lưu trữ sai - Chọn biến số nguyên integer để lưu trữ tiền thưởng bán hàng (được tínhtheo công thức tiền thưởng bán hàng = trị giá hàng *5. - Ví dụ : Một tình huống chọn cấu trúc lưu trữ không phù hợp. - Trong thời gian xử lývăn bản, nếu chọn cấu trúc lưu trữ văn bản trực tiếp lên tập tin thì sẽ gây khókhăn khi xây dựng các giải thuật cập nhật và làm chậm tốc độ xử lý củachương trình vì phải làm việc trên bộ nhớ ngoài. - Trường hợp này nên tìm mộtCTDL có thể tổ chức ở bộ nhớ trong để lưu trữ văn bản suốt thời gian soạnthảo. - TTii ếế ttkkii ệệ mmttààiinngguuyyêênnhh ệệ tthh ốố nngg Cấu trúc dữ liệu chỉ nên sử dụng tài nguyên vừa đủ để đảm nhiệm đượcchức năng của nó. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg55 và bộ nhớ. - Nếu tổ chức sử dụng đề án cần có những xử lý nhanh thì khi chọncấu trúc dữ liệu yếu tố tiết kiệm thời gian xử lý phải đặt nặng hơn tiêu chuẩnsử dụng tối đa bộ nhớ, và ngược lại. - Ví dụ: Một số tình huống chọn cấu trúc lưu trữ lãng phí. - Trong trường hợp này ta cần có một cấu trúc dữ liệu linhđộng hơn mảng, chẳng hạn danh sách liên kết sẽ được học trong Bài 6. - Định nghĩa kiểu dữ liệu Kiểu dữ liệu (KDL) T được xác định bởi 1 bộ , với: V: Tập các giá trị hợp lệ mà 1 đối tượng kiểu T có thể lưu trữ. - Các thuộc tính của một kiểu dữ liệu Các thuộc tính của 1 KDL bao gồm. - Các kiểu dữ liệu cơ bản Các loại dữ liệu cơ bản thường là các dữ liệu đơn giản, không có cấu trúc.Chúng thường là các giá trị vô hướng như số nguyên, số thực, các ký tự, cácgiá trị logic… Các loại dữ liệu này, do tính thông dụng và đơn giản của mình,thường được các Ngôn ngữ lập trình cấp cao xây dựng sẵn như một phần củangôn ngữ để giảm nhẹ công việc cho người lập trình. - Chính vì vậy đôi khingười ta còn gọi chúng là các kiểu dữ liệu định sẵn. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg66 Thông thường trong một hệ kiểu của ngôn ngữ lập trình sẽ có một số kiểudữ liệu được gọi là kiểu dữ liệu đơn hay kiểu dữ liệu phân tử (atomic). - Thông thường, các kiểu dữ liệu cơ bản bao gồm. - Kiểu có thứ tự rời rạc : số nguyên, ký tự, logic, liệt kê, miền con - Kiểu không rời rạc : số thực Tuỳ từng ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa sẵn này có thểkhác nhau đôi chút. - Với ngôn ngữ C, các kiểu dữ liệu này chỉ gồm số nguyên,số thực, ký tự. - Trong khi đó Pascal định nghĩa tất cả cáckiểu dữ liệu đã liệt kê ở trên và phân biệt chung một cách chặt chẽ. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg1133 Nếu một thuật toán có thời gian thực hiện T(n. - chúng ta sẽ nóirằng thuật toán có thời gian thực hiện cấp f(n). - Ví dụ. - Bảng sau đây cho ta các cấp thời gian thực hiện thuật toán được sử dụngrộng rãi nhất và tên gọi thông thường của chúng. - Ký hiệu ô lớn Tên gọi thông thƣờng O(1) Hằng O(log2n) LogaritO(n) Tuyến tính O(nlog2n) nlog2nO(n 2 ) Bình phương O(n 3 ) Lập phương O(2 n ) Mũ Danh sách trên sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện Các hàm như log2n, n, nlog2n, n 2 , n 3 được gọi là các hàm đa thức. - Giảithuật với thời gian thực hiện có cấp hàm đa thức thì thường chấp nhận được. - Một giải thuật mà thờigian thực hiện của nó là các hàm loại mũ thì tốc độ rất chậm. - XXáácc đđ ịị nnhh đđ ộộ pphh ứ ứ cctt ạạ ppttí í nnhhttooáánn Xác định độ phức tạp tính toán của một giải thuật bất kỳ có thể dẫn đếnnhững bài toán phức tạp. - Tuy nhiên, trong thực tế, đối với một số giải thuật tacũng có thể phân tích được bằng một số qui tắc đơn giản. - a) Qui tắc tổng : Giả sử T 1 (n) và T 2 (n) là thời gian thực hiện của hai giai đoạn chương trình P 1 và P 2 mà T 1 (n. - O(g(n)) thì thời gian thực hiện đoạn P 1 rồi P 2 tiếp theo sẽ là T 1 (n. - Ví dụ : Trong một chương trình có 3 bước thực hiện mà thời gian thựchiện tưng bước lần lượt là O(n 2. - O(n 3 ) và O(nlog2n) thì thời gian thực hiện 2 bước đầu là O(max (n 2 , n 3. - Khi đó thời gian thực hiện chương trìnhsẽ là O(max (n 3 ,nlog2n. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg1144 b) Qui tắc nhân : Nếu tương ứng với P 1 và P 2 là T 1 (n. - Để đánh giá thời gian thựchiện thuật toán, ta cần biết cách đánh giá thời gian thực hiện các câu lệnh củaPascal. - S n end là câu lệnh. - là câu lệnh. - Lệnh này được gọi là lệnh case. - Lệnh này được gọi là lệnh while. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg1155 6. - S n until E là câu lệnh. - Lệnh này được gọi là lệnh repeat 7. - Khi đó để đánh giáthời gian thực hiện một chương trình, ta có thể áp dụng phương pháp đệ qui sau 1. - Thời gian thực hiện các lệnh đơn : gán, đọc, viết là O(1) 2. - Lệnh hợp thành : thời gian thực hiện lệnh hợp thành được xác định bởi luật tổng. - Lệnh if : Giả sử thời gian thực hiện các lệnh S 1 , S 2 là O(f(n)) và O(g(n)) tương ứng. - Khi đó thời gian thực hiện lệnh if là O(max (f(n), g(n. - Lệnh while : Giả sử thời gian thực hiện lệnh S (thân của while) là O(f(n. - Lệnh repeat :Giả sử thời gian thực hiện khối begin S 1 , S 2 , ...,S n end là O(f(n. - Khi đó thời gian thực hiệnlệnh repeat là O(f(n)g(n. - Ta sẽ đánh giá thời gian thực hiệncủa hàm đệ qui sau Function Fact (n: integer. - Do quá trình tìmkiếm không những phụ thuộc vào kích thước của dữ liệu vào, mà còn phụthuộc vào tình trạng của dữ liệu. - Tức là thời gian thực hiện giải thuật còn phụthuộc vào vị trí của phần tử trong dãy bằng x. - Vì vậy,trong những trường hợp như trên ta cần phải đánh giá thời gian tính tốt nhất,tồi nhất và trung bình của thuật toán với độ dài đầu vào n. - Rõ ràng thời giantính của thuật toán có thể được đánh giá bởi số lần thực hiện câu lệnh i. - x thì câu lệnh i. - Do đó thời gian tính tốt nhất của thuật toán là O(1. - Vì thế thời gian tính tồi nhất là O(n). - Cuối cùng ta tính thời gian tính trung bình của thuật toán. - i + 1 phải thực hiện i lần (i = 1, 2. - bình phải thực hiện câu lệnh i. - n Vậy thời gian tính trung bình của thuật toán là O(n. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg2211 C HƢƠNG 2: ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY 22..11..KKhhááiinnii ệệ mm đđ ệệ qquuyy.. - Giải thuật đệ quy. - Giảithuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy. - Có thể nêu giải thuật như sau: If từ điển là một trang then tìm từ trong trang này else begin Mở từ điển vào trang “giữa” Xác định xem nửa nào của từ điển chứa từ cần tìm. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg2222 Giải thuật này được gọi là giải thuật đệ quy. - Thủ tục đệ quy Với giải thuật tìm kiếm như trên ta viết một thủ tục tương ứng như sau: Procedure SEARCH(dict, word). - Thủ tục trên được gọi là thủ thục đệ quy. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg2233 - Có một trường hợp đặc biệt, trường hợp suy biến là khi lời gọi callSEARCH với từ điển dict chỉ còn là một trang. - Trường hợp này gọi là đệ quy gián tiếp. - Ƣu và nhƣợc điểm của giải thuật đệ quy Qua các ví dụ trên ta có thể thấy: đệ quy là một công cụ để giải quyết các bài toán. - Có những bài toán, bên cạnh giải thuật đệ quy vẫn có những giảithuật lặp khá đơn giản và hữu hiệu. - Chẳng hạn giải thuật lặp tính n! có thểviết: Function Factorial(n) Beginif (n=0) or (n=1) then gt:=1else begingt:=1. - Hoặc ta xét giải thuật lặp tính số Fibonacci thứ n: Function Fibonacci(n) Beginif nInfo. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg4422 Các thao tác trên đều làm việc với chi phí O(1).Lưu ý, nếu không quản lý phần tử cuối xâu, thao tác dequeue sẽ có độ phức tạp O(n). - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg4488 4.3.3. - Cài đặt và đánh giá giải thuật a) Cài đặt Cài đặt thuật toán sắp xếp chèn trực tiếp thành hàm InsertionSort void InsertionSort(int a. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg4499 b) Đánh giá giải thuật. - Ðối với giải thuật chèn trực tiếp, các phép so sánh xảy ra trong mỗi vònglặp while tìm vị trí thích hợp pos , và mỗi lần xác định vị trí đang xét không thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng. - Giải thuật thực hiện tất cả N- 1 vòng lặp while , do số lượng phép so sánh và dời chỗ này phụ thuộc vàotình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợpnhư sau : Trƣờnghợp Số ph ép sosánh Số phép gán Tốt nhất Xấu nhất c) Bài tập Sắp xếp dãy số sau theo phương pháp chèn trực tiếp. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg5500 Bước 3 : Trong khi j < N thực hiệnxét cặp a[i], a[j] j = j+1. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg5511 4.4.3. - Cài đặt và đánh giá giải thuật a) Cài đặt . - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg5522 Cài đặt thuật toán sắp xếp theo kiểu đổi chỗ trực tiếp thành hàm InterchangeSort: void InterchangeSort(int a. - Cấu trúc dữ liệu và giải thuật - Dùng cho hệ đào tạo TCN, CĐ N TTrraanngg6699 Ví dụ Cho dãy số a gồm 8 phần tử Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau: left = 1, right = 8, midle = 4left = 5, right = 8, midle = 6 Dừng
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt