【线性表】之顺序表(C语言)

typedef int SeqListDataType;
typedef struct SeqList
{
	SeqListDataType* arry;//指向动态开辟的数组
	int size;//数组中有效数据的个数(在数组中说就是最后一个数据的下一个位置，因为数组下标是从0开始的)
	int capacity;//容量空间的大小
}SeqList;

void SeqListInit(SeqList* ps)
{
	ps->arry = NULL;//可以一上来就给空间，也可以不给空间
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListDestory(SeqList* ps)
{
	free(ps->arry);
	ps->arry = NULL;
	ps->capacity = ps->size = 0;
}

void SeqListPrint(SeqList* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arry[i]);
	}
}

void SeqListCheckCapacity(SeqList* ps)
{
	//如果数组满了——有效的数据个数等于空间容量的总大小
	if (ps->size == ps->capacity)
	{
		//要注意如果满了，就进行扩容，在原来基础上*2，但是开始的空间是0，
		//0*2还是0,所以开始插入的时候要加一个判断
		//如果开始的空间是0，那么就给他赋值4，之后就不是0了，就给他*2
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//realloc扩充原来开辟好的空间
		//如果原来的空间在原来的地方是空，那就他是直接申请一个新的空间就跟malloc是一样的。
		SeqListDataType* tmp = (SeqListDataType*)realloc(ps->arry, newCapacity * sizeof(SeqListDataType));
		//如果扩容失败，给予提示
		if (tmp == NULL)
		{
			printf("realloc is fail!");
			exit(-1);//退出
		}
		else
		{
			//把扩充好的数组传给arry
			ps->arry = tmp;
			ps->capacity = newCapacity;//空间容量大小
		}
	}
}

void SeqListPushBack(SeqList* ps,SeqListDataType x)
{
	SeqListCheckCapacity(ps);
    //顺序表中的数据要依次存储
	ps->arry[ps->size] = x;
	ps->size++;
}

void SeqListPushFront(SeqList* ps, SeqListDataType x)
{
	//同尾插-空间不够了需要增容
	SeqListCheckCapacity(ps);
	//从后开始挪
	//注意初识条件-结束条件-迭代过程
	//先找到最后一个位置
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arry[end + 1] = ps->arry[end];
		end--;
	}
	ps->arry[0] = x;
	ps->size++;
}

void SeqListPopBack(SeqList* ps)
{
	assert(ps->size > 0);//等于0直接报错，比较粗暴。
	//下面这行代码没用，因为了顺序表中具体的数据个数是由size决定的
	//把这个位置置 成0，万一这个位置本来就是0呢，或者这个位置的数据类型不是int，是double呢，置成0也不合适，没有意义。
	//ps->arry[ps->size - 1] = 0;
	ps->size--;
	//可以复用删除,头删、头插、尾插、同理
	//SeqListErase(ps,ps->size);
}

void SeqListPopFront(SeqList* ps)
{
	//检查一下还有没有元素，没有就别删了
	assert(ps->size > 0);
	int start = 1;
	//就是用后面的元素将前面的元素给覆盖了，每次消失的都是第一个，其他的依次向前推
	while (start < ps->size)
	{
		ps->arry[start - 1] = ps->arry[start];
		start++;
	}
	ps->size--;
}

void SeqListInsert(SeqList* ps, int pos, SeqListDataType x)
{
	assert(pos < ps->size);//大于就报错
	//思路：先创建空间，利用循环找到pos这个位置，将元素放入数组，size+1
	//创建空间
	SeqListCheckCapacity(ps);
	//找到最后一个元素
	int end = ps->size - 1;
	while (end >= pos)
	{
		//依次往后推移一位，
		ps->arry[end + 1] = ps->arry[end];
		end--;
	}
	ps->arry[pos] = x;
	ps->capacity++;
}

void SeqListErase(SeqList* ps, int pos)
{
	assert(pos < ps->size);
	//被删除元素后面的位置
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->arry[start - 1] = ps->arry[start];
		start++;
	}
	ps->size--;
}

int SeqListFind(SeqList* ps, SeqListDataType x)
{
    //找到返回下标，找不到返回-1
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arry[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListModity(SeqList* ps, int pos, SeqListDataType x)
{
	assert(pos < ps->size);
	ps->arry[pos] = x;
}