CẤU TRÚC LƯU TRỮ DỮ LIỆU VÀ GIẢI THUẬT

Chia sẻ: Pham Nhung | Ngày: | Loại File: PDF | Số trang:106

Thêm vào BST

Báo xấu

471
lượt xem 103
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các cấu trúc...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CẤU TRÚC LƯU TRỮ DỮ LIỆU VÀ GIẢI THUẬT

TRƯỜNG ĐH CÔNG NGHIỆP TP. HCM TT CNTT CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT DATA STRUCTURES & ALGORITHMS Giáo viên: Trần Thị Kim Chi
Giới thiệu Mục tiêu   Nắm vững khái niệm kiểu dữ liệu, kiểu dữ liệu trừu tượng.  Nắm vững và cài đặt được các kiểu dữ liệu trừu tượng cơ bản như danh sách, ngăn xếp, hàng đợi, cây, tập hợp, bảng băm, đồ thị bằng một ngôn ngữ lập trình căn bản.  Vận dụng được các kiểu dữ liệu trừu tượng để giải quyết bài toán đơn giản trong thực tế. Ngôn ngữ lập trình minh hoạ   Mã giả (pseudocode)  C++
Nội dung chương trình Nội dung Số Phân bổ thời gian TT Ghi tiết chú Thực Tự Lý thuyết học hành Tổng quan 1 3 3 0 6 Đệ quy 2 6 3 3 10 Tìm kiếm 3 10 6 4 12 Sắp xếp 4 5 3 3 10 Chồng (Stacks) 5 6 3 3 10 Hàng đợi (Queues) 6 6 3 3 12 Danh sách và chuỗi 7 10 6 4 15 Các bảng và phục hồi thông tin 8 10 6 4 10 Cây nhị phân 9 14 9 5 10
Kiến thức tiên quyết Đã học môn phương pháp lập trình.  Kiến thức về kỹ thuật lập trình.  Sử dụng thành thạo ngôn ngữ C++ 
Tài liệu Tài liệu học tập:  [1] C & Data Structures, P. S. Deshpande, O. G. Kakde - CHARLES RIVER MEDIA, INC. Hingham, Massachusetts. [2] Robert L.Kruse, Alexander J.Ryba, Data Structures And Program Design In C++, Prentice-Hall International Inc., 1999. [3] Bài giảng & Bài thực hành CTDL - Trường ĐHCN. Tài liệu tham khảo:  [1] Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh Đức, Trường DHKHTN – DHQG TP.HCM. [2] Cấu trúc dữ liệu, Nguyễn Trung Trực, Trường DHBK – DHQG TP.HCM [3] Nguyễn Ngô Bảo Trân, Giáo trình cấu trúc dữ liệu và giải thuật – Trường Đại học Bách Khoa TP.HCM, 2005.
Tiêu chuẩn đánh giá Kiểm tra và Thi Điể Tuần m Kiểm tra thường xuyên Bất kỳ 10% Thi giữa kỳ Tuần5 20% Thi cuối kỳ Tuần 9 50% Báo cáo tiểu luận Hàng tuần 20% Yêu cầu đối với sinh viên: • Dự lớp: lý thuyết trên 80% , thực hành bắt buộc 100% • Bài tập: hoàn thành các bài tập trên lớp và ở nhà • Tham gia đầy đủ các buổi thảo luận của nhóm
Trao đổi thông tin Địa chỉ mail: • Kimchi_12041972@yahoo.com Địa chỉ download tài liệu: • http://my.opera.com/LinhChi10/blog/
Chương 1 Tổng quan 1.1. Khái niệm cấu trúc dữ liệu & giải thuật 1.2. Đánh giá cấu trúc dữ liệu và giải thuật 1.3. Ôn lại ngôn ngữ C++ 1.4. Các kiểu dữ liệu 1.5. Kiểu dữ liệu trừu tượng 1.6. Hàm 1.7. Tổng kết 1.8. Câu hỏi và bài tập
Cấu trúc dữ liệu Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung  gian hoặc dữ liệu đưa ra (output data). Mỗi dữ liệu có một kiểu dữ liệu riêng. Kiểu dữ liệu có thể là kiểu cơ bản hay kiểu trừu tượng Cấu trúc dữ liệu là sự sắp xếp có logic của thành phần dữ  liệu được kết hợp với nhau và là tập hợp các thao tác chúng ta cần để truy xuất các thành phần dữ liệu. Ví dụ: thư viện   Bao gồm các sách  Truy cập/tìm kiếm một cuốn sách nào đó đòi hỏi phải biết cách sắp xếp của các sách  Người dùng truy cập sách chỉ thông qua người quản lý thư viện.
Cấu trúc dữ liệu Một cấu trúc dữ liệu tốt phải thỏa mãn:  Phản ánh đúng thực tế: Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn CTDL lưu trữ thể hiện chính xác đối tượng thực tế.  Phù hợp với các thao tác trên đó: Tăng tính hiệu quả của đề án, việc phát triển các thuật toán đơn giản, tự nhiên hơn => chương trình đạt hiệu quả cao hơn về tốc độ xử lý.  Tiết kiệm tài nguyên hệ thống: CTDL chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm được chức năng của nó. Loại tài nguyên cần quan tâm là : CPU và bộ nhớ.
Những cấu trúc dữ liệu cơ bả n Các cấu trúc bao gồm  Danh sách liên kết (linked lists)  Ngăn xếp (Stack), Hàng đợi (Queue)  Cây nhị phân (binary trees)  … 
Giải thuật giải là gì? Giải thuật (Algorithm):  Còn gọi là thuật toán là tập các bước có thể tính toán được  để đạt được kết quả mong muốn. Giải thuật được xây dựng trên cơ sở của cấu trúc dữ liệu  đã được chọn. Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên  (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code). Ví dụ: Sắp xếp các phần tử  2 4 6 1 3 5 7 1 2 3 4 5 6 7
Giải thuật giải là gì? 13 Ví dụ: Tính tổng các số nguyên lẻ từ 1n  B1: S=0  B2: i=1  Nếu i>n thì sang B7, ngược lại sang B4 B3:  B4: S=S+i  B5: i=i+2  Quay lại B3 B6:  Tổng cần tìm là S B7: 
Giải thuật giải là gì? Giải thuật (Algorithm):  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. q 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.  Ngoài ra một giải thuật còn phải có đầu vào (input) và đầu ra (output).
Mối quan hệ giữa cấu trúc dữ liệu và giải thuật CTDL + Thuật toán = Chương trình
Đánh giá CTDL và GT 1. 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á CTDL và GT Thời gian thực hiện chương trình.  Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.  Ví dụ: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số.  Thời gian thực hiện chương trình là một hàm không âm, tức là T(n) ≥ 0 ∀n≥ 0. Đơn vị đo thời gian thực hiện.  Đơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây... mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng.  Ví dụ: Khi ta nói thời gian thực hiện của một chương trình là T(n) = cn thì có nghĩa là chương trình ấy cần cn chỉ thị thực thi.
Đánh giá CTDL và GT Tỷ suất tăng  Ta nói rằng hàm không âm T(n) có tỷ suất tăng (growth rate) f(n) nếu tồn tại các hằng số c và n0 sao cho T(n) ≤ c.f(n) với mọi n ≥ n0. Ví dụ 1-3: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(n) = (n+1)2.  Đặt n0 = 1 và c = 4 thì với mọi n ≥ 1 chúng ta dễ dàng chứng minh rằng T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất tăng của T(n) là n2. Ví dụ 1-4: Tỷ suất tăng của hàm T(n) = 3n3 + 2n2 là n3. Thực  vậy, cho n0 = 0 và c = 5 ta dễ dàng chứng minh rằng với mọi n ≥ 0 thì 3n3 + 2n2 ≤ 5n3
Đánh giá CTDL và GT Khái niệm độ phức tạp của giải thuật  Độ phức tạp tính toán của giải thuật là một hàm chặn trên của hàm thời gian. Vì hằng nhân tử c trong hàm chặn trên không có ý nghĩa nên ta có thể bỏ qua vì vậy hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn. Ba hàm cuối cùng ta gọi là dạng hàm mũ, các hàm khác gọi là  hàm đa thức. Một giải thuật mà thời gian thực hiện có độ phức tạp là một  hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện, còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật.
Độ phức tạp thuật toán 20 Để đá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