文章目录
前言
上篇博客入门了数据结构，学习了时间复杂度和空间复杂度，本篇博客学习线性表中的顺序表。
线性表是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
一、顺序表
1.1 概念与结构
概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。
顺序表和数组的区别？
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接口。
就像下面示例一样，每一个东西都经过精心包装。
1.2分类
1.2.1 静态顺序表
概念：使用指定长度的数组储存元素
typedef int SLDataType;
#define N 7
typedef struct SeqList
{
SLDataType a[N]; //指定长度
int size; // 有效数据个数
};
缺陷：空间给少了不够用，给多了浪费
1.2.2 动态顺序表
按需申请空间
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int capacity; // 有效数据个数
int size; // 空间容量
};
1.3 动态顺序表的实现
使用动态顺序表做到对数据的增删改查等功能。
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int capacity;
int size;
}SL;
void SLInit(SL* ps); // 初始化
void SLDestory(SL* ps); // 销毁
void SLCheckCapacity(SL* ps);// 扩容
void SLPushBack(SL* ps, SLDataType x); // 尾插
void SLPopBack(SL* ps); // 尾删
void SLPushFront(SL* ps, SLDataType x); // 头插
void SLPopFront(SL* ps); // 头删
void SLPrint(SL* ps); // 打印
int SLFind(SL* ps, SLDataType x);// 查找数据
void SLInsert(SL* ps, int pos, SLDataType x); // 指定位置插入
void SLErase(SL* ps, int pos); // 指定位置删除
顺序表的初始化与销毁
void SLInit(SL* ps) // 初始化
{
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void SLDestory(SL* ps) // 销毁
{
assert(ps);
if (ps->a)
{
free(ps->a);
}
ps->a = NULL;
ps->capacity = ps->size = 0;
}
在数据的插入过程中，可能有空间不够的情况
这里是顺序表的扩容，每次扩容到原来的两倍
void SLCheckCapacity(SL* ps) // 判断容量 扩容
{
if (ps->capacity == ps->size)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newCapacity);
ps->a = tmp; // 在原来的空间上扩展两倍
ps->capacity = newCapacity;
}
}
顺序表的插入和删除
void SLPushBack(SL* ps, SLDataType x) // 尾插入
{
assert(ps);
SLCheckCapacity(ps);
ps->a[ps->size++] = x;
}
void SLPopBack(SL* ps) // 尾删除
{
assert(ps);
ps->size--;
}
void SLPushFront(SL* ps, SLDataType x) // 头插
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i > 0; i--)
{
ps->a[i] = ps->a[i - 1];
}
ps->a[0] = x;
ps->size++;
}
void SLPopFront(SL* ps) // 头删
{
assert(ps);
for (int i = 0; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
顺序表的查找与指定位置插入删除
int SLFind(SL* ps, SLDataType x)// 查找数据
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return ps->a[i];
}
}
return -1;
}
void SLInsert(SL* ps, int pos, SLDataType x) // 指定位置插入
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
{
ps->a[i] = ps->a[i - 1];
}
ps->a[pos] = x;
ps->size++;
}
void SLErase(SL* ps, int pos) // 指定位置删除
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
顺序表的打印，便与观察代码执行后是否与预想一样
void SLPrint(SL* ps) // 打印
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
cout << ps->a[i] << ' ';
}
cout << endl;
}
总结
今天学习了线性表中的顺序表，并且模拟实现了动态顺序表，对顺序表有了更深刻的理解。
敲的每一行代码,都是迈向更美好的一步。
