数据结构(data structure)（1）链表和线性表

 类和对象

对象将数据和操作打包在一起，类描述了这一切
用构造器创建(实例化)对象
类和类之间的关系
-关联（组合，聚集）
-泛化

private class Student{
    protected String name;
    protected int age;
    protected int ability;

    public Student(String name,int age){
        this.name=name;
        this.age=age;
    }
4

    public  void study(){
        ability++;
    }

    public String toString(){
         return "Student{"+"name="+name+'\''+",age"+age+",ability="+ability+'}';
    }

    public boolean equals(Object o){
        if(this==o)return true;
        if(o==null||getClass()!=o.getClass())return false;

        Student student =(Student)o;
        return name.equals(student.name);
    }

    public static void main(String[] args){
          Student stu1=new Student();
          Student stu2=new Student();

          System.out.println(stu1.toString());
          System.out.println(stu1.equal(stu2));
    }
}

关于继承

祖先类Object
方法重写
toString方法
equals方法

public class CleverStudent extends Student{
    public CleverStudent(String name,int age){

    super(name,age);
    }

    public void study(){
    super.study();
    super.study();
    }

    public void study(int s){
        ability+=s;
    }
}


Comparable接口，比较大小
Comparator接口,比较器
Cloneable接口，克隆
seriazable接口，可序列化，io接入网路需要

数据结构基本概念

数据(data)
数据元素(data element)
数据对象(data object)

数据是一种泛指

数据对象
数据元素
数据项

（数据对象）student
{
    （name（数据项）,age）   (数据元素)
}

数据结构(data structure)

辑结构
集合:元素罗列在一起
线性结构:元素前后相继(一一对应)
树形结构:(元素存在一对多的关系)
图结构或网状结构：元素之间存在多对多的结构

存储结构
-顺序存储:地址连续，用数组
-链式存储:地址不连续，用指针(引用，面向对象)


Create建立
Destroy消除
Delete删除
Insert插入
Access访问
Modify修改
Sort排序
Search查找
增删改查排历

 列表:顺序表和链表

定义列表接口
用数组实现列表-MyArrayList
实现列表
Java List API

 顺序表

public interface MyList{

    //新增一个元素
    void add(Object element);
    //删除相同元素
    void delete(Object element)
    //根据索引删除元素
    void delete(int index);

    //将指定索引位置的·元素替换成新元素
    void update(int index,Object newElement);

    //当前列表中是否含有target元素
    boolean contains(Object target);

    //返回指定索引处元素
    Object indexOf(int index);

}

    public class MyArrayList implements MyList{

    private int size=0//元素个数

    private int capacity;//容量

    public MyArrayList(int capacity){
        this.capacity=capacity;
        elements=new Object[capacity];
}
          //新增一个元素
    void add(Object element){
        if(size==capacity)//扩容
        {
         capacity*=2;//增加一倍的容量
          Object[] newArr=new Object[capacity];//把旧的柜子扔掉
           newArr[i]=elements[i];
           }
        elements[size++]=element;
    }

    //删除相同元素
    void delete(Object element){
    int index=indexOf(element);
    if(index>=0){
    delete(index);
    }

    }
    //根据索引删除元素
    void delete(int index){
    for(int i=index;i<size;i++){
        elements[i]=elements[i+1];
    }
    size--;

    }
    //将指定索引位置的·元素替换成新元素
    void update(int index,Object newElement){
    elemenyts[index]=newElement;
    }

    //当前列表中是否含有target元素
    boolean contains(Object target){

    }

    //返回指定索引处元素
    Object at(int index){
        return elements[index];
    }

     //查找element的索引，如果没有返回-1
    Object indexOf(Object element){
    for(int i=0;i<size;i++){
    if(elements[i].equals(element))
        return i;
    }

    return -1;
    }
    public String toString(){
    StringgBuilder sb=new StringBuilder("[");
        for(int i=0;i<size;i++){
        sb.append(elements[i]+(i==size-1?"":","));
        }
        sb.appen("]");
        return sb.toString();
    }

    }


publi class MyArraylistTest{
    public  void add() throw Exception{
    MyArrayList list=new MyArrayList();
    list.add("nike");
    List.add("addidiaos");
    List.add("nb");
    }


}

单链表

head头节点,Node[data,point]->[data,point]->[]->[]

public class ListNode{
    private Object data;
    private ListNode next;

    public ListNode(data){
    this.data=data;
    }



}

public class SingleLinkedList implements Mylist{
        private ListNode first;//头节点

