数据结构与算法之线性表(超详细顺序表、链表)

简介: 通过前面数据结构与算法基础知识我么知道了数据结构的一些概念和重要性,那么我们今天总结下线性表相关的内容。当然,我用自己的理解解分享给大家。

前言



通过前面数据结构与算法基础知识我么知道了数据结构的一些概念和重要性,那么我们今天总结下线性表相关的内容。当然,我用自己的理解解分享给大家。


其实说实话,可能很多人依然分不清线性表顺序表,和链表之间的区别和联系!


  • 线性表:逻辑结构, 就是对外暴露数据之间的关系,不关心底层如何实现,数据结构的逻辑结构大分类就是线性结构和非线性结构而顺序表、链表都是一种线性表。
  • 顺序表、链表:物理结构,他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。


在Java中,大家都知道List接口类型,这就是逻辑结构,因为他就是封装了一个线性关系的一系列方法和数据。而具体的实现其实就是跟物理结构相关的内容。比如顺序表的内容存储使用数组的,然后一个get,set,add方法都要基于数组来完成,而链表是基于指针的。当我们考虑对象中的数据关系就要考虑指针的属性。指针的指向和value。


下面用一个图来浅析线性表的关系。可能有些不太确切,但是其中可以参考,并且后面也会根据这个图举例。


b1d8973c78fba1843dfe527c403c7477.png


线性表基本架构



对于一个线性表来说。不管它的具体实现如何,但是它们的方法函数名和实现效果应该一致(即使用方法相同、达成逻辑上效果相同,差别的是运行效率)。线性表的概念与Java的接口/抽象类有那么几分相似。最著名的就是List的Arraylist和LinkedList,List是一种逻辑上的结构,表示这种结构为线性表,而ArrayList,LinkedList更多的是一种物理结构(数组和链表)。


所以基于面向对象的编程思维,我们可以将线性表写成一个接口,而具体实现的顺序表和链表的类可以实现这个线性表的方法,提高程序的可读性,还有一点比较重要的,记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着知识的进步,我们应当采用泛型来实现更合理。至于接口的具体设计如下:


package LinerList;
public interface ListInterface<T> { 
  void Init(int initsize);//初始化表
  int length();
  boolean isEmpty();//是否为空
  int ElemIndex(T t);//找到编号
  T getElem(int index) throws Exception;//根据index获取数据
  void add(int index,T t) throws Exception;//根据index插入数据
  void delete(int index) throws Exception;
  void add(T t) throws Exception;//尾部插入
  void set(int index,T t) throws Exception;
  String toString();//转成String输出  
}


顺序表



顺序表是基于数组实现的,所以所有实现需要基于数组特性。对于顺序表的结构应该有一个存储数据的数组data和有效使用长度length.


还有需要注意的是初始化数组的大小,你可以固定大小,但是笔者为了可用性如果内存不够将扩大二倍。


下面着重讲解一些初学者容易混淆的概念和方法实现。这里把顺序表比作一队坐在板凳上的人。


插入操作


add(int index,T t)


其中index为插入的编号位置,t为插入的数据,插入的流程为:


(1)从后(最后一个有数据位)向前到index依次后移一位,腾出index位置的空间

(2)将待插入数据赋值到index位置上,完成插入操作


b3f7914111e15c38b8808f76063cef1b.png


可以看得出如果顺序表很长,在靠前的地方如果插入效率比较低(插入时间复杂度为O(n)),如果频繁的插入那么复杂度挺高的。


删除操作


同理,删除也是非常占用资源的。原理和插入类似,删除index位置的操作就是从index+1开始向后依次将数据赋值到前面位置上,具体可以看这张图:


a0b1e260bad2f44a436bb21f38e86d01.png


代码实现


这里我实现一个顺序表给大家作为参考学习:


