主方法:
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)); } } }