- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
出于练习目的,我得到了如下所示的代码,我的任务是修改它,以便链表始终排序。我现在的主要问题是我不知道从哪里开始或要修改哪些方法。欢迎任何提示。
import java.util.Iterator;
import java.util.NoSuchElementException;
/
* This is a copy of the LinkedList class, which has been modified to only
* accept elements that can be compared.
*
* Note that the elements accepted by this list must implement the Comparable
* interface. This means that the elements can be compared as follows:
*
* x.compareTo(y) == 0 means x == y
* x.compareTo(y) < 0 means x < y
* x.compareTo(y) > 0 means x > y
*
* Your task is to modify this class so that the elements always are sorted.
*/
public class SortedLinkedList<T extends Comparable<T>> implements Iterable<T> {
/* Easy operations for a linked list
add(x): Searching for the place where the element x is to be added must
take place in the calling routine. This must set previous to
point to the node AFTER which the new element is to be inserted.
curr is set to point to the new element.
remove(): The curr element is removed from the list. Searching for this
element must take place in the calling routine. This must set
curr to point to the element to be removed. After removal curr
points to the element following the removed one.
isEmpty(): checks for an empty list
endOfList(): checks whether curr has reached and passed the end of the list
retrievecurr(): return the info part of the curr element.
reset(): resets the list so that curr points to the first element
succ(): an iterator, moves curr one step forward
Note that when a class implements the interface Iterable<T> then
it can be the target of the "foreach" statement. See IterationExample.java
*/
private Node start, curr, prev;
public SortedLinkedList() {
curr = null; // the curr position in the list
start = null; // the first element
prev = null; // the node before curr
}
public void add(T x) {
if (start == null) { // if start == null, insert a first element into an empty list
Node newNode = new Node(); // create the new element, info and link are set to null.
newNode.info = x; // and assign the data given as parameter. The link is left as null
start = newNode; // start is updated to point to the new element
curr = start; // curr is updated to point to the new first (and only) element
} else if (prev == null) { // a new first element is inserterd into a non-empty list
Node newNode = new Node(); // a new node is created ...
newNode.info = x; // and assigned the data given as parameter
newNode.link = start; // and linked before the old first element
start = newNode; // start is updated to point to the new first element
curr = newNode; // curr is updated to point to the new first element
} else { // a new element is inserted last (if prev.link == null) or between prev and curr
Node newNode = new Node(); // create a new node
newNode.info = x; // assign it the data given as parameter
newNode.link = prev.link; // link it before curr ...
prev.link = newNode; // ... and after previous
curr = newNode; // update curr to point to newNode
}
} // add
public void remove() { // removes the current node
if (isEmpty() || endOfList()) { // no node to be removed
return;
}
else { // curr points to the element to be removed
if (prev == null) { // remove a first element: start is updated!
start = start.link; // "jump over" the first element (curr/start)
curr = start; // update curr to point to the new start
}
else { // the element to be removed is in the middle of the list/last
prev.link = curr.link; // "jump over it!"
curr = curr.link; // curr is updated to the element after the removed one
}
}
} // remove
public boolean isEmpty() { // checks if the list is empty
return start == null;
}
public T retrieveCurr() { // return the curr element's data
return curr.info;
}
public void reset() { // resets a list so that curr points to the first element
curr = start; // curr starts from the beginning of the list
prev = null; // there is no previous element for curr
}
public boolean endOfList() { // has curr reached and passed the end of the list?
return curr == null;
}
public void succ() { // moves curr to the next element
curr = curr.link; // curr is set to the next node
if (prev == null) { // previous must follow; if it was null to begin with ...
prev = start; // ... it must now point to start
}
else {
prev = prev.link; // otherwise it is just moved one step forward
}
}
public Iterator<T> iterator(){ //Needed to implement the iterable interface
return new ListIterator();
}
private class Node {
T info;
Node link;
Node() {
info = null;
link = null;
}
}
/*
* An example iterator class to walk through the list from
* the start to the end. Note the similarity with the methods
* above. They implement similar functionality, but here it
* is hidden behind a standard interface.
*
* Note the class is private and the implementation of the iterator
* is therefore not visible outside.
*
* See the java api documentation for more information on
* how iterators should behave.
*/
private class ListIterator implements Iterator<T>{
private Node curr;
public ListIterator(){
curr=start;
}
public boolean hasNext(){
return curr!=null;
}
public T next(){
if(curr==null){
throw new NoSuchElementException();
}
T value=curr.info;
curr=curr.link;
return value;
}
public void remove(){
throw new UnsupportedOperationException();
}
}
}
最佳答案
我认为您必须在实现中做出的唯一重大更改是在插入元素时保持列表排序。请注意,反向操作(即删除元素)不需要更改,因为您只是扔掉不会改变列表中任何顺序的东西。
下面的 add()
方法遍历列表,直到找到合适的位置。然后,它拼接新节点并在适用的地方更新 start
、prev
和 curr
指针。
public void add(T x) {
Node newNode = new Node();
newNode.info = x;
// case: start is null; just assign start to the new node and return
if (start == null) {
start = newNode;
curr = start;
// prev is null, hence not formally assigned here
return;
}
// case: new node to be inserted comes before the current start;
// in this case, point the new node to start, update pointers, and return
if (x.compareTo(start.info) < 0) {
newNode.link = start;
start = newNode;
curr = start;
// again we leave prev undefined, as it is null
return;
}
// otherwise walk down the list until reaching either the end of the list
// or the first position whose element is greater than the node to be
// inserted; then insert the node and update the pointers
prev = start;
curr = start;
while (curr != null && x.compareTo(curr.info) >= 0) {
prev = curr;
curr = curr.link;
}
// splice in the new node and update the curr pointer (prev already correct)
newNode.link = prev.link;
prev.link = newNode;
curr = newNode;
}
关于java - 保持 LinkedList 始终排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41959004/
当我使用路径文件上的快捷方式在文件之间移动时,似乎我不仅仅是在文件之间移动。 我使用>转到一个文件,在该文件中我更改光标的位置并执行某些操作,然后按 gf noremap 关于vim 通过快捷方式直
我正在尝试使用 Pong P. Chu 的书来学习 Verilog。我有一个关于如何评估和实现始终 block 的问题。作者代码中的风格让我感到困惑。 在此示例中,他编写了一个具有两个输出寄存器“y1
我正在尝试制作一个聊天应用程序,因此我需要它始终接收服务器信息。因此,当请求完成时,在: http.onreadystatechange=function(){ 我再次调用该函数,因此: reques
当您在 always block 敏感度列表中使用通配符 @* 时,我对什么被视为输入有点困惑。例如,在下面的示例中,哪些信号被解释为导致 always block 被重新评估的输入? 据我了解,cl
我有一个充当调试器的程序。我为线程设置了一个 hw bp,将 dr0 设置为我希望 bp 所在的地址,将 dr7 设置为 1,因为我希望 bp 在每次执行该地址时生成一个事件。 它有效,但现在的问题是
如何每次都以管理员身份在 Windows 上运行 git bash。 操作系统 - Windows 10 家庭版 64 位 最佳答案 我在 Google 上找到了这个结果: 将 Git Bash 设置
使用 accept() 时或 getpeername() , sockaddr_storage总是有 ss_family=AF_INET6 : struct sockaddr_storage addr
我在 Cordova 方面还有另一个问题。我想在 Cordova 7.1.0 中使用插件“cordova.custom.plugins.exitapp”和“cordova-plugins-printe
我试图让模块通过 ISE 12.4 中的语法检查,但它给了我一个我不明白的错误。首先是代码片段: parameter ROWBITS = 4; reg [ROWBITS-1:0] temp; genv
我正在使用Cordova开发适用于iOS的应用程序,其中包括地理位置功能(我使用官方插件https://github.com/apache/cordova-plugin-geolocation)。我在
我想知道是否有可能只在敏感列表中的多个信号一起变化时才执行 always block 。 例如,假设我有一个信号“in”和另一个“posedge clk”。我希望在两个信号都发生变化时执行 alway
我需要实现一种算法来访问数据库来检查最后一个元素,以便计算新的元素。当然,第一次这是不可能的,因为数据库是空的,我得到 IndexOutOfBoundsException) index 0 reque
我正在利用我在网上找到的画廊系统,根据鼠标图像的接近程度,它会按比例增长。 链接:Gallery 好吧,我调整了代码以响应(如您所见正在 build 中)并且没有明显的问题。我的问题在更改分辨率时开始
我正在创建一个 kiosk 应用程序,我想确保它无论如何始终位于其他 Windows 应用程序和 Windows 任务栏之上。 我已经阻止了 Windows 键盘命令(alt-tab 等),但仍有可能
我即将开始一个新的 React 项目,并尝试利用我以前的知识来创建一些关于我如何构建应用程序的规则。 有些事情我认为是真的: Redux 保存整个应用程序的“主要”数据 如果需要跨应用程序共享,Red
当你打开 VS Code 时,终端默认是在底部打开的。您可以单击该图标将其向右移动。我想知道是否有办法将右侧打开设置为默认值。 谢谢。 最佳答案 是的 - 在 v1.20 中引入了设置 workb
我有一个Events表,其中包含各种类型的事件。我只关心其中一种类型。因此,我编写的每个查询都以开头 Events.objects.filter(event_type="the_type").\
我在单例中创建了一个Timer,并且我一直在努力解决为什么Timer没有触发。我查看了这里的帖子,但没有找到我认为可以直接回答我的问题的帖子。 class ConnectionStateMonitor
我在 TableViewController 中显示了一组项目。它们在 TVC 中正确显示。下面的代码会继续,但它只会继续到我的 MKMapItem 数组的 indexPath 0,而不是被单击的单元
我的 VC 是这样的: var coins = 50 // coins override func viewDidLoad() { super.viewDidLoad() if(SKP
我是一名优秀的程序员,十分优秀!