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

淩亂°似流年 2024-03-16 19:15 47阅读 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) ##

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

顺序表一般可以分为：

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

![5bbae16e824d419e9cddc9e2116d132d.png][]

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

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <string.h>
    #include <assert.h>
    #include <time.h>
    
    /* 静态顺序表数据结构 */
    #define N 10
    typedef int SQLType;
    typedef struct SeqList
    {
        SQLType data[N];            // 数据存储区。
        size_t size;                // 当前数据去有效数据个数。
    }SeqList;
    
    /* 静态顺序表初始化 */
    void SeqList_Init(SeqList* pSQ);
    
    /* 静态顺序表头插入 */
    void SeqList_PushFront(SeqList* pSQ, SQLType data);
    
    /* 静态顺序表尾插入 */
    void SeqList_PushBack(SeqList* pSQ, SQLType data);
    
    /* 静态顺序表头删除 */
    void SeqList_PopFront(SeqList* pSQ);
    
    /* 静态顺序表尾删除 */
    void SeqList_PopBack(SeqList* pSQ);
    
    /* 静态顺序表在指定位置插入 */
    void SeqList_Insert(SeqList* pSQ, size_t pos, SQLType data);
    
    /* 静态顺序表在指定位置删除 */
    void SeqList_Erase(SeqList* pSQ, size_t pos);
    
    /* 静态顺序表打印 */
    void SeqList_Print(SeqList* pSQ);
    
    /* 静态顺序表查找返回下标 */
    int SeqList_Find(SeqList* pSQ, SQLType data);
    
    /* 静态顺序表修改 */
    void SeqList_Modifi(SeqList* pSQ, size_t pos, SQLType data);
    
    /* 静态顺序表检测满 */
    bool SeqList_Fill(SeqList* pSQ);
    
    /* 静态顺序表检测空 */
    bool SeqList_Empty(SeqList* pSQ);
    
    /* 静态顺序表获取有效数据个数 */
    int SeqList_Size(SeqList* pSQ);
    
    /* 静态顺序表打印 */
    void SeqList_Show(SeqList* pSQ);

### 【1.2】静态顺序表初始化 ###

/* 静态顺序表初始化 */
    void SeqList_Init(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
        memset(pSQ->data, 0, sizeof(pSQ->data));
        pSQ->size = 0;
    }

### 【1.3】静态顺序表头插入 ###

/* 静态顺序表头插入 */
    void SeqList_PushFront(SeqList* pSQ, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断存储空间大小
        if (!SeqList_Fill(pSQ))
        {
            printf("SeqList Full!\n");
            return;
        }
    
        // 移动数据
        size_t end = pSQ->size;
        while (end > 0)
        {
            pSQ->data[end] = pSQ->data[end - 1];
            end--;
        }
        // 数据插入头部
        pSQ->data[0] = data;
        pSQ->size++;
    }

### 【1.4】静态顺序表尾插入 ###

/* 静态顺序表尾插入 */
    void SeqList_PushBack(SeqList* pSQ, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断存储空间大小
        if (!SeqList_Fill(pSQ))
        {
            printf("SeqList Full!\n");
            return;
        }
    
        // 程序走到这里说明数组中的数据没有满！
        pSQ->data[pSQ->size++] = data;
    }

### 【1.5】静态顺序表头删除 ###

/* 静态顺序表头删除 */
    void SeqList_PopFront(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断顺序表中是否还有有效的数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!\n");
            return;
        }
    
        // 移动数据
        int begin = 0;
        while (begin < pSQ->size - 1)
        {
            pSQ->data[begin] = pSQ->data[begin + 1];
            begin++;
        }
    
        pSQ->size--;
    }

### 【1.6】静态顺序表尾删除 ###

/* 静态顺序表尾删除 */
    void SeqList_PopBack(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断顺序表中是否还有有效的数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!\n");
            return;
        }
    
        // 程序走到这里说明数组中还有有效数据
        pSQ->size--;
    }

### 【1.7】静态顺序表在指定位置插入 ###

/* 静态顺序表在指定位置插入 */
    void SeqList_Insert(SeqList* pSQ, size_t pos, SQLType data)
    {
        // 断言保护形参指针变量不为NULL
        assert(pSQ);
    
        // 判断存储空间大小
        if (!SeqList_Fill(pSQ))
        {
            printf("SeqList Full!\n");
            return;
        }
    
        // 移动数据
        int end = SeqList_Size(pSQ) + 1;
        while (end > pos)
        {
            pSQ->data[end] = pSQ->data[end - 1];
            end--;
        }
    
        pSQ->data[pos] = data;
        pSQ->size++;
    }

### 【1.8】静态顺序表在指定位置删除 ###

