线性表之顺序表

typedef int SLDatatype;

#define N 9

typedef struct SeqList
{
	SLDatatype a[N];	//定长数组
	int size;			//有效数据个数
}SL;

typedef int SLDatatype;

typedef struct SeqList
{
	SLDatatype* a;
	int size;		//有效数据个数
	int capacity;	//空间容量
}SL;

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

//typedef struct SeqList SL;

//初始化
void SLInit(SL* ps);

//尾插
void SLPushBack(SL* ps, SLDataType x);

//头插
void SLPushFront(SL* ps, SLDataType x);

//尾删
void SLPopBack(SL* ps);

//头删
void SLPopFront(SL* ps); 

//查找数据找到了返回下标，找不到返回小于0的数
void SLFind(SL* ps, SLDataType x);

//指定位置之前插入数据
void SLErase(SL* ps, int pos, SLDataType x);

//指定位删除数据
void SLInsert(SL* ps, int pos);

//销毁
void SLDesTroy(SL* ps);

//打印
void SLPrint(SL s);

////判断空间是否满了【扩容】
void SLCheckCapacity(SL* ps);

#include "SeqList.h"

//初始化这里我们要考虑的是我们传参时是传参还是传址因为我们要对顺序表中的变量值进行改变所以我们这里用传址
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}


//判断空间是否满了【扩容】因为不管是什么有关插入的操作都要判断空间是否满了
// 所以我们把它用于一个函数包装方便后续调用
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//判断空间是否满了的条件即当顺序表中的有效数据个数==总的数据个数
		                        //但是我们这里要注意一种情况（当顺序表中的有效数据个数==总的数据个数==0时所带来的问题）
	{
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//保证变量的个数！=0
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		//这里我们需要注意几个问题
		//1用realloc扩容时第二个参数的单位是字节所以我们要用变量的个数与变量的空间大小乘积用于空间的扩容且要保证变量的个数！=0
		//2用realloc扩容时可能失败所以后续我们要检查是否扩容成功
		//3扩容的倍数扩:若每次增加的空间较小，可能导致频繁扩容，效率低下
		              //若每次开辟的空间较大，可能存在空间浪费-- > 扩容一般成倍数增加内存[一般成2倍]
		if (tmp == NULL)//检验是否扩容成功
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//这里我们防止顺序表是空的所以我们运用断言
	//判断空间是否满了
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
	
}

//头插
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];
	}
	ps->arr[0] = x;
	++ps->size;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);//这里顺序表不能为空所以我们要判断有效数据个数是否为0保证有数据可删
	--ps->size;
	/*
	不需要给ps->arr[size - 1]修改值
	ps->size--后，ps->arr[size - 1]的值并不会影响其他操作
	*/
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}

//查找 
// 找到了，返回下标没找到，返回 - 1
void SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

//指定位置之前插入数据
void SLErase(SL* ps, int pos, SLDataType x)
{
	/*
	pos可以直接输入值，也可以为SLFind的返回值
	0 <= pos < size所以我们后面要判断pos的范围
	*/
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	++ps->size;
}

//指定位置删除数据
void SLInsert(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}

//打印
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
}

//销毁（原因记住有借不还再借就难有借有还再借就不难）
void SLDesTroy(SL* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
	
}