【数据结构】~顺序表

这篇具有很好参考价值的文章主要介绍了【数据结构】~顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

作者：小蜗牛向前冲

名言：我可以接收失败，但我不能接收放弃

顺序表的结构体类型定义,数据结构,数据结构

如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

一什么是顺序表？

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

上面我们知道了顺序表其实是一个连续存放数据的数组，为了更加清楚的理解顺序表，下面我带领大家写一个顺序表。

那顺序表要如何写呢？

为了规范管理我们的项目，我们将分文件写。

二创建三个文件

1 SeqList.h

在该文件中我们完成，顺序表的类型定义，接口函数的声明，引用的头文件。

2 SeqList.c

完成顺序表接口函数的实现

3 Test.c

主函数，测试顺序表各接口的功能

这里简单的提醒下，我们在定义文件名或者在定义函数名时候尽量定义的有意义点，一般是通过英文单词的缩写或者全名（总之要看到单词知道你这文件或者函数是干什么的），书写风格的话，我一般习惯将单词首字母大小其余小写。

用上面的定义的文件名说明一下

SeqList.h（Sequential 顺序，List表，.h头文件）。

好了下面进入正题。

三 SeqList.h

下面是SeqList.h的全部内容

#define  _CRT_SECURE_NO_WARNINGS

#pragma once//防止头文件被重复引用

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLDateType;
//顺序表的动态储存

typedef struct SeqList
{
	SLDateType* arr;//指向动态开辟的数组
	size_t size;//有效的数据的个数
	size_t capacity;//容量大小
}SL;

//初始化顺序表
void SLInit(SL* ps1);
//销毁顺序表
void SLDestory(SL* ps1);
//增容
void CheckCapacity(SL* ps1);
//顺序表尾部插入
void SLPushBack(SL* ps1, SLDateType x);
//顺序表尾部删除
void SLPopBack(SL* ps1);
//顺序表头部插入
void SLPushFront(SL* ps1, SLDateType x);
//顺序表头删数据
void SLPopFront(SL* ps1);
//打印顺序表
void SLPrint(const SL* ps1);
//顺序表中查找指定值
int SLFind(SL* ps1, SLDateType x);
//顺序表中指定下标插入数
void SLInsert(SL* ps1, size_t pos, SLDateType x);
//顺序表中删除指定下标位置的数据
void SLErase(SL* ps1, size_t pos);
//查看顺序表中有效数据个数
size_t SLSize(SL* ps1);
//修改指定下标位置的数据
void SLAt(SL* ps1, size_t pos, SLDateType x);

顺序表的类型定义

typedef int SLDateType;
//顺序表的动态储存

typedef struct SeqList
{
	SLDateType* arr;//指向动态开辟的数组
	size_t size;//有效的数据的个数
	size_t capacity;//容量大小
}SL;

其实顺序表是分静态和动态二种，静态的话就是给定的内存空间是有限的，这样在实际用途中没什么意义，下面我们要实现的是动态的顺序表。

定义顺序的类型，我们是用结构体来定义的，在结构体中我们主要定义了指向动态开辟的数组的指针arr，数据的有效个数size,数组当前空间的容量大小capacity。为了方便函数的书写我们还用typedef 重新给结构体起个名字叫SL。

四 SeqList.c

在这里我们将完成顺序表接口函数的实现。

我们要首先实现顺序表的那个接口呢？

我们不难想到，我们在第一次使用顺序表时肯定是要对它进行初始化的，因为我们要存放的是自己想要的数据。

1 顺序表的初始化

//初始化顺序表
void SLInit(SL* ps1)
{
	assert(ps1);//断言
	ps1->arr = NULL;//初始化顺序表为空
	ps1->size = 0;//初始化有效数据为0
	ps1->capacity = 0;//初始化空间容量为0
}

当我们不想在要这个顺序表时也可以销毁它

2 顺序表的销毁

这里最为关键的是将开辟的空间释放掉，以免避空间不必要的损失。

//销毁顺序表
void SLDestory(SL* ps1)
{
	assert(ps1);//断言
	free(ps1->arr);//释放开辟的动态空间
	ps1->arr = NULL;//置空
	ps1->size = 0;//数据置0
	ps1->capacity = 0;//空间容量置0
}

既然这个顺序表是动态的那就免不了对顺序表的增容。

3 顺序表的增容

顺序表的扩容是有考量的，我们不能过大的扩容空间（避免空间的浪费），当然我们也要过分的少个空间，所以综合考虑来说我们一般是将空间每次扩容2倍，当空间为0时，我们先给4数据个内存空间。

//检测是否要增容
void CheckCapacity(SL* ps1)
{
	assert(ps1);//断言
	if (ps1->size == ps1->capacity)
	{
		size_t NewCapacity;//新容量
		if (ps1->capacity == 0)
		{
			NewCapacity = ps1->capacity = 4;//原来容量为0，扩容为4
		}
		else
		{
			NewCapacity = 2 * ps1->capacity;//原来容量为0，扩容为原来的2倍
		}
		SLDateType* ptr = (SLDateType*)realloc(ps1->arr, sizeof(SLDateType) * NewCapacity);//扩容
		if (ptr == NULL)
		{
			perror("realloc fail");//报错
			exit(-1);//程序结束
		}
		ps1->arr = ptr;//开辟成功
		ps1->capacity = NewCapacity;//更新容量
	}
}

4 顺序表尾部插入和尾部删除

尾部插入

顺序表的结构体类型定义,数据结构,数据结构

