Data structure course practice 1 - student achievement file management system (experimental preparation)

Experimental content

1. Student information input, including student number, name, major, score of four courses, total score and ranking;
2. The system can browse, add, delete and modify student information;
3. The ranking and information output are determined according to the student's grades, including two-way bubble sorting, Hill sorting, quick sorting and heap sorting.
4. It is required to query the student information according to the student number or name;
Information modification can only modify the scores of four courses;
5. File access student information.

Selection of programming language and development environment

Programming language: java
Development environment: the IDE uses idea, and the jdk version is 1.8

Experimental ideas

1, Design ideas

The student achievement file management system can adopt the DAO design mode. The full name of Dao is (Data Access Object). Its main function is to carry out data operation. It belongs to the operation of data layer in the standard development architecture of the program.

DAO design pattern is mainly divided into three layers:
Display layer: mainly uses JSP/Servlet to display the page effect
Business layer: (Business Object, data object) will combine multiple atomic DAO operations to form a complete business logic.
Data layer: (DAO, Data Access Object, database access object) provides multiple atomic DAO operations, such as add, delete, modify and query, all of which are atomic operations.

2, Preparatory work

First of all, clarify the object involved in the student achievement file management system - students, and create a student class to store relevant student information.

/**
Student class
 */
public class Student {
    /**
    Define student information, including student number, name, major, score of four courses, total score and ranking
     */
    private int number;
    private String name;
    private String Major;
    private double MathScore;
    private double EnglishScore;
    private double ChineseScore;
    private double ArtScore;
    private double TotalScore;
    private int Rank;

    public Student(){

    }

Secondly, create a data class to simulate the database and initialize the student information.

/**
 * Database class
 */
public class Database {
    private List<Student> studentList=new ArrayList<>();

    /**
     * Initialize the data of the collection in the construction method
     */
    public Database(){
        studentList.add(new Student(1001, "Zheng", "software engineering", 95, 89, 86, 75));
        studentList.add(new Student(1002, "Jia", "Computer science and technology", 87, 94, 90, 88));
        studentList.add(new Student(1003, "Kun", "software engineering", 91, 88, 85, 79));
        studentList.add(new Student(1004, "Xue", "information safety", 86, 90, 70, 91));
        studentList.add(new Student(1005, "Qian", "Internet of things project", 97, 81, 90, 72));
        studentList.add(new Student(1006, "Wuan", "communication engineering", 79, 88, 85, 90));
        studentList.add(new Student(1007, "Dian", "Computer science and technology",89,82, 84, 85));
        studentList.add(new Student(1008, "Wang", "Internet of things project", 91, 92, 88, 70));
    }

Then, create a class to operate the data, encapsulate the relevant data access methods, and realize the operations of adding, deleting, modifying, querying and sorting the student data.

**
 * encapsulation students Related data access methods
 */
public class StudentDao {

    private Database database;
    private List<Student> sortList;

    public StudentDao(Database database){
        this.database=database;
    }

Finally, create a class that can display the page effect of the student achievement file management system to show the use of the whole system.

/**
 * Student achievement file management system
 */
public class Service {
    private StudentDao studentDao;
    Scanner scanner=new Scanner(System.in);

    public Service(Database database){
        studentDao=new StudentDao(database);
    }

3, Correlation algorithm

In the operation of sorting students' grades, four sorting algorithms are used.

1. Bidirectional bubble sorting

Similar to one-way bubble sorting, two-way bubble sorting is to orderly pop out elements to both ends at the same time after one-way bubble sorting is completed, so that both ends always remain in an orderly state and the middle is disordered.
Assuming that there are N elements to be sorted, only N /2 times of sorting is required at most to make all elements orderly.

 public List<Student> sortByBubble(){
        List<Student> studentList=database.getStudentList();
        boolean flag=true;
        for(int i=0,j;i<studentList.size()/2&&flag;i++) {
            flag = false;

            /**
             * Forward bubble sort
             */
            for (j = i; j < studentList.size() - 1 - i; j++) {
                Student student = new Student();
                if (studentList.get(j).getTotalScore() > studentList.get(j + 1).getTotalScore()) {
                    student = studentList.get(j);
                    studentList.set(j, studentList.get(j + 1));
                    studentList.set(j + 1, student);
                    flag = true;
                }
            }

            /**
             * Reverse bubble sort
             */
            for (--j; j > i; j--) {
                Student student = new Student();
                if (studentList.get(j).getTotalScore() < studentList.get(j - 1).getTotalScore()) {
                    student = studentList.get(j);
                    studentList.set(j, studentList.get(j - 1));
                    studentList.set(j - 1, student);
                    flag = true;
                }
            }
        }

        for(int i=0;i<studentList.size();i++)
            studentList.get(i).setRank(studentList.size()-i);

        return studentList;

    }

2. Hill sort

Hill sorting is to group the records according to a certain increment of subscript, and sort each group with direct insertion sorting algorithm; As the increment decreases, each group contains more and more keywords. When the increment decreases to 1, the whole file is just divided into one group, and the algorithm terminates.

