数据结构之顺序表的相关知识点及应用

 个人主页（找往期文章包括但不限于本期文章中不懂的知识点）：我要学编程(ಥ_ಥ)-CSDN博客

目录

顺序表的概念及结构

顺序表的分类

顺序表的实现 

在顺序表中增加数据 

在顺序表中删除数据 

在顺序表中查找数据 

顺序表源码

 

顺序表的概念及结构

在了解顺序表之前，得先知道一个东西：线性表。线性表（linear list）是n个具有相同特性的数据元素的有限序列。简单理解就是：线性表指的是具有部分相同特性的一类数据结构的集合。例如：蔬菜分为绿叶类、瓜类、菌菇类。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。 如何理解逻辑结构和物理结构？我们去超市买东西的时候，去付款时要排队，假设有很多人，也就意味着我们需要排成一条对去付款。这是在逻辑上就是一条线性的（我们下意识认为，是理想的），但是实际上在站队时不一定是线性的（现实情况）。但是顺序表在逻辑结构和物理结构上都是线性的。这是因为顺序表的底层实现逻辑是数组。我们知道数组在内存上是连续存放的（实际情况）。

注意：顺序表的底层虽然是数组，但是却是在数组的基础之上对数组进行了封装，实现了增删查改的一些功能。

顺序表的分类

我们知道数组有两种：一种是定长数组，也就是空间大小不可变化，是固定的；还有一种是变长数组，这个变长数组是我们用动态内存开辟函数申请来的（注意区分C99中引入的变长数组）。

根据数组的不同，顺序表也分为两种：静态顺序表（大小不可变），动态顺序表（大小可变）。

顺序表的实现 

这两种顺序表一比较，肯定是第二种的优势明显一些，同样在项目中，动态顺序表的应用远远大于静态顺序表。下面我们就来学习动态顺序表的实现。

首先创建三个文件：SeqList.h  —— 顺序表的头文件  SeqList.c  —— 顺序表的实现  test.c——>测试顺序表

顺序表的创建：

typedef struct SeqList
{
	SLDataType* arr;//数组指针
	int size;//记录当前有效的空间大小
	int capacity;//记录当前总空间大小
}SL;//由于struct SeqList太长，比较麻烦，因此就重新定义

由于数组的类型是暂定为int，后续如果要改动的话，不是很方便，因此也是重定义。

typedef int SLDataType;//数组不一定是int类型

顺序表创建完了之后，就得开始实现它的基本功能：增 删 查 改。

在实现上面那些基本功能之前，我们肯定得把这个顺序表进行初始化。 

//初始化顺序表
void InitSeqList(SL* ps)//由于要改变顺序表，所以传地址
{
	ps->arr = NULL;//没为数组分配内存空间
	ps->capacity = 0;
	ps->size = 0;
}

在顺序表中增加数据 

接下来就开始实现增加数据，这个增加稍微有所不同：是在指定的位置增加数据。

我们先来实现两种特殊的情况：头插和尾插。头插是在顺序表的第一个位置（数组下标为0的位置）插入（增加）数据；尾插是在顺序表的有效数据的末尾插入（增加）数据。

首先，来实现头插：（数据从后往前覆盖）

//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给BASE(4)个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}

注意：在比较大型的项目中，我们写一些功能代码时，一定要去检查功能是否完整。比如：这里我们写这个头插功能的代码时，写完之后一定要去打印结果，看看是否满足我们的要求。 

头插写完就开始写尾插了。

//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->capacity == ps->size)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)//还没分配空间
		{
			newcapacity = BASE;
		}
		else
		{
			newcapacity = 2 * ps->capacity;
		}
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		tmp = NULL;
		ps->capacity = newcapacity;
	}
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}

通过观察上面两个代码，我们会发现那个判断是否需要增容的部分是一样的，因此我们就可以把这个判断是否需要增容的部分写成一个函数（可以只判断，也可以把增容的部分也写进去）。

