0
0

顺序表功能实现（增删查改）《数据结构(C语言版)》

博文内容：

数据结构（C语言版）之顺序表及其功能实现（增删查改）

博文作者：

新晓·故知

注：

★博文转载请注明出处。

★博文仅供学习交流，禁止用于商业用途。

《数据结构(C语言版)》实战项目之顺序表（增删查改）功能实现：

问题导引：

在学习线性表的之顺序表后，可以通过C语言实现顺序表的增、删、查、改功能。

实现步骤：

具体实现步骤参见链接：

P2—＜顺序表＞《数据结构(C语言版)》

https://blog.csdn.net/m0_57859086/article/details/123438461

源码如下，欢迎复制测试指正！

版本1：

版本1测试示例：

源代码：

Test.c：

#include "SeqList.h"

//尾插测试
void TestSeqList1()
{ 
    //尾插
    SeqList s;
    SeqListInit(&s); //这里&是取地址
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPushBack(&s, 5);
    SeqListPushBack(&s, 0);
    SeqListPrint(&s);
    
    SeqListPushBack(&s, 10);
    SeqListPushBack(&s, 20);
    SeqListPrint(&s);

    //如果不小心传了空指针，须使用断言进行报错查找
    //SeqListPrint(NULL);

    //测试越界
    //int a[10];
    a[10] = 1;
    a[11] = 1;
    //a[12] = 1;
    a[100] = 1;

}
//尾删测试
void TestSeqList2()
{
    //尾插
    SeqList s;
    SeqListInit(&s); //这里&是取地址
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPushBack(&s, 5);
    SeqListPushBack(&s, 0);
    SeqListPrint(&s);
    //尾删，删除最后两个数据
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPrint(&s);
    //删除完毕，且删多了
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPrint(&s);
    //再次尾插数据
    SeqListPushBack(&s, 10);
    SeqListPushBack(&s, 20);
    SeqListPrint(&s);

}

//头插测试
void TestSeqList3()
{   //扩容测试
    /*int* p = (int*)malloc(sizeof(int) * 10);
    printf("%p\n", p);

    int* p1 = (int*)realloc(p, sizeof(int) * 100);
    printf("%p\n", p1);*/
    SeqList s;
    SeqListInit(&s);
    //尾插
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPrint(&s);

    //头插
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, -1);
    SeqListPrint(&s);
}
//头删测试
void TestSeqList4()
{
    
    SeqList s;
    SeqListInit(&s);
    //尾插
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPrint(&s);
    //头插
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, -1);
    SeqListPrint(&s);
    //头删
    SeqListPopFront(&s);
    SeqListPopFront(&s);
    SeqListPopFront(&s);
    SeqListPopFront(&s);
    SeqListPopFront(&s);
    SeqListPrint(&s);

    SeqListPopFront(&s);
    SeqListPrint(&s);
    //再次头删，删多了
    SeqListPopFront(&s);
    SeqListPopFront(&s);
    SeqListPrint(&s);
    //再次头插
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, -1);
    SeqListPrint(&s);

}
//pos指定位置插入测试
void TestSeqList5()
{
    SeqList s;
    SeqListInit(&s);
    //尾插
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPrint(&s);
    //pos指定位置插入数据
    SeqListInsert(&s, 10, 100);
    SeqListInsert(&s, 1, 20);
    SeqListInsert(&s, 5, 50);
    SeqListInsert(&s, 0, 50);
    SeqListPrint(&s);
    //销毁释放内存
    SeqListDestroy(&s);

}

//pos指定位置删除测试
void TestSeqList6()
{
    SeqList s;
    SeqListInit(&s);
    //尾插
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPrint(&s);

    //头插
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, -1);
    SeqListPrint(&s);
    //pos指定位置删除
    SeqListErase(&s, 4);
    SeqListPrint(&s);

    SeqListErase(&s, 0);
    SeqListPrint(&s);

    SeqListErase(&s, 1);
    SeqListPrint(&s);
}
//顺序表修改测试
void TestSeqList7()
{
    SeqList s;
    SeqListInit(&s);
    //尾插
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPushBack(&s, 5);
    SeqListPushBack(&s, 6);
    SeqListPrint(&s);
    
    //1.直接修改
    SeqListModify(&s, 3, 1000);
    SeqListPrint(&s);
    //2.按值查找后修改
    int pos = SeqListFind(&s, 6);//括号第二个数是确定的值，不是下标
    if (pos != -1)
    {
        SeqListModify(&s, pos, 90);
    }
    SeqListPrint(&s);

}

