Today we will start with our first data type - Arrays.
I often see this question, how to learn data structures, my answer is to figure out the concrete data structure corresponding to the abstract data type ADT, put aside the language level comes with the data type, and then from the beginning of their own implementation of the first time.
In fact, the data structure is not much more complex, the data structure is the sum of people's experience, according to its specific abstraction of the definition of the name, in the final analysis is that we define, you call it an array it is an array, call it a number of sets that it is a number of sets, all we only need to know the definition of a data structure, and can realize the definition of their own, then it can be said that you have completely mastered the data structure.
01Definitions
What is an array? An array is a sequence of elements of the same type.An array is a linear data structure that uses a contiguous set of memory space to store a set of elements of the same type.
An array of type int of length 10 is stored in memory similar to the following layout.
The linear data structure of the array is reflected in the data one next to another, continuous memory space is reflected in the middle of the storage address [1000-1039] this space is a whole without gaps, the same element means that all the space is used to store the int type.
Thus we can summarize the following properties of arrays:
-
The length is fixed because the size of the memory cannot be changed directly once it is allocated.
-
Memory space addresses are contiguous.
-
The element types are the same and can be either value or reference types.
-
Indexes generally start at 0.
-
Random access, the ability to access elements directly by index, i.e. subscript.
02Realization
1. Definition of ADT
Abstract Data Type (Abstract Data Type, or ADT), is a data abstraction method for describing the logical characteristics and operations of data objects, usually using ternary representation, i.e., ADT = (D, S,P), with the following specific meanings:
D（Data Objects）: A data object that defines collections and properties of data.
S（Structure）: A set of relationships between data objects that describes the structure and constraints between elements within a data object.
P（Primitive Operations）: A set of basic operations on data objects, such as insertion, deletion, modification, lookup, traversal, and so on.
If we want to implement the array should first define the array, the following we use ADT to define the array.
ADT Array{
Data object: D is a finite, non-empty sequence of integers, D = {a1, a2, ... , an}, where ai denotes the ith element in the sequence and n is the length of the sequence.
Data Relationships: The elements in D are organized by their indexes (positions), which are integers from 0 to n-1.
Basic operations: [
Init(n) : Initialize an array of length n, with all elements initialized to the element's corresponding type default value.
Length: return the length of the array.
Get(i): return the element whose index is i, if i is invalid, then report an error.
Set(i,v): set the value of the element with index i to v. If i is invalid, an error is reported.
Insert(i,v): insert v at index i. If there is no element at i, insert v directly; if there is an element at i and there is a position after it that has not yet stored an element, move back one position from the element before the unstored element position until the position i is vacated, and then insert v. If there is an element at i and there is an element in all the positions after it, then an error is reported; If i is invalid, an error is reported.
Remove(i): removes the element indexed at position i and moves all subsequent elements one position forward, always keeping the elements contiguous and removing space to the end of the array and inaccessible.
]
}
With the array ADT defined, we can now start implementing an int type array type ourselves.
2. Define the class
If we were to implement the above definition of arrays, what fields would be needed to give support to these functions?
Because we need to manage memory directly, we need a pointer field to manage memory;
Because we need to get the array length directly, we need a stored array length field;
So our class initially looks like this:
public class MyselfArray
{
// Request a pointer to the start of memory
private IntPtr _pointer; //The length of the array.
// length of the array
private int _length; }
}
3、Initialization Init
First think about how we normally use arrays.
int[] array = new int[5]
We usually write a simple line of code that defines an array of a specified length, but it does a lot behind the scenes. new int[5] is equivalent to allocating a memory space capable of storing five integers, all initialized to zero.
Then we are now in the realization of the process itself. We first need to apply for the space that can store 5 integers, and then initialize each element value, the specific implementation code is as follows:
// Initialize the array to the specified length, and elements set the default value of 0
public MyselfArray Init(int capacity)
{
//Initialize the array length to capacity
_length = capacity; //Allocate the specified number of bytes of memory space.
// Allocate the specified number of bytes of memory space
_pointer = (capacity * sizeof(int)); //Initialize the array elements to capacity.
//Initialize the array elements
for (int i = 0; i < _length; i++)
{
//initialize each element to 0
Marshal.WriteInt32(_pointer + i * sizeof(int), 0);
}
// Return the array
return this; }
}
The following two points need to be clarified separately.
How to calculate the number of bytes to be allocated? Because all the elements in the array are of the same type, here we are using the int type as an example, so the space requested is the size of an int type multiplied by the length of the array i.e. CAPACITY * SIZE OF (int).
How to calculate the location of each element? Let's review the diagram again, since each element type is the same, and therefore each element occupies the same amount of space, we can calculate the memory address of the specified element by using the following addressing company.
a[i] memory address = a[0] memory address + i * type size
IntPtr _pointer in our code is to indicate the allocation of the first address of the memory block, that is, corresponding to the memory address as shown in Figure a [0], the type size can be obtained by sizeof (int), so we can be the first address pointer and the specified element index to locate the specific element, and then directly to the memory operation assignment.
Here's another interesting tidbit, why do most language indexes start at 0? Imagine if indexing started at 1, the addressing formula above would be:
a[i] memory address = a[0] memory address + (i-1) * type size
This leads to each access to the array elements have to be an additional step to subtract 1 operation, and corresponds to the CPU is an additional subtraction instruction, so the index from 0 to start a large part of the reason is so that you can optimize performance and simplify the calculation.
4, the length of the array Length
It's easier to just return the array length as a private field.
//Array length
public int Length
{
get
{
return _length;
}
}
5, according to the index to get the element value Get
In the acquisition of elements, we first need to check whether the index is valid, first of all, the index is less than 0 is certainly meaningless; secondly, greater than the largest element of the array index is also meaningless, the specific code is as follows:
//According to the index of the elements
public int Get(int index)
{
//Index is less than 0 or index is greater than the length of the array - 1, then an error is reported
if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException(); //Read the value of the element with the specified index.
// Read the value of the specified index element
return Marshal.ReadInt32(_pointer + index * sizeof(int)); }
}
6, according to the index to set the element value Set
Similarly the index validity needs to be checked when setting the element value.
//Set the elements according to the index
public void Set(int index, int value)
{
//Index is less than 0 or index is greater than the length of the array - 1, then an error is reported
if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException();
// Set the element value according to the index
Marshal.WriteInt32(_pointer + index * sizeof(int), value);
}
7, according to the index insert element Insert
This piece of logic is currently one of the most complex, first of all, the need to check the validity of the index, and secondly, the need to determine whether the current index position has a value, no value directly into the value of the value of continue to check whether there is a vacant space, no vacant space directly to report an error, there is a vacant space is to move the elements of the index to vacate the position for the insertion of a new element. Specific realization of the code is as follows:
/ / Insert elements according to the index
public void Insert(int index, int value)
{
//Index is less than 0 or index is greater than the length of the array - 1, then an error is reported
if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException(); //Get the value at index.
// Get the value at index
var v = Get(index);
//If there is no value at the index
if (v == 0)
{
//Insert the new element directly at the index and return it
Set(index, value);
return.
}
// Define the null position index
var nullIndex = -1;
//Check if there is a null position after inserting the position
for (int i = index + 1; i < _length; i++)
{
// check if there is empty space after insertion
if (Get(i) == 0)
{
//record the index at the null position and end the check
nullIndex = i.
break;
}
}
// If no null position is found, report an error
if (nullIndex == -1)
{
throw new InvalidOperationException("There are no empty spaces available for insertion.") ;
}
// Move back one bit from the insertion position to the element before the null position.
for (int i = nullIndex; i > index; i--)
{
Set(i, Get(i - 1)); }
}
// Insert a new element at the specified index
Set(index, value);
}
Note: Here the value of 0 to determine whether the empty space, because the array initialization is the default value of 0, so the use of 0 means that the empty space that has not been assigned, which is our own definition. In fact, may be 0 itself is meaningful, if you want to accurately determine whether there is empty space also need additional processing, here we are just to understand the core concepts of arrays and a simple demonstration, do not have to get entangled in this 0 judgment.
8, according to the index to remove the element Remove
The logic of this method is relatively simple, the first to verify the validity of the index, and then to remove the index position from the beginning of all the elements behind to move forward by one, the last one is changed to the default value of 0.
//Remove elements according to the index
public void Remove(int index)
{
//Index is less than 0 or index is greater than the length of the array - 1, then an error is reported
if (index < 0 || index > _length - 1) throw new IndexOutOfRangeException(); //The following elements (except the last one) are moved one place forward.
// move all subsequent elements (except the last one) forward one place
for (int i = index; i < _length - 1; i++)
{
Set(i, Get(i + 1)); }
}
// Set the last bit to the default value of 0
Set(_length - 1, 0); }/ The last bit is set to the default value 0.
}
9, release memory Dispose
Support for array types is basically complete, still missing the last key step, because the memory is our direct application, so we need to release after use, so our class needs to implement the IDisposable interface, and implement the Dispose method, the specific method is as follows:
public void Dispose()
{
if (_pointer != )
{
(_pointer);
_pointer = ;
}
}
Since then we've had a big success with array types.
Through the above method to achieve we can also find that the insertion and deletion of elements is very cumbersome, especially in some special cases how to deal with different definitions is a different realization. For example, the above insertion of elements, insertion of the back if there are more than one empty space how to do? Is the back of all the elements are moved back one, or only used to the first empty space to move back one? If all move back one bit, then if the last bit is thrown away directly or report an error to prevent the operation?
And when it comes to moving elements, there are performance issues involved, so like C# language arrays themselves do not have insertion and deletion methods. Here we define the array in this way, and to implement these methods, mainly to learn the data structure.
At the same time or that data structure is ultimately our human definition out, we define there is, how we define then this data structure is what it looks like, so the data structure is not as difficult as you like, so difficult to understand. As long as the key elements of understanding mastered you will be.
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner