数据结构_顺序表

一、数据结构顺序表的实现

// Created by XuYiMing on 2020/2/2.
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

////////////////////顺序表///////////////////////////
#define InitSize 1000        //表长初始定义
typedef int ElemType;       //在此例中数据类型使用int

typedef struct {            //顺序表的定义
    ElemType *data;         //指示动态分配数组的指针
    int length;             //表当前长度
    int MaxSize;            //表当前分配的最大长度
} SeqList;                  //动态分配数组顺序表的类型定义

int InitList(SeqList &L) {   //初始化线性表，这里如果采用SeqList *L，则调用时则为 L->data
    L.data = (ElemType *) malloc(InitSize * sizeof(ElemType));  //这里数组是从0开始的，如果从1开始，则要为(InitSize+1)
    if (L.data == nullptr) {    //nullptr表示空指针，在C++中可以避免二义性问题
        printf("内存分配错误！\n");
        return 0;
    }
    L.length = 0;
    L.MaxSize = InitSize;
    printf("内存分配成功！\n");
    return 1;
}

int ListInsert(SeqList &L, int i, ElemType e) {     //线性表的插入，在指定位置插入某值(1<=i<=L.length)
    if (i < 1 || i > L.length + 1) {      //这里的i表示的是逻辑上的位置，而实际存储的是物理上的位置
        printf("插入位置不合理！\n"); //判断插入的地址是否为负数或有间隔
        return 0;
    }
    if (i >= L.MaxSize) {
        printf("存储空间已满！\n");
        return 0;
    }
    for (int j = L.length; j >= i; j--) {       //平均插入时间为O(n)
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return 1;
}

int ListDelete(SeqList &L, int i, ElemType &e) {     //线性表的删除，在指定位置删除某值(1<=i<=L.length)
    if (i < 1 || i > L.length + 1) {
        printf("删除位置不合理！\n");
        return 0;
    }
    e = L.data[i - 1];
    for (int j = i; j <= L.length; j++) {           //平均删除时间为O(n)
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return e;
}

int ListLength(SeqList &L) {        //求表长，计算元素个数
    if (L.length == 0) {
        printf("元素个数为0");
        return 0;
    }
    int count = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i]) {
            count++;
        }
    }
    return count;
}

int locateElem(SeqList &L, ElemType e) {    //按值查找逻辑下标
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;       //返回逻辑位置
        }
    }
    return 0;
}

int GetElem(SeqList &L, int i) {    //按位置查找
    if (i < 1 || i > L.length) {
        return 0;
    }
    return L.data[i - 1];
}

void PrintList(SeqList L) {    //从前到后输出值
    if (L.length == 0) {
        cout << "顺序表为空";
        exit(1);
    }
    printf("顺序表如下：");
    for (int i = 0; i < L.length; i++) {
        printf(" %d", L.data[i]);
    }
    cout << endl;
}

//////////////////第19页综合应用题////////////////////
//顺序表删除最小值，把最后一个值填补最小值的位置
int test1(SeqList &L, ElemType &value) {
    if (L.length == 0) {
        return false;
    }
    value = L.data[0];
    int pos = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] < value) {
            value = L.data[i];
            pos = i;
        }
    }
    L.data[pos] = L.data[L.length - 1];
    L.length--;
    return true;
}

