アルゴリズム(第4版)授業後の練習問題(1.3.18~1.3.28)
6661 ワード
package com.zt.data;
import edu.princeton.cs.algs4.StdOut;
public class Listed<Item>{
private Node first;
private Node last;
private int N;
public class Node{
Item item;
Node next;
public Node(Item item) {
this.item = item;
}
public Node(){
}
}
public Listed(){
first = null;
last = null;
}
public Listed(Item[] a){
for(Item item:a){
append(item);
}
}
public int size(){
return N;
}
public void add(Item item){
Node node = new Node(item);
if(first==null) {
first = node;
}
else{
Node temp = first;
while(temp.next!=null){
temp=temp.next;
}
temp.next = node;
}
N++;
}
public String toString(){
StringBuilder str = new StringBuilder();
Node temp=first;
while(temp.next!=null){
temp = temp.next;
str.append(temp.item+" ");
}
return first.item+" "+str;
}
/**
* 1.3.20
* @param k
* @return
*/
public Item delete(int k){
if(k==0){
Node oldFirst = first;
first = oldFirst.next;
N--;
return first.item;
}else{
Node current = first,prev=null;
for(int i=1;i<k;i++){
prev = current;
current = current.next;
}
prev.next = current.next;
N--;
return current.item;
}
}
/**
* 1.3.21 (find rename to contains)
* @param item
* @return
*/
public boolean contains(Item item){
Node current = first;
while(current!=null && !current.item.equals(item)){
current = current.next;
}
return current!=null;
}
/**
* 1.3.19
* @return
* @throws NoSuchFieldException
*/
public Item deleteLastNode() throws NoSuchFieldException{
if(first==null) {
throw new NoSuchFieldException(" ");
}else{
Node current = first,prev = null;
while(current.next!=null){
prev = current;
current = current.next;
}
prev.next=current.next;
N--;
return prev.item;
}
}
/**
* 1.3.24
* @param node
*/
public void removeAfter(Node node){
if(node!=null && node.next!=null){
if(node.next.next==null){
last = node;
}
node.next = node.next.next;
N--;
}
}
/**
* 1.3.25
* @param a
* @param b
*/
public void insertAfter(Node a,Node b){
if(a!=null&&b!=null){
if(last == a)
last = b;
b.next = a.next;
a.next=b;
N++;
}
}
public Node remove(Node node,Item item){
if(node!=null){
Node current = remove(node, item);
if(node.item.equals(item)){
return current;
}else{
current.next = current;
return current;
}
}else{
return null;
}
}
public boolean isEmpty(){
return N==0;
}
public Node createNode(Item item){
Node node = new Node();
node.item = item;
return node;
}
public Item getFrist(){
if(isEmpty()) new RuntimeException("Frist is Empty");
return first.item;
}
public Item getLast(){
if(isEmpty()) new RuntimeException("Last is Empty!");
return last.item;
}
public static void showList(Listed list){
if(!list.isEmpty())
StdOut.printf("Size: %d,first: %s, last: %s
",list.size(),list.getFrist(),list.getLast());
else
StdOut.printf("Size:%d
", list.size());
}
public void append(Item item){
Node node = new Node();
node.item = item;
if(isEmpty()){
first = node;
last = node;
}else{
last.next=node;
last = node;
}
N++;
}
public Node node(int k){
if(k<0) return null;
Node current = first;
int i=1;
while(i<k&¤t!=null){
current = current.next;
i++;
}
return current;
}
/**
* 1.3.27
* @param first
* @return
*/
public int max(Node first){
if(first==null){
return 0;
}
int max = (int) first.item;
while(first.next!=null ){
if((int)first.next.item>max){
max = (int) first.next.item;
}
first = first.next;
}
return max;
}
/**
* 1.3.28
* @param first
* @return
*/
public int maxForRecursion(Node first){
if(first==null) throw new RuntimeException("List is Empty!");
if(first.next==null) return (int)first.item;
else{
int max = maxForRecursion(first.next);
return (int)first.item > max?(int)first.item:max;
}
}
/**
* 1.3.30
* @param node
* @param item
* @return
*/
public Node reverse(Node x){
Node first = x;
Node reverse = null;
while(first!=null){
Node second = first.next;
first.next = reverse;
reverse = first;
first = second;
}
return reverse;
}
/**
* 1.3.30（ ）
* @param x
* @return
*/
public Node reverse1(Node frist){
if(frist==null) return null;
if(frist.next==null) return frist;
Node second = frist.next;
Node rest = reverse1(second);
second.next = frist;
frist.next = null;
return rest;
}
/**
*
*/
private static void testReverse() {
int x=10,y=20,temp;
temp = x;
x = y;
y = temp;
System.out.println(x+"--"+y);
}
/**
*
* @param x
* @return
*/
private static int fb(int x){
if(x==1 || x==2) return 1;
else
return fb(x-1)+fb(x-2);
}
public static void main(String[] args) throws NoSuchFieldException {
Listed<String> linked = new Listed<String>();
for(int i=0;i<9;i++){
linked.add(Integer.toString(i));
}
String s1=linked.toString();
// System.out.println(" :"+s1+" "+linked.size());
// testRemoveAfter();
// testInsertAfter();
testMax();
testMaxForRecursion();
}
public static void testMaxForRecursion(){
Listed<Integer> listed = new Listed<Integer>(new Integer[] { 2000, 6, 8, 13000, 1290 });
int i = listed.maxForRecursion(listed.node(0));
System.out.println(i);
}
public static void testMax(){
Listed<Integer> listed = new Listed<Integer>(new Integer[] { 2000, 6, 8, 13000, 1290 });
int i = listed.max(listed.node(0));
System.out.println(i);
}
public static void testRemoveAfter(){
Listed<Integer> lst = new Listed<Integer>(new Integer[] { 2, 6, 8, 10, 12 });
lst.removeAfter(lst.node(2));
System.out.println("---");
System.out.println(lst.toString());
}
public static void testInsertAfter(){
Listed<Integer> listed = new Listed<Integer>(new Integer[] { 2, 6, 8, 10, 12 });
listed.insertAfter(listed.node(2), listed.createNode(7));
System.out.println(listed.toString());
}
}