/* 静态顺序表在指定位置删除 */
    void SeqList_Erase(SeqList* pSQ, size_t pos)
    {
        // 断言保护形参指针变量不为NULL
        assert(pSQ);
    
        // 判断动态顺序表中是否还有数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!");
            return;
        }
    
        size_t begin = pos;
        while (begin < pSQ->size)
        {
            pSQ->data[begin] = pSQ->data[begin + 1];
            begin++;
        }
    
        --pSQ->size;
    }

### 【1.9】静态顺序表打印 ###

/* 静态顺序表查找返回下标 */
    void SeqList_Print(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        for (int i = 0; i < pSQ->size; i++)
        {
            printf("%d\t", pSQ->data[i]);
        }
        printf("\n");
    }

### 【1.10】静态顺序表查找返回下标 ###

// 静态顺序表 - 查找 - 返回下标
    int SeqList_Find(SeqList* pSQ, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断顺序表中是否还有有效的数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!\n");
            return -1;
        }
    
        // 程序走到这里说明数组中有元素，找到下表并且返回
        for (int i = 0; i < pSQ->size; i++)
        {
            if (pSQ->data[i] == data)
                return i;
        }
    
        return -1;
    }

### 【1.11】静态顺序表修改 ###

/* 静态顺序表修改 */
    void SeqList_Modifi(SeqList* pSQ, size_t pos, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        pSQ->data[pos] = data;
    }

### 【1.12】静态顺序表检测空间是否满 ###

/* 静态顺序表检测满 */
    bool SeqList_Fill(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        return pSQ->size != N;
    }

### 【1.13】静态顺序表检测是否为空 ###

/* 静态顺序表检测空 */
    bool SeqList_Empty(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        return pSQ->size != 0;
    }

### 【1.14】静态顺序表获取有效数据个数 ###

/* 静态顺序表获取有效数据个数 */
    int SeqList_Size(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        return pSQ->size;
    }

### 【1.15】静态顺序表判空 ###

/* 动态顺序表-判空 */
    bool SequenceListEmpty(SeqList* pSL) {
        // 断言保护指针数据.
        assert(pSL);
    
        return pSL->_size == 0;
    }

### 【1.16】静态顺序表实现接口 ###

#include "SeqList.h"
    
    /* 静态顺序表初始化 */
    void SeqList_Init(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
        memset(pSQ->data, 0, sizeof(pSQ->data));
        pSQ->size = 0;
    }
    
    
    /* 静态顺序表头插入 */
    void SeqList_PushFront(SeqList* pSQ, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断存储空间大小
        if (!SeqList_Fill(pSQ))
        {
            printf("SeqList Full!\n");
            return;
        }
    
        // 移动数据
        size_t end = pSQ->size;
        while (end > 0)
        {
            pSQ->data[end] = pSQ->data[end - 1];
            end--;
        }
        // 数据插入头部
        pSQ->data[0] = data;
        pSQ->size++;
    }
    
    /* 静态顺序表尾插入 */
    void SeqList_PushBack(SeqList* pSQ, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断存储空间大小
        if (!SeqList_Fill(pSQ))
        {
            printf("SeqList Full!\n");
            return;
        }
    
        // 程序走到这里说明数组中的数据没有满！
        pSQ->data[pSQ->size++] = data;
    }
    
    /* 静态顺序表头删除 */
    void SeqList_PopFront(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断顺序表中是否还有有效的数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!\n");
            return;
        }
    
        // 移动数据
        int begin = 0;
        while (begin < pSQ->size - 1)
        {
            pSQ->data[begin] = pSQ->data[begin + 1];
            begin++;
        }
    
        pSQ->size--;
    }
    
    /* 静态顺序表尾删除 */
    void SeqList_PopBack(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断顺序表中是否还有有效的数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!\n");
            return;
        }
    
        // 程序走到这里说明数组中还有有效数据
        pSQ->size--;
    }
    
    /* 静态顺序表在指定位置插入 */
    void SeqList_Insert(SeqList* pSQ, size_t pos, SQLType data)
    {
        // 断言保护形参指针变量不为NULL
        assert(pSQ);
    
        // 判断存储空间大小
        if (!SeqList_Fill(pSQ))
        {
            printf("SeqList Full!\n");
            return;
        }
    
        // 移动数据
        int end = SeqList_Size(pSQ) + 1;
        while (end > pos)
        {
            pSQ->data[end] = pSQ->data[end - 1];
            end--;
        }
    
        pSQ->data[pos] = data;
        pSQ->size++;
    }
    
    /* 静态顺序表在指定位置删除 */
    void SeqList_Erase(SeqList* pSQ, size_t pos)
    {
        // 断言保护形参指针变量不为NULL
        assert(pSQ);
    
        // 判断动态顺序表中是否还有数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!");
            return;
        }
    
        size_t begin = pos;
        while (begin < pSQ->size)
        {
            pSQ->data[begin] = pSQ->data[begin + 1];
            begin++;
        }
    
        --pSQ->size;
    }
    
    /* 静态顺序表查找返回下标 */
    void SeqList_Print(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        for (int i = 0; i < pSQ->size; i++)
        {
            printf("%d\t", pSQ->data[i]);
        }
        printf("\n");
    }
    
    /* 静态顺序表查找返回下标 */
    int SeqList_Find(SeqList* pSQ, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        // 判断顺序表中是否还有有效的数据
        if (!SeqList_Empty(pSQ))
        {
            printf("SeqList Empty!\n");
            return -1;
        }
    
        // 程序走到这里说明数组中有元素，找到下表并且返回
        for (int i = 0; i < pSQ->size; i++)
        {
            if (pSQ->data[i] == data)
                return i;
        }
    
        return -1;
    }
    
    /* 静态顺序表修改 */
    void SeqList_Modifi(SeqList* pSQ, size_t pos, SQLType data)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        pSQ->data[pos] = data;
    }
    
    
    
    /* 静态顺序表检测满 */
    bool SeqList_Fill(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        return pSQ->size != N;
    }
    
    /* 静态顺序表检测空 */
    bool SeqList_Empty(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        return pSQ->size != 0;
    }
    
    /* 静态顺序表获取有效数据个数 */
    int SeqList_Size(SeqList* pSQ)
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        return pSQ->size;
    }
    
    /* 静态顺序表打印 */
    void SeqList_Show(SeqList* pSQ) 
    {
        // 断言：保护形参指针不为NULL
        assert(pSQ);
    
        int size = SeqList_Size(pSQ);
        for (int i = 0; i < size; i++)
        {
            printf("%d ", pSQ->data[i]);
        }
        printf("\n");
    }

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