        private ListNode last;//尾节点

        public void add(Object element){
            if(first==null){//如果头节点为空,将新增节点给头节点
       first=new ListNode(element);
       last=head;//此时尾节点等于头节点
        }else{
        last.next=new ListNode(element);//新增节点
        last=last.Next;//尾节点更新到新增的一个节点位置上
        }

        size++;
}
                  //新增一个元素

    //删除相同元素
  public  void delete(Object element){
        ListNode p=first;
        ListNode pre=null;//p前面的位置
        while(p!=null){
            if(p.data.equals(element)){
                  if(p==first){//如果删除头指针元素，让头指针往后挪一位就可以了
                  first=first.next;
                  }
                pre.next=p.next;
                break;
            }
            pre=p;//等于p的位置，p再移动一位,pre就在p的前面了
            p=p.next;
        }
        size--;
    }
    //根据索引删除元素
   public void delete(int index){
        if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;
        ListNode p=first;
        ListNode pre=null;

        while(p!=null){
          if(i==index){
            if(p==first){
                first=first.next;
            }else{
                pre.next=p.next;

            }
            break;
          }
            pre=p;
            p=p.next;
            i++;
        }

           、size--;
    }

    //将指定索引位置的·元素替换成新元素
    public void update(int index,Object newElement){
        if(index<0||index>=size){
        return;
        }

        int i=0;
        ListNode p=first;

        while(p!=null){
            if(i==index){
            p.data=newElement;
            break;
            }
            p=p.next;
            i++;
        }

    }

    //当前列表中是否含有target元素
   public  boolean contains(Object target){
        ListNode p=first;
        while(p!=null){
            if(p.data.equals(target)){
              return true;
            }
            p=p.next;
        }
        return false;
    }

    //返回指定索引处元素
    public Object at(int index){
    if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;//指针指向的节点的索引
        ListNode p=first;
        while(p!=null){
          if(i==index){
            return p.data;
            break;
          }
            p=p.next;
            i++;
        }
    }


    public int indexOf(Object element){

        int i=0;//指针指向的节点的索引
        ListNode p=first;
        while(p!=null){
          if(p.data.equals(element)){
            return i;
            break;
          }
            p=p.next;
            i++;
        }

    return -1;
    }

        public String toString(){
            StringBuilder sb=new StringBuilder();
            ListNode p=first;
            while(p.next!=null){
            sb.append(p.data).append(",");
            p=p.next;
            }
            sb.append("]");
            return sb.toString();

        }


}

//增和删链表更快

双向链表

first和last是亚元所代表的值为null
          <-    <-    <-
null->head->Node->Node->tail->null
a0     a1    a2    a3
双向链表结构

public class ListNode{
    Object data;
    ListNode pre;
    ListNode next;
    public listNode(Object data){this.data=data;}
}



public class DoubleLinkedList implements Mylist{
        private ListNode first=new ListNode(null);//头节点

        private ListNode last=new ListNode(null);//尾节点

        private size=0;

        public DoubleLinkList(){

        first.next=last;
        last.pre=first;

        }

        public void add(Object element){

        ListNode newNode=new ListNode(element);
        last.pre.next=newNode;
        newNode.next=last;
        newNode.pre=last.pre;
        last.pre=newNode;
        size++;
        }
                  //新增一个元素

    //删除相同元素
   public  void delete(Object element){
        ListNode p=first.next;//first为null
        while(p!=last){
            if(p.data.equals(element)){
                 p.pre.next=p.next;
                 p.next.pre=p.pre;
                 p.next=null;
                 p.pre=null;
                 size--;
                break;
            }
             p=p.next;
        }
    }
    //根据索引删除元素
   public void delete(int index){
        if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;
        ListNode p=first.next;//从first的下一个元素开始

        while(p!=last){
          if(i==index){

          p.pre.next=p.next;
          p.next.pre=p.pre;
          p.next=null;
          p.pre=null;
            size--;
            break;//注意这里
          }
            p=p.next;
            i++;
        }

           、
    }

    //将指定索引位置的·元素替换成新元素
    public void update(int index,Object newElement){
        if(index<0||index>=size){
        return;
        }

        int i=0;
        ListNode p=first.next;

        while(p!=last){
            if(i==index){
            p.data=newElement;
            break;
            }
            p=p.next;
            i++;
        }

    }

    //当前列表中是否含有target元素
   public  boolean contains(Object target){
        ListNode p=first.next;
        while(p!=last){
            if(p.data.equals(target)){
              return true;
            }
            p=p.next;

        }
        return false;

    }

