问题描述

好吧，我被困在如何实现将从其他类接收数据的二进制搜索。

我正在尝试在我自己的 ADT 中实现它。

我已经手动实现了一个列表 ADT，但现在我想添加一个搜索操作，该操作手动使用二进制搜索算法并且不使用任何内置的 Java API。

例如，这是我手动实现的排序列表界面。

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T>{



   private boolean binarySearch(// What parameters should I receive from Student Object?) {
       // This will be my binary search implementation
   }         



}

问题是我将创建一个学生类，我将在其中将学生类的实例添加到上面的 sortedArrayList 中。

就像我将如何接收要放入泛型类型 sortedArrayList 中的二进制搜索算法的数据？

请注意，我不允许使用任何 JAVA 内置 API，所有内容都必须手动实现，否则我可以轻松完成此操作，但由于其限制，现在很痛苦。

示例我想按学生班级中的学生姓名进行二分搜索。我需要如何在我的这个手动实现的 ADT 中实现和接收数据？

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T>{

     private T[] list;


   private boolean binarySearch(int first, int last, T desiredItem) {

       int mid = (first + last) / 2;

          if(desiredItem.getFullName().equals(list[mid]) 
                // This part over here. How do I access attributes from Student class in this ADT so that I can access the data and do comparison for the binary search..

   }         



}

如何将 Student 类的属性访问到我自己的 ADT 中，以便我可以对二进制搜索算法进行比较？！

我真的被卡住了。

我会很感激有人给我指示。 我再次重复没有来自 JAVA 的内置 API，只能手动实现

ADT 排序列表接口

    public interface SortedListInterface <T extends Comparable<T>> {


        public boolean add(T element);


        public T get(int index);


        public boolean search(T element);


        public T remove(int index);


        public void clear();


        public int getLength();


        public boolean isEmpty();


        public boolean isFull();


    }

ADT SortedList 实现代码

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T>{

  //Data Types  

  private T[] list;
  private int length;
  private static final int SIZE = 10;


  // Constructors

  public SortedArrayList() {
    this(SIZE);
  }

  public SortedArrayList(int size) {
    length = 0;
    list = (T[]) new Comparable[SIZE]; // an array of instances of a class implementing Comparable interface and able to use compareto method but its overidden instead
  }


  // Setter & Getters

  @Override
  public int getLength() {
    return length;
  }

  @Override
  public boolean isEmpty() {
    return length == 0;
  }

  @Override
  public boolean isFull() {
    return false;
  }

  @Override
  public void clear() {
    length = 0;
  }


  // Array Expansion

  private boolean isArrayFull() {
    return length == list.length;
  }

  private void expandArray() {
    T[] oldList = list;
    int oldSize = oldList.length;

    list = (T[]) new Object[2 * oldSize];

    for (int i = 0; i < oldSize; i++) // copy old array elements into new array elements
      list[i] = oldList[i];

  }




  // ADT METHODs


  // Add New Elements Function


  @Override
  public boolean add(T element) {
    int i = 0;

    while (i < length && element.compareTo(list[i]) > 0) // return 0 with equal , return more than 1 if element larger than list[i] , return -1 if less
      i++;

    makeRoom(i + 1);
    list[i] = element;
    length++;
    return true;
  }  


  private void makeRoom(int index) {  // accepts given index
    int newIndex = index - 1;
    int lastIndex = length - 1;

    for (int i = lastIndex; i >= newIndex; i--) 
      list[i + 1] = list[i];

  }



  //Remove Elements Function

  @Override
  public T remove(int index) {  // accepts given index

    T result = null;

    if ( index >= 1 && index <= length ) {

      result = list[index - 1];

      if (index < length) 
        removeGap(index);

      length--;
    }

    return result;
  }

  private void removeGap(int index) { // accepts given index and remove the gap where the element its removed

    int removedIndex = index - 1;
    int lastIndex = length - 1;

    for (int i = removedIndex; i < lastIndex; i++) 
      list[i] = list[i + 1]; // shifts elements back to remove the gap

  }


  // Get Element

  @Override
  public T get(int index) { // accepts given index and return the object

    T object = null;

    if ( index >= 1 && index <= length) 
      object = list[index - 1];

    return object;

  }


  // Search Algorithms

  @Override
  public boolean search(T element) {

    return binarySearch(element);

  }

  private boolean binarySearch(// Implementation here) {
       // Implementation here
  } 




  //To String Method

  @Override
  public String toString() {

    String result = "";

    for (int i = 0; i < length; i++) 
      result += list[i] + "\n";

    return result;

  }



}

学生课堂实施

public class Student implements Comparable<Student>{


   // Data Types 

   private Name name;
   private char gender;
   private String icNo;
   private String mobileNo;
   private Course course;
   private int group;
   private String dOB;


   // Constructors

   public Student() {
   }

   public Student(Name name, char gender, String icNo, String mobileNo, Course course, int group, String dOB) {
        this.name = name;
        this.gender = gender;
        this.icNo = icNo;
        this.mobileNo = mobileNo;
        this.course = course;
        this.group = group;
        this.dOB = dOB;
    }

   public Student(Name name) {
        this.name = name;
    }


   // setter

   public void setName(Name name) {
        this.name = name;
    }

    public void setGender(char gender) {
        this.gender = gender;
    }

    public void setIcNo(String icNo) {
        this.icNo = icNo;
    }

    public void setMobileNo(String mobileNo) {
        this.mobileNo = mobileNo;
    }

    public void setCourse(Course course) {
        this.course = course;
    }

    public void setGroup(int group) {
        this.group = group;
    }

    public void setdOB(String dOB) {
        this.dOB = dOB;
    }


    // getter


    public Name getName() {
        return name;
    }

    public char getGender() {
        return gender;
    }

    public String getIcNo() {
        return icNo;
    }

    public String getMobileNo() {
        return mobileNo;
    }

    public Course getCourse() {
        return course;
    }

    public int getGroup() {
        return group;
    }

    public String getdOB() {
        return dOB;
    }

    @Override
    public String toString() {
        return "Student{" + "name=" + name + ", gender=" + gender + ", icNo=" + icNo + ", mobileNo=" + mobileNo + ", course=" + course + ", group=" + group + ", dOB=" + dOB + '}';
    }

   public int compareTo(Student object) { // Sort according to name if name same then sort according to gender and so on.

    int c = this.name.getFullName().compareTo(object.getName().getFullName());

    if(c == 0)
        c = this.gender - object.getGender(); 

    if(c == 0)
        c = this.icNo.compareTo(object.getIcNo());  

    if(c == 0)
        c = this.mobileNo.compareTo(object.getMobileNo());

    if(c == 0)
        c = this.group - object.getGroup();

    if(c == 0)
        c = this.dOB.compareTo(object.getdOB());

    return c;

  }


}

课程班

public class Course {


    // Data Types

    private String courseCode;
    private String courseName;
    private double courseFee;


    // Constructors

    public Course() {
    }

    public Course(String courseCode, String courseName, double courseFee) {
        this.courseCode = courseCode;
        this.courseName = courseName;
        this.courseFee = courseFee;
    }

    // setter

    public void setCourseCode(String courseCode) {
        this.courseCode = courseCode;
    }

    public void setCourseName(String courseName) {
        this.courseName = courseName;
    }

    public void setCourseFee(double courseFee) {
        this.courseFee = courseFee;
    }


    // getter

    public String getCourseCode() {
        return courseCode;
    }

    public String getCourseName() {
        return courseName;
    }

    public double getCourseFee() {
        return courseFee;
    }

    @Override
public String toString() {
    return "CourseCode = " + courseCode + "Course Name = " + courseName + "Course Fee = " + courseFee;
}




}

名称类

public class Name {

    // Data Types

    private String firstName;
    private String lastName;


    // Constructors

    public Name() {
    }

    public Name(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    // setter

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

    public void setLastName(String lastName) {
        this.lastName = lastName;
    }

    // getter

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public String getFullName(){
        return firstName + " " + lastName;
    }

    @Override
    public String toString() {
        return "Name{" + "firstName=" + firstName + ", lastName=" + lastName + '}';
    }

标签： javaalgorithmbinary-searchabstract-data-type

解决方案

二分搜索算法依赖于将正在搜索的值与正在搜索的列表中的值进行比较。这就是为什么实现的类的声明SortedListInterface是：

SortedArrayList<T extends Comparable<T>>

注意extends Comparable<T>.
Comparable是一个界面，您可以通过该界面比较两个对象。因此，在search()您必须实现的方法中，您知道列表中的每个对象都定义了该compareTo()方法，并且您只需使用该方法将正在搜索的对象与列表中的各个对象进行比较。

这是在您的项目上下文中二进制搜索算法的简单实现。

private T[] list; // The list to search.

private int count; // The number of non-null elements in 'list'.

public boolean search(T element) {
    boolean found = false;
    int lo = 0;
    int hi = count - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (list[mid].compareTo(element) < 0) {
            lo = mid + 1;
        }
        else if (list[mid].compareTo(element) > 0) {
            hi = mid - 1;
        }
        else {
            found = true;
            break;
        }
    }
    return found;
}

使用方法，您有一个方法参数。在方法代码中，您使用参数名称。但是当您从其他代码调用该方法时，您提供了一个替换参数的值。同样，上面的代码使用类型参数，当您创建 class 的实例时，该参数会替换为实际类的名称SortedArrayList。在您的情况下，T替换为Student并且类Student 必须实现该compareTo()方法。因此search()，类中的方法SortedArrayList不需要知道类中的成员Student。

所以你首先要创建一个这样的实例SortedArrayList：

SortedArrayList<Student> theList = new SortedArrayList<>();

然后你可以像这样调用search()方法：

Student s = new Student(/* relevant parameter values */);
theList.search(s);

编辑

我了解您不一定要搜索 a Student，您可能要搜索Name学生的或学生的手机号码。在那种情况下，我相信你需要一个Comparator。这是SortedArrayList添加了一个类的代码Comparator

import java.util.Comparator;
import java.util.Objects;

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T> {
    private static final int SIZE = 10;

    private Comparator<? super T> comparator;
    private T[] list;
    private int count;

    @SuppressWarnings("unchecked")
    public SortedArrayList(Comparator<? super T> c) {
        comparator = c;
        list = (T[]) new Comparable[SIZE]; // No way to verify that 'list' only contains instances of 'T'.

        /* NOTE: Following is not allowed.
        list = new T[SIZE]; // Cannot create a generic array of T
        */
    }

    @Override
    public boolean add(T element) {
        Objects.requireNonNull(element, "Cannot add null element.");
        boolean result = false;
        if (count == 0) {
            list[0] = element;
            count = 1;
            result = true;
        }
        else {
            if (!isFull()) {
                int i = 0;
                while (list[i] != null) {
                    if (element.compareTo(list[i]) < 0) {
                        break;
                    }
                    i++;
                }
                if (list[i] != null) {
                    for (int j = count - 1; j >= i; j--) {
                        list[j + 1] = list[j];
                    }
                }
                list[i] = element;
                count++;
                result = true;
            }
        }
        return result;
    }

    @Override
    public T get(int index) {
        checkIndex(index);
        return list[index];
    }

    @Override
    public boolean search(T element) {
        if (comparator == null) {
            return binarySearchComparable(element);
        }
        else {
            return binarySearchComparator(element);
        }
    }

    @Override
    public T remove(int index) {
        checkIndex(index);
        T removed = list[index];
        list[index] = null;
        for (int i = index; i < count; i++) {
            list[i] = list[i + 1];
        }
        count--;
        list[count] = null;
        return removed;
    }

    @Override
    public void clear() {
        for (int i = 0; i < count; i++) {
            list[i] = null;
        }
        count = 0;
    }

    @Override
    public int getLength() {
        return count;
    }

    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    @Override
    public boolean isFull() {
        return count == SIZE;
    }

    private boolean binarySearchComparable(T element) {
        boolean found = false;
        int lo = 0;
        int hi = count - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (list[mid].compareTo(element) < 0) {
                lo = mid + 1;
            }
            else if (list[mid].compareTo(element) > 0) {
                hi = mid - 1;
            }
            else {
                found = true;
                break;
            }
        }
        return found;
    }

    private boolean binarySearchComparator(T key) {
        int low = 0;
        int high = count - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            T midVal = list[mid];
            int cmp = comparator.compare(midVal, key);
            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return true; // key found
        }
        return false;  // key not found.
    }

    private void checkIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("Negative index.");
        }
        if (index >= count) {
            throw new IllegalArgumentException(String.format("Supplied index %d is not less than %d", index, count));
        }
    }
}

