顺序表的讲解与实现

顺序表的讲解与实现

  • 一、顺序表的概念及结构
  • 二、顺序表分类
    • 顺序表和数组的区别
    • 顺序表分类
      • 静态顺序表
      • 动态顺序表
  • 三、动态顺序表的实现(使用VS2022)
    • 1.初始化、销毁、打印内容
    • 2.检查扩容
    • 3.尾部插入、尾部删除、头部插入、头部删除
      • 尾部插入
      • 尾部删除
      • 头部插入
      • 头部删除
    • 4.指定插入、指定删除、查找
      • 指定插入
      • 指定删除
      • 查找
  • 四、代码优化
  • 五、完整 SeqList.c 代码

一、顺序表的概念及结构

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表分类

顺序表和数组的区别

顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口。

顺序表分类

静态顺序表

概念：使用定长数组存储元素

#define N 10					// 长度恒定

typedef int SeqListDataType;

typedef struct SeqList
{
	SeqListDataType arr[N];		// 长度恒定
	int size;
} SeqList, *pSeqList;

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。

动态顺序表

概念：按需申请，避免空间进一步浪费

typedef int SeqListDataType;

typedef struct SeqList
{
	SeqListDataType* arr;		// 指针
	int size;					// 当前容量
	int capacity;				// 总容量
} SeqList, * pSeqList;

三、动态顺序表的实现(使用VS2022)

这里以实现动态顺序表为例，开发工具为VS2022。

动态顺序表常用的增删改查等接口包括：

1.初始化、销毁、打印内容

2.检查扩容

3.尾部插入、尾部删除、头部插入、头部删除

4.指定插入、指定删除、查找

在 SeqList.h 中：

#pragma once

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

// 初始化容量
#define INIT_CAPACITY 4

// 扩容倍率
#define EXPANSION_MULTIPLE 2

typedef int SeqListDataType;

typedef struct SeqList
{
	SeqListDataType* arr;
	int size;
	int capacity;
} SeqList, * pSeqList;

// 初始化、销毁、打印
void SeqListInit(pSeqList ps);

void SeqListDestroy(pSeqList ps);

void SeqListPrint(pSeqList ps);

// 检查扩容
void CheckCapacity(pSeqList ps);

// 尾插尾删、头插头删
void SeqListPushBack(pSeqList ps, SeqListDataType x);

void SeqListPopBack(pSeqList ps);

void SeqListPushFront(pSeqList ps, SeqListDataType x);

void SeqListPopFront(pSeqList ps);

// 插入、删除、查找
void SeqListInsert(pSeqList ps, int pos, SeqListDataType x);

void SeqListErase(pSeqList ps, int pos);

int SeqListFind(pSeqList ps, SeqListDataType x);

在 SeqList.c 中：

1.初始化、销毁、打印内容

#include "SeqList.h"

