14天速成PAT-BASIC基础知识！

两周关于PAT的基础学习计划。

Day 1: 基本语法和输入输出

• 知识点

  • 数据类型（int, long, float, double, char）
  • 变量声明和初始化
  • 输入输出函数（scanf, printf）
  • 控制结构（if-else, switch, for, while, do-while）

• 代码练习

  • 编写一个程序，读取两个整数并输出它们的和。
  • 编写一个程序，根据用户输入的成绩判断是否及格（60分以上）。
  • 编写一个程序，使用for循环打印1到100的所有整数。

#include <stdio.h>int main() {int a, b;scanf("%d %d", &a, &b);printf("Sum: %d\n", a + b);return 0;
}// 判断成绩是否及格
#include <stdio.h>int main() {int score;scanf("%d", &score);if (score >= 60) {printf("Pass\n");} else {printf("Fail\n");}return 0;
}// 打印1到100
#include <stdio.h>int main() {for (int i = 1; i <= 100; ++i) {printf("%d ", i);}return 0;
}

Day 2: 数组和字符串

• 知识点

  • 一维数组的声明、初始化和访问
  • 字符串的基本操作（strlen, strcpy, strcat, strcmp, strstr）

• 代码练习

  • 编写一个程序，读取一个数组并输出其最大值。
  • 编写一个程序，读取两个字符串并比较它们是否相等。
  • 编写一个程序，将两个字符串连接起来并输出结果。

#include <stdio.h>
#include <string.h>int main() {int arr[5];for (int i = 0; i < 5; ++i) {scanf("%d", &arr[i]);}int max = arr[0];for (int i = 1; i < 5; ++i) {if (arr[i] > max) {max = arr[i];}}printf("Max: %d\n", max);return 0;
}// 比较两个字符串
#include <stdio.h>
#include <string.h>int main() {char str1[100], str2[100];scanf("%s %s", str1, str2);if (strcmp(str1, str2) == 0) {printf("Equal\n");} else {printf("Not Equal\n");}return 0;
}// 连接两个字符串
#include <stdio.h>
#include <string.h>int main() {char str1[100], str2[100], result[200];scanf("%s %s", str1, str2);strcpy(result, str1);strcat(result, str2);printf("Result: %s\n", result);return 0;
}

Day 3: 函数和指针

• 知识点

  • 函数的定义和调用
  • 参数传递（值传递和指针传递）
  • 指针的基本概念和用法

• 代码练习

  • 编写一个函数，计算两个整数的乘积并返回结果。
  • 编写一个函数，交换两个整数的值（使用指针）。
  • 编写一个函数，查找数组中的最大值（使用指针）。

#include <stdio.h>int multiply(int a, int b) {return a * b;
}void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}int find_max(int *arr, int size) {int max = arr[0];for (int i = 1; i < size; ++i) {if (arr[i] > max) {max = arr[i];}}return max;
}int main() {int a = 5, b = 10;printf("Product: %d\n", multiply(a, b));swap(&a, &b);printf("After swap: a = %d, b = %d\n", a, b);int arr[] = {1, 2, 3, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);printf("Max in array: %d\n", find_max(arr, size));return 0;
}

Day 4: 结构体和文件操作

• 知识点

  • 结构体的定义和使用
  • 文件的打开、读写和关闭（fopen, fscanf, fprintf, fclose）

• 代码练习

  • 定义一个学生结构体，包含姓名和成绩，并编写一个程序读取多个学生的信息并输出。
  • 编写一个程序，从文件中读取数据并处理。

#include <stdio.h>
#include <string.h>struct Student {char name[50];int score;
};void read_students(struct Student students[], int n) {for (int i = 0; i < n; ++i) {scanf("%s %d", students[i].name, &students[i].score);}
}void print_students(struct Student students[], int n) {for (int i = 0; i < n; ++i) {printf("Name: %s, Score: %d\n", students[i].name, students[i].score);}
}int main() {struct Student students[3];read_students(students, 3);print_students(students, 3);return 0;
}// 从文件中读取数据
#include <stdio.h>int main() {FILE *file = fopen("data.txt", "r");if (file == NULL) {printf("File not found!\n");return 1;}int num;while (fscanf(file, "%d", &num) != EOF) {printf("%d\n", num);}fclose(file);return 0;
}

Day 5: 动态内存分配

• 知识点

  • malloc, calloc, realloc, free
  • 动态数组的创建和管理

• 代码练习

  • 编写一个程序，动态分配一个数组并读取用户输入的数据。
  • 编写一个程序，动态分配一个二维数组并进行基本操作。

