数据结构：顺序表+链表

数据结构：顺序表+链表

一。顺序表：

首先在了解顺序表和链表之前，先了解一下线性表，**线性表（linear list）**是n个具有相同特征元素的有限序列 ，在逻辑上是线性结构，也就是一条连续的直线，但是在物理上不一定是连续的。常见的线性表：顺序表，链表，栈，队列…

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

下面将了解顺序表的底层实现逻辑：

接口：

public interface SeqList {
    public void add(int data);//新增元素，默认在数组最后进行新增
    
    public void add(int pos,int data);//新增元素，在pos这个位置加上data这个数据
    
    public boolean contain(int toFind);//查看toFind这个元素是否在数组中存在
    
    public int index(int toFind);//查看这个元素在数组中的下标
    
    public int get(int pos);//获取pos位置的元素
    
    public void set(int pos,int value);//给pos位置的值修改为value
    
    public int remove(int toRemove);//删除第一次出现的的关键字key
    
    public int size();//获取顺序表的长度
    
    public void display();//打印顺序表
}

接口的实现：

import java.util.Arrays;

public class Main implements SeqList{
   private int[] elem=new int[10];
   private int usedSize;
   @Override
   public void add(int data) {
      if(isFull()){
         elem= Arrays.copyOf(elem,elem.length*2);
      }
      this.elem[usedSize]=data;
      usedSize++;
   }
   public boolean isFull(){
      if(usedSize==elem.length){
         return true;
      }
      return false;
   }
   @Override
   public void add(int pos, int data) {
      if(pos<0 || pos>usedSize){
         System.out.println("输入不合法");//可以把这个写进一个方法中，然后写一个异常，如果pos不合法就抛出异常
      }
      if(isFull()){
         elem=Arrays.copyOf(elem,elem.length*2);
      }
      for(int i=usedSize-1;i >=pos;i--){//先把所有的元素向后移动一个单元，当i<pos的时候就结束
         elem[i+1]=elem[i];
      }
      elem[pos]=data;
      usedSize++;
   }

   @Override
   public boolean contain(int toFind) {
      for(int i=0;i<usedSize;i++){
         if(elem[i]==toFind){
            return true;
         }
      }
      return false;
   }

   @Override
   public int index(int toFind) {
      if(this.contain(toFind)){
         for(int i=0;i<usedSize;i++){
            if(elem[i] == toFind){
               return i;
            }
         }
      }
      return 0;
   }

   @Override
   public int get(int pos) {
      if(pos<0||pos>usedSize-1){
         System.out.println("输入的元素不合法");
      }else {
         for (int i=0;i<usedSize;i++){
            if(pos==i){
               //System.out.println(elem[pos]);
               return elem[pos];
            }
         }
      }
      return 0;
   }

   @Override
   public void set(int pos, int value) {
      if(pos<0||pos>usedSize){
         System.out.println("输入不合法");
      }
      elem[pos]=value;
   }

   @Override
   public void remove(int toRemove) {
      int ret=this.index(toRemove);//获取删除元素的下标
      for(int i=ret;i<usedSize-1;i++){
         elem[i]=elem[i+1];
      }
      elem[usedSize-1]=0;
      usedSize--;
   }

   @Override
   public int size() {
      int count=0;
      for(int i=0;i<elem.length;i++){
         count++;
      }
     return count;
   }

   @Override
   public void display() {
      for(int i=0;i<usedSize;i++){
         System.out.println(elem[i]+" ");
      }
   }
}

二。ArrayList的使用

ArrayList是以泛型方式实现的，使用时必须先要将其实例化

1.ArrayList的构造：

List<Integer> list1=new ArrayList<>();//构造一个空的列表
List<Integer> list1=new ArrayList<>(10);//构造一个列表，其中含有10个元素

2.ArrayList的常见操作；

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list1=new ArrayList<>();
        list1.add(10);//加入元素
        list1.add(0,10)//在0下标的位置插入数字10
        list1.remove(1);//删除下标为1的值
        list1.get(2);//获取下标为2的值
        list1.set(1,3);//把下标为1的位置的值改为3
        list1.contain(12);//是否有12这个值在此线性表中
        list1.indexOf(10);//返回第一个值为10的下标
        list1.size();//获取整个顺序表的元素个数  
    }
}

注意：

当实例一个空的列表时，第一次add默认分配一个大小为10的内存（在实例化阶段不分配内存）

扩容是自动以1.5倍的形式扩容

3.顺序表的遍历

//法一：
for(int i=0;i<list.size();i++){
  System.out.println(list.get(i));
}
//法二：
System.out.println(list);

三。ArrayList的具体使用例子

杨辉三角的实现：

在这里插入图片描述

上述这个图片就是我们常说的杨辉三角，在高中的时候没少接触这个东西

