数据结构——顺序表

//静态顺序表
#define N 7 //给定数组的大小
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType arr[N]; // 定长数组
    int size;//有效数据个数
}SL;

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

typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* arr;//
	int size;//有效数据个数
	int capacity;//容量大小
}SL;

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

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

//打印
void SLPrint(SL* ps);

//扩容
SLCheckCapacity(SL* ps);

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

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

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

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

//查找
int SLFind(SL* ps, SLDatatype x);

//在指定位置前插入数据
void SLInsert(SL* ps, int pos,SLDatatype x);

//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLDatatype x);

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

//修改指定位置数据
void SLModify(SL* ps, int pos,SLDatatype x);

#include"SeqList.h"

//初始化
//初始化是要采用传址调用，而不能采用传值调用
//因为传值调用传的是sl的地址，函数内部通过修改指针可以直接修改原始变量
void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}
//err示例,传值调用
//因为传值调用，函数接收的是sl变量的一份临时拷贝（副本）
//在SLInit函数中修改的是形参ps的成员，而非test01()中定义的结构体变量sl
//函数执行完毕后，ps会被销毁，而sl的成员值仍未被初始化
//void SLInit(SL ps)
//{
//	ps.arr = NULL;
//	ps.size = ps.capacity = 0;
//}

//打印
void SLPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//销毁
void SLDestory(SL* ps)
{
	//申请的空间要释放掉
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//扩容
SLCheckCapacity(SL* ps)
{
	//判断空间是否充足
	if (ps->size == ps->capacity)
	{
		//扩容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDatatype* tmp = realloc(ps->arr, newcapacity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("malloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLDatatype x)
{
	SLCheckCapacity(ps);
	//空间充足
	ps->arr[ps->size] = x;
	ps->size++;//插入后，有效数据个数+1，size向后移动一位
}

//头插
void SLPushFront(SL* ps, SLDatatype x)
{
	//判断空间是否充足
	SLCheckCapacity(ps);
	//数据整体向后挪动一次
	for (int i=ps->size;i>0;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;//插入后，有效数据个数+1，size向后移动一位
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);
	//ps和ps->size都不能为空，因为不能传空指针，所以ps不能为空
	//数据表不能为空才能删除数据，所以size不能为空
	ps->size--;
	//不能free，因为free是释放一块连续的空间，如果free，整个数组都会被释放
	//数据表中有多少个有效数据取决于size，而不是实际有几个数，所以size-1就可以了
	//size向前移动一位，尾部的那个数据虽然仍然存在，但是我们就可以把它当成是一个随机值，比如，当我们调试的时候，除了我们插入的数据，其他位置都是随机值
}

//头删
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--;
}

//查找
//在顺序表中查找该数据，并返回下标
//这样如果想要在指定的数据后插入数据时，就不用自己去找这个数据所处的下标，而是调用该函数即可
int SLFind(SL* ps, SLDatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到了
			return i;
		}
	}
	//未找到
	return -1;
}

//在指定位置前插入数据
void SLInsert(SL* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//空间不足
	SLCheckCapacity(ps);
	//空间足够
	//pos及以后的数据向后移动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//空间不足
	SLCheckCapacity(ps);
	for (int i = ps->size; i-1 > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos + 1] = x;
	ps->size++;
}

//删除指定位置数据
void SLErase(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 SLModify(SL* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->arr[pos] = x;
}