#include <stdio.h>
#include <stdlib.h>int main() {int n;printf("Enter the number of elements: ");scanf("%d", &n);int *arr = (int *)malloc(n * sizeof(int));if (arr == NULL) {printf("Memory allocation failed!\n");return 1;}for (int i = 0; i < n; ++i) {scanf("%d", &arr[i]);}for (int i = 0; i < n; ++i) {printf("%d ", arr[i]);}printf("\n");free(arr);return 0;
}// 动态分配二维数组
#include <stdio.h>
#include <stdlib.h>int main() {int rows, cols;printf("Enter the number of rows and columns: ");scanf("%d %d", &rows, &cols);int **matrix = (int **)malloc(rows * sizeof(int *));for (int i = 0; i < rows; ++i) {matrix[i] = (int *)malloc(cols * sizeof(int));}for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {scanf("%d", &matrix[i][j]);}}for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {printf("%d ", matrix[i][j]);}printf("\n");}for (int i = 0; i < rows; ++i) {free(matrix[i]);}free(matrix);return 0;
}

Day 6: 排序算法

• 知识点

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 快速排序（qsort）

• 代码练习

  • 实现冒泡排序、选择排序和插入排序。
  • 使用qsort对数组进行排序。

#include <stdio.h>
#include <stdlib.h>void bubble_sort(int arr[], int n) {for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}void selection_sort(int arr[], int n) {for (int i = 0; i < n - 1; ++i) {int min_index = i;for (int j = i + 1; j < n; ++j) {if (arr[j] < arr[min_index]) {min_index = j;}}int temp = arr[i];arr[i] = arr[min_index];arr[min_index] = temp;}
}void insertion_sort(int arr[], int n) {for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];--j;}arr[j + 1] = key;}
}int compare(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}int main() {int arr[] = {5, 3, 8, 1, 2};int n = sizeof(arr) / sizeof(arr[0]);// Bubble Sortint arr_bubble[n];for (int i = 0; i < n; ++i) {arr_bubble[i] = arr[i];}bubble_sort(arr_bubble, n);printf("Bubble Sort: ");for (int i = 0; i < n; ++i) {printf("%d ", arr_bubble[i]);}printf("\n");// Selection Sortint arr_selection[n];for (int i = 0; i < n; ++i) {arr_selection[i] = arr[i];}selection_sort(arr_selection, n);printf("Selection Sort: ");for (int i = 0; i < n; ++i) {printf("%d ", arr_selection[i]);}printf("\n");// Insertion Sortint arr_insertion[n];for (int i = 0; i < n; ++i) {arr_insertion[i] = arr[i];}insertion_sort(arr_insertion, n);printf("Insertion Sort: ");for (int i = 0; i < n; ++i) {printf("%d ", arr_insertion[i]);}printf("\n");// Quick Sortint arr_quick[n];for (int i = 0; i < n; ++i) {arr_quick[i] = arr[i];}qsort(arr_quick, n, sizeof(int), compare);printf("Quick Sort: ");for (int i = 0; i < n; ++i) {printf("%d ", arr_quick[i]);}printf("\n");return 0;
}

Day 7: 递归和回溯

• 知识点

  • 递归的基本概念
  • 回溯算法（八皇后问题、全排列）

• 代码练习

  • 实现阶乘函数（递归）
  • 实现斐波那契数列（递归）
  • 解决八皇后问题（回溯）

#include <stdio.h>int factorial(int n) {if (n == 0 || n == 1) {return 1;}return n * factorial(n - 1);
}int fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n - 1) + fibonacci(n - 2);
}int board[8][8];int is_safe(int row, int col) {for (int i = 0; i < col; ++i) {if (board[row][i]) {return 0;}}for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {if (board[i][j]) {return 0;}}for (int i = row, j = col; i < 8 && j >= 0; ++i, --j) {if (board[i][j]) {return 0;}}return 1;
}int solve_n_queens(int col) {if (col >= 8) {return 1;}for (int i = 0; i < 8; ++i) {if (is_safe(i, col)) {board[i][col] = 1;if (solve_n_queens(col + 1)) {return 1;}board[i][col] = 0;}}return 0;
}void print_board() {for (int i = 0; i < 8; ++i) {for (int j = 0; j < 8; ++j) {printf("%d ", board[i][j]);}printf("\n");}printf("\n");
}int main() {int n = 5;printf("Factorial of %d: %d\n", n, factorial(n));printf("Fibonacci of %d: %d\n", n, fibonacci(n));if (solve_n_queens(0)) {print_board();} else {printf("No solution exists.\n");}return 0;
}

Day 8: 数学问题

• 知识点

  • 素数筛法（埃氏筛法）
  • 最大公约数（欧几里得算法）
  • 组合数计算

• 代码练习

  • 实现埃氏筛法求素数
  • 实现欧几里得算法求最大公约数
  • 计算组合数

