数据结构：顺序表

目录

一.顺序表

1.1概念以及结构

1.2动态顺序表实现

1.2.1文件创建：

1.2.2接口实现

1.顺序表打印

2.顺序表初始化

3.顺序表尾插

4.顺序表头插

 5.顺序表尾删

6.顺序表头删

 7.顺序表在pos位置插入x

 8.顺序表删除pos位置的值

 9.顺序表销毁

二.顺序表问题

一.顺序表

1.1概念以及结构

顺序表（一般是用数组存储）是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。

顺序表一般可以分为：

  • 静态顺序表：使用定长数组存储元素
  • 动态顺序表：使用动态开辟（malloc）的数组存储。

静态顺序表：

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

#define number 7
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[number];//定长数组
    size_t size;//有效数据个数
}SL;

动态顺序表：

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

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

1.2动态顺序表实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致number定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们来讲解如何实现动态顺序表实现。

1.2.1文件创建：

  • 在seq.h文件中对顺序表结构和接口（增删查改等）函数进行声明
  • 在seq.c文件中对顺序表接口函数进行实现
  • 在test.c文件中一步步对顺序表及其接口进行测试

1.2.2接口实现

对于顺序表我们要实现以下几个功能：

  1. 顺序表打印（可视化每一步的成果）
  2. 顺序表初始化
  3. 顺序表尾插
  4. 顺序表头插
  5. 顺序表尾删
  6. 顺序表头删
  7. 顺序表在pos位置插入x
  8. 顺序表删除pos位置的值
  9. 顺序表销毁
1.顺序表打印
//存储整数的顺序表打印
void SLPrint(SL* psl)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
2.顺序表初始化
//顺序表初始化
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;

}
3.顺序表尾插
// 顺序表尾插
void SLPushBack(SL* psl, SLDataType x)
{
	assert(psl);
	//尾插时 检查顺序表容量大小
	if (psl->size == psl->capacity)
	{
		//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//realloc开辟空间和扩容
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fali:");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;

	}
	//尾插元素
	psl->a[psl->size] = x;
	psl->size++;
}

 写出函数后进行一次测试：

//顺序表尾插测试
void test1()
{

	//定义一个顺序表变量
	SL sl1;
	//初始化这个顺序表变量
	SLInit(&sl1);
	SLPushBack(&sl1, 1);
	SLPushBack(&sl1, 2);
	SLPushBack(&sl1, 3);
	SLPushBack(&sl1, 4);
	SLPushBack(&sl1, 5);

	SLPrint(&sl1);

}
int main()
{
	test1();

	return 0;
}

 

4.顺序表头插
// 顺序表头插
void SLPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	//头插时 检查顺序表容量大小
	if (psl->size == psl->capacity)
	{
		//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//realloc开辟空间和扩容
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fali:");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;

	}
	//与尾插不同的是在进行头插之前我们需要将所有元素先向后移动一位
	int odd_size_to_move = psl->size;
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		psl->a[odd_size_to_move] = psl->a[odd_size_to_move - 1];
		odd_size_to_move--;
	}

	//头插元素
	psl->a[0] = x;
	psl->size++;
}

  写出函数后进行一次测试：

