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

Bài giảng Kỹ thuật lập trình cơ bản (C++): Chương 4 - ThS. Trần Nguyễn Anh Chi

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:19

90
lượt xem
6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình cơ bản (C++) - Chương 4 trang bị cho người học những kiến thức về mảng một chiều. Các nội dung cụ thể trình bày trong chương này: Dữ liệu kiểu mảng, số phần tử mảng, khởi tạo giá trị cho mảng, một số thao tác trên mảng,... Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình cơ bản (C++): Chương 4 - ThS. Trần Nguyễn Anh Chi

  1. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Trường Cao đẳng Công nghệ Thông Tin Khoa Công nghệ Thông Tin CHƯƠNG 4 MẢNG MỘT CHIỀU GV: ThS. TRẦN NGUYỄN ANH CHI TpHCM, 02/2011 Đặt vấn đề Ví dụ  Chương trình cần lưu trữ 3 số nguyên? => Khai báo 3 biến int a1, a2, a3;  Chương trình cần lưu trữ 100 số nguyên? => Khai báo 100 biến kiểu số nguyên!  Người dùng muốn nhập n số nguyên? => Không thực hiện được! Giải pháp  Kiểu dữ liệu mới cho phép lưu trữ một dãy các số nguyên. 2 GV: ThS. Trần Nguyễn Anh Chi 1
  2. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Dữ liệu kiểu mảng Khái niệm  Là một kiểu dữ liệu có cấu trúc do người lập trình định nghĩa.  Biểu diễn một dãy các biến có cùng kiểu. Ví dụ: dãy các số nguyên, dãy các ký tự…  Kích thước được xác định ngay khi khai báo.  NNLT C luôn chỉ định một khối nhớ liên tục cho một biến kiểu mảng. 3 Dữ liệu kiểu mảng (tt) Khai báo []; Ví dụ 1 int Mang1Chieu[10]; 0 1 2 3 4 5 6 7 8 9 Chỉ số Mang1Chieu 1 3 -1 7 -2 9 0 4 5 -1 Giá trị Ví dụ 2 float a[7]; 0 1 2 3 4 5 6 Chỉ số a 1.2 -1 2.5 3.7 8.1 -9 5.2 Giá trị 4 GV: ThS. Trần Nguyễn Anh Chi 2
  3. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Số phần tử mảng Phải xác định cụ thể số phần tử ngay lúc khai báo, không được sử dụng biến chưa có giá trị int n1; int a[n1]; //sai int n2 = 10; int a[n2]; Nên sử dụng chỉ thị tiền xử lý #define để định nghĩa số phần tử mảng #define n3 10 int a[n3]; //  int a[10]; 5 Khởi tạo giá trị cho mảng  Khởi tạo giá trị cho mọi phần tử của mảng int a[4] = {123, 456, -789, 100}; 0 1 2 3 a 123 456 -789 100  Khởi tạo giá trị cho một số phần tử đầu mảng int a[4] = {123, -456}; 0 1 2 3 a 123 -456 0 0 6 GV: ThS. Trần Nguyễn Anh Chi 3
  4. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Khởi tạo giá trị cho mảng(tt)  Khởi tạo giá trị 0 cho mọi phần tử của mảng int a[4] = {0}; 0 1 2 3 a 0 0 0 0  Tự động xác định số lượng phần tử của mảng int a[] = {123, -456, 789, 100}; 0 1 2 3 a 123 -456 789 100 7 Truy xuất đến một phần tử trong mảng  Truy xuất thông qua chỉ số Ví dụ: cho mảng như sau: 0 1 2 3 int a[4]; 11 22 33 44 Các truy xuất:  Hợp lệ: a[0], a[1], a[2], a[3]  Không Hợp lệ: a[-2], a[-1], a[4], a[5]…  Chỉ số không hợp lệ thường cho kết quả không mong muốn 8 GV: ThS. Trần Nguyễn Anh Chi 4
  5. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Truy xuất đến một phần tử (tt) i= 0 i= 1 i= 2 i= 3 i= 4 9 Một số thao tác trên mảng Nhập mảng Xuất mảng Đếm, tính tổng, tính trung bình Tìm kiếm Kiểm tra mảng thỏa điều kiện cho trước Sắp xếp Tách / ghép mảng Chèn / xóa 10 GV: ThS. Trần Nguyễn Anh Chi 5
  6. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Nhập mảng Yêu cầu  Cho phép nhập mảng a, số lượng phần tử n Ý tưởng  Cho trước một mảng có số lượng phần tử là MAX.  Nhập số lượng phần tử thực sự n của mảng.  Nhập từng phần tử cho mảng từ chỉ số 0 đến n – 1. 0 1 2 3 n 4- 1 MAX - 1 … … … 11 Nhập mảng (tt) #define MAX 100 void NhapMang(int a[], int n) { int i; for (i=0; i
  7. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Xuất mảng Yêu cầu  Cho trước mảng a, số lượng phần tử n. Hãy xuất nội dung mảng a ra màn hình. Ý tưởng  Xuất giá trị từng phần tử của mảng từ chỉ số 0 đến n-1. 0 1 2 n-1 MAX - 1 … … … 13 Xuất mảng (tt) void XuatMang(int a[], int n) { int i; for (i = 0; i < n; i++) cout
  8. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện Yêu cầu  Cho trước mảng a, số lượng phần tử n. Hãy xuất các phần tử thỏa điều kiện nào đó. Ý tưởng  Duyệt từ đầu đến cuối mảng (từ chỉ số 0 đến n-1)  Tại vị trí thứ i, nếu a[i] thỏa điều kiện → xuất giá trị a[i]  Nếu không có giá trị nào thỏa điều kiện → xuất thông báo 15 Liệt kê các phần tử thỏa điều kiện (tt) Ví dụ 1: Liệt kê các số chẵn trong mảng void XuatChan(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2==0) cout
  9. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện (tt) void XuatChan(int a[], int n) //co thong bao { int i, flag=0; for (i = 0; i < n; i++) if(a[i]%2==0) { flag = 1; cout
  10. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Liệt kê các phần tử thỏa điều kiện (tt) void XuatSNT(int a[], int n) //co thong bao { int i, flag=0; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) { flag = 1; cout
  11. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Đếm số lượng (tt) Ví dụ 1: Đếm số lượng các số chẵn int DemChan(int a[], int n) { int i, dem=0; for (i = 0; i < n; i++) if(a[i]%2==0) dem++; return dem; } Main: int kq = DemChan(a,n); if(kq==0) cout
  12. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tính tổng/tích các phần tử thỏa đk Yêu cầu  Cho trước mảng a, số lượng phần tử n. Hãy tính tổng/tích các phần tử thỏa điều kiện nào đó. Ý tưởng  Duyệt từ đầu đến cuối mảng  Tại vị trí thứ i, nếu a[i] thỏa điều kiện → cộng dồn/nhân dồn giá trị biến tổng/tích  Trả về giá trị tính được 23 Tính tổng/tích (tt) Ví dụ 1: Tính tổng các số chẵn int TongChan(int a[], int n) { int i, tong=0, flag=0; for (i = 0; i < n; i++) if(a[i]%2==0) { flag = 1; tong+=a[i]; } Main: if(flag==1) return tong; return -1; } 24 GV: ThS. Trần Nguyễn Anh Chi 12
  13. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tính tổng/tích (tt) Ví dụ 2: Tính tích các số nguyên tố long TichSNT(int a[], int n) { int i; long tich=1; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) tich*=a[i]; return tich; } Main: 25 Tính trung bình các phần tử thỏa đk Yêu cầu  Cho trước mảng a, số lượng phần tử n. Hãy tính trung bình cộng các phần tử thỏa điều kiện nào đó. Ý tưởng  Duyệt từ đầu đến cuối mảng  Tại vị trí thứ i, nếu a[i] thỏa điều kiện → tăng giá trị biến đếm và cộng dồn  Tính trung bình = tổng/đếm  Trả về giá trị trung bình tính được 26 GV: ThS. Trần Nguyễn Anh Chi 13
  14. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tính trung bình (tt) Ví dụ 1: Tính trung bình cộng các số chẵn float TrungBinhChan(int a[], int n) { int i, dem=0, tong=0; for (i = 0; i < n; i++) if(a[i]%2==0) { tong+=a[i]; dem++; } return (float)tong/dem; } 27 Tính trung bình (tt) Ví dụ 2: Tính trung bình cộng các số nguyên tố float TrungBinhSNT(int a[], int n) { int i, dem=0, tong=0; for (i = 0; i < n; i++) if(LaSNT(a[i])==true) { tong+=a[i]; dem++; } if(dem!=0) return (float)tong/dem; return 0; } 28 GV: ThS. Trần Nguyễn Anh Chi 14
  15. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tìm kiếm giá trị thỏa đk Yêu cầu  Cho trước mảng a, số lượng phần tử n. Hãy tìm 1 phần tử thỏa điều kiện nào đó. Ý tưởng  Duyệt từ đầu đến cuối mảng  Tại vị trí thứ i, nếu a[i] thỏa điều kiện → trả về giá trị a[i], hoặc trả về vị trí thứ i 29 Tìm kiếm giá trị thỏa đk (tt) Ví dụ 1: Tìm giá trị lớn nhất mảng int TimMax(int a[], int n) { int i, max = a[0]; for (i = 1; i < n; i++) if(a[i]>max) max = a[i]; return max; } 30 GV: ThS. Trần Nguyễn Anh Chi 15
  16. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Tìm kiếm giá trị thỏa đk (tt) Ví dụ 2: Tìm vị trí của giá trị lớn nhất mảng int TimViTriMax(int a[], int n) { int i, max = a[0], vtmax = 0; for (i = 1; i < n; i++) if(a[i] > max) { max = a[i]; vtmax = i; } return vtmax; } 31 Tìm kiếm giá trị thỏa đk (tt) Ví dụ 3: Tìm vị trí giá trị chẵn đầu tiên int TimChanDau(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2==0) return i; return -1; } 32 GV: ThS. Trần Nguyễn Anh Chi 16
  17. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Kiểm tra tính chất mảng TH1: kiểm tra xem trong mảng có tồn tại 1 phần tử thỏa điều kiện nào đó hay không → tìm phần tử thỏa điều kiện rồi kết luận Ý tưởng:  Duyệt từ đầu đến cuối mảng  Tại vị trí thứ i, nếu a[i] thỏa điều kiện → trả về true  Trả về false 33 Kiểm tra tính chất mảng (tt) TH2: kiểm tra xem tất cả các phần tử trong mảng có thỏa điều kiện nào đó hay không → tìm phần tử không thỏa điều kiện rồi kết luận Ý tưởng:  Duyệt từ đầu đến cuối mảng  Tại vị trí thứ i, nếu a[i] không thỏa điều kiện → trả về false  Trả về true 34 GV: ThS. Trần Nguyễn Anh Chi 17
  18. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Kiểm tra tính chất mảng (tt) Ví dụ 1: Kiểm tra xem trong mảng có tồn tại giá trị lẻ hay không? bool KiemTraTonTaiLe(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2!=0) return true; return false; } 35 Kiểm tra tính chất mảng (tt) Ví dụ 2: Kiểm tra xem mảng có chứa toàn giá trị lẻ hay không? bool KiemTraToanLe(int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i]%2==0) return false; return true; } 36 GV: ThS. Trần Nguyễn Anh Chi 18
  19. Kỹ thuật lập trình cơ bản Chương 4: Mảng một chiều Sắp xếp Có nhiều tiêu chí sắp xếp mảng: sắp tăng dần, sắp giảm dần, sắp chẵn tăng lẻ giảm… Có nhiều thuật toán sắp xếp mảng: chọn trực tiếp, chèn trực tiếp, đổi chỗ trực tiếp… Ý tưởng:  Sử dụng 2 biến i và j để so sánh tất cả cặp phần tử với nhau và hoán vị các cặp nghịch thế (sai thứ tự). tạm 85 0 1 2 n–1 MAX - 1 15 51 68 … 86 … … i j j j j 37 Sắp xếp (tt) Ví dụ: Sắp xếp mảng tăng dần void HoanVi(int &x, int &y) { int tam=x; x = y; y = tam; } void SapTang(int a[], int n) { int i, j; for (i=0; i
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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