数据结构——复杂度和顺序表

code-child

发布于 2023-05-30 11:16:34

1300

发布于 2023-05-30 11:16:34

文章被收录于专栏：codechild

在用代码实现算法前的时候就已经估算出时间复杂度和空间复杂度了

时间复杂度

只讲解如何计算在计算时间复杂度的时候，只考虑程序或者算法中关键部分的大概运行次数。我们用大O表示法。

大O表示法 1.只保留高次项(增长速率最快的)并且高次项的系数改成1 2.所有常数项均为1 3.可以含有多个未知元，如：O(m+n) 4.最好运行次数与最差运行次数的平均次数。（一般只关注最差的情况）

log n其实是以2为底的对数，以其他为低的数都要写出来，比如log₃n

空间复杂度

完成某一个算法需要额外开辟的空间，也是用大O表示法。其求法和时间复杂度的求法类似。注意：递归使用的栈空间也属于额外的空间开销

顺序表

内存中开辟连续的储存单元存储数据用以实现增删查改。

创建

ctypedef int SLDataType;
//顺序表中数据的类型
typedef struct seqlist
{
	SLDataType* arr;//用于动态开辟数组
	int size;//有效个数
	int capacity;//空间
}SeqList;

初始化

cvoid SeqListInit(SeqList* psql)
{
	psql->arr = NULL;
	psql->size = 0;
	psql->capacity = 0;
}

销毁

cvoid SeqListDestroy(SeqList* psql)
{
	assert(psql);
	free(psql->arr);
	psql->arr = NULL;
	psql->capacity = psql->size = 0;
}

检查容量是否已满

如果满了，就进行扩容

cvoid CheckCapacity(SeqList* psql)
{
	if (psql->size == psql->capacity)
	{
		psql->capacity += 10;
		SLDataType* temp = (SLDataType*)realloc(psql->arr, psql->capacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			printf("扩容%s\n", strerror(errno));
			exit(-1);
		}
		psql->arr = temp;
	}
}

尾插

cvoid SeqListPushBack(SeqList* psql, SLDataType x)
{
	CheckCapacity(psql);
	psql->arr[psql->size] = x;
	psql->size++;
}

尾删

注意没有有效数的时候，即psql->size等于0的时候

cvoid SeqListPopBack(SeqList* psql)
{
	assert(psql);
	assert(psql->size);
	psql->size--;
}

头插

cvoid SeqListPushFront(SeqList* psql, SLDataType x)
{
	CheckCapacity(psql);
	int i = 0;
	for (i = psql->size; i > 0; i--)
	{
		psql->arr[i] = psql->arr[i - 1];
	}
	psql->arr[i] = x;
	psql->size++;
}

头删

注意没有有效数的时候，即psql->size等于0的时候

cvoid SeqListPopFront(SeqList* psql)
{
	assert(psql);
	assert(psql->size);
	int i = 0;
	while (i < psql->size-1)
	{
		psql->arr[i] = psql->arr[i + 1];
		i++;
	}
	psql->size--;
}

打印

cvoid SeqListPrint(SeqList* psql)
{
	int i = 0;
	for (i = 0; i < psql->size; i++)
	{
		printf("%d ", psql->arr[i]);
	}
	printf("\n");
}

任意一个位置插入

cvoid SeqListInsert(SeqList* psql, int Pos, SLDataType x)
{
	assert(psql);
	assert(Pos >= 0 && Pos <= psql->size);
	CheckCapacity(psql);
	int i = psql->size-1;
	while (i>=Pos)
	{
		psql->arr[i + 1] = psql->arr[i];
		i--;
	}
	psql->arr[Pos] = x;
	psql->size++;
}

任意位置删除

cvoid SeqListErase(SeqList* psql, int Pos)
{
	assert(psql);
	assert(Pos >= 0 && Pos < psql->size);
	int i = Pos;
	while (i<psql->size-1)
	{
		psql->arr[i] = psql->arr[i + 1];
		i++;
	}
	psql->size--;
}

查找

找到返回下标，找不到返回-1。

cint SeqListFind(SeqList* psql, SLDataType x)
{
	assert(psql);
	int pos = 0;
	while (pos < psql->size)
	{
		if (psql->arr[pos] == x)
			return pos;
		pos++;
	}
	return -1;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构