Bài giảng Kỹ thuật lập trình - Chương 1: Mảng một chiều - Trần Minh Thái

Lập trình CChương 1. Mảng một chiều(6 tiết)Trần Minh TháiEmail: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn Cập nhật: 09/11/2016 1Nội dungKhái niệm kiểu dữ liệu mảng một chiềuKhai báoCác thao tác nhập/ xuất mảngKỹ thuật tìm kiếm, liệt kê giá trị trong mảngKỹ thuật xóa, chènChuỗi ký tự và các thao tác xữ lý cơ bảnKHÁI NIỆM VÀ KHAI BÁO3Khái niệmMảng được cấp phát bộ nhớ liên tục và bao gồm nhiều biến thành phầnMỗi biến thành phần có cùng KDL và cùng tên0123456789Giá trịVị tríVị trí được tính từ 0Khai báo [] ;Nhằm thuận tiện cho việc viết chương trình, ta nên định nghĩa hằng số MAX ở đầu chương trình – là kích thước tối đa của mảng - như sau:Ví dụint a[100]; //Khai bao mang so nguyen a toi da 100 phan tufloat b[50]; //Khai bao mang so thuc b toi da 50 phan tuchar str[30]; //Khai bao mang ky tu str toi da 30 ky tu#define MAX 100int main(){int a[MAX], b[MAX];//Các lệnhreturn 0;}Khai báo, gán giá trị ban đầuGán từng phần tửint a[5] = { 3, 6, 8, 1, 12 };Gán toàn bộ phần tử trong mảng có cùng giá trịint a[8] = { 3 };Giá trị368112Vị trí01234Giá trị33333333Vị trí01234567Truy xuất giá trịTênMảng [vị trí cần truy xuất]int main(){int a[5] = { 3, 6, 8, 11, 12 };printf("Gia tri mang tai vi tri 3 = ", a[3]);getch();return 0;}Kết quả: Gia tri mang tai vi tri 3 = 11Vị trí 3Các thao tác trên mảngNhậpXuất (liệt kê)Tìm kiếmĐếmSắp xếpKiểm tra mảng thỏa điều kiện cho trướcTách/ ghép mảngChèn / xóaTHAO TÁC NHẬP VÀ XUẤT9Nhập mảnga[0]a[1]a[2]a[3]a[4]a[5]a[n-1]Nhập a[0]Nhập a[1]Nhập a[2]Nhập a[n-1] Nhập a[i], với 0 ≤ i ≤ n-1 Ví dụ nhập và xuất mảng số nguyên#define MAX 100void NhapKichThuoc(int &n){	printf("Nhap vao kich thuoc mang: ");	scanf("%d", &n);}void NhapMang(int a[], int n){for (int i = 0; i và Dùng hàm srand() trong hàm main() trước khi gọi hàm phát sinh: để khởi tạo bộ giá trị ngẫu nhiênDùng hàm rand()%k để phát sinh số ngẫu nhiên: có giá trị từ 0 đến k-1Ví dụ: Chương trình tạo mảng số nguyên có giá trị ngẫu nhiên từ 1 đến MAX#include #include #include #include #pragma warning(disable: 4996);#define MAX 100void NhapKichThuoc(int &n);void PhatSinh(int a[], int n);void XuatMang(int a[], int n);void NhapKichThuoc(int &n){	printf("Nhap vao kich thuoc mang: ");	scanf("%d", &n);}void PhatSinh(int a[], int n){	for (int i = 0; i a[], int n){	for (int i = 0; i a[], int n, int x){	for (int i = 0; i x)	printf(“%d\t”, a[i]);}Ví dụ 3: Chương trình nhập vào mảng một chiều số nguyên a, kích thước n. In ra các phần tử có giá trị lớn hơn x có trong mảng#define MAX 100void NhapKichThuoc(int &n);void NhapMang(int a[], int n);void XuatMang(int a[], int n);void LietKeLonHonX(int a[], int n, int x);void NhapKichThuoc(int &n){	prinft(“Nhap vao kich thuoc mang: “);	scanf(“%d”, &n);}void NhapMang (int a[], int n){	for (int i = 0; i x)printf(“%d\t”, a[i]);}int main(){int a[MAX], n, x;NhapKichThuoc(n);NhapMang(a, n);printf("Cac phan tu cua mang:\n");XuatMang(a, n);printf("Nhap gia tri x: “);scanf(“%d”, &x);printf("Cac phan tu co gia tri lon hon %d:\n", x); LietKeLonHonX(a, n, x);getch();return 0;}Bài tập tại lớpCho mảng số nguyên a, gồm n phần tử, viết chương trình gồm các hàm thực hiện các yêu cầu sau:Nhập vào kích thước mảng (0 a[], int n){	int d = 0;	for (int i = 0; i a[], int n, int x){	int d = 0;	for (int i = 0; i TongXXX( a[], int n){	 s = 0;	for (int i = 0; i a[], int n){	 s = 0;	int d = 0;	for (int i = 0; i a[], int n){	for (int i = 0; i a[j])	HoanVi(a[i], a[j]); }}void HoanVi( &a, &b){	 tam = a;	a = b;	b = tam;}THAO TÁC KIỂM TRA GIÁ TRỊ MẢNG CÓ THỎA ĐIỀU KIỆN57Kiểm tra tồn tạiKiểm tra xem mảng có tồn tại một phần tử thỏa điều kiện nào đó cho trước hay không? tìm phần tử thỏa điều kiện để kết luận	Trả về: 1 nếu có phần tử thỏa điều kiện0 nếu không có phần tử nào thỏa điều kiệnKiểm tra tồn tạiint KiemTraTonTaiXXX( a[], int n){	for (int i = 0; i a[], int n){	for (int i = 0; i= 0) return 0; return 1;}Bài tậpCho mảng số nguyên kích thước n. Viết các hàm sau:Kiểm tra xem mảng có chứa số nguyên tố không?Kiểm tra xem mảng có thứ tự tăng dần hay không?Kiểm tra xem mảng có chẵn lẻ xen kẽ không?Kiểm tra xem mảng có âm dương xen kẽ không?1. Kiểm tra xem mảng có chứa số nguyên tố không?/*Kiem tra k co phai la so nguyen to khong? * Neu la so nguyen to thi tra ve 1 * Nguoc lai tra ve 0 */int LaSNT(int k);/*Kiem tra xem mang a co chua so nguyen to khong? * Neu co thi tra ve 1 * Nguoc lai tra ve 0 */int CoTonTaiSNT(int a[], int n);66int LaSNT(int k){ int d=0; for(int i=1; i a[i + 1]) return 0; } return 1;}3. Kiểm tra chẵn lẻ xen kẽ?int LaChanLeXenKe(int a[], int n){ for(int i=0; i= 0) return 0; } return 1;}THAO TÁC CHÈN71Chèn phần tử vào mảngCho mảng sau:Hãy trình bày từng bước chèn 111 vào vị trí 3 của mảng12579213801234512570123453821911172Chèn phần tử vào mảngChèn 111 vào vị trí 3 của mảng12579213801234561. Di chuyển a[5] sang a[6]: a[6] = a[5]125792138012345612579213801234562. Di chuyển a[4] sang a[5]: a[5] = a[4]12579213801234563. Di chuyển a[3] sang a[4]: a[4] = a[3]12571119213801234564. Gán a[3] = 1115. Tăng kích thước n++Chèn phần tử vào mảngGọi k là vị trí cần chèn, n là kích thước mảng, x là giá trị cần chèna[6] = a[5]a[5] = a[4]a[4] = a[3]a[3] = 111 n++a[i+1]=a[i]i = n-1i = ka[k]=xChèn phần tử vào mảngBT: Hãy viết hàm chèn phần tử có giá trị x vào vị trí k cho trước trong mảng số nguyên a kích thước n theo mẫu sau:void ChenX(int a[], int &n, int x, int k);75Chèn phần tử vào mảngvoid ChenX(int a[], int &n, int x, int k){ for(int i = n-1; 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 số nguyên 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)77Bài tập áp dụngint TimVTMin(int a[], int n) { int vtmin = 0; for (int i = 1; i [] ;	Ví dụ: char str[25]; Ý nghĩa khai báo 1 mảng kiểu ký tự tên là str có 25 phần tử (như vậy có thể lưu tối đa 24 ký tự vì phần tử thứ 24 đã chứa ký tự kết thúc chuỗi ‘\0’ ) Khai báo chuỗiCách 2: Con trỏ	char *;	Ví dụ:	char *str; Phải cấp phát bộ nhớ trước khi sử dụng chuỗi strVí dụ: char *str;str = (char*)malloc(30); //Cấp phát bộ nhớ cho str gồm 30 ký tự!!!Gán trực tiếp thì không cần cấp phát bộ nhớ Thư viện malloc.hNhập chuỗi – string.hCú pháp: 	char *gets(char *str);Nhận các ký tự nhập từ phím cho đến khi nhấn phím Enter và đưa vào chuỗi strVí dụ:int main(){ char str[80]; printf("Nhap vao chuoi: "); gets(str); printf("Chuoi vua nhap la: %s\n", str); getch(); return 0;}Nhập chuỗiLưu ý: Không thể dùng hàm scanf để nhập chuỗi có khoảng trắngVí dụ:Giả sử nhập vào chuỗi: “Nguyen Van An”Thì kết quả xuất ra màn hình là: “Nguyen” (do str chỉ lưu chuỗi “Nguyen”)int main() { char str[80]; printf("Nhap vao chuoi: "); scanf("%s", &str); printf("Chuoi vua nhap la: %s\n", str); getch(); return 0;}Xuất chuỗi – string.hCú pháp : int puts (const char *s);Ví dụ:int main(){ 	char *str = "Vi du xuat chuoi"; 	puts(str);	return 0;} Có thể dùng printf(): printf(“%s”, str);Các hàm xử lý chuỗi - Tính độ dài chuỗi: strlenSao chép chuỗi: strcpy, strncpyNối chuỗi: strcat, strncatSo sánh chuỗi: strcmp, strncmp, stricmp, strnicmpTìm kiếm: strchr, strstrTách chuỗi: strtokĐổi thành chữ in HOA: struprĐổi thành chữ in thường: strlwrTính độ dài của chuỗi	int strlen(char *s); Ví dụ:char *str = "Borland International";printf("Do dai str = %d\n", strlen(str)); Kết quả: Do dai str = 21Bài tập ví dụ - tính độ dài chuỗiViết hàm đếm số ký tự trắng trong chuỗiViết hàm in ra màn hình chuỗi theo thứ tự đảo ngượcViết hàm tìm xem ký tự ch có trong chuỗi không? Nếu có cho biết vị trí xuất hiện đầu tiên của chViết hàm kiểm tra xem chuỗi có đối xứng hay không?Viết hàm đổi tất cả các ký tự có trong chuỗi thành chữ HOA (không dùng hàm strupr)1. Đếm số ký tự trắng trong chuỗiint DemKyTuTrang(char *s){ int d=0; int n=strlen(s); for(int i=0; i= 0; i--) printf("%c", s[i]);}Bài tập làm thêm – tính độ dài chuỗiViết hàm tra xem trong chuỗi có ký tự số hay không nếu có tách ra thành một mảng số riêng Viết hàm đổi ký tự hoa thành thường và ngược lại trong chuỗi ký tự cho trướcViết chương trình tìm kiếm xem ký tự nào xuất hiện nhiều nhất trong chuỗiViết chương trình đảo ngược các ký tự trong chuỗiVí dụ: 	Nhập: ABCDE	Chuỗi sau khi đảo ngược là: EDCBASao chép chuỗiSao chép nội dung chuỗi scr vào chuỗi dest	strcpy(char *dest, const char *scr); Ví dụ: Kết quả: Chuoi dest: abcdefghi103char dest[10];char *src = "abcdefghi";strcpy(dest, src);printf("Chuoi dest: %s", dest);Sao chép chuỗiChép n ký tự từ chuỗi scr sang dest	strncpy(char *dest, const char *scr, int n); Ví dụ: Kết quả: abc104char dest[4];char *src = "abcdefghi";strncpy(dest, src, 3);printf("%s\n", dest);Nối chuỗiNối chuỗi s2 vào sau chuỗi s1	strcat(char *s1, char *s2); Ví dụ: Kết quả: Khoa CNTTchar s1[] = "Khoa";char s2[] = "CNTT";strcat(s1, " ");strcat(s1, s2);printf("%s", s1);Nối chuỗiNối n ký tự đầu tiên của chuỗi s2 vào sau chuỗi s1 	strncat(char *s1, char *s2, int n);Ví dụ: Kết quả: Khoa CNchar s1[] = "Khoa";char s2[] = "CNTT";strcat(s1, " ");strncat(s1, s2, 2);printf("%s", s1);So sánh chuỗiSo sánh 2 chuỗi s1 và s2 theo nguyên tắc thứ tự từ điển. Phân biệt chữ hoa và thường	int strcmp(char *s1, char *s2);Trả về:0: nếu s1 bằng s2>0: nếu s1 lớn hơn s2<0: nếu s1 nhỏ hơn s2So sánh chuỗi!!! Ký tự HOA < Ký tự thườngVD: ‘A’ < ‘a’ (do mã Ascii ‘A’ = 65, mã Ascii ‘a’ = 97)char s1[] = "abc";char s2[] = "Abc";int kq = strcmp(s1, s2);if (kq == 0) printf("Hai chuoi bang nhau");else if (kq < 0) { printf("Chuoi s1 nho hon chuoi s2");} else printf("Chuoi s1 lon hon chuoi s2"); Kết quả: Chuoi s1 lon hon chuoi s2So sánh chuỗiSo sánh n ký tự đầu tiên của s1 và s2, giá trị trả về tương tự hàm strcmp()	int strncmp(char *s1,char *s2, int n);Ví dụ: Kết quả: Giong nhauchar s1[] = "abcd";char s2[] = "abef";if(strncmp(s1, s2, 2)==0) printf("Giong nhau");else printf("Khac nhau");So sánh chuỗiSo sánh chuỗi s1 và s2 nhưng không phân biệt hoa thường, giá trị trả về tương tự hàm strcmp()	int stricmp(char *s1, char *s2);Ví dụ: Kết quả: Giong nhauchar s1[] = "abcd";char s2[] = "abCD";if(stricmp(s1, s2)==0) printf("Giong nhau");else printf("Khac nhau");So sánh chuỗiSo sánh n ký tự đầu tiên của s1 và s2, không phân biệt hoa thường, giá trị trả về tương tự hàm strcmp()	int strnicmp(char *s1, char *s2, int n); Ví dụ: Kết quả: Giong nhauchar s1[] = "aBcd";char s2[] = "Abef";if(strnicmp(s1, s2, 2)==0) printf("Giong nhau");else printf("Khac nhau");Tìm ký tự trong chuỗiTìm sự xuất hiện đầu tiên của ký tư c trong chuỗi s. 	char *strchr(char *s, char c); Trả về:NULL: nếu không cóCon trỏ đến ký tự c xuất hiện trong s: nếu tìm thấy	Tìm ký tự trong chuỗiVí dụ: Kết quả: m xuat hien tai vi tri 8char s[15];char *ptr, c = 'm';strcpy(s, "Vi du tim ky tu");ptr = strchr(s, c);if (ptr) printf("%c xuat hien tai vi tri %d", c, ptr-s);else printf("Khong tim thay");Tìm chuỗi conTìm sự xuất hiện đầu tiên của chuỗi s2 trong chuỗi s1. 	char *strstr(char *s1, char *s2); Trả về:NULL: nếu không cóNgược lại: Con trỏ vào chuỗi s2 xuất hiện trong s1	Tìm chuỗi conVí dụ: Kết quả: Vi tri xuat hien cua s2: 13char *s1 = "Borland International";char *s2 = "nation", *ptr;ptr = strstr(s1, s2);if(ptr!=NULL) printf("Vi tri xuat hien cua s2: %d", ptr-s1);else printf("Khong ton tai chuoi s2");Tách chuỗichar *strtok(char *s1, char *s2); Nếu s2 có xuất hiện trong s1: Tách chuỗi s1 thành 2 chuỗi: Chuỗi đầu là những ký tự cho đến khi gặp s2 đầu tiên, chuỗi sau là những ký tự còn lại của s1 sau khi đã bỏ đi s2 xuất hiện trong s1Nếu s2 không xuất hiện trong s1 thì kết quả vẫn là s1Tách chuỗiVí dụ:char input[16] = "abc,d";char *p;// Lay chuoi daup = strtok(input, ",");if (p) printf("S11 = %s\n", p);// Lay chuoi con lai, tham so dau la NULLp = strtok(NULL, "");if (p) printf("S12 = %s", p); Kết quả: 	S11 = abc	S12 = dBài tập tách chuỗiViết hàm đếm xem một chuỗi cho trước có bao nhiêu từ (các từ cách nhau bằng khoảng trắng)Viết hàm đảo ngược các từViết hàm tách các từ phân biệt và in ra màn hình (các từ các nhau bởi dấu chấm câu hoặc khoảng trắng) Viết hàm kiểm tra xem chuỗi có tuần hoàn hay không?Viết hàm đổi những ký tự đầu tiên của mỗi từ thành chữ in HOAĐổi sang chữ in HOAĐổi chuỗi str thành chuỗi in HOA	char* strupr(char *str); Ví dụ: Kết quả: s2 = ABCDchar s1[] = "aBcd";char *s2 = strupr(s1);printf("s2 = %s", s2);Đổi sang chữ in thườngĐổi chuỗi str thành chuỗi in thường	char* strlwr(char *str); Ví dụ: Kết quả: s2 = abcdchar s1[] = "aBcd";char *s2 = strlwr(s1);printf("s2 = %s", s2);Q&A