顺序表专题

///！！！在头文件SeqList.h中
#include<stdio.h>
#include<stdlib.h>
typedef int SLDataType;//数据类型要跟下面结构体定义的类型保持一致
//动态顺序表
struct SepList//修改结构的名字：
	//方法一，可以直接在struct前加上typedef,然后在下面的大括号（分号前）直接加上修改后的名字
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
};//SL;
typedef struct SeqList SeqList;//
SeqList SL;//方法二：修改结构体的名字

//SeqList.c中操作
#include"SeqList.h"
void SLInit(SL* ps)//既然传地址就不能用s来接收，就要用指针来接收
                   //定义一个形参ps来接收顺序表sl的地址，通过指针来接收传参
{
	ps->arr = NULL;//不能用.来解引用，应该用箭头来解引用
	ps->size = ps->capacity = 0;//初始化状态都为0
}

//SeqList.h头文件中操作
#include<stdio.h>
#include<stdlib.h>
typedef int SLDataType;//数据类型要跟下面结构体定义的类型保持一致
//动态顺序表
typedef struct SepList//修改结构的名字：
	//方法一，可以直接在struct前加上typedef,然后在下面的大括号（分号前）直接加上修改后的名字
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

//顺序表初始化
void SLInit(SL* ps);//通过指针来接受传参,头文件中方法的申明也要修改

#include "SeqList.h"
void SLTest01()
{
	SL sl;//创建了一个顺序表要初始化
	SLInit(&sl);//传了一个实参sl，通过SeqList.c中的形参s来接收
}

int main(void)
{
	SLTest01();
	return 0;
}

//头文件SeqList.h
//顺序表的销毁
void SLDestroy(SL* ps);

//SeqList.c源文件
//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);//动态申请的数组空间需要手动释放掉，考虑到后面可能会用到realloc malloc等申请空间，有空间就要销毁掉
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//text.c源文件
#include "SeqList.h"
void SLTest01()
{
	SL sl;
	SLInit(&sl);
	//增删查改操作
	SLDestroy(&sl);
}

//在SeqList.h中
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);//SLDataType是数据类型，往数据表里面插入一个x
void SLPushFront(SL* ps, SLDataType x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//SeqList.c中
//顺序表的尾插
void SLPushBack(SL* ps, SLDataType x)
{
	//温柔的方式
	// if(ps == NULL)
	// {
	//		return;
	// }
	assert(ps);//等价于assert(ps !=NULL)
	//插入数据之前要先看一下空间够不够？
	if (ps->capacity == ps->size)
	{
		//申请空间
		//三目表达式
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//为了确保下面操作ps->capacity不等于0
		SLDataType* tmp= (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间,返回值强转为SLDataType*
		//动态申请空间有可能申请失败，所以上一句代码我们最终赋值的时候赋值给一个临时变量，SLDataType* tmp
		if (tmp == NULL)
		{
			perror("realloc fail!");//申请失败就直接返回perror
			exit(1);//直接退出程序，不在继续执行
		}
		//空间
		ps->arr = tmp;//申请成功的这块空间给arr
		//申请的空间已经变成了newCapacity,空间已经增大了
		ps->capacity = newCapacity;//到这里就申请成功了，现在就可以插入数据
	}
	ps->arr[ps->size++] = x;
}

//SeqList.c中操作
//顺序表的头插并且把结果打印出来
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];//前一位挪动到后一位，arr[1]=arr[0]
	}
	ps->arr[0] = x;
	ps->size++;//插入数据size要++，有效数据个数又增加了
}
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ",s.arr[i]);
	}
	printf("\n");
}

//头部插入删除 / 尾部插入删除
//SeqList.h中操作
void SLPushBack(SL* ps, SLDataType x);//SLDataType是数据类型，往数据表里面插入一个x
void SLPushFront(SL* ps, SLDataType x);

//test.c中操作
#include "SeqList.h"
void SLTest01()
{
	SL sl;
	SLInit(&sl);
	//增删查改操作
	//测试尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	SLPushFront(&sl, 5);
	SLPushFront(&sl, 6);
	SLPrint(sl);//不用取地址，传值打印
	SLDestroy(&sl);
}

int main(void)
{
	SLTest01();
	
	return 0;
}

//尾删
void SLPopBack(SL* ps)
{
	//首先传的地址不可以传空
	assert(ps);
	//其次顺序表里面不能为空，一旦为空就不可以执行删除操作
	assert(ps->size);
	//ps->arr[size-1]=-1;删完一个数据把那个数据对应的位置赋值为-1，表示已经删除了；删完一个数据size--
	//ps->arr[ps->size - 1] = -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];//arr[size-2]=arr[size-1]
	}
	ps->size--;
}