    //返回指定索引处元素
    public Object at(int index){
    if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(i==index){
            return p.data;
            break;
          }
            p=p.next;
            i++;
        }

        return null;
    }


    public int indexOf(Object element){

        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(p.data.equals(element)){
            return i;
            break;
          }
            p=p.next;
            i++;
        }

    return -1;
    }

        public String toString(){
            StringBuilder sb=new StringBuilder();
            ListNode p=first.next;
            while(p!=last){
            sb.append(p.data);
            if(p.next!=last)
            sb.append(",");
            p=p.next;
            }
            sb.append("]");
            return sb.toString();

        }


}

迭代器

public interface Iterator<E>{
    boolean hasNext();

    Object next();

}

public interface MyList extends Iterator{

    //新增一个元素
    void add(Object element);
    //删除相同元素
    void delete(Object element)
    //根据索引删除元素
    void delete(int index);

    //将指定索引位置的·元素替换成新元素
    void update(int index,Object newElement);

    //当前列表中是否含有target元素
    boolean contains(Object target);

    //返回指定索引处元素
    Object indexOf(int index);

      boolean hasNext();

    Object next();

}


public class DoubleLinkedList implements Mylist{
        private ListNode first=new ListNode(null);//头节点

        private ListNode last=new ListNode(null);//尾节点

        private size=0;

        public DoubleLinkList(){

        first.next=last;
        last.pre=first;

        }

        public void add(Object element){

        ListNode newNode=new ListNode(element);
        last.pre.next=newNode;
        newNode.next=last;
        newNode.pre=last.pre;
        last.pre=newNode;
        size++;
        }
                  //新增一个元素

    //删除相同元素
   public  void delete(Object element){
        ListNode p=first.next;//first为null
        while(p!=last){
            if(p.data.equals(element)){
                 p.pre.next=p.next;
                 p.next.pre=p.pre;
                 p.next=null;
                 p.pre=null;
                 size--;
                break;
            }
             p=p.next;
        }
    }
    //根据索引删除元素
   public void delete(int index){
        if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;
        ListNode p=first.next;//从first的下一个元素开始

        while(p!=last){
          if(i==index){

          p.pre.next=p.next;
          p.next.pre=p.pre;
          p.next=null;
          p.pre=null;
            size--;
            break;//注意这里
          }
            p=p.next;
            i++;
        }

           、
    }

    //将指定索引位置的·元素替换成新元素
    public void update(int index,Object newElement){
        if(index<0||index>=size){
        return;
        }

        int i=0;
        ListNode p=first.next;

        while(p!=last){
            if(i==index){
            p.data=newElement;
            break;
            }
            p=p.next;
            i++;
        }

    }

    //当前列表中是否含有target元素
   public  boolean contains(Object target){
        ListNode p=first.next;
        while(p!=last){
            if(p.data.equals(target)){
              return true;
            }
            p=p.next;

        }
        return false;

    }

    //返回指定索引处元素
    public Object at(int index){
    if(index<0||index>size){
        return;//啥也不干
        }
        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(i==index){
            return p.data;
            break;
          }
            p=p.next;
            i++;
        }

        return null;
    }


    public int indexOf(Object element){

        int i=0;//指针指向的节点的索引
        ListNode p=first.next;
        while(p!=last){
          if(p.data.equals(element)){
            return i;
            break;
          }
            p=p.next;
            i++;
        }

    return -1;
    }

        public String toString(){
            StringBuilder sb=new StringBuilder();
            ListNode p=first.next;
            while(p!=last){
            sb.append(p.data);
            if(p.next!=last)
            sb.append(",");
            p=p.next;
            }
            sb.append("]");
            return sb.toString();

        }

        private ListNode now=first;

     public boolean hasNext(){

     return now.next!=last;;
     }

    public Object next(){
    ListNode next=now.next;
    now=now.next;

    return next.data;
    }


}

public iter(){
    while(list.hashNext()){
       String next=list.next();
        System.out.println(next);
    }
}


//<T>泛型可以替换掉object

java List API

 

sort{set,List,Tree}

                     collection
         |               |         |
       List           Set        Queue
   |     |        |
Stack ArrayList LinkedList

List<String> list=new ArrayList<>();
list=new LinkedList<>();
list.add("asda");
list.remove("");

Collection.sort(list);

List<Student>list1=new ArrayList<>();
list1.add(new Student("zhangsan",10));
list1.add(new Student("isli",20));
Collection.sort(list1,(o1,o2)->{//camparetor排序器

    return o1.get()-o2.get();

});


