顺序表的基本操作

水深无声 2023-10-04 23:16 48阅读 0赞

**目录**

一.什么是顺序表

二.顺序表的基本操作

1.初始化

2.增容

3.尾插

4.头插

5.尾删

6.头删

7.指定位置插入

8.指定位置删除

9.打印

10.查找

11.销毁

--------------------

## 一.什么是顺序表 ##

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

顺序表一般分为静态顺序表和动态顺序表，静态顺序表一般是用定长数组存储，而动态顺序表则是用动态内存管理函数进行动态分配空间，当空间不够时可以进行增容

静态顺序表：

#define MAX 100
    typedef int SLDataType；//对类型重定义，方便适应不同的数据类型
    struct SeqList
    {
        SLDataType a[MAX];//定长数组
        int size;         //当前数据个数
    };

动态顺序表：

typedef int SLDataType;//对类型重定义，方便适应不同的数据类型
    typedef struct SeqList
    {
    	SLDataType *a;//定义指针指向动态开辟的空间
    	int size;    //当前存储的数据个数
    	int capacity; //数据最大个数
    }SL;

一般我们不太经常使用静态顺序表，因为实际需求往往空间都是不定的，因此我们只讨论动态顺序表

顺序表的本质还是对数组进行操作，只是和数组有所不同的是，顺序表的数据是连续存放的

## 二.顺序表的基本操作 ##

一般地，我们都是用结构体定义顺序表，对顺序表的基本操作分为初始化，插入，删除，打印，查找，增容等操作，下面我们就来学习一下这些基本操作

### 1.初始化 ###

顺序表的初始化我们只需要讲指针置为空指针，然后将当前数据元素个数和最大数据元素个数置为0，到插入时我们便会动态开辟空间给指针a

void SLInit(SL * ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	ps->a = NULL;//置为空指针
    	ps->size = 0;//初始化为0
    	ps->capacity = 0;
    }

### 2.增容 ###

当当前数据元素个数等于最大数据元素个数时，说明空间已满，此时则需要我们进行扩容，而扩容需要我们利用的动态内存管理函数开辟空间，我们选择的是realloc函数，打开cpp网站查看该函数有关信息

![4bb95619a4a24034b7cdf1e6366f1a94.png][]

realloc函数的的两个参数分别为空间的地址和扩容后的空间大小，返回值是指向扩容后空间的地址，返回值void\*,因此我们需要将其强制类型转换为我们需要的类型

当realloc函数的第一个指针为空指针时，其作用相当于malloc，第一次增容，由于我们初始化时给了最大容量capacity为0，因此需要给capacity赋一个初始值4，后面再扩容时则最大容量翻倍

第一次调用realloc函数时，由于我们初始化时将指针a赋为空指针，故第一次调用realloc函数作用和malloc函数相当，后面再次调用则实现扩容功能

void SLCheckCapacity(SL* ps)
    {
    	assert(ps);断言是否为空指针，如传入空指针则报错，防止函数被误用
    	if (ps->size == ps->capacity)//判断当前数据个数是否到达最大值，是则增容
    	{
    		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次给值为4，后面则翻倍
    		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间
    		if (tmp == NULL)//判断是否开辟成功，如果返回空指针说明开辟失败则报错，否则将空间的地址付给a指针
    		{
    			perror("realloc fail");
    			return;
    		}
    		ps->a = tmp;
    		ps->capacity = newCapacity;//最大容量更新为扩容之后的容量
    	}
    }

### 3.尾插 ###

尾插先判断空间是否已满，若空间已满，则需要扩容，然后再直接从尾部插入，后将数据个数加1即可

void SLPushBack(SL* ps, SLDataType x)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	SLCheckCapacity(ps);//检查是否需要增容
    	ps->a[ps->size] = x;//在尾部插入值
    	ps->size++;			//数据个数加1
    }

### 4.头插 ###

头插也需要判断空间是否已满，若空间已满，则需要扩容，然后再从头部插入，插入过程：先将顺序表里面已有的每一个元素往后挪动一个位置，相当于头部就腾出了一个“空位”，然后我们将需要插入的元素放到这个“空位”即可，后将数据元素加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++;  //数据个数加1
    }

### 5.尾删 ###

尾删需要先判断当前顺序表是否有元素，没有元素则直接报错，如果有元素，我们只需要将数据个数减1即达到删除效果，而不需要对最后一个元素进行操作，后续操作直接将它覆盖就行

void SLPopBack(SL* ps)
    {
    	assert(ps->size > 0);//判断当前是否有元素
    	ps->size--;//直接将数据个数减1即可
    }

### 6.头删 ###