那么上面的代码就可以简化成下面的样子。 

//判断是否需要增容（如果需要，则直接自动增容）
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给4个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}


//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}


//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}

两种特殊的插入写完之后，就得开始写指定插入，就是说在指定的位置插入数据。 （和头插一样，从后往前覆盖）

//在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//arr[2] = arr[1]; 
	}
	ps->arr[pos] = x;
	ps->size++;
}

在顺序表中删除数据 

接下来就是删除数据。同样删除数据也根据上面的方式来先实现特殊方式：头删和尾删。 

注意删除数据时，一定要判断是否有数据。

先来看头删。（数据从前往后覆盖）

void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size);//看看有没有数据
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

尾删就比较简单了。 

void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);
	//ps->arr[size-1] = 0; //这一步可有可无
	ps->size--;
}

接下来就是写在指定位置删除数据。 

在顺序表中查找数据 

最后，我们就要实现在顺序表中查找数据。 

找数据的话，就是简单的循环找就行了。

//在顺序表中查找数据
int SLFind(SL* ps, SLDataType x)
{
    assert(ps);
   	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到
}

上面就是顺序表的全部逻辑以及实现。

顺序表源码

下面是顺序表的源码：

SeqList.c

#include "SeqList.h"

//初始化顺序表
void InitSeqList(SL* ps)
{
	ps->arr = NULL;//没为数组分配内存空间
	ps->capacity = 0;
	ps->size = 0;
}


//销毁顺序表
void SLDestroy(SL* ps)
{
	if (ps->arr)//有可能我们还没有使用（为空）
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}


//打印顺序表
void SLPrint(const SL* ps)//只是打印不想被更改数据
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");//可以选择换行，不写也没关系
}


//判断是否需要增容（如果需要，则直接自动增容）
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给4个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}


//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);//ps是一个指针（没有&，因此也是一个值）
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}


//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}


//在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//arr[2] = arr[1]; 
	}
	ps->arr[pos] = x;
	ps->size++;
}


//删除顺序表头部的数据
void SLPopFront(SL* ps)
{
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}


//删除顺序表尾部的数据
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//ps->arr[size-1] = 0; //这一步可有可无
	ps->size--;
}


//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}


//在顺序表中查找数据
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到
}

SeqList.h 

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

#define BASE 4

typedef int SLDataType;//数组不一定是int类型

typedef struct SeqList
{
	SLDataType* arr;//数组指针（）
	int size;//记录当前有效的空间大小
	int capacity;//记录当前总空间大小
}SL;


void InitSeqList(SL* ps);//初始化顺序表

void SLDestroy(SL* ps);//销毁顺序表

void SLPrint(const SL* ps);//打印顺序表的数据

void SLPushFront(SL* ps, SLDataType x);//在顺序表的头部插入数据

void SLPushBack(SL* ps, SLDataType x);//在顺序表的末尾插入数据

void SLInsert(SL* ps, int pos, SLDataType x);//在指定位置插入数据

void SLPopFront(SL* ps);//删除顺序表头部的数据

void SLPopBack(SL* ps);//删除顺序表尾部的数据

void SLErase(SL* ps, int pos);//删除指定位置的数据

int SLFind(SL* ps, SLDataType x);//在顺序表中查找数据

好啦！本期数据结构顺序表的学习就到此为止啦！我们下一期再一起学习吧！ 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/520178.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

浮动辊位移测量功能块(CODESYS ST代码)

浮动辊位移测量功能块(CODESYS ST代码)

1、张力测量+标定(ST代码) 张力测量+标定(ST代码)_动态舞轮控制张力-CSDN博客文章浏览阅读804次。跳舞轮对应张力调节范围，我们可以通过改变气缸的气压方式间接改变，张力跳舞轮在收放卷闭环控制上的详细应用，可以参看下面的文章链接，这里我们主要讨论精密可调气阀的模拟量…
阅读更多...
Java | Leetcode Java题解之第6题Z字形变换