//顺序表头插测试
void test2()
{
	//	定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//	先尾插
	SLPushBack(&sl2, 0);
	SLPushBack(&sl2, 0);
	SLPushBack(&sl2, 0);
	SLPushBack(&sl2, 0);
	//	再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);


	SLPrint(&sl2);
	SLDestory(&sl2);

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

 

 5.顺序表尾删
// 顺序表尾删
void SLPopBack(SL* psl)
{
	//温柔检查
	//要保证顺序表空了就不再删除了，根除错误源头
	if (psl->size == 0)
	{
		return;
	}

	//暴力检查
	//assert(psl->size > 0);

	psl->size--;

}

 写出函数后进行一次测试：

//顺序表尾删测试
void test3()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	SLPrint(&sl2);

	//尾删
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	SLPopBack(&sl2);
	//上面只有九个元素，当我们再调用删除的时候将会报错或者直接退出该函数调用。
	SLPopBack(&sl2);
	//头插                       
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main()
{
	test3();
	return 0;
}

 

6.顺序表头删
// 顺序表头删
void SLPopFront(SL* psl)
{
	assert(psl);

	//挪动覆盖
	int i = (psl->size) - 1;
	int j = 0;
	while (i)
	{
		psl->a[j] = psl->a[j + 1];
		j++;
		i--;
	}
	psl->size--;
}

  写出函数后进行一次测试：

//顺序表头删测试
void test4()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	SLPrint(&sl2);

	//头删
	SLPopFront(&sl2);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main()
{
	test4();
	return 0;
}

 

 7.顺序表在pos位置插入x
// 顺序表在pos位置插入x
void SLInsert(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	//插入元素前先检查顺序表容量大小是否足够
	if (psl->size == psl->capacity)
	{
		//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//realloc开辟空间和扩容
		SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fali:");
			return;
		}
		psl->a = tmp;
		psl->capacity = newcapacity;
	}

	int n = psl->size;
	while (n > pos)
	{
		psl->a[n] = psl->a[n - 1];
		n--;
	}

	psl->a[pos] = x;
	(psl->size)++;


}

   写出函数后进行一次测试：


//顺序表pos位置插入测试
void test5()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	//pos位置插入x
	SLInsert(&sl2, 3, 5000);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main
{
    test5();
    return 0;
}

 8.顺序表删除pos位置的值
// 顺序表删除pos位置的值
void SLErase(SL* psl, size_t pos)
{
	assert(psl);
	while (pos < ((psl->size) - 1))
	{
		psl->a[pos] = psl->a[pos + 1];
		pos++;
	}
	(psl->size)--;
}

   写出函数后进行一次测试：

//顺序表pos位置删除测试
void test6()
{
	//定义一个顺序表变量
	SL sl2;
	//初始化这个顺序表变量
	SLInit(&sl2);
	//先尾插
	SLPushBack(&sl2, 100);
	SLPushBack(&sl2, 99);
	SLPushBack(&sl2, 98);
	SLPushBack(&sl2, 97);
	//再头插
	SLPushFront(&sl2, 5);
	SLPushFront(&sl2, 4);
	SLPushFront(&sl2, 3);
	SLPushFront(&sl2, 2);
	SLPushFront(&sl2, 1);

	//pos位置删除
	SLErase(&sl2, 3);

	SLPrint(&sl2);
	SLDestory(&sl2);
}
int main()
{

	test6();
	return 0;
}

 9.顺序表销毁
//顺序表销毁
void SLDestory(SL* psl)
{
	assert(psl);
	//检查动态开辟的顺序表内存最后是否被释放，没有释放则释放psl->a并且将顺序表全部初始化为最初的形态
	if (psl->a != NULL)
	{
		free(psl->a);
		psl->a = NULL;
		psl->size = 0;
		psl->capacity = 0;
	}
}

二.顺序表问题

我们已经实现了顺序表，那我们能发现顺序表这种数据结构有什么优劣势么？

顺序表缺点：

  1. 头部或者中间插入删除效率低，要挪动数据，O(N)
  2. 空间不够需要扩容，扩容有一定消耗，且可能存在一定的空间消耗
  3. 只适合尾插尾删

顺序表优点：

        支持下标随机访问 O(1)

顺序表无法简要完成的事情我们可以通过学习下一个数据结构链表来完成，咱们下次再见

感谢您的支持！

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

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

相关文章

关于 Docker

关于 Docker

关于 Docker 1. 术语Docker Enginedockerd&#xff08;Docker daemon&#xff09;containerdOCI (Open Container Initiative)runcDocker shimCRI (Container Runtime Interface)CRI-O 2. 容器启动过程在 Linux 中的实现daemon 的作用 Docker 是个划时代的开源项目&#xff0c;…
阅读更多...
「快学Docker」监控和日志记录容器的健康和性能

「快学Docker」监控和日志记录容器的健康和性能

