Java,数据结构与集合源码,数据结构概述

目录

数据结构概念:

数据结构的研究对象:

研究对象一,数据间逻辑关系:

研究对象二,数据的存储结构(或物理结构):

研究对象三:运算结构

数据结构的相关介绍:

链表:

单向链表:每个节点有记录下一个节点的信息

双向链表:每个节点有记录上一个节点的信息和记录上一个节点的信息。

二叉树:每个节点分别后来的两条节点,层层递进。

栈:(Stack)又称为堆栈或堆叠,是限制在表的一端进行插入和删除运算的线性表。

队列:(queue)


数据结构概念:

数据结构是程序设计优化的方法论研究数据的逻辑结构和物理结构以及它们之间的相互关系,并对这种结构定义相应的运算,目的是加快程序的执行速度、减少内存占用的空间。

数据结构的研究对象:

研究对象一,数据间逻辑关系:

①集合结构:数据结构之间的元素只有“同属于同一个集合”的关系。

②线性结构:数据结构中的元素存在一对一的相互关系。(体现:一维数组,链表,栈,队列)

③树形结构:数据结构中的元素存在一对多的相互关系。

④图形结构:数据结构中的元素之间存在多对多的相互关系。

研究对象二,数据的存储结构(或物理结构):

①顺序结构:使用一组连续的存储单元依次存储逻辑上相邻的各个元素。

优点:只需要申请存放数据本身的内存空间即可,支持下标访问,也可以实现随机访问。

缺点:必须静态分配连续空间,内存的利用率较低。插入或删除可能要移动大量元素,效率低。

②链式结构:不使用连续的空间存放结构的元素,而是为每一个元素构造一个节点。节点中除了存放数据本身之外,还需要存放指向下一个节点的指针。

优点:不采用连续的存储空间从而内存空间利用率更高,克服顺序存储结构中预知元素个数的缺点。插入或删除元素时不需要移动大量元素。

缺点:需要额外的空间来表达数据之间的逻辑关系,不支持下标访问和随机访问。

③索引结构:除了建立存储节点信息之外,还建立附加的索引表来记录每个元素节点的地址。索引表由若干索引项组成。索引项的一般形式是:(关键字,地址)

优点:用节点的索引号来来确定节点存储地址,检索速度快。

缺点:增加了附加的索引表,会占用较多的存储空间。在增加和删除数据时要修改索引表,会花费较多的时间。

④散列结构:根据元素的关键字直接计算出该元素的存储地址,又称Hash存储。

优点:检索、增加和删除节点的操作都很快。

缺点:不支持排序,一般比线性表存储需要更多的空间,并且记录的关键字不能重复。

研究对象三:运算结构

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的,指出运算的功能。运算的实现是针对存储结构的,指出运算的具体操作步骤。

·分配资源,建立结构,释放资源

·插入和删除

·获取和遍历

·修改和排序

数据结构的相关介绍:

链表:

单向链表:每个节点有记录下一个节点的信息

模拟单向链表的代码如下:

package 数据结构.链表.单向链表;


public class Test
{
    public static void main(String[] args)
    {
        Node n1 = new Node("aaa");
        Node n2 = new Node("bbb");
        Node n3 = new Node("ccc");
        n1.next = n2;//记录下一个元素
        n2.next = n3;//记录下一个元素
        //尾节点没有下一个元素,next赋值为null
    }
}
class Node
{
    Object Data;//用于记录本节点的数据
    Node next;//用于记录下一个元素


    public Node()
    {
    }


    public Node(Object data)
    {
        Data = data;
    }
}

双向链表:每个节点有记录上一个节点的信息和记录上一个节点的信息。

模拟双向链表的代码如下:

package 数据结构.链表.双向链表;