// 初始化、销毁、打印
void SeqListInit(pSeqList ps)
{
	assert(ps);			// 防止进入空指针

	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListDestroy(pSeqList ps)
{
	assert(ps);

	free(ps->arr);
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPrint(pSeqList ps)
{
	assert(ps);

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

2.检查扩容

// 检查扩容
void CheckCapacity(pSeqList ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * EXPANSION_MULTIPLE;

		// ps->arr 为空时，realloc 会转为 malloc
		SeqListDataType* temp = (SeqListDataType*)realloc(ps->arr, newCapacity * sizeof(SeqListDataType));
		if (temp == NULL)
		{
			perror("realloc failed");
			return;
		}

		// 更新
		ps->arr = temp;
		ps->capacity = newCapacity;
	}
}

3.尾部插入、尾部删除、头部插入、头部删除

尾部插入

void SeqListPushBack(pSeqList ps, SeqListDataType x)
{
	assert(ps);					

	CheckCapacity(ps);			// 检查容量，不足扩容

	ps->arr[ps->size++] = x;	// 尾插
}

尾部删除

void SeqListPopBack(pSeqList ps)
{
	assert(ps);
	assert(ps->size > 0);	// 防止为空

	--ps->size;				// 直接--忽略掉当前位置
}

头部插入

void SeqListPushFront(pSeqList ps, SeqListDataType x)
{
	assert(ps);

	CheckCapacity(ps);

	for (int end = ps->size; end > 0; --end)
	{
		ps->arr[end] = ps->arr[end - 1];
	}
	ps->arr[0] = x;
	++ps->size;
}

在这里插入图片描述
在这里插入图片描述

头部删除

void SeqListPopFront(pSeqList ps)
{
	assert(ps);
	assert(ps->size > 0);

	for (int begin = 0; begin < ps->size - 1; ++begin)
	{
		ps->arr[begin] = ps->arr[begin + 1];
	}
	--ps->size;
}

在这里插入图片描述
在这里插入图片描述

4.指定插入、指定删除、查找

指定插入

void SeqListInsert(pSeqList ps, int pos, SeqListDataType x)
{
	assert(ps);
	assert(0 <= pos && pos <= ps->size); // 当 pos == ps->size 可以实现尾插 

	CheckCapacity(ps);

	for (int end = ps->size; end > pos; --end)
	{
		ps->arr[end] = ps->arr[end - 1];
	}
	ps->arr[pos] = x;
	++ps->size;
}

指定插入与头部插入同理，只需将结束位置改为 pos 指定的位置。

指定删除

void SeqListErase(pSeqList ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	assert(0 <= pos && pos < ps->size);	// 尾删不可删 pos == ps->size 位置上的

	for (int begin = pos; begin < ps->size - 1; ++begin)
	{
		ps->arr[begin] = ps->arr[begin + 1];
	}
	--ps->size;
}

指定删除与头部删除同理，只需将开始位置改为 pos 指定的位置。

查找

int SeqListFind(pSeqList ps, SeqListDataType x)
{
	assert(ps);
	assert(ps->size > 0);
	// 找到返回下标，反之返回 -1
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

四、代码优化

指定插入 包含 尾插头插，指定删除 包含 尾删头删。可以复用两者，提高代码复用率。

// 尾插尾删、头插头删
void SeqListPushBack(pSeqList ps, SeqListDataType x)
{
	SeqListInsert(ps, ps->size, x);
}

void SeqListPopBack(pSeqList ps)
{
	SeqListErase(ps, ps->size - 1);
}

void SeqListPushFront(pSeqList ps, SeqListDataType x)
{
	SeqListInsert(ps, 0, x);
}

void SeqListPopFront(pSeqList ps)
{
	SeqListErase(ps, 0);
}

五、完整 SeqList.c 代码

#include "SeqList.h"

// 初始化、销毁、打印
void SeqListInit(pSeqList ps)
{
	assert(ps);

	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListDestroy(pSeqList ps)
{
	assert(ps);

	free(ps->arr);
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPrint(pSeqList ps)
{
	assert(ps);

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

// 检查扩容
void CheckCapacity(pSeqList ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * EXPANSION_MULTIPLE;

		// ps->arr 为空时，realloc 会转为 malloc
		SeqListDataType* temp = (SeqListDataType*)realloc(ps->arr, newCapacity * sizeof(SeqListDataType));
		if (temp == NULL)
		{
			perror("realloc failed");
			return;
		}

		// 更新
		ps->arr = temp;
		ps->capacity = newCapacity;
	}
}

// 尾插尾删、头插头删
void SeqListPushBack(pSeqList ps, SeqListDataType x)
{
	SeqListInsert(ps, ps->size, x);
}

void SeqListPopBack(pSeqList ps)
{
	SeqListErase(ps, ps->size - 1);
}

void SeqListPushFront(pSeqList ps, SeqListDataType x)
{
	SeqListInsert(ps, 0, x);
}

void SeqListPopFront(pSeqList ps)
{
	SeqListErase(ps, 0);
}

// 插入、删除、查找
void SeqListInsert(pSeqList ps, int pos, SeqListDataType x)
{
	assert(ps);
	assert(0 <= pos && pos <= ps->size);

	CheckCapacity(ps);

	for (int end = ps->size; end > pos; --end)
	{
		ps->arr[end] = ps->arr[end - 1];
	}
	ps->arr[pos] = x;
	++ps->size;
}

void SeqListErase(pSeqList ps, int pos)
{
	assert(ps);
	assert(ps->size > 0);
	assert(0 <= pos && pos < ps->size);

	for (int begin = pos; begin < ps->size - 1; ++begin)
	{
		ps->arr[begin] = ps->arr[begin + 1];
	}
	--ps->size;
}

int SeqListFind(pSeqList ps, SeqListDataType x)
{
	assert(ps);
	assert(ps->size > 0);

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

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

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

相关文章

Go语言 几种常见的IO模型用法 和 netpoll与原生GoNet对比

Go语言 几种常见的IO模型用法 和 netpoll与原生GoNet对比

【go基础】16.I/O模型与网络轮询器netpoller_go中的多路io复用模型-CSDN博客 字节开源的netPoll多路复用器源码解析-CSDN博客 一、几种常见的IO模型 1. 阻塞I/O (1) 解释&#xff1a; 用户调用如accept、read等系统调用&#xff0c;向内核发起I/O请求后&#xff0c;应用程序…
阅读更多...
装机必备——鲁大师安装教程

装机必备——鲁大师安装教程

装机必备——鲁大师安装教程 软件下载 软件名称&#xff1a;鲁大师 软件语言&#xff1a;简体中文 软件大小&#xff1a;144.75M系统要求&#xff1a;Windows7或更高&#xff0c; 32/64位操作系统 硬件要求&#xff1a;CPU2GHz &#xff0c;RAM2G或更高 下载通道①迅雷云盘丨…
阅读更多...
探究 Meme 的金融与社交属性

探究 Meme 的金融与社交属性

原文标题&#xff1a;《A Social and Financial Study of Memecoins》撰文&#xff1a;Andrew Hong编译&#xff1a;Chris&#xff0c;Techub News 每一个市场周期都伴随着 Meme 代币的出现。一群人围绕着某个 Meme 集结起来&#xff0c;暂时抬高了某个资产的价格&#xff08;从…
阅读更多...
YOLOv5白皮书-第Y5周：yolo.py文件解读

YOLOv5白皮书-第Y5周：yolo.py文件解读

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 一、环境 语言&#xff1a;Python3、Pytorch开发环境电脑系统&#xff1a;Windows 10语言环境&#xff1a;Python 3.9.2编译器&#xff1a;VS Code显卡&#…
阅读更多...
LeetCode刷题之HOT100之组合总和

LeetCode刷题之HOT100之组合总和

2024/6/3 周一&#xff0c;工作日的第一天。昨晚梦到被导师说去实验室不积极哈哈哈&#xff0c;风扇开到二级&#xff0c;早上被吹醒。买的书马上快要到了。上午刚来准备刷题&#xff0c;结果去搞了一下数据库sql&#xff0c;做的差不多了&#xff0c;还差点格式转换就差不多出…
阅读更多...
暴力数据结构之排序大杂烩

暴力数据结构之排序大杂烩

1. 冒泡排序&#xff1a;O(N^2) 逻辑解析&#xff1a; 冒泡排序并没有什么实际意义&#xff0c;但是有教学意义&#xff0c;相信大部分小白在学习的初期第一个接触的排序就是冒泡排序。那么接下来我们了解一下他的底层逻辑&#xff1a; 冒泡排序顾名思义就是将最大&#xff08…
阅读更多...
力扣 101. 对称二叉树

力扣 101. 对称二叉树

给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/ bool check(struct TreeNode* L,struct TreeNode* R){if(!L&…
阅读更多...
匠心独运，B 端系统 UI 演绎华章之美

匠心独运，B 端系统 UI 演绎华章之美

匠心独运&#xff0c;B 端系统 UI 演绎华章之美
阅读更多...
kettle从入门到精通 第六十四课 ETL之kettle kettle中执行SQL脚本步骤，使用需当心

kettle从入门到精通 第六十四课 ETL之kettle kettle中执行SQL脚本步骤，使用需当心

1、群里有不定时会有同学反馈执行SQL脚本步骤使用有问题&#xff0c;那么咱们今天一起来学习下该步骤。trans中的执行SQL脚本有两方面功能&#xff0c;使用时需小心&#xff0c;不然很容易踩坑。 官方定义&#xff1a; 翻译&#xff1a; 您可以使用此步骤执行 SQL 脚本&#…
阅读更多...
kafka集群内外网分流方案——筑梦之路

kafka集群内外网分流方案——筑梦之路

前言 在现代分布式系统架构中&#xff0c;Kafka作为一款高性能的消息队列系统&#xff0c;广泛应用于大数据处理、实时流处理以及微服务间的异步通信场景。特别是往往企业级应用中&#xff0c;业务网段和内网通信网段不是同一个网段&#xff0c;内网的机器想要访问业务数据只能…
阅读更多...
考研人注意了：六月份保底进度+复习规划！

考研人注意了：六月份保底进度+复习规划！

六月开始准备考研确实有点晚了&#xff0c;因为大家基本上上都是3月份开始的 开始的比别人晚&#xff0c;学习的时间就会比较紧张&#xff0c;但是不要怕&#xff0c;考研并不是比谁学的时间长&#xff0c;而是比谁学的效果好&#xff0c;就算是六月份开始&#xff0c;只要学习…
阅读更多...
三、基于图像分类预训练编码及图神经网络的预测模型 【框图+源码】

三、基于图像分类预训练编码及图神经网络的预测模型 【框图+源码】

背景&#xff1a; 抽时间补充&#xff0c;先挖个坑。 一、模型结构 二、源码
阅读更多...
python结构化模式匹配switch-case，Python 3.10中引入，Python的模式匹配（pattern matching）语法

python结构化模式匹配switch-case，Python 3.10中引入，Python的模式匹配（pattern matching）语法

增加了采用模式加上相应动作的 match 语句 和 case 语句 的形式的结构化模式匹配。 模式由序列、映射、基本数据类型以及类实例构成。 模式匹配使得程序能够从复杂的数据类型中提取信息、根据数据结构实现分支&#xff0c;并基于不同的数据形式应用特定的动作。 语法与操作 模…
阅读更多...
系统安全及应用11

系统安全及应用11

一个新的服务器到手之后&#xff0c;部署服务器的初始化 1、配置IP地址 网关 dns解析&#xff08;static&#xff09;内网和外网 2、安装源外网&#xff08;在线即可&#xff09;&#xff0c;内网&#xff08;只能用源码包编译安装&#xff09; 3、磁盘分区&#xff0c;lvm …
阅读更多...
coze自定义插件调用3

coze自定义插件调用3

1&#xff0c;打开我的空间&#xff1b; 2&#xff0c;编辑&#xff0c;选择快捷指令 3&#xff0c;编辑指令 4&#xff0c;实际测试【输入框多了一个按钮“查询基础信息”&#xff0c;点击查询基础信息&#xff0c;提示输入缴费卡号&#xff0c;提交后如下图】
阅读更多...
插入排序（直接插入排序与希尔排序）----数据结构-排序①

插入排序（直接插入排序与希尔排序）----数据结构-排序①

1、插入排序 1.1 插入排序的基本思想 将待排序的元素按其数值的大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的元素插入完为止&#xff0c;就可以得到一个新的有序序列 。 实际上在我们的日常生活中&#xff0c;插入排序的应用是很广泛的&#xff0c;例如我…
阅读更多...
从墙的功能出发 -分析欧特克Revit和广联达数维的差别

从墙的功能出发 -分析欧特克Revit和广联达数维的差别

欧特克&#xff08;Autodesk&#xff09;在三维建模软件领域的影响力是有目共睹的&#xff0c;它是行业的头部产商&#xff0c;拥有众多的高质量的三维设计软件&#xff0c;涵盖了建筑设计、机械设计与制造和电影文娱行业。Revit是其发布的建筑三维建模软件&#xff0c;也是BIM…
阅读更多...
老黄自己卷自己！GPU要一年更新一代！预告新动作：AI工厂将吞噬一切

老黄自己卷自己！GPU要一年更新一代！预告新动作：AI工厂将吞噬一切

站在 AI 时代风口浪尖的弄潮儿英伟达又为大家带来了一场科技饕餮盛宴&#xff01; 昨晚 7 点&#xff0c;坐标中国台湾大学体育场&#xff0c;英伟达 CEO 黄仁勋为世界带来了一场名为 The Dawn of a New Industrial Revolution &#xff08;揭开新工业革命序幕&#xff09;的演…
阅读更多...
IDEA 常用技巧

IDEA 常用技巧

1、代码块整体移动 选中&#xff0c;tab整体右移选中&#xff0c;shifttab整体左 移 2、统一修改变量 3.方法分割线 seting >> editor >> apperance >> show method separators 4、快捷键 构造器、set与get方法、方法重写、toString 等快捷操 鼠标停留在…
阅读更多...
微信公众号开发（五）：私信日志记录

微信公众号开发（五）：私信日志记录

之前的开发内容里&#xff0c;基本是基本配置和回复设置&#xff0c;为了之后看用户/粉丝什么样的功能使用的最多&#xff0c;需要增加私信的日志记录&#xff1a; 1、日志表 首先&#xff0c;要在mysql里建表 主要字段&#xff1a;用户id、公众号id、时间、私信类型、私信内…
阅读更多...
最新文章

Copyright @ 2022~2023