4. Data Structure
4.1 Array
4.1.1 Basic Concept
Arrays are objects in Java, so they need to instantiate before using it. The elements in the array can be basic elements, or objects, but the type of elements in the same array must be the same.
Objects stored in arrays are not object itself, but references to objects.
4.1.2 Array Statement and Institutionalization
(1) String Difwords []; Point Hits [];
(2) String [] DifWords []; Point [] Hits; often used for the return type of the method;
(3) String [] names = new string [10]; int [] temps = new int [10];
(4) String [] names = {"jalapeno", "anaheim", "serrano"}
(5) Int coords [] [] = new int [12] [12];
4.1.3 Attributes and methods of arrays
Array is an object, because of its properties and methods, such as Length attributes, etc.
4.2 enumeration
ENUMERATION is an interface that provides some standard methods for accessing the elements, these methods are:
(1) HasmoreElement (): Judging whether there is other elements
(2) NEXTELEMENT (): Returns the elements, if there is no elements, use this method to throw the Nosuchelementexception;
4.3 BitSet
BitSet is more convenient to represent a group of Boolean flags, which can be accessed, without using bit operators:
BitSet Bits = New BitSet (4);
The bit set of the length is 4 Bit, which we can use at least the following methods to operate these BIT bits:
(1) Bits.Set (INDEX): Set the IdEX bit to 1;
(2) Bits.clear (INDEX): Set the INDEX bit to 0;
(3) Bits.get (INDEX): Returns the value of the INDEX bit;
(4) Bits.Size (): Used to return the length of the bit set;
(5) XOR (BitSet SET): Performs an XOR operation with the specified bit set;
(6) There are other operations to see the java.util package
4.4 VECTOR
Vector is similar to Array, but Array's length cannot be automatically increased, but the length of the Vector can be automatically increased. When the VECTOR length is not enough, it will automatically grow, and it can specify the length of each automatic growth, such as:
Vector v = new vector (20,5);
Represents a new VECTOR object, which can accommodate 20 elements, if the number of elements exceeds 20, increase the capacity of 5 elements each time, that is, the first growth rate of 25, second The time growth is changed at 30.
See java.util package in the method in the vector.
4.5 StackStack is a typical data structure that adopts advanced principles. It has several important ways:
(1) POP;
(2) Push (Object);
(3) EMPTY (): Empty
(4) Peek (): View the top elements of the stack, but do not put this element to the stack;
(5) Search (Object): Find the location of the specified element;
4.6 Dictionary
Dictionary is an abstract class that defines the basic Key-mapped data structure. HashTable, etc. inherited from this abstract class. Vector can also access elements via Key (index), but the type of key in the vector is special, default. KEY in Dictionary can be customized. All methods in the Dictionary class are abstract, which indicates that these methods need to be derived to implement, these abstract methods are as follows:
(1) PUT (Object, Object): such as PUT ("Small", New Rectangle (0, 0, 5, 5));
(2) GET (Object): such as get ("small");
(3) Remove (Object): such as Remove ("small");
(4) size ();
(5) ISEMPTY ();
(6) Keys (): such as Enumeration Keys = Dict.keys ()
(7) Elements (): such as Enumeration Elements = Dict.Elements ()
4.7 HashTable
Hashtable is inherited from Dictionary, which implements all methods of the parent class, and implements the serializable interface, so it is often used to serve the data between the client and the server, that is, serialization before passing, re-objects after receiving .
HashTable has the following constructor:
(1) Hashtable (): Perform HashTable (11, 0.75F);
(2) Hashtable (int): Perform HashTable (int, 0.75f);
(3) Hashtable (int Capicility, Float Factor);
(4) Hashtable (Map T): Perform HashTable (Math.max (2 * T.SIZE (), 11), 0.75F); PUTALL (T)
Here, it will be described here that the parameters in the HashTable (int Capicility, Float Factor) are used to initiate the size of the HashTable, t = capiCILITY * FACTOR determines the HashTable He Value Rehash, if the entry in the HashTable exceeds T if HashTable It is necessary to rehash, and rehash is to rebuild a 2 * Capicility's HashTable. Therefore, the value of Factor is 0.0 4.8 Double Link The above is some built-in data structures in Java. If the built-in data structure does not meet our needs, you can customize the data structure, here you will introduce the implementation of the bidirectional chain. To achieve a bidirectional chain, here you have used three classes: (1) LinkedListentry: Entries in the chain; (2) LinkedList: the main class of the chain; (3) LinkedListenumerator: Enumeration interface; 4.8.1 LINKEDLISTENTRY class Class LinkedListentry { Protected Object Val = NULL; Protected LinkedListentry Next = NULL; Protected LinkedListentry Prev = NULL; Public LinkedListentry (Object obj) { IF (Obj == Null) Throw new nullpointerserException (); VAL = OBJ; } } 4.8.2 LinkedListenceUmerator 1: Class LinkedListenumerator imports enumeration { 2: Protected LinkedListentry Pos; 3: 4: Public LinkedListenumerator (LinkedList List) { 5: pOS = list.start; 6:} 7: 8: public boolean hasmorelements () { 9: Return (POS! = NULL); 10:} 11: 12: Public Object nextElement () { 14: IF (POS == NULL) 15: throw new nosuchelementexception (); 18: LinkedListentry TMP = POS; 19: POS = pos. 20: Return Tmp.Val; twenty one: } twenty two: } 4.8.3 LinkedList Members of variables in linkedList: Protected LinkedListentry Start = NULL; Protected LinkedListentry End = NULL; Protected int namelements; LinkedList is mainly managed for LinkedListentry, which has the following features: (1) Increase the designated entry; (2) Insert the specified entry; (3) Delete the specified entry; (4) Find the specified entry according to the object; (5) Find according to position; (6) Return to Enumeration object; (7) Judging whether there is an entry; (8) The determination chain is empty, etc .; To fully implement the above functions, there is a lot of code, of course, these codes are relatively simple, so these only give some code as the origin. (1) Increase the specified entry AddElement: 1: Public void addelement (Object obj) { 3: IF (Obj == NULL) 4: throw new nullpointerException (); 5: 7: LinkedListentry NewElement = New LinkedListentry (OBJ); 8: NumeLements ; 9: 11: if (start == null) { 12: start = newElement; 13: End = newElement; 14:} 15: Else { 16: end.next = newElement; 17: NewElement.prev = End; 18: end = newElement; 19:} 20:} (2) Insert the specified entry insertelementat 1: Public void insertelementat (Object Obj, Object POS) { 3: if (obj == null || POS == NULL) 4: throw new nullpointerException (); 5: 7: LinkedListentry Posentry = Find (POS); 8: if (posentry == null) 9: throw new nullpointerserException (); 10: 12: LinkedListentry News = New LinkedListentry (OBJ); 13: NumeLements ; 14: 16: NewElement.next = Posentry; 17: NewElement.prev = posentry.prev; 18: IF (Posentry == Start) 19: start = newelement; 20: Else 21: Posentry.Prev.next = NewElement; 22: posentry.prev = newElement; twenty three: } (3) Find the specified entry according to the object Private LinkedListentry Find (Object Obj) { IF (iSempty () || OBJ == NULL) Return NULL; LinkedListentry TMP = Start; While (tmp! = null) { IF (tmp.val == obj) Return TMP; TMP = tmp.next; } Return NULL; } (4) Judgment whether to include an entry Public Boolean Contains (Object Obj) { Return (Find (Obj)! = null; } (5) Decision chain is empty Public Boolean ISempty () { Return (Start == NULL); } (6) Return to ENUMERATION object Public Enumeration Elements () { Return New LinkedListence (this); }
