да, это один из моих домашних заданий - реализовать Круговой связанный список, основанный на Единственном связанном списке.Это довольно просто, и код легко читается.Все мои атрибуты общедоступны, чтобы избежать getters и setters и частного бизнеса.Для целей этого проекта будет достаточно public .
Я инициализировал свой счетчик nItems (количество элементов в списке) и заголовок ссылки прямо в поле атрибута,но я изменю его позже, инициализировав его внутри конструктора.
Мой step () метод, похоже, не работает вообще.Мой компилятор на мгновение зависает, а затем ничего не появляется.Вот как должен работать метод step (), если я вызываю его 4 раза:
List: 40 80 30 20 10 70 50
List: 80 30 20 10 70 50 40
List: 30 20 10 70 50 40 80
List: 20 10 70 50 40 80 30
Метод Find () работает нормально, то есть до тех пор, пока искомое значение равновнутри связанного списка.Если это не так, он будет продолжаться вечно.Если это мой список, это то, что происходит с методом find () , если вы ищете значение, которого там нет (я отлаживал его шаг за шагом):
70 60 50 40 30 20 10 10 10 10 10 10 10 10...and 10 forever
Причина: Если значения ключа, которое мы ищем, там нет, оно никогда не выйдет из цикла while, поэтому вечно повторяется current = current.next .
while(current.dData != key) {
current = current.next;
Мой метод удаления говорит, что он удалил значение 60 так, как я хотел, но вот что я получаю:
Deleted link with key 60
70 60 40 30 20 10 // lie! it deletes 50 instead of 60
Пожалуйста, взгляните также на мои методы display () и insert ().Они выглядят хорошо для меня, но я могу ошибаться, и это может быть источником всех проблем, с которыми я сталкиваюсь с методами find () и delete ().
Заранее большое спасибо !!!
class Link {
public int dData;
public Link next;
public Link(int dd) {
dData = dd;
}
public void displayLink() {
System.out.print(dData + " ");
}
}
class CircList {
public Link head = null;
int nItems = 0;
public boolean isEmpty() {
return (nItems == 0);
}
// INSERT
public void insert(int key) {
Link current = new Link(key);
if(isEmpty())
head = current;
current.next = head;
head = current;
nItems++;
}
// STEP
public void step() {
Link current = head;
do {
current = current.next;
} while(current != head);
}
// FIND
public Link find (int key) {
Link current = head;
while(current.dData != key) {
current = current.next;
}
return current;
}
// DELETE
public Link delete(int key) {
Link current = head;
while(current.dData != key) {
current = current.next;
}
if(current == head)
head = head.next;
else {
current.next = current.next.next;
nItems--;
}
return current;
}
// DISPLAY
public void displayList() {
Link current = head; // start at beginning
int counter = nItems;
while(true) {
if(counter != 0) {
current.displayLink();
current = current.next; // move to next link
counter--;
}
else
break;
}
}
}
class CircListApp {
public static void main(String[] args) {
Link f, d;
CircList theList = new CircList();
theList.insert(10); // insert items
theList.insert(20);
theList.insert(30);
theList.insert(40);
theList.insert(50);
theList.insert(60);
theList.insert(70);
//System.out.println(theList.nItems + " ");
theList.displayList(); // display list
System.out.println("");
f = theList.find(30); // find item
if( f != null)
System.out.println("Found link with key " + f.dData);
else
System.out.println("Can't find link with key 30");
// theList.step();
//
// System.out.println("Inserting link with key 80");
// theList.insert(80);
// theList.displayList(); // display list
//
d = theList.delete(60); // delete item
if( d != null )
System.out.println("Deleted link with key " + d.dData);
else
System.out.println("Can't delete link with key 60");
theList.displayList(); // display list
//
// f = theList.find(99); // find item
// if( f != null)
// System.out.println("Found link with key " + f.dData);
// else
// System.out.println("Can't find link with key 99" );
// theList.displayList(); // display list
//
// d = theList.delete(13); // delete item
// if( d != null )
// System.out.println("Deleted link with key " + d.dData);
// else
// System.out.println("Can't delete link with key 13");
// theList.displayList(); // display list
//
// System.out.println("Stepping through list");
// for(int j=0; j<theList.getSize; j++)
// {
// theList.step();
// theList.displayList();
// }
//
// System.out.println("Will delete and step one by one");
// while(theList.isEmpty() == false)
// {
// theList.delete();
// theList.step();
// theList.displayList();
// }
} // end main()
}