#include <stdio.h>
#include <stdbool.h>const int MAXN = 1000000;bool is_prime[MAXN + 1];void sieve() {for (int i = 0; i <= MAXN; ++i) {is_prime[i] = true;}is_prime[0] = is_prime[1] = false;for (int i = 2; i * i <= MAXN; ++i) {if (is_prime[i]) {for (int j = i * i; j <= MAXN; j += i) {is_prime[j] = false;}}}
}int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);
}long long combination(int n, int k) {if (k > n - k) {k = n - k;}long long result = 1;for (int i = 0; i < k; ++i) {result *= (n - i);result /= (i + 1);}return result;
}int main() {sieve();for (int i = 0; i < 20; ++i) {if (is_prime[i]) {printf("%d ", i);}}printf("\n");int a = 48, b = 18;printf("GCD of %d and %d: %d\n", a, b, gcd(a, b));int n = 5, k = 3;printf("Combination C(%d, %d): %lld\n", n, k, combination(n, k));return 0;
}

Day 9: 字符串处理进阶

• 知识点

  • 字符串分割（strtok）
  • 字符串转换（atoi, itoa）
  • 字符串逆序

• 代码练习

  • 实现字符串分割
  • 实现字符串到整数的转换
  • 实现字符串逆序

#include <stdio.h>
#include <string.h>
#include <stdlib.h>void split_string(const char *str, const char *delim, char *result[]) {char *token = strtok((char *)str, delim);int index = 0;while (token != NULL) {result[index++] = token;token = strtok(NULL, delim);}
}int string_to_int(const char *str) {int result = 0;int sign = 1;int i = 0;if (str[0] == '-') {sign = -1;i = 1;}for (; str[i] != '\0'; ++i) {result = result * 10 + (str[i] - '0');}return result * sign;
}void reverse_string(char *str) {int len = strlen(str);for (int i = 0; i < len / 2; ++i) {char temp = str[i];str[i] = str[len - i - 1];str[len - i - 1] = temp;}
}int main() {const char *str = "Hello,World,This,Is,PAT";char *result[10];split_string(str, ",", result);for (int i = 0; result[i] != NULL; ++i) {printf("%s\n", result[i]);}const char *num_str = "-12345";int num = string_to_int(num_str);printf("String to Int: %d\n", num);char str_reverse[] = "PAT";reverse_string(str_reverse);printf("Reversed String: %s\n", str_reverse);return 0;
}

Day 10: 模拟题训练

• 知识点

  • 综合运用前面所学的知识点
  • 解决实际问题

• 代码练习

  • 从PAT Basic历年真题中挑选几个题目进行练习。

// 例题1：统计字母频率
#include <stdio.h>
#include <string.h>int main() {char str[1000];int freq[26] = {0};scanf("%s", str);for (int i = 0; str[i] != '\0'; ++i) {if (str[i] >= 'a' && str[i] <= 'z') {freq[str[i] - 'a']++;} else if (str[i] >= 'A' && str[i] <= 'Z') {freq[str[i] - 'A']++;}}for (int i = 0; i < 26; ++i) {if (freq[i] > 0) {printf("%c: %d\n", 'a' + i, freq[i]);}}return 0;
}// 例题2：矩阵转置
#include <stdio.h>int main() {int rows, cols;scanf("%d %d", &rows, &cols);int matrix[100][100];for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {scanf("%d", &matrix[i][j]);}}for (int i = 0; i < cols; ++i) {for (int j = 0; j < rows; ++j) {printf("%d ", matrix[j][i]);}printf("\n");}return 0;
}

Day 11: 模拟题训练

• 知识点

  • 继续综合运用前面所学的知识点
  • 解决实际问题

• 代码练习

  • 从PAT Basic历年真题中再挑选几个题目进行练习。

// 例题3：查找子串
#include <stdio.h>
#include <string.h>int main() {char str[1000], sub[100];scanf("%s %s", str, sub);char *pos = strstr(str, sub);if (pos != NULL) {printf("Found at position: %ld\n", pos - str);} else {printf("Not Found\n");}return 0;
}// 例题4：最大子数组和
#include <stdio.h>int max_subarray_sum(int arr[], int n) {int max_so_far = arr[0];int current_max = arr[0];for (int i = 1; i < n; ++i) {current_max = (current_max + arr[i] > arr[i]) ? current_max + arr[i] : arr[i];max_so_far = (max_so_far > current_max) ? max_so_far : current_max;}return max_so_far;
}int main() {int n;scanf("%d", &n);int arr[1000];for (int i = 0; i < n; ++i) {scanf("%d", &arr[i]);}printf("Max Subarray Sum: %d\n", max_subarray_sum(arr, n));return 0;
}

Day 12: 模拟题训练

• 知识点

  • 继续综合运用前面所学的知识点
  • 解决实际问题

