[数据结构与算法]C语言数据结构（1）——顺序表

1.顺序表基本数据类型

typedef int SLDataType;//将元素类型名统一，方便以后修改

typedef struct SeqList
{
	SLDataType *a;//存放指针，用于于开辟空间
	int size;//表示数组中当前存储了多少个有效数据
	int capacity;//容量
}SL;

将结构体重命名为SL

2.顺序表的初始化

将容量以及当前大小置为0，元素的类型指针置空。

void SeqListInit(SL* ps)
{
	ps->capacity = 0;
	ps->size = 0;
	ps->a = NULL;
}

3.检查容量

检查当前顺序表的容量，如果大小（size）==容量（capacity），意味着顺序表在新增元素前需要扩容。

void SeqListCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(EXIT_FAILURE);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
		printf("增容成功\n");
	}
}

注意：
1.一个好的命名规则，方便日后你对函数的调用与维护；
2.注意这里realloc的运用，realloc返回的指针并不是马上赋值给ps，不然如果realloc失败，那ps将获得的是NULL，而原来分配的空间则再也找不回来，造成内存泄漏。所以先创建临时变量，如果开辟成功，在赋值给ps。

4.尾插元素

在顺序表尾部添加新元素

void SeqListPushBack(SL* ps, int x)//尾插
{
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

注意先检查容量，以及每添加一个元素就使size++。

5.尾删元素

无需删掉元素，size–，下次尾插元素时即可覆盖。

void SeqListPopBack(SL* ps)//尾删
{
	if (ps->size == 0)
	{
		printf("已为空表\n");
	}
	else
	{
		ps->size--;
	}
}

6.头插元素

将新元素添加在顺序表头，每插入一个元素前需要所有元素往后进一格位置空出第一格的空间。（顺序表的劣势）

void SeqListPushFront(SL* ps, int x)//头插
{
	SeqListCheckCapacity(ps);
	//挪动
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

7.头删元素

void SeqListPopFront(SL* ps)//头删
{
	if (ps->size == 0)
	{
		printf("已为空表\n");
	}
	else
	{
		int begin = 1;
		while (begin < ps->size)
		{
			ps->a[begin - 1] = ps->a[begin];
			begin++;
		}
		ps->size--;
	}
}

8.查找元素返回下标

若无元素x则返回-1

int SeqListFind(SL* ps, SLDataType x)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

9.删除指定位置的元素

void SeqListDelete(SL* ps, int pos)//删除指定位置
{
	//判断删除位置在不在
	if (pos < 0 || pos >= ps->size)
	{
		printf("越界\n");
	}
	else
	{
		while (pos < ps->size-1)
		{
			ps->a[pos] = ps->a[pos + 1];
			pos++;
		}
		ps->size--;
		printf("删除成功\n");
	}
}

10.在指定位置插入元素

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	
	if (pos > ps->size || pos < 0)
	{
		printf("pos invalid\n");
		return;
	}

	SeqListCheckCapacity(ps);//检查容量

	// 挪动数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}

	ps->a[pos] = x;
	ps->size++;
}

也可以用这个函数玩头插和尾插只需改变pos即可
头插：

void SeqListPushFront(SL* ps, SLDataType x)
{
	SeqListInsert(ps,0,x);
}

尾插：

void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListInsert(ps,ps->size,x);
}

11.销毁顺序表

全部置0，free空间。

void SeqListDestroy(SL* ps)//销毁
{
	ps->capacity = 0;
	ps->size = 0;
	free(ps->a);
	ps->a = NULL;
}