「快学Docker」监控和日志记录容器的健康和性能 1. 容器健康状态监控2. 性能监控3. 日志记录几种采集架构图 4. 监控工具和平台cAdvisor&#xff08;Container Advisor&#xff09;PrometheusGrafana 5. 自动化运维 1. 容器健康状态监控 方法1&#xff1a;需要实时监测容器的运…
阅读更多...
在iPad pro上安装VSCode，秒变生产力工具提升编程工作效率！

在iPad pro上安装VSCode，秒变生产力工具提升编程工作效率！

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;网络奇遇记、Cpolar杂谈 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. 本地环境配置二. 内网穿透2.1 安装cpolar内网穿透(支持一键自动安装脚本)2.…
阅读更多...
智慧法院档案数字化解决方案

智慧法院档案数字化解决方案

智慧法院档案数字化解决方案可以采用以下步骤&#xff1a; 1. 确定数字化目标&#xff1a;明确数字化的目标和范围&#xff0c;比如将所有的案件相关文件、纸质档案和材料进行数字化。 2. 确定数字化流程&#xff1a;制定数字化的流程和标准&#xff0c;比如采用哪些设备和软件…
阅读更多...
人工智能基础_机器学习047_用逻辑回归实现二分类以上的多分类_手写代码实现逻辑回归OVR概率计算---人工智能工作笔记0087

人工智能基础_机器学习047_用逻辑回归实现二分类以上的多分类_手写代码实现逻辑回归OVR概率计算---人工智能工作笔记0087

然后我们再来看一下如何我们自己使用代码实现逻辑回归的,对二分类以上,比如三分类的概率计算 我们还是使用莺尾花数据 首先我们把公式写出来 def sigmoid(z): 定义出来这个函数 可以看看到这需要我们理解OVR是如何进行多分类的,我们先来看这个 OVR分类器 思想 OVR（One-vs-…
阅读更多...
Android设计模式--模板方法模式

Android设计模式--模板方法模式

一&#xff0c;定义 定义一个操作中的算法的框架&#xff0c;而将一些步骤延迟到子类中&#xff0c;使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 在面向对象的开发过程中&#xff0c;通常会遇到这样一个问题&#xff0c;我们知道一个算法所需的关键步…
阅读更多...
2023年【上海市安全员C证】考试及上海市安全员C证找解析

2023年【上海市安全员C证】考试及上海市安全员C证找解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年上海市安全员C证考试为正在备考上海市安全员C证操作证的学员准备的理论考试专题&#xff0c;每个月更新的上海市安全员C证找解析祝您顺利通过上海市安全员C证考试。 1、【多选题】2017年9月颁发的《中共上海市委…
阅读更多...
达索系统SOLIDWORKS流体分析网格划分失败，大多是这2种原因

达索系统SOLIDWORKS流体分析网格划分失败，大多是这2种原因

SOLIDWORKS Flow Simulation 是直观的流体力学 (CFD) 分析软件&#xff0c;该软件功能强大、操作人性化&#xff0c;快速轻松的分析产品内部或外部流体的流动情况&#xff0c;以用来改善产品性能和功能。 当流体分析运行网格划分时&#xff0c;提示失败。 这是由于凸起面与圆…
阅读更多...
HTML新手入门笔记整理：HTML基本介绍

HTML新手入门笔记整理：HTML基本介绍

网页 静态页面 仅可供用户浏览&#xff0c;不具备与服务器交互的功能。 动态页面 可供用户浏览&#xff0c;具备与服务器交互的功能。 HTML HTML&#xff0c;全称HyperText Markup Language&#xff08;超文本标记语言&#xff09;,是一种用于创建网页的标准标记语言。用于…
阅读更多...
基于向量加权平均算法优化概率神经网络PNN的分类预测 - 附代码

基于向量加权平均算法优化概率神经网络PNN的分类预测 - 附代码

基于向量加权平均算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于向量加权平均算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于向量加权平均优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xf…
阅读更多...
MySQL 事务的底层原理和 MVCC（二）

MySQL 事务的底层原理和 MVCC（二）

