【数据结构】新篇章 -- 顺序表

🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分80+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）

数据结构

概念

为什么需要数据结构

使用数据结构的效果

线性表

概念

顺序表与数组的区别

顺序表导图

动态顺序表

typedef定义结构的两种方法

空间不够，扩容

尾部插入数据

头部插入数据

尾部数据删除

头部数据删除

指定位置之前插入数据

删除指定位置数据

查找顺序表中元素位置

销毁

数据结构

概念

数据结构是计算机存储、组织数据的方式

为什么需要数据结构

在这之前我们学过数组，数组是最基础的数据结构

那为什么学了数组还用学数据结构呢？

最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现

使用数据结构的效果

1）能够将数据存储

（顺序表、链表等结构）

2）方便查看存储的数据

线性表

概念

线性表在逻辑上是线性结构，也就是说是连续的一条直线

但在物理结构上并不一定是连续的

线性表在物理上存储时，通常以数组和链式结构的形式存储

常见的线性表：

顺序表、链表、栈、队列、字符串

顺序表与数组的区别

顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

顺序表导图

动态顺序表

SX.h：定义顺序表的结构，顺序要实现的接口/方法

SX.c：具体实现顺序表里定义的接口/方法

test.c：测试顺序表

typedef定义结构的两种方法

//第一种方法//数据类型
typedef int datatype;//结构体
struct shunxu
{datatype* arr; //存储数据的底层结构：数组int size;      //顺序表空间大小int nowsize;   //顺序表有效数据个数
};typedef struct shunxu SX;

//第二种方法//数据类型
typedef int datatype;//结构体
typedef struct shunxu
{datatype* arr; //存储数据的底层结构：数组int size;      //顺序表空间大小int nowsize;   //顺序表有效数据个数
}SX;

以下是在SX.c中实现顺序表

空间不够，扩容

//空间不够，扩容
void publicKUOR(SX* ps)
{//如果顺序表空间大小 = 顺序表空间有效个数if (ps->size == ps->nowsize){//三目操作符int newnowsize = ps->nowsize == 0 ? 4 : 2 * sizeof(datatype);//新建一个临时变量，因为如果realloc扩容失败，会造成技术事故datatype* tmp = (datatype*)realloc(ps->arr, newnowsize * sizeof(datatype));if (tmp == NULL){perror("realloc");exit(1);}//扩容后的数组ps->arr = tmp;//扩容后的有效空间大小ps->nowsize = newnowsize;}
}

尾部插入数据

//顺序表的尾插
void CHARUback(SX* ps, datatype x)
{//方式一：断言 -- 暴力方式 --会报错且知道具体错误位置assert(ps);//方式二：断言 -- 温柔方式--会报错，不知道具体错误位置/*if (ps == NULL){return;}*///空间不够，扩容publicKUOR(ps);//空间足够，直接插入/*第一种写法*///ps->arr[ps->size] = x;//ps->size++;/*第二种写法*/ps->arr[ps->size++] = x;}

头部插入数据

//头插
void CHARUfront(SX* ps, datatype x)
{//判断ps是否为空指针assert(ps);//空间不够，扩容publicKUOR(ps);//空间足够，数据往后挪一位int i = 0;for (i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}

尾部数据删除

//尾部删除
void SXdestroyback(SX* ps)
{//判断ps是否为有效指针assert(ps);//判断顺序表中有无数据assert(ps->size);//顺序表不为空ps->size--;
}

头部数据删除

//头部删除
void SXdestroyfront(SX* ps)
{//判断ps是否为有效指针assert(ps);//判断顺序表是否有数据assert(ps->size);//顺序表不为空，往前挪for (int i = 0; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

指定位置之前插入数据

//指定位置之前插入数据
//顺序表下标位置pos
void SXpointfrontestroy(SX* ps,int pos,datatype x)
{//判断ps是否为有效指针assert(ps);//断言，保证下标pos>=0且pos小于等于顺序表空间大小sizeassert(pos >= 0 && pos <= ps->size);for (int i = ps->size; i < pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

删除指定位置数据

//删除指定位置数据
void SXpointdestroy(SX* ps, int pos)
{//判断ps是否为有效指针assert(ps);//断言，保证下标pos>=0且pos小于顺序表空间大小sizeassert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

查找顺序表中元素位置

//查找顺序表元素位置
int SXfind(SX* ps, datatype x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}

销毁

void SXdestroy(SX* ps)
{//保证指针有效assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->nowsize = 0;
}

***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:

“走过这场雾，就是柏林的冬”。

我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！
好了划走吧。