作者：admin

顺序表基本算法

顺序表基本算法

写在前面

代码语法说明：在C语言语法的基础上使用了C++的 “引用”(&) 特性，后缀名为 .cpp

数据结构

定义顺序表的数据结构为：

#define MAX_SIZE 50

// 顺序表数据结构
typedef struct {
    int data[MAX_SIZE];
    int length;
} SqList;

几个算法

  1. 将整数序列 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);
}

  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;
}

  1. 以 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. 从无序顺序表删除重复元素，不改变相对顺序

/*
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;
}

  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;
}

参考资料

《新编数据结构习题与解析》（李春葆等编著）