int main()
{
    SeqList s;
    SeqListInit(&s); //这里&是取地址
    TestSeqList1();
    TestSeqList2();
    TestSeqList3();
    TestSeqList4();
    TestSeqList5();
    TestSeqList6();
    TestSeqList7();

    return 0;
}

SeqList.c：

#include "SeqList.h"

//打印顺序表
void SeqListPrint(SeqList* psl)
{   //Print可以不传指针，因为它不需要修改结构体的内容，但结构体较大，传指针可以减少拷贝
    assert(psl);

    for (int i = 0; i < psl->size; ++i)
    {
        printf("%d ", psl->a[i]);
    }
    printf("\n");
}
//顺序表初始化
void SeqListInit(SeqList* psl)
{
    assert(psl);

    psl->a = NULL;
    psl->size = 0;
    psl->capacity = 0;
}
//顺序表销毁、释放内存
void SeqListDestroy(SeqList* psl)
{
    assert(psl);
    free(psl->a);
    psl->a = NULL;
    psl->capacity = psl->size = 0;
}

//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl)
{
    // ˣҪ
    if (psl->size == psl->capacity)
    {   //relloc扩容
        size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        //因为最初是0，*2也是0.所以最初为0就给4个(4没有特定含义，只要不是太大就行），若不是0就 psl->capacity * 2（折中）*3或*4均可

        SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        else
        {
            psl->a = tmp;
            psl->capacity = newCapacity;
        }
    }

}

//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
    assert(psl);
    SeqListCheckCapacity(psl);

    psl->a[psl->size] = x;
    psl->size++;
}

//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
    assert(psl);

    //psl->a[psl->size - 1] = 0;  
    //此语句是将删除后的覆盖为0，但这样做不太好
    //原因：1.若原有最后一个为0，意义不大  2.若类型不为int，而是double或char，覆盖为0有误
    //因为size标识有效数据，因此即使删除，数据还在capacity，即使删除后没有被覆盖，但不会访问
    if (psl->size > 0)
    {
        psl->size--;
    }
}


//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
        assert(psl);
        SeqListCheckCapacity(psl);
        // 挪动数据，腾出头部空间
        int end = psl->size - 1;
        while (end >= 0)
        {
            psl->a[end + 1] = psl->a[end];
            --end;
        }

        psl->a[0] = x;
        psl->size++;

        //SeqListInsert(psl, 0, x);
    
}


//顺序表头删
void SeqListPopFront(SeqList* psl)
{
    
        assert(psl);
        if (psl->size > 0)
        {
            //挪动数据覆盖删除
            int begin = 1;
            while (begin < psl->size)
            {
                psl->a[begin - 1] = psl->a[begin];
                ++begin;
            }
            --psl->size;

        }
        
}


// 在pos(指定位置）插入x
//void SeqListInsert(SeqList* psl, int pos, SLDataType x)    //解决整型提升形成的死循环,解决1
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
    // 暴力检查
    assert(psl);
    // 温和检查
    if (pos > psl->size)
    {
        printf("pos 越界：%d\n", pos);
        return;
        //exit(-1);  //直接终止程序，没必要
    }
    // 暴力检查
    //assert(pos <= psl->size);

    //检查后，根据需要是否增容
    SeqListCheckCapacity(psl);

    //解决整型提升形成的死循环,解决2
    //int end = psl->size-1;
    //while (end >=(int)pos)
    //{
    //    psl->a[end+1] = psl->a[end];
    //    --end;
    //}

    //解决整型提升形成的死循环,解决3
    size_t end = psl->size;
    while (end > pos)
    {
        psl->a[end] = psl->a[end - 1];
        --end;
    }
    psl->a[pos] = x;
    psl->size++;
}

