顺序表详解（如何实现顺序表）

文章目录

前言

在进入顺序表前，我们先要明白，数据结构的基本概念。

一、数据结构的基本概念

1.1什么是数据结构

数据结构是由“数据”和“结构”两词组合而来。所谓数据就是？常见的数值1、2、3、4.....、姓名、性别、年龄，等。这些都是数据。所谓结构就是当我们想要使用大量同⼀类型的数据时，我们可以借助数组这样的数据结构将大量的数据组织在⼀起，结构也可以理解为组织数据的方式。

1.2数据结构的两个层次

数据结构的两个层次分为逻辑结构和存储结构，逻辑结构与数据的存储无关独立于计算机从具体问题抽象出来的数学模型模。逻辑结构分为线性结构和非线性结构，这里不再强调。存储结构分为顺式存储结构和链式存储结构，今天我们所说的顺序表就是顺数存储结构，链式存储结构的代表就是链表。

1.3最基础的数据结构：数组

二.顺序表的概念及结构

概念：之前说了最基础的数据结构就是数组，它的概念:顺序表其实就是数组，但是在宿主的基础上，他还要求数据必须从头开始连续存放，并且中间不能跳跃间隔。

2.1结构

 顺序表它分为静态顺序表和动态顺序表

静态顺序表

静态顺序表需要用#define来开辟，静态的特点就是N给小了不够用，给大了又浪费，所以我们所说的顺序表一般都是指的动态顺序表。

动态顺序表

2.2接口函数

接口函数就是某个模块写了（主要）给其它模块用的函数。简单的说接口函数就是类中的公有数。顺序表的实现主要是以接口函数来实现的

三.动态顺序表的实现

顺序表（seplist），我们重命名为SL，完成这个它我们使用3个文件，SL.h来放函数的声明，SL.cpp来放函数的定义，test.c来放可执行程序。

3.1一个经典的错误（初始化）

void SLInit(SL ps)
{
	ps.a = NULL;

	ps.size = ps.capacity = 0;

}

void testSL1()
{
    SL S1;
    SLInit(SL);
}

为什么这个代码无法运行？？？

因为在函数中的形参跟实参是有区别的形参的改变，不会影响到实参的，形参只是实参的一份临时拷贝，所以要用指针来找地址。

所以正确的初始化应该要这样

void SLInit(SL* ps)
{
	ps->a = NULL;

	ps->size = ps->capacity = 0;

}


void testSL1()
{
    SL S1;

    SLInit(&SL);
}

3.2接口函数之尾插

在一个数组中，如果我们想在末尾插入一个数，我们该怎么插入呢？这就是我们要想如何完成这个接口函数。

往末尾插东西，我们就要做到3点考虑，一.没有空间,刚刚好，二.空间不够的时候要进行扩容，三.空间足够的时候我们就直接插入。

先来看最容易的情况就是直接尾删

void SLpushBack(SL* ps, SLDataType x)
{
	ps->a[ps->size] = x;
	ps->size++;
}

然后我们在想我们前三点要注意的事情，如果没有空间或者空间不足了的话，我就要扩容，我们可以先将有效个数和空间容量相等来形成一个新的有效空间，这里我用了一个三目操作符，如果他们都等于零，我就给他付个值不等于零，我就翻倍在这个地方的扩容，我们就能想到realloc函数的扩容。过完之后我们还要判断一下，如果为空指针的话我们就要报警告，最后把我开辟的新空间重新付给a就可以了。

void SLPushBack(SL* ps, SLDataType x)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));

		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->size] = x;
    ps->size++;

}

其实扩容这一步，我们完成了另外一种接口函数的使用，那就是检查扩容，我们可以用一个步骤来开辟一个新的结构函数就是检查扩容void SLCheckCapacity(SL* ps)；这样对于后面的来使用就会更加方便。

3.3接口函数之尾删

尾删就非常简单了，我们只要防止数组越界就可以了，我们这里利用断言来警告他不能越界。

void SLPopBack(SL* ps)
{
	assert(ps->size > 0);
	{
		ps->size--;
	}
}

3.4接口函数之头插

头插的话想在第一个数前放一个位置，我们就把已经存放的数每个都向后移一个，注意:如果容量空间已到最大则需开辟空间，所以这就用到了我们之前所讲的检查扩容这个接口函数，所以在头差之前我们先要来检查一下扩容，如果容量够就可以进行头差，如果不够就扩容。

