›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về CTDl và GT - Trần Minh Thái

pptx 34 trang huongle 6940
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về CTDl và GT - Trần Minh Thái", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_1_tong_quan.pptx

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về CTDl và GT - Trần Minh Thái

  1. CHƯƠNG 1. TỔNG QUAN VỀ CTDL & GT Trần Minh Thái Email: minhthai@itc.edu.vn Website: www.minhthai.edu.vn 1
  2. Mục tiêu ▪Giới thiệu vai trò của tổ chức dữ liệu ▪Mối quan hệ giữa GT & CTDL ▪Các khái niệm và yêu cầu về CTDL ▪Nhắc lại các kiểu dữ liệu trong C++ ▪Tổng quan về đánh giá độ phức tạp GT 2
  3. Suy nghĩ ? Theo bạn: trước khi viết một chương trình để giải quyết một bài toán nào đó trên máy tính thì cần phải làm những việc gì? 3
  4. Xét đoạn chương trình sau void main() { int n; cout >n; if(n%2==0) cout<<"La so chan"; else cout<<"La so le"; } 4
  5. Vai trò của CTDL & GT Cấu Giải trúc dữ thuật liệu Chương trình 5
  6. Các tiêu chuẩn đánh giá CTDL ▪Phản ánh đúng thực tế ▪Phù hợp với thao tác ▪Tiết kiệm tài nguyên hệ thống 6
  7. Khái niệm về kiểu dữ liệu T = V = {Tập các giá trị} O = {Tập các thao tác xử lý} Ví dụ: Kiểu dữ liệu số nguyên short trong ngôn ngữ C T = short V = {-32768, 32767} O = {+, -, *, /, %} 7
  8. Khái niệm về kiểu dữ liệu ▪Các thuộc tính của một kiểu dữ liệu gồm: ▪ Tên ▪ Miền giá trị ▪ Kích thước lưu trữ ▪ Tập các thao tác tác động lên kiểu dữ liệu đó ▪Các loại kiểu dữ liệu ▪ Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản ▪ Kiểu dữ liệu có cấu trúc hướng giải quyết vấn đề: Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, 8
  9. Khái niệm về kiểu dữ liệu Tĩnh Động • Được định nghĩa ở thời • Được gắn kết với một con điểm biên dịch. trỏ (tại thời điểm biên dịch chưa có). • Được cấp phát ở thời điểm • Phát sinh lúc thực thi. liên kết. • Có thể có giá trị ban đầu • Không xác định giá trị ban tùy theo từng ngôn ngữ lập đầu. trình. • Tồn tại đến khi kết thúc • Được giải phóng khỏi bộ chương trình. nhớ khi cần. 9
  10. Nhắc lại các kiểu dữ liệu C++ ▪Kiểu cơ sở: Số nguyên, số thực và kiểu logic ▪Kiểu mảng, chuỗi ▪Kiểu có cấu trúc 10
  11. Kiểu số nguyên Stt Tên kiểu Ghi chú Kích thước Ký tự 1 byte 1 char Số nguyên 1 byte 2 unsigned char Số nguyên dương 1 byte 3 short Số nguyên 2 bytes 4 unsigned short Số nguyên dương 2 bytes 5 int Số nguyên 4 bytes 6 unsigned int Số nguyên dương 4 bytes 7 long Số nguyên 4 bytes 8 unsigned long Số nguyên dương 4 bytes 11
  12. Kiểu số thực Stt Tên kiểu Ghi chú Kích thước 1 float 4 bytes 2 double 8 bytes 3 long double 8 bytes Kiểu luận lý Stt Tên kiểu Ghi chú Kích thước 1 bool Gồm 2 giá trị: true hoặc false 12
  13. Kiểu mảng 1 chiều Giá trị 5 7 10 3 11 2 Vị trí 0 1 2 n-2 n-1 ▪Khai báo [ ]; VD: int a[100]; ▪Gán giá trị ban đầu VD1: int a[100] = {0}; VD2: int a[5] = {3, 6, 2, 10, 17}; hoặc: int a[] = {3, 6, 2, 10, 17}; 13
  14. Kiểu mảng 1 chiều Phát sinh ngẫu nhiên -Khởi tạo phát sinh ngẫu nhiên srand((unsigned int)time(NULL)); -Phát sinh giá trị ngẫu nhiên int x = rand()%k; k: Số nguyên dương x [0 k-1] VD: Phát sinh 1 số nguyên có giá trị từ 0 đến 50 srand((unsigned int)time(NULL)); int x = rand()%51; 14
  15. Bài tập 1 1. Cài đặt hàm nhập mảng số nguyên, n phần tử 2. Cài đặt hàm phát sinh n phần tử ngẫu nhiên cho mảng số nguyên 3. Cài đặt hàm phát sinh n phần tử ngẫu nhiên có giá trị tăng dần cho mảng số nguyên 15
  16. Kiểu chuỗi ký tự ▪Khai báo char [ ] ; VD: char hoten[50]; ▪Xem lại các hàm -cin.getline, cin.ignore -strcpy, strcat, strlen -strcmp, stricmp -strchr, strstr 16
  17. Kiểu mảng – Khai báo kiểu con trỏ ▪ Mảng 1 chiều * ; VD: int *a; ▪ Chuỗi ký tự char * ; VD: char *hoten; 17
  18. Kiểu mảng – Khai báo kiểu con trỏ Lưu ý khi sử dụng phải cấp phát biến con trỏ bằng lệnh new, hủy bằng lệnh delete VD: int *a; int n = 10; a = new int[n]; delete a; 18
  19. Bài tập 2 Viết lại các hàm trong Bài tập 1 dùng khai báo kiểu con trỏ 19
  20. Kiểu dữ liệu có cấu trúc struct tên_struct { khai báo các thuộc tính; }; typedef struct tên_struct tên_kiểu; 20
  21. Ví dụ kiểu dữ liệu có cấu trúc struct ttDate { char thu[9]; unsigned char ngay; unsigned char thang; int nam; }; typedef struct ttDate DATE; 21
  22. Truy cập thành phần có cấu trúc ▪Biến cấu trúc kiểu tĩnh .thành phần cấu trúc VD: DATE d; d.nam = 2012; 22
  23. Bài tập 3 Viết hàm nhập và hàm xuất thông tin của một sinh viên gồm các thông tin: -Mã số -Họ tên -Điểm trung bình 23
  24. Truy cập thành phần có cấu trúc ▪Biến cấu trúc kiểu con trỏ ->thành phần cấu trúc VD: DATE *d; d->nam = 2012; 24
  25. Bài tập 4 Viết lại các hàm trong Bài tập 3 sử dụng khai báo biến kiểu con trỏ cấu trúc 25
  26. Các phương pháp mô tả giải thuật ▪Lưu đồ ▪Mã giả ▪Mã tự nhiên 26
  27. Các ký hiệu lưu đồ Bắt đầu/ kết thúc Điều Rẽ nhánh kiện Giá trị trả về Luồng xử lý Điểm nối Khối xử lý Nhập/ Xuất 27
  28. Ký hiệu mã giả ▪IF THEN ENDIF ▪IF THEN ELSE ENDIF ▪WHILE DO ENDWHILE ▪DO UNTIL ▪DISPLAY ▪RETURN 28
  29. Ví dụ mô tả giải thuật Tìm ước số chung lớn nhất của 2 số nguyên dương a và b ▪Đầu vào: 2 số nguyên dương a và b ▪Đầu ra: ước số chung lớn nhất của a và b 29
  30. Mô tả bằng mã tự nhiên Bước 1: Nếu a = b thì kết luận a là ước số chung lớn nhất, kết thúc Bước 2: Nếu a > b thì a = a – b; Ngược lại thì b = b – a; Bước 3: Quay trở lại Bước 1 30
  31. Mô tả bằng mã giả WHILE a ≠ b DO IF a>b THEN a=a-b ELSE b=b-a ENDIF ENDWHILE DISPLAY a 31
  32. Mô tả bằng lưu đồ 32
  33. Đánh giá độ phức tạp giải thuật ▪Phụ thuộc vào ngôn ngữ lập trình ▪Phụ thuộc vào người lập trình ▪Phụ thuộc vào bộ dữ liệu thử ▪Phụ thuộc vào phần cứng 33
  34. Q&A ? 34