//把顺序表逆置，要求时间复杂度为O(1)
void test2(SeqList &L) {
    ElemType temp;
    for (int i = 0; i < L.length / 2; i++) {
        temp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

//线性表删除所有值为x的数据元素，要求时间复杂度O(n),空间复杂度O(1)
void test3(SeqList &L, ElemType 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;
//法二
//    int k = 0, i = 0;
//    while (i < L.length) {
//        if (L.data[i] == x) {
//            k++;
//        } else {
//            L.data[i - k] = L.data[i];
//            i++;
//        }
//    }
//    L.length -= k;
}

//有序顺序表中，删除元素的值在s和t之间的所有元素(不包括s和t)
int test4(SeqList &L, ElemType s, ElemType t) {
    int i, j;
    if (s >= t || L.length == 0)
        return false;
    for (i = 0; i < L.length && L.data[i] < s; i++);
    if (i >= L.length)
        return false;
    for (j = i; j < L.length && L.data[j] <= t; j++);
    for (; j < L.length; i++, j++)
        L.data[i] = L.data[j];
    L.length = i;
    return true;
}

//顺序表中，删除元素的值在s和t之间的所有元素(包括s和t)
int test5(SeqList &L, ElemType s, ElemType t) {
    int i, k = 0;
    if (L.length == 0 || s >= t)
        return false;
    for (i = 0; i < L.length; i++) {
        if (L.data[i] >= s && L.data[i] <= t)
            k++;
        else
            L.data[i - k] = L.data[i];
    }
    L.length -= k;
    return true;
}

//删除有序顺序表中重复的元素，使其值均不同
int test6(SeqList &L) {
//法一
    if (L.length == 0)
        return 0;
    int i, k = 0;
    for (i = 1; i < L.length; i++) {
        if (L.data[i] == L.data[i - 1]) {
            k++;
        } else {
            L.data[i - k] = L.data[i];
        }
    }
    L.length -= k;
    return 1;

//法二
//    if (L.length == 0)
//        return 0;
//    int i, j;
//    for (i = 0, j = 1; j < L.length; j++) {
//        if (L.data[i] != L.data[j])
//            L.data[++i] = L.data[j];
//    }
//    L.length = i + 1;
//    return 1;
}

//合并两个有序顺序表为一个有序顺序表
int test7(SeqList &L1, SeqList &L2, SeqList &L3) {
    if (L1.length + L2.length > L3.MaxSize) {
        return false;
    }
    int i = 0, j = 0, k = 0;
    while (i < L1.length && j < L2.length) {
        if (L1.data[i] <= L2.data[j]) {
            L3.data[k++] = L1.data[i++];
        } else {
            L3.data[k++] = L2.data[j++];
        }
    }
    while (i < L1.length) {
        L3.data[k++] = L1.data[i++];
    }
    while (j < L2.length) {
        L3.data[k++] = L2.data[j++];
    }
    L3.length = k;
    return true;
}

//将数组A[m+n]中两个序列表位置整体互换
void Reverse(ElemType A[], int left, int right, int ArraySize) {
    if (left >= right || right >= ArraySize) {
        return;
    }
    int mid = (left + right) / 2;
    for (int i = 0; i < mid - left; i++) {
        ElemType temp = A[i];
        A[i] = A[right - i];
        A[right - 1] = temp;
    }
}

void test8(ElemType A[], int m, int n, int ArraySize) {
    Reverse(A, 0, m + n - 1, ArraySize);
    Reverse(A, 0, n - 1, ArraySize);
    Reverse(A, n, m + n - 1, ArraySize);
}

//用最少时间的方法查找x，找到则与后继交换位置，没找到则插入且任然递增有序
int test8(ElemType A[], ElemType x, int n) {
    int low = 0, high = n - 1, mid;
    mid = (low + high) / 2;
    while (low <= high) {       //二分法
        if (A[mid] == x)
            break;
        else if (A[mid] < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    if (A[mid] == x && mid != n - 1) {
        int t = A[mid];
        A[mid] = A[mid + 1];
        A[mid + 1] = t;
    }
    //不管是比A[0]小还是比A[n-1]大，都可以插入；因为当在A[0，n-1]之间找不到时，最后会出现low>high的情况
    if (low > high) {
        int i = 0;
        for (i = n - 1; i > high; i--) {
            A[i + 1] = A[i];
        }
        A[i + 1] = x;
    }
    return true;
}

int main() {
    SeqList L;
    InitList(L);
    int i, e;
    cout << "请输入元素个数：";
    cin >> L.length;
    for (i = 0; i < L.length; i++) {
        scanf("%d", &L.data[i]);
    }
    PrintList(L);
//    cout << "test6";
//    test6(L);
//    PrintList(L);
//    cout << "请输入插入的位置和插入的元素：";
//    scanf("%d%d", &i, &e);
//    ListInsert(L, i, e);
//    PrintList(L);
//    cout << "请输入删除的位置：";
//    scanf("%d", &i);
//    ListDelete(L, i, e);
//    cout << e << "被删除了!";
//    PrintList(L);
    return 0;
}