0
0

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

博文内容：

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

博文作者：

新晓·故知

注：

★博文转载请注明出处。

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

**1.****线性表 **

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

**2.****顺序表 **

*2.1***概念及结构 **

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

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

  1. **动态顺序表：使 **

传值调用：

传址调用：

顺序表初始化：

//Test.c  测试
#include "SeqList.h"

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

//SeqList.c  功能实现
#include "SeqList.h"
void SeqListInit(SeqList* psl)
{
    psl->a = NULL;
    psl->size = 0;
    psl->capacity = 0;
}

//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 SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);

顺序表尾插：

//Test.c 测试
#include "SeqList.h"

int main()
{
    SeqList s;
    SeqListInit(&s); //这里&是取地址
    SeqListPushBack(&s, 1);
    SeqListPushBack(&s, 2);
    SeqListPushBack(&s, 3);
    SeqListPushBack(&s, 4);
    SeqListPushBack(&s, 5);
    SeqListPushBack(&s, 0);
    SeqListPrint(&s);
    
    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 SeqListPushBack(SeqList* psl, SLDataType x)
{
    assert(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;
        }
    }

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


//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 SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);

顺序表尾删：

//Test.c  测试
#include "SeqList.h"

int main()
{
    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);

    
    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 SeqListPushBack(SeqList* psl, SLDataType x)
{
    assert(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;
        }
    }

    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--;
    }
}

//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 SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);

报错问题：

** 解决：**

1.使用断言(assert),对size断言。太过暴力！

2.添加条件判断

越界是一种抽查，不能全部被查出来！

顺序表头插：

//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);
//    //尾删，删除最后两个数据
//    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);
//
//    //如果不小心传了空指针，须使用断言进行报错查找
//    //SeqListPrint(NULL);
//
//    //测试越界
//    //int a[10];
//    a[10] = 1;
//    a[11] = 1;
//    //a[12] = 1;
//    a[100] = 1;
//
//}

void TestSeqList2()
{   //扩容测试
    /*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);
    SeqListPushFront(&s, 0);
    SeqListPushFront(&s, -1);
    SeqListPrint(&s);


}

int main()
{
    SeqList s;
    SeqListInit(&s); //这里&是取地址
    TestSeqList2();
    
    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 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);
    
}

//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);

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//尾删
void SeqListPopBack(SeqList* psl);
//头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//头删
void SeqListPopFront(SeqList* psl);

顺序表头删：

不考虑顺序：

1.断言为假就终止程序！并且在打印时会告知出错的行数！

**2.return结束函数（温和），exit终止程序（暴力终止） **

顺序表在pos(指定位置)插入：

以下几张图片代码有误：

有误部分已标记：

一般情况下，动态开辟的内存，是在free的时候检查越界！

静态开辟的内存是在函数结束时检查越界!

添加Destroy函数，free语句进行越界检查！

注：

**-1（整型int）被提升为无符号整型（unsigned int）为1111111111111111...11（全1） **

--end，-2、-3、依旧会提升，形成死循环！

** 解决方法：**

1.

** 2.**

3.

顺序表在pos(指定位置)删除：

**2.2 ****接口实现 **

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
    SLDataType* array; // 指向动态开辟的数组
    size_t size; // 有效数据个数
    size_t capicity; // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

后记：

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

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

“P2&mdash;＜顺序表＞《数据结构(C语言版)》”的评论:

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

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航