Bài giảng Kỹ thuật lập trình - Chương 6: Con trỏ

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 6: Con trỏ

1. BÀI GIẢNG HỌC PHẦN KỸ THUẬT LẬP TRÌNH CHƯƠNG 6: CON TRỎ
2. Nội dung 6.1. Con trỏ và cú pháp khai báo 6.2. Các phép toán trên biến con trỏ 6.3. Con trỏ và hàm 6.4. Con trỏ và dữ liệu kiểu mảng, xâu ký tự, cấu trúc 6.5. Cấp phát bộ nhớ động 2
3. 6.1. Con trỏ và cú pháp khai báo • Khái niệm • Cú pháp khai báo • Con trỏ kiểu void 3
4. Khái niệm • Kiểu con trỏ là kiểu dữ liệu dùng để chứa địa chỉ • Biến con trỏ (gọi tắt là con trỏ) dùng để chứa địa chỉ của một đối tượng (biến hoặc hàm) • Con trỏ thường được dùng trong các trường hợp: - Trả về nhiều giá trị từ hàm (thông qua cơ chế truyền tham số theo địa chỉ trong hàm) - Truyền mảng và xâu ký tự giữa các hàm - Tạo các cấu trúc dữ liệu phức tạp (danh sách liên kết, cây nhị phân, ) 4
5. Cú pháp khai báo (1) • Cú pháp: kiểu_dữ_liệu *tên_con_trỏ; Ví dụ: int x,y,*px,*py; x, y là các biến nguyên px, py là các con trỏ kiểu int (cấp phát các vùng nhớ có tên là px, py dùng để lưu địa chỉ của các đối tượng kiểu int) *px là nội dung của px (giá trị của đối tượng mà px lưu địa chỉ) *py là nội dung của py (giá trị của đối tượng mà py lưu địa chỉ) 5
6. Cú pháp khai báo (2) Khi sử dụng các lệnh: px = &x; //gán địa chỉ của biến x cho con trỏ px py = &y; //gán địa chỉ của biến y cho con trỏ py ta nói: px trỏ tới x và py trỏ tới y *px tương đương với x, *py tương đương với y 6
7. Ví dụ (1) • Khai báo: int x = 4,y = 5,*px,*py; Địa chỉ Nội Địa chỉ Nội Biến Biến vùng nhớ dung vùng nhớ dung x 1201 px 2010 4 1202 2011 1203 2012 1204 2013 y 1205 py 2014 5 1206 2015 1207 2016 7
8. Ví dụ (2) • Thực hiện các lệnh gán: px = &x; py = &y; Địa chỉ Nội Địa chỉ Nội Biến Biến vùng nhớ dung vùng nhớ dung x 1201 px 2010 4 1201 1202 2011 1203 2012 1204 2013 y 1205 py 2014 5 1205 1206 2015 1207 2016 8
9. Ví dụ (3) • Thực hiện các lệnh gán: *px += 10; *py += 10; Địa chỉ Nội Địa chỉ Nội Biến Biến vùng nhớ dung vùng nhớ dung x 1201 px 2010 14 1201 1202 2011 1203 2012 1204 2013 y 1205 py 2014 15 1205 1206 2015 1207 2016 9
10. Con trỏ kiểu void • Là dạng con trỏ đặc biệt (con trỏ không kiểu), có thể nhận bất kỳ địa chỉ kiểu nào • Cú pháp khai báo: void *tên_con_trỏ; Ví dụ: void *p; float a[20][30]; p=a; • Con trỏ void thường được dùng làm tham số để nhận bất kỳ địa chỉ kiểu nào từ tham số thực. Khi đó, trong thân hàm phải sử dụng phép ép kiểu để chuyển sang dạng địa chỉ cần xử lý 10
11. 6.2. Các phép toán trên biến con trỏ (1) Có 4 phép toán cơ bản: Phép gán, phép tăng/giảm địa chỉ, phép truy nhập bộ nhớ, phép so sánh • Phép gán giá trị: - Các con trỏ phải cùng kiểu, muốn gán các con trỏ khác kiểu nên dùng phép ép kiểu Ví dụ: int x; char *p; p = (char*)(&x); 11
12. 6.2. Các phép toán trên biến con trỏ (2) • Phép tăng/giảm địa chỉ: - Ví dụ 1: float x[30],*p; p = &x[10];//p trỏ tới x[10] Giá trị kiểu float lưu trong 4 byte các phép tăng/giảm địa chỉ được thực hiện trên 4 byte p+i trỏ tới x[10+i], p-i trỏ tới x[10-i] - Ví dụ 2: float y[20][30]; y là một mảng gồm các dòng có 30 phần tử thực Kiểu địa chỉ của y là 30*4 = 120 byte y trỏ tới đầu dòng thứ nhất y[0][0] y+1 trỏ tới đầu dòng thứ hai y[1][0] 12
13. 6.2. Các phép toán trên biến con trỏ (3) • Nguyên tắc truy nhập bộ nhớ: - Con trỏ float truy nhập tới 4 byte, con trỏ int truy nhập tới 2 byte, con trỏ char truy nhập tới 1 byte - Ví dụ: float *pf; int *pi; char *pc; Giả sử pf trỏ tới byte 10001 thì *pf biểu thị vùng nhớ 4 byte từ 10001 đến 10004 Giả sử pi trỏ tới byte 10001 thì *pi biểu thị vùng nhớ 2 byte từ 10001 đến 10002 Giả sử pc trỏ tới byte 10001 thì *pc biểu thị vùng nhớ 1 byte 10001 13
14. 6.2. Các phép toán trên biến con trỏ (4) • Phép so sánh: - Áp dụng với các con trỏ cùng kiểu - Ví dụ: float *p1,*p2; Khi đó: + p1 p2 nếu địa chỉ p1 trỏ tới là cao hơn địa chỉ p2 trỏ tới • Lưu ý: Các phép tăng/giảm địa chỉ, truy nhập bộ nhớ và phép so sánh không dùng trên con trỏ void 14
15. 6.3. Con trỏ và hàm (1) • Tham số của hàm có thể được chia làm 2 loại: Tham số đầu vào (chứa các giá trị đã biết) và tham số đầu ra (chứa các kết quả mới nhận được) • Thông thường, hàm được dùng để trả về một kết quả thông qua tên hàm. Khi cần trả về nhiều kết quả, cần sử dụng các tham số đầu ra dạng con trỏ • Ví dụ: Hàm trả về nghiệm của phương trình bậc hai ax2 + bx + c = 0 Tham số đầu vào: a, b, c Tham số đầu ra: x1, x2 Lưu ý: Khi sử dụng các tham số đầu ra là các con trỏ, các tham số thực sự tương ứng trong lời gọi hàm phải là các địa chỉ 15
16. 6.3. Con trỏ và hàm (2) • Chương trình giải phương trình bậc 2: #include #include int ptb2(float a, float b, float c, float *x1,float *x2); int main(void) { float a,b,c,x1,x2; int kt; printf("Nhap vao cac he so:\n"); printf("a = ");scanf("%f",&a); printf("b = ");scanf("%f",&b); printf("c = ");scanf("%f",&c); 16
17. 6.3. Con trỏ và hàm (3) • Chương trình giải phương trình bậc 2: (tiếp) kt = ptb2(a,b,c,&x1,&x2); if (kt == -1) printf("Delta 0, phuong trinh co 2 nghiem: x1 = %6.2f, x2 = %6.2f",x1,x2); return 0; } 17
18. 6.3. Con trỏ và hàm (4) • Chương trình giải phương trình bậc 2: (tiếp) int ptb2(float a, float b, float c, float *x1,float *x2) { float delta; delta = b*b-4*a*c; if (delta < 0) return -1; else if (delta == 0) { *x1 = -b/(2*a); return 0; } 18
19. 6.3. Con trỏ và hàm (5) • Chương trình giải phương trình bậc 2: (tiếp) else { *x1 = (-b+sqrt(delta))/(2*a); *x2 = (-b-sqrt(delta))/(2*a); return 1; } } 19
20. 6.4. Con trỏ và dữ liệu kiểu mảng, xâu ký tự, cấu trúc • Con trỏ và mảng một chiều • Con trỏ và mảng nhiều chiều • Con trỏ và xâu ký tự • Con trỏ và cấu trúc • Mảng con trỏ 20
21. Con trỏ và mảng một chiều (1) • Nhắc lại: Phép lấy địa chỉ áp dụng được với mảng một chiều • Xét khai báo: float a[10]; Khi đó: - Tên mảng biểu thị địa chỉ đầu của mảng, tức là: a tương đương với &a[0] - Mảng a được lưu trữ trong 10 khoảng nhớ liên tiếp (mỗi khoảng 4 byte) nên: a+i tương đương với &a[i] và *(a+i) tương đương với a[i] 21
22. Con trỏ và mảng một chiều (2) • Nếu con trỏ pk trỏ tới phần tử a[k] thì: - pk+i trỏ tới phần tử thứ i sau a[k] tức là trỏ tới a[k+i] - pk-i trỏ tới phần tử thứ i trước a[k] tức là trỏ tới a[k-i] - *(pk+i) tương đương với pk[i] • Xét khai báo: float a[10],*p; Nếu thực hiện lệnh gán: p = a; 4 cách viết sau là tương đương với nhau: a[i] *(a+i) *(p+i) p[i] 22
23. Con trỏ và mảng một chiều (3) • Chương trình tính tổng, trung bình cộng cho dãy số a1, a2 , , an được viết theo 4 cách: Cách 1: (không sử dụng biến con trỏ) #include int main(void) { float a[50],s,tb; int i,n; printf("Nhap so phan tu n = ");scanf("%d",&n); 23
24. Con trỏ và mảng một chiều (4) Cách 1: (tiếp) for(i=0;i<n;i++) { printf("a[%d] = ",i); scanf("%f",&a[i]); } for(s=0,i=0;i<n;i++) s+=a[i]; tb=s/n; printf("Tong = %6.2f. Trung binh cong = %6.2f",s,tb); return 0; } 24
25. Con trỏ và mảng một chiều (5) Cách 2: - Thay lệnh nhập dữ liệu cho phần tử mảng trong chương trình ở Cách 1: Từ scanf("%f",&a[i]); thành scanf("%f",a+i); - Thay lệnh tính tổng s: Từ s+=a[i]; thành s+=*(a+i); 25
26. Con trỏ và mảng một chiều (6) Cách 3: (có sử dụng biến con trỏ) #include int main(void) { float a[50],*p,s,tb; int i,n; p=a; printf("Nhap so phan tu n = ");scanf("%d",&n); 26
27. Con trỏ và mảng một chiều (7) Cách 3 (tiếp): for(i=0;i<n;i++) { printf("a[%d] = ",i); scanf("%f",&p[i]); } for(s=0,i=0;i<n;i++) s+=p[i]; tb=s/n; printf("Tong = %6.2f. Trung binh cong = %6.2f",s,tb); return 0; } 27
28. Con trỏ và mảng một chiều (8) Cách 4: (có sử dụng biến con trỏ) - Thay lệnh nhập dữ liệu cho phần tử mảng trong chương trình ở Cách 3: Từ scanf("%f",&p[i]); thành scanf("%f",p+i); - Thay lệnh tính tổng s: Từ s+=p[i]; thành s+=*(p+i); 28
29. Con trỏ và mảng một chiều (9) • Nếu lời gọi hàm có tham số thực sự là tên mảng một chiều kiểu int (float, double, ) Khi xây dựng hàm, tham số hình thức phải được khai báo là một con trỏ có kiểu dữ liệu tương ứng int (float, double, ), ví dụ: int *p; float *p; double *p; hoặc có thể khai báo như một mảng hình thức: int p[]; float p[]; double p[]; • Ví dụ: Xây dựng chương trình tính tổng các phần tử của dãy số kiểu float, sử dụng hàm tongmang với: - Tham số đầu vào: mảng a, số phần tử của mảng n - Kết quả trả về qua tên hàm: Tổng các phần tử của mảng 29
30. Con trỏ và mảng một chiều (10) • Chương trình: #include float tongmang(float *p,int n); int main(void) { float a[50]; int i,n; printf("Nhap so phan tu n = ");scanf("%d",&n); for(i=0;i<n;i++) { printf("a[%d] = ",i); scanf("%f",a+i); } 30
31. Con trỏ và mảng một chiều (11) • Chương trình: (tiếp) printf("Tong = %6.2f",tongmang(a,n)); return 0; } float tongmang(float *p,int n) { float s; int i; for(s=0,i=0;i<n;i++) s+=p[i]; return s; } 31
32. Con trỏ và mảng nhiều chiều (1) • Nhắc lại: Phép lấy địa chỉ không áp dụng được với các phần tử của mảng nhiều chiều. Trong nhiều trường hợp câu lệnh &a[i][j] không hợp lệ và gây lỗi (mảng 2 chiều nguyên có thể dùng &a[i][j]) • Việc xử lý mảng nhiều chiều phức tạp hơn so với mảng một chiều • Xét mảng 2 chiều: (mảng một chiều của mảng) float a[2][3]; a là mảng một chiều gồm 2 phần tử, mỗi phần tử của nó là một dãy gồm 3 số thực (tương ứng với một hàng) a trỏ tới đầu hàng thứ nhất - phần tử a[0][0] a+1 trỏ tới đầu hàng thứ hai - phần tử a[1][0], 32
33. Con trỏ và mảng nhiều chiều (2) • Sử dụng con trỏ để duyệt mảng 2 chiều: Xét ví dụ: Chương trình nhập dữ float a[2][3],*p; liệu cho mảng: p = (float*)a; #include Khi đó: int main(void) p trỏ tới a[0][0] { p+1 trỏ tới a[0][1] float a[2][3],*p; p+2 trỏ tới a[0][2] int i; p+3 trỏ tới a[1][0] p = (float*)a; p+4 trỏ tới a[1][1] for(i=0;i<6;i++) p+5 trỏ tới a[1][2] scanf("%f",p+i); return 0; } 33
34. Con trỏ và mảng nhiều chiều (3) • Có thể thay thế việc sử dụng con trỏ p bằng cách sử dụng phép ép kiểu địa chỉ ngay trong hàm scanf #include int main(void) { float a[2][3]; int i; for(i=0;i<6;i++) scanf("%f",(float*)a+i); return 0; } 34
35. Con trỏ và mảng nhiều chiều (4) • Chương trình nhập dữ liệu cho mảng số thực cấp m*n không sử dụng con trỏ p: #include int main(void) { float a[20][30]; int i,j,m,n; printf("Nhap so dong m = ");scanf("%d",&m); printf("Nhap so cot n = ");scanf("%d",&n); 35
36. Con trỏ và mảng nhiều chiều (5) • Chương trình nhập dữ liệu cho mảng số thực cấp m*n không sử dụng con trỏ p (tiếp) for(i=0;i<m;i++) for(j=0;j<n;j++) { printf("a[%d][%d] = ",i,j); scanf("%f",(float*)a+i*30+j); } return 0; } 36
37. Con trỏ và mảng nhiều chiều (6) • Lưu ý: Có thể sử dụng biến trung gian để nhập dữ liệu cho mảng nhiều chiều Chương trình: #include int main(void) { float a[20][30],x; int i,j,m,n; printf("Nhap so dong m = ");scanf("%d",&m); printf("Nhap so cot n = ");scanf("%d",&n); 37
38. Con trỏ và mảng nhiều chiều (7) Chương trình (tiếp) for(i=0;i<m;i++) for(j=0;j<n;j++) { printf("a[%d][%d] = ",i,j); scanf("%f",&x); a[i][j]=x; } return 0; } 38
39. Con trỏ và mảng nhiều chiều (8) • Lời gọi hàm có tham số thực sự là tên mảng nhiều chiều: Giả sử a là mảng 2 chiều: float a[20][30]; Có 2 cách để sử dụng tên mảng 2 chiều a trong lời gọi hàm: - Cách 1: Dùng tham số con trỏ kiểu float[30] được khai báo theo một trong 2 cách: float (*p)[30]; //dùng để khai báo con trỏ Hoặc float p[][30]; //dùng để khai báo tham số Trong thân hàm, để truy nhập đến phần tử a[i][j] ta dùng cú pháp p[i][j] 39
40. Con trỏ và mảng nhiều chiều (9) - Cách 2: Dùng 2 tham số float*p; //biểu thị địa chỉ đầu của mảng a int N; //biểu thị số cột của mảng a Trong thân hàm, để truy nhập đến phần tử a[i][j] ta dùng cú pháp *(p+i*N+j) 40
41. Con trỏ và xâu ký tự (1) • Tương tự như tên mảng, tên xâu ký tự là một hằng địa chỉ biểu thị địa chỉ của byte nhớ đầu tiên trong vùng nhớ lưu xâu • Xét khai báo: char *p; Phép gán p = "Tran Ngoc Anh" là thực hiện được, lúc này p sẽ có nội dung là địa chỉ đầu của vùng nhớ lưu xâu ký tự "Tran Ngoc Anh". Khi đó có thể thực hiện các lệnh puts(p) và gets(p) bình thường 41
42. Con trỏ và xâu ký tự (2) • Xét đoạn lệnh: char *p, s[15]; s = "Tran Ngoc Anh"; // * gets(p); // Lệnh * không thực hiện được vì s là một hằng địa chỉ, không thể gán một hằng địa chỉ này cho một hằng địa chỉ khác Lệnh không sai về mặt cú pháp song không nên sử dụng vì nội dung của con trỏ p chưa xác định (chưa trỏ tới vùng nhớ nào) 42
43. Con trỏ và xâu ký tự (3) • Xét chương trình sau: #include int main(void) { char *p,s[30]; p=s; puts("Nhap ho ten cua ban: "); gets(p); puts("Xin chao"); puts(p); return 0; } Kết quả 43
44. Con trỏ và cấu trúc (1) • Xét khai báo: struct ngaythang ngayden,*p, a[10]; p là con trỏ cấu trúc lưu địa chỉ của biến cấu trúc Các phép gán sau là hợp lệ: p = &ngayden; p = &a[0]; p = a; 44
45. Con trỏ và cấu trúc (2) • Truy nhập thành phần của cấu trúc thông qua con trỏ: - Cách 1: tên_con_trỏ ->tên_thành_phần - Cách 2: (*tên_con_trỏ).tên_thành_phần Ví dụ: p->ngay (*p).ngay 45
46. Con trỏ và cấu trúc (3) • Các phép gán thông qua con trỏ, phép cộng địa chỉ đối với con trỏ cấu trúc được áp dụng tương tự như các con trỏ khác • Khi con trỏ p trỏ tới đầu mảng cấu trúc a thì: - Các cú pháp truy nhập thành phần sau là tương đương: a[i].thành_phần p[i].thành_phần (p+i)->thành phần - Các cách viết sau là tương đương: a[i] p[i] *(p+i) 46
47. Con trỏ và cấu trúc (4) • Tương tự như các kiểu dữ liệu khác, kiểu cấu trúc có thể sử dụng để khai báo cho các tham số trong hàm: - Tham số hình thức là biến cấu trúc tham số thực sự là giá trị cấu trúc - Tham số hình thức là con trỏ cấu trúc tham số thực sự là địa chỉ của biến cấu trúc - Tham số hình thức là mảng cấu trúc hoặc con trỏ cấu trúc tham số thực sự là tên mảng cấu trúc • Hàm cũng có thể trả về giá trị dạng: - Giá trị cấu trúc - Con trỏ cấu trúc 47
48. Mảng con trỏ • Mỗi phần tử của mảng có thể chứa được một địa chỉ • Cú pháp khai báo: kiểu_dữ _liệu *tên_mảng[kích_thước]; Ví dụ: float *p[50]; • Lưu ý: - Mảng con trỏ dùng để lưu địa chỉ, không dùng để lưu dữ liệu - Trước khi sử dụng mảng con trỏ cần gán cho mỗi phần tử của nó một giá trị (địa chỉ của biến hoặc của một phần tử mảng). Các phần tử của mảng kiểu char có thể được khởi tạo giá trị bằng các xâu ký tự 48
49. 6.5. Cấp phát bộ nhớ động (1) • Trước khi sử dụng các biến con trỏ, nên cấp phát vùng nhớ cho chúng • Để sử dụng các hàm quản lý việc cấp phát vùng nhớ, cần khai báo tệp tiêu đề stdlib.h (hoặc alloc.h) • Các hàm cấp phát vùng nhớ: - Hàm cấp phát vùng nhớ cho n đối tượng: calloc(n,m);//m=sizeof(đối_tượng) Cấp phát vùng nhớ có kích thước n*m byte. Nếu thành công, hàm trả về con trỏ lưu địa chỉ đầu vùng nhớ được cấp và khởi tạo cho mọi đối tượng giá trị 0; nếu không đủ bộ nhớ để cấp, hàm trả về NULL 49
50. 6.5. Cấp phát bộ nhớ động (2) • Các hàm cấp phát vùng nhớ: (tiếp) - Hàm cấp phát vùng nhớ n byte: malloc(n); Cấp phát vùng nhớ có kích thước n byte. Nếu thành công, hàm trả về con trỏ lưu địa chỉ đầu vùng nhớ được cấp, nếu không đủ bộ nhớ để cấp, hàm trả về NULL 50
51. 6.5. Cấp phát bộ nhớ động (3) • Lưu ý: Khi sử dụng các hàm calloc() và malloc() phải ép kiểu vì nguyên mẫu các hàm này trả về con trỏ kiểu void • Ví dụ: int *pa,*pb; pa = (int*)calloc(10,sizeof(int)); //Cấp phát vùng nhớ lưu được 10 số nguyên kiểu int pb = (int*)malloc(sizeof(int)); //Cấp phát vùng nhớ lưu được 1 số nguyên kiểu int 51
52. 6.5. Cấp phát bộ nhớ động (4) • Hàm cấp phát lại vùng nhớ: realloc(p,n); trong đó: - p: là con trỏ trỏ đến một vùng nhớ đã được cấp phát từ trước - n: số byte cấp phát lại Khi thành công, hàm trả về địa chỉ đầu tiên của vùng nhớ mới gồm n byte được cấp lại cho p (có thể khác với địa chỉ của lần cấp phát trước đó, khi đó nội dung của vùng nhớ cũ sẽ được chuyển tới vùng nhớ mới và có thể tiếp tục sử dụng), ngược lại hàm trả về NULL Ví dụ: realloc(pb,6); 52
53. 6.5. Cấp phát bộ nhớ động (5) • Hàm giải phóng vùng nhớ đã cấp phát: free(p); trong đó: p là con trỏ trỏ đến một vùng nhớ đã được cấp phát bởi calloc() hoặc malloc() Hàm giải phóng vùng nhớ do p quản lý Lúc này nên gán lại giá trị cho con trỏ p = NULL Ví dụ: free(pa); pa=NULL; free(pb); pb=NULL; 53
54. 6.5. Cấp phát bộ nhớ động (6) • Ví dụ về mảng động: Chương trình tìm giá trị min, max trong dãy số a1, a2, , an: #include #include int main(void) { int *a; int n,i,max,min; printf("Nhap so phan tu n = "); scanf("%d",&n); a = (int*)calloc(n,sizeof(int)); 54
55. 6.5. Cấp phát bộ nhớ động (7) • Ví dụ về mảng động: (tiếp) for(i=0;i max) max=a[i]; else if (a[i]<min) min=a[i]; printf("max = %d, min = %d",max,min); free(a); a=NULL; return 0; } 55
56. 6.5. Cấp phát bộ nhớ động (8) • Viết chương trình cho phép người dùng nhập vào từ bàn phím một dãy số nguyên: a1, a2, , an, sử dụng mảng động để lưu trữ. Sau đó xây dựng hàm tìm max, min cho mảng vừa nhập. Thông báo kết quả ra màn hình • Viết chương trình cho phép người dùng nhập vào từ bàn phím một dãy số nguyên: a1, a2, , an, sử dụng mảng động để lưu trữ. Sau đó xây dựng hàm sắp xếp lại mảng vừa nhập theo chiều tăng dần. In dãy sau khi sắp xếp ra màn hình 56