目录

需要实现的接口

顺序表（Sequence List）定义

顺序表的初始化

顺序表查找

顺序表的插入

顺序表删除

顺序表的修改

顺序表打印

顺序表销毁

总结分析

需要实现的接口

• 顺序表的初始化
• 顺序表查找
• 顺序表插入
• 顺序表删除
• 顺序表修改
• 顺序表打印
• 顺序表销毁

//顺序表的初始化
void SeqListInit(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, int pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, int pos);
// 顺序表修改pos位置的值
void SeqListModify(SeqList* psl, int pos, SLDataType x);
// 顺序表打印
void SeqListPrint(SeqList* psl);
// 顺序表销毁
void SeqListDestory(SeqList* psl);

顺序表（Sequence List）定义

typedef int SLDataType;  //元素的数据类型，有利于后续修改储存的数据类型

typedef struct SeqList
{
	SLDataType* array;  //指向动态开辟数组
	int size;         //储存有效数据的个数
	int capicity;     //容量大小
}SeqList;

顺序表的初始化

//顺序表的初始化
void SeqListInit(SeqList* psl) //需要改变结构体内的值，需要传指针
{
	assert(psl);
	psl->array = NULL;  
	psl->capacity = psl->size = 0;
}

•  修改结构体内的值传地址，不能传值，后面都是如此

顺序表查找

// 顺序表查找(找不到返回-1)
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl && psl->size != 0);

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
			return i;
	}

	return -1;
}

顺序表的插入

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	// 检查空间，如果满了，进行增容
	if (psl->size == psl->capacity) //判断空间是否满了
	{
		int newCapicity = psl->capacity == 0 ? 4 : psl->capacity * 2; //空间为0扩为1，满了空间翻倍
		SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * newCapicity);
		if (tmp == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}

		psl->capacity = newCapicity;
		psl->array = tmp;
	}
	
	//挪动数据
	int end = psl->size - 1;//指向顺序表最后一个元素
	while (pos <= end)   //将pos及之后的数据向后移动
	{
		psl->array[end + 1] = psl->array[end];
		end--;
	}

	psl->array[pos] = x;
	psl->size++; 
}

• pos不能小于0，大于size（最后一个数据位置）
• 判断储存数据是否超出容量，进行扩容
• 当pos为末尾，不进入while循环，直接在pos插入数据
• 时间复杂度O(n)

顺序表删除

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, int pos)
{
	assert(psl && psl->size != 0);
	assert(pos >= 0 && pos <= psl->size);

	int begin = pos + 1;
	while (begin < psl->size) //pos后面的数据向前移动，覆盖pos
	{
		psl->array[begin - 1] = psl->array[begin];
		begin++;
	}

	psl->size--;
}

• pos不能小于0，大于size（最后一个数据位置）
• 当pos为末尾，不进入while循环，size--删除末尾数字
• 时间复杂度O(n)

顺序表的修改

// 顺序表修改pos位置的值
void SeqListModify(SeqList* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);

	psl->array[pos] = x;
}

• 通常配合查找，找出须修改数据的下标，然后修改 

顺序表打印

// 顺序表打印
void SeqListPrint(SeqList* psl)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf("n");
}

顺序表销毁

// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);

	free(psl->array);
	free(psl);
}

总结分析

    动态顺序表储存空间物理上一定连续，支持随机访问，删除和插入可能需要搬移元素，效率低O(n)，空间不足时需要扩容，一般需元素高效储存和频繁访问时使用，缓存利用率高。