Bài tập C: con trỏ, cấp phát động, struct, tệp và danh sách liên kết
Nhóm bài này bám Chương 7 đến Chương 9, thiên về viết code. Luôn kiểm NULL trước khi
dùng con trỏ, giải phóng bộ nhớ khi xong. Tự làm trước, bí thì mở Gợi ý.
Bài 1: duyệt mảng bằng con trỏ
Cho mảng số nguyên a gồm 5 phần tử. Dùng một con trỏ và số học con trỏ (không dùng chỉ
số a[i]) để duyệt qua mảng và in tổng các phần tử.
Gợi ý
Cho con trỏ trỏ tới phần tử đầu, rồi cộng dồn *(p + i); đây chính là cách trình biên
dịch hiểu a[i].
#include <stdio.h>
int main(void) {
int a[5] = {3, 1, 4, 1, 5};
int *p = a; /* p points to a[0] */
int sum = 0;
for (int i = 0; i < 5; i++) {
sum += *(p + i); /* same value as a[i] */
}
printf("%d\n", sum);
return 0;
}
Xem lại bài Con trỏ.
Bài 2: cấp phát mảng động đọc n phần tử
Nhập số nguyên dương n, cấp phát động một mảng n số nguyên, đọc n số vào mảng rồi in
lại theo thứ tự ngược. Giải phóng bộ nhớ trước khi kết thúc.
Gợi ý
Dùng malloc(n * sizeof(int)), kiểm NULL ngay sau khi cấp phát, chỉ dùng mảng khi đã
chắc chắn khác NULL. sizeof trả về kiểu size_t nên phép nhân kích thước là an toàn.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int n;
if (scanf("%d", &n) != 1 || n <= 0) return 1;
int *a = malloc(n * sizeof(int)); /* size in size_t */
if (a == NULL) return 1; /* check before use */
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = n - 1; i >= 0; i--) printf("%d ", a[i]);
printf("\n");
free(a); /* release memory */
return 0;
}
Xem lại bài Cấp phát động.
Bài 3: mảng lớn dần với realloc
Đọc các số nguyên tới khi gặp số 0 thì dừng (không biết trước có bao nhiêu số). Lưu tất
cả vào một mảng động, cứ đầy thì mở rộng gấp đôi bằng realloc. In lại số phần tử đã đọc.
Gợi ý
Luôn hứng kết quả realloc vào một con trỏ tạm; nếu gán thẳng vào con trỏ cũ mà realloc
trả NULL thì mất địa chỉ khối cũ và bị rò rỉ. Khi tạm là NULL, khối cũ vẫn còn hợp lệ
nên phải free nó rồi mới thoát.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int cap = 4, count = 0;
int *a = malloc(cap * sizeof(int));
if (a == NULL) return 1;
int x;
while (scanf("%d", &x) == 1 && x != 0) {
if (count == cap) {
cap *= 2;
int *tmp = realloc(a, cap * sizeof(int)); /* catch in temp */
if (tmp == NULL) { free(a); return 1; } /* old block still valid */
a = tmp;
}
a[count++] = x;
}
printf("%d\n", count);
free(a);
return 0;
}
Xem lại bài Cấp phát động.
Bài 4: cấp phát qua con trỏ đôi
Viết hàm int make_array(int **out, int n) cấp phát mảng n số nguyên và trả con trỏ mảng
về cho hàm gọi qua tham số out. Hàm trả 1 nếu thành công, 0 nếu thất bại. Trong main
gọi hàm rồi sử dụng và giải phóng mảng.
Gợi ý
out là con trỏ đôi (int **); muốn ghi con trỏ mới vào biến của hàm gọi thì gán qua
*out. Chỉ ghi khi cấp phát thành công.
#include <stdio.h>
#include <stdlib.h>
/* allocate n ints, return pointer through out */
int make_array(int **out, int n) {
int *p = malloc(n * sizeof(int));
if (p == NULL) return 0; /* failure, do not touch out */
*out = p; /* write pointer back to caller */
return 1;
}
int main(void) {
int *a = NULL;
if (!make_array(&a, 10)) return 1;
for (int i = 0; i < 10; i++) a[i] = i * i;
printf("%d\n", a[9]);
free(a);
return 0;
}
Xem lại bài Con trỏ.
Bài 5: mảng struct sinh viên và sắp xếp
Khai báo struct SinhVien gồm tên và điểm. Nhập 3 sinh viên vào một mảng struct, sắp xếp
theo điểm giảm dần rồi in ra. Hàm hoán đổi nhận con trỏ struct.
Gợi ý
Truyền con trỏ struct để đổi chỗ tại chỗ, tránh sao chép cả struct nhiều lần. Kích thước
sizeof(SinhVien) thường lớn hơn tổng kích thước các thành viên vì trình biên dịch chèn
đệm byte để căn lề.
#include <stdio.h>
typedef struct {
char name[50];
float diem;
} SinhVien;
void doi(SinhVien *x, SinhVien *y) { /* swap via struct pointers */
SinhVien t = *x; *x = *y; *y = t;
}
int main(void) {
SinhVien sv[3];
for (int i = 0; i < 3; i++)
scanf("%49s %f", sv[i].name, &sv[i].diem);
for (int i = 0; i < 3; i++)
for (int j = i + 1; j < 3; j++)
if (sv[j].diem > sv[i].diem) doi(&sv[i], &sv[j]);
for (int i = 0; i < 3; i++)
printf("%s %.1f\n", sv[i].name, sv[i].diem);
return 0;
}
Xem lại bài Cấu trúc struct.
Bài 6: đọc số từ tệp tính trung bình
Mở tệp so.txt chứa các số thực cách nhau bởi khoảng trắng. Đọc lần lượt, tính trung bình
cộng rồi in ra. Đóng tệp sau khi dùng.
Gợi ý
fopen trả NULL khi lỗi nên phải kiểm trước khi đọc. Điều kiện lặp dựa vào giá trị trả
về của fscanf (số trường đọc được), không dùng feof làm điều kiện lặp vì feof chỉ báo
đúng sau khi đã đọc hụt, dễ xử lý dư một lần.
#include <stdio.h>
int main(void) {
FILE *f = fopen("so.txt", "r");
if (f == NULL) return 1; /* check before reading */
double x, sum = 0.0;
int n = 0;
while (fscanf(f, "%lf", &x) == 1) { /* loop on read result, not feof */
sum += x;
n++;
}
fclose(f); /* close when done */
if (n > 0) printf("%.2f\n", sum / n);
return 0;
}
Xem lại bài Tệp.
Bài 7: chèn và xoá nút danh sách liên kết
Xây danh sách liên kết đơn số nguyên. Viết hàm chèn vào đầu, hàm xoá nút đầu tiên mang một giá trị cho trước, và hàm duyệt in. Nhớ giải phóng toàn bộ danh sách khi kết thúc.
Gợi ý
Chèn đầu chỉ cần cấp một nút mới trỏ next vào đầu cũ rồi trả nút mới làm đầu. Khi xoá,
free nút đúng một lần và không dùng lại con trỏ đã giải phóng (con trỏ treo). Dùng một nút
giả (dummy) giúp xử lý cả trường hợp xoá ngay đầu danh sách.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
/* insert at head, return new head */
Node *push(Node *head, int v) {
Node *p = malloc(sizeof(Node));
if (p == NULL) return head; /* keep list on failure */
p->data = v;
p->next = head;
return p;
}
/* remove first node holding value v */
Node *erase(Node *head, int v) {
Node dummy;
dummy.next = head;
Node *prev = &dummy;
while (prev->next != NULL) {
if (prev->next->data == v) {
Node *dead = prev->next;
prev->next = dead->next;
free(dead); /* free once, do not reuse dead */
break;
}
prev = prev->next;
}
return dummy.next;
}
/* print every node */
void print_list(Node *head) {
for (Node *p = head; p != NULL; p = p->next) printf("%d ", p->data);
printf("\n");
}
/* free the whole list, node by node */
void free_list(Node *head) {
while (head != NULL) {
Node *dead = head;
head = head->next;
free(dead);
}
}
int main(void) {
Node *head = NULL;
head = push(head, 1);
head = push(head, 2);
head = push(head, 3);
print_list(head); /* 3 2 1 */
head = erase(head, 2);
print_list(head); /* 3 1 */
free_list(head);
return 0;
}
Xem lại bài Danh sách liên kết.
Bài 8: hoán đổi hai con trỏ qua con trỏ đôi
Viết hàm doi_con_tro(int **p, int **q) tráo đổi chính hai con trỏ (không phải tráo giá
trị chúng trỏ tới). Sau khi gọi, con trỏ đang trỏ tới x phải quay sang trỏ tới y và
ngược lại.
Gợi ý
Muốn sửa được biến con trỏ của hàm gọi thì phải nhận địa chỉ của nó, tức là con trỏ đôi
int **. Thao tác *p cho ra chính con trỏ cần đổi. Đây là mức gián tiếp một bậc cao hơn
so với hoán đổi hai số nguyên.
#include <stdio.h>
// swap the two pointers themselves, not the values they point to
void doi_con_tro(int **p, int **q) {
int *tam = *p;
*p = *q;
*q = tam;
}
int main(void) {
int x = 3, y = 7;
int *a = &x, *b = &y;
doi_con_tro(&a, &b);
printf("%d %d\n", *a, *b); // 7 3
return 0;
}
Xem lại bài Con trỏ.
Bài 9: cấp phát ma trận hai chiều động
Cấp phát động một ma trận rows x cols số nguyên bằng mảng con trỏ (mỗi dòng là một khối
riêng), gán giá trị rồi in một phần tử. Giải phóng đúng thứ tự: giải phóng từng dòng trước,
sau đó giải phóng mảng con trỏ dòng.
Gợi ý
Cấp rows con trỏ int *, rồi cấp cho mỗi dòng một mảng cols số nguyên. Kiểm NULL
sau mỗi lần cấp phát, chỉ dùng khi khác NULL. Khi giải phóng phải làm ngược chiều cấp
phát để không mất địa chỉ các dòng.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int rows = 3, cols = 4;
int **m = malloc(rows * sizeof(int *)); /* array of row pointers */
if (m == NULL) return 1; /* check before use */
for (int i = 0; i < rows; i++) {
m[i] = malloc(cols * sizeof(int)); /* one row */
if (m[i] == NULL) return 1;
}
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
m[i][j] = i * cols + j;
printf("%d\n", m[2][3]); /* 11 */
for (int i = 0; i < rows; i++) free(m[i]); /* free each row first */
free(m); /* then the row pointers */
return 0;
}
Xem lại bài Cấp phát động.
Bài 10: sắp xếp mảng struct theo tên
Khai báo struct Nguoi gồm tên và tuổi. Cho một mảng ba người, sắp xếp theo tên tăng dần
theo bảng chữ cái rồi in ra. Dùng strcmp để so sánh hai chuỗi tên.
Gợi ý
strcmp(x, y) trả về số âm khi x đứng trước y, 0 khi bằng, số dương khi x đứng
sau. So sánh trường tên để quyết định đổi chỗ. Khác với sắp theo trường số, ở đây tiêu chí
là chuỗi. Cần #include <string.h>.
#include <stdio.h>
#include <string.h>
typedef struct {
char ten[50];
int tuoi;
} Nguoi;
int main(void) {
Nguoi a[3] = {{"Chau", 20}, {"An", 22}, {"Binh", 21}};
for (int i = 0; i < 3; i++)
for (int j = i + 1; j < 3; j++)
if (strcmp(a[j].ten, a[i].ten) < 0) { /* compare by name */
Nguoi t = a[i];
a[i] = a[j];
a[j] = t;
}
for (int i = 0; i < 3; i++)
printf("%s %d\n", a[i].ten, a[i].tuoi);
return 0;
}
Xem lại bài Cấu trúc struct.
Bài 11: đảo ngược danh sách liên kết
Cho một danh sách liên kết đơn, viết hàm dao(Node *head) đảo chiều các liên kết và trả
về đầu mới. Không cấp thêm nút nào, chỉ đổi hướng con trỏ next.
Gợi ý
Duyệt một lần, giữ ba con trỏ: prev, nút hiện tại và nút kế. Trước khi trỏ next của nút
hiện tại về prev, phải lưu lại nút kế nếu không sẽ mất phần còn lại của danh sách. Kết
thúc, prev là đầu mới.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
/* reverse the list, return the new head */
Node *dao(Node *head) {
Node *prev = NULL;
while (head != NULL) {
Node *nxt = head->next; /* save before rewiring */
head->next = prev;
prev = head;
head = nxt;
}
return prev;
}
int main(void) {
Node *head = NULL;
for (int i = 1; i <= 3; i++) { /* build 3 -> 2 -> 1 */
Node *p = malloc(sizeof(Node));
if (p == NULL) return 1;
p->data = i;
p->next = head;
head = p;
}
head = dao(head); /* now 1 -> 2 -> 3 */
for (Node *p = head; p != NULL; p = p->next) printf("%d ", p->data);
printf("\n");
while (head != NULL) { /* free the whole list */
Node *dead = head;
head = head->next;
free(dead);
}
return 0;
}
Xem lại bài Danh sách liên kết.
Bài 12: đếm số dòng trong tệp
Mở tệp vanban.txt, đếm số dòng (số ký tự xuống dòng) rồi in ra. Đóng tệp sau khi dùng.
Gợi ý
fopen trả NULL khi lỗi nên phải kiểm trước khi đọc. Đọc từng ký tự bằng fgetc, hàm
này trả về kiểu int (không phải char) để phân biệt được EOF với dữ liệu, nên biến
hứng phải là int. Mỗi lần gặp \n thì tăng bộ đếm.
#include <stdio.h>
int main(void) {
FILE *f = fopen("vanban.txt", "r");
if (f == NULL) return 1; /* check before reading */
int dong = 0, ch;
while ((ch = fgetc(f)) != EOF) { /* fgetc returns int, not char */
if (ch == '\n') dong++;
}
fclose(f); /* close when done */
printf("%d\n", dong);
return 0;
}
Xem lại bài Tệp.
Câu hỏi tự kiểm
- 1Khi malloc hoặc fopen thất bại, chúng trả về giá trị gì mà ta phải kiểm trước khi dùng?
- 2Vì sao phải hứng kết quả của realloc vào một con trỏ tạm thay vì gán thẳng lại con trỏ cũ?
- 3Sau khi free một con trỏ, điều nào đúng?
- 4Vì sao không nên dùng feof làm điều kiện của vòng lặp đọc tệp?