20172323 2018-2019-1 《程序设计与数据结构》课堂测试报告

课程：《程序设计与数据结构》
班级： 1723
姓名：王禹涵
学号： 20172323
实验教师：王志强老师
测试日期：2018年9月
必修/选修：必修

1.测试内容

链表练习，要求实现下列功能：
（1）通过键盘输入一些整数，建立一个链表；
（2）实现节点插入、删除、输出操作；
（3）使用冒泡排序法或者选择排序法根据数值大小对链表进行排序；

2. 测试过程及结果

设计思路

错误的示范：
最开始的思路是借助上学期曾完成的一个代码，它实现了一个以整形数为结点的链表，并实现了选择排序的功能，所以我想就在这串代码的基础之上完成。
首先研究的是它已提供的几个方法
add

public void add(Number num)
    {
        NumberNode node = new NumberNode(num);
        NumberNode current;
        if (list == null)
        {
            list = node;
        }
        else
        {
            current = list;
            while (current.next != null)
            {
                current = current.next;
            }
            current.next = node;
        }
    }

这里的add方法相当于是栈里的Push而不是我们所需要实现的插入的方法，这里是我犯的第一个错误了。把输入整数创建一个链表与在链表中插入整数混为一谈。
但这串代码提供了输入整数创建链表的功能，我借助上学期用过的一个方法，将用户输入的一串数字通过空格间隔开，再用Integer.parseInt的方法重新将字符转化为int型，再通过add的方法存入链表。具体的代码如下

LinkedList a = new LinkedList();
        Scanner scan = new Scanner(System.in);
        System.out.println("Input some numbers into the linkedlist: ");
        String b = scan.nextLine();
        StringTokenizer NUM = new StringTokenizer(b, " ");
        while (NUM.hasMoreTokens()){
            a.add(Integer.parseInt(NUM.nextToken()));
        }

可以说是非常的麻烦了。
这时又得重新编写一个插入的方法，既然是要能实现在指定位置的地方插入元素，于是我想到了运用for循环来完成，又因为插入位置的不同分成了两种情况：头插法以及在中间或尾部插入元素。代码如下

public NumNode InsertNode(int num, int a) {
        NumNode Head = list;
        NumNode node = new NumNode(num);
        if (a == 1){
        node.next = Head;
        Head = node;
        }

        else {
            NumNode temp = Head;
            for (int n = 0; n < a - 2; n++){
               temp = temp.next;
            }
            if (temp.next == null){
                temp.next = node;
            }
            else {
            NumNode node1 = temp.next;
            temp.next = node;
            node.next = node1;
            }
        }
        return Head;
    }

测试类的代码不放在上面，但最终运行的结果出现了问题。虽然在中部和尾部插入没有出现问题，但在头部的插入出现了问题，在执行插入操作之后，最终显示的结果并没有插入成功。如图

最后通过debug的调试发现在编写的类中虽然有return Head，但测试类中并没有语句使得Head的值return到链表里。解决的方法就是将链表a再赋给a一次，如a = a.InsertNode(c,d);(c是要插入的数，d是要插入的位置)，但还是会报错，原因在于类型的不兼容，如图

一边a的定义是LinkedList类型，一边又要调用NumNode的方法。所以方法最终是不可行的。

成功的解决
最终我想选择运用哑结点的方法来解决头插法的插入问题。

通过在列表的前端引入哨兵结点或哑结点，可以去除涉及第一个结点的情况。哨兵结点可以作为一个假的第一个结点，并没有真正表示列表中的某个元素。当使用了哨兵结点时，所有的插入和删除操作都不用考虑太多特殊情况。

一开始我是想真的设置一个哨兵结点，即不在里面放数字，仅有next的方法链接真正的链表。但设置Numnode head1 = null或者Numnode head1 = ""似乎并不能使head1成为空结点，Numnode定义里要求必须插入一个数字，所以最后就只有将就着设置一个假的哑结点Numnode head1 = new Numnode(0),然后很机智的在toString方法里修改一下，不显示第一个结点就可以了。

