第02章 线性表(java版)

  • Published on
    27-Jul-2015

  • View
    391

  • Download
    4

Embed Size (px)

Transcript

<p> 1. 2 2.1 2.2 2.3 2.4 2. MyEclipse 3. Java 3 2.1 LinearList=(a0 a1 an 1) public interface LList { // T boolean isEmpty(); // int length(); // T get(int i); // i i0 void set(int i, T x); // i x void insert(int i, T x); // x i void append(T x); // x T remove(int i); // i void removeAll(); // T search(T key); // key } public class SeqList implements LList // 4. Java 3 2.2 1. ciaLocaLoc i += )()( 0 5. Java 3 public class SeqList implements LList { // protected Object[] element; // protected int len; // } 2. 6. Java 3 4. 3. 7. Java 3 2.1 8. Java 3 get() set() O(1) 5. == == + + = + = n i n i i nO nnn n in n pin 00 )( 22 )1( 1 1 )( 1 1 )( 9. Java 3 6. ( ) 1 public SeqList(SeqList list)// { this.element = list.element; // 10. Java 3 SeqList listb = new SeqList(lista); 11. Java 3 2 12. Java 3 7. 13. Java 3 2.3 2.3.1 2.3.2 2.3.3 14. Java 3 2.3.1 15. Java 3 1. public class Node // { public T data; // public Node next; // } Node p,q; p=new Node("A", null ); q=new Node("B", null ); 2.3.2 16. Java 3 2. Node p = head; while (p!=null) {System.out.print(p.data.toString()+" "); // p p = p.next; } 17. Java 3 p=p.next p.next=p 18. Java 3 3. 1 / if (head == null) // head = new Node(x, null); else // { Node q = new Node(x, null); q.next = head; head = q; } head = new Node(x, head); 19. Java 3 2 / Node q = new Node(x, null); q.next = p.next;//q p p.next = q; //q p p.next = new Node(x, p.next); 20. Java 3 Node q = new Node(x, null); p.next = q; q.next = p.next; 21. Java 3 4. a. head = head.next; b. / if (p.next!=null) p.next = p.next.next; 22. Java 3 5. 23. Java 3 2.2 24. Java 3 6. 1. isEmpty() O(1) 2. length() O(n) 3. get(i) set(i) O(n) 4. insert(i,x) remove(i) O(n) 25. Java 3 1. p q 2. p front 26. Java 3 7. public boolean append(T x) { return insert(this.length(), x); // } return insert(Integer.MAX_VALUE, x); // 27. Java 3 O(n) public String toString() { String str="("; if (this.length()!=0) { for(int i=0; i list) // { this.head = list.head; // } 31. Java 3 8. 32. Java 3 9. 33. Java 3 10. 34. Java 3 11. 35. Java 3 2.3.3 1. p = p.next.pred = p.pred.next 36. Java 3 2. (1) p x q = new DLinkNode(x, p.pred, p); p.pred.next = q; p.pred = q; 37. Java 3 p x q = new DLinkNode(x, p, p.next); // p.next==null if (p.next!=null) p.next.pred = q; // 38. Java 3 2 p.pred.next = p.next; // p.pred! =null if (p.next!=null) p.next.pred = p.pred; 39. Java 3 3. 40. Java 3 4. 41. Java 3 2.4 2.4.1 2.4.2 42. Java 3 2.4.1 = =++++= m i i i m mm xaxaxaxaaxA 0 2 210)( = =++++= n i i i n nn xbxbxbxbbxB 0 2 210)( = +=+ ),max( 0 )()()( nm i i iinm xbaxBxA 43. Java 3 1. 9742 7292)( xxxxxxAn ++= 44. Java 3 2. 9742 7292)( xxxxxxAn ++= 1 2 45. Java 3 3 Polynomial 46. Java 3 2.6 47. Java 3 48. Java 3 public boolean equals(Object obj) // { return this==obj || obj instanceof Polynomial &amp;&amp; this.list.equals(((Polynomial)obj).list) ; 49. Java 3 2.4.2 1 TermXY 2 Polynomial 3 PolySLinkedList 3224 9263),( yxyyxxxyxP +++= 2156362),,( 43342352362310 +++++= yzzyxzyxzyxzyxzyxzyxP 50. Java 3 </p>