~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Development tools and key techniques: linear table
Author: li yu good
Writing time: on May 18, 2020,
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The definition and characteristic of linear table linear table:
1, there is only the first element; (this determines the figure is not linear table)
2, there is only the last element;
3, in addition to the first element, the other is only a precursor (this decision tree is not linear table)
4, in addition to the last element, others are only a successor,
The order of the linear table representation and realize
1, the order of the linear table storage said
The order of the linear table storage structure: the linear list of nodes according to the logical sequence in the address of a set of continuous storage unit, linear table referred to as "order table stored in this way, it is a kind of random access storage structures, sequential storage means is a piece of memory address, can be pressed when random access to visit the subscript random access, storage and access is not the same, if it is stored, is in order, if it is to access, is random, can use the element subscript,
Is faster than linear array is: in situ reverse, return to the intermediate node, select a random node,
Facilitate the structure of the linear table and access any element
Insert: after inserting new node, node backward-shift, average time complexity: O (n)
Delete: delete nodes, and nodes forward, after an average time complexity: O (n)
Table 2, the order of the realization of the basic operation
Order table: he is in the computer memory in the form of an array to save the linear table, using a set of address in the storage unit of continuous linear structure of stored data elements,
The chain of the linear table representation and implementation
Linear list: use a set of random storage unit to deposit in a linear list of nodes, this set of storage unit which can be a continuous, also can be discrete, even scattered distribution in memory at any position, and
Therefore, logical sequence list nodes and the physical order is not necessarily the same, to express correctly the logical relation between nodes, each node can be stored in the value at the same time, also must be stored instructions behind the node address, data is the data domains, used to store the value of the node is next pointer field (also called a chain domain), used for storing the addresses of the direct successor nodes (or position), do not need to estimate storage space size in advance,
1, the definition of a singly linked list and said
Singly linked lists: a chain store structure, with a set of address any linear table storage unit to store the data elements, (don't need memory address space is continuous)
Singly linked lists of each node in the memory address is stored in the next field, its predecessor nodes and excellent start nodes, reason should set the head pointer point head start node, at the same time, as there is no subsequent last node, so the node pointer field is empty, that is NULL, the first interpolation table (reverse), tail interpolation table (order), increase the head node algorithm implementation is the purpose of convenience, but increases the memory overhead,
Find: only from the head of the list pointer, suitable chain domain next node to search them one by one, until the search to the ith node, as a result, the list is not a random access structure,
Insert: first find the table of the ith 1 storage location, and then insert, new nodes even subsequent first, then even the precursor,
Delete: first, find the storage location of ai - 1 p, then make p - & gt; Next to the ai of the subsequent nodes directly, namely the ai took off from the chain, the final release space of node ai. R=p - & gt; Next; P - & gt; Next=r - & gt; Next; The delete r,
Determine whether there is a ring in a singly linked list is the best way to how a pointer,
2, singly linked lists the realization of the basic operation
3, the circular linked list
Circular linked list: is a kind of end of the list, its characteristic is don't need to increase the storage capacity, ways to link with table only make a little change, can make the list processing more convenient and flexible,
In a singly linked list, change the terminal node NULL pointer domain to point to the nodes or start of headers, get the single form of circular linked list, and simply referred to as a single linked list, because no NULL pointer in circular linked list, so it comes traversal operation, its termination condition is no longer like a circular linked list judgment or p - p & gt; Next is empty, but whether they are equal to a specified pointer, such as the head pointer or the tail pointer,