C语言.数据结构.顺序表

1.顺序表的概念及结构

1.1线性表

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

2.顺序表的分类

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

  • 顺序表的分类

    • 静态顺序表
      概念：使用定长数组储存元素
      在这里插入图片描述

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

    • 动态顺序表
      在这里插入图片描述

优先使用动态顺序表，因为其更加灵活。

3.动态顺序表的实现

3.1文件的选取

  1. 头文件.h
    定义顺序表的定义、声明顺序表的方法
  2. 源文件.c
    实现顺序表的方法
  3. 测试文件.c
    检测代码是否能够按照预期运行

3.2动态顺序表的定义：

//定义顺序表的结构
typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

3.2顺序表的打印：

//顺序表的打印
void SLPrint(SL ps)
{
	//遍历顺序表
	for (int i = 0; i < ps.size; i++)
	{
		printf("%d ", ps.arr[i]);
	}
	printf("\n");
}

3.3顺序表的查找

//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
	//遍历顺序表
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到后，就返回下标
			return i;
		}
	}
	//遍历一遍，没有找到，就返回-1；（数组下标不能为负数）
	return -1;
}

3.4申请空间

//申请空间
void SLCheckCapacity(SL* ps)
{
	//再插入数据前，先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序
		}
		//走到这，证明申请空间成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

解释：

  1. capacity = size的时候，证明顺序表的空间与有效数据一样了，已经空间塞满，再插入数据就插不进去了。
  2. int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

1）假如顺序表空间为零，就直接赋值为4个空间大小。
2）假如顺序表空间不为零，就以顺序表的空间大小的2倍申请空间。

3.4顺序表的初始化

//顺序表初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

理解：

  1. 顺序表的底层是数组，arr代表的是数组首元素的地址，先置换为空。
  2. 再让顺序表的空间大小(capacity)置为0，也让有效数据(size)置为空。

3.5顺序表的尾部插入

//尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//等价于assert(ps != NULL)
	//再插入数据前，先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序
		}
		//走到这，证明申请空间成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//进行尾插
	ps->arr[ps->size++] = x;
}

解释：

  1. 问题：一次要申请多大的空间？

增容通常来讲是成倍数的增加，一般是2或3倍。 实际上是数学推理出来的。假若频繁的增容，则会造成程学的运行效率大大的降低。

画图分析：

在这里插入图片描述

3.7顺序表的头部插入

//头部插入
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];
	}
	//头部插入
	ps->arr[0] = x;
	//有效数据也得自增一位
	ps->size++;
}

画图分析：

在这里插入图片描述

3.7顺序表的尾部删除

//尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//有效数据不为空
	//直接使有效数据减少
	--ps->size;
}

画图分析：

在这里插入图片描述

3.8顺序表的头部删除

//头部删除
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];//arr[size-2] = arr[size-1]
	}
	//有效数据自减1
	ps->size--;
}

画图分析：

在这里插入图片描述

3.9在指定位置之前插入数据

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//pos的范围要在顺序表的size范围之内
	assert(pos >= 0 && pos <= ps->size);
	//在插入数据前，看看顺序表的空间够不够
	SLCheckCapacity(ps);
	//让pos及之后的数据整体往后移动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//
	}
	//空出pos位置，插入数据
	ps->arr[pos] = x;
	//有效数据自增1
	ps->size++;
}

画图分析：

在这里插入图片描述

3.10在指定为位置删除数据

//在指定为位置删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//遍历顺序表，让pos之后的数据整体往前移动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	//有效数据自减1
	ps->size--;
}

画图分析：

在这里插入图片描述

3.11顺序表的销毁

//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)//等价于if(ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

4.整体代码展示

SqeList.h

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

//定义顺序表的结构
typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据个数
	int capacity;//空间大小
}SL;

//顺序表的打印
void SLPrint(SL ps);

//顺序表的查找
int SLFind(SL* ps, SLDataType x);

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

//尾部插入
void SLPushBack(SL* ps, SLDataType x);

//头部插入
void SLPushFront(SL* ps, SLDataType x);

//尾部删除
void SLPopBack(SL* ps);

