南浔区住房城乡建设局网站,网页设计基础学什么,搭积木建网站软件,wordpress添加产品图#x1f527; 常用顺序表算法与操作实现#xff08;含O(n)划分、逆置、回文、双向冒泡、二分查找、数组左移等#xff09;
本文整理了顺序表常见操作的 C/C 实现#xff0c;包括划分操作、逆置与回文判断、递归二分查找、双向冒泡排序及数组循环左移#xff0c;适合初学者… 常用顺序表算法与操作实现含O(n)划分、逆置、回文、双向冒泡、二分查找、数组左移等
本文整理了顺序表常见操作的 C/C 实现包括划分操作、逆置与回文判断、递归二分查找、双向冒泡排序及数组循环左移适合初学者学习掌握线性表基础操作。
1️⃣ 顺序表结构定义
#include stdio.h
#include stdbool.h
#define MAX_SIZE 100
struct SeqList {int data[MAX_SIZE];int length;
};2️⃣ O(n) 划分算法小于 key 的在左大于 key 的在右
void spliceArray(struct SeqList *L, int key) {int left 0;int right L-length - 1;while (left right) {while (left right L-data[left] key)left;while (left right L-data[right] key)right--;if (left right) {int tmp L-data[left];L-data[left] L-data[right];L-data[right] tmp;left;right--;}}
}3️⃣ 数组逆置操作
void reverseArray(int ar[], int n) {int i 0, j n - 1;while (i j) {int tmp ar[i];ar[i] ar[j];ar[j] tmp;i;j--;}
} 4️⃣ 回文判断正着读和反着读一致
bool isPalindrome(struct SeqList *L) {int i 0, j L-length - 1;while (i j) {if (L-data[i] ! L-data[j])return false;i;j--;}return true;
}5️⃣ 递归二分查找需在有序表中
int binarySearch(struct SeqList *L, int left, int right, int target) {if (left right)return -1;int mid (left right) / 2;if (L-data[mid] target)return mid;else if (target L-data[mid])return binarySearch(L, left, mid - 1, target);elsereturn binarySearch(L, mid 1, right, target);
} 6️⃣ 双向冒泡排序鸡尾酒排序
void doubleBubbleSort(struct SeqList *L) {int left 0;int right L-length - 1;bool is_swap;do {is_swap false;// 从左向右冒泡最大值for (int i left; i right; i) {if (L-data[i] L-data[i 1]) {int tmp L-data[i];L-data[i] L-data[i 1];L-data[i 1] tmp;is_swap true;}}if (!is_swap) break;right--;is_swap false;// 从右向左冒泡最小值for (int j right; j left; j--) {if (L-data[j] L-data[j - 1]) {int tmp L-data[j];L-data[j] L-data[j - 1];L-data[j - 1] tmp;is_swap true;}}left;} while (is_swap);
}7️⃣ 数组循环左移 p 位高效方法
void reverseSection(int ar[], int left, int right) {while (left right) {int tmp ar[left];ar[left] ar[right];ar[right] tmp;left;right--;}
}void rotateLeft(int ar[], int n, int p) {if (n 1 || p 0 || p n)return;p p % n;reverseSection(ar, 0, n - 1); // 整体反转reverseSection(ar, 0, n - p - 1); // 反转前 n-p 部分reverseSection(ar, n - p, n - 1); // 反转后 p 部分
} 总结
本文涵盖的内容包括 顺序表划分快排思想 数组逆置与回文判断 递归二分查找 双向冒泡排序 高效数组循环左移。
这些算法是常见的基本题型也是数据结构与算法入门的基础内容建议每个模块都亲手敲一遍。
