C 语言常用算法与数据结构基础
C 语言常用算法与数据结构基础涵盖数组、链表、栈、队列、树和图等结构,以及排序、搜索、递归等算法。内容包含时间空间复杂度分析,通过代码示例演示数组遍历、查找、链表创建、冒泡排序、栈实现及递归计算。同时提供内存泄漏、数组越界等常见错误避坑指南,旨在帮助开发者掌握程序设计基础并提升代码效率。

C 语言常用算法与数据结构基础涵盖数组、链表、栈、队列、树和图等结构,以及排序、搜索、递归等算法。内容包含时间空间复杂度分析,通过代码示例演示数组遍历、查找、链表创建、冒泡排序、栈实现及递归计算。同时提供内存泄漏、数组越界等常见错误避坑指南,旨在帮助开发者掌握程序设计基础并提升代码效率。

💡 算法与数据结构是程序设计的基础!选择合适的算法与数据结构可以提高程序的效率和可维护性。
时间复杂度是衡量算法效率的重要指标,表示算法运行时间与输入规模的关系。
常用时间复杂度:
| 时间复杂度 | 描述 |
|---|---|
| O(1) | 常数时间复杂度,不随输入规模变化 |
| O(logn) | 对数时间复杂度,输入规模每次减半 |
| O(n) | 线性时间复杂度,与输入规模成正比 |
| O(nlogn) | 线性对数时间复杂度,如快速排序、归并排序 |
| O(n^2) | 平方时间复杂度,如冒泡排序、插入排序 |
| O(n^k) | 多项式时间复杂度,k 为常数 |
| O(2^n) | 指数时间复杂度,如递归求解斐波那契数列 |
| O(n!) | 阶乘时间复杂度,如全排列算法 |
空间复杂度是衡量算法所需内存空间与输入规模的关系。
代码示例 1:计算时间复杂度
#include <stdio.h>
// 时间复杂度 O(1)
void func1() {
int a = 10;
int b = 20;
int c = a + b;
printf("c 的值:%d\n", c);
}
// 时间复杂度 O(n)
void func2(int n) {
for (int i = 0; i < n; i++) {
printf("%d ", i);
}
printf("\n");
}
// 时间复杂度 O(n^2)
void func3(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", i * j);
}
printf("\n");
}
}
int main() {
int n = 5;
func1();
func2(n);
func3(n);
return 0;
}
代码示例 2:数组遍历
#include <stdio.h>
void traverse_array(int arr[], int length) {
for (int i = 0; i < length; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int length = sizeof(arr) / sizeof(arr[0]);
traverse_array(arr, length);
return 0;
}
功能:从数组的第一个元素开始,逐个比较,直到找到目标元素
代码示例 3:线性查找
#include <stdio.h>
int linear_search(int arr[], int length, int target) {
for (int i = 0; i < length; i++) {
if (arr[i] == target) {
return i; // 找到目标元素的下标
}
}
return -1; // 未找到目标元素
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int length = sizeof(arr) / sizeof(arr[0]);
int target = 30;
int index = linear_search(arr, length, target);
if (index == -1) {
printf("未找到目标元素!\n");
} else {
printf("目标元素在数组中的下标:%d\n", index);
}
return 0;
}
功能:每次将新节点插入到链表的头部
代码示例 4:使用头插法创建链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* create_list(int data[], int length) {
Node* head = NULL;
Node* new_node;
for (int i = 0; i < length; i++) {
new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
printf("内存分配失败!\n");
return NULL;
}
new_node->data = data[i];
new_node->next = head;
head = new_node;
}
return head;
}
void traverse_list(Node* head) {
Node* ptr = head;
while (ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}
int main() {
int data[] = {10, 20, 30, 40, 50};
int length = sizeof(data) / sizeof(data[0]);
Node* head = create_list(data, length);
if (head == NULL) {
return 1;
}
traverse_list(head);
// 释放链表
Node* ptr = head;
Node* temp;
while (ptr != NULL) {
temp = ptr;
ptr = ptr->next;
free(temp);
}
return 0;
}
功能:交换相邻元素,将最大元素移动到末尾
代码示例 5:冒泡排序
#include <stdio.h>
void bubble_sort(int arr[], int length) {
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int length = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, length);
for (int i = 0; i < length; i++) {
printf("%d ", arr[i]);
}
return 0;
}
代码示例 6:使用数组实现栈
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100
typedef struct Stack {
int data[STACK_SIZE];
int top;
} Stack;
void stack_init(Stack* stack) {
stack->top = -1;
}
int stack_is_empty(Stack* stack) {
return stack->top == -1;
}
int stack_is_full(Stack* stack) {
return stack->top == STACK_SIZE - 1;
}
int stack_push(Stack* stack, int value) {
if (stack_is_full(stack)) {
printf("栈已满!\n");
return 0;
}
stack->top++;
stack->data[stack->top] = value;
return 1;
}
int stack_pop(Stack* stack) {
if (stack_is_empty(stack)) {
printf("栈已空!\n");
return 0;
}
int value = stack->data[stack->top];
stack->top--;
return value;
}
int stack_peek(Stack* stack) {
if (stack_is_empty(stack)) {
printf("栈已空!\n");
return 0;
}
return stack->data[stack->top];
}
int main() {
Stack stack;
stack_init(&stack);
stack_push(&stack, 10);
stack_push(&stack, 20);
stack_push(&stack, 30);
printf("栈顶元素:%d\n", stack_peek(&stack));
printf("出栈元素:%d\n", stack_pop(&stack));
printf("出栈元素:%d\n", stack_pop(&stack));
printf("出栈元素:%d\n", stack_pop(&stack));
return 0;
}
代码示例 7:使用递归计算阶乘
#include <stdio.h>
int factorial(int n) {
if (n == 0 || n == 1) {
return 1; // 终止条件
}
return n * factorial(n - 1); // 递归调用
}
int main() {
int n = 5;
int result = factorial(n);
printf("%d 的阶乘:%d\n", n, result);
return 0;
}
代码示例 8:避免数组越界的例子
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50};
int length = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < length; i++) {
if (i < 0 || i >= length) {
printf("数组下标越界!\n");
continue;
}
printf("%d ", arr[i]);
}
return 0;
}
✅ 常用数据结构的基本概念:数组、链表、栈、队列、树、图
✅ 数组与字符串算法:数组遍历、数组查找、数组排序、字符串操作
✅ 链表算法:链表的创建、遍历、查找、插入、删除
✅ 排序与搜索算法:冒泡排序、插入排序、选择排序、快速排序、二分查找
✅ 栈与队列算法:栈的基本操作、队列的基本操作
✅ 递归与分治算法:递归的基本步骤、分治的基本步骤
✅ 常用算法的避坑指南:避免常见的错误和陷阱

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online