//头部删除
void SLPopFront(SL* ps);

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

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

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

SqeList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//顺序表的打印
void SLPrint(SL ps)
{
	//遍历顺序表
	for (int i = 0; i < ps.size; i++)
	{
		printf("%d ", ps.arr[i]);
	}
	printf("\n");
}

//申请空间
void SLCheckCapacity(SL* ps)
{
	//再插入数据前，先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序
		}
		//走到这，证明申请空间成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
	//遍历顺序表
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			//找到后，就返回下标
			return i;
		}
	}
	//遍历一遍，没有找到，就返回-1；（数组下标不能为负数）
	return -1;
}

//顺序表初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

//尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//等价于assert(ps != NULL)
	//再插入数据前，先看空间够不够
	if (ps->capacity == ps->size)
	{
		//申请空间
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);//直接退出程序
		}
		//走到这，证明申请空间成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//进行尾插
	ps->arr[ps->size++] = x;
}

//头部插入
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];
	}
	//头部插入
	ps->arr[0] = x;
	//有效数据也得自增一位
	ps->size++;
}

//尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//有效数据不为空
	//直接使有效数据减少
	--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];//arr[size-2] = arr[size-1]
	}
	//有效数据自减1
	ps->size--;
}

//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//pos的范围要在顺序表的size范围之内
	assert(pos >= 0 && pos <= ps->size);
	//在插入数据前，看看顺序表的空间够不够
	SLCheckCapacity(ps);
	//让pos及之后的数据整体往后移动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//
	}
	//空出pos位置，插入数据
	ps->arr[pos] = x;
	//有效数据自增1
	ps->size++;
}

//在指定为位置删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//遍历顺序表，让pos之后的数据整体往前移动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	//有效数据自减1
	ps->size--;
}

//顺序表的销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)//等价于if(ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void SLTest()
{
	SL sl;
	//顺序表初始化
	SLInit(&sl);

	//尾部插入
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	//顺序表的打印
	SLPrint(sl);

	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);
	SLPrint(sl);

	//尾部删除
	SLPopBack(&sl);
	SLPrint(sl);

	//头部删除
	SLPopFront(&sl);
	SLPrint(sl);

	//顺序表的查找
	int ret = SLFind(&sl, 4);
	if (ret < 0)
	{
		printf("找不到！\n");
	}
	else
	{
		printf("找到了！\n");
	}

	
	//在指定位置之前插入数据
	int ret = SLFind(&sl, 1);
	SLInsert(&sl, ret, 5);
	SLPrint(sl);

	//在指定为位置删除数据
	int ret = SLFind(&sl, 2);
	SLErase(&sl, ret);
	SLPrint(sl);

	//顺序表的销毁
	SLDestroy(&sl);
}

int main()
{
	SLTest();
	return 0;
}

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

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

相关文章

Golang net/http标准库常用方法(三)

Golang net/http标准库常用方法(三)

大家好&#xff0c;针对Go语言 net/http 标准库&#xff0c;将梳理的相关知识点分享给大家~~ 围绕 net/http 标准库相关知识点还有许多章节&#xff0c;请大家多多关注。 文章中代码案例只有关键片段&#xff0c;完整代码请查看github仓库&#xff1a;https://github.com/hltfa…
阅读更多...
面试八股之JVM篇3.6——垃圾回收——强引用、弱引用、虚引用、软引用

面试八股之JVM篇3.6——垃圾回收——强引用、弱引用、虚引用、软引用

&#x1f308;hello&#xff0c;你好鸭&#xff0c;我是Ethan&#xff0c;一名不断学习的码农&#xff0c;很高兴你能来阅读。 ✔️目前博客主要更新Java系列、项目案例、计算机必学四件套等。 &#x1f3c3;人生之义&#xff0c;在于追求&#xff0c;不在成败&#xff0c;勤通…
阅读更多...
LVS精益价值管理系统 LVS.Web.ashx SQL注入漏洞复现

LVS精益价值管理系统 LVS.Web.ashx SQL注入漏洞复现

