数据结构与算法常考代码（C语言）
·
目录
排序
冒泡排序
左边的跟右边的比较
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]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}快速排序
用基准元素分区
void quickSort(int arr[], int low, int high) {
if (low < high) {
// 分区操作
int pivot = partition(arr, low, high);
// 递归排序两部分
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
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++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high]
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i + 1;
}插入排序
每次从左往右的方向加一个数字，然后算作一组，组内排好序
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将比key大的元素后移
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
// 插入key
arr[j+1] = key;
}
}选择排序
依次找最小的
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
// 找到最小元素的位置
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 交换最小元素和当前元素
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
}归并排序
划分很多组，再一组内排好序，然后再组跟组的数字排序
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// 计算中间点
int m = l + (r - l) / 2;
// 递归排序左右两部分
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// 合并已排序的两部分
merge(arr, l, m, r);
}
}
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组
int L[n1], R[n2];
// 复制数据到临时数组
for (i = 0; i < n1; i++) L[i] = arr[l + i];
for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
// 合并临时数组回原数组
i = 0; j = 0; k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}希尔排序
插入排序的改进，用增量划分组
void shellSort(int arr[], int n) {
// 初始增量为n/2，逐渐减半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个增量进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
// 对相隔gap的元素进行比较和移动
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
// 插入temp
arr[j] = temp;
}
}
}堆排序
二叉树
void heapSort(int arr[], int n) {
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个从堆中取出元素
for (int i = n - 1; i > 0; i--) {
// 交换堆顶(最大值)和当前元素
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新调整堆
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化根
int l = 2 * i + 1; // 左子节点
int r = 2 * i + 2; // 右子节点
// 如果左子节点比根大
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
// 如果右子节点比根大
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
// 如果最大的不是根
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}查找
在一棵树中找到一个字符，输出查找时经过的结点序列
链表
合并两个有序单链表
Node* mergeLists(Node* l1, Node* l2) {
// 创建虚拟头节点，避免处理空链表的边界情况
Node dummy = {0, NULL};
// 尾指针始终指向新链表的最后一个节点
Node* tail = &dummy;
// 同时遍历两个链表，直到其中一个遍历完
while (l1 && l2) {
// 比较当前节点值，选择较小的节点接入新链表
if (l1->data < l2->data) {
tail->next = l1; // 将l1接入新链表
l1 = l1->next; // l1指针后移
} else {
tail->next = l2; // 将l2接入新链表
l2 = l2->next; // l2指针后移
}
tail = tail->next; // 尾指针后移
}
// 处理剩余节点：直接将非空链表的剩余部分接入新链表尾部
tail->next = l1 ? l1 : l2;
// 返回虚拟头节点的下一个节点，即合并后链表的头节点
return dummy.next;
}数组
合并两个有序数组
void mergeArrays(int* arr1, int m, int* arr2, int n) {
// i指向arr1的有效元素末尾（从m-1开始）
int i = m - 1;
// j指向arr2的末尾（从n-1开始）
int j = n - 1;
// k指向合并后数组的末尾（总长度m+n-1）
int k = m + n - 1;
// 从后向前遍历两个数组，将较大元素放入合并位置
while (i >= 0 && j >= 0) {
if (arr1[i] > arr2[j]) {
// arr1的当前元素更大，放入k位置
arr1[k] = arr1[i];
i--; // 移动arr1的指针
} else {
// arr2的当前元素更大或相等，放入k位置
arr1[k] = arr2[j];
j--; // 移动arr2的指针
}
k--; // 合并位置指针前移
}
// 处理arr2中可能剩余的元素（arr1剩余元素无需处理，已在正确位置）
while (j >= 0) {
arr1[k] = arr2[j]; // 将arr2剩余元素复制到arr1前面
j--;
k--;
}
}有序数组倒置
void reverseArray(int* arr, int n) {
int left = 0; // 左指针初始化为数组起始位置
int right = n - 1; // 右指针初始化为数组末尾位置
while (left < right) { // 当左指针小于右指针时循环
// 交换左右指针所指元素
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++; // 左指针右移
right--; // 右指针左移
}
}树
判断二叉树是否为二叉搜索树
bool isBST(Node* root, Node* min, Node* max) {
if (root == NULL) return true; // 空树是BST
// 检查当前节点是否在(min, max)范围内
if ((min != NULL && root->data <= min->data) ||
(max != NULL && root->data >= max->data)) {
return false;
}
// 递归检查左右子树：左子树<root<右子树
return isBST(root->left, min, root) &&
isBST(root->right, root, max);
}
// 调用示例
bool checkBST(Node* root) {
return isBST(root, NULL, NULL);
}栈
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE]; // 存储栈元素的数组
int top; // 栈顶指针
} Stack;
// 初始化栈
void initStack(Stack* s) {
s->top = -1; // 空栈的栈顶指针为-1
}
// 判断栈是否为空
bool isEmpty(Stack* s) {
return s->top == -1;
}
// 判断栈是否已满
bool isFull(Stack* s) {
return s->top == MAX_SIZE - 1;
}
// 入栈操作
bool push(Stack* s, int value) {
if (isFull(s)) return false; // 栈满则操作失败
s->data[++(s->top)] = value; // 先移动栈顶指针，再存入值
return true;
}
// 出栈操作
bool pop(Stack* s, int* value) {
if (isEmpty(s)) return false; // 栈空则操作失败
*value = s->data[(s->top)--]; // 先取出值，再移动栈顶指针
return true;
}
// 获取栈顶元素
bool peek(Stack* s, int* value) {
if (isEmpty(s)) return false; // 栈空则操作失败
*value = s->data[s->top]; // 仅获取值，不移动指针
return true;
}括号匹配
bool isValid(char* s) {
// 创建一个足够大的栈（数组模拟）
char stack[10000];
int top = -1; // 栈顶指针初始化为-1表示空栈
// 遍历输入字符串
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
// 左括号入栈
if (c == '(' || c == '[' || c == '{') {
stack[++top] = c; // 先移动栈顶指针，再存入元素
}
// 右括号尝试匹配
else if (c == ')' || c == ']' || c == '}') {
// 栈为空，无法匹配
if (top == -1) {
return false;
}
// 获取栈顶元素并出栈
char topChar = stack[top--];
// 检查是否匹配
if ((c == ')' && topChar != '(') ||
(c == ']' && topChar != '[') ||
(c == '}' && topChar != '{')) {
return false; // 不匹配则返回失败
}
}
// 忽略非括号字符
else {
continue;
}
}
// 栈为空表示所有括号都匹配成功
return top == -1;
}用两个栈实现队列
typedef struct {
Stack s1, s2; // s1用于入队，s2用于出队
} MyQueue;
// 初始化队列
MyQueue* myQueueCreate() {
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
init(&q->s1);
init(&q->s2);
return q;
}
// 入队操作
void myQueuePush(MyQueue* q, int x) {
push(&q->s1, x);
}
// 出队操作
int myQueuePop(MyQueue* q) {
if (isEmpty(&q->s2)) {
while (!isEmpty(&q->s1)) {
int val;
pop(&q->s1, &val);
push(&q->s2, val);
}
}
int val;
pop(&q->s2, &val);
return val;
}更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)