【rush】单链表的增、删、改、查操作

雨点打透心脏的1/2处 2024-04-19 10:00 33阅读 0赞

注意代码中的注释中的指针并非与c++以及c中的指针一样，Java中是不存在指针这个概念的，之所以将其称为指针是为了加深对链表这一重要数据结构的理解。

package chailong;
    import java.util.Scanner;
    class Point                        //结点类
    {
    	Point next;   //指针域
    	int data;       //数据域
    	public Point() {}
    	public Point(int data)
    	{
    		this.data=data;       //初始化数据域
    		this.next=null;   //默认将指针域初始化为空指针
    	}
    }
    public  class LinkList {                 //链表类
    	static Point head=new Point(0); //头节点，这里其数据域用来记录链表中结点的数目
    	public static void Create()    //链表初始化函数
    	{
    		
    		Point fore;              //用来保存前一个结点待会在循环创建结点的时候会有用
    		Point point;
    		fore=head;
    		System.out.print("请输入你要创建的链表长度：");
    		Scanner in=new Scanner(System.in);
    		int m=in.nextInt();		
    		for(int i=0;i<m;i++)
    		{
    			System.out.println("创建的第"+(i+1)+"个结点");
    			System.out.print("请输入结点所保存的数据：");
    		    point=new Point(in.nextInt());	       //前一个结点的指针域指向当前结点	
    			fore.next=point;
    			fore=point;
    			head.data++;                    //链表中结点的数目加一
    		}
    	}
    	public  static void Traverse()                      //遍历链表的函数
    	{
    		Point m;
    		m=head;   //从头节点开始
    		System.out.print("链表的结构为：(头结点)");
    		for(int i=0;i<head.data;i++)
    		{
    			m=m.next;      //获得结点的下一个对象
    			System.out.print("---->("+(i+1)+","+m.data+")");
    		}
    		System.out.println();
    	}
    	public static void Add()                  //向链表中指定添加元素的方法
    	{
    		System.out.print("请输入插入到链表的第几个结点的位置：");
    		Scanner in=new Scanner(System.in);
    		int hj=in.nextInt();                 //录入要插入结点的位置
    		Point point=head,point2;
    		System.out.print("请输入要插入结点的数据：");
    		Point  a=new Point(in.nextInt());            //录入新节点的信息
    		int i=1;
    		while(i<hj)                      //找到要插入位置的前一个结点
    		{
    			point=point.next;
    			i++;
    		}
    		point2=point.next;           //将要插入结点的前一个结点的next指针域所指向的后面一个结点保存到point2中
    		point.next=a;                //将要插入结点的前一个结点的next设为要插入的结点
    		a.next=point2;               //并将要插入的结点的next指针域指向本来将要插入结点的前一个结点的next指针域所指向的后面一个结点
    		head.data++;
    	}
    	public static  void Delete()              //删除链表中元素的方法
    	{
    
    		System.out.print("请输入你要删除链表的第几个结点的位置：");
    		Scanner in=new Scanner(System.in);
    		int hj=in.nextInt();   
    		Point point=head;
    		int i=1;
    		while(i<hj)                      //找到要插入位置的前一个结点
    		{
    			point=point.next;
    			i++;
    		}
    		point.next=point.next.next;  //直接将要删除结点的前一个结点的next指针设置为要删除结点的后一个结点达到删除效果
    		head.data--;
    	}
    	public static void deleteWholeTable()
    	{
    		Point re,re2;       //定义两个记录指针
    		re=head;
    		while(re.next!=null)         //当指针域为空指针说明整个链表也就删除完了
    		{
    			re2=re.next;
    			re.next=null;             //在java中堆中的一块内存若没有再被引用（即可以理解为游离的）则会被Java的垃圾回收机制给回收掉
    			re=re2;
    			head.data--;
    		}
    	}
    	public static void main(String[] args)
    	{
    	    LinkList.Create();
    	    LinkList.Traverse();
    	    LinkList.Add();
    	    LinkList.Traverse();
    	    LinkList.Delete();
    	    LinkList.Traverse();
    	    LinkList.deleteWholeTable();
    	    LinkList.Traverse();    
    	}
    }