B=(D,R) Among them, B is a logical data structure, D is a collection of data elements, there may be multiple relationships between data elements on D, and R is a set of all relationships. Right now: D={di | 0≤i≤n-1, n≥0} R={rj | 1≤j≤m，m≥0}

R={rj | 1≤j≤m，m≥0} A certain relation rj (1≤j≤m) in R is a set of ordered pairs. For any ordered couple <x, y> (x, y∈D) in rj, x is called the first element of the ordered couple, and y is called the second element of the ordered couple. It is also called the first element of the ordered couple. The precursor element of the second element is called the successor element of the first element. For example, in the sequence of <x, y>, x is the predecessor element of y, and y is the successor element of x. If an element has no predecessor elements, it is called a starting element; if an element has no successor elements, it is called a terminal element. For symmetric ordinal pairs, this condition is met: if <x, y>∈r (r∈R), then <y, x>∈r (x, y∈D), parentheses can be used instead of angle brackets, that is ( x,y)∈r.

Set (element relationship 0:0): There is no other relationship between data elements in the structure other than the relationship of "belonging to the same set", which is the same as the concept of sets in mathematics.

Linear structure (element relationship 1:1): If the structure is non-empty, there is and is only one start element and terminal element, and all elements have at most one predecessor element and one successor element.

Tree structure (element relationship 1:n): If the structure is non-empty, there is and is only one element as the starting element (also called the root node). There can be multiple terminal elements, and each element has zero or Multiple successor elements, each element except the start element has exactly one predecessor element.

Graphical structure (element relationship n:m): If the structure is non-empty, each element can have multiple predecessor elements and multiple successor elements.

The mapping should meet two requirements

sequential storage structure

chain storage structure

Index storage structure

Hash (or hash) storage structure

Finite. It means that the algorithm ends automatically after executing a limited number of steps without infinite loops, and each step is completed within an acceptable time.

Certainty. The operations performed in each case have a definite meaning in the algorithm and there is no ambiguity. And under any conditions, the algorithm has only one execution path.

feasibility. Each instruction of the algorithm is executable and can be completed by humans with the help of paper and pen.

Inputability. Algorithms have zero or more inputs. Input parameters are necessary in most algorithms, but for simpler algorithms, such as calculating the value of 1 2, no input parameters are required, so the input to the algorithm can be zero.

Outputability. An algorithm has at least one or more outputs. Algorithms are used for certain data processing. If there is no output, such an algorithm is meaningless. The output of an algorithm is a quantity that has some specific relationship with the input.

Correctness. Usability. readability. Robustness. High time performance and low storage requirements.

time complexity:

Space complexity:

Focus on complexity calculation

All data elements are of the same type.

A linear table is composed of a limited number of data elements.

Data elements in a linear table are position-related, that is, each data element has a unique sequence number.

The unique position of each element ai in the linear table is represented by the serial number or index i. For the convenience of algorithm design, the logical serial number and the storage serial number are unified, and both are assumed to start from 0, so that the element serial number i of a linear table containing n elements satisfies 0 ≤i≤n-1.

When dynamically allocating space in a sequence table, the initial capacity is set to initcapacity. The capacity may need to be expanded when elements are added or inserted, and the capacity may need to be reduced when elements are deleted.

1. Overall establishment sequence table Create a sequence table from all the elements of the array a containing several elements, that is, add the elements in a to the end of the data array in sequence, and when overflow occurs, expand the capacity by twice the actual number of elements, size.

(1) Add element e to the end of the linear table Add(e)

(2) Find the length of the linear table size()

(3) Set the length of the linear table Setsize(nlen) Used to reduce the length of the linear table. When the parameter nlen is correct (0≤nlen≤size-1), set the length size to nlen, otherwise the corresponding exception will be thrown.

(4) Find the element with serial number i in the linear table GetElem(i)

(5) Set the element with serial number i in the linear table SetElem(i, e)

(6) Find the logical sequence number of the first element with value e in the linear table GetNo(e)

(7) Swap the elements of sequence number i and sequence number j in the linear table swap(i,j)

(8) Insert e as the i-th element in the linear table Insert(i, e)

(9) Delete the i-th data element in the linear table Delete(i)

(10) Convert linear table to string toString()

If each node only has one pointer member pointing to its successor node, such a linked list is called a linear one-way linked list, or singly linked list for short.

Each node is a LinkNode<E> generic class object, including the data member data that stores elements (let its data type be E) and the pointer member next that stores subsequent nodes.

Single linked list generic class LinkListClass<E>

Create table

insert

delete

Find

Revise

length

Convert linear table to string toString()

logic

If two pointer members are set in each node to point to its predecessor node and successor node, such a linked list is called a linear doubly linked list, or doubly linked list for short.

DLinkNode<E>generic class

Double linked list generic class DLinkListClass<E>

Create table

insert

delete

A stack is a linear list that can only be inserted or deleted at the same end. The end of the table that allows insertion and deletion operations is called the top of the stack, and the other end of the table is called the bottom of the stack. The insertion operation of the stack is usually called pushing or pushing, and the deletion operation of the stack is usually called popping or popping.

Last-in-first-out means that the elements pushed into the stack last are popped out first. A stack is also called a last-in-first-out list.

sequence stack

chain stack

A queue is a linear list that can only be inserted or deleted at different ends. The end where insertion is done is called the rear, and the end where deletion is done is called the head or front. The insertion operation of the queue is usually called entering the queue or entering the queue (push), and the deletion operation of the queue is usually called dequeuing or leaving the queue (pop).

First in, first out, that is, the elements in the advanced queue are dequeued first. Queues are also called first-in-first-out lists.

Queue abstract data type = linear structure Basic operations of queue

circular queue

non-circular queue

How queues are implemented

Set front=rear=null initially. The four elements of a chain team are as follows: Team empty condition: frontr=rear==null, you might as well use front==null as the team empty condition. Since the queue is full only when the memory overflows, this situation is usually not considered. Element e is added to the queue: insert the s node storing e at the end of the singly linked list, and let the queue tail pointer point to it. Dequeue operation: Take out the data value of the head node of the queue and delete it from the chain queue.

Type of node LinkNode<E>

Chain queue generic class LinkQueueClass<E>

Determine whether the queue is empty()

Enter the queue push(e)

Dequeue pop()

Get the head element of the queue peek()

Like the sequence table, a data array and an integer variable size are used to represent a sequence string. Size represents the actual number of characters in the data array. For the sake of simplicity, the data array uses a fixed capacity of MaxSize (it can imitate the sequential table and change it to dynamic capacity).

Find substrings: For a sequential string, find the substring starting from sequence number i and with length j.

The node type of the link string is LinkNode (node ​​size is 1)

Implementation: First create an empty string s. When the parameters are correct, use the tail interpolation method to create the result string s: (1) Copy the first i nodes of the current chain string to s. (2) Copy all nodes in t to s. (3) Then copy the remaining nodes of the current string to s.