顺序表基本算法
写在前面
代码语法说明：在C语言语法的基础上使用了C++的 “引用”(&) 特性，后缀名为 .cpp
数据结构
定义顺序表的数据结构为：
#define MAX_SIZE 50
// 顺序表数据结构
typedef struct {
int data[MAX_SIZE];
int length;
} SqList;
几个算法
- 将整数序列 R 循环左移 P(0<p<n) 个位置：
- 方法一：
123456789==>23456789 1==>3456789 12==> … ==>789 123456 - 方法二：
123456789==>987 654321==>789 123456
/*
循环左移1:
1. temp = x_0
2. x_1 ... x_n-1 左移一位
3. x_n-1 = temp
4. 步骤1至3循环p次
*/
void leftShift1(SqList &L, int p) {
for (int i=0; i<p; i++) {
int temp = L.data[0];
for (int j=0; j<L.length-1; j++) {
L.data[j] = L.data[j+1];
}
L.data[L.length-1] = temp;
}
}
/*
循环左移2:
1. 如 123456789 整体转置为 987654321
2. 再 987 654321 分别局部转置为 789 123456
3. 以上即相当于整体左移6位
*/
void leftShift2(SqList &L, int p) {
reverse(L, 0, L.length-1); // reverse 为转置的功能函数，函数定义见下方测试部分
reverse(L, 0, L.length-1-p);
reverse(L, L.length-p, L.length-1);
}
- 删除所有值为 x 的元素
/*
删除值为x元素1：
1. 用k记录值不为x的元素个数
2. 比较当前元素data[i]，若值不为x，则放至第k个位置
3. 值为x的元素被一一覆盖
*/
void delAll1(SqList &L, int x) {
int k=0;
for (int i=0; i<L.length; i++) {
if (L.data[i] != x) {
L.data[k] = L.data[i];
k++;
}
}
L.length = k; // 不能忘
}
/*
删除值为x的元素2：
1. 用k记录值为x的元素个数
2. 比较当前元素data[i]，若值不为x，则放到第i-k个位置
3. 值为x的元素被一一覆盖
*/
void delAll2(SqList &L, int x) {
int k=0;
for (int i=0; i<L.length; i++) {
if (L.data[i] != x) {
L.data[i-k] = L.data[i];
} else {
k++;
}
}
L.length = L.length-k;
}
/*
删除值为x的元素3：
1. 开辟等长的数组空间
2. 比较当前元素data[i]，若值不为x，则放到新数组中
3. 新数组即为所有值不为x的元素
*/
void delAll3(SqList &L, int x) {
int temp[L.length];
int k=0;
for (int i=0; i<L.length; i++) {
if (L.data[i] != x) {
temp[k] = L.data[i];
k++;
}
}
// 临时数组复制到L中
for (int i=0; i<k; i++) {
L.data[i] = temp[i];
}
L.length = k;
}
- 以
flag为分界线，重新排列数组，使左侧均小于flag，右侧均大于flag
/*
以flag分割数组1：
1. 左右两侧分别向中间遍历
2. 找到左边值大于flag的索引i，找到右边小于flag的位置j
3. i 和 j 两个位置的值交换
*/
void move1(SqList &L, int flag) {
int i=0, j=L.length-1;
while (i < j) {
while (i < j && L.data[i] < flag) i++;
while (i < j && L.data[j] >= flag) j--;
int temp = L.data[i];
L.data[i] = L.data[j];
L.data[j] = temp;
}
}
/*
以flag分割数组2：（联想到快排的思想）
1. 左右两侧分别向中间遍历，temp = data[0]，i = 0
2. 找到右边值小于flag的索引j，data[i] = data[j]
3. 找到左边值大于flag的索引i，data[j] = data[i]
4. i，j 相遇时，data[i] = temp，或 data[j] = temp
*/
void move2(SqList &L, int flag) {
int temp=L.data[0], i=0, j=L.length-1;
while (i < j) {
while (i < j && L.data[j] >= flag) j--;
L.data[i] = L.data[j];
while (i < j && L.data[i] < flag) i++;
L.data[j] = L.data[i];
}
L.data[i] = temp;
}
- 从无序顺序表删除重复元素，不改变相对顺序
/*
1. data[i] 指当前元素
2. j 指不重复序列的边界，即前 j 个元素互不重复
3. data[i] 和前 j 个元素比较，若 data[i] 在前 j 个元素中不重复，
则放至第 j+1 个位置，然后边界后移即j++
*/
void delSame1(SqList &L) {
int j=0;
for (int i=0; i<L.length; i++) {
int k;
for (k=0; k<=j; k++) {
if (L.data[k] == L.data[i]) break;
}
if (k > j) { // data[i] 不与前 j 个元素重复
L.data[++j] = L.data[i];
}
}
L.length = j+1;
}
- 从有序顺序表删除重复元素，不改变相对顺序
/*
类似删除所有值为x的做法，直接覆盖
1. data[i] 指当前元素
2. k 为不重复元素边界。因为数组有序，所以重复元素均相邻。
3. data[i] 和 data[k] 比较，若不相同，则说明不重复，data[i] 放至第 k+1 个位置
*/
void delSame2(SqList &L) {
int k=0;
for (int i=1; i<L.length; i++) {
if (L.data[i] != L.data[k]) L.data[++k] = L.data[i];
}
L.length = k+1;
}
测试代码
#include <stdio.h>
#define MAX_SIZE 50
// 顺序表数据结构
typedef struct {
int data[MAX_SIZE];
int length;
} SqList;
// 功能函数：打印顺序表
void print(SqList L, const char* tips) {
printf("%s", tips);
for (int i=0; i<L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\tlength:%d\n", L.length);
}
// 功能函数：顺序表排序（快排）
void quickSort(SqList &L, int left, int right) {
if (left >= right) return; // 递归结束条件
int temp = L.data[left];
int i=left, j=right;
while (i<j) {
while (i<j && L.data[j]>=temp) j--;
if (i<j) L.data[i++] = L.data[j];
while (i<j && L.data[i]<temp) i++;
if (i<j) L.data[j--] = L.data[i];
}
L.data[i] = temp; // 以temp为分割线分成两部分
quickSort(L, left, i-1);
quickSort(L, i+1, right);
}
void sort(SqList &L) {
quickSort(L, 0, L.length-1);
}
// 功能函数：元素转置
void reverse(SqList &L, int left, int right) {
while (left<right) {
int temp = L.data[left];
L.data[left] = L.data[right];
L.data[right] = temp;
left++;
right--;
}
}
/*
...(上述顺序表基本算法)
*/
// 主函数用于测试
int main(void) {
SqList list;
list.data;
list.length = 10;
// 初始化顺序表
int data[10] = {3,3,6,4,2,1,2,3,6,8};
for (int i=1; i<10; i++) {
list.data[i] = data[i];
}
print(list, "原数组:\t");
/* 测试转置 */
// reverse(list, 0, list.length-1);
/* 测试元素左移p位 */
// leftShift1(list, 4);
// leftShift2(list, 4);
/* 测试删除所有值为x元素 */
// delAll1(list, 3);
// delAll2(list, 3);
// delAll3(list, 3);
/* 测试以flag分割数组 */
// move1(list, 4);
// move2(list, 4);
/* 测试删除重复元素，不改变相对顺序 */
// delSame1(list); // 针对无序数组
// sort(list);
// print(list, "排序后:\t");
// delSame2(list); // 针对有序数组
print(list, "操作后:\t");
return 0;
}
参考资料
《新编数据结构习题与解析》（李春葆等编著）