头删也需要先判断当前顺序表是否有元素，没有元素则直接报错，如果有元素，则删除的过程为：以我们排队打饭为例，当队伍的最前面一个人打完饭，后面的每一个人就都会往前一个位置，此时删除元素也是一样，从第二个位置开始到最后一个元素每个元素都依次往前挪动一个元素即可，后将数据个数减1

void SLPopFront(SL* ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	assert(ps->size > 0);//判断当前是否有元素
    	
    	int begin = 0;
    	while (begin < ps->size - 1)//从尾部一次挪动元素
    	{
    		ps->a[begin] = ps->a[begin+1];
    		begin++;
    	}
    	ps->size--;//数据个数减1
    }

### 7.指定位置插入 ###

指定位置我们需要先判断指定位置是否合法，如果小于0或者大于最大元素个数则直接报错，再判断是否需要增容，然后从指定位置开始到最后一个元素每个元素依次往后挪动一个位置，然后再将所插入的元素放到指定位置即可，后将数据元素个数加1

void SLInsert(SL* ps, int pos, SLDataType x)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	assert(pos >= 0 && 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++;//数据个数加1
    }

### 8.指定位置删除 ###

指定位置删除野需要先判断给定位置是否合法，不合法则直接报错，然后从指定位置到最后一个元素依次往前挪动一个位置即可，后将数据元素减1

void SLErase(SL* ps, int pos)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	assert(pos >= 0 && pos < ps->size);//判断给定的位置是否合法
    	int begin = pos;
    	while (begin < ps->size - 1)//从指定位置依次挪动元素，直到到达尾部的前一个元素
    	{
    		ps->a[begin] = ps->a[begin + 1];
    		begin++;
    	}
    	ps->size--;//数据个数减1
    }

### 9.打印 ###

打印只需要定义一个循环变量，以下标的形式遍历顺序表打印即可

void SLPrint(SL* ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	int i = 0;
    	for (i = 0; i < ps->size; i++)//依次遍历打印顺序表即可
    	{
    		printf("%d ", ps->a[i]);
    	}
    }

### 10.查找 ###

查找也是遍历顺序表，将每一个元素与查找的元素比较，若相等则返回元素下标，若遍历完没有找到元素，则返回-1，证明找不到该元素

int SLFind(SL* ps, SLDataType x)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	int i = 0;
    	for (i = 0; i < ps->size; i++)//遍历数组，比较是否相等，相等则返回元素下标
    	{
    		if (ps->a[i] == x)
    			return i;
    	}
    	return -1;//如果遍历没有找到该元素，则返回-1
    }

### 11.销毁 ###

由于我们前面开辟空间是利用动态内存管理函数realloc开辟的，而该函数开辟的空间是由程序员自行开辟的，空间位于堆上，使用完空间后需要我们手动销毁，否则会导致内存泄露

销毁空间我们需要用到free函数，我们打开cpp网站查看该函数有关信息

![a0aa4f3ec0fa4573b763d22bcedefc36.png][]

freea函数的参数是一个指针，即所需要销毁的空间的地址，我们销毁顺序表只需要将指针a传给free函数即可，后讲指针a赋为空指针，防止其成为野指针

void SLDestroy(SL* ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	if (ps->a)
    	{
    		free(ps->a);//释放a指针指向的空间
    		ps->a = NULL;//将a指针置为空，防止其成为野指针
    		ps->size = ps->capacity = 0;//当前数据元素个数和最大数据元素个数全置为0
    	}
    }

可以看到，上面的基本操作都是有相应的接口函数，我们只需要调用相应的函数即可实现顺序表的一些基本操作

上面所有的接口函数都用到了assert函数，且都位于函数体开头，assert函数称之为断言函数，当表达式为真是继续执行，当表达式为假时则直接报错，而这种报错可以让我们快速了解错误出在什么地方

我们打开cpp网站查看该函数有关信息

![17942dc453c74508a8cf12bea088f1a7.png][]

上面的所有接口函数调用assert函数，传的参数时指针a，当指针a为空指针时则直接报错，可以防止函数被误用而导致一些未知的错误

上面就是顺序表的一些基本操作，以下是全部代码：

SeqList.c

