From the logical structure point of view, the one-dimensional array A is a finite sequence composed of n (n>1) data elements of the same type a1, a2,..., an. Its logical expression is: A=(a1,a2,…,an) Among them, ai (1≤i≤n) represents the i-th element of array A. A two-dimensional array A with m rows and n columns can be regarded as a one-dimensional array in which each data element is a one-dimensional array of the same type. It can be seen that multi-dimensional arrays are a generalization of linear tables.

Taking the C/C language as an example, the array data type has the following properties:

The main forms of special matrices are: (1) Symmetric matrix (2) Upper triangular matrix/lower triangular matrix (3) Diagonal matrix They are both square matrices, that is, they have the same number of rows and columns.

subtopic

Convention: The non-zero elements represented in the data field are usually arranged in row-major order. It is a storage structure in which subscripts are ordered in rows. This ordered storage structure simplifies most matrix operations algorithms.

subtopic

subtopic

The length of a generalized table is defined as the number of elements contained in the outermost layer. The depth of a generalized table is defined as the multiplicity of contained parentheses. Among them, the depth of atoms is 0, and the depth of empty tables is 1. The head of the generalized table GL is the first element a1, and the remaining parts (a2,...,an) are the tail of GL. The tail of a generalized table is always a generalized table. An empty table has no header or footer. The length of a generalized table is defined as the number of top elements in the table. The depth of a generalized table is defined as the maximum number of levels of brackets it contains. Among them, the depth of atoms is 0, and the depth of empty tables is 1.

subtopic

subtopic

subtopic

subtopic

subtopic

subtopic

tree nature

subtopic

subtopic

Parent storage structure

Child chain storage structure

Child sibling chain storage structure

Storage structure of generalized table

String equality: When the lengths of the two strings are equal and the characters at each corresponding position are the same. All empty strings are equal.

Each unit (such as 4 bytes) only stores one character, which is called a non-compressed format (its storage density is small).

Each unit stores multiple characters, which is called a compressed format (its storage density is high).

When the chain node size is 1, the node type of the chain string is declared as follows:

Brute-Force is referred to as BF algorithm, also known as simple matching algorithm. Use an exhaustive approach. BF means violence!

For example, s="aaaabcd", t="abc". BF algorithm idea: starting from each character of s, match the characters of t in sequence.

i, j scan strings s and t respectively i loops from 0 to s.length-t.length. For each s[i], k=i,j=0 starts comparison If t scan is completed, return i If all comparisons of s are completed without return, then -1 is returned.

KMP is to quickly find the substring you want from the main string. Only moves the pattern string backward, the comparison pointer does not move back

Based on the BF algorithm, the space-for-time method is used to extract and save information that is beneficial to matching. Extract information from s or t? Match different characters starting from s each time, and t always starts matching from t0 -> Extract the information in t What information is in t? -> Partial matching information.

The sequential storage structure of the stack and its basic operation implementation

A linear list is a finite sequence of data elements with the same characteristics.

Finiteness: The number of data elements is limited. Consistency: All elements have the same nature, that is, they belong to the same data type. Seriality: Data elements are uniquely determined by logical sequence numbers. A linear list can have elements with the same value. Logical relationship: There is a 1-to-1 relationship between elements.

The number of elements contained in the linear table is called the length of the linear table, represented by n, n≥0. When n=0, it means that the linear list is an empty list, that is, the list does not contain any elements.

1 Initialize the linear list InitList(&L): Construct an empty linear list L. 2 Destroy the linear list DestroyList(&L): Release the memory space occupied by the linear list L. 3 Determine whether the linear list is an empty list ListEmpty(L): If L is an empty list, return true, otherwise return false. 4 Find the length of the linear list ListLength(L): return the number n of elements in L. 5 Output linear list DispList(L): When linear list L is not empty, the value range of each node in L is displayed sequentially. 6 Find a data element at the specified position 8 in the linear table L. GetElem(L, i, & e): Use e to return the value of the i-th (1≤i≤n) element in L. 7 Locate and search LocateElem(L, e): Return the logical bit sequence in which the first value range in L is equal to e. If such an element does not exist, the return value is 0. 8 Insert a data element ListInsert(&L, i, e): Insert a new element e before the i-th (1≤i≤n) element of L, and the length of L is increased by 1. Delete data elements ListDelete(&L, i, &e): Delete the i-th (1≤i≤n) element of L, and use e to return its value, and the length of L is reduced by 1.

Basic operations: InitList, DestroyList Reference operation: the result of the operation does not change the structure Processing operations: the result of the operation changes the structure

Abstract data types for linear tables:

Algorithm parameter description

Delete all elements with value x in the sequence list

Each element in a linear list has a unique predecessor element and successor element.

Each physical node adds a pointer field pointing to the subsequent node  Single linked list. Each physical node adds a pointer field pointing to the successor node and a pointer field pointing to the predecessor node  Double linked list.

storage density

Advantages of adding a head node to a singly linked list

Characteristics of singly linked list

Implementation of basic operations of linear tables on singly linked lists

In the linked storage structure of a linear list, each physical node adds a pointer field pointing to the successor node and a pointer field pointing to the predecessor node Double linked list.

Advantages of doubly linked list:

Design basic computing algorithms

Data is a collection of numbers and characters that describe objective things

A data item is the smallest unit of data with independent meaning, also called a field or domain.

Data object refers to a collection of data elements with the same nature, which is a subset of data

Data structure refers to all data elements and the relationship between data elements. It can be regarded as a collection of data elements that have a certain relationship with each other.

Data structures usually include

Representation of logical structure

Type of logical structure

sequential storage structure

chain storage structure

Index storage structure

Hash (or hash) storage structure

Data type (c/c)

abstract data type ADT

Finiteness

certainty

feasibility

There is input

There is output

correctness

usability

readability

Robustness

Efficiency and storage requirements

Time performance analysis of the algorithm (CPU time)

Spatial performance analysis of algorithms (memory time)

The purpose of algorithm analysis: