【通讯录项目 （2 / 3）】基于顺序表的通讯录实现——顺序表功能实现

基于顺序表的通讯录实现——顺序表功能实现

1 初始化与销毁

这里我们用“ SLDataType”来代替传统的int char等关键字，这样以后，就可以避免在修改变量类型的时候，进入"地狱模式"。

1.1 初始化

void SLInit(SL* ps)
{
	assert(ps);//断言检测是否为空指针
	ps->a = NULL;//初始化
	ps->size = ps->capacity = 0;//初始化
}

注意这里我们使用的是“传址操作”，这样可以在原有基础上修改数据信息。

1.2 销毁

void SLDestroy(SL* ps)
{
	assert(ps);//断言检测是否为空指针
	free(ps->a);//释放顺序表数据空间
	ps->size = ps->capacity = 0;//销毁归零
	ps->a = NULL;//避免“野指针”
}

注意这里我们使用的是“传址操作”，这样可以在原有基础上修改数据信息。

初始化和销毁的操作比较简单，不在做详细阐释。观察代码即可。

2 头部插入与删除

2.1 头部插入

void SLPushFront(SL* ps, SLDataType x)
 {
	assert(ps);//断言检测是否为空指针
	//判断空间是否足够,不够则扩容
	SLCheckCapacity(ps);
	//空间足够，历史数据后移一位
	for (size_t i = ps->size; i > 0; i--){
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}

这里我们插入的时候需要考虑空间是否足够
于是我们单独分装一个函数进行容量判断

2.1.1检查容量

void SLCheckCapacity(SL* ps)
{

	if (ps->size == ps->capacity){
		//三目操作符，为零设为 4，反之为原来空间的2倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//开辟空间
		SLDataType* tmp = (SLDataType*)realloc(ps->a,newcapacity*sizeof(SLDataType));
		//检查开辟是否成功
		if (tmp == NULL){
			perror("realloc fail!");
			return;
		}
		ps->a = tmp;//转移新空间
		ps->capacity = newcapacity;//设置新容量                                           
	}
}

我们一行一行的解读
1 首先判断原顺序表是否为空，如果为空则设置为四个容量，反之为原来二倍
倍数原则上可以设置为任意大小，这里之所以设置为二倍，是因为这样利用率最高
2 然后开辟空间
我们重温一下realloc函数

注意“size”代表新的空间大小，而不是需要增加的空间大小
开辟完空间即可进行对顺序表的扩容

2.1.2 插入数据

头部插入只需在检查容量之后，依次移动顺序表数据即可，再将数据插入到头部即可，类似数组操作。
插入完成之后不要忘记将 size 加 1

2.2 头部删除

void SLPopFront(SL* ps)
{
	assert(ps);//断言检测是否为空指针
	assert(!SLIsEmpty(ps));//断言检测指针指向是否为空数据。
	for (int i = 0; i < ps->size - 1 ; i++)
	{
		ps->a[i] = ps->a[i + 1]; // a[size-2]=a[size-1] （模拟最后一次操作）
	}
	ps->size--;
}

头部删除非常简单，将顺序表中的数据从第二个依次向前覆盖即可。

2.2.1 检测数据是否为空

bool SLIsEmpty(SL* ps) {
	assert(ps);
	//这样子是不对的，这里只能判断空间是否足够
	//return ps->size == ps->capacity;
	return ps->size == 0;
}

使用断言即可，切记不要用“ps->size == ps->capacity”这样只能判断空间是否足够

3 尾部插入与删除

尾部操作相对于头部更加简单

3.1 尾部插入

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//断言检测是否为空指针
	SLCheckCapacity(ps);//判断空间是否足够,不够则扩容
	ps->a[ps->size++] = x;
}

检查空间之后，进行赋值即可。

3.2 尾部删除

void SLPopBack(SL* ps)
{
	assert(ps);//断言检测是否为空指针
	assert(!SLIsEmpty(ps));//断言检测指向是否为空数据。
	ps->size--;
}

在断言并检测数据之后，将size减1即可，这里不需要将删除的数据进行处理，避免出现数据类型的不符合。

4 指定位置插入与删除

指定位置的插入与删除需要一步“查找”目标数据操作，才可以进行精准操作。
当然也可以不进行“操作”，直接对位置进行修改。

4.1 指定位置插入

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);//断言检测是否为空指针
	SLCheckCapacity(ps);//判断空间是否足够,不够则扩容
	if (pos >= 0 && pos < ps->size)//防止越界操作
	{
		for (int i = ps->size; i > pos; i--)
		{
			ps->a[i] = ps->a[i - 1];//a[pos+1]=a[pos]
		}
		ps->a[pos] = x;
		ps->size++;
	}
	else
		assert(pos);//越界进行停止
}

pos是要修改的位置，再检测容量和检测pos是在合理范围内之后，即可进行移动插入操作。
如果要精准插入到一个数据之前则需要对pos进行操作。

4.1.1 查找数据

    pos = SLFind(SL, 5)//举例 “5”
//函数内部
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);//断言检测是否为空指针
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;//找到返回偏移量 i 
		else
			continue;
	}
	return -1;//没找到
}

这样便可以进行准确插入。

4.2 指定位置删除

void SLErase(SL*ps,int pos)
{                                                                                          
	assert(ps);//断言检测是否为空指针
	if (pos >= 0 && pos < ps->size)
	{
		for (int i = pos; i < ps->size - 1; i++)
		{
			ps->a[i] = ps->a[i + 1];  //a[size-2]=a[size-1]（模拟最后一次操作）
		}
		ps->size--;
	}
	else
		assert(pos);
}

删除较为简单，对pos位置进行覆盖操作即可。注意size减1。

5 打印顺序表

打印操作十分简单，与打印数组类似。

5.1 打印顺序表

void SLPrint(SL* ps)
{
	assert(ps);//断言检测是否为空指针
	int i = 0;
	//依次打印数据即可
	for (i = 0; i < ps->size; i++)
	{
		printf("%2d", ps->a[i]);
	}
	printf("\n");
}

由于我们这里展示的是最简单的顺序表。所以打印十分简单。

6 结束语

顺序表的功能我们已经实现，我们使用的是最简单的顺序表，所以整个过程看起来没有困难。在下一篇文章中我们将进行通讯录的实现。
在通讯录里，顺序表的类型不在是简单的" int ",而是结构体类型。
下面给出通讯录的基本功能供大家参考预习。

期待下一次与你见面！！！