Bài giảng Tin học đại cương - Bài 9: Mảng, con trỏ và xâu kí tự - Đỗ Bá Lâm

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Đỗ Bá Lâm lamdb@soict.hut.edu.vn TIN HỌC ĐẠI CƯƠNG Bài 9. Mảng, con trỏ và xâu kí tự Nội dung 9.1. Mảng 9.2. Con trỏ 9.3. Xâu kí tự 2 Nội dung 9.1. Mảng 9.1.1. Khái niệm mảng 9.1.2. Khai báo và sử dụng mảng 9.1.3. Các thao tác cơ bản trên mảng 9.1.4. Tìm kiếm trên mảng 9.1.5. Sắp xếp trên mảng 9.2. Con trỏ 9.3. Xâu kí tự 3 9.1.1. Khái niệm mảng • Tập hợp hữu hạn các phần tử cùng kiểu, lưu trữ kế tiếp nhau trong bộ nhớ • Các phần tử trong mảng có cùng tên (là tên mảng) nhưng phân biệt với nhau ở chỉ số cho biết vị trí của nó trong mảng • Ví dụ: – Bảng điểm của sinh viên – Vector – Ma trận 4 9.1.2. Khai báo và sử dụng mảng • Khai báo mảng một chiều: kiểu_dữ_liệu tên_mảng [kích_thước_mảng]; • Trong đó – kiểu_dữ_liệu: kiểu dữ liệu của các phần tử trong mảng – tên_mảng: tên của mảng – kích_thước_mảng: số phần tử trong mảng • Ví dụ int mang_nguyen[10]; // khai báo mảng 10 phần tử có kiểu dữ liệu int 5 9.1.2. Khai báo và sử dụng mảng • Cấp phát bộ nhớ – Các phần tử trong mảng được cấp phát các ô nhớ kế tiếp nhau trong bộ nhớ – Biến mảng lưu trữ địa chỉ ô nhớ đầu tiên trong vùng nhớ được cấp phát • Ngôn ngữ C đánh chỉ số các phần tử trong mảng bắt đầu từ 0 – Phần tử thứ i trong mang_nguyen được xác định bởi mang_nguyen[i-1] 6 mang_nguyen[0] mang_nguyen[1] .. mang_nguyen[9] mang_nguyen 9.1.2. Khai báo và sử dụng mảng • Mảng mảng nhiều chiều: Mỗi phần tử của mảng cũng là một mảng • Ví dụ – int a[6][5] ; mảng a gồm 6 phần tử mỗi phần tử là mảng gồm 5 số nguyên int – int b[3][4][5]; // mảng b gồm 3 phần tử, mỗi phần tử là mảng hai chiều gồm 4 phần tử. Mỗi phần tử mảng hai chiều là mảng gồm 5 số nguyên int. b là mảng 3 chiều 7 9.1.2. Khai báo và sử dụng mảng • Khai báo một biến mảng kiểu_dữ_liệu tên_mảng[size1][size2][sizek]; Trong đó • sizei là kích thước chiều thứ i của mảng 8 9.1.2. Khai báo và sử dụng mảng • Sử dụng mảng – Truy cập vào phần tử thông qua tên mảng và chỉ số của phần tử trong mảng tên_mảng[chỉ_số_phần_tử] – Chú ý: chỉ số bắt đầu từ 0 • Ví dụ – int a[4]; – phần tử đầu tiên (thứ nhất) của mảng: a[0] – phần tử cuối cùng (thứ tư) của mảng: a[3] – a[i]: là phần tử thứ i+1 của a 9 9.1.2. Khai báo và sử dụng mảng • Ví dụ (tiếp) – int b[3][4]; – phần tử đầu tiên của mảng: b[0] là một mảng một chiều – phần tử đầu tiên của mảng b[0]: b[0][0] – b[i][j]: là phần tử thứ j+1 của b[i], b[i] là phần tử thứ i+1 của b 10 9.1.3. Các thao tác cơ bản trên mảng a. Nhập dữ liệu cho mảng • Khởi tạo giá trị cho mảng ngay khi khai báo – int a[4] = {1,4,6,2}; – int b[2][3]={ {1,2,3}, {4,5,6} }: – Số lượng giá trị khởi tạo không được lớn hơn số lượng phần tử trong mảng – Nếu số lượng này nhỏ hơn, các phần tử còn lại được khởi tạo giá trị 0 11 9.1.3. Các thao tác cơ bản trên mảng a. Nhập dữ liệu cho mảng – Có thể xác định kích thước mảng thông qua số giá trị khởi tạo nếu để trống kích thước mảng – int array1 [8] = {2, 4, 6, 8, 10, 12, 14, 16}; – int array2 [] = {2, 4, 6, 8, 10, 12, 14, 16}; 12 9.1.3. Các thao tác cơ bản trên mảng a. Nhập dữ liệu cho mảng • Nhập dữ liệu từ bàn phím bằng hàm scanf – int a[10]; – Nhập dữ liệu cho a[1]: scanf(“%d”, & a[1]); – Nhập dữ liệu cho toàn bộ phần tử của mảng a => Sử dụng vòng lặp for • Lưu ý – Tên mảng là một hằng (hằng con trỏ) do đó không thể thực hiện phép toán với tên mảng như phép gán sau khi đã khai báo 13 9.1.3. Các thao tác cơ bản trên mảng #include #define MONTHS 12 int main(){ int rainfall[MONTHS], i; for ( i=0; i < MONTHS; i++ ){ printf(“Nhap vao phan tu thu %d: “, i+1); scanf("%d", &rainfall[i] ); } getch(); return 0; } 14 9.1.3. Các thao tác cơ bản trên mảng a. Nhập dữ liệu cho mảng • Lưu ý – Nếu số phần tử của mảng được nhập từ bàn phím và chỉ biết trước số phần tử tối đa tối đa => khai báo mảng với kích thước tối đa và sử dụng biến lưu số phần tử thực sự của mảng. – Ví dụ: Khai báo mảng số nguyên a có tối đa 100 phần tử. Nhập từ bàn phím số phần tử trong mảng và giá trị các phần tử đó. 15 9.1.3. Các thao tác cơ bản trên mảng #include #include main(){ int a[100]; int n, i; do{ printf(“\n Cho biet so phan tu cua mang: “); scanf(“%d”,&n); }while (n>100||n<1); 16 9.1.3. Các thao tác cơ bản trên mảng for(i = 0; i < n; i++){ printf(“a[%d] = ", i); scanf("%d",&a[i]); } getch(); } 17 9.1.3. Các thao tác cơ bản trên mảng b. Xuất dữ liệu trong mảng – Dùng hàm printf() – Để hiển thị tất cả các phần tử: dùng vòng for • Ví dụ – Hiển thị một phần tử bất kì – Hiển thị tất cả các phần tử, mỗi phần tử trên một dòng – Hiển thị tất cả các phần tử trên một dòng, cách nhau 2 vị trí – Hiển thị từng k phần tử trên một dòng 18 9.1.3. Các thao tác cơ bản trên mảng #include #define MONTHS 12 int main(){ int rainfall[MONTHS], i; for ( i=0; i < MONTHS; i++ ){ printf(“Nhap vao phan tu thu %d: “, i+1); scanf("%d", &rainfall[i] ); } for ( i=0; i < MONTHS; i++ ) printf( "%2d ” , rainfall[i]); printf("\n"); return 0; } 19 9.1.3. Các thao tác cơ bản trên mảng c. Tìm giá trị lớn nhất, nhỏ nhất • Tìm giá trị lớn nhất – Giả sử phần tử đó là phần tử đầu tiên – Lần lượt so sánh với các phần tử còn lại – Nếu lớn hơn hoặc bằng => so sánh tiếp – Nếu nhỏ hơn => coi phần tử này là phần tử lớn nhất và tiếp tục so sánh • Tìm giá trị nhỏ nhất: tương tự 20 9.1.3. Các thao tác cơ bản trên mảng max = rainfall[0]; for(i = 1; i < n; i++) if(max < a[i]) max = a[i]; printf("\n Luong mua nhieu nhat la: %d", max); 21 9.1.4. Tìm kiếm trên mảng • Bài toán – Cho mảng dữ liệu a và một giá trị k – Tìm các phần tử trong mảng a có giá trị bằng (giống) với k. Nếu có in ra vị trí (chỉ số) các phần tử này. Ngược lại thông báo không tìm thấy • Cách làm – Duyệt toàn bộ các phần tử trong mảng – Nếu a[i] bằng (giống) k thì lưu lại chỉ số i – Sử dụng một biến để xác định tìm thấy hay không tìm thấy 22 9.1.4. Tìm kiếm trên mảng • Phân tích – Duyệt toàn bộ các phần tử • Vòng lặp for (while, do while) – Lưu lại i nếu a[i] bằng (giống) k • Sử dụng mảng lưu chỉ số – Biến xác định tìm thấy hay không tìm thấy • Biến nhận giá trị 0 hoặc 1 • Biến nhận giá trị 0 hoặc >=1 (tìm thấy thì tăng giá trị) 23 9.1.4. Tìm kiếm trên mảng #include #include main(){ int a[100], chi_so[100]; int n;//n la số phần tử trong mảng int i, k, kiem_tra; printf(“Nhap vao so phan tu cua mang:“); scanf(“%d”,&n); for ( i=0; i < n; i++ ){ printf(“Nhap vao phan tu thu %d:“,i+1); scanf("%d",&a[i]); } 24 9.1.4. Tìm kiếm trên mảng printf(“Nhap vao giá trị tim kiem“); scanf(“%d”,&k); kiem_tra = 0; // Duyệt qua tất cả các phần tử for(i=0; i<n; i++) if(a[i] == k) { chi_so[kiem_tra] = i; kiem_tra ++; } 25 9.1.4. Tìm kiếm trên mảng if(kiem_tra > 0){ printf(“Trong mang co %d phan tu co gia tri bang %d”,kiem_tra,k); printf(“\nChi so cua cac phan tu la:“); for(i = 0;i < kiem_tra; i++) printf(“%3d”,chi_so[i]); } else printf(“\n Trong mang khong co phan tu nao co gia tri bang %d”,k); getch(); } 26 9.1.5. Sắp xếp mảng • Bài toán: Cho mảng a gồm n phần tử. Sắp xếp các phần tử của mảng a theo thứ tự tăng dần/giảm dần 27 9.1.5. Sắp xếp mảng • Giải thuật sắp xếp – Sắp xếp thêm dần (insertion sort) – Sắp xếp lựa chọn (selection sort) – Sắp xếp nổi bọt (bubble sort) – Sắp xếp vun đống (heap sort) – Sắp xếp nhanh (quick sort) – Sắp xếp trộn (merge sort) – . 28 9.1.5. Sắp xếp mảng • Ý tưởng – Lần sắp xếp thứ 1 • So sánh a[0] với các a[i], i = 1..n-1 a[0] > a[i] => đổi chỗ a[0] và a[i] • Thu được a[0] là phần tử nhỏ nhất – Lần sắp xếp thứ 2 • So sánh a[1] với các a[i], i = 2..n-1 a[1] > a[i] => đổi chỗ a[1] và a[i] • Thu được a[1] là phần tử nhỏ thứ 2 29 9.1.5. Sắp xếp mảng • Ý tưởng – Lần sắp xếp thứ k • So sánh a[k-1] với các a[i], i = k..n-1 a[k-1] > a[i] => đổi chỗ a[k-1] và a[i] • Thu được a[k-1] là phần tử nhỏ thứ k – .. – Lần sắp xếp thứ n-1 • So sánh a[n-2] và a[n-1] a[n-2] > a[n-1] => đổi chỗ a[n-2] và a[n-1] • Thu được a[n-2] là phần tử nhỏ thứ n-1 => còn lại a[n-1] là phần tử nhỏ thứ n (lớn nhất) 30 9.1.5. Sắp xếp mảng • A = { 12, 5, 3, 4 }; Lượt 1 Lượt 2 Lượt 3 12 3 3 3 5 12 4 4 3 5 12 5 4 4 5 12 31 9.1.5. Sắp xếp mảng //Khai bao cac bien int a[100]; int i, j, temp; //Sap xep for (i = 0; i < n-1; i++) for (j = i+1; j <n ; j++) if ( a[i] > a[j]){ tmp = a[i]; a[i]= a[j]; a[j]= tmp; } 32 9.1.5. Sắp xếp mảng • Ví dụ – Nhập vào từ bàn phím một mảng số nguyên m trong đó số phần tử cũng được nhập từ bàn phím – Hiển thị các phần tử vừa được nhập vào – Sắp xếp mảng m theo thứ tự tăng dần trong đó có hiển thị các phần tử trong mỗi lượt sắp xếp. 33 9.1.5. Sắp xếp mảng #include #include main(){ int m[100]; int n; // n la số phần tử trong mảng int i, j, k; // Nhập giá trị dữ liệu cho mảng m printf(“ Cho biet so phan tu co trong mang: “); scanf(“%d”,&n); 34 9.1.5. Sắp xếp mảng // nhập giá trị cho các phần tử for(i=0;i<n;i++){ printf(“Cho biet gia tri cua m[%d] = “,i); scanf(“%d”,&m[i]); } // Hiển thị mảng vừa nhập vào printf(“Mang truoc khi sap xep\n“); for(i=0;i<n;i++) printf(“%3d”,m[i]); 35 9.1.5. Sắp xếp mảng for(i = 0; i<n-1; i++){ for(j = i+1; j<n; j++){ if(m[i]>m[j]){ temp = m[j];m[j] = m[i];m[i] = temp; } printf(“\nMang o luot sap xep thu %d”,i+1); for(k = 0;k < n ;k++) printf(“%3d”,m[k]); } getch(); } 36 Nội dung 9.1. Mảng 9.2. Con trỏ 9.2.1. Khái niêm, khai báo con trỏ 9.2.2. Toán tử địa chỉ, toán tử nội dung 9.2.3. Phép toán trên con trỏ 9.2.4. Con trỏ và mảng 9.3. Xâu kí tự 37 9.2.1. Khái niệm, khai báo con trỏ • Địa chỉ và giá trị của một biến – Bộ nhớ như một dãy các byte nhớ. – Các byte nhớ được xác định một cách duy nhất qua một địa chỉ. – Biến được lưu trong bộ nhớ. – Khi khai báo một biến • Chương trình dịch sẽ cấp phát cho biến đó một số ô nhớ liên tiếp đủ để chứa nội dung của biến. Ví dụ một biến số nguyên (int) được cấp phát 2 byte. • Địa chỉ của một biến chính là địa chỉ của byte đầu tiên trong số đó. 38 39 Địa chỉ và giá trị của một biến (tiếp) • Một biến luôn có hai đặc tính: • Địa chỉ của biến. • Giá trị của biến. • Ví dụ: • int i, j; • i = 3; • j = i + 1; Biến Địa chỉ Giá trị i FFEC 3 j FFEE 4 40 Khái niệm và khai báo con trỏ • Con trỏ là một biến mà giá trị của nó là địa chỉ của một vùng nhớ. • Khai báo con trỏ: Kieu_du_lieu *ten_bien_con_tro; • Ví dụ • int i = 3; • int *p; • p = &i; • Một con trỏ chỉ có thể trỏ tới một đối tượng cùng kiểu. ... ...a...p Biến Địa chỉ Giá trị i FFEC 3 p FFEE FFEC 9.2.2. Toán tử địa chỉ, toán tử nội dung • Toán tử &: Trả về địa chỉ của biến. • Toán tử *: Trả về giá trị chứa trong vùng nhớ được trỏ bởi con trỏ. • Cả hai toán tử * và & có độ ưu tiên cao hơn tất cả các toán tử số học ngoại trừ toán tử đảo dấu. • Ví dụ: void main() { int i = 3; int *p; p = &i; printf("*p = %d \n",*p); getch(); } 41 42 9.2.2. Toán tử địa chỉ, toán tử nội dung • Một biến con trỏ có thể được gán bởi: – Địa chỉ của một biến khác: • ten_bien_con_tro = &ten_bien; – Giá trị của một con trỏ khác (tốt nhất là cùng kiểu): • ten_bien_con_tro2 = ten_bien_con_tro1; – Giá trị NULL (số 0): • ten_bien_con_tro = 0;// hoặc là NULL • Gán giá trị cho biến con trỏ: – *ten_bien_con_tro = 10; 43 Ví dụ 1 void main() { int i = 3, j = 6; int *p1, *p2; p1 = &i; p2 = &j; *p1 = *p2; } 44 Ví dụ 2 void main() { int i = 3, j = 6; int *p1, *p2; p1 = &i; p2 = &j; p1 = p2; } 45 Con trỏ void • void *ten_bien_con_tro; • Con trỏ đặc biệt, không có kiểu, • Có thể nhận giá trị là địa chỉ của một biến thuộc bất kỳ kiểu dữ liệu nào. • Ví dụ: – void *p, *q; – int x = 21; – float y = 34.34; – p = &x; q = &y; 46 9.2.3. Các phép toán làm việc với con trỏ • Cộng/trừ con trỏ với một số nguyên (int, long) → Kết quả là một con trỏ cùng kiểu • ptr--; //ptr trỏ đến vị trí của phần tử đứng trước nó. • Trừ hai con trỏ cho nhau • Kết quả là một số nguyên • Kết quả này nói lên khoảng cách (số phần tử thuộc kiểu dữ liệu của con trỏ) ở giữa hai con trỏ. • Các phép toán: Cộng, nhân, chia, lấy số dư trên con trỏ là không hợp lệ. • Ví dụ: (p2 trỏ đến số nguyên nằm ngay sau x trong bộ nhớ) int x, *p1, *p2; p1= &x; p2= p1+1; 9.2.4. Con trỏ và mảng • Với mảng một chiều có tên là a thì ▪ a là một địa chỉ ▪ a có giá trị bằng &a[0] • Giả sử có khai báo: int a[10], *p; • Nếu p = a thì ▪ p + 1 trỏ tới a[1] ▪ p + i trỏ tới a[i] 47 Nội dung 9.1. Mảng 9.2. Con trỏ 9.3. Xâu kí tự 9.3.1. Khái niệm xâu kí tự 9.3.2. Khai báo và sử dụng xâu 9.3.3. Các hàm xử lý kí tự 9.3.4. Các hàm xử lý xâu 9.3.5. Mảng các xâu kí tự 48 9.3.1. Khái niệm xâu kí tự • Xâu kí tự (string) là một dãy các kí tự viết liên tiếp nhau – Độ dài xâu là số kí tự có trong xâu – Xâu rỗng là xâu không có kí tự nào • Ví dụ: “Tin hoc”, “String” • Lưu trữ: kết thúc xâu bằng kí tự ‘\0’ hay NUL (mã ASCII là 0) 49 ‘T’ ‘i’ ‘ n ‘ ‘ ‘ ‘h’ ‘o’ ‘c’ ‘\0’ 9.3.1. Khái niệm xâu kí tự • So sánh – Xâu kí tự và mảng kí tự? • Tập hợp các kí tự viết liên tiếp nhau • Sự khác biệt: xâu kí tự có kí tự kết thúc xâu, mảng kí tự không có kí tự kết thúc xâu – Xâu kí tự “A” và kí tự ‘A’? • ‘A’ là 1 kí tự • “A” là 1 xâu kí tự, ngoài kí tự ‘A’ còn có kí tự ‘\0’ 50 9.3.2. Khai báo và sử dụng xâu a. Khai báo xâu • Cú pháp char tên_xâu [số_kí_tự]; • Lưu ý: – Để lưu trữ một xâu có n kí tự chúng ta cần một mảng có kích thước n+1 • Ví dụ – Để lưu trữ xâu “Tin hoc” chúng ta phải khai báo xâu có số phần tử tối đa ít nhất là 8 char str [8]; 51 9.2.2. Khai báo và sử dụng xâu b. Truy cập vào một phần tử của xâu • Cú pháp: tên_xâu [chỉ_số_của_kí_tự] • Ví dụ char quequan[10]; Giả sử xâu này có nội dung là “Ha noi”  quequan[0] lưu trữ ‘H’ quequan[1] ‘a’ quequan[6] ‘i’ quequan[7] ‘\0’ 52 9.3.3. Các hàm xử lý kí tự • Tệp tiêu đề sử dụng: ctype.h • int toupper(int ch): chuyển kí tự thường thành kí tự hoa toupper(‘a’) => ‘A’ • int tolower(int ch): chuyển kí tự hoa thành kí tự thường tolower(‘B’) => ‘b’ 53 9.3.3. Các hàm xử lý kí tự • int isalpha(int ch): kiểm tra xem kí tự có phải chữ cái hay không (‘a’’z’,’A’,..’Z’) • int isdigit(int ch): kiểm tra chữ số (‘0‘,‘1‘,..‘9‘) • int islower(int ch): kiểm tra chữ thường • int isupper(int ch): kiểm tra chữ hoa • int iscntrl(int ch): kiểm tra kí tự điều khiển (0-31) • int isspace(int ch): kiểm tra kí tự dấu cách (mã 32), xuống dòng (‘\n’ 10), đầu dòng (‘\r’ 13), tab ngang (‘\t’ 9), tab dọc (‘\v’ 11) • trả về khác 0 nếu đúng, ngược lại trả về 0 54 9.3.3. Các hàm xử lý kí tự #include #include #include main(){ char ch; printf(“Nhap vao mot ki tu: “); scanf(“%c”, &ch); 55 9.2.3. Các hàm xử lý kí tự if(isupper(ch)){ printf(“Ki tu nay la chu hoa\n”); printf(“Ki tu chu thuong tuong ung %c\n”,tolower(ch)); }else if(islower(ch)){ printf(“Ki tu nay la chu thuong\n”); printf(“Ki tu chu hoa tuong ung %c\n”,toupper(ch)); } getch(); } 56 9.3.3. Các hàm xử lý kí tự Vào ra xâu kí tự • Tệp tiêu đề: stdio.h • Nhập xâu kí tự – gets(tên_xâu); – scanf(“%s”,&tên_xâu); • Hiển thị xâu kí tự – puts(tên_xâu); – printf(“%s”,tên_xâu); • Sự khác nhau giữa gets và scanf? 57 9.3.4. Các hàm xử lý xâu kí tự Tệp tiêu đề: string.h • size_t strlen(char[] tên_xâu): trả về độ dài xâu • char[] strcpy(char[] xâu_đích, char[] xâu_nguồn): sao chép xâu • int strcmp(char[] xâu_thứ_nhất, char[] xâu_thứ_hai): so sánh hai xâu – giá trị 0 : hai xâu giống nhau – giá trị<0: xâu thứ nhất nhỏ hơn xâu thứ hai – giá trị >0: xâu thứ nhất lớn hơn xâu thứ hai 58 9.3.4. Các hàm xử lý xâu kí tự • char[] strcat(char[] xâu_đích, char[] xâu_nguồn): ghép nối xâu nguồn vào ngay sau xâu đích Tệp tiêu đề: stdlib.h • int atoi(char[] str): chuyển một xâu kí tự thành một số nguyên tương ứng • int atol(char[] str): chuyển thành số long int • float atof(char[] str): chuyển thành số thực • Không thành công cả 3 hàm: trả về 0 59 9.3.4. Các hàm xử lý xâu kí tự #include #include #include main(){ clrscr(); char str1[10] = “abc”; char str2[10] = “def”; printf(“ str1: %s”,str1); printf(“\n str2: %s”,str2); printf(“\n strcmp(str1,str2)= %d”, strcmp(str1,str2)); 60 9.3.4. Các hàm xử lý xâu kí tự printf(“\n strcpy(str1,str2) = %s”, strcpy(str1,str2)); printf(“ str1: %s”,str1); printf(“\n str2: %s”,str2); strcpy(str1,”ab”);strcpy(str2,”abc”); printf(“ str1: %s”,str1); printf(“\n str2: %s”,str2); printf(“\n strcmp(str1,str2) = %d”, strcmp(str1,str2)); getch(); } 61 Thảo luận 62