// 删除pos(指定位置）的数据
void SeqListErase(SeqList* psl, size_t pos)
{
    assert(psl);
    assert(pos < psl->size);

    size_t begin = pos + 1;
    while (begin < psl->size)
    {
        psl->a[begin - 1] = psl->a[begin];
        ++begin;
    }

    psl->size--;
}
//按值查找
int SeqListFind(SeqList* psl, SLDataType x)
{
    assert(psl);

    for (int i = 0; i < psl->size; ++i)
    {
        if (psl->a[i] == x)
        {
            return i;
        }
    }

    return -1;
}
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
    assert(psl);
    assert(pos < psl->size);
    psl->a[pos] = x;
}

SeqList.h：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 要求：存储的数据从0开始，依次连续存储
// 静态的顺序表
// 问题：开小了，不够用。开大了，存在浪费。
//#define N 10000
//struct SeqList
//{
//    int a[N];
//    int size; // 记录存储了多少个数据
//};

typedef int SLDataType;

// 动态的顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;     // 存储数据个数
    int capacity; // 存储空间大小
}SL, SeqList;


//void SLInit(SeqList* psl);
//顺序表初始化
void SeqListInit(SeqList* psl);
//顺序表销毁
void SeqListDestroy(SeqList* psl);

//打印顺序表
void SeqListPrint(SeqList* psl);
//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl);

// 时间复杂度是O(1)
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);

// 时间复杂度是O(N)
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);

// 在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos);

// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

版本2：

附用SeqListInsert、SeqListErase版

附用SeqListInsert、SeqListErase测试示例：

Test.c：

#include "SeqList.h"

//附用SeqListInsert、SeqListErase版测试
void TestSeqList7()
{
    SeqList s;
    SeqListInit(&s);
    //尾插
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPushBack(&s, 5);
    SeqListPushBack(&s, 6);
    SeqListPrint(&s);
    //头插
    SeqListPushFront(&s, -1);
    SeqListPushFront(&s, -2);
    SeqListPrint(&s);
    //头删
    SeqListPopFront(&s);
    SeqListPopFront(&s);
    SeqListPrint(&s);
    //尾删
    SeqListPopBack(&s);
    SeqListPopBack(&s);
    SeqListPrint(&s);
    
    //1.直接修改
    SeqListModify(&s, 3, 1000);
    SeqListPrint(&s);
    //2.按值查找后修改
    int pos = SeqListFind(&s, 6);//括号第二个数是确定的值，不是下标
    if (pos != -1)
    {
        SeqListModify(&s, pos, 90);
    }
    SeqListPrint(&s);
}

int main()
{
    SeqList s;
    SeqListInit(&s); //这里&是取地址
    TestSeqList7();

    return 0;
}

SeqList.c:

#include "SeqList.h"

//打印顺序表
void SeqListPrint(SeqList* psl)
{   //Print可以不传指针，因为它不需要修改结构体的内容，但结构体较大，传指针可以减少拷贝
    assert(psl);

    for (int i = 0; i < psl->size; ++i)
    {
        printf("%d ", psl->a[i]);
    }
    printf("\n");
}
//顺序表初始化
void SeqListInit(SeqList* psl)
{
    assert(psl);

    psl->a = NULL;
    psl->size = 0;
    psl->capacity = 0;
}
//顺序表销毁、释放内存
void SeqListDestroy(SeqList* psl)
{
    assert(psl);
    free(psl->a);
    psl->a = NULL;
    psl->capacity = psl->size = 0;
}

//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl)
{
    // ˣҪ
    if (psl->size == psl->capacity)
    {   //relloc扩容
        size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        //因为最初是0，*2也是0.所以最初为0就给4个(4没有特定含义，只要不是太大就行），若不是0就 psl->capacity * 2（折中）*3或*4均可

        SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        else
        {
            psl->a = tmp;
            psl->capacity = newCapacity;
        }
    }

}


