【C数据结构】动态顺序表_SeqList

怼烎@ 2024-03-16 19:49 89阅读 0赞

**目录**

一、动态顺序表\_SeqList(C)

【1.1】动态顺序表定义数据结构和接口

【1.2】动态顺序表创建初始化

【1.3】动态顺序表初始化

【1.4】动态顺序表内存释放

【1.5】动态顺序表检测扩容

【1.6】动态顺序表头插入

【1.7】动态顺序表尾插入

【1.8】动态顺序表指定位置前插入

【1.9】动态顺序表头删除

【1.10】动态顺序表尾巴删除

【1.11】态顺序表指定位置前删除

【1.12】动态顺序表修改

【1.13】动态顺序表有效数据个数

【1.14】动态顺序表查找

【1.15】动态顺序表打印

【1.16】动态顺序表判断空

【1.17】动态顺序表实现接口

【1.18】动态顺序表测试接口

--------------------

## 一、动态顺序表\_SeqList(C) ##

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

*  **静态顺序表**：使用定长数组存储元素。
 *  **动态顺序表**：使用动态开辟的数组存储。

![b39ab254bb144a1ea9241255a4bf13f8.png][]

### 【1.1】动态顺序表定义数据结构和接口 ###

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <assert.h>
    #include <time.h>
    
    /* 顺序表 > 数据结构 */ 
    typedef int SLDataType;
    typedef struct SeqList
    {
        SLDataType* _buffer;    // 存储容器
        size_t _size;           // 有效元素数量
        size_t _capacity;       // 存储容量
    }SeqList;
    
    /* 顺序表操作接口 > 初始化 */
    void SeqList_Init(SeqList* pSL);
    
    /* 顺序表操作接口 > 内存销毁 */
    void SeqList_Destroy(SeqList* pSL);
    
    /* 顺序表操作接口 > 检查容量 */
    void SeqList_CheckCapacity(SeqList* pSL);
    
    /* 顺序表操作接口 > 头插 */
    void SeqList_PushFront(SeqList* pSL, SLDataType val); 
    
    /* 顺序表操作接口 > 尾插 */
    void SeqList_PushBack(SeqList* pSL, SLDataType val);
    
    /* 顺序表操作接口 > 指定位置插入 */
    void SeqList_Insert(SeqList* pSL, size_t pos, SLDataType val);
    
    /* 顺序表操作接口 > 头插 */
    void SeqList_PopFront(SeqList* pSL);
    
    /* 顺序表操作接口 > 尾插 */
    void SeqList_PopBack(SeqList* pSL);
    
    /* 顺序表操作接口 > 指定位置删除 */
    void SeqList_Erase(SeqList* pSL, size_t pos);
    
    /* 顺序表操作接口 > 指定位置修改 */
    void SeqList_Modif(SeqList* pSL, size_t pos, SLDataType val);
    
    /* 顺序表操作接口 > 返回大小 */
    size_t SeqList_Size(SeqList* pSL);
    
    /* 顺序表操作接口 > 返回容量 */
    size_t SeqList_Capacity(SeqList* pSL);
    
    /* 顺序表操作接口 > 查找 */
    int SeqList_Find(SeqList* pSL, SLDataType val);
    
    /* 顺序表操作接口 > 判断是否空 */
    bool SeqList_Empty(SeqList* pSL);
    
    /* 顺序表操作接口 > 打印 */
    void SeqList_Print(SeqList* pSL);

### 【1.2】动态顺序表创建初始化 ###

/* 动态顺序表-创建初始化函数 */
    SeqList* SequenceListCreateInitialize() {
        // 创建SeqList指针对象，初始化后返回指针.
        SeqList* pTemp = (SeqList*)malloc(sizeof(SeqList));
        if (pTemp == NULL) {
            perror("SequenceListCreateInitialize malloc fail!\n");
            exit(-1);
        }
    
        // 处理数据.
        pTemp->_data = NULL;
        pTemp->_size = pTemp->_capacity = 0;
        return pTemp;
    }

### 【1.3】动态顺序表初始化 ###

/* 顺序表操作接口 > 初始化 */
    void SeqList_Init(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 初始化
        pSL->_buffer = NULL;
        pSL->_capacity = pSL->_size = 0;
    }

### 【1.4】动态顺序表内存释放 ###

/* 顺序表操作接口 > 内存销毁 */
    void SeqList_Destroy(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 释放内存
        free(pSL->_buffer); 
        // 初始化
        pSL->_buffer = NULL;
        pSL->_capacity = pSL->_size = 0;
    }

### 【1.5】动态顺序表检测扩容 ###

