引言
在计算机科学领域，数据结构和算法是基础中的基础。无论是在学校的考试还是职场的技术面试中，掌握数据结构算法都是必不可少的。本文将揭秘数据结构必考的10大算法，并提供实战技巧，帮助读者在考试中游刃有余。
1. 排序算法
1.1 冒泡排序
原理
：通过比较相邻元素，将较大的元素向后移动。
代码示例
：
void bubbleSort(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;
}
}
}
}
1.2 快速排序
原理
：选择一个基准值，将数组分为两部分，一部分比基准值小，另一部分比基准值大。
代码示例
：
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low – 1);
for (int j = low; j <= high- 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
2. 查找算法
2.1 线性查找
原理
：逐个比较数组中的元素，直到找到目标值。
代码示例
：
int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
2.2 二分查找
原理
：在有序数组中，通过比较中间元素与目标值，缩小查找范围。
代码示例
：
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
3. 栈和队列
3.1 栈
原理
：遵循后进先出（LIFO）原则的数据结构。
代码示例
：
typedef struct Stack {
int top;
unsigned capacity;
int* array;
} Stack;
void push(Stack* stack, int item) {
if (stack->top == stack->capacity – 1) {
return;
}
stack->array[++stack->top] = item;
}
int pop(Stack* stack) {
if (stack->top == -1) {
return -1;
}
return stack->array[stack->top–];
}
3.2 队列
原理
：遵循先进先出（FIFO）原则的数据结构。
代码示例
：
typedef struct Queue {
int front;
int rear;
unsigned capacity;
int* array;
} Queue;
void enqueue(Queue* queue, int item) {
if (queue->rear == queue->capacity – 1) {
return;
}
queue->array[++queue->rear] = item;
}
int dequeue(Queue* queue) {
if (queue->front == queue->rear) {
return -1;
}
return queue->array[queue->front++];
}
4. 链表
4.1 单链表
原理
：由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
代码示例
：
struct Node {
int data;
struct Node* next;
};
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
4.2 双向链表
原理
：与单链表类似，但每个节点包含指向前一个节点的指针。
代码示例
：
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
new_node->prev = last;
}
5. 树
5.1 二叉树
原理
：每个节点最多有两个子节点，分别为左子节点和右子节点。
代码示例
：
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
5.2 二叉搜索树
原理
：左子节点的值小于根节点的值，右子节点的值大于根节点的值。
代码示例
：
struct Node* insert(struct Node* node, int data) {
if (node == NULL) {
return newNode(data);
}
if (data < node->data) {
node->left = insert(node->left, data);
} else if (data > node->data) {
node->right = insert(node->right, data);
}
return node;
}
6. 图
6.1 邻接矩阵
原理
：使用二维数组表示图，其中元素表示顶点之间的连接关系。
代码示例
：
#define MAX_VERTICES 5
int graph[MAX_VERTICES][MAX_VERTICES];
void addEdge(int start, int end) {
graph[start][end] = 1;
graph[end][start] = 1;
}
6.2 邻接表
原理
：使用链表表示图，每个节点包含顶点和指向相邻顶点的指针。
代码示例
：
struct Node {
int vertex;
struct Node* next;
};
struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
};
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = dest;
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
7. 动态规划
7.1 最长公共子序列
原理
：找出两个序列中最长的公共子序列。
代码示例
：
int lcs(char* X, 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] = max(L[i-1][j], L[i][j-1]);
}
}
return L[m][n];
}
8. 贪心算法
8.1 背包问题
原理
：在不超过背包重量限制的情况下，尽可能多地装入物品。
代码示例
：
int knapsack(int W, int wt[], int val[], int n) {
int Wt[n+1], Val[n+1], dp[n+1][W+1];
for (int i = 0; i <= n; i++)
Wt[i] = wt[i-1], Val[i] = val[i-1];
for (int i = 0; i <= n; i++)
dp[i][0] = 0;
for (int w = 0; w <= W; w++)
dp[0][w] = 0;
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (Wt[i-1] <= w)
dp[i][w] = max(dp[i-1][w], Val[i-1] + dp[i-1][w-Wt[i-1]]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
9. 分治算法
9.1 快速排序
原理
：选择一个基准值，将数组分为两部分，一部分比基准值小，另一部分比基准值大。
代码示例
：
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high- 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
10. 总结
通过学习以上10大算法，读者可以更好地掌握数据结构算法，为考试和职场中的挑战做好准备。在实际应用中，灵活运用这些算法，可以解决各种复杂问题。祝大家考试顺利！