C语言数据结构深入探索顺序表

1.顺序表的概念及结构

顺序表是使用一段连续物理地址的单元来依次储存数据的线性结构，一般采用数组存储。在数组上完成增删查改。

顺序表分为两类：

静态顺序表：使用定长数组储存元素

struct SeqList
{
    int data;//存储的数据
    int size;//记录数据个数
    int 1000;//给定当前顺序表的总容量为1000
};

动态顺序表：使用动态开辟的数组存储

struct SeqList
{
    int data;//存储的数据
    int size;//记录数据个数
    int capacity;//顺序表的总容量
};

2.增删查改的实现

当我们需要储存的数据数目不确定时我们使用动态顺序表更佳，所以下面就用动态顺序表来实现增删查改。

2.1扩容

首先我们动态顺序表想要实现自动扩容，当当前数据量size等于总容量capacity时我们就需要自动增容，具体就是使用malloc函数开辟一定数量的空间，假如我们设定每次扩充二倍，代码如下：

//增容
void SLCheckcapacity(SL* pc)
{
	assert(pc != NULL);
	//检查容量，满了就扩容
	if (pc->sz == pc->capacity)
	{
		//一次扩容二倍，如果初始为0就先扩容到4
		int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
		//注意类型转换
		SLDatatype* tmp = (SLDatatype*)realloc(pc->data, sizeof(SLDatatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("SLCheckcapacity::realloc");
			exit(-1);
		}
		//讲开辟的空间tmp给到数组
		pc->data = tmp;
		pc->capacity = newcapacity;
	}
}

2.2插入数据

插入数据时我们有三种情况，头插尾插和中间任意位置插。

2.2.1尾插

先从最简单的尾插开始，我们尾插时需要记录下当前的size，这样插入的时候就可以直接找到尾部，我们需要注意的是，我们插入之前需要判断一下当前的容量满了没有，如果满了就需要扩容，没满就可以直接插入。

//尾插
void SLPushBack(SL* pc, SLDatatype x)
{
	assert(pc != NULL);
	//需要判断是否需要增容
	SLCheckcapacity(pc);
	pc->data[pc->sz] = x;
	pc->sz++;
}

2.2.2头插

头插相对来说要复杂一点，当头上没有数据时，我们就可以看成尾插直接插入，当头上有数据时，我们为了避免数据的覆盖，需要将所有数据向后移动，再放入在头部，在我们向后移动数据时我们也需要判断是否满容了。

//头插
void SLPushFront(SL* pc, SLDatatype x)
{
	assert(pc != NULL);
	SLCheckcapacity(pc);
	//挪动数据
	int end = pc->sz - 1;
	while (end >= 0)
	{
		pc->data[end + 1] = pc->data[end];
		--end;
	}
	//插入数据
	pc->data[0] = x;
	pc->sz++;
}

2.2.3任意位置插入

我们任意位置插入时有三种情况，当在第一个位置时就是头插可以调用头插的函数，在最后一个位置时就是尾插，就调用尾插的函数，当我们在中间的时我们需要找到需要插入的位置，然后将数据从这个位置开始向后挪动，再插入进去。

//任意位置插入
void SLInsert(SL* pc, int pos, SLDatatype x)
{
	assert(pc);
    //判断pos是否在有效数据范围内
	assert(pos >= 0 && pos <= pc->sz);
	SLCheckcapacity(pc);
    //挪动数据
	int end = pc->sz - 1;
	while (end >= pos)
	{
		pc->data[end+1] = pc->data[end];
		--end;
	}
	pc->data[pos] = x;
	pc->sz++;
}

2.3删除数据

删除数据和上面的插入数据差不多，我们也需要凑够三个方面来撕开，头部删除，尾部删除，中间任意位置删除，当我们删除数据时我们只需要将这个数据后的数据依次向前挪动，覆盖住这个数据即可。这里我们不能用free函数去释放那块地址的空间来删除，因为顺序表的物理地址是连续的。链表可以，下一章会介绍。

2.3.1尾删

尾部后面没有数据那么就把最后一个数据制成0就好了

//尾删
void SLPopBack(SL* pc)
{
	assert(pc != NULL);
	//不能删多了
	assert(pc->sz > 0);
	pc->sz--;
}

2.3.2头删

将从第二个位置开始的数据往前挪动，这里需要注意，删除需要检查，以免越界。

//删除需要检查，删多了会越界
//头删
void SLPopFront(SL* pc)
{
	assert(pc != NULL);
	//检查
	assert(pc->sz > 0);
	//从第二个元素开始从后往前挪直接将其覆盖
	int begin = 0;
	while (begin <= pc->sz)
	{
		pc->data[begin-1] = pc->data[begin];
		++begin;
	}
	pc->sz--;
}

2.3.3任意位置删除

任意位置删除我们只需要将我们需要删除的位置后面的数往前挪动就行了

//任意位置删除
void SLErase(SL* pc, int pos)
{
	assert(pc != NULL);
	assert(pos >= 0 && pos < pc->sz);
	int begin = pos;
	while (begin < pc->sz-1)
	{
		pc->data[begin] = pc->data[begin + 1];
		begin++;
	}
	pc->sz--;
}

2.4查找

我们给一个数据x来表示我们想要查找的数据，从前往后把顺序表遍历一遍，当给的X等于顺序表中的X时就找到了，返回当前位置的下标。

//查找
int SLFind(SL* pc, SLDatatype x)
{
	assert(pc != NULL);
	for (int i = 0; i < pc->sz; ++i)
	{
		if (pc->data[i] == x)
		{
			return i;
		}
	}
	printf("找不到\n");
	return;
}

2.5修改数据

当我们想要修改某一个地方的数据时，直接将那个位置的数据输入新的数据覆盖掉就行了。

//改数据
void SlModify(SL* pc, int pos, SLDatatype x)
{
	assert(pc != NULL);
	if (pos >= 0 && pos <= pc->sz)
	{
		pc->data[pos] = x;
	}
	else
	{
		printf("超出范围了\n");
	}
}

2.6销毁空间

当我们顺序表使用完成过后，我们需要注意的是，我们malloc的空间并没有得到释放，可能会造成内存泄漏等问题（可参考前面的博客 '动态内存开辟' ），释放内存就需要用到free函数

//销毁空间
void SLDestory(SL* pc)
{
	if (pc->data)
	{
		free(pc->data);
		pc->data = NULL;
		pc->capacity = pc->sz = 0;
	}
}

这里就简单的给大家介绍了动态顺序表的简单功能，在这里都是封装成接口函数使用的，下一章给大家介绍链表的实现。

频道导航