/* 顺序表操作接口 > 检查容量 */
    void SeqList_CheckCapacity(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // == 需要扩容 != 不需要扩容
        if (pSL->_size == pSL->_capacity)
        {
            // 当前容量
            size_t curCapacity = SeqList_Capacity(pSL);
            // 新容量=当前容量*2
            size_t newCapacity = curCapacity == 0 ? 4 : curCapacity * 2;
            SLDataType* newBuffer = (SLDataType*)realloc(pSL->_buffer, sizeof(SLDataType) * newCapacity);
            assert(newBuffer);
            
            // 程序走到这里说明扩容成功了
            pSL->_buffer = newBuffer; newBuffer = NULL;
            pSL->_capacity = newCapacity;
        }
    }

### 【1.6】动态顺序表头插入 ###

/* 顺序表操作接口 > 头插 */
    void SeqList_PushFront(SeqList* pSL, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 判断是否需要扩容，需要扩容就扩容2倍，不需要扩容直接插入数据
        SeqList_CheckCapacity(pSL);
        // 挪动数据后
        size_t end = SeqList_Size(pSL);
        while (end > 0)
        {
            pSL->_buffer[end] = pSL->_buffer[end - 1];
            --end;
        }
        // 头部插入数据
        pSL->_buffer[0] = val;
        pSL->_size++;
    }

### 【1.7】动态顺序表尾插入 ###

/* 顺序表操作接口 > 尾插 */
    void SeqList_PushBack(SeqList* pSL, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        
        // 判断是否需要扩容，需要扩容就扩容2倍，不需要扩容直接插入数据
        SeqList_CheckCapacity(pSL);
        // 插入数据
        pSL->_buffer[pSL->_size++] = val;
    }

### 【1.8】动态顺序表指定位置前插入 ###

/* 顺序表操作接口 > 指定位置插入 */
    void SeqList_Insert(SeqList* pSL, size_t pos, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        // 保证pos的值是合法的
        assert(pos >= 0 && pos <= SeqList_Size(pSL)); 
        
        // 判断是否需要扩容，需要扩容就扩容2倍，不需要扩容直接插入数据
        SeqList_CheckCapacity(pSL);
    
        // 挪动数据后
        size_t end = SeqList_Size(pSL);
        while (end > pos)
        {
            pSL->_buffer[end] = pSL->_buffer[end - 1];
            --end;
        }
    
        // pos位置插入数据
        pSL->_buffer[pos] = val;
        pSL->_size++;
    }

### 【1.9】动态顺序表头删除 ###

/* 顺序表操作接口 > 头删 */
    void SeqList_PopFront(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 检查是否还有数据
        if (SeqList_Empty(pSL))
            return;
    
        size_t curSize = SeqList_Size(pSL);
        size_t begin = 0;
        // 从前往后挪动相当于删除数据
        while (begin < curSize)
        {
            pSL->_buffer[begin] = pSL->_buffer[begin + 1];
            begin++;
        }
    
        // 删除数据
        pSL->_size--;
    }

### 【1.10】动态顺序表尾巴删除 ###

/* 顺序表操作接口 > 尾删 */
    void SeqList_PopBack(SeqList* pSL) 
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 检查是否还有数据
        if (SeqList_Empty(pSL))
            return;
    
        // 删除数据
        pSL->_size--;
    }

### 【1.11】态顺序表指定位置前删除 ###

/* 顺序表操作接口 > 指定位置删除 */
    void SeqList_Erase(SeqList* pSL, size_t pos)
    {
        // 保证指针参数不是NULL指针  
        assert(pSL); 
        // 保证pos的值是合法的
        assert(pos >= 0 && pos < SeqList_Size(pSL)); 
    
        // 检查是否还有数据
        if (SeqList_Empty(pSL))
            return;
    
        size_t curSize = SeqList_Size(pSL);
        size_t begin = pos;
        // 从前往后挪动相当于删除数据
        while (begin < curSize)
        {
            pSL->_buffer[begin] = pSL->_buffer[begin + 1];
            begin++;
        }
    
        // 删除数据
        pSL->_size--;
    }

### 【1.12】动态顺序表修改 ###

/* 顺序表操作接口 > 指定位置修改 */
    void SeqList_Modif(SeqList* pSL, size_t pos, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        // 保证pos的值是合法的
        assert(pos >= 0 && pos <= SeqList_Size(pSL)); 
        // 修改pos位置的数据
        pSL->_buffer[pos] = val;
    }

### 【1.13】动态顺序表有效数据个数 ###

/* 顺序表操作接口 > 返回大小 */
    size_t SeqList_Size(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        return pSL->_size;
    }

### 【1.14】动态顺序表查找 ###

/* 顺序表操作接口 > 查找 */
    int SeqList_Find(SeqList* pSL, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        int curSize = SeqList_Size(pSL);
        
        // 遍历查找匹配的项
        for (int i = 0; i < curSize; i++)
        {
            if (pSL->_buffer[i] == val)
                return i;
        }
    
        // 未找到
        return -1;
    }