Java | Leetcode Java题解之第6题Z字形变换

题目&#xff1a; 题解&#xff1a; class Solution {public String convert(String s, int numRows) {int n s.length(), r numRows;if (r 1 || r > n) {return s;}int t r * 2 - 2;int c (n t - 1) / t * (r - 1);char[][] mat new char[r][c];for (int i 0, x …
阅读更多...
[Spring Cloud] gateway全局异常捕捉统一返回值

[Spring Cloud] gateway全局异常捕捉统一返回值

文章目录 处理转发失败的情况全局参数同一返回格式操作消息对象AjaxResult返回值状态描述对象AjaxStatus返回值枚举接口层StatusCode 全局异常处理器自定义通用异常定一个自定义异常覆盖默认的异常处理自定义异常处理工具 在上一篇章时我们有了一个简单的gateway网关 [Spring C…
阅读更多...
比selenium体验更好的ui自动化测试工具: cypress介绍

比selenium体验更好的ui自动化测试工具: cypress介绍

话说 Cypress is a next generation front end testing tool built for the modern web. And Cypress can test anything that runs in a browser.Cypress consists of a free, open source, locally installed Test Runner and a Dashboard Service for recording your tests.…
阅读更多...
leetcode077——排序链表

leetcode077——排序链表

题目&#xff1a; 给定链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 1&#xff1a; 输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4] 思路&#xff1a; 1.找链表中点【使用快慢指针 慢指针每次移动一步&#xff0c;快指针每…
阅读更多...
基于单片机12864的出租车计价器设计

基于单片机12864的出租车计价器设计

**单片机设计介绍&#xff0c;基于单片机12864的出租车计价器设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机和12864液晶显示屏的出租车计价器设计&#xff0c;主要是利用单片机的强大控制能力和液晶显示屏的直观显示特性&…
阅读更多...
牛客网BC-125 序列中整数去重复（难题讲解）

牛客网BC-125 序列中整数去重复（难题讲解）

题目如下 --------------------------------------------------------------------------------------------------------------------------------- 题目讲解&#xff08;思路&#xff09; -------------------------------------------------------------------------------…
阅读更多...
单一职责原则

单一职责原则

1.1 阅读干吗不直接用手机&#xff1f; 电子阅读器比较专注&#xff0c;而手机功能比较多&#xff0c;影响专注。 1.2 手机不纯粹 手机确实很方便。但是现在的手机就是一台小型智能电脑。它不仅能打电话&#xff0c;还能听音乐、看电影电视、与个人交流、与一群人群聊&#…
阅读更多...
基于java+SpringBoot+Vue的大学生入学审核系统设计与实现

基于java+SpringBoot+Vue的大学生入学审核系统设计与实现

基于javaSpringBootVue的大学生入学审核系统设计与实现 开发语言: Java 数据库: MySQL技术: SpringBoot VUE工具: IDEA/Eclipse、Navicat、Maven 系统展示 前台展示 入学办理模块&#xff1a;学生可以提交入学申请并跟踪入学办理进度。 后台展示 学生管理模块&#xff1…
阅读更多...
【Docker系列】在 Linux 上安装 Docker Compose 的简明步骤

【Docker系列】在 Linux 上安装 Docker Compose 的简明步骤

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
前端学习之DOM编程案例：抽奖案例

前端学习之DOM编程案例：抽奖案例

代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>抽奖案例</title><style>*{margin: 0;padding: 0;}</style> </head> <body><div id"container"&g…
阅读更多...
【放假第3天】幻兽帕鲁 雾锁王国 我的世界 游戏云服务器选购指南 附最新价格对比表 新手、小白秒懂

【放假第3天】幻兽帕鲁 雾锁王国 我的世界 游戏云服务器选购指南 附最新价格对比表 新手、小白秒懂

更新日期&#xff1a;4月6日&#xff08;半年档 价格回调&#xff0c;京东云采购季持续进行&#xff09; 本文纯原创&#xff0c;侵权必究 【云服务器推荐】价格对比&#xff01;阿里云 京东云 腾讯云 选购指南视频截图 《最新对比表》已更新在文章头部—腾讯云文档&#xf…
阅读更多...
LeetCode 1483.树节点的第 K 个祖先：树上倍增

LeetCode 1483.树节点的第 K 个祖先：树上倍增

【LetMeFly】1483.树节点的第 K 个祖先&#xff1a;树上倍增 力扣题目链接&#xff1a;https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/ 给你一棵树&#xff0c;树上有 n 个节点&#xff0c;按从 0 到 n-1 编号。树以父节点数组的形式给出&#xff0c;其中 paren…
阅读更多...
redis主从复制与哨兵模式

redis主从复制与哨兵模式

redis主从复制 Redis主从复制&#xff08;Redis replication&#xff09;是Redis提供的一种数据备份和故障转移机制。通过主从复制&#xff0c;可以将一个Redis服务器&#xff08;主节点&#xff09;的数据复制到一个或多个Redis服务器&#xff08;从节点&#xff09;。这样做…
阅读更多...
【面经】interrupt()、interrupted()和isInterrupted()的区别与使用

【面经】interrupt()、interrupted()和isInterrupted()的区别与使用

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;面经 ⛺️稳中求进&#xff0c;晒太阳 interrupt方法 如果打断线程正在sleep&#xff0c;wait&#xff0c;join会导致被打断的线程抛出InterruptedException&#xff0c;并清除打断标记。如…
阅读更多...
FebHost：什么是土耳其.TR域名？

FebHost：什么是土耳其.TR域名？

当前互联网高速发展,一个国家的顶级域名已成为其网络形象的重要标识。近期,土耳其国家顶级域名”.TR”引起了广泛关注,成为业界热议的话题。 作为代表土耳其共和国的国家顶级域名(ccTLD),.TR域名于1991年首次引入,由土耳其科技和信息技术部负责管理。除了常见的”.com.tr”、”…
阅读更多...
画图理解JVM相关内容

画图理解JVM相关内容

文章目录 1. JVM视角下&#xff0c;内存划分2. 类内存分布硬核详解1. 获取堆内存参数2. 扫描堆内存&#xff0c;定位实例3. 查看实例所在地址的数据4. 找到实例所指向的类信息的地址5. 查看class信息6. 结论 3. Java的对象创建流程4. 垃圾判别算法4.1 引用计数法4.2 可达性分析…
阅读更多...
GD32F470_光敏电阻光照传感器模块移植手册

GD32F470_光敏电阻光照传感器模块移植手册

2.3 光敏电阻光照传感器 光敏电阻是用硫化隔或硒化隔等半导体材料制成的特殊电阻器&#xff0c;其工作原理是基于内光电效应。随着光照强度的升高&#xff0c;电阻值迅速降低&#xff0c;由于光照产生的载流子都参与导电&#xff0c;在外加电场的作用下作漂移运动&#xff0c;电…
阅读更多...
如何从文本数据中提取子列表

如何从文本数据中提取子列表

提取文本数据中的子列表可以通过各种方式实现&#xff0c;具体取决于文本数据的结构和提取子列表的条件。例如&#xff1a;使用字符串操作和条件判断、使用正则表达式、使用自然语言处理工具、使用自定义解析器等几种模式&#xff0c;那么对于在日常使用中会有那些问题呢 &…
阅读更多...
ssm基于HTML5的出租车管理系统论文

ssm基于HTML5的出租车管理系统论文

摘 要 网络技术和计算机技术发展至今&#xff0c;已经拥有了深厚的理论基础&#xff0c;并在现实中进行了充分运用&#xff0c;尤其是基于计算机运行的软件更是受到各界的关注。加上现在人们已经步入信息时代&#xff0c;所以对于信息的宣传和管理就很关键。因此出租车信息的管…
阅读更多...
最新文章

Copyright @ 2022~2023