基于单链表的直接插入排序-蒲公英云

基于单链表的直接插入排序

问题描述：

用单链表作为待排序数据的存储结构，在其上实现直接插入排序算法。

基本要求：

（1）待排序数据表采用单链表存储结构；

（2）设计非降序的直接插入排序算法，要求算法空间复杂度为O（1）。

（3）输入：待排序表可从文件读入、程序中定义、键盘输入或随机生成；

（4）输出：待排序记录，已排序记录。

Node.java

LinkList.java

Main.java

package ch01;
public class Node
{
    public Object data;
    public Node next;
    //无参的构造方法
    public Node()
    {
        this(null,null);
    }
    //有一个参数的构造方法
    public Node(Object data)
    {
        this(data,null);
    }
    //有两个参数的构造方法
    public Node(Object data,Node next)
    {
        this.data = data;
        this.next = next;
    }
}

LinkList.java

package ch01;
import ch01.*;
import java.lang.*;
public class LinkList
{
    public Node head;
    public LinkList()  
    {
        head = new Node();  //头指针
    }
    //将一个已经存在的带头结点的单链表置成空表
    public void clear()
    {
        head.data = null;
        head.next = null;
    }
    //单链表插入算法
    public void insert(int i,Object x)throws Exception
    {
        Node p = head;
        int j=-1;
        while(p!=null&&j<i-1)
        {
            p = p.next;
            ++j;
        }
        if(j>i-1||p==null)
            throw new Exception("插入位置不合法！");
        Node s = new Node(x);
        s.next = p.next;
        p.next = s;
    }
    //直接插入排序算法
    public void insertSort(LinkList L)
        {
            Node p,q,r,u;
            p = L.head.next;
            L.head.next = null;
            while(p!=null)
            {
                r =L.head;
                q=L.head.next;
                while(q!=null&&(Integer.valueOf((int)q.data).intValue())<=(Integer.valueOf((int)p.data).intValue()))
                {
                    r = q;
                    q = q.next;
                }
                u = p.next;
                p.next = r.next;
                r.next = p;
                p = u;
            }
        }
    public void display()
    {
        Node node = head.next;
        while(node!=null)
        {
            System.out.print(node.data+"  ");
            node = node.next;
        }
        System.out.println();
    }
}

package ch01;
import ch01.*;
import java.util.Scanner;
public class Main
{
    public static void main(String []args) throws Exception
    {
        int n = 10;
        Scanner sc = new Scanner(System.in);
        LinkList L = new LinkList();  //创建一个空的单链表
        for(int i=0;i<n;i++) 
        {
            System.out.print("请输入第"+i+"个数字：");
            int t= sc.nextInt();
            L.insert(i,t);
        }
        System.out.println("单链表上的数据为：");
        L.display();
        System.out.println("排序后的顺序为：");
        L.insertSort(L);
        L.display();        
    }
}