数据结构--线性表

• 代码

代码

直接放代码了，题目就是王道2022线性表那节的题目。

// 线性表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

# include <iostream>
# define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
# define LISTINCREMENT 10//线性表存储空间的分配增量
typedef struct {
    int* elem; //存储空间基址
    int length;//当前长度
    int listsize;//当前分配的存储容量(以sizeof(int)为单位)
}SqList;

/*
    初始化创建
*/
bool InitList_Sq(SqList &L) {
    L.elem = (int*)malloc(LIST_INIT_SIZE * sizeof(int));
    memset(L.elem, 0, LIST_INIT_SIZE * sizeof(int));
    if (!L.elem) return false;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return true;
}

void ListPrint_Sq(SqList& L) {
    if (L.length == 0) { printf_s("该顺序表为空"); exit(0); }
    for (int i = 0; i <= L.length - 1; i++) {
        printf_s("%d->", *(L.elem + i));
    }
    printf_s("\n");
}
/*
    在固定位置插入元素
*/
bool ListInsert_Sq(SqList& L, int i, int e) {
    //在顺序线性表L中第i个位置之前插入新的元素e
    //i的合法值
    if (i<1 || i>L.length + 1) return false;
    if (L.length > L.listsize) {//当前存储空间已满，增加分配
        int* newbase = (int*)realloc(L.elem, ((L.listsize + LISTINCREMENT)*sizeof(int)));
        if (!newbase) exit(OVERFLOW);
        L.elem = newbase;//新基址
        L.listsize  = L.listsize + LISTINCREMENT;
    }
    int* q = &(L.elem[i - 1]); //q为插入位置
    for (int* p = &(L.elem[L.length - 1]); p >= q; --p)
        *(p + 1) = *p;//插入位置的元素后移
    *q = e;
    ++L.length;
    return true;
}
/*
    删除固定位置的元素
*/
bool ListDelete_Sq(SqList& L, int i, int& e) {
    //在顺序线性表L中删除第i个元素，并用e返回值
    if (i<1 || i>L.length + 1)return false;
    int* p = &(L.elem[i - 1]);//被删除元素的位置
    e = *p;
    int* q = L.elem + L.length - 1;
    for (++p; p <= q; ++p) *(p - 1) = *p;//被删除元素之后的元素左移
    --L.length;
    return false;
}
/*
    删除顺序表中最小的元素 √
*/
bool ListDeleteMin_Sq(SqList& L, int& e) {
    if (!(L.elem) || L.length == 0) { printf_s("长度为零"); exit(-1); }
    int* q = L.elem + L.length - 1;
    int* p = L.elem;
    int* tag = L.elem;
    for (; p <= q; p++) {
        if (*p < *tag) tag = p;
    }
    e = *tag;
    *tag = *q;
    return true;
}
/*
    顺序表逆置 √
*/
bool ListReverse_Sq(SqList& L) {
    if (L.length == 0) return false;
    int* temp,*p,*q;
    // C++不允许空指针，定义只是定义int*,定义了并没有实际的指向。习惯上一定要进行初始指针的初始化操作。
    temp =(int*)malloc(1*sizeof(int));
    //也或者在这里直接用int类型的test即可。
    int test;
    for (int i = 0; i <= L.length/ 2-1; i++) {
        p = L.elem + i;
        q = L.elem + L.length - 1 - i;
        test = *p;
        *p = *q;
        *q = test;
    }
    return true;
}
/*
    删除顺序表中所有值为x的元素 √
     ----无论是有序表还是无序表用这个都行，有序表可以先找到所有的元素，然后一起移动，但是从时间复杂度上面来讲是一样的
    从逻辑上讲，2这个值的确被删除了
    但是从存储的结构上讲，2这个值还在存储空间里，只不过在逻辑上，这个位置已经是不合法的了。(改变了顺序表的长度)
*/
bool ListDeleValue(SqList& L, int e) {
    int k = 0;
    if (L.length == 0)return false;
    for (int i = 0; i < L.length; i++) {
        if (*(L.elem + i) != e) {
            k++;
            *(L.elem + k - 1) = *(L.elem + i);
        }
    }
    L.length = k;
}
/*
    删除值在s和t之间的节点 √
    跟上面的方法很像了
*/
bool ListDeleValueBetween(SqList& L, int s, int t) {
    if (s > t) {
        printf_s("请检查参数设置\n"); 
        return false;
    }
    int k = 0;
    if (L.length == 0)return false;
    for (int i = 0; i < L.length; i++) {
        if (*(L.elem + i) <s || *(L.elem + i) > t) {
            k++;
            *(L.elem + k - 1) = *(L.elem + i);
        }
    }
    L.length = k;
}
/*
    删除有序线性表中所有的重复值
*/
bool ListDeleteDuplicateValueInOrder(SqList& L) {
    if (L.length == 0 || L.length == 1)return false;
    int k=0;
    for (int i = 0; i < L.length; i++) {
        if (*(L.elem + i) != *(L.elem + i + 1)) {
            k++;
            *(L.elem + k - 1) = *(L.elem + i);
        }
    }
    L.length = k;
    return true;
}
int main()
{
    SqList test;
    InitList_Sq(test);
    ListInsert_Sq(test, 1, 2);
    ListInsert_Sq(test, 2, 2);
    ListInsert_Sq(test, 3, 2);
    ListInsert_Sq(test, 4, 3);
    ListInsert_Sq(test, 5, 4);
    ListInsert_Sq(test, 6, 5);
    ListInsert_Sq(test, 7, 5);
    ListInsert_Sq(test, 8, 6);

    //测试删除最小的元素
    //int tag;
    //ListDeleteMin_Sq(test, tag);
    //printf_s("%d", tag);

    //测试元素逆序
    //ListReverse_Sq(test);
    //ListPrint_Sq(test);

    //测试删除所有值为x的元素
    //ListDeleValue(test, 2);
    //ListPrint_Sq(test);

    //测试删除区间内的值
    //ListDeleValueBetween(test,2, 5);
    //ListPrint_Sq(test);

    //测试删除有序表中的重复值
    ListDeleteDuplicateValueInOrder(test);
    ListPrint_Sq(test);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件