刚学OO,对于应用方面还不太了解.
想问下怎么把英文字和数字分别放进linkedlist?
然后再用BinarySearchTree的inorder tree来排?我做了一个,英文字可以由a到z排序,可是数字不能.
还有就是重复了两次apple.
应该怎么做?aa.txt file
banana 5 7 10 1
apple 3 50 20
orange 21 16 17 30
apple 7 8 30 9输出的结果
apple 3 7 8 9 20 30 50
banana 1 5 7 10
orange 16 17 21 30
import trees.BinarySearchTree;
import java.io.*;class rtf{public static void main ( String[] args ) {
String fileName = "aa.txt" ;
String line;
ListNode head;
LinkedList s = new LinkedList();
BinarySearchTree tree = new BinarySearchTree(); try {
BufferedReader in = new BufferedReader(new FileReader(fileName)); line = in.readLine(); while ( line != null ) { // continue until end of file String[]words = line.split (" ");
for (int i=0; i < words.length; i++){
}
s.insert(line);
line = in.readLine();
}
tree.inorder();
s.print();
in.close();
}
catch ( IOException iox ) {
System.out.println("Problem reading " + fileName );
}
}
}
想问下怎么把英文字和数字分别放进linkedlist?
然后再用BinarySearchTree的inorder tree来排?我做了一个,英文字可以由a到z排序,可是数字不能.
还有就是重复了两次apple.
应该怎么做?aa.txt file
banana 5 7 10 1
apple 3 50 20
orange 21 16 17 30
apple 7 8 30 9输出的结果
apple 3 7 8 9 20 30 50
banana 1 5 7 10
orange 16 17 21 30
import trees.BinarySearchTree;
import java.io.*;class rtf{public static void main ( String[] args ) {
String fileName = "aa.txt" ;
String line;
ListNode head;
LinkedList s = new LinkedList();
BinarySearchTree tree = new BinarySearchTree(); try {
BufferedReader in = new BufferedReader(new FileReader(fileName)); line = in.readLine(); while ( line != null ) { // continue until end of file String[]words = line.split (" ");
for (int i=0; i < words.length; i++){
}
s.insert(line);
line = in.readLine();
}
tree.inorder();
s.print();
in.close();
}
catch ( IOException iox ) {
System.out.println("Problem reading " + fileName );
}
}
}
用BinarySearchTree把数字由小排到大
把英文字由小排到大需求:
原本放到aa.txt里面的東西
banana 5 7 10 1
apple 3 50 20
orange 21 16 17 30
apple 7 8 30 9 運行程序想要的結果
apple 3 7 8 9 20 30 50
banana 1 5 7 10
orange 16 17 21 30 英文由a到z順序排列
apple
banana
orange每个水果(英文)里面的数字由小到大排列
apple 3 7 8 9 20 30 50
但我写的程序,输出的结果是
apple 3 50 20
apple 7 8 30 9
banana 5 7 10 1
orange 21 16 17 30两个apple不会合并为一个
水果(英文)里的数字不会由小到大排放
BinarySearchTree
package trees;class BinaryNode {
Object data;
BinaryNode left;
BinaryNode right; public BinaryNode(Object d) {
data = d;
left = right = null;
}
public Object getData() {
return data;
}
}public class BinarySearchTree { private BinaryNode root; public BinarySearchTree() {
root = null;
} public boolean isEmpty() {
return root == null;
} public BinaryNode search(BinaryNode t, Object x) {
if (t == null)
return null;
if (((Comparable)x).compareTo(t.data) < 0)
return search(t.left, x);
else if (((Comparable)x).compareTo(t.data) > 0)
return search(t.right, x);
else
return t;
} public void insert(Object x) {
root = insertSubtree(root, x);
} private BinaryNode insertSubtree(BinaryNode t, Object x) {
if (t == null)
t = new BinaryNode(x);
else if (((Comparable)x).compareTo(t.data) < 0)
t.left = insertSubtree(t.left, x);
else
t.right = insertSubtree(t.right, x);
return t;
} private void visit(BinaryNode t) {
System.out.print(t.data + " ");
} public void preorder() {
preorderSubtree(root);
System.out.println();
} private void preorderSubtree(BinaryNode t) {
if (t == null) return;
visit(t);
preorderSubtree(t.left);
preorderSubtree(t.right);
} public void inorder() {
inorderSubtree(root);
System.out.println();
} private void inorderSubtree(BinaryNode t) {
if (t == null) return;
inorderSubtree(t.left);
visit(t);
inorderSubtree(t.right);
} public void postorder() {
postorderSubtree(root);
System.out.println();
} private void postorderSubtree(BinaryNode t) {
if (t == null) return;
postorderSubtree(t.left);
postorderSubtree(t.right);
visit(t);
} public Object getMin() {
return findMin(root).data;
} private BinaryNode findMin(BinaryNode t) { if (t == null) return t;
while (t.left != null) {
t = t.left;
}
return t;
} public Object getMax() {
return findMax(root).data;
} private BinaryNode findMax(BinaryNode t) {
if (t == null)
return null;
else if (t.right == null)
return t;
else
return findMax(t.right);
} public void delete(Object x) {
root = deleteSubtree(root, x);
} private BinaryNode deleteSubtree(BinaryNode t, Object x) {
BinaryNode temp, child; if (t == null) return null;
if (((Comparable)x).compareTo(t.data) < 0)
t.left = deleteSubtree(t.left, x);
else if (((Comparable)x).compareTo(t.data) > 0)
t.right = deleteSubtree(t.right, x);
else if (t.left != null && t.right != null) { t.data = findMin(t.right).data;
t.right = deleteSubtree(t.right, t.data);
}
else
t = (t.left != null) ? t.left : t.right; return t;
} public int size() {
return sizeSubtree(root);
} private int sizeSubtree(BinaryNode t) {
if (t == null) return 0;
return sizeSubtree(t.left) + sizeSubtree(t.right) + 1;
} public int height() {
return heightSubtree(root);
} private int heightSubtree(BinaryNode t) {
if (t == null) return -1;
int h = heightSubtree(t.left);
int k = heightSubtree(t.right);
return h > k ? h + 1 : k + 1;
}}
Linkedlistimport java.util.Iterator;class ListNode { private Object data;
private ListNode next; public ListNode(Object o) { data = o; next = null; }
public ListNode(Object o, ListNode nextNode)
{ data = o; next = nextNode; } public Object getData() { return data; }
public void setData(Object o) { data = o; } public ListNode getNext() { return next; }
public void setNext(ListNode next) { this.next = next; }} // class ListNodeclass EmptyListException extends RuntimeException {
public EmptyListException ()
{ super("List is empty"); }
} // class EmptyListExceptionpublic class LinkedList { private ListNode head;
private ListNode tail; private int length; // the length of the list public LinkedList() {
head = tail = null;
length = 0;
} public boolean isEmpty() { return head == null; } public void addToHead(Object item) {
if (isEmpty())
head = tail = new ListNode(item);
else
head = new ListNode(item, head);
length++;
} public void addToTail(Object item) {
if (isEmpty())
head = tail = new ListNode(item);
else {
tail.setNext(new ListNode(item));
tail = tail.getNext();
}
length++;
} public Object removeFromHead() throws EmptyListException {
Object item = null;
if (isEmpty())
throw new EmptyListException();
item = head.getData();
if (head == tail)
head = tail = null;
else
head = head.getNext();
length--;
return item;
} public Object removeFromTail() throws EmptyListException {
Object item = null;
if (isEmpty())
throw new EmptyListException();
item = tail.getData();
if (head == tail)
head = tail = null;
else {
ListNode current = head;
while (current.getNext() != tail)
current = current.getNext();
tail = current;
current.setNext(null);
}
length--;
return item;
} public void print() {
System.out.print("\n");
ListNode current = head;
while (current != null) {
System.out.print(current.getData() + " \n");
current = current.getNext();
}
//System.out.print("]");
//System.out.print(" head: " + (head == null ? "null" : head.getData()));
//System.out.print(" tail: " + (tail == null ? "null" : tail.getData()));
}
public String toString() {
String str = "[ ";
ListNode current = head;
while (current != null) {
str = str + current.getData() + " ";
current = current.getNext();
}
return str + " ]";
} public int count() {
return length;
} public Object remove(int n) {
Object item = null;
if (n <= length) { // make sure there is nth node to remove
// special treatment for first and last nodes
if (n == 1) return removeFromHead();
if (n == length) return removeFromTail();
// removal of nth node which has nodes in front and behind
ListNode current = head;
ListNode previous = null;
for (int i = 1; i < n; i++) { // current will point to nth node
previous = current;
current = current.getNext();
}
// data to be returned
item = current.getData();
// remove the node by adjusting two pointers (object reference)
previous.setNext(current.getNext());
}
length--;
return item;
} public void add(int n, Object item) {
// special treatment for insert as first node
if (n == 1) {
addToHead(item);
return;
}
// special treatment for insert as last node
if (n > length) {
addToTail(item);
return;
}
// locate the n-1th node
ListNode current = head;
for (int i = 1; i < n-1; i++) // current will point to n-1th node
current = current.getNext();
// create new node and insert at nth position
current.setNext(new ListNode(item, current.getNext()));
length++;
} public Object get(int n) {
// n is too big, no item can be returned
if (length < n) return null;
// locate the nth node
ListNode current = head;
for (int i = 1; i < n; i++)
current = current.getNext();
return current.getData();
}
// ADVANCED methods for ORDERED LIST public Object remove(String s) { // remove() is overloaded
// method 0: use the add(n,s)
int position = 0;
ListNode current = head;
while (current != null) {
position++;
if (((String)current.getData()).compareToIgnoreCase(s) < 0) {
current = current.getNext();
}
else {
if (((String)current.getData()).compareToIgnoreCase(s) == 0) {
System.out.println("Found in positon " + position);
return remove(position);
}
break; // current points to a node with string >= s
}
} // while
System.out.println(" Not found in the list. Position at " + position);
return null;
} // remove(String s)
// method 0: use the add(n,s)
int position = 0;
ListNode current = head;
while (current != null) {
position++;
if (((String)current.getData()).compareToIgnoreCase(line) < 0) {
current = current.getNext();
}
else {
// System.out.println("Found in positon " + position);
add(position,line);
return;
//break; // current points to a node with string >= s
}
} // while
// System.out.println("Search all list. Position at " + position);
add(position+1,line);
return;
}class MyIterator implements Iterator { private ListNode current; public MyIterator() {
current = head;
} public boolean hasNext() {
return current != null;
} public Object next() {
Object item = current.getData();
current = current.getNext();
return item;
} public void remove() { // remove is not available
throw new UnsupportedOperationException();
} } // class ListIterator
// iterator method
public Iterator iterator() {
return new MyIterator();
}
}
你所需要的功能很多方法都能实现，加入PriorityQueue容器是最简便也是扩展性比较强的一种;
public static void main(String args[]) {
Main main = new Main();
main.add("banana", new int[]{5, 7, 10, 1});
main.add("apple", new int[]{3, 50, 20});
main.add("orange", new int[]{21, 16, 17, 30});
main.add("apple", new int[]{7, 8, 30, 9});
main.p();
} public void add(String name, int[] value) {
Node head = map.get(name);
for (int i : value) {
if (head == null) {
head = new Node(i);
map.put(name, head);
continue;
}
if (i < head.t) {
Node _head = new Node(i);
_head.next = head;
head = _head;
map.put(name, head);
continue;
}
Node temp = head;
while (temp != null) {
if (temp.t == i) {
break;
}
if (temp.next == null || i < temp.next.t) {
Node next = temp.next;
temp.next = new Node(i);
temp.next.next = next;
break;
} else {
temp = temp.next;
}
}
}
} public void p() {
for (String str : map.keySet()) {
System.out.print(str);
Node temp = map.get(str);
while (temp != null) {
System.out.print(" " + temp.t);
temp = temp.next;
}
System.out.println();
}
}
private Map<String, Node> map = new TreeMap<String, Node>(); private static class Node { public Node(int t) {
this.t = t;
}
private int t;
private Node next;
}
public void add(String name, int[] value) {
TreeSet<Integer> set = map.get(name);
if (set == null) {
set = new TreeSet<Integer>();
map.put(name, set);
}
for (Integer i : value) {
set.add(i);
}
} public void p() {
for (String str : map.keySet()) {
System.out.print(str);
for (Integer i : map.get(str)) {
System.out.print(" " + i);
}
System.out.println();
}
}
private Map<String, TreeSet<Integer>> map = new TreeMap<String, TreeSet<Integer>>();