0
J'ai créé une liste triée triée et maintenant j'essaie de comprendre comment supprimer les doublons. Je voulais ajouter du code qui ferait cela dans la méthode Add que j'ai créée mais je n'arrive pas à le comprendre. Je pense que ça devrait être relativement facile mais je suis un peu mort de cerveau en ce moment.Recherche de doublons dans la liste triée et liée
Dans ma méthode d'ajout, je vérifie l'index pour voir où un élément doit être ajouté. "Index" est une variable int mais je voulais vérifier si "item", un comparable, était le même élément stocké avant. Je voulais utiliser la méthode compareTo mais j'obtiendrais une différence de type. Quelqu'un at-il une idée d'une meilleure façon de faire cela?
Voici le code de ma méthode d'ajouter:
package sortedListReferenceBased;
public class SortedListReferenceBasedIterativeNoDuplicates
implements SortedListInterface {
// reference to linked list of items
private Node head;
private int numItems; // number of items in list
public SortedListReferenceBasedIterativeNoDuplicates() {
numItems = 0;
head = null;
} // end default constructor
public boolean sortedIsEmpty() {
return numItems == 0;
//TODO
} // end sortedIsEmpty
public int sortedSize() {
return numItems;
//TODO
} // end sortedSize
private Node find(int index) {
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the desired
// node. Assumes that 1 <= index <= numItems+1
// Postcondition: Returns a reference to the desired
// node.
// --------------------------------------------------
Node curr = head;
for (int skip = 1; skip < index; skip++) {
curr = curr.getNext();
} // end for
return curr;
} // end find
public Comparable sortedGet(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems){
Node curr = find(index);
Object dataItem = curr.getItem();
return (Comparable) dataItem;
}
else {
throw new ListIndexOutOfBoundsException("List index out of bounds on get.");
}
//TODO
} // end sortedGet()
public void sortedAdd(Comparable item) throws ListException{
int index = locateIndex(item); //to find location where item should be added
if(index >=1 && index <= numItems+1){
//if adding an item to the very beginning of list
if (index == 1){
Node newNode = new Node(item,head);
head = newNode;
}
if (item.compareTo(something something?)== 0){ //if item is a duplicate of previous item do nothing
System.out.println("No duplicates!");
}
//advances
else {
Node prev = find(index-1); //finds out where previous node is
Node newNode = new Node(item, prev.getNext()); //creates Node with item you wish to add
prev.setNext(newNode); //links new node with previous node
}
numItems++;
}//end main if statement
else {
throw new ListIndexOutOfBoundsException("List index out of bounds on add.");
}
//TODO
} // end sortedAdd()
public void sortedRemove(Comparable item) throws ListException {
int index = locateIndex(item);
if (index >= 1 && index <= numItems){ //if the index is greater than 1 (meaning list not empty) and
//index doesn't exceed list size do the following:
//if index is value of one then delete first node in this special way
if (index == 1) {
head = head.getNext();
}
//if there is only one item in the list then set head to nothing so index out of bounds error won't occur
if (numItems == 1){
head = null;
}
else { //if none of these things occur go ahead and delete item, allocating Nodes accordingly
Node prev = find(index-1);
Node curr = prev.getNext();
prev.setNext(curr.getNext());
}
numItems--;//must account for one less item
}
if (!sortedIsEmpty()){
System.out.println("Item does not exist!");
}
else { //if index doesn't meet if statement requirements
throw new ListIndexOutOfBoundsException("List index out of bounds on remove.");
}
//TODO
} // end sortedRemove
public void sortedRemoveAll() {
// setting head to null causes list to be
// unreachable and thus marked for garbage
// collection
head = null;
numItems = 0;
} // end sortedRemoveAll
//Returns the position where item belongs or exists in a sorted list;
//item and the list are unchanged.
public int locateIndex(Comparable item) {
Node curr = head;
for (int i = 1; i <= sortedSize(); i++){
if (item.compareTo(curr.getItem())<= 0){
return i;
}//end if
else {
curr = curr.getNext();
}//end else
}//end for
return sortedSize()+1;
//TODO
} //end locateIndex()
} // end ListReferenceBased
Je présente mes excuses pour la mise en forme étrange. C'est assez dur en ce moment. Je m'excuse aussi si cette question est vraiment évidente! Haha
C'est une affectation pour ma classe Data Structures. Mon professeur nous a demandé de le créer de cette manière. Nous n'avons pas appris sur les arbres. hashtables, ou quelque chose comme ça encore si nous essayons de faire cette mission avec très peu de connaissances. D'où c'est si étrange. Merci pour votre perspicacité! – Bell
Vous devez ajouter l'étiquette de devoirs à cette question. –