0x01 产品简介 LVS精益价值管理系统是杭州吉拉科技有限公司研发的一款专注于企业精益化管理和价值流优化的解决方案。该系统通过集成先进的数据分析工具、可视化的价值流映射技术和灵活的流程改善机制，帮助企业实现高效、低耗、高质量的生产和服务。 0x02 漏洞概述 LVS精益…
阅读更多...
全国数据库管理系统设计赛-人大金仓内核实训安排正式发布

全国数据库管理系统设计赛-人大金仓内核实训安排正式发布

作为数据库领域国家队&#xff0c;人大金仓积极响应国家战略&#xff0c;通过赛题设计、内核技术支撑及赛前培训等多方面&#xff0c;大力支持全国大学生计算机系统能力大赛-数据库管理系统设计大赛成功举办。目前第二届全国大赛正在火热报名中&#xff0c;各种奖项等你来拿&am…
阅读更多...
RabbitMQ 发布订阅

RabbitMQ 发布订阅

RabbitMQ 发布订阅视频学习地址&#xff1a; 简单模式下RabbitMQ 发布者发布消息 消费者消费消息 Publist/Subscribe 发布订阅 在 RabbitMQ 中&#xff0c;发布订阅模式是一种消息传递方式&#xff0c;其中发送者&#xff08;发布者&#xff09;不会将消息直接发送到特 定的…
阅读更多...
Linux文本处理三剑客（详解）

Linux文本处理三剑客（详解）

一、文本三剑客是什么&#xff1f; 1. 对于接触过Linux操作系统的人来说&#xff0c;应该都听过说Linux中的文本三剑客吧&#xff0c;即awk、grep、sed&#xff0c;也是必须要掌握的Linux命令之一&#xff0c;三者都是用来处理文本的&#xff0c;但侧重点各不相同&#xff0c;a…
阅读更多...
Docker-镜像迁移的三种方式=＞备份恢复公有仓库私有仓库

Docker-镜像迁移的三种方式=＞备份恢复公有仓库私有仓库

制作好的镜像要被别人使用&#xff0c;有三种方式&#xff1a; 1.先备份镜像&#xff0c;别人通过u盘或者其它方式拷贝后&#xff0c;再恢复镜像&#xff0c;这种方式比较麻烦 2.将制作的镜像上传到公共镜像仓库&#xff0c;被别人拉取后使用&#xff0c;但可能存在网络不通畅或…
阅读更多...
嵩山为什么称为三水之源

嵩山为什么称为三水之源

三水指黄河、淮河、济河&#xff0c;这三条河流环绕在嵩山周边。 黄河横亘在嵩山北部&#xff0c;其支流伊洛河从西南方环绕嵩山&#xff0c;然后汇入黄河。济河&#xff0c;古称济水&#xff0c;源自济源王屋山&#xff0c;自身河道在东晋时代被黄河夺占&#xff0c;从此消失。…
阅读更多...
【Spring MVC】_SpringMVC项目返回数据

【Spring MVC】_SpringMVC项目返回数据

目录 1. 注解使用示例 1.1 使用Controller注解 1.2 使用RestController注解 1.3 使用Controller与ResponseBody注解 2. 关于ResponseBody注解 前文已经介绍过使用Controller注解向前端返回一个HTML页面&#xff0c;接下来将介绍向前端返回数据。 关于Controller和RestCon…
阅读更多...
算法金 | Dask，一个超强的 python 库

算法金 | Dask，一个超强的 python 库

本文来源公众号“算法金”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;Dask&#xff0c;一个超强的 python 库 1 Dask 概览 在数据科学和大数据处理的领域&#xff0c;高效处理海量数据一直是一项挑战。 为了应对这一挑战&am…
阅读更多...
初学者都能掌握的操作符（中）

初学者都能掌握的操作符（中）

&#xff08;1&#xff09;位操作符&#xff08;& | ^&#xff09; &&#xff1a;&#xff08;按二进制位“与”&#xff09; 也就是两个数的每一位二进制数按照 “与” 的算法&#xff0c;如下&#xff1a; int a 3 ,b 5 ; c a & b; 我们首先写出a和b的二进…
阅读更多...
Java面试八股之Synchronized和ReentrantLock的区别

Java面试八股之Synchronized和ReentrantLock的区别

