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

旧城等待， 2021-09-20 08:42 333阅读 0赞

# 学号 2018-2019-1 《程序设计与数据结构》实验一报告 #

## 课程：《程序设计与数据结构》 ##

###### 班级： 1723 ######

###### 姓名： 康皓越 ######

###### 学号：20172326 ######

###### 实验教师：王志强 ######

###### 实验日期：2018年9月26日 ######

###### 必修/选修： 必修 ######

### 1.实验内容 ###

*  实验一  
    链表练习，要求实现下列功能：  
    通过键盘输入一些整数，建立一个链表；  
    这些数是你学号中依次取出的两位数。 再加上今天的时间。  
      例如你的学号是 20172301  
      今天时间是 2018/10/1， 16：23：49秒数字就是20， 17，23，1， 20， 18，10，1，16，23，49  
      打印所有链表元素， 并输出元素的总数。 在你的程序中，请用一个特殊变量名来纪录元素的总数，变量名就是你的名字。 例如你叫 张三， 那么这个变量名就是  
      int nZhangSan = 0; //初始化为 0.  
    做完这一步，把你的程序签入源代码控制（git push）。
 *  实验二  
    实现节点插入、删除、输出操作；  
      继续你上一个程序，扩展它的功能，每做完一个新功能，或者写了超过10行新代码，就签入代码，提交到源代码服务器；  
    从磁盘读取一个文件， 这个文件有两个数字。  
    从文件中读入数字1， 插入到链表第 5 位，并打印所有数字，和元素的总数。 保留这个链表，继续下面的操作。  
    从文件中读入数字2， 插入到链表第 0 位，并打印所有数字，和元素的总数。 保留这个链表，并继续下面的操作。  
    从链表中删除刚才的数字1. 并打印所有数字和元素的总数。  
    签入所有代码。
 *  实验三  
    使用冒泡排序法或者选择排序法根据数值大小对链表进行排序；  
      如果你学号是单数， 选择冒泡排序，否则选择选择排序。  
      在排序的每一个轮次中，打印元素的总数，和目前链表的所有元素。 在实验二得到的程序中继续扩展， 用同一个程序文件，写不同的函数来实现这个功能。 仍然用 nZhangSan （你的名字）来表示元素的总数。
 *  实验四  
    使用数组实现实验一、二的相关内容
 *  实验五  
    实验数组实现实验三的内容
    
    ### 2. 实验过程及结果 ###
    
    #### 实验一 ####
 *  用scanner方法将数组读取后，使用Stringtokenizer方法将其分开，之后存入链表，打印

public void TailInsert(LinkedList head, LinkedList node){
            LinkedList temp;
            temp =head;
            while (temp.next != null){
                temp = temp.next;
            }
            temp.next = node;
            nkhy++;
        }

#### 实验二 ####

*  使用InputStream is = new FileInputStream方法实现从文件中读取数据，在实现成功后，使用头插法和插入法实现插入，以及删除。

front=head;
            node.next=front;
            head=node;
            System.out.println("The element is :"+ head.element);
            nkhy++;

public void Insertnode(int num,LinkedList head,LinkedList node2){
            LinkedList temp = head;
            while (num != temp.element){
              temp = temp.next;
              }
    
              node2.next = temp.next;
              temp.next = node2;
              nkhy++;
        }

public  void DeleteNode(LinkedList Head,LinkedList node){
            LinkedList PreNode = Head, CurrentNode = Head;
            while (CurrentNode !=null){
                if(CurrentNode.element != node.element){
                    PreNode = CurrentNode;
                    CurrentNode = CurrentNode.next;
                }
                else
                    break;
            }
            PreNode.next = CurrentNode.next;
            nkhy--;
        }

#### 实验三 ####

*  使用选择排序对链表进行排序

public void selectSort(LinkedList head){
            LinkedList temp = head;
            int sort[] = new int[head.size()];
            for(int index = 0;index<head.size();index++){
                sort[index] = temp.element;
                temp = temp.next;
                }
             selectionSort(sort);
        }
    
        public static void selectionSort(int[] a) {
    
            int n = a.length;
            for (int i = 0; i < n; i++) {
                int k = i;
                // 找出最小值的小标
                for (int j = i + 1; j < n; j++) {
                    if (a[j] < a[k]) {
                        k = j;
                    }
                }
                // 将最小值放到排序序列末尾
                if (k > i) {
                    int tmp = a[i];
                    a[i] = a[k];
                    a[k] = tmp;
                }
                String res = "";
                for (int index=0;index<a.length;index++){
                    res += a[index] + " ";
                }
                System.out.println("the current linkedlist is :" +res);
                System.out.println("the number of the elements is :" + a.length);
                System.out.println();
            }
        }

#### 实验四 ####

*  使用数组实现插入，删除，文件读取，数组的特点在于不必过于在意对象之间的引用关系，只需考虑空间不足时申请新的空间。对于在头部插入元素，我选择申请一个新的数组，其容量为之前二倍，将新数组的0位置处放入想要插入的元素，之后，从1开始依次放入旧数组的各个元素。删除方法同理。

public void HeadInsert(int element){
    
            array2[0] = element;
            for(int i =0;i<nKHY;i++){
                array2[i+1] = array[i];
            }
            nKHY++;
            array = array2;
            array2 = new int[DEFAULT_CAPACITY*2];
        }
    
    
        public void delete(int id){
            for(int index=0; index<id;index++){
             array2[index]=array[index];
            }
            for(int index=id ; index<nKHY;index++){
                array2[index] = array[index+1];
    
            }
            array = array2;
            array2 = new int[DEFAULT_CAPACITY*2];
            nKHY--;
        }

#### 实验五 ####

*  这里使用插入排序法，较为简单。

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

*  问题一，超出边界
 *  解决方法：可以看出，数字的个数为31，也就是说，加入的数字个数超过申请的空间，在比较后，使用了hasMoreElements()方法，于是解决了方法。
 *  问题二：在从数组插入读取的数字时，总是将末尾数字变为零。并且删除失败。同时，没有将新申请的数组在赋给原数组后将其清空，导致出现问题。同时，在将需要插入的值插入进去后，由于index值出现问题，导致后续插入出错  
    错误代码：

for(int index=0 ; index<nKHY-id+2;index++){
             array2[id+1] = array[id];
             id++;
         }

改正后：

for(int index = id ; id < nKHY ;id++){
             array2[id+1] = array[id];
    
         }

### 其他（感悟、思考等） ###

*  本次实验是对链表、数组相关知识理解，实践的一次考察，因此，很多代码相对注重基础理解，让我进一步理解了其原理。

### 参考资料 ###

*  [《Java软件结构与数据结构》][Java]

转载于:https://www.cnblogs.com/326477465-a/p/9752004.html

[Java]: https://book.douban.com/subject/26851579/