Comparator这是Namea的示例Student

import java.util.Comparator;

public class NameComparator implements Comparator<Student> {

    @Override
    public int compare(Student student1, Student student2) {
        int result;
        if (student1 == null) {
            if (student2 == null) {
                result = 0;
            }
            else {
                result = -1;
            }
        }
        else {
            if (student2 == null) {
                result = 1;
            }
            else {
                result = student1.getName().getFullName().compareTo(student2.getName().getFullName());
            }
        }
        return result;
    }
}

因此，为了根据属性的任意组合搜索列表Student，只需实现一个适当的Comparator并将其传递给SortedArrayList类。

编辑 2

根据您 2019 年 11 月 17 日的评论。
以下是“姓名和手机”的代码Comparator。正如我在之前的EditComparator中所写，您需要为给定的Student属性组合编写适当的。

import java.util.Comparator;

/**
 * Compares {@code Student} name and mobile phone number.
 */
public class NameAndMobileComparator implements Comparator<Student> {
    @Override
    public int compare(Student student1, Student student2) {
        int result;
        if (student1 == null) {
            if (student2 == null) {
                result = 0;
            }
            else {
                result = -1;
            }
        }
        else {
            if (student2 == null) {
                result = 1;
            }
            else {
                result = student1.getName().getFullName().compareTo(student2.getName().getFullName());
                if (result == 0) {
                    result = student1.getMobileNo().compareTo(student2.getMobileNo());
                }
            }
        }
        return result;
    }
}

java - 如何在我自己的 ADT 中手动实现二进制搜索 [JAVA]

问题描述

解决方案

编辑

编辑 2

推荐阅读