Bài giảng Cấu trúc dữ liệu: Chương 1 - Trịnh Xuân

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

58
lượt xem 2
download

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

Chương 1 - Các khái niệm cơ bản. Nội dung chính trong chương này gồm: Giới thiệu, các bước xây dựng chương trình, cấu trúc dữ liệu và thuật toán, đánh giá độ phức tạp thuật toán, biểu diễn thuật toán, giải thuật đệ quy,... Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 1 - Trịnh Xuân

!  Hình thức thi: BTL CẤU TRÚC DỮ LIỆU "  Nhóm 4 SV !  Cách tính điểm: Khoa Công nghệ thông tin Email: trinhxuan@gmail.com " Điểm CC: 10% Thời lượng: 60 tiết – LT " Điểm GK: 20% " Điểm thi: 70% ! Bài tập lớn Web: //sites.google.com/site/trinhxuan ! Test Bài tập lớn CTDL – Khoa CNTH – Viện ĐH Mở HN 1 CTDL – Khoa CNTH – Viện ĐH Mở HN 2 *Tài liệu học tập: Mục đích môn học #  Hiểu được khái niệm CTDL và Thuật toán ! Giáo trình bắt buộc " Giáo trình Cấu trúc dữ liệu – Khoa CNTT, #  Biết cách đánh giá độ phức tạp của một thuật toán Viện ĐH Mở HN – Lưu hành nội bộ #  Nắm được các CTDL cơ bản: Mảng, Danh sách #  Hiểu và vận dụng được một số CTDL đặc biệt: ! Giáo trình tham khảo Hàng đợi, Ngăn xếp, Cây, Đồ thị " Đỗ Xuân Lôi, “Cấu trúc dữ liệu và giải #  Hiểu và áp dụng được một số thuật toán cơ bản: thuật”, NXB Khoa học và kỹ thuật. Tìm kiếm, Sắp xếp, … " Introduction to Algorithms – The cormen CTDL – Khoa CNTH – Viện ĐH Mở HN 3 CTDL – Khoa CNTH – Viện ĐH Mở HN 4 *Nội dung môn học SỐ Y/C STT NỘI DUNG GIẢNG DẠY Ghi chú TIẾT Đọc TL 1 5 Đánh giá Thuật Toán - Phân công BTL 2 5 TK và SX x 3 5 TK và SX x 4 5 Thực hành mảng - Test x 5 5 DSLK Đơn x Các buổi 6 5 Thực hành DSLK Đơn - Test x Thực hành có thể mang máy 7 5 Danh sách liên kết đôi x tính cá nhân 8 5 Stack - Queue x đi thực hành 9 5 Cây x 10 5 Cây - Test x 11 5 Đồ thị x 12 5 Test BTL – Đánh giá sơ bộ - TH x CTDL – Khoa CNTH – Viện ĐH Mở HN 5 CTDL – Khoa CNTH – Viện ĐH Mở HN 6
Lưu ý sử dụng Phòng máy Yêu cầu kiến thức cần có !  Sử dụng điều hòa: Phải đăng ký và mất phí !  Xem và tổng hợp lại ngôn ngữ C !  Nội dung cần tổng hợp lại: !  Tổng số buổi thực hành: 03 buổi "  Cấu trúc chương trình !  Tổng phí phải nộp: 600.000đ (200.000/1 buổi) "  Khai báo biến "  Phí tính trên 1 sinh viên: 10.000đ/3 buổi "  Nhập/xuất dữ liệu "  Cấu trúc điều khiển !  Lớp trưởng thu giúp "  Mảng "  Chuỗi !  Cách thức thực hiện: "  Chương trình con – hàm "  Cấu trúc "  Buổi 1: Thu thập nguyên vọng sử dụng điều hòa "  Con trỏ "  Buổi 2+3: Thu tiền sử dụng điều hòa "  File ! Nguyên tắc số ít theo số nhiều "  … CTDL – Khoa CNTH – Viện ĐH Mở HN 7 CTDL – Khoa CNTH – Viện ĐH Mở HN 8 I. Giới thiệu !  Các bước để xây dựng bài toán tin học trong máy tính CHƯƠNG I: Lập trình #include Bài toán Thiết kế … CÁC KHÁI NIỆM thực tế Yêu cầu CƠ BẢN Giải thuật Chương trình Thuật toán Xây dựng một bài toán tin • Ngôn ngữ lập trình: học thực chất là chuyển một • PASCAL, • C/C++, bài toán thực tế thành một • JAVA, bài toán giải quyết được • Visual Basic bằng máy tính •  … CTDL – Khoa CNTH – Viện ĐH Mở HN 9 CTDL – Khoa CNTH – Viện ĐH Mở HN 10 II. Các bước xây dựng chương trình 1. Xác định bài toán Xác định bài toán #  Xác định xem ta phải giải quyết vấn đề gì? Tìm CTDL biểu diễn bài toán #  Xác định yêu cầu cần thực hiện của bài toán $ các thao tác cần thực hiện Tìm thuật toán #  Các bài toán tin học cần phải chỉ ra lời giải tốt nhất bởi Lập trình vì nếu không lời giải đó có thể đòi hỏi nhiều thời gian và chi phí. Kiểm thử Tối ưu chương trình CTDL – Khoa CNTH – Viện ĐH Mở HN 11 CTDL – Khoa CNTH – Viện ĐH Mở HN 12
2. Tìm CTDL biểu diễn bài toán 3. Tìm thuật toán %  Xác định input và output của bài toán %  Xác định hệ thống chặt chẽ và rõ ràng các quy tắc để %  Input: dữ liệu đầu vào từ Input có được Output %  Output: Kết quả mong muốn đạt được %  Xác định dãy thao tác trên CTDL đầu vào để giải Các tiêu chuẩn: quyết yêu cầu bài toán #  Biểu diễn đầy đủ các thông tin nhập và xuất của bài toán #  Phải phù hợp với các thao tác của thuật toán mà ta lựa Đảm bảo chọn để giải quyết bài toán #  Mỗi bước thao tác rõ ràng #  Cài đặt được trên máy tính với một ngôn ngữ lập trình #  Không được rơi vào quá trình vô hạn xác định #  Sau khi thực hiện các bước phải cho kết quả đúng #  Phải đảm bảo cài đặt được chương trình CTDL – Khoa CNTH – Viện ĐH Mở HN 13 CTDL – Khoa CNTH – Viện ĐH Mở HN 14 4. Lập trình 5. Kiểm thử #  Kiểm tra lỗi chương trình #  Xác định ngôn ngữ lập trình được sử dụng #  Lỗi cơ bản &  Lỗi cú pháp #  Thông thường ta không nên cụ thể hóa ngay toàn bộ &  Lỗi cài đặt chương trình mà nên tiến hành theo phương pháp tinh &  Lỗi thuật toán chế từng bước #  Lập bộ test để kiểm thử # Nguyên tắc % Ban đầu, thể hiện thuật toán với các bước tổng thể, mỗi bước nêu lên một công việc phải thực hiện #  Nguyên tắc xây dựng bộ test % Một công việc đơn giản hoặc là một đoạn chương trình đã &  Bắt đầu với bộ test nhỏ, đơn giản, được học thuộc thì ta tiến hành viết mã lệnh ngay bằng ngôn &  Tiếp theo vẫn là các bộ test nhỏ, nhưng chứa các giá ngữ lập trình trị đặc biệt hoặc tầm thường. % Một công việc phức tạp thì ta lại chia thành những công việc &  Các bộ test phải đa dạng, tránh sự lặp đi lặp lại nhỏ hơn để lại tiếp tục với những công việc nhỏ hơn đó. &  Có một vài bộ test lớn CTDL – Khoa CNTH – Viện ĐH Mở HN 15 CTDL – Khoa CNTH – Viện ĐH Mở HN 16 6. Tối ưu chương trình III. CTDL và Thuật toán !  Xây dựng một bài toán cần: #  Đặt mục tiêu viết chương trình sao cho đơn giản, làm sao chạy ra kết quả đúng, sau đó ta xem lại những chỗ " Xác định Cấu trúc dữ liệu nào viết chưa tốt thì tối ưu lại mã lệnh để chương trình ! Đốitượng dữ liệu dùng trong bài toán $ Tổ chức biểu ngắn hơn, chạy nhanh hơn diễn được đối tượng " Xác định Thuật toán #  Không nên viết tới đâu tối ưu tới đó, bởi chương trình ! Các yêu cầu xử lý trên đối tượng đó $ Xác định và có mã lệnh tối ưu thường phức tạp và khó kiểm soát. xây dựng thao tác xử lý trên đối tượng #  Tiêu chuẩn tối ưu &  Tính tin cậy CTDL + Thuật toán = Chương trình &  Tính uyển chuyển &  Tính trong sáng Structure Data + Algorithm = Program &  Tính hữu hiệu CTDL – Khoa CNTH – Viện ĐH Mở HN 17 CTDL – Khoa CNTH – Viện ĐH Mở HN 18
a. Cấu trúc dữ liệu – Structure Data !  Các yếu tố xác định một kiểu CTDL: ! Cấu trúc dữ liệu là một cách để tổ chức và "  Tên kiểu CTDL lưu thông tin các đối tượng bài toán (thực tế) "  Miền giá trị "  Kích thước lưu trữ vào trong máy tính sao cho nó có thể được sử "  Tập các toán tử (thao tác) thực hiện trên kiểu dữ liệu đó dụng một cách hiệu quả !  Các tiêu chuẩn đánh giá một CTDL: ! Các kiểu cấu trúc dữ liệu cơ bản: "  Phản ảnh đúng thực tế "  Phù hợp với thao tác xử lý " Mảng, Bản ghi "  Tiết kiệm tài nguyên hệ thống " Danh sách liên kết, Ngăn xếp, Hàng đợi !  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, " Cây "  Sử dụng càng ít tài nguyên, " Đồ thị "  Thời gian xử lý và không gian bộ nhớ tốt CTDL – Khoa CNTH – Viện ĐH Mở HN 19 CTDL – Khoa CNTH – Viện ĐH Mở HN 20 b. Thuật toán - Algorithm: * Tính chất của thuật toán !  Thuật toán, còn gọi là giải thuật ! Tính chính xác " là một bộ các qui tắc hay qui trình cụ thể nhằm ! Tính rõ ràng giải quyết một vấn đề nào đó trong một số bước ! Tính khách quan hữu hạn, ! Tính phổ dụng " hoặc cho ra một kết quả (output) từ một tập hợp của các dữ liệu đưa vào (input) ! Tính kết thúc Thuật toán Input Output CTDL – Khoa CNTH – Viện ĐH Mở HN 21 CTDL – Khoa CNTH – Viện ĐH Mở HN 22 IV. Đánh giá độ phức tạp thuật toán a. Độ phức tạp không gian: !  Các tiêu chí lựa chọn thuật toán: ! Là tổng số chi phí về mặt không gian (bộ "  1. Thuật toán đơn giản, dễ hiểu. nhớ) cần thiết sử dụng cho thuật toán $ "  2. Thuật toán dễ cài đặt (dễ viết chương trình) đánh giá dựa vào tổng số bộ nhớ khai báo "  3. Thuật toán cần ít bộ nhớ "  4. Thuật toán chạy nhanh cho các biến !  => để đánh giá thuật toán dựa vào độ phức tạp ! Chi phí bộ nhớ gồm: thuật toán "  Lưu dữ liệu vào - input !  Độ phức tạp thuật toán được thể hiện qua: "  Lưu dữ liệu ra - output "  Không gian "  Lưu các kết quả trung gian - temp "  Thời gian CTDL – Khoa CNTH – Viện ĐH Mở HN 23 CTDL – Khoa CNTH – Viện ĐH Mở HN 24
b. Độ phức tạp thời gian: VD: Xác định độ phức tạp thuật toán !  là tổng thời gian cần thiết để hoàn thành thuật toán int sum (int n) { !  Được đánh giá dựa vào số lượng các thao tác được sử int sum, i ; No time dụng trong thuật toán dựa trên bộ dữ liệu đầu vào sum = 0; 1 Unit !  Các thao tác được xem xét: i = 1; 1 Unit "  Phép so sánh while (i < n) n Unit (n Comparison) "  Phép cộng, trừ, nhân, chia, … { sum = sum + i; 2 x (n-1) Unit "  Phép toán thay đổi i = i+ 1; 2 x (n-1) Unit "  Phép gán } return sum; 1 Unit "  Phép trả lại giá trị } "  … !  Khi xét độ phức tạp thuật toán chỉ tập trung vào độ phức T"(n)"="1+1+n+2*(n+1)+2*(n+1)+1"="5n"+"1"" tạp tính toán (độ phức tạp thời gian) CTDL – Khoa CNTH – Viện ĐH Mở HN 25 CTDL – Khoa CNTH – Viện ĐH Mở HN 26 *Phân loại đánh giá: VD: Xác định độ phức tạp không gian và thời gian thuật toán 5" 5 3 10 13 6 9 15 21 12 8 61 39 39" int Sum (int n) { int sum ; sum =0; Best Case Average Case Worst Case for ( int i =0 ; i
VD: Xác định ký hiệu O –lớn của thuật toán *Một số trường hợp ký tự O-lớn đặc biệt %  Các câu lệnh thông thường int Sum (int n) s1, s2,………, sk (i = 1; i = i*i ) { O(1) int sum ; No time sum = 0; 1 Unit %  Vòng lặp đơn (for, while, do-while) for ( int i =1 ; i
V. Biểu diễn thuật toán * Sử dụng lưu đồ khối ! Liệtkê theo bước !  Làcông cụ rất trực quan để diễn đạt các thuật toán ! Sơ đồ khối – flow chart !  Làhệ thống các nút có hình dạng khác nhau, thể hiện các chức năng khác nhau và được nối bởi các ! Mã giả - Pseudocode cung " Dùng ngôn ngữ C để cài đặt thuật toán !  Các thành phần của lưu đồ khối: CTDL – Khoa CNTH – Viện ĐH Mở HN 37 CTDL – Khoa CNTH – Viện ĐH Mở HN 38 VD: Xây dựng sơ đồ thuật toán sau VI. Giải thuật đệ quy (recursion) int sum (int n) !  Khái niệm Begin { !  Bài toán int sum, i ; sum = 0; Sum = 0; !  Lời giải và giải thuật đệ quy i = 1; i = 1; while (i < n) { Sai sum = sum + i; i
2. Phân loại hàm đệ quy 3. Kỹ thuật tìm giải thuật đệ quy # Đệ quy tuyến tính Trong thân hàm gọi 1 lần chính nó #  Thông số hóa bài toán #  Tìm các điều kiện biên (điều kiện chặn) # Đệ quy nhị phân Thân hàm gọi 2 lần chính nó &  Lời giải với giá trị cụ thể # Đệ quy phi tuyến Thân hàm lặp gọi nhiều lần chính nó &  Tìm giải thuật cho các tình huống này # Đệ quy tương hỗ Hai hàm đệ quy gọi nhau #  Tìm giải thuật tổng quát theo hướng đệ quy lui dần về tình long Tong ( int huống bị chặn long G( nint) n ); int long { Fibonaci Giaithua ( int (nint )U (nint) n) long G( int n ) #  Thực hiện cài đặt long { { if (n
Cài đặt đệ quy tìm phần tử lớn nhất trong mảng BÀI TẬP VỀ NHÀ float Max ( float a[ ], int n ) ! Giảibài toán tìm phần tử lớn nhất của mảng { a gồm n số nguyên bằng đệ quy if (n==1) return a[0]; else return ((a[n-1] > Max(a, n-1))? a[n-1] : Max(a,n-1)); ! Yêu cầu: } " Viếtbằng tay đầy đủ các bước để giải " Đầu giờ sau nộp lại cho GV CTDL – Khoa CNTH – Viện ĐH Mở HN 49 CTDL – Khoa CNTH – Viện ĐH Mở HN 50 Tóm lược bài học Bài tập về nhà !  Làm theo nhóm !  Trình bày đầy đủ - chi tiết các bước để giải quyết bài toán Các khái niệm CTDL và thuật toán !  Bài toán: cho thông tin của hàng hóa gồm: mã hàng hóa, tên hàng hóa, số lượng và đơn giá. Viết chương trình Đánh giá độ phức tạp thuật toán quản lý hàng hóa với các yêu cầu: "  Nhập vào một danh sách hàng hóa "  In lại danh sách hàng hóa Biểu diễn thuật toán "  In danh sách hàng hóa có đơn giá trên 50000 "  Tính tổng tiền của tất cả các hàng hóa Các bước thiết kế thuật toán "  Đếm số hàng hóa có số lượng dưới 20 !  Yêu cầu: Cài đặt code Giải thuật đệ quy "  "  Làm báo cáo chi tiết các bước để giải bài toán (viết tay hoặc đánh máy) CTDL – Khoa CNTH – Viện ĐH Mở HN 51 CTDL – Khoa CNTH – Viện ĐH Mở HN 52 Bài tập viết hàm đệ quy 5. Nhận xét về hàm đệ quy !  Tínhtổng các số nguyên nhỏ hơn hoặc bằng n !  Tính tổng các phần tử của mảng a gồm n số HÀM ĐỆ QUY: Vừa tốn bộ nhớ nguyên vừa chạy chậm vì gọi hàm nhiều !  BTVN: Bài tập viết hàm đệ quy   Giải thuật đệ quy đẹp (gọn gàng), dễ chuyển "  Tính số Fibonaci thứ n thành chương trình. "  Tìm phần tử lớn nhất của mảng a gồm n phần tử   Nhiều ngôn ngữ không hỗ trợ giải thuật đệ quy (Fortran).   Nhiều giải thuật rất dễ mô tả dạng đệ quy nhưng lại rất khó mô tả với giải thuật không-đệ-quy. CTDL – Khoa CNTH – Viện ĐH Mở HN 54 CTDL – Khoa CNTH – Viện ĐH Mở HN 68
7. Khử đệ quy *Khử đệ quy bằng vòng lặp !  Là quá trình chuyển đổi 1 giải thuật đệ quy thành giải thuật không đệ quy. !  Ý tưởng: Lưu lại các trị của các lần tính toán !  Chưa có giải pháp cho việc chuyển đổi này một trước làm dữ liệu cho việc tính toán của lần sau. cách tổng quát. !  Đi từ điều kiện biên đi tới điều kiện kết thúc. !  Cách tiếp cận: " Dùng quan điểm đệ quy để tìm giải thuật cho bài toán. " Mã hóa giải thuật đệ quy. " Khử đệ quy để có giải thuật không-đệ-quy. CTDL – Khoa CNTH – Viện ĐH Mở HN 69 CTDL – Khoa CNTH – Viện ĐH Mở HN 70 Thí dụ: Hàm tính giai thừa của n Thí dụ hàm tính trị thứ n của dãy Fibonacci: long Fibo(int n) 1 1 2 3 5 8... { long GiaiThua( int n) Trị cần lưu if (n