Phương pháp lập trình - Chương 1: Khái niệm cơ bản

Nội dung text: Phương pháp lập trình - Chương 1: Khái niệm cơ bản

1. MƠN HỌC PHƯƠNG PHÁP LẬP TRÌNH Bài giảng mơn Phương pháp lập Trình
2. Giới thiệu ◆ Mục tiêu mơn học Cung cấp cho sinh viên kiến thức căn bản về kỹ thuật lập trình và lập trình theo tiếp cận hướng đối tượng, một phương pháp lập trình rất thơng dụng hiện nay. ◆ Nội dung – Một số thuật ngữ liên quan đến máy tính và lập trình. – Sơ lược về ngơn ngữ lập trình – Ngơn ngữ minh họa Pseudo code và C/C++ – Các giải thuật cơ bản ◆ Kỹ năng tư duy và thực hành trên ngơn ngữ cụ thể. Trang 2
3. Phương thức ◆ Phương thức học – Giờ lý thuyết: giảng và báo cáo – Giờ thực hành tại phịng máy ◆ Kiểm tra và thi – Kiểm tra thực hành: kỹ năng lập trình – Thi lý thuyết : trắc nghiệm khách quan ◆ Tài liệu tham khảo – Slide bài giảng Lập Trình Căn Bản – Giáo trình Phương Pháp Lập trình – Khoa CNTT ◆ Tài liệu khác – CDROM bài tập và thực hành Trang 3
4. Chương 1 Khái niệm cơ bản ◆Một số khái niệm cơ bản về –Máy tính & chương trình máy tính –Ngơn ngữ lập trình ,translator, ◆Giải thuật và flow chart –Giải thuật & biểu diễn giải thuật –Flowchart ◆Cơng cụ phát triển –Cơng cụ IDE, Compiler –Error & debug Bài giảng mơn Phương pháp lập Trình
5. Máy tính - Computer ◆ Máy tính Analog ◆ Máy tính số – Hệ nhị phân – Máy tính lập trình được – Mơ hình máy Turing và Von Newman – Các thế hệ máy tính ◆ Đặc tính chung – Khả năng tính tốn – Khả năng thực hiện các phép tốn logic – Tốc độ tính tốn cao – Làm theo chỉ thị Trang 5
6. Kiến trúc máy tính ◆ Máy tính (Computer system) Bao gồm nhiều thiết bị phần cứng (hardware devices) ◆ Keyboard ◆ Screen (monitor) ◆ Disks ◆ Memory ◆ Processing Units ◆ Hệ điều hành (Operating System – OS) ◆ Phần mềm (software) – Cơng dụng: êệ thống, ứng dụng, cơ sở dữ liệu – Mơi trường hoạt động: OS, Network, WEB, Server, Trang 6
7. Chương trình máy tính ◆ Chương trình – Danh mục các trang thiết bị, tài nguyên sử dụng – Tiến trình sử dụng các tài nguyên và thực hiện các cơng việc định trước – Kết quả thực hiện ◆ Chương trình máy tính – Tập hợp các lệnh được liệt kê theo một trình tự nhất định – Các dữ liệu sẽ được nhận – Các tài nguyên cần sử dụng – Các kết quả sẽ cĩ được – Mục tiêu: xử lý dữ liệu theo yêu cầu định trước ◆ Lập trình: viết chương trình cho máy tính Trang 7
8. Ngơn ngữ lập trình ◆ Ngơn ngữ lập trình – Phương tiện để viết chương trình cho máy tính – Hàng trăm ngơn ngữ lập trình khác nhau – Những quy định về cú pháp (syntax) & ngữ nghĩa (semantic) – Máy tính cĩ thể hiểu được ◆ Phân chia làm 3 nhĩm chính – Ngơn ngữ máy - Machine languages ◆ Ngơn ngữ duy nhất của máy tính - CPU – Hợp ngữ - Assembly languages – Ngơn ngữ cấp cao - High-level languages Trang 8
9. Ngơn ngữ máy - Machine languages ◆ Ngơn ngữ duy nhất được máy tính (CPU) hiểu trực tiếp. ◆ Được xác định bởi tập lệnh của CPU – Phụ thuộc vào máy tính cụ thể – Dạng nhị phân {0,1}* – Rất khĩ đọc hiểu – Khĩ cĩ khả năng viết chương trình trực tiếp ◆ Khĩ nhớ hàng chục ngàn lệnh dạng {0,1}* ◆ Rất khĩ xác định & sửa lỗi ◆ Khơng được sử dụng trong thực tế để viết chương trình ◆ Nền tảng xây dựng hợp ngữ Trang 9
10. Hợp ngữ - Assembly Languages ◆ Sử dụng các từ khĩa tiếng Anh cho các lệnh hay nhĩm lệnh của mã máy. ◆ Được dịch sang mã máy khi thực hiện ◆ Chuyển đỗi nhanh chĩng ◆ Dễ đọc và dễ hiểu hơn ◆ Vẫn tương đối khĩ sử dụng do – Các lệnh cịn đơn giản nên phải dùng nhiều lệnh. – Chưa cĩ những cấu trúc điều khiển thuận tiện – Khả năng tìm và sửa lỗi cũng chưa thuận tiện. ◆ Nền tảng xây dựng các ngơn ngữ cấp cao Trang 10
11. Ngơn ngữ cấp cao ◆ Một câu lệnh diễn tả nhiều động thái ◆ Cĩ cấu trúc ngày càng giống ngơn ngữ tự nhiên (tiếng Anh) ◆ Được dịch sang assembly hay mã máy bằng các chương trình dịch trước khi thực thi. – Source code & Executed code ◆ Được phân làm nhiều lớp – Lập trình goto – Lập trình cấu trúc – Structured – Lập trình hướng đối tượng – Object Oriented – Các dạng khác Trang 11
12. Học ngơn ngữ lập trình ◆ Học ngữ pháp – Quy tắc ngữ pháp – Từ vựng – Cấu trúc câu ◆ Ngữ nghĩa của các lệnh ◆ Các “thành ngữ” ◆ Học ngơn ngữ lập trình VS. Học ngơn ngữ tự nhiên – Quy tắc ngữ pháp đơn giản – Từ vựng ít, tự quy định – Cấu trúc câu đơn giản ◆ Hạn chế và khĩ khăn của sử dụng ngơn ngữ lập trình. Trang 12
13. Chương trình dịch ◆ Dùng để dịch từ một ngơn ngữ lập trình này sang ngơn ngữ lập trình khác ◆ Mục tiêu cuối cùng là dịch sang mã máy để cĩ được executed code –> chương trình thực thi ◆ Phân loại: – Intepreter – thơng dịch – Compiler – biên dịch – Intepreter vs. Compiler ◆ Cơng cụ phát triển – Integrated Development Environment (IDE) – Soạn thảo – Dịch và sửa lỗi chương trình – Chạy thử và sửa lỗi Trang 13
14. Một số khái niệm khác ◆ Lỗi và sửa lỗi – Syntax error – lỗi ngữ pháp – Semantic error- lỗi ngữ nghĩa – Runtime error - Lỗi thực thi ◆ Debug – Tìm và sửa lỗi ◆ Dữ liệu, kiểu dữ liệu – Các kiểu dữ liệu cơ bản ◆ Số nguyên, Số thực, Kí tự – Kiểu dữ liệu cĩ cấu trúc: mảng, chuỗi, cấu trúc, ◆ Biến (Variable) & Hằng (Constant) ◆ Giải thuật: khái niệm, cơng cụ biểu diễn ◆ Flow chart – lưu đồ Trang 14
15. Flow chart Start • Start /Begin bắt đầu giải thuật. Chỉ cĩ 1 và chỉ 1 điểm START. • Dịng xử lý • Input / Output dữ liệu xuất/nhập • Đặc tả thao tác xử lý hay tính tốn dữ liệu No Điều kiện • Điều khiển rẽ nhánh Yes Giá trị xét phân nhánh • Phát biểu rẽ nhánh khác Trường hợp 1 Trường hợp i Khác Stop • Stop/End kết thúc của giải thuật. Cĩ thể cĩ một hoặc nhiều điểm STOP. Trang 15
16. Flow chart ◆ Ưu điểm – Trình bày trực quan giải thuật – Độc lập với ngơn ngữ tự nhiên – Độc lập với ngơn ngữ lập trình – Bảo đảm khả năng lập trình – Cho phép dễ dàng kiểm tra giải thuật ◆ Nguyên tắc kiểm tra – Đi từ START theo bất cứ đường nào cũng phải đến một điểm dừng STOP – Khơng cĩ sự quay vịng vĩnh viễn – Khơng cĩ sự kết thúc lưng chừng Trang 16
17. Flow chart Start Algorithms Giải phương trình ax + b = 0 Nhập a, b Yes Yes a=0 ? b=0 ? No No X=-b/a Khơng cĩ nghiệm Vơ số nghiệm Stop Trang 17
18. Cấu trúc lệnh cơ bản ◆ if (condition) Statement; ◆ if (condition) Statement 1; else Statement 2; ◆ switch(BiểuThứcChọn) { case hằng 1: S1;break; case hằng 2: S2;break; . case hằng n: Sn;break; default: S0; } ◆ while (condition) Statement; ◆ do{ Statement }while (condition); ◆ for (BT1; ĐK ; BT2) Statement; Trang 18
19. Chu kỳ sống của phần mềm ◆ Thu thập yêu cầu ◆ Phân tích thiết kế ◆ Phát triển chương trình - codeing – Xác định giải thuật – Viết code và dịch thử , hiệu chỉnh các lỗi syntax ◆ Thử nghiệm - Testing – Chạy thử với các dữ liệu mẫu để kiểm tra lỗi semantic và runtime ◆ Vận hành và bảo trì ◆ Phát triển theo yêu cầu Trang 19
20. Một số ngơn ngữ lập trình ◆ Lập trình goto – Assembly – Basic ◆ Lập trình cấu trúc – Pascal, C – Foxpro ◆ Lập trình hướng đối tượng – Java, C++, Object Pascal, ◆ Khác – Prolog, LISP, Visual basic (VB), VC++, J++, Delphi, ASP, PHP, – Visual studio .NET: VB.NET, ASP.NET, C++.NET, C# Trang 20
21. Chương 2 Dữ liệu & cấu trúc chương trình ◆Các khái niệm cơ bản về dữ liệu và biểu diễn dữ liệu trong máy tính ◆Khai báo dữ liệu trong chương trình ◆Một số phép tốn cơ bản ◆Cấu trúc cơ bản một chương trình C/C++ Bài giảng mơn Phương pháp lập Trình
22. Danh hiệu ◆ Khái niệm “Danh hiệu” – Là tên của các đối tượng khác nhau trong lập trình, dùng để phân biệt giữa đối tượng này với đối tượng khác. – Các đối tượng thường được đặt tên bằng danh hiệu: biến, hằng, chương trình con, ◆ Qui tắc ngữ pháp của danh hiệu: – Bắt đầu bằng chữ cái (A-Z, a-z) hay dấu gạch dưới ( _ ) – Theo sau là chữ cái, dấu gạch dưới hay chữ số. – Với Pascal khơng phân biệt CHỮ HOA hay chữ thường – Một số ngơn ngữ cĩ phân biệt như Java, ◆ Ví dụ: X , BienDem, Bien_dem, X1 , X2 , X3 , x1,x2,x3 ◆ Ví dụ sai: 101X3, (X1), Bien Dem Trang 22
23. Danh hiệu (tt) ◆ Danh hiệu gồm 2 loại: – Danh hiệu thuộc ngơn ngữ (Pre-defined) ◆ Do ngơn ngữ quy định trước ý nghĩa của nĩ. ◆ Được dùng cho các đối tượng cĩ sẵn trong ngơn ngữ – Ví dụ: int, cin, cout, – Danh hiệu do người sử dụng đặt ra (user defined) ◆ Do người sử dụng tự qui ước và qui định ý nghĩa của nĩ trong chương trình nguồn (source code) – Ví dụ: abc, xyz1, xyz2, delta, namsinh, tinh_giai_thua ◆ Từ dành riêng: Là những từ do ngơn ngữ quy định sẵn như là một bộ phận cấu thành ngơn ngữ đĩ. – Ví dụ: if, else, do, while ◆ Ký hiệu đặc biệt: là những ký tự cĩ ý nghĩa được quy định trước trong ngơn ngữ. – Ví dụ: + - * / > >= := <> ; , ( ) @ [ ] Trang 23
24. Qui ước đặt tên danh hiệu ◆ Qui tắc đặt tên danh hiệu – Tuân thủ quy tắc ngữ pháp của danh hiệu – Khơng được trùng lắp với danh hiệu thuộc ngơn ngữ hoặc đã được định nghĩa. – Nên sử dụng các tên gợi nhớ ◆ Tên gợi nhớ? – Tên mà khi đọc đến sẽ giúp ta biết được ý nghĩa của đối tượng mang tên đĩ. – Lợi ích của tên gợi nhớ: giúp chương trình dễ đọc, dễ hiểu & dể kiểm tra. if (ABC < 0) cout<<“ Phuong trinh vo nghiem”; ABC khơng gợi nhớ if (Delta < 0) cout<<“ Phuong trinh vo nghiem”) Delta là tên gợi nhớ Trang 24
25. Kiểu dữ liệu (data type) ◆ Kiểu dữ liệu là gì? – Một kiểu dữ liệu là một qui định về hình dạng, cấu trúc, miền giá trị, cách biểu diễn và cách xử lý một loại dữ liệu thực tế nào đĩ trong máy tính. Kiểu int biểu diễn số nguyên từ -32767 đến 32768 và thực hiện được các phép tốn cộng, trừ, nhân, chia, div, mod Kiểu char biểu diễn các ký tự và biểu diễn giữa cắp dấu nháy đơn. ‘A’ Cĩ thể thực hiện phép so sánh, khơng thể cộng, trừ, nhân, chia ◆ Mọi dữ liệu muốn được xử lý bằng máy tính thì phải quy về một kiểu dự liệu nào đĩ mà ngơn ngữ lập trình đĩ hiểu được. ◆ Số kiểu dữ liệu là một yếu tố so sánh ngơn ngữ lập trình. Càng nhiều kiểu thì càng thuận lợi cho xử lý. ◆ Bao nhiêu kiểu dữ liệu thì đủ? Trang 25
26. Các kiểu dữ liệu ◆ Các kiểu dữ liệu đơn giản – Kiểu liên tục: float, double – Kiểu rời rạc: int, char, liệt kê, – Các kiểu dữ liệu cĩ cấu trúc/Kiểu do người dùng định nghĩa – MÃNG – CẤU TRÚC – TẬP TIN – CHUỖI – Kiểu pointer (con trỏ) Trang 26
27. Kiểu dữ liệu cơ sở ◆Kiểu int: biểu diễn các số nguyên dạng thập phân. Chiếm 2 byte trong bộ nhớ, miền giá trị -32767 đến 32768 ◆Kiểu float: biểu diễn các số thực dạng thập phân hay dạng lũy thừa 10 bằng ký tự E. (3.2E8) Chiếm 4 byte trong bộ nhớ.Miền giá trị nhỏ nhất đến (1.9E-39) và lớn nhất đến (1.7E38) ◆Kiểu char: biểu diễn cho dữ liệu ký tự. Chiếm 1 byte trong bộ nhớ . Miền giá trị theo bảng mã ASCCI. Biểu diễn bằng ký tự nằm giữa hai dấu nháy đơn 'A’, 'a’, – Bảng mã ASSCI chuẩn và mở rộng. – Bảng mã và fonts – Các vấn đề bản mã tiếng Việt 1 byte, 2 byte, Unicode Một số phép tốn: so sánh, int ('F’) = 70 , char(65) = 'A’ Trang 27
28. Cấu trúc đơn giản chương trình C/C++ ◆ Phần Khai báo ◆ Các #include Chứa các khai báo tài ◆ Các #define nguyên sẽ sử dụng ◆ Các prototype hàm Các khai báo nào khơng cần thiết cĩ thể bỏ đi. ◆ Các biến tồn cục ◆ Hàm main() ◆ { ◆ Phần Thân Chương Các khai bao biến cục bộ , hằng trình các phát biểu, câu lệnh; Nội dung các câu lệnh mơ tả ◆ } cơng việc sẽ được thực hiện. ◆ Định nghĩa các hàm Trang 28
29. Các Khai báo trong C/C++ ◆ #define tênhằng giátrịhằng ◆ const kiểu tênhằng=giátrịhằng; ◆ #define PI 3.14 ◆ const int PI=3.14159; Hằng và ý nghĩa sử dụng hằng trong chương trình. ◆ Biến và khai báo biến – Biến: là ơ nhớ lưu trữ dữ liệu và thay đỗi được. Cĩ kiểu dữ liệu tương ứng. kiểu dữ liệu tên biến; Trang 29
30. Biểu thức ◆ Các phép tốn quan hệ: != == , , = cho kết quả bằng 0 hoặc 1 ( ‘a’ > ‘B’ ) cĩ giá trị bằng 0 ◆ Các phép tốn logic !, &&, || ◆ Các phép tốn số học: – +, - , * , /, % ◆ Phép gọi hàm: gọi một chương trình con loại hàm số tương đương với một phép tốn ◆ Biểu thức: là một cơng thức tính tốn tạo từ các biến, hằng, các giá trị cụ thể, các phép tốn và dấu (, ) . Kiểu dữ liệu trả về cũng là kiểu dữ liệu của biểu thức. A+2*b(c-d) Biến là một biểu thức Trang 30
31. Phát biểu gán và thủ tục xuất nhập ◆ Phát biểu gán = Gán một giá trị của một biểu thức cho một biến TenBien = Bieuthuc; ◆ Các thao tác xuất nhập: – cin>>B1>>B2; – cout >a>>b ; 12 15 Trang 31
32. Chương 3 Các phát biểu điều khiển ◆Các phát biểu điều khiển ◆Phát biểu điều khiển và flowchart ◆So sánh và đánh giá Bài giảng mơn Phương pháp lập Trình
33. Tổng quan ◆ Phát biểu điều khiển: là những dịng lệnh dùng để điều khiển hoạt động của chương trình. ◆ Các phát biểu điều khiển cơ bản 1. Phát biểu gán (assignment statement) 2. Các phát biểu điều khiển (control statements) 1. Phát biểu ghép { } 2. Phát biểu điều kiện if 3. Phát biểu điều kiện if else 4. Phát biểu điều kiện switch case 5. Phát biểu lặp while 6. Phát biểu lặp for 7. Phát biểu lặp do while 8. Phát biểu goto, break, continue 9. Phát biểu gọi hàm (function call): gọi các hàm Trang 33
34. Phát biểu ghép { }; ◆ Dùng để ghép nhiều phát biểu thành một phát biểu. ◆ Cú pháp : { các phát biểu;} Ví dụ { { S1; S1 S1; t =x; S2; S2 S2; x =y; y =t; Sn Sn; Sn; cout<<“Hello!”; } } { N phát biểu } 1 phát biểu Trang 34
35. Phát biểu if ◆ Dùng để thực hiện hay khơng một phát biểu theo một điều kiện. Chỉ cĩ 1 ◆ Cú pháp phát biểu trong thân if (condition) của if statement; ◆ Ví dụ Yes Condition if (Delta > 0) No { Statements X1= (-b + sqrt(Delta))/(2*a); X2= (-b - sqrt(Delta))/(2*a); } Trang 35
36. Phát biểu if else ◆ Dùng để chọn lựa phát biểu nào sẽ được thực hiện giữa 2 phát biểu. ◆ Cú pháp if (condition) statement1 else statement2 ; ◆ Ví dụ if (Delta > 0) Condition { No X1= (-b + sqrt(Delta))/(2*a); Yes X2= (-b - sqrt(Delta))/(2*a); Statement1 Statement2 } else { cout<<(‘Cịn xét tiếp’);} Trang 36
37. Trường hợp đặc biệt ◆ Xét phát biểu sau: ◆ if (ĐK1) if (ĐK2) S1; else S2; ? else else ◆ else sẽ thuộc về if nào gần nhất chưa cĩ ELSE Yes ĐK2 ĐK2 No No Yes S1 S2 Trang 37
38. Phát biểu switch case ◆ Dùng để chọn một switch(BiểuThứcChọn) trong số những phát { biểu để thực hiện tùy case hằng 1: S1;break; theo giá trị của biểu case hằng 2: S2;break; . thức chọn. case hằng n: Sn;break; ◆ Các nhãn case: chỉ ra các trường hợp phân default: S0; nhánh. } BiểuThứcChọn ◆ Các nhãn case là một hay nhiều giá trị hằng rời rạc theo sau là dấu : Hằng1 Hằng 2 Hằng N default: và một phát biểu tương S1 S2 SN S0 ứng. Trang 38
39. Phát biểu while ◆ Dùng để lặp đi lặp lại nhiều lần ◆ Ví dụ: một cơng việc nào đĩ. gt =1; i=1 ; ◆ Cú pháp while (i<n) do while(ĐK) statement; { ◆ while kiểm tra điều kiện trước rồi i=i+1; mới thực hiện phát biểu. gt=gt*i; ◆ Số lầp lặp là khơng biết trước. } ◆ Số lần lặp tối thiểu là 0 và tối đa là khơng xác định. ◆ Chú ý: Trong thân của while phải cĩ ít nhất một phát biểu cĩ khả Yes năng thay đổi giá trị của điều kiện. S1 ĐK Nếu khơng sẽ lặp vơ tận (infinite loop) No Trang 39
40. Phát biểu do while ◆ Dùng để lặp đi lặp lại nhiều lần ◆ Ví dụ: một cơng việc nào đĩ. gt=1; i=1 ◆ Cú pháp do{ do{ statements; } while (ĐK); i:=i+1; ◆ do while thực hiện xong các phát gt:=gt*I; biểu rồi mới kiểm tra điều kiện. }while( i<=n); ◆ Số lầp lặp là khơng biết trước. ◆ Số lần lặp tối thiểu là 1 và tối đa S1 là khơng xác định. ◆ Chú ý: Trong thân của do while phải cĩ ít nhất một phát biểu cĩ No khả năng thay đổi giá trị của điều ĐK kiện. Nếu khơng sẽ lặp vơ tận Yes (infinite loop) Trang 40
41. Phát biểu for ◆ Dùng để lặp lại một cơng việc nào đĩ với số lần lặp là xác định được. ◆ Sử dụng biến đếm và biểu thức cận để xác định số lần lặp lại. ◆ for (BT1;ĐK;BT2) Statements; Hoạt động của cấu trúc for: cấu trúc for làm việc theo các bước sau đây: b1.Xác định biểu thức 1 b2.Xác định biểu thức 2. b3.Tuỳ thuộc vào tính đúng sai của biểu thức 2 mà máy sẽ lựa chọn một trong hai nhánh:Nếu biểu thức 2 có giá trị 0(sai) máy sẽ ra khỏi for, ngược lại nếu biểu thức khác 0( đúng) máy sẽ thực hiện các câu lệnh trong thân for, khi gặp dấu } cuối cùng trong thân for hoặc gặp câu lệnh continue máy sẽ chuyển đến bước 4( khởi đầu lại) b4.Tính biểu thức 3 sau đó quay trở lại bước 2 để bắt đầu một vòng mới của chu trình. Trang 41
42. Một số chú ý với phát biểu for ◆ Biểu thức 1 bao giờ cũng chỉ được tính một lần. Còn biểu thức 2,3 và thân vòng lặp có thể được lặp đi lặp lại nhiều lần. ◆ -Khi biểu thức 2 vắng mặt thi thì nó luôn được xem là đúng. Trong trường hợp này việc ra khỏi chu trình for cần được thực hiện nhờ câu lệnh break hoặc return ( viết trong thân chu trình) ◆ -Trong dấu ngoặc tròn sau từ khoá for gồm 3 thành phần cách nhau bởi dấu chấm phẩy, trong mỗi phần không những có thể viết một biểu thức mà còn có quyền viết một dãy biểu thức phần cách với nhau bởi dấu phẩy. Khi đó biểu thức trong mỗi phần sẽ được xác định từ trái qua phải. Tính đúng sai của dãy biểu thức trong phần thứ 2 được hiểu là tính đúng sai của biêu thức cuối cùng trong dãy này. ◆ -Bên trong thân cấu trúc for có thể dùng các cấu trúc for khác. -Lệnh break có thể được sử dụng để thoát sớm khỏi vòng lặp for.( while, do while) ◆ -khi gặp continue thì máy sẽ bỏ qua các câu lệnh còn lại trong thân chu trình để chuyển đến xét biểu thức 3. Trang 42
43. Chương 4 Các kiểu dữ liệu do người dùng định nghĩa Các kiểu dữ liệu rời rạc Các kiểu dữ liệu cĩ cấu trúc Một số giải thuật trên aray. Khái niệm cơ bản về cấu trúc dữ liệu Bài giảng mơn Phương pháp lập Trình
44. Bài tập ◆ Các bài tập trong sách giáo trình ◆ Bài tập nhân 2 ma trận. ◆ Bài tập xác định ma trận đối xứng ◆ Bài tập quản lý điểm sinh viên dùng mảng và cấu trúc ◆ Các bài tập khác bằng chương trình C/C++ Trang 44
45. Chương 4:Kiểu dữ liệu MẢNG ◆ Định nghĩa: Mảng là một dãy gồm nhiều phần tử cùng một kiểu. – Các phần tử cĩ mối quan hệ về vị trí trong dãy được xác định bằng chỉ số (index). Chính là thứ tự về vị trí của nĩ trong dãy ◆ Khai báo dãy: kieudulieu tenmang[SPT]; ◆ SPT là số phần tử tối đa của mảng ◆ SPT là kiểu đếm được ◆ Phần tử đầu tiên của mảng cĩ chỉ số = 0 Trang 45
46. Khởi tạo các giá trị của mảng ◆ int A[ 10 ]; /* khai báo mảng A */ ◆ A[ 0 ] = 1; /* Khởi tạo các giá trị của mảng 1, 2, 3 10 */ ◆ A[ 1 ] = 2; ◆ A[ 2 ] = 3; ◆ A[ 3 ] = 4; ◆ A[ 4 ] = 5; ◆ A[ 5 ] = 6; ◆ A[ 6 ] = 7; ◆ A[ 7 ] = 8; ◆ A[ 8 ] = 9; ◆ A[ 9 ] = 10; Trang 46
47. Truy xuất phần tử mảng ◆ Cĩ thể truy xuất hoặc thay đổi giá trị của mảng thơng qua tên mảng và chỉ số. ◆ Ví dụ: Khai báo int A[10]; – A[0] = 10; //Gán giá trị 10 cho phần tử đầu tiên – A[9] = 100;// Gán giá trị 100 cho phần tử cuối cùng ◆ Chỉ số phần tử cuối cùng của mảng 10 -1 ◆ Khởi tạo giá trị mảng dùng vịng lặp – int A[ 5000 ]; – /* Khởi tạo 5000 phần tử (chỉ số từ 0 đến 4999) for (i = 0; i < 5000; i++) { A[ i ] = 0; } Trang 47
48. Trang 48
49. Trang 49
50. Một số đặc tính của kiểu array ◆ Số phần tử của kiểu array là cố định ngay từ khi khai báo. Dù là ta dùng bao nhiêu phần tử thì cũng chiếm đúng số bộ nhớ mà dãy đã khai báo. ◆ Do đĩ thơng thường phải khai báo dư hơn số thường dùng để tránh bị thiếu => lãng phí bộ nhớ. ◆ Các phần tử của dãy được xếp liên tục trong bộ nhớ do đĩ: – Cho phép khả năng truy xuất ngẫu nhiên => nhanh – Cần cĩ vùng nhớ trống liên tục đủ lớn khi cấp phát bộ nhớ cho dãy. => khĩ cấp phát. Trang 50
51. Một số giải thuật trên mảng ◆ Khi tổ chức lưu trữ trên array của nhiều phần tử, thao tác thường phải thực hiện là tìm kiếm (search) và sắp xếp (sort) các phần tử trong dãy ◆ Việc tìm kiếm (search) dùng để truy vấn thống tin. ◆ Việc sắp xếp (sort) dùng để trình bày thơng tin và giúp cho thao tác search hiệu quả hơn. ◆ Một số giải thuật: – Linear search cĩ và chưa sort, Binary search – Buble sort, quick sort Trang 51
52. Linear search ◆ Xem xét từng phần tử xem cĩ phải giá trị cần tìm hay khơng cho đến khi tìm thấy hoặc hết số phần tử của array thì kết luận cĩ khơng cĩ. – Timthay := 0; for (int i= 0;i<n; i++) if(a[i]==giatricantim) timthay = i; if (timthay==0) cout<<“Khơng cĩ”; else cout<<“Cĩ tại”<< timthay<<endl; – i=1 while (i<n&&a[i]!=giatricantim) i= i + 1; ◆ Số phần tử tổng quát cần duyệt tối đa là N. Cĩ thể áp dụng cho dãy bất kỳ, tuy nhiên nếu dãy cĩ thứ tự thì cĩ thể duyệt nhanh hơn “một ít”. Trang 52
53. Binary search ◆ Áp dụng cho dãy đã cĩ thứ tự. Nguyên tắc chính là dựa vào tính thứ tự của dãy để thực hiện số phép so sánh tối thiểu bằng cách lấy phần tử giữa so sánh với giá trị cần tìm: – nếu bằng cĩ nghĩa là tìm thấy tại vị trí đĩ. – nếu khơng bằng thì phân nữa số phần tử sẽ được loại bỏ khơng cần xét vì chắc chắn khơng thể bằng. ◆ Giải thuật này cho tốc độ tìm kiếm rất cao. Ví dụ dãy cĩ 1 triệu phần tử chỉ tốn khơng đến 20 phép so sánh là đã xác định được trong khi với linear search là 1 triệu phép so sánh. Trang 53
54. Binary search – giải thuật Dãy A cĩ n phần tử từ 0 n-1 . Giá trị cần tìm là X. I =1; j =n; co =0; while (i X) j=m; else i=m; } If (co) cout<<“Tim co phan tu”<< X<<endl; else cout<<“Khong co phan tu”<< X<<endl; Trang 54
55. Trang 55
56. Bubble Sort ◆ Dùng để sắp thứ tự một dãy. ◆ Nguyên tắc : – Tìm phần tử lớn nhất đặt vào vị trí cuối cùng A[n] bằng cách so sánh lần lượt các cặp từ a[j], a[j+1] với j từ 1=> n- 1. Nếu phần tử a[i] >a[j] thì hốn đỗi 2 phần tử này – Lặp lâi bước trên với số phần tử củ dãy cịn lại giảm dần từ n -> 2 . – Khi hồn tất dãy sẽ cĩ thứ tự tăng dần. ◆ Ưu điểm của giải thuật là đơn giản. Tuy nhiên tốc độ sắp thứ tự khơng cao. ◆ Cĩ một giải thuật khác khá mạnh là QuickSort Trang 56
57. Bubble Sort – giải thuật Giải thuật bubble Sort cho dãy cĩ n phần tử và tăng dần. for (int i= 0 ;i A[j+1] ) So sánh và hốn { đổi giá trị 2 phần t= a[i]; tử. Biến t cĩ dùng a[j]=a[j+1]; kiểu dữ liệu với kiểu cơ sở của a[j+1]=t; array } Trang 57
58. Trang 58
59. Array nhiều chiều Trang 59
60. Trang 60
61. Trang 61
62. Trang 62