【数据结构】手撕顺序表

一，概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储；

在数组上完成数据的增删查改。

 1， 静态顺序表：使用定长数组存储元素。

2.，动态顺序表：使用动态开辟的数组存储。

 

二，接口实现

静态顺序表只适用于确定知道需要存多少数据的场景；

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用；

所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表；

        1，顺序表的创建（动态）

//动态顺序表
typedef int SLDataType;typedef struct SqList
{SLDataType* a;int size;		//存储有效数据个数int capacity;	//容量空间大小
}SL;

这里我们将数据类型暂时定为int类型，typedef为SLDataType，便于我们后续对顺序表数据类型的修改；

定义属性表为SL*的指针a，有效数据个数size，现有容量capacity;

        2，接口函数

// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos);

        3，初始化 

	//定义SL s1;//初始化SLInit(&s1);
// 顺序表初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->a== NULL){perror("malloc");exit(-1);}ps->size = 0;ps->capacity = 4;
}

首先要进行断言ps不能为空，如果ps为空则下面对ps解引用就会报错；

刚开始先给 a 申请4个SLDataType大小的空间，这个自己可以任意修改，然后对size和capacity进行赋值；

        4，销毁

// 顺序表销毁
void SLDestroy(SL*ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}

然后就是销毁顺序表，直接用 free 释放掉 a 即可，再置为空指针，再重置 size 和 capacity ；

        5，判断是否增容

// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){ps->a = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (ps->a == NULL){perror("realloc");exit(-1);}ps->capacity = ps->capacity * 2;}
}

像后面如果进行尾插，头插的话就需要检查空间是否需要增容了，也很好判断，当size等于capacity时就需要增容了，我们这里是选择直接扩容一倍；

然后再更新一下capacity的值就行了；

        6，尾插

//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查空间SLChenkCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

首先判断是否需要增容，此时size的值就是末尾的数的下标加一；

直接对其下标进行赋值，再让size加一；

        7，尾删

//顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);//温柔的检查//if (ps->size == 0)//	return;//暴力检查assert(ps->size > 0);ps->size--;
}

这里有两种检查方式，推荐暴力检查法，要删除值，size的值必须大于0；

然后直接令size减一即可，访问不到即为删除；

          8，头插

//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLChenkCapacity(ps);int end = ps->size-1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--; }ps->a[0] = x;ps->size++;
}

还是先判断是否需要增容，然后先将整体的值往后推一位；

给头赋值，令size加一；

           9，头删

//顺序表头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int i = 0;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}

要删除数据首先数据不能为空，要进行断言一下；

然后将整体往前推一位，再令size减一；

        10，打印

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

size是数据个数，其减一就是末尾数据的下标，然后进行遍历打印即可；

        11，查找

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

直接遍历数组进行查找然后返回下标，没有则返回-1；

         12，指定位置进行插入

// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{assert(ps);assert(pos>=0 && pos <= ps->size);SLChenkCapacity(ps);int end = ps->size - 1;while (end >=pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

首先判断pos要大于等于0且小于等于size，是否需要增容；

然后从pos数组的值往后推一位，再对其位置重新赋值，再令size++；

         13，指定位置进行删除

// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int i = pos;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}

首先还是要判断pos的值，大于等于0小于size，因为数组下标为size是没有值的，所以pos不能等于size；

然后在pos处往前推一位，令size--；

三，源码

        1，头文件

SqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//动态顺序表
typedef int SLDataType;typedef struct SqList
{SLDataType* a;int size;		//存储有效数据个数int capacity;	//容量空间大小
}SL;// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos);

         2，执行文件

SqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SqList.h"// 顺序表初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->a== NULL){perror("malloc");exit(-1);}ps->size = 0;ps->capacity = 4;
}// 顺序表销毁
void SLDestroy(SL*ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){ps->a = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (ps->a == NULL){perror("realloc");exit(-1);}ps->capacity = ps->capacity * 2;}
}//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查空间SLChenkCapacity(ps);ps->a[ps->size] = x;ps->size++;
}//顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);//温柔的检查//if (ps->size == 0)//	return;//暴力检查assert(ps->size > 0);ps->size--;
}//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLChenkCapacity(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);assert(ps->size > 0);int i = 0;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}//顺序表打印
void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{assert(ps);assert(pos>=0 && pos <= ps->size);SLChenkCapacity(ps);int end = ps->size - 1;while (end >=pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int i = pos;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}

如有不足之处欢迎来补充交流！

完结。。。

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

java bs项目_BS（Java平台）

java bs项目_BS（Java平台）

采用前后端分离的体系架构。采用前后端分离的开发模式的好处是前端、后台互不影响，发挥各自的特长，提高工作效率。前后端根据约定好的接口规范，按照规范的报文格式分别进行独立开发。前后端开发完成后，进行前后端联调，联调过程中对前后端的参数传递，页面串联，业务逻辑等…
阅读更多...
BS架构和CS架构的优缺点

BS架构和CS架构的优缺点

1、CS、BS架构定义 CS（Client/Server）：客户端----服务器结构。C/S结构在技术上很成熟，它的主要特点是交互性强、具有安全的存取模式、网络通信量低、响应速度快、利于处理大量数据。因为客户端要负责绝大多数的业务逻辑和UI展示，又称为胖客户端。它充分利用两端硬件，将任…
阅读更多...
HAproxy+keepalived高可用配置搭建

HAproxy+keepalived高可用配置搭建

目录 一、概述 &#xff08;一&#xff09;简介 &#xff08;二&#xff09;核心功能 &#xff08;三&#xff09;关键特性 &#xff08;四&#xff09;应用场景 二、安装 1&#xff09;拓补图 2&#xff09;配置 &#xff08;一&#xff09;内核配置 &#xff08;二…
阅读更多...
oracle orcl不存在,oracle服务丢失的处理方法之OracleServiceORCL不存在示例

oracle orcl不存在,oracle服务丢失的处理方法之OracleServiceORCL不存在示例

oracle服务是oracle数据库的重要组成部分，下面就教您oracle服务丢失的处理方法，如果您之前遇到过oracle服务丢失的问题，不妨一看。 今天发现数据库服务器上的所有oracle服务都丢失了——也就是说在服务管理器中没有oracle服务了，如OracleOraDb10g_home1TNSListener、Oracle…
阅读更多...
如何打开计算机的Oracle服务,win10系统手动启动oracle服务的操作方法

如何打开计算机的Oracle服务,win10系统手动启动oracle服务的操作方法

有关win10系统手动启动oracle服务的操作方法想必大家有所耳闻。但是能够对win10系统手动启动oracle服务进行实际操作的人却不多。其实解决win10系统手动启动oracle服务的问题也不是难事&#xff0c;小编这里提示两点&#xff1a;1、打开“服务”窗口。或者“管理”口&#xff1…
阅读更多...
在现有oracle服务器上新建一个oracle实例

在现有oracle服务器上新建一个oracle实例

一 概述 假如一台服务器上已经安装了一个单机版的oracle实例orcl&#xff0c;这时想在这台服务器上再部署一个单机版的oracle实例ystat&#xff0c;则可以参考该文档进行部署。 注意&#xff1a;新实例名不要带特殊字符&#xff0c;下划线也不要。 二 操作步骤 2.1 创建相关…
阅读更多...
linux下Oracle服务的启动和关闭

linux下Oracle服务的启动和关闭

1.前言 确保我们能够访问oracle数据库包含两部分&#xff0c;一个是oracle实例&#xff0c;一个是监听&#xff0c;两个同时开启&#xff0c;我们才能正常的使用数据库&#xff0c;因此我们在关闭和启动oracle服务时&#xff0c;也需要同时操作实例和监听。能够操作linux的工具…
阅读更多...
AI绘图（11）stable diffusion 如何写好prompt 四

AI绘图（11）stable diffusion 如何写好prompt 四

在最开始我写了三篇关于prompt的&#xff0c;具体的大家可以跳转来去看&#xff0c;以下给出来链接&#xff1a; AI绘图&#xff08;3&#xff09;stable diffusion如何写好prompt 一_牧子川的博客-CSDN博客 AI绘图&#xff08;4&#xff09;stable diffusion如何写好prompt …
阅读更多...
几个nlp的小任务(生成式任务——语言模型(CLM与MLM))

几个nlp的小任务(生成式任务——语言模型(CLM与MLM))

@TOC 本章节需要用到的类库 微调任意Transformers模型（CLM因果语言模型、MLM遮蔽语言模型） CLM MLM 准备数据集 展示几个数据的结构
阅读更多...
MERN Stack 教程

MERN Stack 教程

This tutorial will show you how to build a full-stack MERN application—in this case, an employee database—with the most current tools available. Before you begin, make sure that you are familiar with Node.js and React.js basics and have Node and Create R…
阅读更多...
取消开机自检

取消开机自检

1. 打开运行窗口 win R &#xff0c;输入regedit&#xff0c;点击确定&#xff0c;如图&#xff1a; 2. 一次打开以下节点&#xff0c;如图&#xff1b; 3. 在找到如图所示的节点 4. 双击BootExecute&#xff0c;如图&#xff1a; 5. 清空弹窗中的数据&#xff0c;点击确定&a…
阅读更多...
拯救者Y7000 2020新版Bios关闭开机自检

拯救者Y7000 2020新版Bios关闭开机自检

原因 重启按F2进入bios&#xff08;联想笔记本是F2&#xff09; 点击boot选项 关闭自检&#xff08;PXE Boot to LAN改为Disabled&#xff09;
阅读更多...
服务器系统自检时间长,我的服务器开机自检提示：waiting for controller to start...是什么意思，而且要等1-5分钟的时间问题是？...

服务器系统自检时间长,我的服务器开机自检提示：waiting for controller to start...是什么意思，而且要等1-5分钟的时间问题是？...

满意答案 alexteresa 2013.06.11 采纳率&#xff1a;46% 等级&#xff1a;12 已帮助&#xff1a;16267人 你好&#xff0c;电脑开机自检&#xff0c;主要是&#xff1a;“内存有错误”或“非正常关机”引起&#xff01; 这是解决方法&#xff1a;(原创&#xff0c;引用请说明…
阅读更多...
服务器跳过系统自检,win7 64位旗舰版跳过开机自检功能直接进入系统的方法

服务器跳过系统自检,win7 64位旗舰版跳过开机自检功能直接进入系统的方法

如果遇到断电或其他情况导致电脑不正常关机&#xff0c;下次开机电脑会出现磁盘自动检测&#xff0c;win7 64位旗舰版系统磁盘自检的过程需要花费好几分钟的时间&#xff0c;来检测到硬盘是否有坏道或系统是否损坏等问题。如果碰到每次开机磁盘会自检好长时间怎么办呢&#xff…
阅读更多...
计算机主板 上电顺序,BIOS很熟悉，电脑开机BIOS开机自检顺序你知道吗？

计算机主板 上电顺序,BIOS很熟悉，电脑开机BIOS开机自检顺序你知道吗？

原标题：BIOS很熟悉，电脑开机BIOS开机自检顺序你知道吗？ 开机键→主板控制芯片向→CPU发出RESET信号→CPU初始化 当电源供电稳定后，芯片组便撤去RESET信号，CPU马上就从FFFFOH处开始执行指令。注：这个地址在系统BIOS的地址范围内，无论是BIOS还是AMI BIOS，放在这里的只是一…
阅读更多...
xp计算机启动检测硬盘,取消WinXP开机自检技巧五则

xp计算机启动检测硬盘,取消WinXP开机自检技巧五则

有时我们正常关闭计算机后&#xff0c;再次开机时发现系统会出现自行检测&#xff0c;这让许多XP用户们感到不方便&#xff0c;那么该怎么取消XP开机自检呢&#xff1f;下面就是具体的方法了&#xff0c;一起来看看吧。 方法①&#xff1a; 假如分区是FAT32格式&#xff0c;将其…
阅读更多...
华为服务器自检信息怎么开,服务器开机自检内存

华为服务器自检信息怎么开,服务器开机自检内存

服务器开机自检内存 内容精选 换一换 华为云帮助中心&#xff0c;为用户提供产品简介、价格说明、购买指南、用户指南、API参考、最佳实践、常见问题、视频帮助等技术文档&#xff0c;帮助您快速上手使用华为云服务。 当对弹性云服务器执行绑定密钥对操作时失败。管理控制台上密…
阅读更多...
计算机的开机自检是在 里完成的,计算机的开机自检是在里完成的

计算机的开机自检是在 里完成的,计算机的开机自检是在里完成的

摘要&#xff1a; 计算机须办在动的动域内理(火区火必凡是。自检土高指路质路高路堤是堤填度大的土堤于(。计算机)米作业在(高度级高处作业为二时称。... 计算机须办在动的动域内理(火区火必凡是。 开机二级小时作业作业证》动火的《动火期不安全超过有效。 自检土高指路质路高…
阅读更多...
开机自检过程和systemd服务

开机自检过程和systemd服务

开机自检 自检过程 1&#xff1a;bios开机自检 2&#xff1a;MBR引导 3&#xff1a;grub文件 4&#xff1a;加载内核 5&#xff1a;开启进程 过程解释 第一步&#xff1a;bios开机时自检&#xff0c;检测硬件是否正常 第二部&#xff1a;硬件正常后&#xff0c;将系统控制权…
阅读更多...
戴尔服务器关闭系统自检,戴尔开机自检取消操作方法

戴尔服务器关闭系统自检,戴尔开机自检取消操作方法

摘要 腾兴网为您分享:洛克王国菲菲&#xff0c;美丽拍&#xff0c;nba2k17选秀名单&#xff0c;瞩目会议&#xff0c;助理来也&#xff0c;hevc&#xff0c;奥迪出行,优奢易拍&#xff0c;威海公积金&#xff0c;久币网&#xff0c;奸笑表情包&#xff0c;gocom&#xff0c;htm…
阅读更多...
最新文章

Copyright @ 2022~2023