void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

3.5接口函数之头删

先思考为什么头删不可以size--???

因为根据顺序表的概念必须从头开始连续存放，并且中间不能跳跃间隔。

所以这个地方我们采取先挪动在尾删的方式。

void SLPopFront(SL* ps)
{
	assert(ps->size > 0);
		//挪动数据
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

3.6还原空间

因为我们之前动态开辟了内存，所以说我们肯定要把这个内存进行释放。

void SLDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

3.7接口函数之查找

查找的意思就是说找到对应元素所在的下标，即便他有多个也没关系，顺序表是从头到尾开始存放的，但是存放的内容不一定需要从头到尾他还可以存放字符等各种变量。

int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[ps->size] == x)
		{
			return i;
		}
	}
	return -1;
}

3.8接口函数之在指定的pos下标位置插入

pos下标也是有要求，他不可以违背顺序表的概念

其实挪动方法都是一样的，不管是尾插还是头插它的移动方法其实是一样的

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while(end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

3.9接口函数之删除pos下标位置的数据

其实挪动方法都是一样的，不管是尾插还是头插它的移动方法其实是一样的，挪动的方式是一样的，只是可能方向不一样，做法是一样的，然后我们还是要判断下标的合法性

void SLErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
}

4.0复用

这个时候有没有突然间恍然大悟大！！！

之前写的头删尾删头差尾插好像都可以用pos去代替去完善

头删
void PushBack(SL* ps)
{
	SLErase(ps, ps->0);
}
尾删
void SLPopBack(SL* ps)
{
	SLErase(ps, ps->size-1);
}
头插
void SLPushFront(SL* ps, SLDataType x)
{
	SLInsert(ps, ps->0,X);
}
尾插
void SLpushBack(SL* ps, SLDataType x)
{
	SLInsert(ps, ps->size, X);
}

这就是复用。

四.整体的实现

SL.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//#define N 1000
typedef int SLDataType;
#pragma once
typedef struct SeqList
{
	SLDataType * a;//动态开辟的数组大小
	int size; // 有效数据个数
	int capacity; // 空间容量

}SL;
void SLInit (SL* ps);//初始化
void SLPrint(SL* ps);//打印
void SLCheckCapacity(SL* ps);//检查扩容
void SLDestory(SL* ps);//销毁，还原空间
void SLpushBack(SL* ps, SLDataType x);//尾插
void SLPopBack(SL* ps);//尾删
void SLPushFront(SL* ps, SLDataType x);//头插
void SLPopFront(SL* ps);//头删
int SLFind(SL* ps, SLDataType x);//查找
void SLInsert(SL* ps, int pos, SLDataType x);//在指定的pos下标位置插入
void SLErase(SL* ps, int pos);//删除pos位置的数据
SL.cpp
#include"SL.h"
//初始化
void SLInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;

}

//打印
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d", ps->a[i]);
	}
	printf("\n");
}

//检查扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));

		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

//销毁，还原空间
void SLDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//尾插
void SLpushBack(SL* ps, SLDataType x)
{
	ps->a[ps->size] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps->size > 0);
	{
		ps->size--;
	}
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps->size > 0);
		//挪动数据
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

//查找
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[ps->size] == x)
		{
			return i;
		}
	}
	return -1;
}

//在指定的pos下标位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while(end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

//删除pos位置的数据
void SLErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
}

//头删
//void PushBack(SL* ps)
//{
//	SLErase(ps, ps->0);
//}
//尾删
//void SLPopBack(SL* ps)
//{
//	SLErase(ps, ps->size-1);
//}
//头插
//void SLPushFront(SL* ps, SLDataType x)
//{
//	SLInsert(ps, ps->0,X);
//}
//尾插
//void SLpushBack(SL* ps, SLDataType x)
//{
//	SLInsert(ps, ps->size, X);
//}

总结

有了顺序表，为什么还要学习其他的数据结构？顺序表作为数据结构的最基本，假设数据量非常庞大，频繁的获取数字，有效数据个数会影响程序的执行程序所以说最基础的数据结构提供的操作已经不能完全满足复杂的算法实现只有不断地提升自己才能变得强大。

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

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

