数据结构与算法—线性表详解

前言通过前面数据结构与算法前导我么知道了数据结构的一些概念和重要性,那么我们今天总结下线性表相关的内容。当然,我用自己的理解解分享给大家。其实说实话,可能很多人依然分不清线性表,顺序表,和链表之间的区别和联系!线性表:逻辑结构,就是对外暴露数据之间的关系,不关心底层如何实现。顺序表、链表:物理结构,他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构...

数据结构与算法—线性表详解

前言


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

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

    • 线性表逻辑结构, 就是对外暴露数据之间的关系,不关心底层如何实现。
    • 顺序表、链表物理结构,他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
  • 对于java来说,大家都知道List接口类型,这就是逻辑结构,因为他就是封装了一个线性关系的一系列方法和数据。而具体的实现其实就是跟物理结构相关的内容。比如顺序表的内容存储使用数组的,然后一个get,set,add方法都要基于数组来完成,而链表是基于指针的。当我们考虑对象中的数据关系就要考虑指针的属性。指针的指向和value。

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

在这里插入图片描述

线性表基本架构


  • 对于一个线性表来说。不管它的具体实现方法如何,我们应该有的函数名称实现效果应该一致。你也可以感觉的到在一些结构的设计。比如List的ArraylistLinkedList。Map的HashMap和currentHashMap他们的接口api都是相同的,但是底层设计实现肯定是有区别的。
  • 所以,基于面向对象的编程思维,我们可以将线性表写成一个接口,而具体实现的顺序表和链表可以继承这个接口的方法,提高程序的可读性。
  • 还有一点比较重要的,记得初学数据结构与算法时候实现的线性表都是固定类型(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为插入的数据在这里插入图片描述在这里插入图片描述在这里插入图片描述
  • 根据图片你就很好理解插入操作。当插入一个index时候,他的后面所有元素都要后移一位。你可以看的出插入时候整个操作的臃肿性。所以这也是顺序表性能表现最差的地方,频繁的插入,删除。

删除

  • 同理,删除也是非常占用资源的。原理和插入类似,不过人走了,空一个小板凳后面的人需要往前挪在这里插入图片描述

其他操作

  • 其他操作就很简单了。比如如果按照编号获取数据getElem(int index),你可以直接根据数据坐标返回。a[index],而其他操作,可以通过遍历直接操作数组即可。

链表


  • 我想,表应该是很多人感觉很绕的东西,这个很大原因可能因为指针。很多人说java没指针,其实java他也有隐形指针。只不过不能直接用罢了。
  • 指针建立的数据关系往往比数组这些要抽象的多。对于指针域,你把他当成一个对象就好了,不过这个对象指向的是另一个同等级对象。对于这个关系,你可以比作每个person类。每个person类都有老公(老婆),而这个老公老婆也是一个实际对象,可以理解这更像一种逻辑约定关系,而不是硬生生的关系吧。在这里插入图片描述
  • 指针你可以考虑成脑子记忆。上面的顺序表我们说它有序因为每个小板凳(数组)有编号,我们可以根据这个来确定位置。而对于链表来说,你可以看作成一个站在操场上的一队人。而他的操作也略有不同,下面针对一些比较特殊和重要的进行归纳。

基本结构

对于线性表,我们只需要一个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; } }

当然,这个节点有数据域指针域。数据域就是存放真实的数据,而指针域就是存放下一个node的指针。所以相比顺序表,如果用满数组情况下,链表占用更多的资源,因为它要存放指针占用资源。

在这里插入图片描述

插入

add(int index,T t)其中index为插入的编号位置,t为插入的数据 加入插入一个节点node,根据index找到插入的前一个节点叫pre。那么操作流程为

  1. node.next=pre.next如下1的操作,将插入节点后面联系起来。此时node.next和pre.next一致。
  2. pre.next=node因为我们要插入node,而node链可以替代pre自身的next。那么直接将pre指向node。那么就相当于原始链表插入了一个node。

在这里插入图片描述在这里插入图片描述

带头节点与不带头节点

在这里插入图片描述很多人搞不清什么是带头节点

源文地址:https://www.guoxiongfei.cn/cntech/24334.html