7.2. undo 日志 7.2.1. 事务回滚的需求 我们说过事务需要保证原子性&#xff0c;也就是事务中的操作要么全部完成&#xff0c;要么什么也不做。但是偏偏有时候事务执行到一半会出现一些情况&#xff0c;比如&#xff1a; 情况一&#xff1a;事务执行过程中可能遇到各种错误&a…
阅读更多...
C语言--数组与指针--打印字符串的n种方式

C语言--数组与指针--打印字符串的n种方式

一.知识背景 一维数组名的含义 arr一般表示数组的起始地址&#xff08;除了两种例外&#xff09; 1.在定义数组的同一个函数中(不是形参),求sizeof(arr),求整个数组的字节数 2.在定义数组的同一个函数中(不是形参),&arr1,加整个数组的大小 (经常考试) 3.除上面以外,arr都表…
阅读更多...
io+day5

io+day5

1&#xff0c;select服务端 1 #include<myhead.h>2 3 #define PORT 8888 //端口号4 #define IP "192.168.228.165" //IP地址5 6 7 int main(int argc, const char *argv[])8 {9 //1、创建用于接受连接的套接字10 int sfd socket(…
阅读更多...
使用低代码可视化开发平台快速搭建应用

使用低代码可视化开发平台快速搭建应用

目录 一、JNPF可视化平台介绍 二、搭建JNPF可视化平台 【表单设计】 【报表设计】 【流程设计】 【代码生成器】 三、使用JNPF可视化平台 1.前后端分离&#xff1a; 2.多数据源&#xff1a; 3.预置功能&#xff1a; 4.私有化部署&#xff1a; 四、总结 可视化低代码…
阅读更多...
java_函数式接口

java_函数式接口

文章目录 一、什么是函数式接口二、四大核心函数式接口三、使用举例 一、什么是函数式接口 如果一个接口只有一个抽象方法&#xff0c;那么该接口就是一个函数式接口函数式接口的实例可以通过 lambda 表达式、方法引用或者构造方法引用来创建如果我们在某个接口上声明了 Funct…
阅读更多...
每日一题：LeetCode-589.N叉树的前序遍历

每日一题：LeetCode-589.N叉树的前序遍历

每日一题系列&#xff08;day 01&#xff09; 前言&#xff1a; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f50e…
阅读更多...
Spring Boot创建和使用（重要）

Spring Boot创建和使用（重要）

Spring的诞生是为了简化Java程序开发的&#xff01; Spring Boot的诞生是为了简化Spring程序开发的&#xff01; Spring Boot就是Spring框架的脚手架&#xff0c;为了快速开发Spring框架而诞生的&#xff01;&#xff01; Spring Boot的优点&#xff1a; 快速集成框架&#x…
阅读更多...
三维控件中定位一个点_vtkPointWidget

三维控件中定位一个点_vtkPointWidget

开发环境&#xff1a; Windows 11 家庭中文版Microsoft Visual Studio Community 2019VTK-9.3.0.rc0vtk-example参考代码 demo解决问题&#xff1a;允许用户使用三维光标在三维空间中定位一个点。关键类vtkPointWidget , 光标具有轮廓边界框、轴对齐十字准线和轴阴影&#xff…
阅读更多...
【C++】vector的介绍与使用

【C++】vector的介绍与使用

&#x1f9d1;‍&#x1f393;个人主页&#xff1a;简 料 &#x1f3c6;所属专栏&#xff1a;C &#x1f3c6;个人社区&#xff1a;越努力越幸运社区 &#x1f3c6;简 介&#xff1a;简料简料&#xff0c;简单有料~在校大学生一枚&#xff0c;专注C/C/GO的干货分…
阅读更多...
9、鸿蒙应用桌面图标外观和国际化

9、鸿蒙应用桌面图标外观和国际化

一、项目资源目录 项目下的resoueces目录为资源配置目录&#xff0c;其中base为基础配置&#xff0c;即在任何语言环境下都会加载的资源&#xff0c; color.json&#xff1a;用于配置颜色&#xff0c;如页面的背景和文字的颜色。 string.json&#xff1a;用于设置文字&#…
阅读更多...
最新文章

Copyright @ 2022~2023