Kĩ thuật lập trình - Chương 1: Mảng một chiều

TRẦN MINH THÁIEmail: minhthai@itc.edu.vnWebsite: www.minhthai.edu.vn Cập nhật: 05 tháng 01 năm 2015Chương 1. Mảng một chiều (nc)Nội dungKhái quát các kỹ thuật cơ bản xử lý mảngXoá phần tử trong mảngChèn phần tử vào mảngBài tậpKhái niệm mảng một chiềuTập các phần tử có cùng kiểu dữ liệu (KDL) được lưu trữ liên tiếp nhauCác phần tử có chỉ sốChỉ số của phần tử đầu tiên của mảng là 0Khai báo tên mảng [số phần tử tối đa]; VD: mảng số nguyên a có tối đa 100 phần tử int a[100];Khái niệm mảng một chiềuKhởi tạo mảng tên mảng [] = {giá trị 1, giá trị 2, }; hoặc tên mảng [số lượng] = {giá trị};VD1: Khởi tạo mảng gồm 5 giá trị riêng biệt int a[] = {10, 12, 20, 15, 34};VD2: Khởi tạo mảng gồm 10 phần đều có giá trị 30 int a[10] = {30};Khái niệm mảng một chiềuTruy xuất mảng thông qua chỉ số tên mảng[chỉ số]VD int a[] = {10, 12, 20, 15, 34}; int x = a[2]; // Giá trị x = 20 a[0] = 32; // Cập nhật phần tử tại vị trí 0 bằng 32Các thao tác trên mảngNhập/ xuấtXuất có điều kiệnTìm kiếmTìm min/ maxĐếm số lượng thoả điều kiệnTính tổng/ giá trị trung bình theo điều kiện cho trướcSắp xếpChèn và xoá phần tửCác thao tác trên mảngSử dụng vòng lặp để thực hiện các thao tác trên mảngCấu trúc lặp phổ biến: for(int i=0; i=k; i--) { a[i+1]=a[i]; } a[k]=x; n++;}Bài tập áp dụngHãy viết hàm chèn phần tử có giá trị x vào sau phần tử có giá trị nhỏ nhất có trong mảng a, kích thước n (giả sử mảng không có giá trị trùng nhau)Gợi ý:Viết hàm tìm vị trí phần tử có giá trị nhỏ nhất (min)Viết hàm chèn x vào sau min (sử dụng hàm ChenX)14Bài tập áp dụngint TimVTMin(int a[], int n){ int vtmin=0; for(int i=1; i<=n-1; i++) { if(a[i]<a[vtmin]) vtmin=i; } return vtmin;}Bài tập áp dụngvoid ChenXSauMin(int a[], int &n, int x){ int vtmin=TimVTMin(a, n); ChenX(a, n, x, vtmin+1);}Xóa phần tử khỏi mảngCho mảng sau:Hãy trình bày từng bước xóa phần tử tại vị trí 3 trong mảng12579213801234512579012345213817Xoá phần tử khỏi mảngXoá phần tử tại vị trí 3 125721380123451. Dời a[4] sang a[3]: a[3] = a[4]1257921380123452. Dời a[5] sang a[4]: a[4] = a[5]12572138012345Xoá phần tử khỏi mảngGọi k là vị trí cần xoá, n là kích thước mảnga[3] = a[4]a[4] = a[5]a[i]=a[i+1]i=ki=n-2Xóa phần tử khỏi mảngBT: Hãy viết hàm xóa phần tử tại vị trí k cho trước trong mảng a kích thước n theo mẫu sau: void XoaTaiVTk(int a[], int &n, int k);20Xoá phần tử khỏi mảngvoid XoaTaiVTk(int a[], int &n, int k){ for(int i=k, i<=n-2; k++) { a[i]=a[i+1]; } n--;}Bài tập áp dụngHãy viết hàm xóa phần tử x (nếu có) trong mảng a, kích thước n (giả sử mảng không có giá trị trùng nhau)Gợi ý: Viết hàm tìm vị trí phần tử có giá trị xViết hàm xoá phần tử x (sử dụng hàm XoaTaiVTk)22Bài tập áp dụngint TimX(int a[], int n, int x){ for(int i=0; i<=n-1; i++) { if(a[i]==x) return i; } return -1;}Bài tập áp dụngvoid XoaX(int a[], int &n, int x){ int vtx=TimX(a, n, x); if(vtx!=-1) XoaTaiVTk(a, n, vtx);}Q&A