刨析数据结构（一）

typedef int SLDataType
typedef struct SeqList
{
   SLDataType*arr//数据的底层结构
   int capacity;//顺序表的空间大小
   int size;//有效个数
}SL
void SLInit(SL*ps)//顺序表的初始化
void SLDestory(SL*ps)//顺序表的销毁

void SLInit(SL*ps)
{
  PS->arr=NULL;
  PS->size=ps->capcity=0;
}
void SLPrint(SL*ps)
{ 
for (int i=0;i<ps->size;i++)
 {
    printf("%d ",ps->arr[i]);
 }
printf("\n")
}

5.增加元素：

void SLPushBack(SL*ps,SLDataType X)//头插
void SLPushDate(SL*ps,SLDataType X)//尾插
void SLInsert(SL* ps, int pos, SLDataType x);//中间插
void SLCheckCapacity(SL* ps) //扩容

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);
	//空间足够，直接插入
	ps->arr[ps->size++] = x;
}//尾插
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);
void SLPopFront(SL* ps);
void SLErase(SL* ps, int pos);

void SLPopBack(SL* ps) {
	assert(ps);
	assert(ps->size);
	ps->size--; //ps->arr[ps->size - 1] = -1==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* ps, int pos, SLDataType x)

void SLModify(SL* ps1, int pos, SLDataType x)
{
	assert(ps1);
	assert(0 <= pos && pos < ps1->size);
	ps1->arr[pos] = x;
}

8.查找元素

void SLFind(SL* psl, SLDatatype x)

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个数据空间

这种的局限性已经被我们的计算机前辈给解决了，如果你想知道怎么解决，请持续关注😀

🥇🥇🥇 新的专栏：数据结构————"带你无脑刨析"博主正在火速创作中，可以关注博主一下哦！φ(゜▽゜*)♪o(*￣▽￣*)ブ[●´︶｀●]

🎁🎁🎁今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是我前进的动力！

原文地址:https://blog.csdn.net/2301_79712692/article/details/135943091 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1752545756918714368.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部