#include "SeqList.h"
    /*【特点】
     * 1) - 内存是连续的。
     *【优点】
     * 1) - 下标访问（随机访问）时间复杂度是O(1)。
     * 2) - 末尾位置增加删除元素时间复杂度是O(1)。
     * 3) - 访问元素前后相邻位置的元素非常方便。
     *【缺点】
     * 1) - 非末尾位置增加删除元素需要进行大量的数据移动O(n)。
     * 2) - 搜索的时间复杂度：无序数组-线性搜索O(n)、有序数组-二分搜索O(logn)。
     * 3) - 数组扩容消耗比较大：扩容。
     */
    int main()
    {
        // 随机数种子
        srand((unsigned int)time(NULL));
        SeqList pSQ;
        SeqList_Init(&pSQ);
        // 尾插
        for (int i = 0; i < 5; i++)
        {
            SeqList_PushBack(&pSQ, rand() % 100);
        }
        SeqList_Show(&pSQ);
    
        // 头插
        for (int i = 0; i < 5; i++)
        {
            SeqList_PushFront(&pSQ, rand() % 100);
        }
        SeqList_Show(&pSQ);
    
        // 测满
        // SeqList_PushFront(&pSQ, rand() % 100);
    
        // 尾删
        for (int i = 0; i < 5; i++)
        {
            SeqList_PopBack(&pSQ);
        }
        SeqList_Show(&pSQ);
    
        // 头删
        for (int i = 0; i < 5; i++)
        {
            SeqList_PopFront(&pSQ);
        }
        SeqList_Show(&pSQ);
    
        // 测空
        // SeqList_PopFront(&pSQ);
         
        // 位置插入
        for (int i = 0; i < 5; i++)
        {
            SeqList_Insert(&pSQ, i, rand() % 100);
        }
        SeqList_Show(&pSQ);
        SeqList_Insert(&pSQ, 1, 1000);
        SeqList_Show(&pSQ);;
    
        // 位置移除
        SeqList_Erase(&pSQ, 0);
        SeqList_Show(&pSQ);
        SeqList_Erase(&pSQ, 0);
        SeqList_Show(&pSQ);
        SeqList_Erase(&pSQ, 0);
        SeqList_Show(&pSQ);
        SeqList_Erase(&pSQ, 0);
        SeqList_Show(&pSQ);
        SeqList_Erase(&pSQ, 0);
        SeqList_Show(&pSQ);
        SeqList_Erase(&pSQ, 0);
        SeqList_Show(&pSQ);
        // 测空
        SeqList_Erase(&pSQ, 0);
        SeqList_Show(&pSQ);
    
        // 尾插
        for (int i = 0; i < 9; i++)
        {
            SeqList_PushBack(&pSQ, rand() % 100);
        }
        SeqList_PushBack(&pSQ, 1000);
        SeqList_Show(&pSQ);
    
        // 测修改
        size_t pos = SeqList_Find(&pSQ, 1000);
        if (pos != -1)
        {
            SeqList_Modifi(&pSQ, pos, 2000);
        }
        SeqList_Show(&pSQ);
    
        return 0;
    }

[5bbae16e824d419e9cddc9e2116d132d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1b3f368f8e654418957a0b1677aca659.png