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

26-数据结构-线性表2

news 2025/6/14 6:40:36

🔧 常用顺序表算法与操作实现（含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 部分
}