for(int i=0;i<list1.size();i++){
    System.out.println(list1.get(i));
}//不能删东西，需要确保边界

for(Student stu:list1){
    System.out.println(stu);
}


Iterator<Student> iterator=new list1.Iterator();
//Iterator可以
while(iterator.hasNext()){
    System.out,println(iterator.next());
}

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

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

相关文章

基于Springboot的社区疫情返乡管控系统（有报告）。Javaee项目，springboot项目。

基于Springboot的社区疫情返乡管控系统（有报告）。Javaee项目，springboot项目。

演示视频&#xff1a; 基于Springboot的社区疫情返乡管控系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系…
阅读更多...
OpenHarmony 上传和下载（API 10）教程~

OpenHarmony 上传和下载（API 10）教程~

介绍 本示例使用ohos.request接口创建上传和下载任务&#xff0c;实现上传、下载功能&#xff0c;hfs作为服务器&#xff0c;实现了文件的上传和下载和任务的查询功能。 效果预览 使用说明 1.本示例功能需要先配置服务器环境后使用&#xff0c;具体配置见上传下载服务配置。…
阅读更多...
中颖51芯片学习7. printf重定向到串口与自定义日志输出函数

中颖51芯片学习7. printf重定向到串口与自定义日志输出函数

中颖51芯片学习7. printf重定向到串口与自定义日志输出函数 一、 printf 重定向1. 概念2. 实现方式3. C51 中printf数值格式化 二、日志函数1. 实现方案分析2. 代码&#xff08;1&#xff09;log_utils.h&#xff08;2&#xff09;main.c 3. 通过预定义宏实现日志分级输出&…
阅读更多...
汇编语言88888

汇编语言88888

汇编语言安装指南 第一步&#xff1a;在github上下载汇编语言的安装包 网址&#xff1a;GitHub - HaiPenglai/bilibili_assembly: B站-汇编语言-pdf、代码、环境等资料B站-汇编语言-pdf、代码、环境等资料. Contribute to HaiPenglai/bilibili_assembly development by creat…
阅读更多...
Flyweight 享元

Flyweight 享元

意图 运用共享技术有效地支持大量细粒度的对象。 结构 其中 Flyweight描述一个接口&#xff0c;通过这个接口Flyweight可以接受并作用于外部状态。ConcreteFlyweight实现Flyweight接口&#xff0c;并作为内部状态&#xff08;如果有&#xff09;增加存储空间。ConcreteFlywe…
阅读更多...
数字阅览室解决方案

数字阅览室解决方案

一、方案概述 “数字阅览室”概念一经提出&#xff0c;就得到了广泛的关注&#xff0c;纷纷组织力量进行探讨、研究和开发&#xff0c;进行各种模型的试验。随着数字地球概念、技术、应用领域的发展&#xff0c;数字阅览室已成为数字地球家庭的成员&#xff0c;为信息高速公路…
阅读更多...
vue3：树的默认勾选和全选、取消全选

vue3：树的默认勾选和全选、取消全选

实现的功能&#xff0c;上面有个选择框&#xff0c;当选中全部时&#xff0c;下方树被全选 代码&#xff1a; <template><div><el-select v-model"selectAll" style"margin-bottom: 10px;" change"handleSelectAllChange">&…
阅读更多...
运行transformers报错check_min_version(“4.40.0.dev0“)

运行transformers报错check_min_version(“4.40.0.dev0“)

在huggingface &#xff08;transformers项目地址&#xff09;下载transformers的项目 并 python /transformers/examples/pytorch/language-modeling/run_clm.py 时报错 报错如下&#xff1a; 安装的 transformers 版本不对&#xff0c;这里安装了 4.39.3&#xff0c;实际想…
阅读更多...
网站备案期间怎么关闭首页显示无法访问-文章及其它页面正常访问

网站备案期间怎么关闭首页显示无法访问-文章及其它页面正常访问

自从做了开发者之后才发现每个人博主的需求都是不同的&#xff0c;的的确确颠覆了我的观点&#xff0c;无论是页面布局还是SEO相关的设置&#xff0c;可能是因为站点属性不同所以需求不同&#xff0c;慢慢的就会在主题加入一些自定接口来满足不同人的需求&#xff0c;有人需要P…
阅读更多...
双链表的实现

双链表的实现