public String toString()
    {
        String result = "";

        NumNode current = head1.next;
        while (current != null)
        {
            result += current.number + " ";
            current = current.next;
        }
        return result;
    }

toString方法:这里就设置了一下，使得显示的时候从head1的下一个head1.next开始。

private class NumNode{
        public int number;
        public NumNode next;

        public NumNode(int number)
        {
            this.number = number;
            next = null;
        }

    }

Numnode方法:定义了结点的方法，包括一个int型number，和指向下一结点的next。

public void InsertNode(int num, int a) {
        head1.next = list;
        NumNode node = new NumNode(num);
        NumNode temp = head1;

        for (int x = 0; x < a - 1; x++){
            temp = temp.next;
        }
        if (temp.next == null){
            temp.next = node;
        }
        else {
            NumNode node1 = temp.next;
            temp.next = node;
            node.next = node1;
        }
    }

InsertNode方法:num表示要插入的数字，a表示要插入的位置。先将num放入一个无链接的元素node，用for循环找到要插入的位置之后，再将前一个位置的next指针指向node，再将node的next指向下一个指针。
如果是直接在链表的末端插入的话就是上文提到的add方法了。我编写的代码里有一点小的缺陷就是，没有将插入和添加的方法分得很开，如果故意用插入的方法将元素添加到链表末尾应该是会报错的吧，因为node的next指针不能指向下一结点。

public void delete(int k){
        head1.next = list;
        NumNode PreNode = null, Currentnode = head1;
        for (int x = 0; x < k - 1; x++){
        if (Currentnode.next != null){
                PreNode = Currentnode;
                Currentnode = Currentnode.next;
                PreNode.next = Currentnode.next;
        }
        else{
            PreNode = Currentnode;
            PreNode.next = null;
        }
        }
    }

delete方法:删除的代码实现本质上与插入相差无异，插入的编好删除也完成了一大半了。

public void sort()
    {
        NumNode min;
        int temp;
        NumNode numNode = list;

        while (numNode != null)
        {
            min = numNode;
            NumNode current = min.next;
            while (current!=null)
            {
                if(Integer.parseInt(String.valueOf(min.number)) > Integer.parseInt(String.valueOf(current.number)))
                {
                    min = current ;
                }
                current = current.next;
            }
            temp = min.number;
            min.number = numNode.number;
            numNode.number = temp;

            numNode  = numNode.next;
        }
    }

sort方法:排序的方法是借鉴的上学期的选择排序法，这大概是唯一没遇见问题的地方。

实验运行截图

码云代码链接

3. 测试过程中遇到的问题和解决过程

问题：InsertNode方法里关于头插法的实现，设置node.next = Head,Head = node,return Head,但最后toString并没有显示头插法的结果。
解决：需要在插入后设置一个接受的语句，将新实现的语句值赋给原来的语句，即a = a.InsertNode(c,d);,但在这串代码里InsertNode是Numnode的方法，而a是LinkedList型，所以两者类型不兼容，不同类型的值的赋值会报错

4.其他

本来是想这学期每个测试都能好好做，一篇博客也不要补，即便是自己做的很差劲也不要补博客。嗯...真香
测试其实是有在好好做，奈何读题太快，完成作业的心态也比较浮躁，导致最后并没有好的结果，所以不得不认认真真地再补一篇博客。一开始还是抱着想快点了事的心态在做，所以很快就把前半部分写了出来，后来补代码遇到瓶颈再仔细审题我才眉头一皱发现事情并不简单，特别是涉及到头结点的问题真是费脑筋，上面的只是一小部分我的记录，真实情况远比这复杂得多，一个星期里我既抱着我的代码不放，不想就此打水漂，但问题又始终解决不了，另一方面我借鉴了数十个同学的代码，发现多多少少都有一些问题，想借此蒙混过关几乎不可能。
所以最后献上的代码绝对使我绞尽脑汁想了很久很久才写出来的解决方法，万望学长学姐多给点分。