public class Test
{
    public static void main(String[] args)
    {
        Node n1 = new Node("aaa");
        Node n2 = new Node("bbb");
        Node n3 = new Node("ccc");
        Node n4 = new Node("ddd");
        Node n5 = new Node("eee");
        n1.next = n2;//记录下一个元素
        //头节点没有上一个元素,prev赋值为null


        n2.next = n3;//记录下一个元素
        n2.prev = n1;//记录上一个元素


        n3.next = n4;//记录下一个元素
        n3.prev = n2;//记录上一个元素


        n4.next = n5;//记录下一个元素
        n4.prev = n3;//记录上一个元素


        n5.prev = n4;//记录上一个元素
        //尾节点没有下一个元素,next赋值为null
    }
}
class Node
{
    Object Data;//用于记录本节点的数据
    Node prev;//用于记录上一个元素
    Node next;//用于记录下一个元素


    public Node()
    {
    }


    public Node(Object data)
    {
        Data = data;
    }
}

二叉树:每个节点分别后来的两条节点,层层递进。

模拟二叉树的代码如下:

package 数据结构.二叉树;


public class Test
{
    public static void main(String[] args)
    {
        TreeNode t1 = new TreeNode("aaa");
        TreeNode t2 = new TreeNode("bbb");
        TreeNode t3 = new TreeNode("ccc");
        TreeNode t4 = new TreeNode("ddd");
        TreeNode t5 = new TreeNode("eee");
        TreeNode t6 = new TreeNode("fff");
        TreeNode t7 = new TreeNode("ggg");
        t1.left = t2;//左分支
        t1.right = t3;//右分支


        t2.parent = t1;//父节点
        t2.left = t4;//左分支
        t2.right = t5;//右分支


        t3.parent = t1;//父节点
        t3.left = t6;//左分支
        t3.right = t7;//右分支


        t4.parent = t2;//父节点
        t5.parent = t2;//父节点


        t6.parent = t3;//父节点
        t7.parent = t7;//父节点
    }
}
class TreeNode
{
    Object Data;//本节点信息
    TreeNode left;//左分支
    TreeNode right;//右分支
    TreeNode parent;//父节点


    public TreeNode()
    {
    }


    public TreeNode(Object data)
    {
        Data = data;
    }
}

结构图如图:

 

栈:(Stack)又称为堆栈或堆叠,是限制在表的一端进行插入和删除运算的线性表。

最先进入的数据被压入栈底,最后的数据在栈顶。每次删除(退栈),删除的总是当前栈中最后进入(进栈)的元素,而最先插入的数据在栈底,最后退栈。(后进先出,先进后出)

·属于抽象数据类型。

·可以使用数组或链表来构建

栈的模拟代码如下:

package 数据结构.栈;


import java.util.Arrays;


public class Test
{
    public static void main(String[] args)
    {
        Stack ss = new Stack(5);
        ss.push("abc");
        ss.push("def");
        ss.push("ghi");
        System.out.println(Arrays.toString(ss.values));
        ss.pop();
        System.out.println(Arrays.toString(ss.values));
    }
}
class Stack{
    Object[] values;//栈中的元素
    int size;//用来记录存储元素的个数


    public Stack(int length)
    {
        values = new Object[length];
    }
    //入栈
    public void push(Object ele)
    {
        if(size >= values.length)
        {
            throw new RuntimeException("栈空间已满");
        }
        values[size] = ele;
        size++;
    }
    //出栈
    public Object pop()
    {
        if(size <= 0)
        {
            throw new RuntimeException("栈空间已空");
        }
        Object o = values[size - 1];
        values[size - 1] = null;
        size--;
        return o;
    }
}

队列:(queue)

·属于抽象数据类型

·元素的添加获取满足“先进先出”。

队列的模拟代码如下:

package 数据结构.队列;


public class Test
{

}
class Queue
{
    Object[] values;
    int size;//记录村存储的数据的个数
    public Queue(int length)
    {
        values = new Object[length];
    }
    public void add(Object ele)//添加
    {
         if(size >= values.length)
         {
             throw new RuntimeException("队列已满");
         }
         values[size] = ele;
         size++;
    }
    public Object get()//获取
    {
        if(size <= 0)
        {
            throw new RuntimeException("队列已空");
        }
        Object o = values[0];
        //数据前移
        for (int i = 0; i < size - 1; i++)
        {
            values[i] = values[i + 1];
        }
        //最后一个元素置空
        values[size - 1] = null;
        return o;
    }
}

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

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

