数据结构之顺序表

  • 开发
  • 28

片头

嗨! 小伙伴们,大家好! 哈哈,今天我们来一起学习顺序表,本篇超级详细,一定可以教会你! 

一、线性表

1.1是线性表呢？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。常见的线性表：顺序表、链表、栈、队列、字符串......

线性表在逻辑上是线性结构,就像一串珠子穿在一根绳上。但是线性表在物理结构上不一定是连续的,线性表以数组的形式存储时和以链式结构存储时在物理内存上的布局是不一样的。

线性表以数组的形式存储时在内存中是连续的，而线性表以链式结构存储时在内存中不一定连续。

二、顺序表

2.1 顺序表的定义

线性表的顺序存储又称为顺序表，顺序表是用一段地址连续的存储单元来依次存储数据元素的线性结构，从而使得逻辑上相邻的两个元素在物理位置上也相邻，也就是说我们可以通过下标来依次访问结构中的内容。平时我们使用的数组也是顺序表的一种实现方式。

2.2 顺序表的种类

顺序表一般可以分为：（1）静态顺序表：使用定长数组存储元素

我们先来试一下创建一个静态顺序表

#define N 10
typedef int ElemType;

typedef struct SeqList {
	ElemType arr[N];	//定长数组
	int size;			//有效数据个数
}SL;

我们可以看到,静态顺序表中定义了一个定长数组,也就是说数组一旦开辟就无法再更改大小了。

所以静态顺序表只适用于已知需要存储多少数据的场景，如果定长数组过大，就会浪费空间，如果过小，又不够用。所以一般情况下，我们都使用动态顺序表，可以根据需要来动态分配空间，接下来我们认识一下动态顺序表。

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

typedef int ElemType;

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

动态顺序表中存储数据的空间需要我们进行动态内存开辟，以上便是动态顺序表的结构。

2.3 顺序表的增删改查接口实现

接下来我们一步一步来实现顺序表的增删改查接口，当然此处使用的是动态顺序表。

本次演示的是vs2019,我们先创建一个新项目,并新建头文件"SeqList.h"和两个源文件"SeqList.c" 和"test.c",它们的作用分别是:

SeqList.h 顺序表的定义,头文件的引用和接口函数的声明
SeqList.c 具体实现顺序表里定义的接口/方法
test.c 测试各个函数

首先我们展示"SeqList.h"的完整代码,不要忘了在两个源文件中引用"SeqList.h"

#pragma once//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//静态顺序表
//#define N 10
//typedef struct SeqList {
//	ElemType arr[N];	//定长数组
//	int size;			//有效数据个数
//}SL;

//动态顺序表
typedef int ElemType;	//如果要修改存储的数据类型可直接在此修改
typedef struct SeqList {
	ElemType* arr;		//指向动态数组开辟的空间
	int capacity;		//开辟空间的容量大小
	int size;		    //有效数据个数
}SL;

//顺序表的增删改查接口
//顺序表的初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表的打印
void SLPrint(SL* ps);

//检查顺序表的容量,如果满了,进行扩容
void SLCheckCapacity(SL* ps);

//顺序表的尾插
void SLPushBack(SL* ps, ElemType x);
//顺序表的头插
void SLPushFront(SL* ps, ElemType x);
//顺序表的尾删
void SLPopBack(SL* ps);
//顺序表的头删
void SLPopFront(SL* ps);

//顺序表指定位置插入数据
void SLInsert(SL* ps, int pos, ElemType x);
//顺序表删除指定位置的数据
void SLErase(SL* ps,int pos);
//顺序表中查找目标值
int SLFind(SL* ps, ElemType x);

接下来,我们逐一的实现各个接口函数,每一步都详细讲解,必须让你学会

