Chương I: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mục tiêu: Mô tả được khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. Trình bày được các tiêu chuẩn để đánh giá độ phức tạp của giải thuật. Ghi nhớ được các kiểu dữ liệu cơ bản, kiểu dữ liệu trừu tượng và các cấu trúc dữ liệu cơ bản. Thực hiện các thao tác an toàn với máy tính.
Nội dung chính: Chương này trình bày về tổng quan về cấu trúc dữ liệu và giải thuật, các tiêu chuẩn danh gia cấu trúc dữ liệu ,phản ánh đúng thực tếp, phù hợp với các thao tác trên đó, tiết kiệm tài nguyên hệ thống. Kiểu dữ liệu, kiểu dữ liệu cơ bản, các kiểu dữ liệu có cấu trúc, kiểu chuỗi ký tự, kiểu mảng, kiểu union, kiểu mẫu tin (cấu trúc), kiểu con trỏ, kiểu tập tin, mối quan hệ giữa cấu trúc dữ liệu và giải thuật. KHÁI NIỆM THUẬT GIẢI VÀ ĐÁNH GIÁ ĐỘ PHỨC TẠP CỦA GIẢI THUẬT 1. Khái niệm thuật giải.
Tập các bước có thể tính toán được để đạt được kết quả mong muốn. Khi đã có mô hình thích hợp cho một bài toán ta cần cố gắng tìm cách giải quyết bài toán trong mô hình đó. Khởi đầu là tìm một giải thuật, đó là một chuỗi hữu hạn các chỉ thị (instruction) mà mỗi chỉ thị có một ý nghĩa rõ ràng và thực hiện được trong một lượng thời gian hữu hạn. Knuth (1973) định nghĩa giải thuật 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 giải thuật là: - Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước. - Xác định (definiteness): mỗi bước của giải thuật 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. - Hiệu quả (effectiveness): các thao tác trong giải thuật phải được thực hiện trong một lượng thời gian hữu hạn. Mỗi thuật toán có một dữ liệu vào (Input) và một dữ liệu ra (Output); Nói tóm lại, một giải thuật phải giải quyết xong công việc khi ta cho dữ liệu vào.
Có nhiều cách để thể hiện giải thuật: dùng lời, dùng lưu đồ,. Và một lối dùng rất Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 2 phổ biến là dùng ngôn ngữ giả, đó là sự kết hợp của ngôn ngữ tự nhiên và các cấu trúc của ngôn ngữ lập trình Ví dụ: Tính tổng các số nguyên lẻ từ 1n B1: S=0 B2: i=1 B3: Nếu i>n thì sang B7, ngược lại sang B4 B4: S=S+i B5: i=i+2 B6: Quay lại B3 B7: Tổng cần tìm là S 1. Đặc trưng của thuật giải - Tính đúng đắn: Thuật toán cần phải đảm bảo cho một kết quả đúng sau khi thực hiện đối với các bộ dữ liệu đầu vào. ây có thể nói là đặc trưng quan trọng nhất đối với một thuật toán: Thuật toán cần phải đảm bảo sẽ dừng sau một số hữu hạn bước.
- Tính xác định: Các bước của thuật toán phải được phát biểu rõ ràng, cụ thể, tránh gây nhập nhằng hoặc nhầm lẫn đối với người đọc và hiểu, cài đặt thuật toán. - Tính hiệu quả: Thuật toán được xem là hiệu quả nếu như nó có khả năng giải quyết hiệu quả bài toán đặt ra trong thời gian hoặc các điều kiện cho phép trên thực tế đáp ứng được yêu cầu của người dùng. - Tính phổ quát: Thuật toán được gọi là có tính phố quát (phổ biến) nếu nó có thể giải quyết được một lớp các bài toán tương tự. Biểu diễn thuật giải - Cách 1: Mô tả các bước thực hiện của thuật giải - Cách 2: Sử dụng sơ đồ giải thuật Ví dụ: mô tả thuật toán giải phương trình bậc nhất ax+b=0 (a,b là các số thực) Cách 1: Mô tả các bước thực hiện của thuật toán Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 3 Cách 2: Sử dụng sơ đồ giải thuật Sử dụng các ký hiệu hình khối cơ bản để tạo thành một mô tả mang tính hình thức Hình 3.
ký hiệu hình khối cơ bản Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 4 Hình 3. Đánh giá độ phức tạp của giải thuật 2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu ể đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau: - Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong), - Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán, - Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu. Đánh giá độ phức tạp của thuật giải Việc đánh giá độ phức tạp của một thuật toán quả không dễ dàng chút nào.
Ở dây, chúng ta chỉ muốn ước lượng thời gian thực hiện thuận toán T(n) để có thể có sự so sánh tương đối giữa các thuật toán với nhau. Trong thực tế, thời gian thực hiện một thuật toán còn phụ thuộc rất nhiều vào các điều kiện khác như cấu tạo của máy tính, dữ liệu đưa vào, …, ở đây chúng ta chỉ xem xét trên mức độ của lượng dữ liệu đưa vào ban đầu cho thuật toán thực hiện. ể ước lượng thời gian thực hiện thuật toán chúng ta có thể xem xét thời gian thực hiện thuật toán trong hai trường hợp: - Trong trường hợp tốt nhất: Tmin - Trong trường hợp xấu nhất: Tmax Từ đó chúng ta có thể ước lượng thời gian thực hiện trung bình của thuật toán: Ta Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 5 ể đánh giá hiệu quả của một thuật toán, có thể tính số lượng các phép tính phải thực hiện của thuật toán này: - Phép so sánh - Phép gán - Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán,tức là độ lớn của đầu vào - Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào - Tuy nhiên, không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng - ể ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm Big-O Bước 1. - Tăng i thêm 1 đơn vị.
- Gán Tổng = Tổng + i Bước 3. So sánh i với n - Nếu i < n, quay lại bước 2. - Ngược lại, dừng thuật toán. Số phép gán của thuật toán là bao nhiêu? • Số phép so sánh là bao nhiêu? - Gán: f(2n + 2), So sánh: f(n) ộ phức tạp: O(n) Ví dụ: Thuật toán tính tổng các số từ 1 đến n s=0; for(i= 1; i<=n; i++) s=s+i; Sử dụng quy tắc cộng: O(1)+O(n) ộ phức tạp: O(n) Ví dụ: Xác định độ phức tạp của thuật toán sau: for (i= 1;i<=n;i++) // lệnh1 for (j= 1;j<=m;j++) // lệnh 2 ộ phức tạp: O(max(n,m)) Ví dụ: Xác định độ phức tạp của thuật toán sau: for(i=1; i<=n; i++) for (j=1; j<=n; j++) //Lệnh thực hiện Sử dụng quy tắc nhân: O(n)*O(n) ộ phức tạp: O(n2) Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 6 2.
Các độ phức tạp thường gặp ộ phức tạp hằng số: O(1) – thời gian chạy không phụ thuộc vào độ lớn đầu vào - ộ phức tạp tuyến tính: O(n) – thời gian chạy tỉ lệ thuận với độ lớn đầu vào - ộ phức tạp logarit: O(logn) - ộ phức tạp đa thức: O(P(n)), với P là đa thức có bậc từ 2 trở lên - ộ phức tạp hàm mũ: O(2n) II. CÁC KIỂU DỮ LIỆU CƠ BẢN 1. Định nghĩa kiểu dữ liệu. Kiểu dữ liệu T được xác định bởi một bộ < V, O > , với : V (Value): tập các giá trị hợp lệ mà một đối tượng kiểu T có thể lưu trữ O (Operation): tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T.
Ví du: Giả sử có kiểu dữ liệu mẫu tự = < Vc , Oc > với Vc = { a-z,A-Z} Oc = { lấy mã SCII của ký tự, biến đổi ký tự thường thành ký tự hoa…} Giả sử có kiểu dữ liệu số nguyên = < Vi, Oi > với Vi = { -32768.32767} Oi = { +, -, *, /, %} Như vậy, muốn sử dụng một kiểu dữ liệu cần nắm vững cả nội dung dữ liệu được phép lưu trữ và các xử lý tác động trên đó. Các thuộc tính của 1 kiểu dữ liệu bao gồm: * Tên kiểu dữ liệu * Miền giá trị * Kích thước lưu trữ Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 7 * Tập các toán tử tác động lên kiểu dữ liệu 2. 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 loại dữ liệu đơn giản, không có cấu trúc như số nguyên, số thực, các ký tự, các giá 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 (NNLT) cấp cao xây dựng sẵn như một thành phần của ngôn ngữ để giảm nhẹ công việc cho người lập trình.
Chính vì vậy đôi khi người ta còn gọi chúng là các kiểu dữ liệu định sẵn. 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 Tùy ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa sẵn 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ự. Và theo quan điểm của C, kiểu ký tự thực chất cũng là kiểu số nguyên về mặt lưu trữ, chỉ khác về cách sử dụng.
Ngoài ra, giá trị logic ÚNG (TRUE) và giá trị logic S I (F LSE) được biểu diễn trong C như là các giá trị nguyên khác zero và zero. Các kiểu dữ liệu định sẵn trong C gồm các kiểu sau: Tên kiểu Kích thƣớc Miền giá trị Ghi chú Có thể dùng như số nguyên Char 01 byte -128 đến 127 1 byte có dấu hoặc kiểu ký tự Số nguyên 1 byte không Unsign char 01 byte 0 đến 255 dấu Int 02 byte -32738 đến 32767 Số nguyên 2 byte Unsign int 02 byte 0 đến 65535 Có thể gọi tắt là unsign Long 04 byte -232 đến 231 -1 Unsign long 04 byte 0 đến 232-1 Giới hạn chỉ trị tuyệt đối. Tuy nhiên kiểu float chỉ có 7 chữ số có nghĩa.7E308 Long double 10 byte 3.1E4932 Chƣơng I: Tổng quan về cấu trúc dữ liệu và giải thuật 8 Như vậy, trong C xét cho cùng chỉ có 2 loại dữ liệu cơ bản là số nguyên và số thực. Tức là chỉ có dữ liệu số.
Hơn nữa các số nguyên trong C có thể được thể hiện trong 3 hệ cơ số là hệ thập phân, hệ thập lục phân và hệ bát phân.