这个杨辉三角主要的实现方式是通过二维顺序表实现的，下面将对用二维顺序表来实现杨辉三角的实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Soulation {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入");
        int input=sc.nextInt();
        List<List<Integer>> list=new ArrayList<>();
        //第一行的导入
        List<Integer> arr=new ArrayList<>();
        arr.add(1);
        list.add(arr);
        //从第二行开始，进行计算、
        for(int i=1;i<input;i++){
            List<Integer> curRow=new ArrayList<>();
            curRow.add(1);
            List<Integer> prevRow=list.get(i-1);
            for(int j=1;j<i;j++){
                int val=prevRow.get(j)+prevRow.get(j-1);
            }
            curRow.add(1);
            list.add(curRow);
        }
    }
}

四。链表：

在介绍链表之前，先说一下ArrayList的缺点；当在ArrayList任意位置进行删除元素或者增加元素的时候，就需要将所有元素进行前移或者后移，这样时间复杂度就是O(n)，效率非常低，因此涉及到数据的大量插入和删除的操作就不太适合ArrayList了，因此引入了链表来解决这个问题

链表是一种物理存储上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接的次序进行实现的（物理上是不连续的，但是逻辑上是连续的）

图示：

五。无头单向链表的实现

接口：

public interface SingleLinkedList {
    public void add(int data);//头插法
  
    public void addLast(int data);//尾插法

    public void addIndex(int index,int data);//把data插入到index位置

    public boolean contains(int key);//链表中是否存在数据key

    public void remove(int key);//删除第一次出现key数据的节点

    public void display();//展示链表中所有的元素
}

接口的实现：

public class SingleList implements SingleLinkedList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;

    @Override
    public void add(int data) {
        ListNode node=new ListNode(data);
        if(this.head==null){
            head=node;
        }else {
            node.next=head;
            head=node;
        }
    }

    @Override
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        ListNode cur=head;
        if(head==null){
            head=node;
        }else{
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        ListNode node=new ListNode(data);
        int count=0;
        ListNode cur=head;
        if(head==null){
            head=node;
        }else{
            while(cur.next!=null){
                if(count==index-1){
                    ListNode hi=cur.next;
                    cur.next=node;
                    node.next=hi;
                    break;
                }
                count++;
            }
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur=head;
        if(head==null){
            return false;
        }else{
            while(cur.next!=null){
                if(cur.val==key){
                    return true;
                }
                cur=cur.next;
            }
        }
        return false;
    }

    @Override
    public void remove(int key) {
        ListNode cur=head;
        ListNode last=head;
        if(head.val==key){
            head=head.next;
        }//当要删除的值是链表的第一位的时候
        while(cur.next!=null){
            cur=cur.next;
            if(cur.val==key){
                last.next=cur.next;
            }
            last=last.next;
        }
    }

    @Override
    public void display() {
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }
}

主函数：

public class Main {
    public static void main(String[] args) {
        SingleList singleList=new SingleList();
        singleList.addLast(12);
        singleList.addLast(23);
        singleList.addLast(34);
        singleList.addLast(45);
        singleList.addIndex(1,2);
        singleList.display();
        System.out.println(singleList.contains(2));
        singleList.remove(23);
        singleList.display();
    }
}

以上就是单链表的增删查所有的代码，大家可以尝试自己写一遍

六。LinkedList的使用

1.LinkedList介绍：

LinkedList本质上是一个双向链表，由于链表没有将元素存储在连续的空间之中，元素存储在单独的节点之中，然后通过引用节点将节点连接起来了，因此在插入或删除元素的时候，不需要搬移元素，效率较高

2.LinkedList的构造：

List<Integer> list1=new LinkedList<>();

3.LinkedList的其他方法的介绍：

list1.add(45);//尾插45
list1.add(3,10);//在3这个位置插入10这个数字
list1.remove(2);//删除2位置这个元素
list1.get(2);//获取下标为2的元素的值
list1.set(2,199);//把下标为2的位置的值改为199
list1.contains(199);//查看此链表中是否含有199这个数字
list1.indexOf(199);//返回这个链表中第一次出现199这个元素的下标

4.LinkedList的遍历：

法一：

System.out.println(list);

法二：

for(int i=0;i<list.size;i++){
  System.out.println(list.get(i));
}

七。ArrayList与LinkedList的区别

不同点ArrayListLinkedList
存储空间上物理上连续逻辑上连续，但是物理上不一定连续
随机访问支持不支持
头插需要搬移元素，效率低，O（n）只用修改引用的指向，空间复杂读：O（1）
插入空间不够时可以进行扩容没有容量大概念
应用场景元素高效存储+频繁访问任意位置删除添加频繁

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

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

相关文章

深入剖析预处理

深入剖析预处理

