20172311 实验一《程序设计与数据结构》线性结构 实验报告

20172311 实验一《程序设计与数据结构》线性结构 实验报告

课程:《程序设计与数据结构》
班级: 1723
姓名: 赵晓海
学号:20172311
实验教师:王志强
实验日期:2018年9月30日
必修/选修: 必修


1.实验内容

  • 线性结构之链表(1):通过键盘输入一些整数,建立一个链表,打印所有链表元素, 并输出元素的总数。
  • 线性结构之链表(2):实现节点插入、删除、输出操作,扩展功能,从磁盘读取一个文件,从链表中删除刚才的数字1. 并打印所有数字和元素的总数。
  • 线性结构之链表(3):使用选择排序法根据数值大小对链表进行排序,在排序的每一个轮次中, 打印元素的总数,和目前链表的所有元素。
  • 线性结构之数组(4):通过键盘输入一些整数,建立一个数组,打印所有数组元素, 并输出元素的总数;实现数组插入、删除、输出操作, 扩展功能,从磁盘读取一个文件,从链表中删除刚才的数字1. 并打印所有数字和元素的总数。
  • 线性结构之数组(5):使用选择排序法根据数值大小对数组进行排序,在排序的每一个轮次中, 打印元素的总数,和目前数组的所有元素。

2.实验过程及结果

链表与数组练习,所有功能在一个程序中完成,每完成一个功能签入一次码云

  • 线性结构之链表(1):
    1.通过键盘输入一些整数,建立一个链表
    2.这些数是学号中依次取出的两位数,再加上今天的时间
    3.打印所有链表元素, 并输出元素的总数
    4.用一个特殊变量名来记录元素的总数,变量名是你的名字

  • 结果提交截图

  • 本实验小结:
    本实验要求完成链表类的初步创建,需要完成toString()size()两个方法。在链表类的创建方面,我采用了泛型的方式,创建了一个ADT,然后采用了泛型,以便于在链表中添加任何数据,方便后期的使用。


  • 线性结构之链表(2):
    1.实现节点插入、删除、输出操作
    2.继续上一个程序,扩展它的功能,每做完一个新功能,或者写了超过10行新代码,就签入代码,提交到源代码服务器
    3.从磁盘读取一个文件, 这个文件有两个数字
    4.从文件中读入数字1, 插入到链表第5位,并打印所有数字,和元素的总数。保留这个链表,继续下面的操作
    从文件中读入数字2, 插入到链表第 0 位,并打印所有数字,和元素的总数。 保留这个链表,继续下面的操作
    5.从链表中删除刚才的数字1. 并打印所有数字和元素的总数
  • 结果提交截图:

  • 本实验小结
    本实验要求对实验(1)中创建的链表类进行功能的拓展,首先要添加节点插入、删除的功能。还要求有一个读取文件内容的方法,这个方法我直接在测试类里加了一个静态方法,因为我觉得把这个方法放到链表类里并不合适。

  • 线性结构之链表(3):
    1.使用冒泡排序法或者选择排序法根据数值大小对链表进行排序
    2.学号是双数, 使用选择排序
    3.在排序的每一个轮次中, 打印元素的总数,和目前链表的所有元素

  • 结果提交截图:


本实验小结:

本实验要求在链表类里加一个冒泡排序的方法,该方法实现了冒泡排序,而且返回每一步排序后的结果,对选择排序的方法进行适当的修改即可完成。


  • 线性结构之数组(4):
    1.通过键盘输入一些整数,建立一个数组
    2.这些数是学号中依次取出的两位数,再加上今天的时间
    3.打印所有数组元素, 并输出元素的总数
    4.用一个特殊变量名来记录元素的总数,变量名是你的名字
    5.实现数组插入、删除、输出操作
    6.继续上一个程序, 扩展它的功能,每做完一个新功能,或者写了超过10行新代码,就签入代码,提交到源代码服务器
    7.从磁盘读取一个文件, 这个文件有两个数字
    8.从文件中读入数字1, 插入到数组第 5 位,并打印所有数字,和元素的总数。 保留这个数组,继续下面的操作
    从文件中读入数字2, 插入到数组第 0 位,并打印所有数字,和元素的总数。 保留这个数组,继续下面的操作
    9.从数组中删除刚才的数字1. 并打印所有数字和元素的总数

  • 结果提交截图:

本实验小结:

个人以为本实验可以通过创建一个能够对数组操作的类来实现,声明该类也就创建也一个数组,然后该类中还具备节点的插入和删除以及toStringsize()方法,通过调用这些方法即可以完成本实验


  • 线性结构之数组(5):
    1.使用插入排序法或者选择排序法根据数值大小对数组进行排序
    2.学号是双数, 使用插入排序
    3.在排序的每一个轮次中, 打印元素的总数,和目前数组的所有元素

  • 结果提交截图:


  • 本实验小结:
    本实验要求在创建的数组操作类中新建一个选择排序的方法,该方法不仅要完成选择排序,还要返回选择排序的每一步过程,对选择排序进行一定的修改即可完成。


3.实验代码链接


4.实验过程中遇到的问题和解决过程

  • 问题:链表类的删除方法有问题,简单来说就是删除一个小一点的数没有问题,删除一个大点的数就会有问题。
  • 有bug删除方法代码如下:
//删除某一元素,一次删一个且就近
    public void deleteNumber(T t) {

            LinearNode temp = head;

            if(temp.getElement()==t)
            {
                head = temp.next;
            }
            else {
                while (!(temp.next.getElement() == t))
                {
                    temp = temp.next;
                }
                temp.next = temp.next.next;
            }
            nZhaoXiaoHai--;
    }
    
  • 使用有bug方法运行结果如图(删除的数较大时):

  • 使用有bug方法运行结果如图(删除的数较小时):

  • 看到这个就真的很蒙圈了,同样的代码,数大了会有bug,我真的佛了,要是我测试的时候用的数不是500而是20,那我这个bug可就真的可能看不到了,真的挺有意思!!!!

  • 解决方案:通过单步调试发现当数小时,连表中的数和方法引用里的数的地址一样,但是当数比较大时,两者的地址就不一样了,也就完成不了正确的删除功能了。最终通过老师的指导问题得到了解决,只需要把代码中的==改为使用.equals方法判断是否相等即可,因为==是用来判断地址是否相同的,而.equals方法则是判断元素是否相同。

  • 修复后的删除方法代码如下:

 //删除某一元素,一次删一个且就近
    public void deleteNumber(T t) {

            LinearNode temp = head;

            if(temp.getElement().equals(t))
            {
                head = temp.next;
            }
            else {
                while (!(temp.next.getElement().equals(t)))
                {
                    temp = temp.next;
                }
                temp.next = temp.next.next;
            }
            nZhaoXiaoHai--;
    }
  • 无bug方法运行结果如图:

5.感想

从对链表和数组的陌生到对他们的熟悉,真的很有成就感,有点小激动!要走的路还很长,继续努力吧!

6.参考资料

原文地址:https://www.cnblogs.com/zhaoxiaohai/p/9746741.html