【数据结构】顺序表解析及实战运用

目录

线性表

顺序表

概念及结构

静态顺序表

动态顺序表

接口实现

初始化与销毁顺序表

检查容量（扩容函数）

打印顺序表

尾部插入和尾部删除

头部插入与头部删除

查找数据

指定下标位置插入

删除指定下标位置的数据

顺序表优缺点

优点

缺点

顺序表实战运用

删除有序数组中的重复项

合并两个有序数组

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表就是数组,但是再数组的基础上,它还要求数据是从头开始连续存储的,不能跳跃间隔。

静态顺序表

#pragma once#define N 1000
typedef int SLDataType;//静态顺序表
typedef struct SeqList
{SLDataType a[N];int size;//表示数组中存储了多少个数据}SL;//接口函数
void SeqListInit(SL* ps, SLDataType x);//静态特点：如果满了就不让插入 缺点：给多少的合适呢？这个很难确定
//N给小了不够用，N给大了浪费
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListpushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps, SLDataType x);

动态顺序表

#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLDataType;//动态顺序表
typedef struct SeqList
{SLDataType* a;int size;//表示数组中存储了多少个数据（有效数据个数）int capacity;//数组实际能存数据的空间容量是多大（能存储的数据个数）
}SL;//接口函数
void SeqListInit(SL* ps);//初始化
void SeqListCheckCapacity(SL* ps);//检查容量（扩容）
void SeqListDestroy(SL* ps);
//销毁顺序表，释放空间
void SeqListPushBack(SL* ps, SLDataType x);
//尾插
void SeqListPopBack(SL* ps);
//尾删
void SeqListpushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);
//头删
void SeqListPrint(SL* ps);//打印顺序表
//找到了返回x位置下标，没有找到返回-1
int SeqListFind(SL* ps, SLDataType x);
//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除pos下标位置的数据
void SeqListErase(SL* ps, int pos);

接口实现

初始化与销毁顺序表

void SeqListInit(SL* ps)//初始化
{ps->a = NULL;ps->capacity = ps->size = 0;
}void SeqListDestroy(SL* ps)//顺序表不用了，销毁，释放空间
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

检查容量（扩容函数）

void SeqListCheckCapacity(SL* ps)//检查容量，扩容
{//如果没有空间或者空间不足，我们就扩容if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果为0，则给4，如果不是0，则扩大二倍SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL)//扩容失败{printf("realloc fail\n");exit(-1);//系统函数，退出程序，正常退出是返回0，这里是退出程序并返回-1，说明是异常退出}//扩容成功ps->a = tmp;ps->capacity = newcapacity;}
}

打印顺序表

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

尾部插入和尾部删除

void SeqListPushBack(SL* ps, SLDataType x)//尾插，从尾部插入
{SeqListCheckCapacity(ps);//从尾部插入ps->a[ps->size] = x;ps->size++;
}void SeqListPopBack(SL* ps)//尾部删除
{assert(ps->size > 0);    //防止多次调用导致size小于0出现非法访问的情况//ps->a[ps->size - 1] = 0;    //可加可不加ps->size--;
}

头部插入与头部删除