(1)顺序表初始化
//顺序表初始化
void SLInit(SL* ps) {
	assert(ps);		 //断言,防止传入空指针
	ps->arr = NULL;	 //初始化动态数组为空
	ps->capacity = 0;//初始化动态数组的空间容量为0
	ps->size = 0;	 //初始化有效元素个数为0
}
(2)检查顺序表的容量,如果为空或者满了,进行增容
//扩容
void SLCheckCapacity(SL* ps) {
	assert(ps);	//断言,防止传入空指针
	if (ps->capacity == ps->size) //如果容量为空或者有效数据个数等于空间容量大小则已满,扩容
	{
		//定义一个新变量来表示顺序表的空间容量,如果当前容量为空,则给顺序表的容量开辟4个空间,如果当前容量非空,则开辟原来空间的2倍
		//创建一个临时变量来存储新空间的地址,防止开辟失败
		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
		if (temp == NULL) //防止空间开辟失败
		{
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = temp;	//将临时指针变量中存放的新空间地址赋给arr
		ps->capacity = newCapacity;//空间容量更新
	}
}
(3)顺序表的尾插
//顺序表的尾插
void SLPushBack(SL* ps, ElemType x) {
	assert(ps);		//断言,防止传入空指针
	//空间不足,扩容
	SLCheckCapacity(ps);//如果容量为空或者已满,则扩容
	//空间足够,填充数据
	ps->arr[ps->size] = x;//在数组arr中的下标为size的地方插入数据x
	ps->size++;			  //size指向下一个位置
}

测试一下:


int main() {
	SL sl;				//定义一个顺序表sl
	SLInit(&sl);		//将顺序表sl初始化
	SLPushBack(&sl, 1); //将"1"尾插到顺序表中
	SLPushBack(&sl, 2); //将"2"尾插到顺序表中
	SLPushBack(&sl, 3); //将"3"尾插到顺序表中
	SLPushBack(&sl, 4); //将"4"尾插到顺序表中
	SLPrint(&sl);		//打印顺序表

	return 0;
}

运行结果为:

1    2    3    4 

(4)顺序表的头插

在顺序表的第一个位置(下标为0处)插入新元素"5"

//顺序表的头插
void SLPushFront(SL* ps, ElemType x) {
	assert(ps);			//断言,防止传入空指针
	SLCheckCapacity(ps);//如果容量为空或者已满则扩容
	for (int i = ps->size-1; i >= 0; i--) //从后到前,通过循环将所有数据向后移动
	{
		ps->arr[i + 1] = ps->arr[i];
		//最后一次循环:  ps->arr[1] = ps->arr[0];
	}
	ps->arr[0] = x;//将头部插入新数据
	ps->size++;	   //size指向下一个位置
}

测试一下:

int main() {
	SL sl;				//定义一个顺序表sl
	SLInit(&sl);		//将顺序表sl初始化
	SLPushBack(&sl, 1); //将"1"尾插到顺序表中
	SLPushBack(&sl, 2); //将"2"尾插到顺序表中
	SLPushBack(&sl, 3); //将"3"尾插到顺序表中
	SLPushBack(&sl, 4); //将"4"尾插到顺序表中
	SLPrint(&sl);		//打印顺序表

	SLPushFront(&sl, 5);//将"5"头插到顺序表中
	SLPrint(&sl);

	return 0;
}

运行结果为:

1    2    3    4 

5    1    2    3    4 

(5) 顺序表尾删

//顺序表尾删
void SLPopBack(SL* ps) {
	assert(ps);		//断言,防止传入空指针
	assert(ps->size);//断言,防止数组中元素个数已经为空,却还在执行删除
	ps->size--;		 //通过更新size把尾部数据覆盖即可
}

测试一下:

int main() {
	SL sl;				//定义一个顺序表sl
	SLInit(&sl);		//将顺序表sl初始化
	SLPushBack(&sl, 1); //将"1"尾插到顺序表中
	SLPushBack(&sl, 2); //将"2"尾插到顺序表中
	SLPushBack(&sl, 3); //将"3"尾插到顺序表中
	SLPushBack(&sl, 4); //将"4"尾插到顺序表中
	SLPrint(&sl);		//打印顺序表

	SLPopBack(&sl);		//将最后一个元素"4"删除
	SLPrint(&sl);		//打印顺序表

	return 0;
}

运行结果为:

1    2    3    4    

1    2    3   

(6) 顺序表头删

//顺序表头删
void SLPopFront(SL* ps) {
	assert(ps);			//断言,防止传入空指针
	assert(ps->size);	//断言,防止有效数据为空却还在执行删除操作

	for (int i = 1; i < ps->size; i++)//从前往后,通过循环将所有数据向前移动,把头数据覆盖
	{
		ps->arr[i - 1] = ps->arr[i];
		//最后一次: ps->arr[size-2] = ps->arr[size-1];
	}
	ps->size--;	//size更新
}

测试一下:

int main() {
	SL sl;				//定义一个顺序表sl
	SLInit(&sl);		//将顺序表sl初始化
	SLPushBack(&sl, 1); //将"1"尾插到顺序表中
	SLPushBack(&sl, 2); //将"2"尾插到顺序表中
	SLPushBack(&sl, 3); //将"3"尾插到顺序表中
	SLPushBack(&sl, 4); //将"4"尾插到顺序表中
	SLPrint(&sl);		//打印顺序表

	SLPopFront(&sl);	//将第一个元素"1"删除
	SLPrint(&sl);		//打印顺序表
	return 0;
}

运行结果:

1    2    3    4    

2    3    4

(7) 顺序表中查找目标值
//顺序表中查找目标值
int SLFind(SL* ps, ElemType x) {
	assert(ps);//断言,防止传入空指针
	for (int i = 0; i < ps->size; i++) //遍历顺序表
	{
		if (ps->arr[i] == x) {
			return i;//找到了,返回下标
		}
	}
	return -1;//没有找到,返回-1
}

测试一下:

int main() {
	SL sl;				//定义一个顺序表sl
	SLInit(&sl);		//将顺序表sl初始化
	SLPushBack(&sl, 1); //将"1"尾插到顺序表中
	SLPushBack(&sl, 2); //将"2"尾插到顺序表中
	SLPushBack(&sl, 3); //将"3"尾插到顺序表中
	SLPushBack(&sl, 4); //将"4"尾插到顺序表中
	SLPrint(&sl);		//打印顺序表

	int ret = SLFind(&sl, 2);//在顺序表中寻找"2"
	if (ret == -1) {
		printf("对不起,没有找到!\n");
	}
	else {
		printf("找到了,下标为: %d\n", ret);
	}
	return 0;
}

运行结果:

1    2    3    4    

找到了,下标为: 1

 (8)顺序表指定位置插入数据

//在指定位置插入数据
void SLInsert(SL* ps, int pos, ElemType x) {
	assert(ps);	//断言,防止传入空指针
	assert(pos >= 0 && pos <= ps->size);//断言,防止pos超出有效数据范围
	SLCheckCapacity(ps);//如果空间已满则扩容

	for (int i = ps->size-1; i >= pos; i--) //把pos之后的数据向后移动
	{
		ps->arr[i + 1] = ps->arr[i];
		//最后一次: ps->arr[pos+1] = ps->arr[pos];
	}
	ps->arr[pos] = x;//在pos处插入数据
	ps->size++;		 //size更新
}

测试一下:

int main() {
	SL sl;				//定义一个顺序表sl
	SLInit(&sl);		//将顺序表sl初始化
	SLPushBack(&sl, 1); //将"1"尾插到顺序表中
	SLPushBack(&sl, 2); //将"2"尾插到顺序表中
	SLPushBack(&sl, 3); //将"3"尾插到顺序表中
	SLPushBack(&sl, 4); //将"4"尾插到顺序表中
	SLPrint(&sl);		//打印顺序表

	SLInsert(&sl, 2, 100);	//在下标为2的位置插入"100"
	SLPrint(&sl);			//打印顺序表
	return 0;
}

运行结果为:

1    2    3    4    

1    2    100    3    4

 (9)顺序表删除指定位置的数据

//删除指定位置的数据
void SLErase(SL* ps, int pos) {
	assert(ps);	//断言,防止传入空指针
	assert(pos >= 0 && pos < ps->size);//断言,防止pos超出有效数据范围

	for (int i = pos; i < ps->size-1; i++)//将pos之后的数据向前移动,覆盖pos处的数据
	{
		ps->arr[i] = ps->arr[i+1];
		//最后一次: ps->arr[size-2] = ps->arr[size-1];
	}
	ps->size--;//size更新
}

测试一下:


int main() {
	SL sl;				//定义一个顺序表sl
	SLInit(&sl);		//将顺序表sl初始化
	SLPushBack(&sl, 1); //将"1"尾插到顺序表中
	SLPushBack(&sl, 2); //将"2"尾插到顺序表中
	SLPushBack(&sl, 3); //将"3"尾插到顺序表中
	SLPushBack(&sl, 4); //将"4"尾插到顺序表中
	SLPrint(&sl);		//打印顺序表

	SLErase(&sl, 1);			//删除下标为1的元素
	SLPrint(&sl);				//打印顺序表
	return 0;
}

运行结果为:

1    2    3    4    

1    3    4    

(10) 顺序表的销毁
//顺序表的销毁
void SLDestroy(SL* ps) {
	assert(ps);			//断言,防止传入空指针
	if (ps->arr) {		//如果动态数组arr非空,就把arr释放
		free(ps->arr);
		ps->arr = NULL;	//置空,避免野指针
	}
	ps->capacity = 0;	//空间容量为0
	ps->size = 0;		//有效数据为0
}
(11)打印顺序表
//打印顺序表
void SLPrint(SL* ps) {
	assert(ps);			//断言,防止传入空指针
	for (int i = 0; i < ps->size; i++) //遍历顺序表
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

片尾

我们今天学习了什么是顺序表以及如何实现顺序表,希望看完这篇文章能对友友们有所帮助 !   !   !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !

阅读全部

相关推荐

  8. 数据结构之顺序表

    2024-04-21 06:32:05       31 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-21 06:32:05       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-21 06:32:05       101 阅读

  9. 在Django里面运行非项目文件

    2024-04-21 06:32:05       82 阅读

  19. Python语言-面向对象

    2024-04-21 06:32:05       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-21 06:32:05       85 阅读

热门阅读

  2. 为什么redis在进行持久化存储的过程中使用Fork（）

    2024-04-21 06:32:05       30 阅读

  11. html5与css3前端学习笔记

    2024-04-21 06:32:05       29 阅读

  14. 分类与预测算法评价的介绍

    2024-04-21 06:32:05       35 阅读

  15. MySQL数据加密，模糊查询

    2024-04-21 06:32:05       31 阅读

  18. mysql和Nosql到底有什么区别，分别应用与什么场景？

    2024-04-21 06:32:05       37 阅读

  22. 优雅的最大公约数函数

    2024-04-21 06:32:05       33 阅读

  27. C++11统一列表初始化，initializer_list

    2024-04-21 06:32:05       30 阅读

  28. 代码随想录-哈希表 | 242 有效的字母异位词

    2024-04-21 06:32:05       35 阅读

  29. Rust常用特型之TryFrom和TryInto特型

    2024-04-21 06:32:05       36 阅读