数据结构：概述和顺序表
🌈个人主页：Rookie Maker 🔥 系列专栏：数据结构 🏆🏆关注博主，随时获取更多关于IT的优质内容！🏆🏆
😀欢迎来到我的代码世界~ 😁 喜欢的小伙伴记得一键三连哦 ૮(˶ᵔ ᵕ ᵔ˶)ა
文章目录
一.数据结构是啥？
二.常见的数据结构
三.数据结构三要素
1.逻辑结构:
2.物理结构:
3.数据运算：
四.数据结构基本概念
1.数据：
2.数据元素
3.数据对象
4.数据结构
4.数据类型
5.抽象数据类型
6.逻辑结构
7.物理结构（存储结构）
8.算法
五.线性表
六.顺序表
1.顺序表的定义
2.顺序表的分类
1.静态顺序表
2.动态顺序表
3.创建文件
4.初始化
5.增加元素：
6.删除元素
7.修改元素
8.查找元素
七.顺序表的局限性
一.数据结构是啥？
🌏数据结构是由“数据”和“结构”两词组合而来。
🔥1，2，3，4（数据）按照一定规律组织在一起（结构）
👨🚀数据结构是计算机存储、组织数据的方式
🌏数据结构+算法=程序
二.常见的数据结构
- 数组
- 链表
- 栈
- 队列
- 树
- 队
- 散列表
- 图
三.数据结构三要素
1.逻辑结构:
由数据元素之间的逻辑关系构成
2.物理结构:
由数据元素之间的逻辑关系构成
3.数据运算：
施加在数据上的运算包括运算的定义和实现。
四.数据结构基本概念
1.数据：
数据是能描述客观事物的数值，字符以及能输入机器且能被处理的各种符号集合
2.数据元素
组成数据结构的基本单位
3.数据对象
性质相同的数据元素的的集合，是数据的一个子集
4.数据结构
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
4.数据类型
数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称
数据类型其实包含了数据结构，注意“一个值的集合”，这个值可以是原子类型的值集和结构类型的值集，而结构类型的值集就是数据结构。这里的数据结构指的是它的定义而不是它的实现。
按值来分————————原子类型（不可再分） 结构类型（可以再分）
5.抽象数据类型
抽象数据类型（Abstract Date Type，简称 ADT）：指从问题中抽象出来的一个数据模型以及定 义在此数据模型上的一组操作，不考虑计算机的具体存储结构与运算的具体实现算法。
6.逻辑结构
DS = ( D, S ) 【Data Structure】 D：数据集合 R:关系集合
根据数据元素之间关系的不同特征，通常有下列4类基本结构，复杂程度依次递进。
①集合：结构中的数据元素之间除了同属于一个集合外，没有其他的关系。
②线性结构：线性结构中的数据元素之间是一对一的关系。
③树形结构：树形结构中的数据元素之间是一对多的关系。
④图状结构或网状结构：结构中的元素之间是多对多的关系。
7.物理结构（存储结构）
逻辑结构在计算机的存储映象
数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。对应的两种不同的存储结构分别是顺序存储结构和链式存储结构‘
划分：
根据逻辑结构分为：
- 线性和非线性
- 集合/线性/树形/图状
根据存储结构分为：
- 顺序存储结构
- 链式存储结构
- 索引存储结构
- 散列存储结构
8.算法
对特定问题求解步骤的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作
特性：有限性 确定性 可行性 输入 输出
评价算法性能：算法执行时间与占用存储的空间
算法复杂度，大方面来看分为时间复杂度和空间复杂度
空间复杂度（规模有无关系）
五.线性表
线性表（List）：零个或多个数据元素的有限序列。
👍我们想从最简单的开始：顺序表
🥇🥇🥇正片开始喽
六.顺序表
1.顺序表的定义
类比：数组是顺序表的封装
2.顺序表的分类
静态顺序表.动态顺序表
1.静态顺序表
typedef int SLDataType
#define N 66
typedef struct SeqList
{
SLDataType a[N];//数组长度
int size;//数量
}SL；2.动态顺序表
typedef int SLDataType
typedef struct SeqList
{
SLDataType*a;
int size;
int capcity;
}SL;3.创建文件
- SeqList.h ：数据的各种准备，接口的各种准备
- SeqList.c ： 函数如何实现
- test.c：测试操作是否成功
4.创建
typedef int SLDataType
typedef struct SeqList
{
SLDataType*arr//数据的底层结构
int capacity;//顺序表的空间大小
int size;//有效个数
}SL5.初始化：
void SLInit(SL*PS)
{
PS->arr=NULL;//定义为空
PS->size=ps->capcity=0;//数量和容量为空
}5.增加元素：
//检测是否需要扩容
void SLCheckCapacity(SL* ps) {
if (ps->size == ps->capacity) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL) {
perror("realloc fail!");
exit(1);
}
//扩容成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//空间不够，扩容
SLCheckCapacity(ps);
}
//尾插
void SLPushBack(SL* ps, SLDataType x) {
assert(ps);
SLCheckCapacity(ps);
ps->arr[size]=x;
ps->size++;
}
//头插
void SLPushFront(SL* ps, SLDataType x) {
assert(ps);
//判断是否扩容
SLCheckCapacity(ps);
//旧数据往后挪动一位
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
void SLInsert(SL* ps, int pos, SLDataType x) {
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
//pos及之后的数据往后挪动一位，pos空出来
for (int i = ps->size; i > pos;i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}任意位置插6.删除元素
/尾删
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
ps->size--;
}
//头删
void SLPopFront(SL* ps) {
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//指定位置删除
void SLErase(SL* ps, int pos) {
assert(ps);
assert(pos >= 0 && pos < ps->size);
//pos以后的数据往前挪动一位
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}7.修改元素
void SLModify(SL* ps1, int pos, SLDataType x)
{
assert(ps1);
assert(0 <= pos && pos < ps1->size);//在数组内
ps1->arr[pos] = x;
}8.查找元素
void SLFind(SL* ps, SLDatatype x)
{
assert(ps);//断言是否为空
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}七.顺序表的局限性
1.中间/头部的插⼊删除，时间复杂度为O(N)
2.增容需要申请新空间，拷⻉数据，释放旧空间。会有不小的消耗 3.增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插⼊了5个数据，后⾯没有数据插入了，那么就浪费了95个数据空间
这种的局限性已经被我们的计算机前辈给解决了，如果你想知道怎么解决，请持续关注😀
🎁🎁🎁今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是我前进的动力！