//顺序表尾插--附用SeqListInsert版
void SeqListPushBack(SeqList* psl, SLDataType x)
{
    assert(psl);
    SeqListInsert(psl, psl->size, x);
}

//顺序表尾删—附用SeqListErase版
void SeqListPopBack(SeqList* psl)
{
    assert(psl);
    SeqListErase(psl, psl->size - 1);
}

//顺序表头插--附用SeqListInsert版
void SeqListPushFront(SeqList* psl, SLDataType x)
{
    assert(psl);
    SeqListInsert(psl, 0, x);

}

//顺序表尾头删—附用SeqListErase版
void SeqListPopFront(SeqList* psl)
{

    assert(psl);
    SeqListErase(psl, 0);

}

// 在pos(指定位置）插入x
//void SeqListInsert(SeqList* psl, int pos, SLDataType x)    //解决整型提升形成的死循环,解决1
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
    // 暴力检查
    assert(psl);
    // 温和检查
    if (pos > psl->size)
    {
        printf("pos 越界：%d\n", pos);
        return;
        //exit(-1);  //直接终止程序，没必要
    }
    // 暴力检查
    //assert(pos <= psl->size);

    //检查后，根据需要是否增容
    SeqListCheckCapacity(psl);

    //解决整型提升形成的死循环,解决2
    //int end = psl->size-1;
    //while (end >=(int)pos)
    //{
    //    psl->a[end+1] = psl->a[end];
    //    --end;
    //}

    //解决整型提升形成的死循环,解决3
    size_t end = psl->size;
    while (end > pos)
    {
        psl->a[end] = psl->a[end - 1];
        --end;
    }
    psl->a[pos] = x;
    psl->size++;
}

// 删除pos(指定位置）的数据
void SeqListErase(SeqList* psl, size_t pos)
{
    assert(psl);
    assert(pos < psl->size);

    size_t begin = pos + 1;
    while (begin < psl->size)
    {
        psl->a[begin - 1] = psl->a[begin];
        ++begin;
    }

    psl->size--;
}
//按值查找
int SeqListFind(SeqList* psl, SLDataType x)
{
    assert(psl);

    for (int i = 0; i < psl->size; ++i)
    {
        if (psl->a[i] == x)
        {
            return i;
        }
    }

    return -1;
}
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
    assert(psl);
    assert(pos < psl->size);
    psl->a[pos] = x;
}

SeqList.h:

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 要求：存储的数据从0开始，依次连续存储
// 静态的顺序表
// 问题：开小了，不够用。开大了，存在浪费。
//#define N 10000
//struct SeqList
//{
//    int a[N];
//    int size; // 记录存储了多少个数据
//};

typedef int SLDataType;

// 动态的顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;     // 存储数据个数
    int capacity; // 存储空间大小
}SL, SeqList;


//void SLInit(SeqList* psl);
//顺序表初始化
void SeqListInit(SeqList* psl);
//顺序表销毁
void SeqListDestroy(SeqList* psl);

//打印顺序表
void SeqListPrint(SeqList* psl);
//检查容量，降低冗余度
void SeqListCheckCapacity(SeqList* psl);

// 时间复杂度是O(1)
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);

// 时间复杂度是O(N)
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);

// 在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos);

// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
//顺序表修改
void SeqListModify(SeqList* psl, size_t pos, SLDataType x);

顺序表修改功能：

顺序表按值查找功能：

后记：

●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                            ——By 作者：新晓·故知
标签： 数据结构 c语言
本文转载自: https://blog.csdn.net/m0_57859086/article/details/123451223
版权归原作者 新晓·故知 所有， 如有侵权，请联系我们删除。
登录后发布评论

“顺序表功能实现（增删查改）《数据结构(C语言版)》”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

前端必知必会-Bootstrap 5 导航栏Navbars

【Spring】RESTful设计风格

MyBatis——#{} 和 ${} 的区别和动态 SQL

表的增删改查（MySQL）

Linux 再入门整理：详解 /etc/fstab 文件

HBase Java API编程-学习记录

【大数据技术基础 | 实验十二】Hive实验：Hive分区

文章导航