相关文章

学习总结22

学习总结22

解题思路 简单模拟。 代码 #include <bits/stdc.h> using namespace std; long long g[2000000]; long long n; int main() {long long x,y,z,sum0,k0;scanf("%lld",&n);for(x1;x<n;x)scanf("%lld",&g[x]);for(x1;x<n;x){scanf(&qu…
阅读更多...
尚未创建默认 SSL 站点。若要支持不带 SNI 功能的浏览器，建议创建一个默认 SSL 站点。

尚未创建默认 SSL 站点。若要支持不带 SNI 功能的浏览器，建议创建一个默认 SSL 站点。

在 Windows Server 2012 IIS 站点中设置 SSL 证书后&#xff0c;IIS 右上角提示&#xff1a; 尚未创建默认 SSL 站点。若要支持不带 SNI 功能的浏览器&#xff0c;建议创建一个默认 SSL 站点。 该提示客户忽略不管&#xff0c;但是若要支持不带 SNI(Server Name Indication)…
阅读更多...
外卖柜平台的设计与实现以及实践与总结

外卖柜平台的设计与实现以及实践与总结

近年来&#xff0c;外卖行业的快速发展推动了外卖配送行业的进步和创新。外卖柜平台作为一种新兴的配送方式&#xff0c;在提高配送效率和服务质量方面具有很大的优势。本文将探讨美团外卖柜平台的设计与实现&#xff0c;以及如何保障其稳定性和安全性。 架构设计 美团外柜平台…
阅读更多...
React -- useEffect

React -- useEffect

React - useEffect 概念理解 useEffect是一个React Hook函数&#xff0c;用于在React组件中创建不是由事件引起而是由渲染本身引起的操作&#xff08;副作用&#xff09;, 比 如发送AJAX请求&#xff0c;更改DOM等等 :::warning 说明&#xff1a;上面的组件中没有发生任何的用…
阅读更多...
市场复盘总结 20240222

市场复盘总结 20240222

仅用于记录当天的市场情况&#xff0c;用于统计交易策略的适用情况&#xff0c;以便程序回测 短线核心&#xff1a;不参与任何级别的调整&#xff0c;采用龙空龙模式 一支股票 10%的时候可以操作&#xff0c; 90%的时间适合空仓等待 二进三&#xff1a; 进级率中 25% 最常用…
阅读更多...
leetcode日记（32）字符串相乘

leetcode日记（32）字符串相乘

做了很久很久……真的太繁琐了&#xff01;&#xff01; class Solution { public:string multiply(string num1, string num2) {string s;string str;if (num1 "0" || num2 "0") return "0";for(int inum2.size()-1;i>0;i--){int c2num2[…
阅读更多...
银行项目网上支付接口调用测试实例

银行项目网上支付接口调用测试实例

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 公司最近有一个网站商城项目要开始开发了&#xff0c;这几天老板和几个同事一起开着需求会议&…
阅读更多...
常见消息中间件

常见消息中间件

ActiveMQ 我们先看ActiveMQ。其实一般早些的项目需要引入消息中间件&#xff0c;都是使用的这个MQ&#xff0c;但是现在用的确实不多了&#xff0c;说白了就是有些过时了。我们去它的官网看一看&#xff0c;你会发现官网已经不活跃了&#xff0c;好久才会更新一次。 它的单机吞…
阅读更多...
2024 ，Android 15 预览版来了

2024 ，Android 15 预览版来了

日前&#xff0c;Android 15 发布了 Preview 1 预览版&#xff0c;预览计划将从 2024 年 2 月持续到 Android 15 公开发布&#xff08;预计 10 月&#xff09;&#xff0c;3月是开发者预览版 2&#xff0c;4 月将推出 Beta 1&#xff0c;5 月将推出 Beta 2&#xff0c;6 月的 B…
阅读更多...
Studio One 6免费下载安装激活教程

Studio One 6免费下载安装激活教程

一、Studio One 6安装 1.双击Studio One6安装包&#xff08;见文章尾部&#xff09;&#xff0c;如下图&#xff0c;可以切换语言&#xff0c;点击【OK】。 2.根据安装导航&#xff0c;点击【下一步】 3.阅读许可证协议后&#xff0c;点击【我接受】。 4.选择安装位置&#xf…
阅读更多...
Java 数据结构篇-深入了解排序算法（动态图 + 实现七种基本排序算法）

