数据结构实验报告——排序算法设计及分析（排序单链表）_二、实验目的 1.熟悉并掌握各种排序方法的设计思路。 2.掌握各种具体排序算法在计

一、实验目的和要求

通过学习多种排序算法，体会对同一种操作多种不同的算法设计；通过比较各排序算法对于数据存储结构的要求，体会算法设计不依赖于数据存储结构，而算法实现依赖于数据存储结构:通过分析排序算法的效率，研究如何进一步提高算法性能的方法。

要求掌握每种排序算法思路、算法描述、算法设计 与算法实现手段，掌握排序算法时间复杂度和空间复杂度的分析方法，具有排序算法的设计能力。

二、实验题目

实验一：由单链表构造排序单链表

public SortedSinglyList(SinglyList<T> list)

实验二：返回归并后的排序单列表

Public SortedSinglyList<T> mergeWith(SortedSinglyList<T> list)

三、实验方法与步骤（需求分析、算法设计思路、流程图等）

(1)由单链表构造排序单链表

遍历单链表，定义一个结点记录最小值，如果所在结点比最小值小，就进行替换，否则移动到下一个结点，最后返回链表。

(2) 返回归并后的排序单列表

创建一个新的、空的排序单链表，开始比较两个单链表中元素的大小，如果this的元素小于list的第一个，就一直遍历this，一直到this的元素大于list时，再遍历list，list的遍历和之前步骤一样。

• 实验原始纪录（源程序、数据结构等）

public class SortedSinglyList<T extends Comparable<? super T>> extends SinglyList<T>

{    

    public SortedSinglyList()                             

    {

        super();                                          

    }

    

    public SortedSinglyList(T[] values)                    

    {

        super();                                          

        for (int i=0;  i<values.length;  i++)             

            this.insert(values[i]);                       

    }

    public SortedSinglyList(SortedSinglyList<T> list)      

    {

        super(list);                                      

    }   

    public void set(int i, T x)

    {

        throw new UnsupportedOperationException("set(int i, T x)");

    }

    public Node<T> insert(int i, T x)

    {

        throw new UnsupportedOperationException("insert(int i, T x)");

    }

    

    public Node<T> insert(T x)

    {

        Node<T> front=this.head, p=front.next;             

        while (p!=null && x.compareTo(p.data)>0)           

        {

            front = p;

            p = p.next;

        }

        front.next = new Node<T>(x, p);               

        return front.next;                

    }

    

    public Node<T> search(T key)

    {

        for (Node<T> p=this.head.next;  p!=null && key.compareTo(p.data)>=0;  p=p.next)

        {

            if (key.compareTo(p.data)==0)              

                return p;

        }

        return null;

    }

    

    public Node<T> insertDifferent(T x)

    {

        Node<T> front=this.head, p=front.next;            

        while (p!=null && x.compareTo(p.data)>0)           

        {

            front = p;

            p = p.next;

        }

        if (p!=null && x.compareTo(p.data)==0)

            return p;                                      

        return front.next = new Node<T>(x, p);           

    }

    public T remove(T key)

    {

        Node<T> front=this.head, p=front.next;             

        while (p!=null && key.compareTo(p.data)>0)      

        {

            front = p;

            p = p.next;

        }

        if (p!=null && key.compareTo(p.data)==0)          

        {

            front.next = p.next;                          

            return p.data;

        }

        return null;

    }

   

    public void concat(SinglyList<T> list)                

    {

        throw new UnsupportedOperationException("concat(SinglyList<T> list)");

    }

    public void addAll(SinglyList<T> list)

    {

        for (Node<T> p=list.head.next;  p!=null;  p=p.next)

            this.insert(p.data);                  

    }    

    

    public SortedSinglyList<T> union(SinglyList<T> list)

    {

        SortedSinglyList<T> result = new SortedSinglyList<T>(this);   

        result.addAll(list);

        return result;

    }

    public SortedSinglyList(SinglyList<T> list)

    {

        super(list);                                       

        for (Node<T> first=this.head.next;  first.next!=null;  first=first.next)

        {                                                

            Node<T> min=first;                             

            for (Node<T> p=min.next;  p!=null;  p=p.next)  

                if (p.data.compareTo(min.data)<0)          

                    min = p;                               

            if (min!=first)                                

            {

                T temp = min.data;

                min.data = first.data;

                first.data = temp;

            }

        }

    }

    public void merge(SortedSinglyList<T> list)            

    {

        Node<T> front=this.head, p=front.next;            

        Node<T> q=list.head.next;                         

        while (p!=null && q!=null)                         

            if ((p.data).compareTo(q.data)<0)             

            {

                front = p;

                p = p.next;

            }

            else

            {                                              

                front.next = q;

                q = q.next;

                front = front.next;

                front.next = p;

            }

        if (q!=null)                                       

            front.next=q;

        list.head.next=null;                            

    }

    

    public SortedSinglyList<T> mergeWith(SortedSinglyList<T> list)  

    {

        Node<T> p=this.head.next, q=list.head.next;      

        SortedSinglyList<T> result = new SortedSinglyList<T>();

        Node<T> rear = result.head;                     

        while (p!=null || q!=null)                       

            if (p!=null && (q!=null && (p.data).compareTo(q.data)<=0 || q==null))

            {                                             

                rear.next = new Node<T>(p.data,null);

                rear = rear.next;

                p = p.next;

            }

            else if (q!=null && (p!=null && (p.data).compareTo(q.data)>0 || p==null))

            {                                              

                rear.next = new Node<T>(q.data,null);

                rear = rear.next;

                q = q.next;

            }

        return result;

    }

    

五、实验结果及分析（计算过程与结果、数据曲线、图表等）

public static void main(String args[])

    {

     Integer []values={1,2,3,5,7,9};

     Integer []values1={6,8,10,11};

     Integer []values2={1,3,4,2,8,5,9,6,7};

     SinglyList<Integer>list3=new SinglyList<Integer>(values2);

     SortedSinglyList<Integer>list=new SortedSinglyList<Integer>(values);

     SortedSinglyList<Integer>list1=new SortedSinglyList<Integer>(values1);

     SortedSinglyList<Integer>list2=new SortedSinglyList<Integer>(list3);

     System.out.println(list+"和"+list1+"连接之后为："+"\n"+list.mergeWith(list1));

     System.out.println(list3+"转化成排序单链表之后为"+"\n"+list2);    }

}

实验结果：

1. 由单链表构造排序单链表：

 

1. 返回归并后的排序单链表：