好的,我的教授(数据结构类)分配了这个:你的任务是编写一个程序,可以在双链表中更新字符访问频率。程序应该从包含许多字符的文本文件中一次读取一个字符。为了更容易,不要计算空格。每次访问字符时,在列表的节点中将其访问频率递增1。如果当前节点的频率高于其前一个节点的频率,则需要在列表中交换两个节点。继续为所有先前的节点这样做,直到没有更多的前一个节点具有较低的访问频率。最终,频率最高的字符将出现在列表的开头,次高的字符将出现在下一个节点等。您的程序还需要根据列表的顺序打印出列表中的字符。Java双链表
这是我迄今为止制作的程序。这只是一个双向链表。 我的主要问题是我应该如何去做:“每次访问一个字符时,在列表的节点中将其访问频率增加1,如果当前节点的频率高于其前一个节点的频率,则两个节点需要在列表中交换。“?
我知道没有任何行从文件中获取信息。我将在稍后补充。 任何帮助表示赞赏!
public class DoublyLinkedList {
private class Node {
String value;
Node next,prev;
public Node(String val, Node n, Node p) {
value = val;
next = n;
prev=p;
}
Node(String val) {
this(val, null, null);
}
}
private Node first;
private Node last;
public DoublyLinkedList() {
first = null;
last = null;
}
public boolean isEmpty(){
return first==null;
}
public int size(){
int count=0;
Node p=first;
while(p!=null){
count++;
p=p.next;
}
return count;
}
public void add(String e) {
if(isEmpty()){
last=new Node(e);
first=last;
}
else{
last.next=new Node(e, null, last);
last=last.next;
}
}
public void add(int index, String e){
if(index<0||index>size()){
String message=String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}
if(index==0){
Node p=first;
first=new Node(e,p,null);
if(p!=null)
p.prev=first;
if(last==null)
last=first;
return;
}
Node pred=first;
for(int k=1; k<=index-1;k++){
pred=pred.next;
}
Node succ=pred.next;
Node middle=new Node(e,succ,pred);
pred.next=middle;
if(succ==null)
last=middle;
else
succ.prev=middle;
}
public String toString(){
StringBuilder strBuilder=new StringBuilder();
Node p=first;
while(p!=null){
strBuilder.append(p.value+"\n");
p=p.next;
}
return strBuilder.toString();
}
public String remove(int index){
if(index<0||index>=size()){
String message=String.valueOf(index);
throw new IndexOutOfBoundsException(message);
}
Node target=first;
for(int k=1; k<=index;k++){
target=target.next;
}
String element=target.value;
Node pred=target.prev;
Node succ=target.next;
if(pred==null)
first=succ;
else
pred.next=succ;
if(succ==null)
last=pred;
else
succ.prev=pred;
return element;
}
public boolean remove(String element){
if(isEmpty())
return false;
Node target=first;
while(target!=null&&!element.equals(target.value))
target=target.next;
if(target==null)
return false;
Node pred=target.prev;
Node succ=target.next;
if(pred==null)
first=succ;
else
pred.next=succ;
if(succ==null)
last=pred;
else
succ.prev=pred;
return true;
}
public static void main(String[] args){
DoublyLinkedList list1=new DoublyLinkedList();
String[] array={"a","c","e","f"};
for(int i=0; i<array.length; i++){
list1.add(array[i]);
}
list1.add(1,"b");
list1.add(3,"d");
System.out.println(list1);
}
}
*您的Node类需要一个额外的字段为计数器*我不会推荐这个,而是使用不同于'String'的类作为包含'counter'和字符的'Node'的值。请记住链表节点应该只有数据和指向其他节点的指针。 – 2013-03-24 00:09:36
@LuiggiMendoza为什么?它只有两个字段,为什么要将它们聚合到一个类中? – Sebastian 2013-03-24 00:11:34
@LuiggiMendoza - 请阅读问题。他就是这样告诉**解决问题的。这是学习编码的学习/教学练习,而不是寻找解决问题的最佳算法的练习。 ('因为我们都知道这将是使用TreeMap ...) – 2013-03-24 00:21:16