Java 数据结构篇-深入了解排序算法（动态图 + 实现七种基本排序算法）

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 实现冒泡排序 2.0 实现选择排序 2.1 选择排序的改良升级 3.0 实现堆排序 4.0 实现插入排序 5.0 实现希尔排序 6.0 实现归并排序 6.1 递归实现归并排序 6.2 使用…
阅读更多...
用了大品牌做流量，用自主品牌做利润。

用了大品牌做流量，用自主品牌做利润。

用国际品牌和有品牌的产品把用户数量做起来&#xff0c;用大品牌做流量&#xff0c;积累用户数据。当你的用户数量达到一定量之后&#xff0c;再做自主品牌&#xff0c;这叫水到渠成。 用户最好的商业模式不需要教育。用别人的品牌去打穿流量&#xff0c;打穿用户&#xff0c;…
阅读更多...
SpringBoot基于JWT的token做登录认证

SpringBoot基于JWT的token做登录认证

背景 我们在基于Session做登录认证的时候&#xff0c;会有一些问题&#xff0c;因为Session存储到服务器端&#xff0c;然后通过客户端的Cookie进行匹配&#xff0c;如果正确&#xff0c;则通过认证&#xff0c;否则不通过认证。这在简单的系统中可以这么使用&#xff0c;并且…
阅读更多...
如何重启docker中运行的镜像

如何重启docker中运行的镜像

要重启 Docker 中运行的容器&#xff0c;您可以使用 docker restart 命令。首先&#xff0c;您需要知道容器的 ID 或名称&#xff0c;然后使用该信息来重启容器。以下是具体步骤&#xff1a; 找出容器的 ID 或名称 执行 docker ps 命令列出所有正在运行的容器&#xff0c;找到您…
阅读更多...
软件常见设计模式

软件常见设计模式

设计模式 设计模式是为了解决在软件开发过程中遇到的某些问题而形成的思想。同一场景有多种设计模式可以应用&#xff0c;不同的模式有各自的优缺点&#xff0c;开发者可以基于自身需求选择合适的设计模式&#xff0c;去解决相应的工程难题。 良好的软件设计和架构&#xff0…
阅读更多...
vite是什么

vite是什么

vite 是什么 vite —— 一个由 vue 作者尤雨溪开发的 web 开发工具 Vite由两个主要部分组成 dev server&#xff1a;利用浏览器的ESM能力来提供源文件&#xff0c;具有丰富的内置功能并具有高效的HMR生产构建&#xff1a;生产环境利用Rollup来构建代码&#xff0c;提供指令用…
阅读更多...
SpringIOC之support模块StaticApplicationContext

SpringIOC之support模块StaticApplicationContext

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
vmware的ubuntu虚拟机因空间满无法启动

vmware的ubuntu虚拟机因空间满无法启动

正在虚拟机编译android源代码&#xff0c;没注意空间不足&#xff0c;结果回来发现了 Assuming drive cache: write through 的问题&#xff0c;经查是空间不足的原因 按照这个教程&#xff0c;清除出来部分空间&#xff0c;才能进去系统&#xff0c;并且对系统空间做下优化 …
阅读更多...
测试总监，让我们用这份《测试用例规范》，再也没加班过

测试总监，让我们用这份《测试用例规范》，再也没加班过

经常看到无论是刚入职场的新人&#xff0c;还是工作了一段时间的老人&#xff0c;都会对编写测试用例感到困扰&#xff1f;例如&#xff1a; 固然&#xff0c;编写一份好的测试用例需要&#xff1a;充分的需求分析能力 理论及经验加持&#xff0c;作为测试职场摸爬打滚的老人…
阅读更多...
GitHub热门项目之Memos 打造私有备忘录

GitHub热门项目之Memos 打造私有备忘录

效果 1. 写备忘录或简单笔记&#xff0c;支持Markdown 2. 时间线 3. 探索可以看到其他用户公开的内容 项目地址 usememos/memos&#xff1a;一种开源的轻量级笔记服务。轻松捕捉和分享您的伟大想法。 (github.com)https://github.com/usememos/memos 体验地址 Memoshttp://…
阅读更多...
最新文章

Copyright @ 2022~2023