#include"SeqList.h"
    void SLCheckCapacity(SL* ps)
    {
    	assert(ps);断言是否为空指针，如传入空指针则报错，防止函数被误用
    	if (ps->size == ps->capacity)//判断当前数据个数是否到达最大值，是则增容
    	{
    		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次给值为4，后面则翻倍
    		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间
    		if (tmp == NULL)//判断是否开辟成功，如果返回空指针说明开辟失败则报错，否则将空间的地址付给a指针
    		{
    			perror("realloc fail");
    			return;
    		}
    		ps->a = tmp;
    		ps->capacity = newCapacity;//最大容量更新为扩容之后的容量
    	}
    }
    void SLInit(SL * ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	ps->a = NULL;//置为空指针
    	ps->size = 0;//初始化为0
    	ps->capacity = 0;
    }
    void SLDestroy(SL* ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	if (ps->a)
    	{
    		free(ps->a);//释放a指针指向的空间
    		ps->a = NULL;//将a指针置为空，防止其成为野指针
    		ps->size = ps->capacity = 0;//当前数据元素个数和最大数据元素个数全置为0
    	}
    }
    void SLPushBack(SL* ps, SLDataType x)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	SLCheckCapacity(ps);//检查是否需要增容
    	ps->a[ps->size] = x;//在尾部插入值
    	ps->size++;			//数据个数加1
    }
    void SLPrint(SL* ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	int i = 0;
    	for (i = 0; i < ps->size; i++)//依次遍历打印顺序表即可
    	{
    		printf("%d ", ps->a[i]);
    	}
    }
    void SLPopBack(SL* ps)
    {
    	assert(ps->size > 0);//判断当前是否有元素
    	ps->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++;  //数据个数加1
    }
    void SLPopFront(SL* ps)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	assert(ps->size > 0);//判断当前是否有元素
    	
    	int begin = 0;
    	while (begin < ps->size - 1)//从尾部一次挪动元素
    	{
    		ps->a[begin] = ps->a[begin+1];
    		begin++;
    	}
    	ps->size--;//数据个数减1
    }
    void SLInsert(SL* ps, int pos, SLDataType x)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	assert(pos >= 0 && 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++;//数据个数加1
    }
    void SLErase(SL* ps, int pos)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	assert(pos >= 0 && pos < ps->size);//判断给定的位置是否合法
    	int begin = pos;
    	while (begin < ps->size - 1)//从指定位置依次挪动元素，直到到达尾部的前一个元素
    	{
    		ps->a[begin] = ps->a[begin + 1];
    		begin++;
    	}
    	ps->size--;//数据个数减1
    }
    int SLFind(SL* ps, SLDataType x)
    {
    	assert(ps);//断言是否为空指针，如传入空指针则报错，防止函数被误用
    	int i = 0;
    	for (i = 0; i < ps->size; i++)//遍历数组，比较是否相等，相等则返回元素下标
    	{
    		if (ps->a[i] == x)
    			return i;
    	}
    	return -1;//如果遍历没有找到该元素，则返回-1
    }

SeqList.h

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    //动态顺序表
    typedef int SLDataType;//对类型重定义，方便适应不同的数据类型
    typedef struct SeqList
    {
    	SLDataType *a;//定义指针指向动态开辟的空间
    	int size;    //当前存储的数据个数
    	int capacity; //数据最大个数
    }SL;
    void SLCheckCapacity(SL *ps);
    void SLInit(SL * ps);
    void SLDestroy(SL* ps);
    void SLPrint(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);

test.c

#define _CRT_SECURE_NO_WARNINGS
    #include"SeqList.h"
    void TestSeqList()
    {
    	SL sl;
    	SLInit(&sl);
    	SLPushBack(&sl, 1);
    	SLPushBack(&sl, 2);
    	SLPushBack(&sl, 3);
    	SLPushBack(&sl, 4);
    	SLPushBack(&sl, 5);
    	SLPushFront(&sl, 0);
    	SLInsert(&sl, 2, 9);
    	SLErase(&sl, 2);
    	int pos = SLFind(&sl, 5);
    	if (pos != -1)
    		SLErase(&sl, pos);
    	SLPrint(&sl);
    	SLDestroy(&sl);
    }
    int main()
    {
    
    	TestSeqList();
    	return 0;
    }

输出结果：

![55ac510c1d7b4f67ae9e7c2095c300d6.png][]

好啦，顺序表我们就先学到这里，如果喜欢我的文章，欢迎动动手指一键三连~

[4bb95619a4a24034b7cdf1e6366f1a94.png]: https://img-blog.csdnimg.cn/4bb95619a4a24034b7cdf1e6366f1a94.png
[a0aa4f3ec0fa4573b763d22bcedefc36.png]: https://img-blog.csdnimg.cn/a0aa4f3ec0fa4573b763d22bcedefc36.png
[17942dc453c74508a8cf12bea088f1a7.png]: https://img-blog.csdnimg.cn/17942dc453c74508a8cf12bea088f1a7.png
[55ac510c1d7b4f67ae9e7c2095c300d6.png]: https://img-blog.csdnimg.cn/55ac510c1d7b4f67ae9e7c2095c300d6.png