### 【1.15】动态顺序表打印 ###

/* 顺序表操作接口 > 打印 */
    void SeqList_Print(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        int curSize = SeqList_Size(pSL);
    
        // 遍历打印
        for (int i = 0; i < curSize; i++)
        {
            printf("%d ", pSL->_buffer[i]);
        }
        printf("\n");
    }

### 【1.16】动态顺序表判断空 ###

/* 顺序表操作接口 > 判断是否空 */
    bool SeqList_Empty(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        return pSL->_size == 0;
    }

### 【1.17】动态顺序表实现接口 ###

#include "SeqList.h"
    
    /* 顺序表操作接口 > 初始化 */
    void SeqList_Init(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 初始化
        pSL->_buffer = NULL;
        pSL->_capacity = pSL->_size = 0;
    }
    
    /* 顺序表操作接口 > 内存销毁 */
    void SeqList_Destroy(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 释放内存
        free(pSL->_buffer); 
        // 初始化
        pSL->_buffer = NULL;
        pSL->_capacity = pSL->_size = 0;
    }
    
    /* 顺序表操作接口 > 检查容量 */
    void SeqList_CheckCapacity(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // == 需要扩容 != 不需要扩容
        if (pSL->_size == pSL->_capacity)
        {
            // 当前容量
            size_t curCapacity = SeqList_Capacity(pSL);
            // 新容量=当前容量*2
            size_t newCapacity = curCapacity == 0 ? 4 : curCapacity * 2;
            SLDataType* newBuffer = (SLDataType*)realloc(pSL->_buffer, sizeof(SLDataType) * newCapacity);
            assert(newBuffer);
            
            // 程序走到这里说明扩容成功了
            pSL->_buffer = newBuffer; newBuffer = NULL;
            pSL->_capacity = newCapacity;
        }
    }
    
    /* 顺序表操作接口 > 头插 */
    void SeqList_PushFront(SeqList* pSL, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 判断是否需要扩容，需要扩容就扩容2倍，不需要扩容直接插入数据
        SeqList_CheckCapacity(pSL);
        // 挪动数据后
        size_t end = SeqList_Size(pSL);
        while (end > 0)
        {
            pSL->_buffer[end] = pSL->_buffer[end - 1];
            --end;
        }
        // 头部插入数据
        pSL->_buffer[0] = val;
        pSL->_size++;
    }
    
    /* 顺序表操作接口 > 尾插 */
    void SeqList_PushBack(SeqList* pSL, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        
        // 判断是否需要扩容，需要扩容就扩容2倍，不需要扩容直接插入数据
        SeqList_CheckCapacity(pSL);
        // 插入数据
        pSL->_buffer[pSL->_size++] = val;
    }
    
    /* 顺序表操作接口 > 指定位置插入 */
    void SeqList_Insert(SeqList* pSL, size_t pos, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        // 保证pos的值是合法的
        assert(pos >= 0 && pos <= SeqList_Size(pSL)); 
        
        // 判断是否需要扩容，需要扩容就扩容2倍，不需要扩容直接插入数据
        SeqList_CheckCapacity(pSL);
    
        // 挪动数据后
        size_t end = SeqList_Size(pSL);
        while (end > pos)
        {
            pSL->_buffer[end] = pSL->_buffer[end - 1];
            --end;
        }
    
        // pos位置插入数据
        pSL->_buffer[pos] = val;
        pSL->_size++;
    }
    
    /* 顺序表操作接口 > 头插 */
    void SeqList_PopFront(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 检查是否还有数据
        if (SeqList_Empty(pSL))
            return;
    
        size_t curSize = SeqList_Size(pSL);
        size_t begin = 0;
        // 从前往后挪动相当于删除数据
        while (begin < curSize)
        {
            pSL->_buffer[begin] = pSL->_buffer[begin + 1];
            begin++;
        }
    
        // 删除数据
        pSL->_size--;
    }
    
    /* 顺序表操作接口 > 尾插 */
    void SeqList_PopBack(SeqList* pSL) 
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
    
        // 检查是否还有数据
        if (SeqList_Empty(pSL))
            return;
    
        // 删除数据
        pSL->_size--;
    }
    
    /* 顺序表操作接口 > 指定位置删除 */
    void SeqList_Erase(SeqList* pSL, size_t pos)
    {
        // 保证指针参数不是NULL指针  
        assert(pSL); 
        // 保证pos的值是合法的
        assert(pos >= 0 && pos < SeqList_Size(pSL)); 
    
        // 检查是否还有数据
        if (SeqList_Empty(pSL))
            return;
    
        size_t curSize = SeqList_Size(pSL);
        size_t begin = pos;
        // 从前往后挪动相当于删除数据
        while (begin < curSize)
        {
            pSL->_buffer[begin] = pSL->_buffer[begin + 1];
            begin++;
        }
    
        // 删除数据
        pSL->_size--;
    }
    
    /* 顺序表操作接口 > 指定位置修改 */
    void SeqList_Modif(SeqList* pSL, size_t pos, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        // 保证pos的值是合法的
        assert(pos >= 0 && pos <= SeqList_Size(pSL)); 
        // 修改pos位置的数据
        pSL->_buffer[pos] = val;
    }
    
    /* 顺序表操作接口 > 返回大小 */
    size_t SeqList_Size(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        return pSL->_size;
    }
    
    /* 顺序表操作接口 > 返回容量 */
    size_t SeqList_Capacity(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        return pSL->_capacity;
    }
    
    /* 顺序表操作接口 > 查找 */
    int SeqList_Find(SeqList* pSL, SLDataType val)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        int curSize = SeqList_Size(pSL);
        
        // 遍历查找匹配的项
        for (int i = 0; i < curSize; i++)
        {
            if (pSL->_buffer[i] == val)
                return i;
        }
    
        // 未找到
        return -1;
    }
    
    /* 顺序表操作接口 > 判断是否空 */
    bool SeqList_Empty(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        return pSL->_size == 0;
    }
    
    /* 顺序表操作接口 > 打印 */
    void SeqList_Print(SeqList* pSL)
    {
        // 保证指针参数不是NULL指针
        assert(pSL); 
        int curSize = SeqList_Size(pSL);
    
        // 遍历打印
        for (int i = 0; i < curSize; i++)
        {
            printf("%d ", pSL->_buffer[i]);
        }
        printf("\n");
    }