我们特别要注意不是把数据直接插入到尾部空间去，而是从尾部的方向插入。

//顺序表尾部插入
void SLPushBack(SL* ps1, SLDateType x)
{
	assert(ps1);//断言
	CheckCapacity(ps1);//检测是否要增容
	ps1->arr[ps1->size] = x;//尾插数据，size始终指向数组的下个元素
	ps1->size++;//有效数据+1
}

尾部删除

//顺序表尾部删除
void SLPopBack(SL* ps1)
{
	assert(ps1);//断言
	assert(ps1->size > 0);//size为空时，不要在删除了
	ps1->size--;//有效数据-1
}

特别注意

我们在每次写一个函数时都应该测试该函数是否会报错，功能能否实现（前面的函数我在编译器是测试了，就不展示给大家看了ヾ(≧▽≦*)o）

测试尾插和尾删

顺序表的结构体类型定义,数据结构,数据结构

5 头插数据和头删数据

头插数据就是每次要插入数据时我们都应该，将插入之前的数据后移，为插入数据腾出空间。

顺序表的结构体类型定义,数据结构,数据结构

//头插数据
void SLPushFront(SL* ps1, SLDateType x)
{
	assert(ps1);//断言
	CheckCapacity(ps1);//检测顺序表是否满
	int i = 0;
	for (i = ps1->size - 1;i >= 0;i--)//顺序表中的元素依次向后移动一位
	{
		ps1->arr[i + 1] = ps1->arr[i];
	}
	ps1->arr[0] = x;//头插数据
	ps1->size++;//有效数据+1
}

头删数据

//顺序表头删数据
void SLPopFront(SL* ps1)
{
	assert(ps1);//断言
	assert(ps1->size > 0);
	int i = 0;
	for (i=1;i<ps1->size;i++)
	{
		ps1->arr[i - 1] = ps1->arr[i];
	}
	ps1->size--;//有效数据-1
}

测试头插和头删

顺序表的结构体类型定义,数据结构,数据结构

这里补充一下打印顺序表的函数

//打印顺序表
void SLPrint(const SL* ps1)
{
	assert(ps1);//断言
	if (ps1->size == 0)//判断顺序表是否为空
	{
		printf("顺序表为空\n");
		return;
	}
	int i = 0;
	for (i = 0;i < ps1->size;i++)//打印顺序表
	{
		printf("%d ", ps1->arr[i]);
	}
	printf("\n");
}

5 顺序表查找指定值

有时我们要查找顺序表中的数据，为此我们可以写个函数来实现该接口的功能，其实就是遍历一便数组，在找到了就返回数组的下标，没找到就返回-1


//在顺序表中查找指定值
int SLFind(SL* ps1, SLDateType x)
{
	assert(ps1);//断言
	int i = 0;
	for (i = 0;i < ps1->size - 1;i++)
	{
		if (ps1->arr[i] == x)
		{
			return i;//返回找到的下标
		}
	}
	return -1;//没找到
}

测试

顺序表的结构体类型定义,数据结构,数据结构

6 顺序表中指定下标插入和删除数据

指定下标插入

在写这个函数时我们要注意判断pos（下标）是否合法，这样是非常关键的，不然当pos==0时会出现死循环的现象。

//顺序表中指定下标插入数
void SLInsert(SL* ps1, size_t pos, SLDateType x)
{
	assert(ps1);//断言
	assert(pos >= 0 && pos <= ps1->size);//检测pos的合法性
	CheckCapacity(ps1);//检测顺序表是否满
	size_t i = 0;
	for (i = ps1->size-1;i >= pos;i--)//顺序后移动
	{
		ps1->arr[i + 1] = ps1->arr[i];
	}
	ps1->arr[pos] = x;//插入数据
	ps1->size++;//有效数据+1
}

指定下标删除数据

有插入就会有删除，对于删除数据我们不能简单就把数据置0就可以了。

为什么这么说呢？

因为要是顺序表中你要删除的数据就是0，这不就没删除，那我们直接吧那块空间释放掉总行吧，这是不被允许的，内存函数中不能指定释放空间，就算我们要删除的空间是顺序表的最后一个元素也不建议删除（避免不必要的空间浪费）。

//顺序表中删除指定下标位置的数据
void SLErase(SL* ps1, size_t pos)
{
	assert(ps1);//断言
	assert(pos >= 0 && pos <= ps1->size);//检测pos的合法性
	assert(ps1->size > 0);//顺序表不为空
	size_t i = 0;
	for (i = pos+1;i < ps1->size;i++)//将pos后的数据前移动一个单位
	{
		ps1->arr[i-1] = ps1->arr[i];
	}
	ps1->size--;//有效数据-1
}

测试

顺序表的结构体类型定义,数据结构,数据结构

7 查看顺序表中有效数据个数和修改指定下标位置的数据

查看顺序表中有效数据个数

我们直接调用结构体不就行，还写个函数干嘛呢？

这是因为，顺序表规定在调用顺序表的功能时，最好是通过函数接口来实现

修改指定下标位置的数据

这里没什么好说的，只要顺序表不为空，直接修改就好了

//修改指定下标位置的数据
void SLAt(SL* ps1, size_t pos,SLDateType x)
{
	assert(ps1);//断言
	assert(pos > 0 && pos <= ps1->size);//pos合法性检查
	assert(ps1->size > 0);//顺序表不为空
	ps1->arr[pos] = x;//修改
}

下面我在来测试一下上面写顺序表的功能

顺序表的结构体类型定义,数据结构,数据结构