目录 1.预定义符号 2.#define 定义常量 3.#define定义宏 4.带有副作用的宏参数 5.宏替换的规则 6.宏函数的对比 7.#和## 7.1 #运算符 7.2 ## 运算符 8.命名约定 9.#undef 10.命令行定义 11.条件编译 12.头文件的包含 12.1 头文件被包含的方式&#xff1a; 12.1…
阅读更多...
React setState

React setState

老生常谈之setState 是同步的还是异步的&#xff1f; 设想setState是同步的&#xff0c;那也就是每次调用setState都要进行新旧虚拟DOM的对比&#xff0c;然后将差异化的dom更新到页面上&#xff0c;性能损耗很大 所以react把setState设置为了异步&#xff0c;当状态更新时不…
阅读更多...
基于springboot+vue实现的厨艺交流平台（文末源码+Lw）093

基于springboot+vue实现的厨艺交流平台（文末源码+Lw）093

93基于SpringBootVue的实现的厨艺交流平台&#xff08;源码数据库万字Lun文流程图ER图结构图演示视频软件包&#xff09; 系统功能&#xff1a; 这次开发的厨艺交流平台功能有个人中心&#xff0c;食材分类管理&#xff0c;用户管理&#xff0c;菜品分类管理&#xff0c;菜谱信…
阅读更多...
【Axure】产品原型如何在谷歌浏览器中打开

【Axure】产品原型如何在谷歌浏览器中打开

作为一名前端开发来说&#xff0c;在拿到产品的原型图后&#xff0c;如何打开&#xff1f;直接用谷歌浏览器打开&#xff0c;是打不开的&#xff0c;需要安装对应的插件。但是谷歌插件市场在不翻墙的情况下&#xff0c;是没有办法直接打开的&#xff0c;分享一种超级简单的方法…
阅读更多...
Softmax回归中的损失函数

Softmax回归中的损失函数

目录 一、损失函数介绍&#xff1a; 因为Softmax回归时逻辑回归的推广&#xff0c;所以Softmax回归的损失函数是逻辑回归损失函数的推广。 原文链接&#xff1a;逻辑回归中的损失函数 一、损失函数介绍&#xff1a; 与回归问题成本函数不同的是&#xff0c;Softmax回归模型&a…
阅读更多...
python-小杨的储蓄（赛氪OJ）

python-小杨的储蓄（赛氪OJ）

题目描述 小杨共有 N 个储蓄罐&#xff0c;编号从 0 到 N−1。从第 1 天开始&#xff0c;小杨每天都会往存钱罐里存钱。具体来说&#xff0c;第 i 天他会挑选一个存钱罐 ai​&#xff0c;并存入 i 元钱。过了 D 天后&#xff0c;他已经忘记每个储蓄罐里都存了多少钱了&#xff…
阅读更多...
如何网页在线编辑微软Office Word，并导出为PDF格式。

如何网页在线编辑微软Office Word，并导出为PDF格式。

随着互联网技术的不断发展&#xff0c;越来越多的企业开始采用在线办公模式&#xff0c;微软Office Word 是最好用的文档编辑工具&#xff0c;然而doc、docx、xls、xlsx、ppt、pptx等格式的Office文档是无法直接在浏览器中直接打开的&#xff0c;如果可以实现Web在线预览编辑Of…
阅读更多...
Vue3 pdf.js将二进制文件流转成pdf预览

Vue3 pdf.js将二进制文件流转成pdf预览

好久没写东西&#xff0c;19年之前写过一篇Vue2将pdf二进制文件流转换成pdf文件&#xff0c;如果Vue2换成Vue3了&#xff0c;顺带来一篇文章&#xff0c;pdf.js这个东西用来解决内网pdf预览&#xff0c;是个不错的选择。 首先去pdfjs官网&#xff0c;下载需要的文件 然后将下载…
阅读更多...
通用后台管理（二）——项目搭建

通用后台管理（二）——项目搭建

目录 前言 一、安装vue-cli依赖 1、使用yarn下载vue-cli 2、使用npm下载 3、检查一下是否下载成功 二、创建项目 1、创建项目&#xff0c;my-app是项目名称 2、 这里选择vue 2&#xff0c;蓝色表示选中的。 3、启动项目 三、下载项目依赖 四、配置项目 1、修改esli…
阅读更多...
哪些独立站外链策略最有效？

哪些独立站外链策略最有效？

在当前的SEO领域中&#xff0c;独立站外链策略的效果差异很大&#xff0c;但GPB外链无疑是其中最为有效的一种。GPB外链&#xff0c;指的是通过高质量、包收录且dofollow的顶级域名独立站来获得外链&#xff0c;这种外链策略能够显著提升目标网站的整体排名数据。 关键词排名的…
阅读更多...
最全 Steam 流操作！！！Java Stream 流操作常用 API