相关文章

C++初阶--类型模板

文章目录 泛型编程函数模板使用通用加法函数多模板参数必须用实例化 函数模板的原理类模板使用 注意事项 泛型编程 先看一个例子&#xff1a; 这是一些对于Swap重载的函数&#xff0c;区别是类型不同&#xff1b; 虽然能够重载使用&#xff0c;但代码复用率比较低&#xff0c…

C++11新特性 变参模板、完美转发和emplace

#include <iostream> #include <vector> #include <deque> #include <list> #include <algorithm> using namespace std;class student { public:student() {cout << "无参构造函数被调用!" << endl;}student(int age, st…

C++静态链接库的生成以及使用

目录 一.前言二.生成静态链接库三.使用静态链接库四.其他 一.前言 这篇文章简单讨论一下VS如何生成和使用C静态链接库&#xff0c;示例使用VS2022环境。 二.生成静态链接库 先创建C项目-静态库 然后将默认生成的.h和.cpp文件清理干净&#xff0c;当然你也可以选择保留。 然…

Spring:IoC,AOP的简单理解与使用

IoC容器 IoC &#xff0c;Spring全家桶各个功能模块的基础&#xff0c;是创建对象的容器。 IoC概念 控制反转&#xff0c;将对象的创建进行反转&#xff0c;常规情况下对象由开发者手动创建&#xff0c;而使用IoC不再需要创建对象&#xff0c;由IoC容器根据需求自动创建项目…

2023年【上海市安全员C3证】考试内容及上海市安全员C3证复审考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 上海市安全员C3证考试内容是安全生产模拟考试一点通总题库中生成的一套上海市安全员C3证复审考试&#xff0c;安全生产模拟考试一点通上上海市安全员C3证作业手机同步练习。2023年【上海市安全员C3证】考试内容及上海…

MyCAT2的主从配置

http://t.csdnimg.cn/KzwDy&#xff08;mysql主从搭建&#xff09; 前提&#xff0c;先搭建好MySQL的主从配置&#xff0c;登录MyCAT 2在MyCAT2里面操作&#xff0c;也就是连接8066这个端口。 一、创建数据源 ​​​​​​​1.创建数据源 添加读写的数据源 /* mycat:createD…

U4_1:图论之DFS/BFS/TS/Scc

文章目录 一、图的基本概念二、广度优先搜索&#xff08;BFS&#xff09;记录伪代码时间复杂度流程应用 三、深度优先搜索&#xff08;DFS&#xff09;记录伪代码时间复杂度流程时间戳结构BFS和DFS比较 四、拓扑排序一些概念有向图作用拓扑排序 分析伪代码时间复杂度彩蛋 五、强…

阿里云oss存储文件上传功能实现(保姆级教程)

先登录&#xff1a; 点击进入控制台 点击左上角导航栏按钮 搜索oss&#xff0c;点击进入 进入之后点击立即开通oss按钮&#xff0c;开通之后点击下图立即创建&#xff0c;弹出创建Bucket 填上Bucket名称&#xff0c;读写权限改为公共读。其他不变点击确定创建&#xff0c;完成…

uniapp、微信小程序返回上页面刷新数据

目录 前言&#xff1a; 方法1&#xff1a; 方法2&#xff1a; 方法3&#xff1a; 前言&#xff1a; 返回上页面刷新数据这个功能主要用于在当前页面点击跳转到另一个页面之后&#xff0c;在另一个页面对数据进行了操作&#xff0c;比如&#xff1a;阅读量&#xff0c;然后返…

计算机组成原理-主存储器与CPU的连接

文章目录 知识总览单块存储芯片与CPU的连接位扩展&#xff08;存储字的位数&#xff09;字扩展&#xff08;存储字数&#xff09;关于线选法和片选法字位同时扩展总结补充&#xff1a;译码器 知识总览 单块存储芯片与CPU的连接 数据总线&#xff0c;地址总线&#xff0c;片选线…

Web 自动化神器 TestCafe—页面基本操作篇

