›
›

Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về cấu trúc dữ liệu và giải thuật - Võ Quang Hoàng Khang

pdf 32 trang huongle 2490
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về cấu trúc dữ liệu và giải thuật - Võ Quang Hoàng Khang", để 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:

  • pdfgiao_trinh_cau_truc_du_lieu_va_giai_thuat_chuong_1_tong_quan.pdf

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về cấu trúc dữ liệu và giải thuật - Võ Quang Hoàng Khang

  1. CHƯƠNG 1. TỔNG QUAN VỀ CTDL & GT Võ Quang Hoàng Khang Email: vqhkhang@gmail.com 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 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 • Phát sinh lúc thực thi. điểm 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. • Được giải phóng khỏi bộ • Tồn tại đến khi kết thúc nhớ khi cần. chương trình. 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 .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] 14
  15. Kiểu chuỗi ký tự .Khai báo char [ ] ; VD: char hoten[50]; .Xem lại các hàm -gets, puts -strcpy, strcat, strlen -strcmp, stricmp -strchr, strstr 15
  16. 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; 16
  17. Bài tập 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 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. 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; 19
  20. 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; 20
  21. 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 = 2015; 21
  22. Bài tập 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 22
  23. 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 = 2015; 23
  24. Các phương pháp mô tả giải thuật .Lưu đồ .Mã giả .Mã tự nhiên 24
  25. 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 25
  26. Ký hiệu mã giả .IF THEN ENDIF .IF THEN ELSE ENDIF .WHILE DO ENDWHILE .DO UNTIL .DISPLAY .RETURN 26
  27. 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 27
  28. 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 28
  29. 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 29
  30. Mô tả bằng lưu đồ 30
  31. Đá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 31
  32. Q&A ? 32