最全 Steam 流操作！！！Java Stream 流操作常用 API

文章目录 Java Stream 流操作常用 API一、准备工作二、Stream 常用 API1、sorted 排序2、list 转为 map(并解决重复key问题)3、filter 方法过滤指定查询条件4、根据指定列分组5、通过 map 获取指定列集合6、根据 List 中 Object 某个属性去重7、list 统计&#xff08;求和、最大…
阅读更多...
Nignx配置

Nignx配置

Nginx配置之nginx.conf文件解析及配置 1、nginx.conf文件解析 user www-data; worker_processes auto; pid /run/nginx.pid; include /etc/nginx/modules-enabled/*.conf;events {worker_connections 768;# multi_accept on; }http {### Basic Settings###开启文件的高效传输…
阅读更多...
RK3568------Openharmony 4.0-Release WIFI/BT模组适配

RK3568------Openharmony 4.0-Release WIFI/BT模组适配

RK3568------Openharmony 4.0-Release WIFI/BT模组(ap6236)适配 文章目录 RK3568------Openharmony 4.0-Release WIFI/BT模组(ap6236)适配前言一、驱动移植二、设备树配置三 、内核配置四、遇到的问题五、效果展示总结 前言 随着RK3568适配工作的推进&#xff0c;整体适配工作…
阅读更多...
差分+前缀和习题集

差分+前缀和习题集

&#xff08;luogu题号&#xff09; P6568 [NOI Online #3 提高组] 水壶 思路分析 前缀和优化问题。 其实题意就是让你求有k1个数的区间和最大值&#xff0c;那么直接前缀和优化&#xff0c;就可以通过本题。 代码 #include<bits/stdc.h> using namespace std;const in…
阅读更多...
spring的bean注册

spring的bean注册

bean注册 第三方jar包的类想添加到ioc中&#xff0c;加不了Component该怎么办呢。 可以使用Bean和Import引入jar包&#xff0c;可以使用maven安装到本地仓库。 修改bean的名字&#xff1a;Bean("aaa")使用ioc的已经存在的bean对象&#xff0c;如Country&#xff1a;p…
阅读更多...
【数据分享】1981—2023年中国逐日归一化植被指数（NDVI）栅格数据

【数据分享】1981—2023年中国逐日归一化植被指数（NDVI）栅格数据

NDVI&#xff0c;全名为Normalized Difference Vegetation Index&#xff0c;中文名称为归一化植被指数。这个指数可以用来定性和定量评价植被覆盖及其生长活力&#xff0c;我们也可以简单地将它理解为体现植被密度和健康状况的一个指标。 本次我们给大家分享的是1981年6月24日…
阅读更多...
VSCode用ssh连接ubuntu虚拟机实现远程访问文件夹

VSCode用ssh连接ubuntu虚拟机实现远程访问文件夹

1. ubuntu安装ssh服务 1.1 安装 sudo apt-get install ssh sudo apt-get install openssh-server1.2 启动ssh服务 sudo service ssh start sudo service ssh status # 查看状态 ## 或者用下面方式重启ssh服务 ## /etc/init.d/ssh restart1.3 ssh服务加入开机启动 sudo syst…
阅读更多...
从天空到地面：无人机航拍推流直播技术在洞庭湖决口封堵中的全方位支援

从天空到地面：无人机航拍推流直播技术在洞庭湖决口封堵中的全方位支援

据新闻报道&#xff0c;受持续强降雨影响&#xff0c;湖南省华容县团洲垸洞庭湖一线堤防发生管涌险情&#xff0c;随后出现决口。截至7月8日20时左右&#xff0c;226米长的洞庭湖一线堤防决口已累计进占208米&#xff0c;目前剩余18米&#xff0c;有望在今晚或9日凌晨实现合龙。…
阅读更多...
python爬虫基础入门

python爬虫基础入门

步骤 获取网页内容&#xff1a; http请求 python的Requests库 解析网页内容 html网页结构 python的Beautiful Soup库 储存或分析数据 储存进数据库 作为ai分析的数据 转化为图表显示出来 DDoS攻击 通过给服务器发送海量高频请求&#xff0c;大量消耗网页资源&#…
阅读更多...
加密与安全_密钥体系的三个核心目标之完整性解决方案

加密与安全_密钥体系的三个核心目标之完整性解决方案

文章目录 Pre机密性完整性1. 哈希函数&#xff08;Hash Function&#xff09;定义特征常见算法应用散列函数常用场景散列函数无法解决的问题 2. 消息认证码&#xff08;MAC&#xff09;概述定义常见算法工作原理如何使用 MACMAC 的问题 不可否认性数字签名&#xff08;Digital …
阅读更多...
最新文章

Copyright @ 2022~2023