数据结构于算法—线性表 agile Posted on Jul 13 2023 数据结构与算法 ## 前言 通过前面数据结构与算法基础知识我么知道了数据结构的一些概念和重要性，那么我们今天总结下线性表相关的内容。当然，我用自己的理解解分享给大家。 其实说实话，可能很多人依然分不清**线性表**，**顺序表**，和**链表**之间的区别和联系！ - 线性表：**逻辑结构**， 就是对外暴露数据之间的关系，不关心底层如何实现，数据结构的逻辑结构大分类就是线性结构和非线性结构而顺序表、链表都是一种线性表。 - 顺序表、链表：**物理结构**，他是实现一个结构实际物理地址上的结构。比如顺序表就是用**数组**实现。而链表用**指针**完成主要工作。不同的结构在不同的场景有不同的区别。 在Java中，大家都知道`List`接口类型，这就是逻辑结构，因为他就是封装了一个线性关系的一系列方法和数据。而具体的实现其实就是跟物理结构相关的内容。比如顺序表的内容存储使用数组的，然后一个get，set，add方法都要**基于数组**来完成,而链表是**基于指针**的。当我们考虑对象中的数据关系就要考虑指针的属性。指针的指向和value。 下面用一个图来浅析线性表的关系。可能有些不太确切，但是其中可以参考，并且后面也会根据这个图举例。  ## 线性表基本架构 对于一个线性表来说。不管它的具体实现如何，但是它们的方法函数名和实现效果应该一致(即使用方法相同、达成逻辑上效果相同，差别的是运行效率)。线性表的概念与Java的接口/抽象类有那么几分相似。最著名的就是List的Arraylist和LinkedList，List是一种逻辑上的结构，表示这种结构为线性表，而ArrayList，LinkedList更多的是一种物理结构(数组和链表)。 所以基于面向对象的编程思维，我们可以将线性表写成一个接口，而具体实现的顺序表和链表的类可以实现这个线性表的方法，提高程序的可读性，还有一点比较重要的，记得初学数据结构与算法时候实现的线性表都是`固定类型`(int),随着知识的进步，我们应当采用`泛型`来实现更合理。至于接口的具体设计如下： ```java 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位置上，完成插入操作  可以看得出如果顺序表很长，在靠前的地方如果插入效率比较低(插入时间复杂度为O(n))，如果频繁的插入那么复杂度挺高的。 ### 删除操作 同理，删除也是非常占用资源的。原理和插入类似，删除index位置的操作就是从index+1开始向后依次将数据赋值到前面位置上，具体可以看这张图：  ### 代码实现 这里我实现一个顺序表给大家作为参考学习： ```java 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虽然不直接使用指针但是我们也要理解指针的原理和运用。链表不同于顺序表(数组)它的结构像一条链一样链接成一个线性结构，而链表中每一个节点都存在不同的地址中，链表你可以理解为它存储了指向节点(区域)的地址，能够通过这个指针找到对应节点。 对于物理存储结构，地址之间的联系是无法更改的，相邻就是相邻。但对于链式存储，下一位的地址是上一个**主动记录的**，可以进行更改。这就好比亲兄弟从出生就是同姓兄弟，而我们在成长途中最好的朋友可能会由于阶段性发生一些变化！ 就如西天取经的唐僧、悟空、八戒、沙和尚。他们本无联系，但结拜为师徒兄弟，你问悟空他的师父它会立马想到唐僧，因为五指山下的约定。  ### 基本结构 对于线性表，我们只需要一个data数组和length就能表示基本信息。而对于链表，我们需要一个node(head头节点)，和length分别表示存储的节点数据和链表长度，这个节点有**数据域**和**指针域**。数据域就是存放真实的数据，而指针域就是存放下一个node的指针，其具体结构为： ```java 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头的指向。  **删除上**：非第0个位置删除区别不大，不带头结点的删除第0号位置之后需要重新改变head头的指向。 头部删除(带头节点)：带头节点的删除和普通删除一样。直接`head.next=head.next.next`，这样head.next就直接指向第二个元素了。第一个就被删除了 头部删除(不带头节点)：不带头节点的第一个节点(head)就存储有效数据。不带头节点删除也很简单，直接将head指向链表中第二个node节点就行了。即：`head=head.next`  总而言之：带头结点通过一个固定的头可以使链表中任意一个节点都同等的插入、删除。而不带头结点的链表在插入、删除第0号位置时候需要特殊处理，最后还要改变head指向。两者**区别就是插入删除首位**(尤其插入)当然我是建议你以后在使用链表时候**尽量用带头结点的链表**避免不必要的麻烦。 ### 带头指针VS带尾指针 基本上是个链表都是要有头指针的，那么头尾指针是个啥呢？ **头指针：** 其实头指针就是链表中head节点，成为头指针。 **尾指针： **尾指针就是多一个tail节点的链表，尾指针的好处就是进行尾插入的时候可以直接插在尾指针的后面，然后再改变一下尾指针的顺序即可。  但是带尾指针的单链表如果删除尾的话效率不高，需要枚举整个链表找到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节点插入到链表中。  当然，很多时候链表需要插入在尾部，如果频繁的插入在尾部每次枚举到尾部的话效率可能比较低，可能会借助一个尾指针去实现尾部插入。 ### 删除操作 **按照index移除(主要掌握)**：delete(int index) 本方法为带头结点普通链表的通用方法(删除尾也一样)，找到该index的前一个节点pre，`pre.next=pre.next.next`  ### 代码实现 在这里我也实现一个单链表给大家作为参考使用： ```java 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; } } ``` ## 总结 你可能会问这个是否正确啊，那我来测试一下：  这里的只是简单实现，实现基本方法。链表也只是单链表。完善程度还可以优化。能力有限， **如果有错误或者优化的地方还请大佬指正**。 单链表查询速度较慢，因为他需要从头遍历，如果在尾部插入，可以考虑设计带尾指针的链表。而顺序表查询速度虽然快但是插入很费时费力，**实际应用根据需求选择**！ Java中的Arraylist和LinkedList就是两种方式的代表，不过LinkedList使用双向链表优化，并且JDK也做了大量优化。所以大家不用造轮子，可以直接用，但是手写顺序表、单链表还是很有学习价值的。 【排序算法】基数排序 「干货总结」程序员必知必会的十大排序算法