我想找到链表之间的数字
I want to find the number in between a linked list
我正在尝试寻找如何使用 inBetween 作为 public 方法来获取列表中数字的中间值。
双联 Class:
public class DoublyLinkedList
{
private Link first; // ref to first item
private Link last; // ref to last item
// -------------------------------------------------------------
public DoublyLinkedList() // constructor
{
first = null; // no items on list yet
last = null;
}
// -------------------------------------------------------------
public boolean isEmpty() // true if no links
{ return first==null; }
// -------------------------------------------------------------
public void insertFirst(long dd) // insert at front of list
{
Link newLink = new Link(dd); // make new link
if( isEmpty() ) // if empty list,
last = newLink; // newLink <-- last
else
first.previous = newLink; // newLink <-- old first
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}
// -------------------------------------------------------------
public void insertLast(long dd) // insert at end of list
{
Link newLink = new Link(dd); // make new link
if( isEmpty() ) // if empty list,
first = newLink; // first --> newLink
else
{
last.next = newLink; // old last --> newLink
newLink.previous = last; // old last <-- newLink
}
last = newLink; // newLink <-- last
}
// -------------------------------------------------------------
public Link deleteFirst() // delete first link
{ // (assumes non-empty list)
Link temp = first;
if(first.next == null) // if only one item
last = null; // null <-- last
else
first.next.previous = null; // null <-- old next
first = first.next; // first --> old next
return temp;
}
// -------------------------------------------------------------
public Link deleteLast() // delete last link
{ // (assumes non-empty list)
Link temp = last;
if(first.next == null) // if only one item
first = null; // first --> null
else
last.previous.next = null; // old previous --> null
last = last.previous; // old previous <-- last
return temp;
}
// -------------------------------------------------------------
// insert dd just after key
public boolean insertAfter(long key, long dd)
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return false; // didn't find it
}
Link newLink = new Link(dd); // make new link
if(current==last) // if last link,
{
newLink.next = null; // newLink --> null
last = newLink; // newLink <-- last
}
else // not last link,
{
newLink.next = current.next; // newLink --> old next
// newLink <-- old next
current.next.previous = newLink;
}
newLink.previous = current; // old current <-- newLink
current.next = newLink; // old current --> newLink
return true; // found it, did insertion
}
// -------------------------------------------------------------
public Link deleteKey(long key) // delete item w/ given key
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return null; // didn't find it
}
if(current==first) // found it; first item?
first = current.next; // first --> old next
else // not first
// old previous --> old next
current.previous.next = current.next;
if(current==last) // last item?
last = current.previous; // old previous <-- last
else // not last
// old previous <-- old next
current.next.previous = current.previous;
return current; // return value
}
// -------------------------------------------------------------
public void displayForward()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning
while(current != null) // until end of list,
{
current.displayLink(); // display data
current = current.next; // move to next link
}
System.out.println("");
}
// -------------------------------------------------------------
public void displayBackward()
{
System.out.print("List (last-->first): ");
Link current = last; // start at end
while(current != null) // until start of list,
{
current.displayLink(); // display data
current = current.previous; // move to previous link
}
System.out.println("");
}
// -------------------------------------------------------------
} // end class DoublyLinkedList
InBetweenDemo Class 为主 class:
public class InBetweenDemo
{
public static void main(String[] args)
{ // make a new list
DoublyLinkedList theList = new DoublyLinkedList();
theList.insertFirst(22); // insert at front
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11); // insert at rear
theList.insertLast(33);
theList.insertLast(55);
theList.displayForward();
int n=55;// display list forward
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.deleteFirst(); // delete first item
theList.displayForward();
n=55;
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.deleteLast();
theList.displayForward();
n=33;
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.deleteKey(22); // delete item with key 11
theList.displayForward();
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
n=99;
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.displayForward(); // display list forward
theList.insertAfter(11, 77); // insert 77 after 22
theList.insertAfter(33, 88); // insert 88 after 33
theList.displayForward(); // display list forward
} // end main()
} // end class DoublyLinkedApp
////////////////////////////////////////////////////////////////
我计划让 inBetween 方法接受一个项目作为其参数，如果该项目位于该列表中的最小元素和最大元素之间，则 return 为真。否则，方法 return 为假。但是我不确定如何用代码编写它。另外，我想知道如果删除列表中最小的项目或删除列表中最大的项目，程序可能不知道哪个项目是最大的和最小的。那我是不是也应该先用一个方法得到max和min？
您可以创建 inBetween 方法，这样它将数字作为参数，您可以在其中调用一个方法，在该方法中您将实现确定列表中最小值和最大值的算法。 注意 这仅在您的列表是全局定义的而不是在特定方法中才有效，否则您还必须将列表作为参数提供给 inBetween 方法。所以在伪代码中你可以这样做：
inBetween(numberToBeChecked):
max = getMax(yourList)
min = getMin(yourList) // you can implement this in one method and return an array containing of two elements for example. It's your choice.
if (numberToBeChecked > min && numberToBeChecked < max):
return True
else:
return False
希望这对您有所帮助。
我正在尝试寻找如何使用 inBetween 作为 public 方法来获取列表中数字的中间值。
双联 Class:
public class DoublyLinkedList
{
private Link first; // ref to first item
private Link last; // ref to last item
// -------------------------------------------------------------
public DoublyLinkedList() // constructor
{
first = null; // no items on list yet
last = null;
}
// -------------------------------------------------------------
public boolean isEmpty() // true if no links
{ return first==null; }
// -------------------------------------------------------------
public void insertFirst(long dd) // insert at front of list
{
Link newLink = new Link(dd); // make new link
if( isEmpty() ) // if empty list,
last = newLink; // newLink <-- last
else
first.previous = newLink; // newLink <-- old first
newLink.next = first; // newLink --> old first
first = newLink; // first --> newLink
}
// -------------------------------------------------------------
public void insertLast(long dd) // insert at end of list
{
Link newLink = new Link(dd); // make new link
if( isEmpty() ) // if empty list,
first = newLink; // first --> newLink
else
{
last.next = newLink; // old last --> newLink
newLink.previous = last; // old last <-- newLink
}
last = newLink; // newLink <-- last
}
// -------------------------------------------------------------
public Link deleteFirst() // delete first link
{ // (assumes non-empty list)
Link temp = first;
if(first.next == null) // if only one item
last = null; // null <-- last
else
first.next.previous = null; // null <-- old next
first = first.next; // first --> old next
return temp;
}
// -------------------------------------------------------------
public Link deleteLast() // delete last link
{ // (assumes non-empty list)
Link temp = last;
if(first.next == null) // if only one item
first = null; // first --> null
else
last.previous.next = null; // old previous --> null
last = last.previous; // old previous <-- last
return temp;
}
// -------------------------------------------------------------
// insert dd just after key
public boolean insertAfter(long key, long dd)
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return false; // didn't find it
}
Link newLink = new Link(dd); // make new link
if(current==last) // if last link,
{
newLink.next = null; // newLink --> null
last = newLink; // newLink <-- last
}
else // not last link,
{
newLink.next = current.next; // newLink --> old next
// newLink <-- old next
current.next.previous = newLink;
}
newLink.previous = current; // old current <-- newLink
current.next = newLink; // old current --> newLink
return true; // found it, did insertion
}
// -------------------------------------------------------------
public Link deleteKey(long key) // delete item w/ given key
{ // (assumes non-empty list)
Link current = first; // start at beginning
while(current.dData != key) // until match is found,
{
current = current.next; // move to next link
if(current == null)
return null; // didn't find it
}
if(current==first) // found it; first item?
first = current.next; // first --> old next
else // not first
// old previous --> old next
current.previous.next = current.next;
if(current==last) // last item?
last = current.previous; // old previous <-- last
else // not last
// old previous <-- old next
current.next.previous = current.previous;
return current; // return value
}
// -------------------------------------------------------------
public void displayForward()
{
System.out.print("List (first-->last): ");
Link current = first; // start at beginning
while(current != null) // until end of list,
{
current.displayLink(); // display data
current = current.next; // move to next link
}
System.out.println("");
}
// -------------------------------------------------------------
public void displayBackward()
{
System.out.print("List (last-->first): ");
Link current = last; // start at end
while(current != null) // until start of list,
{
current.displayLink(); // display data
current = current.previous; // move to previous link
}
System.out.println("");
}
// -------------------------------------------------------------
} // end class DoublyLinkedList
InBetweenDemo Class 为主 class:
public class InBetweenDemo
{
public static void main(String[] args)
{ // make a new list
DoublyLinkedList theList = new DoublyLinkedList();
theList.insertFirst(22); // insert at front
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11); // insert at rear
theList.insertLast(33);
theList.insertLast(55);
theList.displayForward();
int n=55;// display list forward
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.deleteFirst(); // delete first item
theList.displayForward();
n=55;
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.deleteLast();
theList.displayForward();
n=33;
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.deleteKey(22); // delete item with key 11
theList.displayForward();
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
n=99;
System.out.println("inBetween("+n+") "+ theList.inBetween(n));
theList.displayForward(); // display list forward
theList.insertAfter(11, 77); // insert 77 after 22
theList.insertAfter(33, 88); // insert 88 after 33
theList.displayForward(); // display list forward
} // end main()
} // end class DoublyLinkedApp
////////////////////////////////////////////////////////////////
我计划让 inBetween 方法接受一个项目作为其参数，如果该项目位于该列表中的最小元素和最大元素之间，则 return 为真。否则，方法 return 为假。但是我不确定如何用代码编写它。另外，我想知道如果删除列表中最小的项目或删除列表中最大的项目，程序可能不知道哪个项目是最大的和最小的。那我是不是也应该先用一个方法得到max和min？
您可以创建 inBetween 方法，这样它将数字作为参数，您可以在其中调用一个方法，在该方法中您将实现确定列表中最小值和最大值的算法。 注意 这仅在您的列表是全局定义的而不是在特定方法中才有效，否则您还必须将列表作为参数提供给 inBetween 方法。所以在伪代码中你可以这样做：
inBetween(numberToBeChecked):
max = getMax(yourList)
min = getMin(yourList) // you can implement this in one method and return an array containing of two elements for example. It's your choice.
if (numberToBeChecked > min && numberToBeChecked < max):
return True
else:
return False
希望这对您有所帮助。