前 言 Testcafe是基于node.js的框架&#xff0c;以操作简洁著称&#xff0c;是web自动化的神器 今天主要给大家介绍一下testcafe这个框架和页面元素交互的方法。 一、互动要求 使用 TestCafe 与元素进行交互操作&#xff0c;元素需满足以下条件&#xff1a;☟ 元素在 body 页…

迅为RK3568开发板学习之Linux驱动篇第十三期输入子系统

驱动视频全新升级&#xff0c;并持续更新~更全&#xff0c;思路更科学&#xff0c;入门更简单。 迅为基于iTOP-RK3568开发板进行讲解&#xff0c;本次更新内容为第十三期&#xff0c;主要讲解输入子系统&#xff0c;共计24 讲。 关注B站&#xff1a;北京迅为电子&#xff0c;在…

Parallel Diffusion Models of Operator and Image for Blind Inverse Problems

盲逆问题算子和图像的并行扩散模型 论文链接&#xff1a;https://arxiv.org/abs/2211.10656 项目链接&#xff1a;https://github.com/BlindDPS/blind-dps Abstract 在正向算子已知的情况下(即非盲)&#xff0c;基于扩散模型的逆问题求解器已经展示了最先进的性能。然而&…

OSG文字-各种文字效果(边框、阴影及颜色倾斜)示例(2)

各种文字效果(边框、阴影及颜色倾斜)示例 各种文字效果(边框、阴影及颜色倾斜)示例的代码如程序清单9-2所示&#xff1a; 1. /* 各种文字效果(边框、阴影及颜色倾斜)示例 */ 2. osg::ref_ptr<osg::Camera> createAllKindText(const string &strDataFolder) 3. {…

华为云cce中环境变量的使用

如上图&#xff0c;cce中的环境变量可配置。 配置后的这些参数怎么用呢&#xff1f; 我们可以在docker打包前在springboot的配置文件中配置&#xff0c;cce在启动的时候会调用环境变量中的设置。 如上图&#xff0c;配置的东西以key值标记&#xff0c;冒号后面的是默认配置项…

YOLO改进系列之注意力机制(GatherExcite模型介绍)

模型结构 尽管在卷积神经网络&#xff08;CNN&#xff09;中使用自底向上的局部运算符可以很好地匹配自然图像的某些统计信息&#xff0c;但它也可能阻止此类模型捕获上下文的远程特征交互。Hu等人提出了一种简单&#xff0c;轻量级的方法&#xff0c;以在CNN中更好地利用上下…

ssm+vue的药店药品信息管理系统(有报告)。Javaee项目,ssm vue前后端分离项目。

演示视频&#xff1a; ssmvue的药店药品信息管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;ssm vue前后端分离项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结…

Run Legends将健身运动游戏化,使用户保持健康并了解Web3游戏

最近&#xff0c;我们有机会采访Talofa Games的首席执行官兼创始人Jenny Xu&#xff0c;一起讨论游戏开发&#xff0c;Talofa Games是Run Legends这款健身游戏的开发工作室。她已经创作了超过一百款游戏&#xff0c;对于推动游戏的可能性并将她的创造力和叙事技巧带入她最喜爱的…

简单但好用:4种Selenium截图方法了解一下!

前言 我们执行UI自动化操作时&#xff0c;大多数时间都是不在现场的&#xff0c;出现错误时&#xff0c;没有办法第一时间查看到&#xff0c;这时我们可以通过截图当时出错的场景保存下来&#xff0c;后面进行查看报错的原因&#xff0c;Selenium中提供了几种截图的方法&#x…

【Linux学习笔记】基础IO

这里写目录标题 1. 系统文件I/O1.1. 接口介绍1.2. 库函数接口与系统接口的关系 2. 文件描述符fd2.1. 0&1&2文件描述符2.2. 文件描述符的分配规则2.3. 重定向2.4. 重定向系统调用2.5. 进程独立性 3. Linux下一切皆文件4. 缓冲区4.1. 缓冲区的理解4.2. 缓冲区的位置 5. 理…