当前位置：首页 > news >正文

数据结构小白必看：手把手教你用C语言实现PTA题库中的经典算法

news 2026/4/14 23:11:27

数据结构小白必看：手把手教你用C语言实现PTA题库中的经典算法

第一次接触数据结构时，看着课本上那些抽象的概念和复杂的图示，我完全摸不着头脑。直到在PTA题库里反复练习那些经典算法，才真正理解了数据结构的精髓。这篇文章将带你用最接地气的方式，从零开始实现那些让无数初学者头疼的数据结构算法。

1. 顺序表：数据结构的入门基石

顺序表就像一排连续的储物柜，每个格子都有固定编号。在C语言中，我们用数组来实现这种线性结构。先来看一个最简单的例子——顺序查找：

int sequentialSearch(int arr[], int size, int target) { for (int i = 0; i < size; i++) { if (arr[i] == target) { return i; // 找到返回索引 } } return -1; // 未找到 }

顺序表的插入操作需要特别注意元素的后移：

#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int length; } SeqList; int insert(SeqList *L, int index, int value) { if (L->length == MAX_SIZE || index < 0 || index > L->length) { return 0; // 插入失败 } for (int i = L->length; i > index; i--) { L->data[i] = L->data[i-1]; // 元素后移 } L->data[index] = value; L->length++; return 1; // 插入成功 }

顺序表操作要点：

插入/删除时间复杂度为O(n)
随机访问时间复杂度为O(1)
适合元素数量固定、查询频繁的场景

2. 链表：灵活的动态数据结构

当我们需要频繁插入删除时，链表就派上用场了。单链表的基本结构如下：

typedef struct Node { int data; struct Node *next; } ListNode;

头插法创建链表是PTA常考题型：

ListNode* createListHead(int arr[], int n) { ListNode *head = (ListNode*)malloc(sizeof(ListNode)); head->next = NULL; for (int i = 0; i < n; i++) { ListNode *node = (ListNode*)malloc(sizeof(ListNode)); node->data = arr[i]; node->next = head->next; head->next = node; } return head; }

链表删除操作要特别注意指针的修改顺序：

int deleteNode(ListNode *head, int index) { ListNode *p = head; int i = 0; while (p->next && i < index) { p = p->next; i++; } if (!p->next) return 0; // 删除失败 ListNode *temp = p->next; p->next = temp->next; free(temp); return 1; // 删除成功 }

提示：链表操作最容易出现内存泄漏，记得每次删除节点后都要free

3. 栈与队列：受限的线性表

栈是后进先出(LIFO)的结构，十进制转二进制是栈的经典应用：

#define STACK_SIZE 100 int stack[STACK_SIZE]; int top = -1; void push(int x) { if (top == STACK_SIZE - 1) return; stack[++top] = x; } int pop() { if (top == -1) return -1; return stack[top--]; } void decimalToBinary(int num) { while (num > 0) { push(num % 2); num /= 2; } while (top != -1) { printf("%d", pop()); } }

循环队列解决假溢出问题：

#define QUEUE_SIZE 5 typedef struct { int data[QUEUE_SIZE]; int front, rear; } CircularQueue; void initQueue(CircularQueue *q) { q->front = q->rear = 0; } int enQueue(CircularQueue *q, int x) { if ((q->rear + 1) % QUEUE_SIZE == q->front) return 0; // 队满 q->data[q->rear] = x; q->rear = (q->rear + 1) % QUEUE_SIZE; return 1; }

4. 二叉树：递归的艺术

二叉树遍历是理解递归的最佳案例。先序遍历的递归实现：

typedef struct TreeNode { char data; struct TreeNode *left, *right; } TreeNode; void preOrder(TreeNode *root) { if (root) { printf("%c ", root->data); preOrder(root->left); preOrder(root->right); } }

计算二叉树高度展示递归的威力：

int treeHeight(TreeNode *root) { if (!root) return 0; int left = treeHeight(root->left); int right = treeHeight(root->right); return (left > right ? left : right) + 1; }

二叉树操作要点：

递归终止条件必须明确
先处理当前节点，再递归处理子树
时间复杂度通常为O(n)

5. 查找算法：从暴力到优雅

顺序查找简单直接，但效率低下：

int seqSearch(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) return i; } return -1; }

二分查找要求数组有序，但效率极高：

int binarySearch(int arr[], int n, int key) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) left = mid + 1; else right = mid - 1; } return -1; }