（ One ） Basic concepts
1. data structure
A collection of data elements that have one or more specific relationships with each other .
2. Logical structure
The relationship between data elements in a data object .
There are four kinds of logical relations . Namely aggregate 、 linear relationship 、 Trees and graphs .
Between data structure elements , Except that they belong to the same set , It's nothing else .
l linear relationship
There is a one-to-one relationship between data structure elements .
l Tree relationship
There is a one to many hierarchical relationship between the data elements of a data structure .
There is a many to many relationship between the data elements of a data structure .
3. Physical structure
The logical structure of data stored in a computer .
There are two ways to store data . Sequential storage and Chain store .
l Sequential storage
Put data elements in a storage unit with consecutive addresses . The logical and physical relationships between the data are consistent . The most common example is Array .
l Chain store
Put data elements in any storage unit , These storage units can be continuous or discontinuous 【 The storage relationship of data cannot reflect the logical relationship of data elements , So you need a pointer to store the address of the element , Therefore, the position of the associated element can be found through the pointer 】.
Logical relationship is facing problems , Physical relations are computer oriented . The basic goal is to keep the data and the logical relationship of the data in the computer .
4. data type
A set of values with the same data properties and the operations defined on the set .
It is divided into Element type and Structure type .
5. Abstract data types
Mathematical models and operations defined on data models .
Abstract data types tend to describe things more essentially . such as , The abstract data type of a stack is the abstraction of all stacks . It's understandable . A class is an abstraction of an object . Abstract data type is a kind of abstraction .
（ Two ） The linear table
A finite sequence of zero or more data elements .
1. Sequential storage of linear tables
Refers to the use of a continuous storage unit to store the data elements of a linear table in turn .
(1) Basic concepts
It's usually a one-dimensional array . The sequential storage structure requires three properties .
l The starting location of the storage space . Array data, Its storage location is the beginning of the storage space .
l The maximum storage capacity of linear table . The length of the array MaxSize, Capacity .
l The current length of the linear meter .Length.
(2) Insertion of linear table sequential storage
Xiang di i Place to insert an element .
l If the insertion position is not reasonable , Report errors
l From the last position to i A location traversal . Move them back one position respectively .
l And then insert the data into i A place .
l Watch length plus one .
(3) Deletion of linear table sequential storage
l If the deletion location is unreasonable , Report errors
l From i Start traversing to the position of the last element . Move their data one position forward separately .
l Watch length minus one .
2. Chain storage of linear table
Data preservation needs to preserve the relationship between the data elements themselves and the data elements . therefore , Nodes are called data cells . The data node consists of data field and pointer field . It stores the information of the data itself and the pointer to the directly succeeding node .
A linked list with a pointer field in each node is called a single linked list .
(1) Insertion of single chain table
Suppose the storage element e The node of s, It needs to be inserted into p and p->next Between two nodes .
The rest of the nodes don't need to change , It just needs to be modified s->next and p->next that will do . Revised as follows ：
s->next = p->next;
p->next = s;
(2) Deletion of single chain table
Suppose you delete P The node after the node . The specific code is as follows ：
p->next = p->next->next;
Record the nodes that need to be deleted , Point the pointer field of the precursor node of the node to be deleted to the successor node to be deleted .
(3) Single linked list creation
The first interpolation ： The node created is always the first . Because of the head pointer , This idea is easy to understand .
The tail interpolation ： In the course of an iterative cycle , Do not assign a value to the pointer field . Assign a node to r. And the next time it's cycled , New node created p. Assign a value to the pointer field of the previous node r->next=p; Specifies that the pointer to the previous node is the current node .
3. Static list
(1) Define and understand
Static list ： A list described by data is called a static list . Each element of an array consists of two parts .Data and cur. among data It's used to store data elements . It's also the data we need to process .Cur The pointer equivalent to a single linked list , Store the subscript of the element in the array .Cur It's also called a cursor . Also known as cursor implementation .
Spare linked list ： Unused array elements in a static linked list are called standby lists . The first and last elements of a static linked list are treated as special elements , No data . The first element of a static linked list , That is, the subscript is 0 The elements of the cur Just store the subscript of the first node of the standby list . When the static linked list needs to insert data , It only needs space->cur , Get the first unused element in the spare list . And the last element cur It holds the subscript of the first element with a value . It is equivalent to the function of header in single chain list . When the whole list is empty , by O2.
difficulty ： Personally think that , The difficulty of static linked list is to understand Spare linked list Initializing 、 Changes in the process of inserting and deleting data . As long as you understand the process , The static linked list is completely understood .Space[n] Stands for static linked list .
l Initialization of standby linked list
In the process of static list initialization , The whole list is still empty . All component positions are empty . The code is as follows . Guarantee space.cur Is the subscript of the first unused node .pace[MaxSize-1].cur The subscript for the first element used . That is, the index of the static list .
for (i = 0; i < MaxSize - 1; i++)
space[i].cur = i + 1;
space[MaxSize-1].cur = 0;
l Static linked list insert data, change of backup linked list
Insert requirement as ： Give the static list of the first i Place to insert an element . Values for value. Get the first free bit from the standby list j,【 In the course of this, we've already dealt with space It is amended as follows j】. Then save the data to the subscript j The elements of the data in . Then adjust the subscripts of the use list and the spare list correctly .
space[j].cur = space[i-1].cur; // The original In the list i Subscripts of elements , Assigned to the current new element cur.
space[i-1].cur = j;// The deleted element is placed in the first position of the alternate linked list .
l Static linked list delete data backup list changes
space[k].cur = space.cur; // The original spare list is placed after the deleted node
space.cur = k;// The deleted element is placed in the first position of the alternate linked list .
The data structure consists of two parts , The data of data elements and the relationship between data elements . If you can store these two parts in a computer , It means that the current data is completely saved to the computer . Static linked list node data with node The data field of data Express , The relationship between data has nodes node A pointer to the domain cur To express . Usually record the current node The rear drive position of .
Use arrays to describe linked lists . I feel very unique . Its advantages and disadvantages . The size of the array needs to be determined in advance . advantage Each node directly uses , No need to request and free memory , Save time . shortcoming yes The applied resource size is fixed , It's troublesome to expand the capacity . It can only be used with a circular list , Greater significance .
(2) Insert static linked list insert
In order to distinguish which components in an array are not used , The solution is ： All unused and deleted components are linked into a spare linked list by cursor . Every time you insert , The first node in the list needs to be inserted from the new node .
Basic linked list operation ： Suppose that the new node M Insert P and Q Between . The pointer of the previous node points to the pointer of the new node . The pointer to the new node covers the pointer to the previous node .
M->next = P->next;P->next = M;
The operation of the spare list .
(3) Static linked list delete
Basic linked list operation ： Will set P、Q It's two nodes in order . Need to delete Q, be
P->next = Q->next
Standby linked list operation ： Take the first element of the standby list as the next element of the deleted node . Delete the node as the first element of the standby list .
4. Circular linked list
Point the pointer of the terminal node of the linked list from the null pointer to the head node . Form a single chain into a ring . The circular list of single chain list is called circular list for short .
Add a pointer field of the precursor node to the node of the single chain list . It's called a double linked list .
（ 3、 ... and ） Stacks and queues
There are two data structures: stack and queue , My understanding is the specific application of linear table . Because data structures represent two kinds of meanings . The relationship between the data itself and the data elements . Real world scenarios are usually based on the relationships between data elements 【 In terms of the linear table, it is the relationship between the front and the rear 】 To determine the order in which to use the data . Usually there are “ First come, first served ” and “ Later, I used ” Two scenarios . So , Limit the location of the linear table , As a result, there are two data structures of queue and stack .
Queues and stacks only limit the insertion and deletion positions of linear tables .
Linear tables that are limited to insertion and deletion at the end of the team . The end that allows insertion is called the top of the stack (top), The other end is called the bottom of the stack (bottom), Stacks are called LIFO LIFO The linear table .
The insertion of a stack is called ： Into the stack 、 Push 、 Pressing stack . The deletion of a stack is called a stack 、 Bomb stack .
(1) The implementation of stack sequential storage
Data structure of stack , A linear table 、top and stackSize.
Top： The position of the stack array where the top element is located （ from 0 At the beginning ）,-1 For empty stacks .Top The maximum value of is StackSize-1.
StackSize： The length of the stack . That is, the length of the stack's linear table .
l Stack operation
Push ：top Self increasing 1,s->top++; Give the linear table , Subscript to be top The element assignment of s.data[top]=e;
Out of the stack ： obtain top Location data ,top--
l Two stacks of shared space
The data types of the two stacks of data elements are the same , There are scenarios where one element is added and another is reduced , It is more suitable to use two stacks of shared memory .
Use the table head and table position of the linear table as the bottom of the stack , Use the order from both sides to the middle .Top1 and top2 The sub table represents the subscript of the first element at the top of the stack of two stacks .Top1+1=top2 The stack is full .
(2) The implementation of stack chain storage
For chain stacks , You don't need a head pointer . Because the stack address represents the position of the head pointer .
form ： Linked list ,top： The address of the top element of the stack ,count： The number of elements in the stack .
Push ： Assign a new element to the top of the stack （ Pointer to the domain ）. Assign the new node to the top pointer of the stack .Count++.
Out of the stack ： Get elements s->top->data, Reset stack top pointer .S->top = s->top->next;
(3) The function and application of stack
The introduction of stack simplifies the programming problem . Recursion is realized in programming language .
Recursive function ： A function that calls itself or indirectly calls itself , Called a recursive function .
In the definition of recursion , When at least one condition is satisfied , Recursion is no longer going on . That is, the return value exits without reference recursion .
The difference between recursion and iteration ： Iterations use the structure of loops , Recursion uses the structure of choice .
Four Operational expressions ：
The calculation rules of subsequent expressions ： When it comes to numbers , Just into the stack . Encounter symbols , Pop up the two elements at the top of the stack , Carry out operations , Put the result of the operation on the stack . Always get the final result .
Java In the virtual machine , This is how the stack of operands in the stack frame performs data calculation .
Only insert operations at one end are allowed , A linear table with a delete operation at the other end . A queue is a first in, first out linear table . The end of the line is allowed to be inserted , Allow to delete the end for the team head .
(1) Circular queue
Queues to avoid having only one element , When the head and tail of the team coincide , Introduce two pointers .Front The element pointing to the team head ,rear The element that points to the end of the team . The sequential storage structure in which the head and tail of a queue are connected is called a circular queue .
l Empty queue ：front==rear
l The queue is full ：【 because front Maybe it's better than rear Small , Or maybe rear Big （rear A cycle , Run to the head of the team ）】 when ,front and rear The difference between them is （rear+1）%QueueSize = front
l captain ：(rear+QueueSize -front)%QueueSize
l Team inserts data ： Judge if the team is full , If it is not full, insert the element data[rear] =e, And then rear Move back a bit .Rear=(rear+1)%QueueSize
l Team delete data ： Determine whether the queue is empty , If not , Get data from the team leader data[front]. team front Move back one position front=(front+1)%QueueSize.
(2) Chain storage of queues
A linear list is essentially a linear list . It's just that it can only come in from the tail and out from the head . Also known as chain queue . Put the head of the team front Point to the head node , Pointer to a party rear Point to the terminal node . Empty queue ：front and rear They all point to the head pointer .
l Joining operation ： Assign the address of the new element to the pointer of the element at the end of the queue .Q->rear->next=s; Assign a new address to an element rear.Q->rear=s;
l Out of line operation ： Get the successor of the header element ( The first data element ),p=Q->front->next; get data .e=P->data; Judge p Whether the end of the node is . If it's a tail node ,rear Need to reassign .