1. C语言经典题目解析(71-80题)
作为C语言学习的重要环节,算法题目练习是检验编程能力的最佳方式。下面我将详细解析71-80题的实现思路和代码细节,这些题目涵盖了结构体、链表、指针函数等核心知识点。
1.1 学生信息管理系统(第71题)
这个题目要求我们实现一个简单的学生信息管理系统,主要考察结构体的使用。
c复制#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
typedef struct Stu {
char name[20];
char sex[5];
int age;
};
void input(struct Stu* stu) {
for (int i = 0; i < 5; i++) {
printf("请输入第%d个学生的信息(姓名 性别 年龄):", i+1);
scanf("%s %s %d", stu[i].name, stu[i].sex, &stu[i].age);
}
}
void output(struct Stu* stu) {
printf("\n学生信息如下:\n");
for (int i = 0; i < 5; i++) {
printf("姓名:%-10s 性别:%-5s 年龄:%d\n",
stu[i].name, stu[i].sex, stu[i].age);
}
}
int main() {
struct Stu stu[5];
input(stu);
output(stu);
return 0;
}
关键点解析:
- 结构体定义:使用typedef定义学生结构体,包含姓名、性别和年龄字段
- 输入输出分离:将输入(input)和输出(output)逻辑封装成独立函数
- 格式化输出:使用%-10s等格式控制符使输出对齐美观
常见问题:
- 缓冲区溢出风险:使用scanf直接读取字符串存在风险,建议添加长度限制
- 性别字段长度:定义5字节是为了容纳"male"和"female"等字符串
- 输入提示:添加序号提示提高用户体验
1.2 链表基础操作(第72-74题)
1.2.1 链表创建与遍历(第72题)
c复制#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* createList(int arr[], int n) {
if (n == 0) return NULL;
Node* head = (Node*)malloc(sizeof(Node));
head->data = arr[0];
head->next = NULL;
Node* tail = head;
for (int i = 1; i < n; i++) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = arr[i];
newNode->next = NULL;
tail->next = newNode;
tail = newNode;
}
return head;
}
void printList(Node* head) {
Node* p = head;
while (p != NULL) {
printf("%d->", p->data);
p = p->next;
}
printf("NULL\n");
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
Node* head = createList(arr, 5);
printList(head);
// 释放内存
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
链表操作要点:
- 头节点创建:需要单独处理第一个节点的创建
- 尾指针技巧:使用tail指针可以避免每次遍历到链表末尾
- 内存管理:动态分配的内存必须手动释放
1.2.2 链表反转(第73题)
c复制Node* reverseList(Node* head) {
Node* prev = NULL;
Node* curr = head;
Node* next = NULL;
while (curr != NULL) {
next = curr->next; // 保存下一个节点
curr->next = prev; // 反转指针
prev = curr; // 移动prev
curr = next; // 移动curr
}
return prev; // 新头节点
}
反转算法解析:
- 三指针法:使用prev、curr、next三个指针逐步反转
- 边界条件:空链表和单节点链表需要特殊处理
- 时间复杂度:O(n),空间复杂度O(1)
1.2.3 链表排序(第74题)
c复制void selectionSort(Node* head) {
Node *i, *j, *min;
int temp;
for (i = head; i != NULL; i = i->next) {
min = i;
for (j = i->next; j != NULL; j = j->next) {
if (j->data < min->data) {
min = j;
}
}
if (min != i) {
temp = i->data;
i->data = min->data;
min->data = temp;
}
}
}
排序注意事项:
- 选择排序实现简单但效率较低(O(n²))
- 只交换数据域不改变指针结构
- 对于大型链表建议使用归并排序等更高效算法
1.3 数字处理与字符串操作(第75-80题)
1.3.1 数字反转(第75题)
c复制int reverseNumber(int num) {
int reversed = 0;
while (num != 0) {
reversed = reversed * 10 + num % 10;
num /= 10;
}
return reversed;
}
关键点:
- 处理负数:可以先记录符号再处理绝对值
- 溢出检查:反转后可能超出int范围,需要添加检查
- 尾随零:如100反转后应为1而不是001
1.3.2 指针函数应用(第76题)
c复制double sumOdd(int n) {
double sum = 0;
for (int i = 1; i <= n; i += 2) {
sum += 1.0 / i;
}
return sum;
}
double sumEven(int n) {
double sum = 0;
for (int i = 2; i <= n; i += 2) {
sum += 1.0 / i;
}
return sum;
}
double calculateSum(int n) {
double (*funcPtr)(int);
funcPtr = (n % 2 == 1) ? sumOdd : sumEven;
return funcPtr(n);
}
指针函数技巧:
- 函数指针声明:注意返回类型和参数类型的匹配
- 条件选择:根据n的奇偶性选择不同处理函数
- 代码复用:避免重复的条件判断
1.3.3 字符串排序(第79题)
c复制#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
void sortStrings(char str[][MAX_LEN], int n) {
char temp[MAX_LEN];
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n; j++) {
if (strcmp(str[i], str[j]) > 0) {
strcpy(temp, str[i]);
strcpy(str[i], str[j]);
strcpy(str[j], temp);
}
}
}
}
int main() {
char strings[3][MAX_LEN];
printf("输入3个字符串:\n");
for (int i = 0; i < 3; i++) {
fgets(strings[i], MAX_LEN, stdin);
strings[i][strcspn(strings[i], "\n")] = '\0';
}
sortStrings(strings, 3);
printf("排序结果:\n");
for (int i = 0; i < 3; i++) {
printf("%s\n", strings[i]);
}
return 0;
}
字符串处理要点:
- 安全输入:使用fgets代替gets避免缓冲区溢出
- 去除换行:strcspn找到换行符位置并替换为结束符
- 二维数组:字符串数组实际上是字符的二维数组
1.3.4 猴子分桃问题(第80题)
c复制int findMinPeaches() {
int peaches = 1; // 从1开始尝试
int found = 0;
while (!found) {
int remaining = peaches;
int valid = 1;
for (int i = 0; i < 5; i++) {
if ((remaining - 1) % 5 == 0) {
remaining = (remaining - 1) / 5 * 4;
} else {
valid = 0;
break;
}
}
if (valid && remaining > 0) {
found = 1;
return peaches;
}
peaches++;
}
return -1; // 未找到解
}
算法分析:
- 逆向思维:从最后一步倒推初始数量
- 数学建模:每次分桃都满足(peach-1)能被5整除
- 优化:可以增加步长减少循环次数
2. 编程技巧与最佳实践
2.1 内存管理规范
- malloc/free配对使用:每个malloc必须有对应的free
- 检查分配结果:malloc可能返回NULL,需要错误处理
- 避免内存泄漏:特别是链表等动态数据结构
c复制Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
fprintf(stderr, "内存分配失败\n");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
2.2 防御性编程
- 输入验证:检查用户输入是否合法
- 边界条件:处理空指针、空链表等特殊情况
- 错误处理:使用返回值或异常处理机制
c复制void safePrintList(Node* head) {
if (head == NULL) {
printf("链表为空\n");
return;
}
// 正常打印逻辑
}
2.3 代码优化建议
- 函数单一职责:每个函数只做一件事
- 避免全局变量:使用参数传递数据
- 合理注释:解释复杂逻辑,但避免过度注释
3. 常见问题与调试技巧
3.1 链表常见错误
- 指针丢失:在修改指针前确保备份
- 头节点处理:插入/删除头节点需要特殊处理
- 循环引用:检查链表是否形成环
3.2 调试方法
- 打印调试:在关键位置打印变量值
- 分治法:隔离问题区域逐步排查
- 内存检查工具:如valgrind检测内存问题
3.3 性能优化
- 算法选择:根据数据规模选择合适的算法
- 缓存友好:优化数据访问模式
- 避免重复计算:存储中间结果
4. 扩展练习建议
- 双向链表实现:增加前驱指针
- 环形缓冲区:固定大小的循环队列
- 多项式相加:使用链表表示多项式
- 大数运算:用链表实现超长整数运算
通过这10道题目的练习,可以全面掌握C语言的核心数据结构与算法实现。建议读者不仅要理解代码,还要自己动手实现并尝试优化。编程能力的提升关键在于实践,遇到问题时多思考、多调试,积累经验。