我们知道链表其实有很多种&#xff0c;什么带头&#xff0c;什么双向啊&#xff0c;我们今天来介绍双向带头循环链表&#xff0c;了解了这个其他种类的链表就很简单了。冲冲冲&#xff01;&#xff01;&#xff01; 链表的简单分类 链表有很多种&#xff0c;什么带头循环链表&…
阅读更多...
【c基础】文件操作

【c基础】文件操作

1.fopen和fclose函数 函数原型 FILE *fopen(const char *path, const char *mode); 参数解释&#xff1a; 返回值&#xff1a;fopen打开成功&#xff0c;则返回有效file的有效地址&#xff0c;失败返回NULL。path是文件路径&#xff0c;可以相对路径&#xff0c;可以绝对路径…
阅读更多...
“手撕“三大特性之一的＜继承＞（上）

“手撕“三大特性之一的＜继承＞（上）

目录 一、为什么需要继承 二、什么是继承 三、继承怎么写 四、成员的访问 1.父类与子类的成员变量不同名 2.父类与子类的成员变量同名 3.父类与子类的成员方法不同名 4.父类与子类的成员方法同名 五、super关键字 一、为什么需要继承 先让我们看一段Java代码&#…
阅读更多...
Unity地形关联出错的解决办法以及地形深度拷贝

Unity地形关联出错的解决办法以及地形深度拷贝

问题 最近发现unity地形系统的一个bug&#xff0c;导入的场景地形数据关联错乱了&#xff0c;关联到别的场景的地形数据了&#xff0c;meta替换了也没用&#xff0c;不清楚它具体是怎么关联的。 看下面的案例&#xff1a; 可以看到正常这个场景的地形数据应该关联的是Scene_E…
阅读更多...
力扣HOT100 - 142. 环形链表 II

力扣HOT100 - 142. 环形链表 II

解题思路&#xff1a; public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> set new HashSet<>();while (head ! null) {if (!set.add(head)) {return head;}head head.next;}return null;} }
阅读更多...
文心一言 VS 讯飞星火 VS chatgpt （241）-- 算法导论17.3 7题

文心一言 VS 讯飞星火 VS chatgpt （241）-- 算法导论17.3 7题

七、为动态整数多重集 S (允许包含重复值)设计一种数据结构&#xff0c;支持如下两个操作&#xff1a;① INSERT(S,x) 将 x 插入 S 中&#xff1b;② DELETE-LARGER-HALF(S) 将最大的 ⌈|S|/2⌉ 个元素从S中删除。解释如何实现这种数据结构&#xff0c;使得任意 m 个 INSERT 和…
阅读更多...
Linux的firewalld防火墙

Linux的firewalld防火墙

介绍firewalld&#xff1a; ①、firewalld&#xff08;Dynamic Firewall Manager of Linux systems&#xff0c;Linux系统的动态防火墙管理器&#xff09;服务是默认的防火墙配置管理工具&#xff0c;它拥有基于CLI&#xff08;命令行界面&#xff09;和基于GUI&#xff08;图…
阅读更多...
Web Tours系统使用说明书

Web Tours系统使用说明书

1.系统简介 产品名称&#xff1a;LoadRunner的Web Tours系统 产品功能&#xff1a;注册和登录用户信息、订票办理、退片办理、查询已定票信息、退出系统 系统默认用户&#xff1a;用户名jojo 密码&#xff1a;bean 2. 功能简介 2.1 注册用户信息 点击 sign up now&#xff…
阅读更多...
（自学用）正演理论

（自学用）正演理论

基于波动方程如何解决数值频散问题——快速正演方法 NAD方法&#xff1a; 怎样离散/逼近高阶偏导数&#xff08;如何采样&#xff09;&#xff1a; 传统方法是用某一点及其周围点的函数f的线性组合来逼近导数。只有函数值&#xff0c;要想提高精度&#xff0c;压制数值频散就必…
阅读更多...
（C语言）fscanf与fprintf函数详解

（C语言）fscanf与fprintf函数详解

目录 1 fprintf详解 1.1 向文件流中输入数据 1.2 向标准输入流写数据 2. fscanf函数详解 2.1 从文件中读取格式化数据 2.2 从标准输入流中读取格式化数据 1 fprintf详解 头文件&#xff1a;stdio.h 该函数和printf的参数特别像&#xff0c;只是多了一个参数stream&#…
阅读更多...
Unity类银河恶魔城学习记录13-5,6 p146 Delete save file,p147 Encryption of saved data源代码

Unity类银河恶魔城学习记录13-5,6 p146 Delete save file,p147 Encryption of saved data源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili FileDataHandler.cs using System; using System.IO; using UnityEngine; p…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站