• 代码练习

  • 从PAT Basic历年真题中再挑选几个题目进行练习。

// 例题5：字符串压缩
#include <stdio.h>
#include <string.h>void compress_string(const char *input, char *output) {int len = strlen(input);int count = 1;int j = 0;for (int i = 0; i < len; ++i) {if (i + 1 < len && input[i] == input[i + 1]) {count++;} else {output[j++] = input[i];if (count > 1) {sprintf(output + j, "%d", count);j += strlen(output + j);}count = 1;}}output[j] = '\0';
}int main() {char input[1000], output[1000];scanf("%s", input);compress_string(input, output);printf("Compressed: %s\n", output);return 0;
}// 例题6：最长公共子序列
#include <stdio.h>
#include <string.h>int lcs_length(const char *X, const char *Y, int m, int n) {int L[m + 1][n + 1];for (int i = 0; i <= m; ++i) {for (int j = 0; j <= n; ++j) {if (i == 0 || j == 0) {L[i][j] = 0;} else if (X[i - 1] == Y[j - 1]) {L[i][j] = L[i - 1][j - 1] + 1;} else {L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1];}}}return L[m][n];
}int main() {char X[100], Y[100];scanf("%s %s", X, Y);int m = strlen(X);int n = strlen(Y);printf("Length of LCS: %d\n", lcs_length(X, Y, m, n));return 0;
}

Day 13: 模拟题训练

• 知识点

  • 继续综合运用前面所学的知识点
  • 解决实际问题

• 代码练习

  • 从PAT Basic历年真题中再挑选几个题目进行练习。

// 例题7：二叉树的层次遍历
#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;TreeNode* create_node(int val) {TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;
}void level_order_traversal(TreeNode *root) {if (root == NULL) {return;}int front = 0, rear = 0;TreeNode *queue[1000];queue[rear++] = root;while (front < rear) {TreeNode *node = queue[front++];printf("%d ", node->val);if (node->left != NULL) {queue[rear++] = node->left;}if (node->right != NULL) {queue[rear++] = node->right;}}
}int main() {TreeNode *root = create_node(1);root->left = create_node(2);root->right = create_node(3);root->left->left = create_node(4);root->left->right = create_node(5);root->right->left = create_node(6);root->right->right = create_node(7);level_order_traversal(root);return 0;
}// 例题8：快速排序
#include <stdio.h>
#include <stdlib.h>void quick_sort(int arr[], int low, int high) {if (low < high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; ++j) {if (arr[j] < pivot) {++i;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}++i;int temp = arr[i];arr[i] = arr[high];arr[high] = temp;quick_sort(arr, low, i - 1);quick_sort(arr, i + 1, high);}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quick_sort(arr, 0, n - 1);printf("Sorted array: ");for (int i = 0; i < n; ++i) {printf("%d ", arr[i]);}printf("\n");return 0;
}

Day 14: 总结与模拟考试

• 知识点

  • 复习前两周所学的知识点
  • 解决实际问题

• 代码练习

  • 从PAT Basic历年真题中再挑选几个题目进行练习。
  • 模拟一次完整的PAT Basic考试，严格按照考试时间进行。

// 例题9：合并两个有序数组
#include <stdio.h>void merge(int arr1[], int n1, int arr2[], int n2, int merged[]) {int i = 0, j = 0, k = 0;while (i < n1 && j < n2) {if (arr1[i] < arr2[j]) {merged[k++] = arr1[i++];} else {merged[k++] = arr2[j++];}}while (i < n1) {merged[k++] = arr1[i++];}while (j < n2) {merged[k++] = arr2[j++];}
}int main() {int arr1[] = {1, 3, 5, 7};int n1 = sizeof(arr1) / sizeof(arr1[0]);int arr2[] = {2, 4, 6, 8};int n2 = sizeof(arr2) / sizeof(arr2[0]);int merged[100];merge(arr1, n1, arr2, n2, merged);printf("Merged array: ");for (int i = 0; i < n1 + n2; ++i) {printf("%d ", merged[i]);}printf("\n");return 0;
}// 例题10：矩阵旋转
#include <stdio.h>void rotate_matrix(int matrix[100][100], int n) {for (int layer = 0; layer < n / 2; ++layer) {int first = layer;int last = n - 1 - layer;for (int i = first; i < last; ++i) {int offset = i - first;int top = matrix[first][i];matrix[first][i] = matrix[last - offset][first];matrix[last - offset][first] = matrix[last][last - offset];matrix[last][last - offset] = matrix[i][last];matrix[i][last] = top;}}
}int main() {int n;scanf("%d", &n);int matrix[100][100];for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {scanf("%d", &matrix[i][j]);}}rotate_matrix(matrix, n);for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {printf("%d ", matrix[i][j]);}printf("\n");}return 0;
}