{"id":536,"date":"2024-11-08T14:48:24","date_gmt":"2024-11-08T06:48:24","guid":{"rendered":"https:\/\/eve2333.top\/?p=536"},"modified":"2024-11-08T14:49:17","modified_gmt":"2024-11-08T06:49:17","slug":"cs61b%e5%ad%a6%e4%b9%a0-part3","status":"publish","type":"post","link":"https:\/\/eve2333.top\/?p=536","title":{"rendered":"CS61b\u5b66\u4e60-part3"},"content":{"rendered":"\n

\u5982\u679c\u4f60\u6709\u8bb8\u591alist\uff0c\u8fd9\u91cc\u5c06\u4f1a\u662f\u5927\u91cf\u7684\u65f6\u95f4\uff0c\u6211\u6307\u7684\u662f\u5bf9\u4e8e\u5355\u5411\u94fe\u8868\u67e5\u627e\u65f6\u95f4\u590d\u6742\u5ea6O(N)\u76f8\u5bf9\u4e8e\u6570\u7ec4O(1)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4f1a\u6162\u4e00\u4e9b<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n

 \u6240\u4ee5\u8fd9\u7a76\u7adf\u662f\u987a\u5e8f\u8868\u7684\u7f16\u5199<\/strong>\u8fd8\u662f\u94fe\u8868\u7684\u6539\u8fdb?<\/p>\n\n\n\n

IntList<\/p>\n\n\n\n

public class IntList {\n\tpublic int first;\n\tpublic IntList rest;\n\n\tpublic IntList(int f, IntList r) {\n\t\tfirst = f;\n\t\trest = r;\n\t}\n\n\t\/** Return the size of the list using... recursion! *\/\n\tpublic int size() {\n\t\tif (this.rest == null) {\/* base case *\/\n\t\t\treturn 1;\n\t\t}\n\t\treturn 1 + this.rest.size();\n\t}\n\n\t\/** Return the size of the list using no recursion! *\/\n\tpublic int iterativeSize() {\n\t\t\/* You can not assign \"this\" in Java*\/\n\t\tIntList p = this;\n\t\tint totalSize = 0;\n\t\twhile (p != null) {\n\t\t\ttotalSize += 1;\n\t\t\tp = p.rest;\n\t\t}\n\t\treturn totalSize;\n\t}\n\n\t\/** Returns the ith value in this list.*\/\n\tpublic int get(int i) {\n\t\tIntList p = this;\n\t\tint nth = 0;\n\t\tif (i >= p.size()) {\n\t\t\treturn -1;\n\t\t}\n\t\twhile (nth != i) {\n\t\t\tp = p.rest;\n\t\t\tnth += 1;\n\t\t}\n\t\treturn p.first;\n\t}\n\n\tpublic static void main(String[] args) {\n\t\tIntList L = new IntList(15, null);\n\t\tL = new IntList(10, L);\n\t\tL = new IntList(5, L);\n\t\tSystem.out.println(L.size());\n\t\tSystem.out.println(L.iterativeSize());\n\t\tSystem.out.println(L.get(2));\n\t}\n} <\/code><\/pre>\n\n\n\n
SLList <\/p>\n\n\n\n
\/** An SLList is a list of integers, which hides the terrible truth\n   * of the nakedness within. *\/\npublic class SLList {\t\n\tprivate static class IntNode {\n\t\tpublic int item;\n\t\tpublic IntNode next;\n\n\t\tpublic IntNode(int i, IntNode n) {\n\t\t\titem = i;\n\t\t\tnext = n;\n\t\t\tSystem.out.println(size);\n\t\t}\n\t} \n\n\t\/* The first item (if it exists) is at sentinel.next. *\/\n\tprivate IntNode sentinel;\n\tprivate int size;\n\n\tprivate static void lectureQuestion() {\n\t\tSLList L = new SLList();\n\t\tIntNode n = IntNode(5, null);\n\t}\n\n\t\/** Creates an empty SLList. *\/\n\tpublic SLList() {\n\t\tsentinel = new IntNode(63, null);\n\t\tsize = 0;\n\t}\n\n\tpublic SLList(int x) {\n\t\tsentinel = new IntNode(63, null);\n\t\tsentinel.next = new IntNode(x, null);\n\t\tsize = 1;\n\t}\n\n \t\/** Adds x to the front of the list. *\/\n \tpublic void addFirst(int x) {\n \t\tsentinel.next = new IntNode(x, sentinel.next);\n \t\tsize = size + 1;\n \t}\n\n \t\/** Returns the first item in the list. *\/\n \tpublic int getFirst() {\n \t\treturn sentinel.next.item;\n \t}\n\n \t\/** Adds x to the end of the list. *\/\n \tpublic void addLast(int x) {\n \t\tsize = size + 1; \t\t\n\n \t\tIntNode p = sentinel;\n\n \t\t\/* Advance p to the end of the list. *\/\n \t\twhile (p.next != null) {\n \t\t\tp = p.next;\n \t\t}\n\n \t\tp.next = new IntNode(x, null);\n \t}\n \t\n \t\/** Returns the size of the list. *\/\n \tpublic int size() {\n \t\treturn size;\n \t}\n\n\tpublic static void main(String[] args) {\n \t\t\/* Creates a list of one integer, namely 10 *\/\n \t\tSLList L = new SLList();\n \t\tL.addLast(20);\n \t\tSystem.out.println(L.size());\n \t}\n}<\/code><\/pre>\n\n\n\n
3 DLList(LinkedListDeque\u94fe\u8868\u53cc\u8fb9\u961f\u5217)<\/p>\n\n\n\n
\n\/**\n * Created by JianjunChen on 08\/16\/2020\n * This is a Linked List Doubly ended queue Data Structure using Lists!\n * @Rule The amount of memory that your program uses at any given time must be\n * proportional to the number of items.\n * @Rule Do not maintain references to items that are no longer in the deque.\n * @Rule Implement all the methods listed above in \u201cThe Deque API\u201d section.\n *\/\n\n\npublic class LinkedListDeque<T> {\n    \/**LinkedNode Nested Class*\/\n    private class LinkedNode {\n        private LinkedNode prev; \/* Doubly Linked List*\/\n        private T item;\n        private LinkedNode next;\n\n        public LinkedNode(LinkedNode p, T i, LinkedNode n) {\n            prev = p;\n            item = i;\n            next = n;\n        }\n    }\n\n    private LinkedNode sentinel;\n    \/\/private LinkedNode last;\n    private int size;\n\n    \/** Constructor of LinkedListDeque *\/\n    public LinkedListDeque() {\n        sentinel = new LinkedNode(null, null, null);\n        sentinel.prev = sentinel;\n        sentinel.next = sentinel;\n        \/\/last = sentinel;\n        size = 0;\n    }\n\n    \/** Adds an item of type T to the front of the deque.*\/\n    public void addFirst(T item) {\n        LinkedNode first = new LinkedNode(sentinel, item, sentinel.next);\n        \/* Note that the order cannot be reversed since if we firstly write\n         * sentinel.next = first; the sentinel.next.prev will equal to first.prev!!!!*\/\n        sentinel.next.prev = first;\n        sentinel.next = first;\n        size += 1;\n    }\n\n    \/** Adds an item of type T to the back of the deque. *\/\n    public void addLast(T item) {\n        LinkedNode last = new LinkedNode(sentinel.prev, item, sentinel);\n        \/* Note that the order cannot be reversed!!! *\/\n        sentinel.prev.next = last;\n        sentinel.prev = last;\n        size += 1;\n    }\n\n    \/** Returns true if deque is empty, false otherwise. *\/\n    public boolean isEmpty() {\n        if (sentinel.next == sentinel) {\n            return true;\n        }\n        return false;\n    }\n\n    \/** Returns the number of items in the deque. *\/\n    public int size() {\n        return size;\n    }\n\n    \/* Prints the items in the deque from first to last, separated by a space. *\/\n    public void printDeque() {\n        LinkedNode p = sentinel;\n        while (p.next != sentinel) {\n            System.out.print(p.next.item + \" \");\n            p = p.next;\n        }\n    }\n\n    \/** Removes and returns the item at the front of the deque.\n    If no such item exists, returns null.*\/\n    public T removeFirst() {\n        if (isEmpty()) {\n            return null;\n        }\n\n        T firstItem = sentinel.next.item;\n        \/* Note that the order cannot be reversed!!!*\/\n        sentinel.next.next.prev = sentinel;\n        sentinel.next = sentinel.next.next;\n\n        size -= 1;\n        return firstItem;\n    }\n\n    \/** Removes and returns the item at the back of the deque.\n     * If no such item exists, returns null. *\/\n    public T removeLast() {\n        if (isEmpty()) {\n            return null;\n        }\n\n        T lastItem = sentinel.prev.item;\n        \/* Note that the order cannot be reversed!!! *\/\n        sentinel.prev.prev.next = sentinel;\n        sentinel.prev = sentinel.prev.prev;\n\n        size -= 1;\n        return lastItem;\n\n    }\n\n    \/** Gets the item at the given index, where 0 is the front, 1 is the next item,\n    * and so forth. If no such item exists, returns null. Must not alter the deque! *\/\n    public T get(int index) {\n        if (index > size - 1) {\n            return null;\n        }\n\n        LinkedNode p = sentinel.next;\n        int i = 0;\n        while (i != index) {\n            p = p.next;\n            i += 1;\n        }\n        return p.item;\n    }\n\n    \/** Helper method for getRecursive *\/\n    private T getRecursiveHelper(LinkedNode currentNode, int index) {\n        if (index == 0) {\n            return currentNode.item;\n        }\n        return getRecursiveHelper(currentNode.next, index - 1);\n    }\n\n    \/** Same as get but using recursion!! *\/\n    public T getRecursive(int index) {\n        if (index > size - 1) {\n            return null;\n        }\n\n        return getRecursiveHelper(sentinel.next, index);\n    }\n}<\/code><\/pre>\n\n\n\n
4 AList(ArrayDeque\u6570\u7ec4\u53cc\u8fb9\u961f\u5217) <\/p>\n\n\n\n
\n\/**\n * Created by JianjunChen on 08\/18\/2020\n * This is a Array based Doubly Ended Queue Data Structure!!\n * @Rule The starting size of your array should be 8.\n * @Rule Implement all the methods listed above in \u201cThe Deque API\u201d section.\n * @Rule The amount of memory that at any given time must be proportional to the number\n * of items. For arrays of length 16 or more, your usage factor should always be at least 25%.\n *\n *\/\n\n\n\/\/ Circular ArrayDeque\npublic class ArrayDeque<T> {\n    private int initialCapacity = 8; \/\/initial array capacity\n    private int capacity;  \/\/current array capacity\n    private int eFactor = 2; \/\/expanding factor\n    private double usageFactor;\n    private int mCapacity = 16; \/\/ The minimum capacity for contraction\n    private double mRatio = 0.25; \/\/The minimum usage ratio before contraction\n    private int cFactor = 2; \/\/contraction factor\n    private T[] items;\n    private int size;\n    private int nextFirst;\n    private int nextLast;\n\n    public ArrayDeque() {\n        capacity = initialCapacity;\n        items = (T[]) new Object[initialCapacity];\n        size = 0;\n        nextFirst = 4;\n        nextLast = 5;\n    }\n\n    \/** Finding the next nextFirst and nextLast index in circle ArrayDeque. *\/\n    private int oneMinus(int index) {\n        if (index == 0) { \/\/ whether the index is out of bounds!\n            index = capacity - 1;\n        } else {\n            index -= 1;\n        }\n        return index;\n    }\n\n    private int onePlus(int index) {\n        if (index == capacity - 1) { \/\/ whether the index is out of bounds!\n            index = 0;\n        } else {\n            index += 1;\n        }\n        return index;\n    }\n\n    \/** Resize the original array to a new array with given capacity. *\/\n    private void resize(int newCapacity) {\n        T[] a = (T[]) new Object[newCapacity];\n\n        int currentFirst = onePlus(nextFirst);\n        int currentLast = oneMinus(nextLast);\n\n        if (currentFirst < currentLast) {\n            int length = currentLast - currentFirst + 1;\n            System.arraycopy(items, currentFirst, a, 0, length);\n            nextFirst = newCapacity - 1;\n            nextLast = length;\n        } else {\n            int firstRightCount = capacity - currentFirst;\n            int firstLeftCount = capacity - firstRightCount;\n            System.arraycopy(items, currentFirst, a, 0, firstRightCount);\n            System.arraycopy(items, 0, a, firstRightCount, firstLeftCount);\n\n            nextFirst = newCapacity - 1;\n            nextLast = capacity;\n        }\n\n        capacity = newCapacity;\n        items = a;\n\n    }\n\n    \/** Adds an item of type T to the front of the deque.\n     * @Rule Must take constant time, except during resizing operations.\n     *\/\n    public void addFirst(T item) {\n        items[nextFirst] = item;\n        size += 1;\n        nextFirst = oneMinus(nextFirst);\n\n        \/\/The array is full, needed resize operation!\n        if (size == capacity) {\n            resize(size * eFactor);\n        }\n    }\n\n    \/** Adds an item of type T to the back of the deque.\n     * @Rule Must take constant time, except during resizing operations.\n     *\/\n    public void addLast(T item) {\n        items[nextLast] = item;\n        size += 1;\n        nextLast = onePlus(nextLast);\n\n        \/\/The array is full, needed resize operation!\n        if (size == capacity) {\n            resize(size * eFactor);\/*\u6b64\u5904\u539f\u4e3a+1*\/\n        }\n    }\n\n    \/** Returns true if deque is empty, false otherwise. *\/\n    public boolean isEmpty() {\n        if (size == 0) {\n            return true;\n        }\n        return false;\n    }\n\n    \/** Returns the number of items in the deque. *\/\n    public int size() {\n        return size;\n    }\n\n    \/** Prints the items in the deque from first to last, separated by a space. *\/\n    public void printDeque() {\n        if (isEmpty()) {\n            return;\n        }\n        int index = onePlus(nextFirst);\n        while (index != nextLast) {\n            System.out.print(items[index] + \" \");\n            index = onePlus(index);\n        }\n    }\n\n    private void contract() {\n        usageFactor = (double) size \/ capacity;\n        if (usageFactor <= mRatio && capacity >= mCapacity) {\n            int newCapacity = capacity \/ cFactor;\n            resize(newCapacity);\n        }\n    }\n\n    \/** Removes and returns the item at the back of the deque. If no such item exists, returns null.\n     * @Rule must take constant time, except during resizing operations.\n     *\/\n    public T removeFirst() {\n        if (isEmpty()) {\n            return null;\n        }\n\n        int currentFirst = onePlus(nextFirst);\n        T currentFirstItem = items[currentFirst];\n        nextFirst = currentFirst;\n        items[nextFirst] = null;\n        size -= 1;\n\n        contract();\n\n        return currentFirstItem;\n    }\n\n    \/** Removes and returns the item at the back of the deque. If no such item\n     * exists, returns null..\n     * @Rule must take constant time, except during resizing operations.\n     *\/\n    public T removeLast() {\n        if (isEmpty()) {\n            return null;\n        }\n\n        int currentLast = oneMinus(nextLast);\n        T currentLastItem = items[currentLast];\n        nextLast = currentLast;\n        items[nextLast] = null;\n        size -= 1;\n\n        return currentLastItem;\n    }\n\n    \/**\n     * Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth.\n     * If no such item exists, returns null. Must not alter the deque!\n     * @Rule must take constant time.\n     *\/\n    public T get(int index) {\n        if (index >= size) {\n            return null;\n        }\n\n        int indexFromFirst = nextFirst + 1 + index;\n        if (indexFromFirst >= capacity) {\n            indexFromFirst -= capacity;\n        }\n\n        return items[indexFromFirst];\n    }\n}<\/code><\/pre>\n\n\n\n
\"\"<\/figure>\n\n\n\n
C\u3001203<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
100+101+\u2026.+999+1000=495550\uff0c\u5927\u6982500000<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u8fd9\u5f20\u56fe\u7247\u5c55\u793aSLList\u4ee3\u8868Single-Linked List\uff08\u5355\u5411\u94fe\u8868\uff09\uff0c\u800cALList\u4ee3\u8868Array-Backed List\uff08\u6570\u7ec4\u652f\u6301\u94fe\u8868\uff09\u7684\u533a\u522b\uff0c\u5373O(N)\u548cO(NlogN)\u5b58\u7591<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\u4e3a\u4e86\u8ba9alist\u66f4\u52a0\u901a\u7528\u5b9e\u73b0\u4e86\u5982\u4e0b\u53d8\u5316\u00a0\u5de6\u8fb9\u662f\u539f\u6765\u7684\uff0c\u53f3\u8fb9\u662f\u53d8\u5316\u540e<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\/* Array based list.\n@author Josh Hug\n *\/\n\/\/        0  1  2  3  4  5  6  7\n\/\/items:[ 6  9  -1 2  0  0  0  0]\n\/\/size:5\n\/*Invariants:\n    addlast:The next item we want to add,will go into position size\n    getlast:The item we want to return is in position size -1\n    size:The number of items in the list should be size.\n*\/\npublic class AList<Item> {\n    private Item[] items;\n    private int size;\n\n    \/**\n     * Creates an empty list.\n     *\/\n    public AList() {\n        items = (Item[]) new Object[100];\n        size = 0;\n    }\n\n    \/*Resizes the underlying array to the target capacity.*\/\n    private void resize(int capacity) {\n        Item[] a = (Item[]) new object[capacity];\n        System.arraycopy(items, 0, a, 0, size);\n        items = a;\n    }\n\n    \/*Inserts x into the back of the list.*\/\n    public void addLast(Item x) {\n        if (size == items.length) {\n            resize(size + 1);\n        }\n        items[size] = x;\n        size = size + 1;\n    }\n\n    \/*Returns the item from the back of the List.*\/\n    public Item getlast() {\n        return items[size - 1];\n    }\n\n    \/*Gets the ith item in the list (0 is the front).*\/\n    public Item get(int i) {\n        return items[i];\n    }\n\n    \/*Returns the number of items in the list.*\/\n    public int size() {\n        return size;\n    }\n\n    \/*Deletes item from back of the list and returns deleted item.*\/\n    public Item removeLast() {\n        Item x = getLast();\n        items[size - 1] = null;\n        size = size - 1;\n        return x;\n    }\n}<\/code><\/pre>\n\n\n\n
\"\"<\/figure>\n","protected":false},"excerpt":{"rendered":"
\u5982\u679c\u4f60\u6709\u8bb8\u591alist\uff0c\u8fd9\u91cc\u5c06\u4f1a\u662f\u5927\u91cf\u7684\u65f6\u95f4\uff0c\u6211\u6307\u7684\u662f\u5bf9\u4e8e\u5355\u5411\u94fe\u8868\u67e5\u627e\u65f6\u95f4\u590d\u6742\u5ea6O(N)\u76f8\u5bf9\u4e8e\u6570\u7ec4O(1)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4f1a\u6162\u4e00\u4e9b &n …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"emotion":"","emotion_color":"","title_style":"","license":"","footnotes":""},"categories":[2],"tags":[17,18],"class_list":["post-536","post","type-post","status-publish","format-standard","hentry","category-2","tag-17","tag-18"],"_links":{"self":[{"href":"https:\/\/eve2333.top\/index.php?rest_route=\/wp\/v2\/posts\/536","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eve2333.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eve2333.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eve2333.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eve2333.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=536"}],"version-history":[{"count":0,"href":"https:\/\/eve2333.top\/index.php?rest_route=\/wp\/v2\/posts\/536\/revisions"}],"wp:attachment":[{"href":"https:\/\/eve2333.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=536"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eve2333.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=536"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eve2333.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=536"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}