package LinerList;
public class seqlist<T> implements ListInterface<T> {
  private Object[] date;//数组存放数据
  private int lenth;
  public seqlist() {//初始大小默认为10
    Init(10);
  }
  public void Init(int initsize) {//初始化
    this.date=new Object[initsize];
    lenth=0;    
  }
  public int length() {   
    return this.lenth;
  }
  public boolean isEmpty() {//是否为空
    if(this.lenth==0)
      return true;
    return false;
  }
  /*
   * * @param t 
   * 返回相等结果,为-1为false
   */
  public int ElemIndex(T t) {
    // TODO Auto-generated method stub
    for(int i=0;i<date.length;i++)
    {
      if(date[i].equals(t))
      {
        return i;
      }
    }
    return -1;
  }
  /*
   *获得第几个元素
   */
  public T getElem(int index) throws Exception {
    // TODO Auto-generated method stub
    if(index<0||index>lenth-1)
      throw new Exception("数值越界");
    return (T) date[index];
  }
  public void add(T t) throws Exception {//尾部插入
     add(lenth,t);
  }
  /*
   *根据编号插入
   */
  public void add(int index, T t) throws Exception {
    if(index<0||index>lenth)
      throw new Exception("数值越界");
    if (lenth==date.length)//扩容
    {
      Object newdate[]= new Object[lenth*2];
      for(int i=0;i<lenth;i++)
      {
        newdate[i]=date[i];
      }
      date=newdate;
    }
    for(int i=lenth-1;i>=index;i--)//后面元素后移动
    {
      date[i+1]=date[i];
    }
    date[index]=t;//插入元素
    lenth++;//顺序表长度+1
  }
  public void delete(int index) throws Exception {
    if(index<0||index>lenth-1)
      throw new Exception("数值越界");
    for(int i=index;i<lenth;i++)//index之后元素前移动
    {
      date[i]=date[i+1];
    }
    lenth--;//长度-1  
  }
  @Override
  public void set(int index, T t) throws Exception {
    if(index<0||index>lenth-1)
      throw new Exception("数值越界");
    date[index]=t;
  }
  public String  toString() {
    String vaString="";
    for(int i=0;i<lenth;i++)
    {
      vaString+=date[i].toString()+" ";
    }
    return vaString;
  }
}


链表



学习c/c++的时候链表应该是很多人感觉很绕的东西,这个很大原因可能因为指针,Java虽然不直接使用指针但是我们也要理解指针的原理和运用。链表不同于顺序表(数组)它的结构像一条链一样链接成一个线性结构,而链表中每一个节点都存在不同的地址中,链表你可以理解为它存储了指向节点(区域)的地址,能够通过这个指针找到对应节点。


对于物理存储结构,地址之间的联系是无法更改的,相邻就是相邻。但对于链式存储,下一位的地址是上一个主动记录的,可以进行更改。这就好比亲兄弟从出生就是同姓兄弟,而我们在成长途中最好的朋友可能会由于阶段性发生一些变化!


就如西天取经的唐僧、悟空、八戒、沙和尚。他们本无联系,但结拜为师徒兄弟,你问悟空他的师父它会立马想到唐僧,因为五指山下的约定。


ba08599ccf17e1f561413d24e84e31d7.png


基本结构



对于线性表,我们只需要一个data数组和length就能表示基本信息。而对于链表,我们需要一个node(head头节点),和length分别表示存储的节点数据和链表长度,这个节点有数据域和指针域。数据域就是存放真实的数据,而指针域就是存放下一个node的指针,其具体结构为:


class node<T>{
    T data;//节点的结果
    node next;//下一个连接的节点
    public node(){}
    public node(T data)
    {
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    } 
}


带头结点链表VS不带头结点链表


有很多人会不清楚带头结点和不带头结点链表的区别,甚至搞不懂什么是带头结点和不带头结点,我给大家阐述一下:


带头结点:head指针始终指向一个节点,这个节点不存储有效值仅仅起到一个标识作用(相当于班主任带学生)

不带头结点:head指针始终指向第一个有效节点,这个节点储存有效数值。

那么带头结点和不带头结点的链表有啥区别呢?


查找上:无大区别,带头结点需要多找一次。

插入上:非第0个位置插入区别不大,不带头结点的插入第0号位置之后需要重新改变head头的指向。


253db74ee10c00ae10883921f699a851.png


删除上:非第0个位置删除区别不大,不带头结点的删除第0号位置之后需要重新改变head头的指向。


头部删除(带头节点):带头节点的删除和普通删除一样。直接head.next=head.next.next,这样head.next就直接指向第二个元素了。第一个就被删除了


头部删除(不带头节点):不带头节点的第一个节点(head)就存储有效数据。不带头节点删除也很简单,直接将head指向链表中第二个node节点就行了。即:head=head.next


c7c9e64d2530e885973dc71d90b59223.png


总而言之:带头结点通过一个固定的头可以使链表中任意一个节点都同等的插入、删除。而不带头结点的链表在插入、删除第0号位置时候需要特殊处理,最后还要改变head指向。两者区别就是插入删除首位(尤其插入)当然我是建议你以后在使用链表时候尽量用带头结点的链表避免不必要的麻烦。


带头指针VS带尾指针


基本上是个链表都是要有头指针的,那么头尾指针是个啥呢?

头指针: 其实头指针就是链表中head节点,成为头指针。


**尾指针: **尾指针就是多一个tail节点的链表,尾指针的好处就是进行尾插入的时候可以直接插在尾指针的后面,然后再改变一下尾指针的顺序即可。



10ca4b69ad5ad0b777201d38b614c228.png


