脚本宝典收集整理的这篇文章主要介绍了【数据结构(C语言描述)】线性表之顺序表,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
线性表(linear list):是n个具有相同特性的数据元素的有限序列。 常见的线性表:顺序表、链表、栈、队列、字符串…
🔵特点: 逻辑上:线性结构 物理上:不一定是连续(一般以数组和链式结构的形式存储)
顺序表:是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储
顺序表可以分为两种:
动态顺序表是静态顺序表的升级版,这里我们的接口实现考虑动态顺序表:
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
SLDataType* array; // 指向动态开辟的数组
size_t size; // 有效数据个数
size_t capicity; // 容量空间的大小
}SeqList;
// 顺序表初始化
void SeqListInit(SeqList* psl)
{
psl =NULL;
psl->capicity = 0;
psl->size = 0;
}
// 检查空间,如果满了,进行增容
void CheckCapacity(SeqList* psl)
{
//新增的空间大小
//考虑两种情况:①啥也没②有东西但满
int newcapacity = psl->capicity == 0 ? 4 : psl->capicity * 2;//*2是为了避免不断开辟空间
//新空间的指针
SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * newcapacity);
if (tmp == NULL)
{
printf("failn");
exit(-1);
}
//新空间指针给旧空间,原始数据迁移旧空间销毁
psl->array = tmp;
//容量变成新的数值
psl->capicity = newcapacity;
}
// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
free(psl->array);
psl->array = NULL;
psl->size = psl->capicity = 0;
}
// 顺序表打印
void SeqListPrint(SeqList* psl)
{
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->array[i]);
}
}
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
if (psl->capicity == psl->size)
{
CheckCapacity(psl);
}
psl->array[psl->size] = x;
psl->size++;
}
// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
if (psl->size == 0)
{
printf("empty!fail!n");
exit(-1);
}
//暴力点
//assert(ps->size>0);
psl->array[psl->size-1] = 0;//这条只是初始化数据实际没啥用可以屏蔽
//|0 1 2 3 4 5|
//size=6,要删除最后一个数据需要-1
psl->size--;
}
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
if (psl->size == psl->capicity)
{
CheckCapacity(psl);
}
for (int i = psl->size; i > 0; i--)
{
psl->array[i] = psl->array[i - 1];
}
psl->array[0] = x;
psl->size++;
}
// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
if (psl->size == 0)
{
printf("empty!fail!");
exit(-1);
}
//直接覆盖前一个数据
for (int i = 1; i < psl->size - 1; i++)
{
psl->array[i - 1] = psl->array[i];
}
psl->size--;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
if (psl->size == psl->capicity)
{
CheckCapacity(psl);
}
for (int i = psl->size; i > pos-1; i--)
{
psl->array[i] = psl->array[i - 1];
}
psl->array[pos-1] = x;
psl->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
//pos的值有误
if (pos<-1 || (pos-1)>(psl->size - 1))
{
printf("fail!");
exit(-1);
}
//表是空的
if (psl->size == 0)
{
printf("empty!fail!");
exit(-1);
}
for (int i = pos - 1; i < psl->size - 2; i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->size--;
}
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{
for (int i = 0; i < psl->size - 1; i++)
{
if (x == psl->array[i])
return i;
}
return -1;
}
以上是脚本宝典为你收集整理的【数据结构(C语言描述)】线性表之顺序表全部内容,希望文章能够帮你解决【数据结构(C语言描述)】线性表之顺序表所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。