Synchronized和ReentrantLock的区别 实现级别&#xff1a; synchronized是Java的一个关键字&#xff0c;属于JVM层面的原生支持&#xff0c;它通过监视器锁&#xff08;Monitor&#xff09;来实现同步控制&#xff0c;无需手动获取和释放锁。 ReentrantLock是java.util.conc…
阅读更多...
【Linux网络编程】传输层中的TCP和UDP（TCP篇）

【Linux网络编程】传输层中的TCP和UDP（TCP篇）

【Linux网络编程】传输层中的TCP和UDP&#xff08;TCP篇&#xff09; 目录 【Linux网络编程】传输层中的TCP和UDP&#xff08;TCP篇&#xff09;TCP协议TCP协议段格式确认应答&#xff08;ACK&#xff09;机制&#xff08;保证可靠性&#xff09;超时重传机制连接管理机制理解T…
阅读更多...
aws msk加密方式和问控制连接方式

aws msk加密方式和问控制连接方式

msk加密方式 msk提供了两种加密方式 静态加密传输中加密 创建集群时可以指定加密方式&#xff0c;参数如下 aws kafka create-cluster --cluster-name "ExampleClusterName" --broker-node-group-info file://brokernodegroupinfo.json --encryption-info file:/…
阅读更多...
ASP+ACCESS公司门户网站建设

ASP+ACCESS公司门户网站建设

【摘 要】随着计算机科学的发展&#xff0c;数据库技术在Internet中的应用越来越广泛&#xff0c;为广大网络用户提供了更加周到和人性化的服务。本文讲解了一个公司的网站的建设&#xff0c;它基于数据关联规则的公司个性化页面及动态数据生成案例&#xff0c;在网页方面&…
阅读更多...
Kubeadm安装部署k8s集群、踩坑日常

Kubeadm安装部署k8s集群、踩坑日常

背景 ​ Docker是一个非常流行的容器化平台&#xff0c;它可以让我们方便构建、打包、发布和运行容器化应用程序。但是&#xff0c;在生产环境中&#xff0c;我们可能需要处理成百上千个容器&#xff0c;需要更好的管理这些容器&#xff0c;这就是Kubernetes(K8S)的用武之地。…
阅读更多...
利用大语言模型增强网络抓取：一种现代化的方法

利用大语言模型增强网络抓取：一种现代化的方法

本文将探讨大语言模型(LLMs)与网络抓取的集成&#xff0c;以及如何利用LLMs高效地将复杂的HTML转换为结构化的JSON。 作为一名数据工程师&#xff0c;我的职业生涯可以追溯到2016年。那时&#xff0c;我的主要职责是利用自动化工具从不同网站上获取海量数据&#xff0c;这个过…
阅读更多...
网络模型-策略路由配置

网络模型-策略路由配置

在实际网络应用中&#xff0c;策略路由也是一种重要的技术手段。尽管在考试并不注重策略路由&#xff0c;但是实际上应用较多建议考生除了掌握基本的静态路由协议IP route-static&#xff0c;动态路由协议RIP、还要掌握如何配置策略路由。策略路由的基本原理:根据ACL定义的不同…
阅读更多...
云界洞见：移动云服务开启技术创新与问题解决的新篇章

云界洞见：移动云服务开启技术创新与问题解决的新篇章

一、什么是移动云 移动云以“央企保障、安全智慧、算网一体、属地服务”为品牌支撑&#xff0c;聚焦智能算力建设&#xff0c;打造一朵智能、智慧、安全可信可控的云&#xff0c;提供更优质的算力服务&#xff0c;引领云计算产业发展。 那么下面博主带领大家了解移动云的优势所…
阅读更多...
Golang单元测试

Golang单元测试

文章目录 传统测试方法基本介绍主要缺点 单元测试基本介绍测试函数基准测试示例函数 传统测试方法 基本介绍 基本介绍 代码测试是软件开发中的一项重要实践&#xff0c;用于验证代码的正确性、可靠性和预期行为。通过代码测试&#xff0c;开发者可以发现和修复潜在的错误、确保…
阅读更多...
最新文章

Copyright @ 2022~2023