03.顺序表实现

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删改查。一般见到的顺序表都是在结构体中定义的数组，只是比普通数组多了增删改查等一些其他功能函数。

        上节已经介绍了顺序表有动态顺序表和静态顺序表。动态比静态有很多优点，这节将实现动态顺序表。

一、头文件定义

        1、包含实现动态顺序表所需的头文件。

        2、定义顺序表结构体。

        3、功能函数的声明。

//1、包含头文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//assert()函数的作用：如果()内为假则断言报错终止运行

//2、定义结构体
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;	//指针数组
	int size;		//数据个数
	int capacity;	//容量
}SL;

//3、声明功能函数
//初始化加销毁
void SLInit(SL* ps);
void SLDestory(SL* ps);
//检查空间大小，如果空间小了则申请空间
void SLCheckCapacity(SL* ps);
//尾插和头插
void SLBackPush(SL* ps, SLDataType x);
void SLFrontPush(SL* ps, SLDataType x);
//尾删和头删
void SLBackPop(SL* ps);
void SLFrontPop(SL* ps);
//查找数据下标
int SLFind(SL* ps, SLDataType x);
//指定位置插入/删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//打印顺序表
void SLPrint(SL* ps);

二、功能函数实现

#include "SeqList.h"

//初始化加销毁
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//销毁
void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
//检查空间是否足够
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail\n");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}
//尾插
void SLBackPush(SL* ps, SLDataType x)
{
	assert(ps);		//断言
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//头插
void SLFrontPush(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}
//尾删
void SLBackPop(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}
//头删
void SLFrontPop(SL* ps)
{
	assert(ps);
	assert(ps->size);

	for (int i = 0; i < ps->size-1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
//查找数据下标
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}
//在指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}
//在指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->size--;
	for (int i = pos; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
}
//打印顺序表
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

三、主函数测试

#include "SeqList.h"

int main()
{
	SL sl;
	SLInit(&sl);

	SLFrontPush(&sl, 1);
	SLFrontPush(&sl, 2);
	SLFrontPush(&sl, 3);
	SLFrontPush(&sl, 4);
	SLBackPush(&sl, 0);
	printf("插入的数据：");
	SLPrint(&sl);

	SLFrontPop(&sl);
	SLBackPop(&sl);
	printf("删除头和尾后：");
	SLPrint(&sl);

	printf("在下标1处添加数据9后:");
	SLInsert(&sl, 1, 9);
	SLPrint(&sl);
	int pos = SLFind(&sl, 9);
	printf("查找数据为9的下标：%d\n", pos);
	SLErase(&sl, pos);
	printf("删除下标为1的数据：");
	SLPrint(&sl);
	printf("查找数据为9的下标：%d\n", SLFind(&sl, 9));
	SLDestory(&sl);
	return 0;
}

 分别建立名为SeqList.h的头文件和SeqList.c的源文件，和一个主函数文件。运行上述代码：