但是带尾指针的单链表如果删除尾的话效率不高,需要枚举整个链表找到tail前面的那个节点进行删除。


插入操作


add(int index,T t)


其中index为插入的编号位置,t为插入的数据,在带头结点的链表中插入在任何位置都是等效的。

加入插入一个节点node,根据index找到插入的前一个节点叫pre。那么操作流程为


1. `node.next=pre.next`,将插入节点后面先与链表对应部分联系起来。此时node.next和pre.next一致。
2. `pre.next=node` 将node节点插入到链表中。

233e0cc79e9a168bb116a0f13a877632.png


当然,很多时候链表需要插入在尾部,如果频繁的插入在尾部每次枚举到尾部的话效率可能比较低,可能会借助一个尾指针去实现尾部插入。


删除操作


按照index移除(主要掌握):delete(int index)


本方法为带头结点普通链表的通用方法(删除尾也一样),找到该index的前一个节点pre,pre.next=pre.next.next


54e5bc3c6b1a838f27415192cb8f51dd.png


代码实现


在这里我也实现一个单链表给大家作为参考使用:


package LinerList;
class node<T>{
    T data;//节点的结果
    node next;//下一个连接的节点
    public node(){}
    public node(T data)
    {
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    }
}
public class Linkedlist<T> implements ListInterface<T>{
  node head;
  private int length;
  public Linkedlist() {
    head=new node();
    length=0;
  }
  public void Init(int initsize) {
    head.next=null;
  }
  public int length() {
        return this.length;
  }
  public boolean isEmpty() {
    if(length==0)return true;
    else return false;
  }
  /*
   * 获取元素编号
   */
  public int ElemIndex(T t) {
    node team=head.next;
    int index=0;
    while(team.next!=null)
    {
      if(team.data.equals(t))
      {
        return index;
      }
      index++;
      team=team.next;
    }
    return -1;//如果找不到
  }
  @Override
  public T getElem(int index) throws Exception {
    node team=head.next;
    if(index<0||index>length-1)
    {
      throw new Exception("数值越界");
    }
    for(int i=0;i<index;i++)
    {
      team=team.next;
    }
    return (T) team.data;
  }
  public void add(T t) throws Exception {
    add(length,t);
  }
  //带头节点的插入,第一个和最后一个一样操作
  public void add(int index, T value) throws Exception {
    if(index<0||index>length)
    {
      throw new Exception("数值越界");
    }
    node<T> team=head;//team 找到当前位置node
    for(int i=0;i<index;i++)
    {
         team=team.next;
    }
    node<T>node =new node(value);//新建一个node
    node.next=team.next;//指向index前位置的下一个指针
    team.next=node;//自己变成index位置  
    length++;
  }
  @Override
  public void delete(int index) throws Exception {
    if(index<0||index>length-1)
    {
      throw new Exception("数值越界");
    }
    node<T> team=head;//team 找到当前位置node
    for(int i=0;i<index;i++)//标记team 前一个节点
    {
         team=team.next;
    }
    //team.next节点就是我们要删除的节点
    team.next=team.next.next;
    length--;
  }
  @Override
  public void set(int index, T t) throws Exception {
    // TODO Auto-generated method stub
    if(index<0||index>length-1)
    {
      throw new Exception("数值越界");
    }
    node<T> team=head;//team 找到当前位置node
    for(int i=0;i<index;i++)
    {
         team=team.next;
    }
    team.data=t;//将数值赋值,其他不变
  }
  public String toString() {
    String va="";
    node team=head.next;
    while(team!=null)
    {
      va+=team.data+" ";
      team=team.next;
    }
    return va;
  }
}


总结



你可能会问这个是否正确啊,那我来测试一下:


ac480950d169e9f87f726445a7ebcca6.png


这里的只是简单实现,实现基本方法。链表也只是单链表。完善程度还可以优化。能力有限, 如果有错误或者优化的地方还请大佬指正。


单链表查询速度较慢,因为他需要从头遍历,如果在尾部插入,可以考虑设计带尾指针的链表。而顺序表查询速度虽然快但是插入很费时费力,实际应用根据需求选择!


Java中的Arraylist和LinkedList就是两种方式的代表,不过LinkedList使用双向链表优化,并且JDK也做了大量优化。所以大家不用造轮子,可以直接用,但是手写顺序表、单链表还是很有学习价值的。


单链表搞懂了,双链表也就不远了(下集预告)!


原创不易,bigsai请csdn的朋友们帮两件事帮忙一下:


点赞、在看、分享支持一下, 您的肯定是我创作的源源动力。


微信搜索「bigsai」,2021我需要你的支持!


咱们下次再见!


目录
相关文章
|
5天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
26 5
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
55 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
29天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
42 0
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
2天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。
|
14天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。