Let's first look at the linear table. The so-called sequential storage is implemented with "array", and linked storage is implemented using "linked list". The structure is roughly as follows:
array = [1,2,3,4,5]
list = (1)->(2)->(3)->(4)->(5)
and the tree structure, take the following binary tree for example:
b
/ \
a c
Sequential Storage needs to be implemented with three "arrays":
ele = ["a","b","c"]
left = [null,0,null]
right = [null,2,null]
you see:
the element of bit 0 is ele [0] is "a", the left node of bit 0 is position left [0] is null, and the position of right node right [0] is null The element of
1 bit memory is ele [1] is "b", and the left node position left [1] of bit 1 is 0. It is deduced that the element of left node of bit 1 is ele [left [1]] is ele [0], that is, "a". Similarly, the element of the right node of bit 1 is ele [right [1]] is ele [2], that is, "c". The element of
2 bit memory is ele [2] is "c", the left node position left [2] is null, and the right node position right [2] is null;
. This is a binary tree implemented by an array.
The binary tree implemented by the
linked list will not be expanded here.
as you can see, for linear tables that need to be searched, it is best to use arrays. After all, you can sort them once and then use binary search, while the sorting of linked lists is very troublesome and can only be searched from beginning to end.
for the tree structure that needs to be searched, it is generally stored in chain. after all, the tree structure (sort binary tree, balanced tree) can easily insert and delete data into it, and the insertion, deletion and search efficiency is all O (logN). Although the binary tree implemented by the array is the same, it is difficult to estimate how much space the three arrays need to open because they do not know the scale of the data at first.
need to pay attention to the array to achieve the linear table, insert, delete efficiency is very low O (N), so if you need efficient insert, delete, find data, you also need to learn balance tree knowledge, here will not expand.
Have I made myself clear about the above? I hope I can help you.
first of all, there are two types of data structures, one is logical, the other is physical.
there are three kinds of logic: one-to-one linear table, one-to-many tree, and many-to-many graph.
there are only two physical types, sequence, and chain. What is the logical structure of physics? That is, logically contiguous node addresses in memory are contiguous or discontiguous. Continuous storage is called sequential storage, and discontinuous storage is called chain storage.
after we know this premise, we will see that what we generally call a linear table only refers to one-to-one logically, which naturally can be physically continuous or discontinuous. A continuous table is generally array, and a discontinuous table is generally linked list.
when thinking about when to choose continuous or discontiguous storage, first of all, we need to know one thing: how do we usually access a piece of memory data?
obviously, we want to access a piece of data in memory, we need to find this piece of memory, and we need its address, whether contiguous or discontiguous.
so how do we access data with continuous memory? We first know the address of the first block of memory, the so-called first address, and then we need to know how far the other memory is from the first block of memory, that is, the offset, and then we add the first address to find this piece of memory.
then we want to access the address in a piece of continuous storage, we need the first address and offset, we can easily know the first address and offset, so we can access which block of continuous memory when and when, that is, the so-called random access.
and discontinuous memory? How do we access the address of a piece of memory? Because memory is not contiguous, for any node, to access the next block of memory, we need to know the address of the next block of memory, and what do we usually do? Quite simply, we put the address of the next block of memory in this node.
so what do we need to do to access a piece of discontiguous memory? We need to know the address of the previous node, because the address of the memory to be accessed is in the previous node, so how can we access the last piece of memory? Obviously, if we keep pushing like this, we need to know the first piece of memory, and for any piece of memory, if we want to access one of them, we have to start with the first block. Random access is not supported.
now if we have a requirement, we want to store a linear table and ask you, shall we choose sequential storage or chained storage? You may have a starting point, and as we know above, if we want to look for a piece of memory frequently, sequential storage is obviously better.
this is just one of them, and one more thing. Is to add and delete, capacity. Todo
