›
›

Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 5 đến 8 - Khương Đại Thế

ppt 68 trang hoanguyen 2970
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 5 đến 8 - Khương Đại Thế", để 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:

  • pptbai_giang_lap_trinh_can_ban_khuong_dai_the.ppt

Nội dung text: Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 5 đến 8 - Khương Đại Thế

  1. Tài liệu tham khảo “Lập trình C”, Quách Tuấn Ngọc, Nhà Xuất Bản Giáo dục 2004 “Kỹ thuật lập trình C cơ sở và nâng cao”, Phạm Văn Ất, Nhà Xuất Bản Khoa Học Kỹ Thuật – 1996. “Giáo trình ngôn ngữ C”, Lê Hoài Bắc – Lê Hoàng Thái – Nguyễn Tấn Trần Minh Khang – Nguyễn Phương Thảo, Nhà Xuất Bản Đại Học Quốc Gia Tp. Hồ Chí Minh – 2003. “Giáo trình lý thuyết & Bài tập ngôn ngữ C”, Nguyễn Đình Tê – Hoàng Đức Hải, Nhà Xuất Bản Mũi Cà Mau. “Bài tập ngôn ngữ C từ A đến Z”, Huỳnh Tấn Dũng – Hoàng Đức Hải, Nhà Xuất Bản Lao Động – Xã Hội. Khương Đại Thể Slide 1/68
  2. Chương 5 MỞ ĐẦU VỀ NGÔN NGỮ C Khương Đại Thể Slide 2/68
  3. Nội dung Nhận biết tập ký tự dùng trong C Nhận biết một số từ khóa của C. Nhận biết tổ hợp ESCAPE của C Dạng thức của một chương trình C Chỉ thị tiền xử lý Nhận biết các kiểu dữ liệu cơ bản của C Tự định nghĩa được kiểu dữ liệu Định nghĩa và phân biệt được hằng và biến Nhận diện và sử dụng được các toán tử của C Biết sử dụng các cấu trúc điều khiển của C Khương Đại Thể Slide 3/68
  4. 5.1. Tập ký tự của C – Character set Digits: 0 9 Letters- alphabet characters: a z, A Z Special characters: + - * / % & ! # ^ & ➔ Các ký tự in được của bàn phím chuẩn Khương Đại Thể Slide 4/68
  5. 5.2. Từ khóa– Keywords Là những từ ngôn ngữ C đã định nghĩa sẵn cho người lập trình sử dụng để thiết kế chương trình. Là thành phần cơ bản để tạo câu lệnh trong C. Bao gồm các nhóm: – Kiểu số nguyên :char , int , short , unsigned , long – Kiểu số thực:float , double – Kiểu rời rạc :enum – Kiểu cấu trúc : struct , union – Kiểu rỗng: void – Tự định kiểu: typedef – Khai báo hằng: const , define – Khai báo biến: static , extern , auto, register, volatile – cấu trúc chọn : if , else , switch , case , default – cấu trúc lăp: for , while , do – Từ khóa điều khiển: break , continue , return , goto – Khương Đại Thể Slide 5/68
  6. 5.3. Tên – Name / Identifier Do người lập trình tự định nghĩa, dùng đặt tên cho hằng, biến, hàm Tên là 1 từ, chiều dài 1 từ : Có thể tự ấn định bằng Menu Options / Compiler / Source / Identifier Length Các từ trong C phân biệt chữ hoa chữ thường (case- sensitive) ‘a’ ’z’, ‘A’ ’Z’ ‘_’ (gạch nối) ‘a’ ’z’, ‘A’ ’Z’ ‘_’ (gạch nối) ‘0’ ’9’ Hãy cho biết các tên sau tên nào là hợp lệ? m _12 _m12 12m 6L Hãy cho biết các tên sau có cùng ngữ nghĩa hay không? delta Delta dElta DELTA Khương Đại Thể Slide 6/68
  7. 5.4. Chuỗi ESCAPE Cách Tên gọi Ý nghĩa viết Escape: thoát, bỏ qua '\'' Single quote Ký tự ' '\"' Double quote Ký tự " Chuỗi escape bắt đầu '\\' Backslash Ký tự \ bằng ký tự ‘\’ mang ý ‘\?’ Question mark Ký tự ? nghĩa bỏ qua ý nghĩa thông thường của ký ‘\a’ Alert Phát tiếng Beep ra loa '\n' New line Xuống dòng mới tự đứng sau ký tự này. '\0' NULL Rỗng Do đó chuỗi escape Di chuyển con nhấp nháy '\t' Horizontal tab mang một ý nghĩa đặc tới vị trí tab kế tiếp biệt. '\b' Backspace Lùi con nhấp nháy 1 vị trí Đưa con nhấp nháy về Carriage return '\r' đầu dòng '\f' Form feed Sang trang kế tiếp Khương Đại Thể Slide 7/68
  8. 5.5.Các kiểu dữ liệu cơ bản của –C Data types Kích thước và phạm vi của kiểu dữ liệu phụ thuộc vào trình biên dịch ( xem file limit.h và float.h ) Định dạng Số Kiểu Phạm vi Nhập/Xuất byte %c unsigned char 1 0 255 %c char 1 -128 127 %u unsigned int 2 0 65,535 %d, %i int 2 - 32,768 32,767 %lu unsigned long 4 0 4,294,967,295 %ld, %li long 4 -2,147,483,648 2,147,483,647 %f float 4 3.4 * (10-38) 3.4 * (10+38) %lf double (long float) 8 1.7 * (10-308) 1.7 * (10+308) %lf long double 10 3.4 * (10-4932) 1.1 * (10+4932) Khương Đại Thể Slide 8/68
  9. 5.6. Hằng – Constant Cách 1:Dùng macro. Ví dụ: #define PI 3.141592 Cách 2: Dùng từ khóa const. Ví dụ: const PI = 3.141592; Hay là: const double PI = 3.141592; Khương Đại Thể Slide 9/68
  10. Chú ý: #define Đặt một tên gọi cho một nội dung Còn gọi là macro. #include #include #define PI 3.141592 void main() { printf("%lf", 3.141592*3.2*3.2); getch(); } Thay thế trị trước khi biên dịch Khương Đại Thể Slide 10/68
  11. Hiệu ứng lề – Side effect Error! #include #include #define PI =3.141592; void main() { printf("%lf", =3.141592;*3.2*3.2); getch(); } #include #include Không được mong đợi #define Area(x) x*x void main() { printf("%lf", 3+2*3+2); getch(); } #define Area(x) (x)*(x) (3+2)*(3+2) OK Khương Đại Thể Slide 11/68
  12. Thí dụ: -Hằng không kiểu: trình biên dịch dùng bộ nhớ ít nhất để chứa, tối thiểu là 2 bytes. -Hằng có kiểu sẽ buộc trình biên dịch phải dùng đúng kiểu đã chỉ định để lưu trữ trị hằng. -Hằng chuỗi ký tự được để trong cặp nháy đôi. -Hằng ký tự được để trong Toán tửsizeof(data) cho biết số byte cặp nháy đơn. mà data này chiếm chỗ. Khương Đại Thể Slide 12/68
  13. 5.7. Biến – Variable Biến phải thuộc 1 kiểu dữ liệu. Khai báo biến: tênbiến; 2 biến cùng kiểu cách nhau dấu phẩy. C chuẩn chỉ cho phép khai báo biến ở đầu chương trình. Còn C++, cho phép khai báo biến bất kỳ chỗ nào nếu thấy cần. Ví dụ: int m=3 ; long t1=23, t2=3*t1; double z1, z2, z3 ; char c1 , c2 = ‘A’ ; Khương Đại Thể Slide 13/68
  14. Ví dụ Lỗi “khai báo kết thúc không đúng cách” vì khai báo xong biến t, sang biến kiểu khác mà để dấu “phẩy”. Đáng lẽ phải là dấu “chấm phẩy”. Khương Đại Thể Slide 14/68
  15. 5.7. Biến – Variable Lấy địa chỉ của biến: &tênbiến Đúng về Syntax, nhưng Sai về Lý luận Khương Đại Thể Slide 15/68
  16. 5.8. Cấu trúc một chương trình C /* CHAO.CPP Chuong trinh minh hoa don gian */ /* */ Khối chú thích // Xuat chuoi “Chao cac ban” ra man hinh // Chú thích đến cuối dòng #include #include Khai báo sử dụng thư viện void main() #include : chỉ thị tiền xử lý { clrscr(); printf(“Chao cac ban"); Chương trình chính , bắt getch(); buộc là main() } ; kết thúc 1 câu lệnh đơn Khương Đại Thể Slide 16/68
  17. Ví dụ: Cấu trúc một chương trình C Từ nay về sau, chúng ta nên thêm phần chú thích để gợi nhớ Khương Đại Thể Slide 17/68
  18. Chú thích – Comment Dùng để giải thích chương trình. Chú thích 1 dòng: chỉ dùng trong C++ // Chú thích Chú thích nhiều dòng: C/C++ /* Các dòng chú thích */ Dòng chú thích được bỏ qua khi biên dịch Khương Đại Thể Slide 18/68
  19. Chỉ thị tiền xử lý– Preprocessor indicators Còn được gọi là chỉ thị tiền biên dịch vì đây là những chỉ thị mà trình biên dịch phải làm trước khi chuyển chương trình C thành chương trình mã máy. Các chỉ thị này bắt đầu bằng‘#’ Khương Đại Thể Slide 19/68
  20. Cách làm việc của chỉ thị#include nội dung file stdio.h nội dung file Compile conio.h code chương trình Khương Đại Thể Slide 20/68
  21. Chỉ thị #include : Chèn 1 file #include #include “file không thuộc Include Directories” Lưu ý: Không nên có khoảng trống giữa và tên file vì trong cặp ký tự này được hiểu là tên file Khương Đại Thể Slide 21/68
  22. Không có Lưu ý chỉ thị#include khoảng trắng có khoảng trắng (Error) Khương Đại Thể Slide 22/68
  23. Chương 6 BIỂU THỨC VÀ CÁC PHÉP TOÁN Khương Đại Thể Slide 23/68
  24. 6.1. Toán tử - Operators Toán tử: Ký hiệu mô tả 1 phép toán cho kết qủa 1 trị duy nhất. Toán hạng (operand): Dữ liệu để phép toán tác động. Kết qủa (result): Dữ liệu mới được sinh ra sau khi thực thi xong phép toán. C hỗ trợ các phép toán có 1/2/3 toán hạng Unary/binary/ternary operator: Toán tử 1/2/3 ngôi. Khương Đại Thể Slide 24/68
  25. Các loại toán tử của C Toán tử số học– Arithmetic ops Toán tử so sánh – Relational ops Toán tử luận lý – Logical ops Toán tử gán – Assignment ops Toán tử trên bit – Bitwise ops Các toán tử khác Khương Đại Thể Slide 25/68
  26. 6.1.1. Toán tử số học – Arithmetic operators Khương Đại Thể Slide 26/68
  27. Ví dụ: int k = 3, t = 6; int u = k- -; int v = - - t; Hỏi k, t, u, v có trị bao nhiêu? Khương Đại Thể Slide 27/68
  28. Lưu ý về Toán tử chia Kết quả % Nguyên % Nguyên Phần dư Phép chia Kết quả trong C Nguyên / Nguyên Phần nguyên Kết quả Nguyên / Thực Thực / Kết quả Thực / Nguyên Thực Kết quả Thực / Thực Thực Khương Đại Thể Slide 28/68
  29. Ví dụ: Toán tử % chỉ dùng cho số nguyên Khương Đại Thể Slide 29/68
  30. 6.1.2. Toán tử so sánh – Relational operators Khương Đại Thể Slide 30/68
  31. Ví dụ: Toán tử so sánh Khương Đại Thể Slide 31/68
  32. 6.1.2. Toán tử luận lý – Logical operators Toán tử Luận lý Khương Đại Thể Slide 32/68
  33. 6.1.3. Toán tử gán – Assigment operators Khi gán trị mới cho 1 biến, trị cũ bị ghi đè. 0000000000000001 0000000000001011 x=1; x=11; Ví dụ Tương đương s = s+a; s += a; s = s / a; s /= a; Khương Đại Thể Slide 33/68
  34. Ví dụ: Khương Đại Thể Slide 34/68
  35. 6.1.4. Toán tử bit – Bitwise operators > 7d 1 bit 00001110 14d 00000011 3d 2 bit 00011100 28d 00000001 1d Bạn có nhận xét gì ? Khương Đại Thể Slide 35/68
  36. Ví dụ: 0000 0000 0000 0011 0000 0000 0000 0111 0000 0000 0000 0100 7*4 → 28 7/4 → 1 Khương Đại Thể Slide 36/68
  37. 6.1.5. Các toán tử khác Ép kiểu (type casting) : – (kiểuT) x – kiểuT (x) Toán tử 3 ngôi: BTĐK ? X : Y; Quản lý bộ nhớ: – sizeof(biến) : Lấy kích thước byte của ‘biến’ – sizeof(kiểu dữ liệu) : Lấy kích thước byte của ‘kiểu dữ liệu’ – new : Cấp phát động một vùng nhớ – delete : Trả một nhớ đã được cấp phát động – &biến : Lấy địa chỉ bộ nhớ của ‘biến’ (địa chỉ chiếm 4 byte ở DOS) Khương Đại Thể Slide 37/68
  38. Ví dụ về ép kiểu lớn sang kiểu nhỏ 0000 0001 0000 0000 m=256 0000 0000 c Ép kiểu lớn sang kiểu nhỏ Khương Đại Thể Slide 38/68
  39. Ép kiểu tự động Kiểu kết qủa của 1 biểu thức là kiểu lớn nhất của toán hạng tham gia int n=3; long t=123; double x=5.3; biểu thức. 3*n + 620*t – 3*x (int*int) + (int*long) - (int*double) int + long - double Hãy giải thích vì sao long - double chương trình sau double cho kết qủa sai? Theo bạn, một hộ sử dụng 155 kwh điện một tháng và tính tiền theo công thức sau sẽ cho kết qủa đúng hay sai? 0111 1111 1111 1111 + t =100*650+50*850+5*1150; 0000 0000 0000 0001 1000 0000 0000 0000 Khương Đại Thể Slide 39/68
  40. 6.2. Độ ưu tiên của toán tử – Operator Precedence Thứ tự mà một toán tử được thực hiện khi biểu thức có nhiều toán tử. Khương Đại Thể Slide 40/68
  41. Độ ưu tiên của toán tử TT Phép toán Trình tự kết hợp 1 () [] Trái qua phải Nhìn chung độ ưu tiên: 2 ! ~ & –(dấu trừ) ++ (type ) sizeof Phải qua trái 3 * ( phép nhân ) / % Trái qua phải – Cặp ngoặc từ trong ra 4 + – (phép trừ) Trái qua phải ngoài 5 > Trái qua phải – Toán tử số học, nhân chia 6 >= Trái qua phải trước cộng trừ sau. 7 == != Trái qua phải – Toán tử so sánh 8 & Trái qua phải – Toán tử luận lý 9 ^ Trái qua phải – Toán tử gán 10 | Trái qua phải 11 && Trái qua phải 12 || Trái qua phải 13 ?: Phải qua trái = += -= *= /= %= >= &= ^= |= 15 , Trái qua phải Khương Đại Thể Slide 41/68
  42. 6.3. Biểu thức – Expressions Sự kết hợp đúng cách của hằng, biến, hàm, toán tử Hàm trong biểu thức là một tác vụ cho một trị duy nhất và thuộc kiểu cơ bản. Các hàm toán học được khai báo trong math.h Khương Đại Thể Slide 42/68
  43. Tham khảo thư viện toán học của C Gõ vào màn hình soạn thảo: math.h Để con nháy dưới từ math, Gõ Ctrl + F1 Khương Đại Thể Slide 43/68
  44. Chương 7 NHẬP XUẤT DỮ LIỆU TRONG C Khương Đại Thể Slide 44/68
  45. Nội dung Các hàm nhập dữ liệu chuẩn Các hàm xuất dữ liệu chuẩn Khương Đại Thể Slide 45/68
  46. 7.1. Nhập – Input Macro: – int getchar(); // nhận 1 ký tự từ bàn phím, // không in ra màn hình Functions: – int getch(); // tương tự như getchar() – int getche(); // nhận 1 ký tự từ bàn phím và // in ra màn hình – char* gets(char *s); // nhận chuỗi ký tự – int scanf(char *format, [, address, ]); Khương Đại Thể Slide 46/68
  47. 7.2. Xuất – Output Macro: – int putchar(int c); // xuất ký tự c ra màn hình. Functions: – int putch(int c); // tương tự như putchar() – int puts(const char *s); // xuất chuỗi ký tự ra // màn hình – int printf(const char *format [, argument, ]); – int cprintf(const char *format [, argument, ]); Khương Đại Thể Slide 47/68
  48. Ví dụ: Khương Đại Thể Slide 48/68
  49. Chương 8 CẤU TRÚC ĐIỀU KHIỂN TRONG C Khương Đại Thể Slide 49/68
  50. Nội dung: Câu lệnh đơn Khối lệnh Cấu trúc chọn Cấu trúc lặp Ngắt điều khiển Khương Đại Thể Slide 50/68
  51. 8.1. Câu lệnh đơn – Simple statement Là một câu lệnh đơn giản như: – Khai báo hằng, biến – Gán trị cho biến – Kết thúc bằng dấu chấm phẩy ; Khương Đại Thể Slide 51/68
  52. 8.2. Khối lệnh – Block/compound statement Gồm một nhóm câu lệnh lại thành một khối trong cặp ngoặc nhọn { }. Kết thúc 1 khối lệnh không cần dấu chấm phẩy. Khối lệnh được xem là một câu lệnh. Khương Đại Thể Slide 52/68
  53. 8.3. cấu trúc chọn – Select structure Còn gọi là cấu trúc rẽ nhánh (branching). Dựa trên một điều kiện hay một dữ liệu để xác định một hướng thực thi chương trình. Cấu trúc chọn 1/2: if else Cấu trúc chọn 1/n : switch case Khương Đại Thể Slide 53/68
  54. 8.3.1. Cấu trúc chọn ½ : if else Cú pháp : if (condition) CâuLệnh_1; else phải đi với if ngay trước đó [ else CâuLệnh_2;] Biểu thức điều kiện được tính toán (trả trị 0: sai, 1 hay khác 0:đúng) trước khi rẽ nhánh. condition no condition no ? ? yes yes CâuLệnh CâuLệnh_1 CâuLệnh_2 Khương Đại Thể Slide 54/68
  55. Ví dụ Cả 2 chương trình cùng cho một kết qủa Hãy vẽ lưu đồ cho 2 chương trình này và tìm sự khác biệt giữa chúng Khương Đại Thể Slide 55/68
  56. Ví dụ về một điều kiện thỏa phải làm nhiều lệnh Bạn giải thích thế nào về lỗi trong chương trình này? Khương Đại Thể Slide 56/68
  57. Ví dụ về if lồng nhau - nesting if statement Bạn hãy diễn đạt chương trình trên bằng ngôn ngữ tự nhiên. Bạn hãy vẽ lưu đồ cho chương trình trên Khương Đại Thể Slide 57/68
  58. 8.3.2. Cấu trúc chọn 1/n – switch case Dựa trên trị một biểu thức số nguyên hoặc ký tự (kiểu có thứ tự) để rẽ nhánh. switch (Bt) { case c1: CácCLệnh_1;break; thân case c2: CácCLệnh_2;break; Cấu trúc case c3: CácCLệnh_3;break; Bt Switch case default: CácCLệnhCuối; c1 other } c2 c3 • c1,c2,c3, là các hằng số nguyên hoặc ký tự. • Nếu không cóbreak , câu lệnh kế tiếp được thực thi cho đến khi gặp break, hoặc hết thân của switch. • Các case đóng vai trò điểm nhập của một lựa chọn. Khương Đại Thể Slide 58/68
  59. Ví dụ: Bài toán người cha thưởng con Theo bạn, người con được thưởng mấy cái áo và bao nhiêu tiền ? Khương Đại Thể Slide 59/68
  60. 8.4. Cấu trúc lặp – Loops Cấu trúc lặp while Cấu trúc lặp do while Cấu trúc lặp for Khương Đại Thể Slide 60/68
  61. 8.4.1. do while Loops, while Loops KhởiTạo; KhởiTạo; do Thực thi trước while (BiểuThứcĐiềuKiện) { Kiểm tra sau Khối lệnh; { Tăng/ giảm; Khối lệnh; Kiểm tra trước } Tăng/ giảm; Thực thi sau while(BiểuThứcĐiềuKiện); } Khởi tạo Khởi tạo no Khối lệnh BTĐK yes Tăng/ giảm Khối lệnh yes no BTĐK Tăng/ giảm Khương Đại Thể Slide 61/68
  62. 8.4.2. for Loops Kiểm tra điều kiện for (KhởiTạo ; Biểu thứcĐiềuKiện; Tăng/giảm) trước khi thực thi { Khối lệnh; } KhởiTạo; Khởi tạo for ( ; Biểu thứcĐiềuKiện ; Tăng/giảm) { no Khối lệnh; BTĐK } yes KhởiTạo; Khối lệnh for ( ; ĐiềuKiện ;) { Tăng/ giảm Khối lệnh; Tăng/giảm; } Khương Đại Thể Slide 62/68
  63. Chuyển for → while for ( Khởi tạo ; BTĐK ; Tăng/Giảm ) { S=0; for (i = 1; i <= n; i = i + 1) Khối lệnh; { S = S + i; } } Khởi tạo ; S=0; while ( BTĐK ) i = 1; { while(i <= n) { Khối lệnh; S = S + i; i = i + 1; Tăng/Giảm; } } Khương Đại Thể Slide 63/68
  64. Thí dụ: S= 1+2+3+4+ +10 Khương Đại Thể Slide 64/68
  65. 8.5. Ngắt điều khiển – Control statement 3 tình huống ngắt: – Ngắt cả chương trình: exit(0); // stdlib.h – Ngắt một chương trình con(function): return [Exp]; – Ngắt 1 cấu trúc switch hay loops • break; // ngắt ngang • continue; // bỏ qua 1 lần lặp Câu lệnh return sẽ được bàn đến trong Hàm. Câu lệnh goto không khuyến khích sử dụng. Khi gặp câu lệnh break, cấu trúc switch hay Loops đang được thực thi sẽ bị cắt ngang để lệnh kế sau đó được thực thi (được gọi là chuyển điều khiển sang lệnh kế tiếp). Khương Đại Thể Slide 65/68
  66. Thí dụ về break và continue với loops Khương Đại Thể Slide 66/68
  67. Xem trợ giúp về một file thư viện Ctrl + F1 Khương Đại Thể Slide 67/68
  68. Xin cám ơn Khương Đại Thể Slide 68/68