intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Cấu trúc dữ liệu và thuật toán

Chia sẻ: Nguyen Quoc Khanh | Ngày: | Loại File: PPT | Số trang:29

Thêm vào BST
Báo xấu
240
lượt xem 47
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng lưu đồ (flow chart) hoặc bằng mã giả (pseudo code).

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 dữ liệu và thuật toán

  1. [1] Bài giảng CTDL. Nguyễn Hữu Tuân [2] Cấu trúc dữ liệu và thuật toán. PGS.TS Hoàng Nghĩa Tý. 2007 [3] Ngôn ngữ lập trình C++ và cấu trúc dữ liệu. Nguyễn Việt Hương. 2007 [4] Data Structure for Game Programmers. Premier Press. 2007
  2. CHƯƠNG II :: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢII THUẬT CHƯƠNG TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢ THUẬT CHƯƠNG II : MỘT SỐ THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP CHƯƠNG III : DANH SÁCH LIÊN KẾT - NGĂN XẾP VÀ HÀNG ĐỢI CHƯƠNG IV : CÂY
  3. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 1. Cấu trúc dữ liệu là gì ? :
  4. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 1. Cấu trúc dữ liệu là gì ? :
  5. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 1. Cấu trúc dữ liệu là gì ? : Int Int a Int Int Int Int a c a[1] a[2] a[3] a[4] Int Int b d
  6. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 1. Cấu trúc dữ liệu là gì ? :  Tổ chức dữ liệu để lưu trữ.  Mô hình dữ liệu để biễu diễn thông tin  Dữ liệu không có cấu trúc (đơn giản):  Int, Char, Boolean, Float…  Mỗi đối tượng dữ liệu là một phần tử đơn lẻ.  Dữ liệu có cấu trúc:  Được cấu thành bởi các phần tử dữ liệu đơn giản.  Mảng, Chuỗi, Danh sách, Tập tin.
  7. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 2. Một số ví dụ 4 14 22 38 27 15 A 0 1 2 3 4 5 Array 1 chiều
  8. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 2. Một số ví dụ Cột 0 1 2 3 4 5 Dòng 0 [0][0] [0][1] [0][2] [0][3] [0][4] [0][5] 3 5 10 13 6 9 [1][0] [1][1] [1][2] [1][3] [1][4] [1][5] 4 25 16 23 1 11 1 [2][0] [2][1] [2][2] [2][3] [2][4] [2][5] 88 21 13 4 22 19 2 Array 2 chiều
  9. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 2. Một số ví dụ Sinh viên (Họ tên, MSSV, Năm sinh) struct { Biến 1; typdef struct STUDENT Biến 2; { }; char HoTen[255]; char MSSV[3]; int NamSinh; } Danh sách
  10. I. KHÁI NIỆM VỀ CẤU TRÚC DỮ LIỆU 3. Vai trò cấu trúc dữ liệu trong lập trình Cấu Trúc Dữ Liệu + Giải Thuật = Chương trình (Data Structures + Algorithms = Program)
  11. II. GIẢI THUẬT 1. Khái niệm giải thuật : Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng lưu đồ (flow chart) hoặc bằng mã giả (pseudo code).
  12. II. GIẢI THUẬT 2. Cách viết một giải thuật ( Biểu diễn giải thuật ) A. Ngôn ngữ tự nhiên B. Lưu đồ (flow chart) C. Mã giả (pseudo code)
  13. • Điểm bắt đầu / Kết thúc giải thuật Begin End • Thao tác nhập/ xuất dữ liệu • Thao tác xử lý • Thao tác lựa chọn • Đường tiến trình • Chú thích • Ký hiệu kết nối cùng trang hay 2 sang trang khác
  14. Ví dụ: Hãy dùng lưu đồ mô tả bài toán tính Chu vi và Di ện tích hình vuông khi người sử dụng cho biết số đo cạnh của nó. Bắt đầu Nhập cạnh CV=cạnh x 4 DT=cạnh x cạnh Xuất kết quả  CV,DT Kết thúc 15
  15. Giải thuật Tính CV, DT hình vuông; {khai báo các biến} Cạnh,CV,DT: số thực; BEGIN Nhập vào số đo cạnh; CV = cạnh x 4; DT = cạnh x cạnh; Xuất ra CV (in kết quả trên màn hình) Xuất ra DT (in kết quả trên màn hình) END;
  16. III. ĐỘ PHỨC TẠP CỦA GIẢI THUẬT (Algorithm Efficiency) 1. Dạng tổng quát f (n) n : kích cỡ đầu vào của dữ liệu
  17. III. ĐỘ PHỨC TẠP CỦA GIẢI THUẬT (Algorithm Efficiency) 2. Vòng lặp đơn 1 i=1 1 i=1 2 loop ( i
  18. III. ĐỘ PHỨC TẠP CỦA GIẢI THUẬT (Algorithm Efficiency) 2. Vòng lặp đơn
  19. III. ĐỘ PHỨC TẠP CỦA GIẢI THUẬT (Algorithm Efficiency) 2. Vòng lặp đơn 1 i=1 1 i=1 2 loop ( i
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
18=>0