The data structure

The linear table

A linear list is a finite sequence of N (n >= 0) data elements of the same data type.

  1. Sequential storage structures, called sequential tables

    • Insert A new data element item at position I of linear table A of length N
    • Delete the ith data element from linear table A of length N
    • Determines the position of the element item in linear table A of length N
    • Removes duplicate elements from the table
    • Sort the elements in a linear table

  2. Chain storage structure, called linear list or singly linked lists, the structure of the link point | data | link |

    • Create a linear linked list
    • Find the length of a linear list
    • Tests whether a linear linked list is empty
    • Determines the position of the element item in a linear list
    • Insert a link point with data information item before the first link point in a non-empty linear list
    • Insert a link point with item data information at the end of a non-empty linear list
    • Insert a link point with item data after the link point indicated by pointer Q in a linear list
    • Insert a link point with data information item after the ith link point in the linear list
    • Inserts a link point with the data information item into a linear list ordered by value
    • Removes the link point referred to by Q from the non-empty linear list
    • Destroy a linear linked list
    • Delete all link points in a linear list whose data field value is item
    • Reverse a linear linked list
    • Join two non-empty linear lists to form a linear list
    • Combine two non-empty linear lists ordered by value into a linear list ordered by value
    • Copy a linear linked list
    • Use linear linked lists to sort data

  3. Circular linked list

  4. Two-way linked list

    • Insert a new node with item to the right of the node with x in the first data field in the bidirectional circular linked list with a head node
    • Removes the node whose first data field is x from the bidirectional circular list with a header

An array of

An Array is an ordered sequence of elements.

  1. Matrix Symmetric matrix, diagonal matrix, sparse matrix (triplet list, transpose algorithm)

Stack (In back out)

A stack is a linear table that allows insertions and deletions at only one end of the table. The end of the allowed operation is called the top of the stack, and the position of the top element is given by a variable called the top pointer. The other end is called the bottom of the stack.

  1. Order of the stack

    • Initialize a stack top = -1;
    • Return top == -1;
    • Return top == m-1;
    • Remove the current top element of the stack
    • Insert (push)
    • Delete (unstack)

  2. The chain of the stack

    • Link stack initialization top = NULL;
    • Return (top == NULL);
    • Item = top->data
    • The insertion of the link stack
    • Removal of the link stack

Queue (first in, first out)

A queue is a special kind of linear table, special in that it only allows deletion at the front of the table and insertion at the rear. Like a stack, a queue is a linear table with limited operation. The end that inserts is called the end of the queue, and the end that deletes is called the head of the queue.

  1. The order queue

    • Initialize a queue front = -1; rear = -1;
    • Return front == rear;
    • Item = QUEUE[front + 1];
    • Queue insertion
    • Queue deletion (outqueue)

  2. Loop queue (front=rear=0)

    • Whether the loop queue is full (rear + 1) % M == front
    • Whether the loop queue is empty front == rear
    • The insertion of the loop queue
    • Delete the loop queue

  3. Link queue

    • Front = rear = NULL;
    • Return front = NULL;
    • Takes the current queue head element
    • Link queue insertion
    • Deletion of link queues
    • Destruction of link queues

Generalized table

Generalized tables, also known as lists, are linear storage structures.

Both non-separable elements and generalized tables can be stored in generalized tables

LS = (a1, a2,... ,an)Copy the code

LS indicates the name of the generalized table, and an indicates the data stored in the generalized table. Each AI in a generalized table can represent either a single element or another generalized table.

Atoms and subtables:

In general, a single element stored in a generalized table is called an “atom”, and a stored generalized table is called a “child table”.

  • Find the length of the generalized table
  • Find the depth of the generalized table
  • Replicated generalized table

Representation of multivariate polynomials

string

The basic concept of string:

String: A finite sequence of zero or more characters. Remember: S = “a1a2a3…” , S is a string name, and AI (1 ≤ I ≤ N) is a single character that can contain letters, digits, or other characters.

String values: Sequences of characters enclosed in double quotes are string values.

String length: The number of characters contained in a string is called the length of the string.

Empty string (empty string) : A string of length zero is called an empty string and contains no characters.

Whitespace: A string whose characters are all Spaces is called whitespace. Note: The difference between empty and blank strings, for example “” and” “represent blank strings of length 1 and empty strings of length 0 respectively.

Substring: Any sequence of consecutive characters in a string is called the substring of the string, and the string containing the substring is called the main string.

Serial number of a substring: The serial number (or position) of a substring that corresponds to the first character of the substring when it first appears in the main string.

In particular, an empty string is a substring of any string, which is a substring of itself.

String equality: Two strings are said to be equal if they have the same value. In other words, two strings are equal only if they are of the same length and have the same characters in each corresponding position.

String basic operations:

  • Assign a value to a string variable
  • Tests whether a string is empty
  • Tests whether two strings are equal
  • Two series of connection
  • Find the length of the string
  • Strives for the substring
  • Find the position of the substring in the main string
  • List of replacement
  • List of assignment
  • List of insert
  • List of deleted

String storage structure:

  • Sequential storage structure
  • Chain storage structure

Trees and binary trees

A tree is a finite set containing n (n >= 1) nodes and edges, where:

(1) Each element is called node;

(2) There is a specific node called the root node or root.