 public List<Student> sortByShell(){
        List<Student> studentList=database.getStudentList();
        int length=studentList.size();
        int gap=1;
        while(gap<length){
            gap=gap*3+1;
        }
        while(gap>0){
            for(int i=gap;i<length;i++){
                Student student=studentList.get(i);
                int j=i-gap;
                //Cross region sorting
                while(j>=0&&studentList.get(j).getTotalScore()> student.getTotalScore()){
                    studentList.set(j+gap, studentList.get(j));
                    j-=gap;
                }
                studentList.set(j+gap, student);
            }
            gap=gap/3;
        }

        for(int i=0;i<studentList.size();i++)
            studentList.get(i).setRank(studentList.size()-i);

        return studentList;
    }

3. Quick sort

The core idea of quick sorting is divide and conquer, divide and conquer. Its implementation method is to select a benchmark value from the sequence each time, and compare other numbers with the benchmark value in turn. The one larger than the benchmark value is placed on the right, and the one smaller than the benchmark value is placed on the left. Then, select a benchmark value for the two groups of numbers on the left and right respectively, carry out the same comparison movement, and repeat the steps until they finally become a single element, and the whole array becomes an orderly sequence.

public List<Student> sortByQuick(){
        List<Student> studentList=database.getStudentList();
        sort(studentList,0,studentList.size()-1);

        for(int i=0;i<studentList.size();i++)
            studentList.get(i).setRank(studentList.size()-i);

        return studentList;
    }

private void sort(List<Student> studentList,int startIndex,int endIndex){
        if(endIndex<=startIndex)
            return;
        //segmentation
        int midIndex=partition(studentList, startIndex, endIndex);
        sort(studentList, startIndex, midIndex-1);
        sort(studentList, midIndex+1, endIndex);
    }

private int partition(List<Student> studentList,int startIndex,int endIndex){
        double mid=studentList.get(startIndex).getTotalScore();     //Take reference value
        int mark=startIndex;

        for(int i=startIndex+1;i<=endIndex;i++){
            if(studentList.get(i).getTotalScore()<mid){
                //If it is less than the reference value, mark+1 and exchange positions.
                mark++;
                Student student=studentList.get(mark);
                studentList.set(mark, studentList.get(i));
                studentList.set(i, student);
            }
        }
        //Exchange position between reference value and corresponding element of mark
        studentList.set(startIndex,studentList.get(mark));
        studentList.set(mark, studentList.get(startIndex));

        return mark;
    }

4. Heap sort

Heap sorting is a tree selection sorting method. Its characteristics are: in the process of sorting, array[0,..., n-1] is regarded as the sequential storage structure of a complete binary tree, and the element with the largest (smallest) keyword is selected in the current unordered area by using the internal relationship between parent nodes and child nodes in the complete binary tree.

   public List<Student> sortByHeap(){
        List<Student> studentList=database.getStudentList();
        int length=studentList.size();
        //Build heap
        buildHeap(studentList, length);
        for(int i=length-1;i>0;i--){
            Student student=studentList.get(0);
            studentList.set(0, studentList.get(i));
            studentList.set(i, student);
            length--;
            sink(studentList, 0, length);
        }

        for(int i=0;i<studentList.size();i++)
            studentList.get(i).setRank(studentList.size()-i);

        return studentList;
    }
    private void buildHeap(List<Student> studentList,int length){
        for(int i=length/2;i>=0;i--){
            sink(studentList,i,length);
        }
    }
    private void sink(List<Student> studentList,int index,int length){
        int leftchild=2*index+1;//Left child node subscript
        int rightchild=2*index+2;//Right child node subscript
        int present=index;

        if(leftchild<length&&studentList.get(leftchild).getTotalScore()>studentList.get(present).getTotalScore())
            present=leftchild;

        if(rightchild<length&&studentList.get(rightchild).getTotalScore()>studentList.get(present).getTotalScore())
            present=rightchild;

        if(present!=index){
            Student student=studentList.get(index);
            studentList.set(index, studentList.get(present));
            studentList.set(present, student);
        }
    }
}

Posted by anon_amos on Thu, 14 Apr 2022 05:43:12 +0930