【初识数据结构】c语言实现动态顺序表（已配图）-创新互联

前言 

成都创新互联长期为千余家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为阿巴嘎企业提供专业的网站制作、成都网站设计，阿巴嘎网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。

大家好啊，这里是幸麟

一名普通的大学牲

🧩希望通过寒假多学一些知识，对自己进行一些有益的补充

也愿意与各位一起奋斗，为了更好的明天努力

目录

什么是顺序表

接口

初始化SLInit

顺序表空间检查&扩容

插入元素

头插SLPushFront

尾插

万能插SLInsert

删除数据

万能删SLErase

查询SLFind

打印顺序表SLPrint

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

但其存储并不像数组那样可以在其区间内任意位置存储，顺序表需要依次存储，正如其名，只有存储完上一位置后才能存储下一位置

顺序表：（自己做的可能有点不太好看哈），其中size代表下一个要存储在a数组内的元素下标，也代表有效数据的数量

其中顺序表可以分为采用定长数组进行存储的静态顺序表和使用动态开辟数组的动态顺序表

其中静态顺序表由于是采用定长数组进行存储，常常会有数组开大了空间浪费，数组开小了不够用的窘况，所以实际中还是动态顺序表使用居多

其中我们用typedef定义我们创建的结构体seqlist为SL，这样写起来时方便一些

同时由于我们可能更改顺序表中存储数据的类型，为了方便日后可能有的调整我们定义一个数据类型SLDataType，这里先使用int，如果以后想将存储数据类型为longlong的元素直接更改SLDataType即可

#pragma once
#include#include 
#includeusing namespace std;
typedef int SLDataType ;
typedef struct Seqlist
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据的大小，同时也是下一个数据存储位置
	int capacity;//顺序表空间的大小
}SL;

void SLPrint(SL* ps);//打印
void SLInit(SL* ps);//初始化
void SLDestory(SL* ps);//顺序表销毁
void SLCheckCapacity(SL* ps);//顺序表扩容

//尾插尾删
void SLPushBack(SL* ps,SLDataType x);
void SLPopBack(SL* ps);

//头插头删
void SLPushFront(SL* ps,SLDataType x);
void SLPopFront(SL* ps);

//万能插，万能删
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

在初始化时，我们要注意ps所指向的地址是不是空指针，如果是空指针程序会错误，所以这边加了一个断言判断，刚开始的顺序表空间与有效数据大小都没有，所以直接赋0

void SLInit(SL* ps)
{
	assert(ps);//断言ps是否为空指针，防止程序错误

	ps->a = NULL;
	ps->size = 0;//顺序表空间与有效数据大小都为0
	ps->capacity = 0;
}

在每一次进行插入操作时我们都应该进行一次空间的检查，如果发现以使用的有效数据大小与顺序表空间相等时就需要使用realloc函数对其进行扩容（一般扩大的容量为原来的两倍），在给newcapacity赋值时可以加一个判断，如果capacity并没有容量（即为0时），则让newcapacity=4，给予一个初始的空间

值得注意的是使用realloc函数申请空间时，可能会出现以下三种情况

①数组a原本的地址后面有充足的空余空间，扩容结束后返回原来数组a的地址

②数组a原本的地址后面并没有足够的空间用来扩容，这时候就需要重新找一个地址进行扩容，所以这时候会返回一个新的地址

③realloc有可能扩容失败，返回一个空指针NULL

所以我们这里用用一个指针tmp用来接收realloc的返回值，如果返回值不为NULL则将a的地址变更为tmp接收的地址

void SLCheckCapacity(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)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

由于是插入操作，所以在开始前一定要检查一下容量是否充足

创建一个变量end，从size-1,即最后一个数据的下标开始，把每一个数据往后挪一个位置，直到移完第一个数据，然后再将所要插入的数据插入即可，插入结束后size++，有效数据＋1

void SLPushFront(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	int end = ps->size-1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

代码：

由于是插入操作同样需要检查一个容量是否足够

然后直接插入末尾即可，同样最后size++，有效数据＋1

void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

所有的插入，都可以用万能插实现，头插和尾插也都是万能插的一种特殊情况

头插相当在pos=0时的万能插，尾插相当于pos=size-1时的万能插

，我们用pos表示想要插入的位置，同时pos有效范围为[0,size-1]，如果超出这个范围会出错，所以这边加个断言，移动数据的时候同样使用从size-1开始移动，直到把原本下标为pos的数据移走，然后在pos位置插入新数据，结束后size++

void SLInsert(SL* ps, int pos,SLDataType x )
{
	assert(ps);
	assert(pos >= 0);
	assert(pos<= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

我们插入有头插，尾插，万能插

那同理，我们删除也有头删，尾删，万能删

同样，这边头删，尾删都可以用万能删来替代，所以删除部分我们主要介绍万能删

如果想要删除在pos位置的元素，我们可以让pos后面的数据全部往前挪，用后面的数据覆盖掉pos位置的数据即可完成删除，结束后size--，有效数据-1

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(ps->size >pos);
	int begin = pos + 1;
	while (beginsize)
	{
		ps->a[begin-1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

这个操作主要是用于寻找在顺序表中第一个出现的元素x的位置，如果没有找到则返回-1

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);

	for (int i = 0; i< ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

如果我们想要找到所有值为x的数组，也可以这么写，增加一个形参begin用于表示查询开始的下标位置

int SLFind1(SL* ps, SLDataType x, int begin)
{
	assert(ps);

	for (int i = begin; i< ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

SL s1;
	int pos = 0;
	while (SLFind1(&s1, 1, pos) != -1)
	{
		pos = SLFind1(&s1, 1, pos);
	}

这样每次SLFind1返回值就是想要查找的元素的位置

打印时下标从0开始打印，从图可以看到，size所指向的下标是未使用的位置，所以打印size-1结束即可

void SLPrint(SL* ps)
{
	assert(ps);

	for (int i = 0; i< ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

好了我们的顺序表的介绍到这里就结束了，如果有错误欢迎在评论区指出

写文不易，可以给个赞吗

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