线性表
- 1.什么是线性表?
- 2.线性表的定义:
- 3.线性表图解:
- 4.线性表的长度:
- 5.线性表的顺序储存结构：
- 6.顺序存储结构的全部用法:(ArrayList)
- 7.单链表的全部用法
- 8.循环链表(双指针快慢)
- 9.双向链表:
- 9.双向链表的全部用法
1.什么是线性表?
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
2.线性表的定义:
线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。(直接前驱和直接后继)
3.线性表图解:
有限:数据元素是有限个的
序列:小朋友排队是有顺序的.
4.线性表的长度:
线性表的元素个数n就是线性表的长度: 当n=0时,那么就是空表.i称为序列！
线性表的长度不等于数组的长度，通常数组的长度大于等于线性表的长度:
5.线性表的顺序储存结构：
5.1定义:
顺序储存结构:是指的时一段地址连续的储存单元依次存储线性表的数据元素.
5.2顺序储存结构的插入元素:
注意事项:
阐述:
表长+1并不是说数组的长度+1，而是指的时数据元素+1
方法:
public static int[] InsertNumber(int []nums,int idex,int number){ if(nums.length==5){ //假设数组的最大为5个，假如说表的长度等于5，返回null return null; } if(idex==nums.length-1){ //假如说插入元素的下表在线性表中的最后一个，那么就执行下面这样的循环 nums[idex]=number; //插入 return nums; } if(idex<nums.length-1){ //假如说插入元素的下表不是线性表的最后一个，那么就执行一下程序 for(int k=nums.length-1;k>idex;k--){ nums[k]=nums[k-1]; //插入元素后的所有元素后退 } nums[idex ]=number; //插入 return nums; } return null; }}主函数:
import java.sql.SQLOutput;import java.util.*;import java.awt.*;public class hello { public static void main(String []avgs) { int []nums=new int[4]; nums[0]=1; //线性表 nums[1]=2; //线性表 nums[2]=3; //线性表 int []arr=InsertNumber(nums,0 ,5); //数组 插入坐标 插入元素 for(int i=0;i<arr.length;i++){ //打印输出 System.out.println(arr[i]); } }
5.3线性表的顺序结构的删除元素:
删除算法的思路:
(1)如果删除位置不合理，抛出异常;(2)取出删除元素;
(3)从删除元素位置开始遍历至到最后一个元素位置，分别将它们都向前移动一个位置;
(4)表长减1。
方法:
public static int[] InsertNumber(int []nums,int idex){ if(nums.length==0){ //假设线性表为0 return null; } if(idex>nums.length){ //假如说删除的数据大于线性表长度 return null; } if(idex<nums.length){ for(int k=idex;k<nums.length-1;k++) //中间条件目的是为了防止线性表超限 { nums[k]=nums[k+1]; } return nums; } return null; }}主函数:
import java.sql.SQLOutput;import java.util.*;import java.awt.*;public class hello { public static void main(String []avgs) { int []nums=new int[4]; nums[0]=1; //线性表 nums[1]=2; //线性表 nums[2]=3; //线性表 int []arr=InsertNumber(nums,1 ); //数组 插入坐标 插入元素 for(int i=0;i<arr.length;i++){ //打印输出 System.out.println(arr[i]); } }
*切记哈，删除和插入的是线性表=====并不是数组*
5.4线性表顺序储存结构的优缺点
6.顺序存储结构的全部用法:(ArrayList)
判断是否清空
public boolean isEmpty(){ return N==0; }线性表的长度`
public int getLength(){ return N; }索引所在的值
public T getNumber(int i){ return elem[i]; }在线性表中插入元素
public void Insert(T t){ elem[N++]=t; }在指定索引i处增加t
public void add(int idex,T t){ for(int i=N;i>idex;i--){ elem[i]=elem[i-1]; } N++; elem[idex]=t; }}删除指定索引i的值，并返回删除索引的值
public T remove(int i){ T count=elem[i]; for(int idex=i;idex<N-1;idex++){ elem[idex]=elem[idex+1]; } //元素个数-1 N--; return count; }查找元素T，在链表中出现的第一个位置
public int Find(T t){ for(int i=0;i<N;i++){ if(elem[i].equals(t)){ return i; } } return -1; }数组的扩容
public void resize(int size){ T [] newelem=(T[]) new Object[size]; for(int i=0;i<N;i++){ newelem[i]=elem[i]; //老数组赋值给新数组 } elem=newelem; //新数组赋值给老数组 }`类方法展示:
public class SquenceList <T>{ private T[]elem; //定义一个数据类型为T的数组 //代表线性表中存放的元素个数 private int N; public SquenceList(int capacity){ //构造方法 //初始化数组 this.elem=(T[])new Object[capacity]; this.N=0; } //实现对数组的扩容处理 public void resize(int size){ T [] newelem=(T[]) new Object[size]; for(int i=0;i<N;i++){ newelem[i]=elem[i]; //老数组赋值给新数组 } elem=newelem; //新数组赋值给老数组 } //清空线性表 public void clear(){ N=0; } //判断线性表是否为空 public boolean isEmpty(){ return N==0; } //求线性表的长度 public int getLength(){ return N; } //获取索引所在的值: public T getNumber(int i){ return elem[i]; } //向线性表中插入元素 public void Insert(T t){ elem[N++]=t; } //在指定索引i处增加t public void add(int idex,T t){ for(int i=N;i>idex;i--){ elem[i]=elem[i-1]; } N++; elem[idex]=t; } //删除指定索引i的值，并返回删除索引的值 public T remove(int i){ T count=elem[i]; for(int idex=i;idex<N-1;idex++){ elem[idex]=elem[idex+1]; } //元素个数-1 N--; return count; } //查找元素T，在链表中出现的第一个位置 public int Find(T t){ for(int i=0;i<N;i++){ if(elem[i].equals(t)){ return i; } } return -1; }}主方法:
public class SquenceListTest { public static void main(String []avgs){ //创建顺序表对象 SquenceList<String> s1=new SquenceList<>(10); //测试插入 s1.Insert("李明"); s1.Insert("傻子"); s1.Insert("王二" ); s1.Insert("张三"); //测试获取 String result=s1.getNumber(1); System.out.println(result); //测试删除 String remove1=s1.remove(1); System.out.println("删除的是:"+remove1); //测试清空 s1.clear(); System.out.println("清空后的元素个数为:"+s1.getLength()); }}
7.单链表的全部用法
创建链表结点
private class Node1 { //调用结点类 T item; //数据域 Node1 next; //指针域 public Node1(T item, Node1 next) { this.item = item; this.next = next; } }//调用节点类对链表进行初始化
public LinkedList() { //初始化链表 this.head=new Node1(null,null); this.size=0; }//获取指定位置的元素:
public T get(int idex){ Node1 target=this.head.next; //获取0结点的指针，且目前表示的是第一个结点 for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target.item;}//获取指定位置的结点
public Node1 getNode(int idex){ if(idex==-1){ //目的是在指定位置0的时候的作用 return head; } Node1 target=this.head.next; for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target;}//在尾部添加数据
public void add(T t){Node1 node=new Node1(t,null);if(this.size==0){ //假如说是0结点，那么就添加到零结点 this.head.next=node;}else { //找到最后一个结点 this.getNode(this.size-1).next=node;}//链表长度++ this.size++;}//在指定位置插入数据
public void add(int idex,T t){ //获取需要插入点的节点 Node1 node2 =new Node1(t,null); //获取被插入点的结点 Node1 current=this.getNode(idex); //获取被插入点的前一个为止 Node1 BeforeCurrent=this.getNode(idex-1); //把前一个结点的指针指向插入点 BeforeCurrent.next= node2; //把插入点的指针指向被插入点 node2.next=current; this.size++;}//删除指定位置的结点
public T remove(int idex){ //获取删除点的前一个结点 Node1 before =this.getNode(idex-1); //获取删除点的结点 Node1 current=this.getNode(idex); before.next=current.next; this.size--; return current.item; }类文件:
import org.jetbrains.annotations.NotNull;public class LinkedList<T> { Node1 head; //设置头节点 int size; //链表长度 public LinkedList() { //初始化链表 this.head=new Node1(null,null); this.size=0; } public void reverse2(){ reverse1(this.head.next); } //使用快慢指针寻找中间元素 public T QuickSlowP(){ //设置慢指针 Node1 slow=this.head.next; //设置快指针 Node1 quick=this.head.next; //设置慢指针计数器: int length=0; //设置快指针计数器 int length1=0; while(quick!=null){ //慢指针 slow=slow.next; //快指针 quick=quick.next; quick=quick.next; length++; length1++; } int mid=length1/2; quick=this.head.next; //这边的node要进行重新初始化 for(int i=0;i<mid;i++){ quick=quick.next.next; } return quick.item; } //利用慢指针进行寻找中间元素 public T Slowp(){ //获取第一个结点的指针 Node1 node=this.head.next; //定义一个链表的长度的计数器: int length=0; while(node!=null){ node=node.next; length++; } //获取中间元素的长度: int mid=length/2; node=this.head.next; //这边的node要进行重新初始化 for(int i=0;i<mid;i++){ node=node.next; } return node.item; } //通过递归函数完成链表的反转 public Node1 reverse1(@NotNull Node1 curr){ if(curr.next!=null){ //通过反转下一个结点获取，获取prev Node1 prev=reverse1(curr.next); //将之前的next结点设置成当前的结点 prev.next=curr; //返回curr的结点 return curr; }else{ //当前结点没有下一个结点 // 将头部的next结点指向当前结点 this.head.next=curr; return curr.next; } } //链表的反转: public void reverseList(){ //设置反转头 Node1 reverse = new Node1(null, null); //获取正序第一个结点 Node1 first=this.head.next; while(first!=null) { //把正序的头节点连接到first的下一个结点 this.head.next = first.next; //将反转的next赋值给first的next first.next = reverse.next; //将头节点指向first reverse.next = first; // 从正序链表中获取第一个原始元素 first = this.head.next; } //将原始头的next指向反转头结点的next this.head.next=reverse.next; } //获取当前链表的长度: public int size(){ return this.size; } //获取指定位置的元素: public T get(int idex){ Node1 target=this.head.next; //获取0结点的指针，且目前表示的是第一个结点 for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target.item; } //获取指定位置的结点 public Node1 getNode(int idex){ if(idex==-1){ //目的是在指定位置0的时候的作用 return head; } Node1 target=this.head.next; for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target; } //在尾部添加数据 public void add(T t){ Node1 node=new Node1(t,null); if(this.size==0){ //假如说是0结点，那么就添加到零结点 this.head.next=node; }else { //找到最后一个结点 this.getNode(this.size-1).next=node; } //链表长度++ this.size++; } //在指定位置插入数据 public void add(int idex,T t){ //获取需要插入点的节点 Node1 node2 =new Node1(t,null); //获取被插入点的结点 Node1 current=this.getNode(idex); //获取被插入点的前一个为止 Node1 BeforeCurrent=this.getNode(idex-1); //把前一个结点的指针指向插入点 BeforeCurrent.next= node2; //把插入点的指针指向被插入点 node2.next=current; this.size++; } //删除指定位置的结点 public T remove(int idex){ //获取删除点的前一个结点 Node1 before =this.getNode(idex-1); //获取删除点的结点 Node1 current=this.getNode(idex); before.next=current.next; this.size--; return current.item; } private class Node1 { //调用结点类 T item; //数据域 Node1 next; //指针域 public Node1(T item, Node1 next) { this.item = item; this.next = next; } }//调用节点类}主文件:
import java.sql.SQLOutput;import java.util.*;import java.awt.*;public class hello { public static void main(String []avgs) { LinkedList<String> s=new LinkedList<>(); s.add("aa"); s.add("bb"); s.add("cc"); s.remove(2); for(int i=0;i<s.size();i++) { System.out.println(s.get(i)); } }}7.1练习:
类方法:
public class test{ private class Node{ Node next; //指针 int item; //数据 public Node(int item,Node next){ this.next=next; this.item=item; } }//定义节点 Node head;//定义头节点 int size; //定义长度 public test(){ int size=0; //对长度进行初始化 } public int getSize(){ return size; } public Node getNode(int idex){ Node target=this.head.next; for(int i=0;i<idex;i++){ target=target.next; } return target; }//获得结点 public int get(int idex){ return getNode(idex).item; }//获得值 public void add(int t){ Node node=new Node(t,null); if(this.size==0){ this.head.next=node; }else{ getNode(this.size-1).next=node; } this.size++; } }主方法:
import java.sql.SQLOutput;import java.util.*;import java.awt.*;import java.lang.Math;public class hello { public static void main(String []avgs) { LinkedList s=new LinkedList<>(); Scanner sc=new Scanner(System.in); System.out.println("请输入您的数据"); for(int i=0;i<100;i++){ int m=sc.nextInt(); s.add(m); if(s.get(i).equals(-1)){ System.out.println("链表创建完毕！"); break; } } System.out.println("链表的数据为:"); for (int i=0;i<s.size();i++){ System.out.print(s.get(i)+" "); } }}
8.循环链表(双指针快慢)
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
8.1判断是否是循环链表
利用快慢指针判断是否这个链表是否为环形
基本思路:
因为快指针比慢指针走的快，慢指针比快指针走的慢。会有多次相遇的机会的
方法:
public boolean QuickSlowP(){ //设置慢指针 Node1 slow=this.head.next; //设置快指针 Node1 quick=this.head.next; while(quick!=null&&quick.next!=null){ //慢指针 slow=slow.next; //快指针 quick=quick.next; quick=quick.next; if(quick!=null&&quick.equals(slow)){ return true; } } return false; }//创建环形链表:
只需要把你想要的结点的指针指向你要循环的地方，就可以构成一个循环链表.
public void Recle(int start,int end){ Node1 node=getNode(start); Node1 node1=getNode(end); node1.next=node; }全部代码:
主方法:import java.sql.SQLOutput;import java.util.*;import java.awt.*;import java.lang.Math;public class hello { public static void main(String []avgs) { LinkedList<String> s=new LinkedList<>(); //构造一个单链表 s.add("aa"); s.add("cc"); s.add("ee"); s.add("zz"); System.out.println(s.QuickSlowP()); //构造一个环形链表 s.Recle(2,s.size()-1); System.out.println(s.QuickSlowP()); }}类方法import org.jetbrains.annotations.NotNull;public class LinkedList<T> { Node1 head; //设置头节点 int size; //链表长度 public LinkedList() { //初始化链表 this.head=new Node1(null,null); this.size=0; } public void Recle(int start,int end){ Node1 node=getNode(start); Node1 node1=getNode(end); node1.next=node; } //使用快慢指针寻找中间元素 public boolean QuickSlowP(){ //设置慢指针 Node1 slow=this.head.next; //设置快指针 Node1 quick=this.head.next; while(quick!=null&&quick.next!=null){ //慢指针 slow=slow.next; //快指针 quick=quick.next; quick=quick.next; if(quick!=null&&quick.equals(slow)){ return true; } } return false; } //获取当前链表的长度: public int size(){ return this.size; } //获取指定位置的元素: public T get(int idex){ Node1 target=this.head.next; //获取0结点的指针，且目前表示的是第一个结点 for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target.item; } //获取指定位置的结点 public Node1 getNode(int idex){ if(idex==-1){ //目的是在指定位置0的时候的作用 return head; } Node1 target=this.head.next; for(int i=0;i<idex;i++ ){ //移动指针 target=target.next; } return target; } //在尾部添加数据 public void add(T t){ Node1 node=new Node1(t,null); if(this.size==0){ //假如说是0结点，那么就添加到零结点 this.head.next=node; }else { //找到最后一个结点 this.getNode(this.size-1).next=node; } //链表长度++ this.size++; } //在指定位置插入数据 private class Node1 { //调用结点类 T item; //数据域 Node1 next; //指针域 public Node1(T item, Node1 next) { this.item = item; this.next = next; } }//调用节点类}
8.2求循环链表的入口元素
基本思路:
首先我们要判断这个链表是否是一个循环链表，如果是循环链表的话那么我们就继续执行操作，不是循环链表的话返回一个NULL。判断是否是入口的关键就在于慢指针slow，和一个新的指针（从第一个元素开始）往后遍历，如果新的指针和指针slow相交的位置，就是元素的所在位置.
public T QuickSlowP(){ //设置慢指针 Node1 slow=this.head.next; //设置快指针 int length=-1; int a=0; Node1 quick=this.head.next; while(quick!=null&&quick.next!=null){ //慢指针 slow=slow.next; //快指针 quick=quick.next; quick=quick.next; if(quick!=null&&quick.equals(slow)){ //假如环形 Node1 entry=this.head.next; //定义一个新的指针 while(!entry.equals(slow)){ entry=entry.next; slow=slow.next; } return entry.item; } } return null; }
8.3指定点循环链表的建立
public void Recle(int start,int end){ Node1 node=getNode(start); //开始点 Node1 node1=getNode(end);//结束点 node1.next=node; //首尾相连接 }8.4不指定点循环链表建立
public void SolveYsf (int m,int n){ //m是元素的个数，n是间隔几个 //建立一个链表 for(int i=1;i<=m;i++){ //添加链表的元素 add((T)(i+"")); } //进行加环处理 Node1 node=getNode(0); Node1 node1=getNode(this.size-1); node1.next=this.head.next;8.5约瑟夫问题
进行自杀操作，一共m个人，没间隔n个，那么就第n个人进行自杀操作。
public void SolveYsf (int m,int n){ //建立一个链表 for(int i=1;i<=m;i++){ //添加链表的元素 add((T)(i+"")); } //进行加环处理 Node1 node=getNode(0); Node1 node1=getNode(this.size-1); node1.next=this.head.next; //开始处理约瑟夫问题 Node1 target=this.head.next; int cn=1; while(target!=target.next){ //获取前一个元素 Node1 prev=target; //获取中间元素的前一个位置 //游标进行后移 target=target.next; //获取中间元素 //计算 cn++; if(cn==n){ //假如说cn=指定的n，那么就自杀 System.out.println("需要移除的元素是:"+target.item); prev.next=target.next; //把中间元素的前一个元素指向中间元素后一个元素 target=target.next; //把中间元素指向中间元素的后一个元素. cn=1; } } System.out.println("保留的元素是:"+target.item); }
9.双向链表:
9.1双向链表结点的定义：
private class Node1 { //设置结点 T item; //数据域 Node1 next; //指针域Node1 prev; Node1 prev; public Node1(Node1 prev,T item, Node1 next) { this.item = item; this.next = next; this.prev=prev; } }//调用节点类9.2双向链表添加末尾元素:
public void add(T t){ //先把插入点的prev指针指向前一个last Node1 prev=last; //获取插入的元素 Node1 node1=new Node1(prev,t,null); //然后把插入点前的next指针指向插入点的结点 if(prev==null){ //假如说插入点的前一个点是null first=node1; } else { prev.next = node1; } //将last指向新插入的元素 last=node1; //进行++操作 this.size++; }9.3获取双向链表的结点:
public Node1 getNode(int idex){ int mid=size/2; //获取中间值 if(idex<mid){ //如果小于，那么就从第一个节点开始遍历 Node1 x=first; for(int i=0;i<idex;i++){ x=x.next; } return x; }else{ //否则，那么就从最后i一个结点遍历 Node1 x=last; for(int i=size-1;i>idex;i--){ //这里可不能少 x=x.prev; } return x; } }9.4向指定位置添加元素
public void add(int idex,T t){ if(idex==size){//假如说是最后一个位置 add(t); }else{ //获取需要插入元素的结点 Node1 node1=new Node1(null,t,null); //获取被插入点的结点 Node1 current=getNode(idex); if(current==null){ first=node1; }else { //获取被插入点前的结点 Node1 befor = current.prev; //插入点prev指向前结点 node1.prev=befor; //插入点next指向后一个结点 node1.next=current; //后一个结点prev指向插入点 current.prev=node1; //假如说是第一个位置 if(befor==null){ first=node1; } else { befor.next = node1; } } this.size++; } }9.5删除元素
public void remove(int idex) { //设置删除点 Node1 current = getNode(idex); //删除点前面 Node1 before = current.prev; //删除点后面 Node1 after = current.next; if(before==null){ //假如说删除头部 first=after; }else{ before.next = after;} if (after == null) { //假如说删除末尾 last = before; } else { after.prev = before; } this.size--;}9.双向链表的全部用法
类方法:
import org.jetbrains.annotations.NotNull;public class LinkedList<T> { Node1 first; //指向第一个结点 Node1 last; //指向最后一个结点 int size; //链表长度 public LinkedList() { //初始化链表 this.size = 0; } //获取指定位置的结点 public Node1 getNode(int idex) { int mid = size / 2; //获取中间值 if (idex < mid) { //如果小于，那么就从第一个节点开始遍历 Node1 x = first; for (int i = 0; i < idex; i++) { x = x.next; } return x; } else { //否则，那么就从最后i一个结点遍历 Node1 x = last; for (int i = size - 1; i > idex; i--) { //这里可不能少 x = x.prev; } return x; } } //在指定位置添加元素 public void add(int idex,T t){ if(idex==size){//假如说是最后一个位置 add(t); }else{ //获取需要插入元素的结点 Node1 node1=new Node1(null,t,null); //获取被插入点的结点 Node1 current=getNode(idex); if(current==null){ first=node1; }else { //获取被插入点前的结点 Node1 befor = current.prev; //插入点prev指向前结点 node1.prev=befor; //插入点next指向后一个结点 node1.next=current; //后一个结点prev指向插入点 current.prev=node1; //假如说是第一个位置 if(befor==null){ first=node1; } else { befor.next = node1; } } this.size++; } } //获取指定位置的元素 public T get(int idex) { return getNode(idex).item; } //在末尾元素进行添加 public void add(T t) { //先把插入点的prev指针指向前一个last Node1 prev = last; //获取插入的元素 Node1 node1 = new Node1(prev, t, null); //然后把插入点前的next指针指向插入点的结点 if (prev == null) { //假如说插入点的前一个点是null first = node1; } else { prev.next = node1; } //将last指向新插入的元素 last = node1; //进行++操作 this.size++; } //在指定位置进行删除 public void remove(int idex) { //设置删除点 Node1 current = getNode(idex); //删除点前面 Node1 before = current.prev; //删除点后面 Node1 after = current.next; if(before==null){ //假如说删除头部 first=after; }else{ before.next = after;} if (after == null) { //假如说删除末尾 last = before; } else { after.prev = before; } this.size--;} //获取当前链表的长度 public int size(){ return size; } private class Node1 { //设置结点 T item; //数据域 Node1 next; //指针域Node1 prev; Node1 prev; public Node1(Node1 prev,T item, Node1 next) { this.item = item; this.next = next; this.prev=prev; } }//调用节点类}主方法:
import java.sql.SQLOutput;import java.util.*;import java.awt.*;import java.lang.Math;public class hello { public static void main(String []avgs) { LinkedList<String> s=new LinkedList<>(); s.add("aa"); s.add("bb"); s.add("cc"); s.add("dd"); s.add("ee"); s.remove(4); for(int i=0;i<s.size();i++){ System.out.println(s.get(i)); } }}
来源地址：https://blog.csdn.net/qq_69683957/article/details/126673359
