不定长顺序表

一.不定长顺序表的结构:

typedef struct DSQList{
int* elem;//动态内存的地址
int length;//有效数据的个数
int listsize;//总容量
}DSQList,*DPSQList;

很明显,为了能实现扩容(否则如何实现再次判满呢?),我们必须要在定长顺序表的基础上增加一个总容量;结构示意图如下:

二.不定长顺序表的实现(重点)

//初始化
void InitSqlist(DPSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;

	ps->elem = (int*)malloc(INIT_SIZE * sizeof(int));
	ps->length = 0;
	ps->listsize = INIT_SIZE;
}
static bool IsFull(DPSQList ps)
{
	return ps->length == ps->listsize;
}

static bool Inc(DPSQList ps)
{
	ps->elem = (int*)realloc(ps->elem, ps->listsize * 2 * sizeof(int));
	assert(ps->elem != NULL);
	ps->listsize *= 2;
	//ps->length;
	return true;
}

//插入数据，在ps顺序表的pos位置插入val;
bool Insert(DPSQList ps, int pos, int val)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	if (pos<0 || pos>ps->length)
	{
		return false;
	}
	if (IsFull(ps))
	{
		Inc(ps);
	}
	//把数据往后移
	for (int i = ps->length - 1; i >= pos; i--)
	{
		ps->elem[i + 1] = ps->elem[i];
	}
	//插入新数据
	ps->elem[pos] = val;
	//有效数据个数++
	ps->length++;

	return true;
}

//判空
bool IsEmpty(DPSQList ps)
{
	return ps->length == 0;
}

//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
int Search(DPSQList ps, int key)
{
	for (int i = 0; i < ps->length; i++)
	{
		if (key == ps->elem[i])
			return i;
	}
	return -1;
}

//删除pos位置的值
bool DelPos(DPSQList ps, int pos)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	if (pos < 0 || pos >= ps->length)
	{
		return false;
	}
		//后面的数据前移
	for (int i = pos; i < ps->length - 1; i++)
	{
		ps->elem[i] = ps->elem[i + 1];
	}
}

三.顺序表总结

顺序表的特点：

1.插入数据的时间复杂度是O(n),如果是尾插时间复杂度是O(1);

2.删除数据的时间复杂度是O(n),如果是尾删时间复杂度是O(1);

3.通过下标访问数据时间复杂度是O(1);

顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除操作需要移动大量元素; 存储密度大(高),每个结点只存储数据元素(对比链表);

随机访问:顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以在O(1)时间内找到指定的元素,这就是随机存取的概念;