void SeqListpushFront(SL* ps, SLDataType x)//头插
{SeqListCheckCapacity(ps);//挪动数据，从后往前，依次向后挪动一个位置int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}void SeqListPopFront(SL* ps)//头删 
{assert(ps->size > 0);int begin = 1;//从数组第二个位置开始依次往前移动覆盖while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

查找数据

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

指定下标位置插入

//指定下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(pos >= 0 && pos <= ps->size);//防止pos插入位置非法SeqListCheckCapacity(ps);int end = ps->size - 1;//挪动数据while (pos <= end){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

删除指定下标位置的数据

//删除pos下标位置的数据
void SeqListErase(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++;}ps->size--;
}

顺序表优缺点

优点

        支持随机访问。

缺点

        1.空间不够了需要增容，而增容是需要付出代价的。

        2.为了避免频繁扩容，我们满了基本都是扩大2倍，可能会导致一定的空间浪费。

        3.顺序表要求数据从开始位置连续存储，那么我们在头部或者中间位置插入删除数据就需要挪动数据，效率不高。

        （针对顺序表的缺陷，就设计出了链表）

顺序表实战运用

删除有序数组中的重复项

解题思路：

定义三个指针，dst，i，j。使j++、向后移动，判断i和j指向的数据是否相等测定重复数据的范围，j++直到i和j指向的数据不相等，就让nums[dst] = nums[i]，然后i = j，将i移动到j的位置上，dst+1指向下一个需要改变的位置，然后j++继续向后移动测定重复数据的范围。这样dst就可以一个一个将去重后的数据放到数组中。（需要注意j++越界）

代码如下：

//去重
int removeDuplicates(int* nums, int numsSize)//返回数据个数
{if (numsSize == 0)//防止空数组return 0;int i = 0, j = 0;int dst = 0;while (j < numsSize){if (nums[i] != nums[j]){nums[dst] = nums[i];i = j;j++;}else{j++;}}//当j++越界后会导致直接跳出循环，最后一个去重后的数据还需要录入nums[dst] = nums[i];dst++;return dst;
}

合并两个有序数组

思路：

两个指针将两个数组从最后一个开始进行相互比较，大的放进左边大数组的最后一个位置，然后将该已经放入数组的指针向前移动一个位置，然后再进行比较。

大的放进数组中，再将指针前移。

依次向前就可以把两个数组合并。如果是左侧大数组的指针先向左走到头，那么只需要将右侧数组中剩余的元素拷贝到左侧未放入新数据的位置就可以了。

代码实现：

void merge(int* nums1, int muns1Size, int m, int* nums2, int nums2Size, int n)
{int left = m - 1, right = n - 1;int end = m + n - 1;while (right >= 0 && left >= 0){if (nums1[left] > nums2[right]){nums1[end] = nums1[left];end--;left--;}else{nums1[end] = nums2[right];end--;right--;}}if (left < 0){while (right >= 0){nums1[end] = nums2[right];end--;right--;}}
}

（全文完）

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

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

相关文章

二进制的bitset做法

二进制的bitset做法

题目 代码&#xff08;bitset的to_ulong()) 别的学校oj平台过不了&#xff0c;但是用他们后台数据推算&#xff0c;自测是能过的 string -> find bitset erase to_ulong() #include<bits/stdc.h> using namespace std;int main() {int n;cin >> n;getchar…
阅读更多...
SSM药房管理系统—计算机毕业设计源码42430

SSM药房管理系统—计算机毕业设计源码42430

目 录 摘要 1 绪论 1.1课题目的及意义 1.2研究背景 1.3 研究方法 1.4论文结构与章节安排 2 药房管理系统系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.…
阅读更多...
PC端微信多开

PC端微信多开

PC端一键微信多开&#xff0c;应用分身&#xff0c;方便快捷实现&#xff1b;WeChatStart.bat 第一种普通多开 echo off taskkill /F /FI "IMAGENAME eq WeChat.exe" taskkill /F /FI "IMAGENAME eq WeChatCopy.exe" start C:"\Program Files (x86)…
阅读更多...
Java集合框架高频面试问题精粹（下篇）

Java集合框架高频面试问题精粹（下篇）

书接上回&#xff0c;上一篇文章介绍了 Java 集合常见面试题全解&#xff08;上&#xff09;&#xff0c;反响不错&#xff0c;也有很多同学发表了自己的观点&#xff0c;这次又来了&#xff0c;这次是Java集合常见面试题总结&#xff08;下&#xff09;了&#xff0c;主要讲解…
阅读更多...
vue3初始项目结构与分析

vue3初始项目结构与分析

简介 时隔多年再次学习vue&#xff0c;单纯学习刚创立好的项目分析其结构与运作方式&#xff0c;掌握了基础才能在工作中延申 环境&#xff1a; nvm: v1.1.12 node.js: v18.20.5 npm: v10.8.2 vue: 3 visual studio code&#xff1a;v1.95.2 正文 下图抛开HelloVue.vue就是一…
阅读更多...
【51单片机】LCD1602液晶显示屏

【51单片机】LCD1602液晶显示屏

学习使用的开发板&#xff1a;STC89C52RC/LE52RC 编程软件&#xff1a;Keil5 烧录软件&#xff1a;stc-isp 开发板实图&#xff1a; 文章目录 LCD1602存储结构时序结构 编码 —— 显示字符、数字 LCD1602 LCD1602&#xff08;Liquid Crystal Display&#xff09;液晶显示屏是…
阅读更多...
【C#设计模式(6)——适配器模式(Adapter Pattern)】

【C#设计模式(6)——适配器模式(Adapter Pattern)】

前言 C#设计模式(6)——适配器模式(Adapter Pattern) 适配器模式主要用于在不修改现有类的情况下&#xff0c;使本来不包含的类可以一起工作。 代码 //插头接口 public interface IPlug {void Charge(); } //插头适配 public class Adapter {public void ConverterCharge(){Co…
阅读更多...
鸿蒙next ui安全区域适配（刘海屏、摄像头挖空等）

鸿蒙next ui安全区域适配（刘海屏、摄像头挖空等）

目录 相关api 团结引擎对于鸿蒙的适配已经做了安全区域的适配，也考虑到了刘海屏和摄像机挖孔的情况，在团结引擎内可以直接使用Screen.safeArea 相关api
阅读更多...
【C++融会贯通】二叉树进阶

【C++融会贯通】二叉树进阶

目录 一、内容说明 二、二叉搜索树 2.1 二叉搜索树概念 2.2 二叉搜索树操作 2.2.1 二叉搜索树的查找 2.2.2 二叉搜索树的插入 2.2.3 二叉搜索树的删除 2.3 二叉搜索树的实现 2.3.1 二叉搜索树的节点设置 2.3.2 二叉搜索树的查找函数 2.3.2.1 非递归实现 2.3.2.2 递…
阅读更多...
JMeter初体验：从入门到入门的性能测试之旅

JMeter初体验：从入门到入门的性能测试之旅

一、关于性能测试 1、性能测试概述 性能测试是一种非功能测试&#xff0c;旨在评估系统在不同负载条件下的性能表现。它包括负载测试、压力测试、稳定性测试和基准测试等。性能测试的目的是确保系统在预期的负载下能够正常运行&#xff0c;并满足用户对响应时间、吞吐量和其他…
阅读更多...
计算机网络-数据链路层

计算机网络-数据链路层

一、数据链路层所使用的信道类型&#xff1a; 1、点对点信道->PPP协议 2、广播信道。->CSMA/CD协议 二、从层次上看数据的流动 三、数据链路和帧 链路&#xff1a;即物理链路&#xff0c;从一个结点到相邻节点的一段物理链路。 数据链路&#xff1a;逻辑链路&#x…
阅读更多...
Web入门

Web入门

Spring 官网&#xff1a;Spring | Home Spring是一个开源的Java企业级应用开发框架。Spring的主要目的是使Java EE&#xff08;Java Platform, Enterprise Edition&#xff09;开发更容易&#xff0c;并且通过提供一系列丰富的库和接口来促进良好编程实践&#xff0c;是…
阅读更多...
人工智能下半场，全球期待AI超级应用

人工智能下半场，全球期待AI超级应用

人工智能&#xff08;AI&#xff09;这个概念&#xff0c;从1955年的达特茅斯会议开始&#xff0c;已经走过了很长的路。从最初的统计语言模型&#xff0c;到专家系统、神经网络&#xff0c;再到深度学习&#xff0c;AI技术不断进步。2019年到2022年&#xff0c;预训练模型大量…
阅读更多...
西圣、猛玛、科唛领夹麦克风哪个牌子好？领夹麦精品实测大PK

西圣、猛玛、科唛领夹麦克风哪个牌子好？领夹麦精品实测大PK

无线领夹麦克风&#xff0c;这个在音频领域逐渐崭露头角的设备&#xff0c;已经深入到我们生活中的许多场景。从线上会议的清晰收音&#xff0c;到自媒体创作者户外拍摄时的便捷声音采集&#xff0c;它的重要性不言而喻。可是&#xff0c;市场上无线领夹麦克风的乱象令人担忧。…
阅读更多...
哈工大华为出品｜大模型「幻觉」，看这一篇就够了

哈工大华为出品｜大模型「幻觉」，看这一篇就够了

大模型“幻觉”&#xff0c;终于有系统综述了&#xff01; 一口气49页&#xff0c;详细阐述了幻觉定义、分类、导致幻觉的原因&#xff0c;还有检测幻觉、减轻幻觉的方法。 这篇最新综述来自哈工大和华为&#xff0c;一po出就在网上火得不行&#xff1a; 具体来说&#xff0c…
阅读更多...
STM32 BootLoader 刷新项目 (十) Flash擦除-命令0x56

STM32 BootLoader 刷新项目 (十) Flash擦除-命令0x56

STM32 BootLoader 刷新项目 (十) Flash擦除-命令0x56 1. STM32F407 BootLoader 中的 Flash 擦除功能详解 在嵌入式系统中&#xff0c;BootLoader 的设计是非常关键的部分&#xff0c;它负责引导主程序的启动、升级以及安全管理。而在 STM32F407 等 MCU 上实现 BootLoader&…
阅读更多...
J.U.C - 深入解读重入锁和读写锁

J.U.C - 深入解读重入锁和读写锁

文章目录 概述synchronized的缺陷1&#xff09;synchronized不能控制阻塞&#xff0c;不能灵活控制锁的释放。2&#xff09;在读多写少的场景中&#xff0c;效率低下。 独占锁ReentrantLock原理ReentrantLock概述AQS同步队列1. AQS实现原理2. 线程被唤醒时&#xff0c;AQS队列的…
阅读更多...
异地双活容灾技术研究

异地双活容灾技术研究

摘要 随着技术快速发展&#xff0c;尤其是人工智能、大数据等新兴技术的应用&#xff0c;对数据安全提出了新的挑战&#xff0c;平台部署在机房云资源池&#xff0c;当云平台因人为错误原因出现基础设施故障&#xff0c;或自然灾害使得云平台的机房出现停电、断网等故障&#x…
阅读更多...
从Facebook到Meta：公司转型背后的战略与意义

从Facebook到Meta：公司转型背后的战略与意义

2021年&#xff0c;Facebook宣布更名为Meta&#xff0c;转型聚焦于“元宇宙”——这一虚拟世界的构建标志着公司从传统社交平台向更前沿的科技领域迈进。本文将探讨这一转型的背景、战略布局及其深远意义。 一、转型背景&#xff1a;应对市场和技术的挑战 自2004年成立以来&am…
阅读更多...
前端在PC端实现支付思路流程

前端在PC端实现支付思路流程

一.去支付 1.前端点击“去支付”按钮&#xff0c;请求订单详情接口&#xff0c;传递订单的id、订单号给后端和请求支付方式接口 2.后端返回支付信息和支付方式数据 二.弹出支付窗口 接收支付信息和支付方式数据后&#xff0c;前端弹出支付弹窗 三.确认支付 前端无论选择任何…
阅读更多...
最新文章

Copyright @ 2022~2023