### 【1.18】动态顺序表测试接口 ###

#include "SeqList.h"
    #define NUM 10
    
    void TestSeqList_1()
    {
        srand((unsigned int)time(NULL));
    
        SeqList pSL;
        SeqList_Init(&pSL);
        // 尾插
        printf("尾插：\n");
        for (int i = 0; i < NUM; i++)
        {
            SeqList_PushBack(&pSL, rand() % 100);
            SeqList_Print(&pSL);
        }
        
        // 头插
        printf("头插：\n");
        for (int i = 0; i < NUM; i++)
        {
            SeqList_PushFront(&pSL, rand() % 100);
            SeqList_Print(&pSL);
        }
        
        // 尾删
        printf("尾删：\n");
    
        for (int i = 0; i < NUM / 2; i++)
        {
            SeqList_PopBack(&pSL);
          SeqList_Print(&pSL);
        }
        
        // 头删
        printf("头删：\n");
        for (int i = 0; i < NUM / 2 + 1; i++)
        {
            SeqList_PopFront(&pSL);
          SeqList_Print(&pSL);
        }
        
        printf("CurCapacity:%d CurSize:%d\n", pSL._capacity, pSL._size);
        SeqList_Destroy(&pSL);
    }
    
    void TestSeqList_2()
    {
        SeqList pSL;
        SeqList_Init(&pSL);
        // 指定位置插入
        printf("指定位置插入数据：\n");
        SeqList_Insert(&pSL, 0, 0);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, 1, 1);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, 2, 2);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, 3, 3);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, 4, 4);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, pSL._size, 1000);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, pSL._size, 2000);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, pSL._size, 3000);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, 0, 5000);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, 0, 6000);
        SeqList_Print(&pSL);
        SeqList_Insert(&pSL, 0, 7000);
        SeqList_Print(&pSL);
        // 指定位置删除
        printf("指定位置删除数据：\n");
        SeqList_Print(&pSL);
        SeqList_Erase(&pSL, 0);
        SeqList_Print(&pSL);
        SeqList_Erase(&pSL, 0);
        SeqList_Print(&pSL);
        SeqList_Erase(&pSL, pSL._size - 1);
        SeqList_Print(&pSL);
        SeqList_Erase(&pSL, pSL._size - 1);
        SeqList_Print(&pSL);
        // 查找修改
        printf("查到位置后修改值：\n");
        int pos = SeqList_Find(&pSL, 0);
        if (pos != -1)
        {
            SeqList_Modif(&pSL, pos, 9999);
        }
        SeqList_Print(&pSL);
    
        printf("CurCapacity:%d CurSize:%d\n", pSL._capacity, pSL._size);
        SeqList_Destroy(&pSL);
    }
    
    int main()
    {
        TestSeqList_1();
        TestSeqList_2();
    
        return 0;
    }

[b39ab254bb144a1ea9241255a4bf13f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6898f9bfff4b4cda93e601d3f19c180a.png