Bài giảng Ngôn ngữ lập trình C - Chương 3: Mảng và con trỏ - Nguyễn Thị Hiền

Ngôn ngữ lập trình C Chương 3 – Mảng và con trỏ 3.1. Mảng 3.2. Con trỏ 3.3. Liên hệ giữa mảng và con trỏ 3.4. Cấp phát bộ nhớ động 3.5. Xâu ký tự 3.1. Mảng  Mảng là tập hợp các giá trị cùng kiểu dữ liệu  Khai báo: <[Kích thước chiều thứ nhất][Kích thước chiều thứ 2][]>;  Mỗi phần tử của mảng lưu trữ 1 giá trị.  Mỗi một phần tử của mảng được coi như 1 biến.  Có bao nhiêu kiểu biến thì có bấy nhiêu kiểu mảng. 3.1. Mảng  Số chiều và kích thước của mảng Ví dụ các khai báo: int a[10],b[4][2]; float x[5],y[3][3]; Khi đó ta có: Thứ tự Tên mảng Kiểu mảng Số chiều Kích thước Các phần tử 1 a int 1 10 a[0],a[1],a[2]...a[9] 2 b int 2 4x2 b[0][0], b[0][1] b[1][0], b[1][1] b[2][0], b[2][1] b[3][0], b[3][1] 3 x float 1 5 x[0],x[1],x[2]...x[4] 4 y float 2 3x3 y[0][0], y[0][1], y[0][2] y[1][0], y[1][1], y[1][2] y[2][0], y[2][1], y[1][2] 3.1. Mảng  Một số lưu ý  Các phần tử của mảng được cấp phát trong các khoảng nhớ liên tiếp trong bộ nhớ.  Một phần tử cụ thể của mảng được xác định thông qua tên mảng và chỉ số của nó.  Chỉ số của mảng phải có kiểu nguyên, không vượt quá kích thước mảng.  Chỉ số của mảng bắt đầu từ 0.  Khi chỉ số vượt ra ngoài kích thước mảng, trình biên dịch vẫn biên dịch thành công, tuy nhiên khi thực hiện chương trình sẽ có lỗi.  Kích thước của mảng phải là một hằng số. 3.1. Mảng  Khởi tạo giá trị ban đầu cho biến mảng  Để khởi tạo giá trị ban đầu cho biến mảng, ta có thể sử dụng biểu thức hằng hoặc các câu lệnh gán. Ví dụ: float x[6] = {3.2,0,5.1,23,0,42}; float y[6] = {3.2}; int z[3][2] = {{25,31},{12,13},{45,15}};  Khi khởi tạo giá trị ban đầu cho biến mảng, có thể không cần chỉ ra kích thước mảng. Ví dụ: float a[]={0,5.1,23,0,42}; int m[][3]={{25,31,4},{12,13,89},{45,15,22}}; 3.1. Mảng  Một số thao tác cơ bản đối với mảng  Duyệt mảng (nhập, xuất, tính tổng, .)  Tìm kiếm  Tìm xem một phần tử nào đó có thuộc mảng hay không?  Tìm các phần tử thỏa mãn tính chất nào đó.   Sắp xếp (Mảng một chiều)  Sắp xếp giá trị các phần tử của mảng theo thứ tự tăng dần hoặc giảm dần 3.1. Mảng  Sơ đồ khối sau thể hiện thuật toán tìm kiếm nhị phân. Hãy viết chương trình nhập N số thực (N nhập từ bàn phím) vào mảng array, nhập khóa key, tìm kiếm xem key có xuất hiện trong dãy không, nếu xuất hiện thì tại vị trí nào? Begin Low = 0; High = N-1; Flag = 0; Pos = 0 Low <= High; Flag = 0 Mid = (Low + High)/2; Key = A[Mid] Flag = 1; Pos = MId Key < A[Mid] High = Mid - 1; Low = Mid +1; Flag = 0 Print “Khong tim thay” Print Key xuat hien tai vi tri Pos End Y Y Y N N Y N N 3.2. Con trỏ  Khái niệm: Là một đối tượng dữ liệu mà giá trị của nó là địa chỉ của một đối tượng khác  Đặc trưng  Không lưu trữ giá trị của biến đó  Như vậy, nếu một biến chứa địa chỉ của một biến khác, thì biến này được gọi là con trỏ, trỏ đến biến thứ hai.  Kích thước của biến con trỏ không phụ thuộc vào kiểu dữ liệu, luôn có kích thước cố định là 2 bytes hoặc 4 bytes 3.2. Con trỏ  Cú pháp khai báo * ;  Ý nghĩa: Khai báo 1 biến có tên là Tên_con_trỏ dùng để chứa địa chỉ của 1 biến có kiểu là Kiểu_dữ_liệu.  Ví dụ: int a, b, *pa, *pb; float f, *pf;  Chú ý: Nếu chưa muốn khai báo kiểu dữ liệu mà con trỏ ptr đang trỏ đến, ta sử dụng : void *ptr; 3.2. Con trỏ  Toán tử &  Dùng để định vị con trỏ đến địa chỉ của 1 biến đang làm việc  Cú pháp: = &;  Giải thích: gán địa chỉ của biến Tên_biến cho con trỏ Tên_con_trỏ pt=&i;  Khi gán địa chỉ của biến cho con trỏ cần phải lưu ý kiểu dữ liệu của chúng. int Bien_Nguyen; float *Con_Tro_Thuc; ... Con_Tro_Thuc=&Bien_Nguyen; 3.2. Con trỏ  Toán tử *  Để truy cập nội dung của ô nhớ con trỏ chỉ tới  Cú pháp: *  Với cách cách truy cập này thì * có thể coi là một biến có kiểu được mô tả trong phần khai báo biến con trỏ.  Ví dụ int x=100; int *ptr; ptr=&x; int y= *ptr; 3.2. Con trỏ  Các phép toán trên con trỏ  Phép gán: chỉ thực hiện với các con trỏ cùng kiểu. Muốn gán các con trỏ khác kiểu phải dùng phép ép kiểu. int x; char *pc; pc=(char*)(&x);  Phép tăng, giảm địa chỉ: di chuyển giữa các ô nhớ float x[30],*px; px=&x[10];  px + i trỏ tới phần tử x[10+i]  px - i trỏ tới phần tử x[10-i] 3.2. Con trỏ  Các phép toán trên con trỏ  Phép truy cập bộ nhớ: Con trỏ float trỏ tới địa chỉ dài 4 byte, con trỏ int trỏ tới địa chỉ dài 2 byte, con trỏ char trỏ tới địa chỉ dài 1 byte. float *pf; int *pi; char *pc;  Phép so sánh: so sánh các con trỏ cùng kiểu  p1<p2: địa chỉ p1 trỏ tới thấp hơn địa chỉ p2 trỏ tới.  p1==p2: địa chỉ p1 trỏ tới cũng là địa chỉ p2 trỏ tới.  p1>p2: địa chỉ p1 trỏ tới cao hơn địa chỉ p2 trỏ tới 3.2. Con trỏ  Con trỏ NULL  Con trỏ không chứa địa chỉ của bất kỳ vùng nhớ nào.  Nên khởi tạo giá trị NULL hoặc địa chỉ của vùng nhớ nào đó cho biến trỏ lúc khai báo.  Con trỏ void  Cú pháp: void *tên_con_trỏ;  Đây là con trỏ đặc biệt, con trỏ không kiểu, nó có thể nhận địa chỉ kiểu bất kỳ  Ví dụ: void *pa; float a[20][30]; pa=a;  Thường được dùng làm tham số hình thức, nhận bất kỳ địa chỉ kiểu nào từ tham số thực.  Chú ý: Các phép toán tăng giảm địa chỉ, so sánh và truy cập bộ nhớ không dùng được trên con trỏ void. 3.2. Con trỏ  Mảng con trỏ  Kiểu phần tử của biến mảng có thể là kiểu con trỏ. Các biến mà địa chỉ chứa trong các phần tử mảng con trỏ là một mảng, nhưng có vùng nhớ không liên tục.  Thường dùng để lưu mảng của chuỗi.  Ví dụ: char *s[5] = {“Orange”, “Mango”, “Coconut”, “Longan”, “Banana”}; Mỗi phần tử của s trỏ đến char * (1 chuỗi) Mảng không chứa chuỗi, chỉ trỏ đến chuỗi. 3.2. Con trỏ  Con trỏ đa cấp  Bản thân biến trỏ cũng có địa chỉ, do đó, có thể chứa địa chỉ của nó trong 1 biến trỏ khác, gọi là con trỏ trỏ đến con trỏ, hay con trỏ 2 cấp.  Số lượng dấu “*” xác định cấp của 1 biến trỏ.  Con trỏ 2 cấp có liên quan mật thiết với mảng 2 chiều.  Ví dụ: int a[2][3]; int **p = (int **)malloc(2*sizeof(int *)) p[0] = a[0]; p[1] = a[1]; 3.3. Liên hệ giữa mảng và con trỏ  Con trỏ và mảng 1 chiều  Trong C, có mối quan hệ chặt chẽ giữa con trỏ và mảng: các phần tử của mảng có thể được xác định nhờ chỉ số hoặc thông qua con trỏ.  Phép toán lấy địa chỉ:  Giả sử ta có khai báo: double b[20];  phép toán: &b[9] sẽ cho địa chỉ của phần tử b[9]  Tên mảng là một hằng địa chỉ: a  &a[0] a+i  &a[i] *(a+i)  a[i] 3.3. Liên hệ giữa mảng và con trỏ  Con trỏ và mảng nhiều chiều Giả sử, mảng hai chiều a[2][3] có 6 phần tử ứng với sáu địa chỉ liên tiếp trong bộ nhớ được xếp theo thứ tự sau:  Tên mảng a biểu thị địa chỉ đầu tiên của mảng.  Phép cộng địa chỉ: C coi mảng hai chiều là mảng (một chiều) của mảng, như vậy khai báo float a[2][3]; thì a là mảng mà mỗi phần tử của nó là một dãy 3 số thực (một hàng của mảng). 3.3. Liên hệ giữa mảng và con trỏ  Do đó:  a trỏ phần tử thứ nhất của mảng: phần tử a[0][0]  a+1 trỏ phần tử đầu hàng thứ hai của mảng: phần tử a[1][0],  ...  a+i trỏ phần tử đầu hàng thứ i của mảng: phần tử a[i][0].  Khi dùng con trỏ để duyệt mảng, ta cần làm như sau: float *pa,a[2][3]; pa=(float*)a; pa  &a[0][0] pa+1  &a[0][1] pa+2  &a[0][2] pa+3  &a[1][0] pa+4  &a[1][1] pa+5  &a[1][2] 3.4. Cấp phát bộ nhớ động  Hàm malloc và calloc cho phép cấp phát các vùng nhớ ngay trong lúc chạy chương trình. Cú pháp: void *malloc (size_t size); void *calloc (size_t nItems, size_t size)  Hàm calloc cấp phát vùng nhớ và khởi tảo tất cả các bit trong vùng nhớ mới cấp phát về 0.  Hàm malloc chỉ cấp phát vùng nhớ 21 3.4. Cấp phát bộ nhớ động  Hàm free() được sử dụng để giải phóng bộ nhớ khi nó không cần dùng nữa.  Cú pháp: void free(void*ptr);  Hàm này giải phóng không gian được trỏ bởi ptr, để dùng cho tương lai.  ptr phải được dùng trước đó với lời gọi hàm malloc(), calloc(), hoặc realloc(). 22 3.4. Cấp phát bộ nhớ động  Cấp phát lại vùng nhớ: realloc  C dung hàm realloc để cấp phát lại vùng nhớ, thực hiện sao chép nội dung của vùng nhớ cũ sang vùng nhớ mới.  Cú pháp: void *realloc(void *block, size_t size); 3.4. Cấp phát bộ nhớ động Cấp phát động mảng 1 chiều, nhập và in mảng sử dụng con trỏ #include #include main() { int *p,n,i,j,temp; printf(“Nhap n = ”);scanf(“%d”,&n); p = (int *)malloc(n*sizeof(int)); // p = (int *)calloc (n, sizeof(int); for(i=0; i<n; i++) { printf(“\n Enter value: %d : ”, i+1); scanf(“%d”,p+i); } for(i=1; i<10; i++) printf(“%d\n“,i, *(p+i)); free(p); } 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 3.4. Cấp phát bộ nhớ động Cấp phát động mảng 2 chiều, nhập và in mảng sử dụng con trỏ #include main() { float **a; int m,n, i, j; printf("m = ");scanf("%d",&m); printf("n = ");scanf("%d",&n); a = (float **) malloc(m*sizeof(float *)); for (i=0;i<m;i++){ a[i] = (float *) malloc (n*sizeof (float)); for (j = 0;j<n;j++){ printf("a[%d][%d] = ",i,j); scanf("%f",a[i]+j); } } for (i =0;i<m;i++){ for (j =0;j<n;j++) printf("%.2f\t",a[i][j]); printf("\n"); } } 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 3.4. Cấp phát bộ nhớ động  Ví dụ:  Nhập vào một ma trận A cấp mxn (m,n nhập từ bàn phím). Tìm và in ra phần tử lớn nhất của hàng k (k nhập từ bàn phím)  Nhập vào một ma trận A cấp mxn (m,n nhập từ bàn phím). Tìm và in ra hàng có tổng các phần tử lớn nhất.  Nhập vào một ma trận A cấp mxn (m,n nhập từ bàn phím). Kiểm tra xem ma trận A có phải là ma trận tam giác trên không? 3.5. Xâu ký tự  Khái niệm:  Là một dãy ký tự đặt trong hai dấu nháy kép, ví dụ như xâu ký tự: "Viet nam".  Khi gặp một xâu ký tự, máy sẽ cấp phát một lượng ô nhớ kiểu char đủ để chứa các ký tự của xâu và chứa thêm ký tự ‘\0’.  Xâu ký tự là một hằng địa chỉ . 3.5. Xâu ký tự  Khai báo và khởi tạo:  Bằng một mảng  Bằng một con trỏ  Ví dụ: char firstname[10] = "Bill"; char lastname[] = "Clinton"; char *namept = "Bill Clinton"; 3.5. Xâu ký tự  Phép gán xâu ký tự: Gán xâu ký tự cho một con trỏ char *namept; namept = "Bill Clinton";  Chú ý: Không thể gán char firstname[15]; firstname = "Bill Clinton";  Nhận và lưu vào mảng chuỗi ký tự được gõ từ bàn phím bằng hàm gets() gets(firstname); 3.5. Xâu ký tự  Gán xâu ký tự:  Lưu ý: char *xau, ten[15]; ten="Ha noi" ; (1) gets(xau); (2) xau= "Ha noi" ; gets(ten) ;  Các câu lệnh (1) và (2) là không hợp lệ.  Câu lệnh (1) sai vì ten 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.  Câu lệnh (2) không thực hiện được bởi mục đích của câu lệnh là đọc từ bàn phím một dãy ký tự và lưu vào một vùng nhớ mà con trỏ xau trỏ tới vì địa chỉ vùng nhớ của con trỏ xau còn chưa xác định. 3.5. Xâu ký tự  Một số hàm xử lý xâu:  Xác định chiều dài xâu: strlen(địa_chỉ_chuỗi_ký tự);  Sao chép một chuỗi sang một chuỗi khác: strcpy() char* s; char* src = “KSDS13” strcpy(s, src); Ghép hai xâu: strcat() char D[20]= “DTVT”; strcat(D, “+VTDT");