Data structure core noun explanation

The following name explanation is taken from Weimin Yan of Algorithms and Data Structures.

Data

It is a symbolic representation of objective things. In computer science, the collective term for all symbols that can be entered into a computer and processed by a computer program.

Data Elements

A data element is a basic unit of data and is usually considered and processed as a whole in a program. A Data element can consist of several Data items.

Data Item

A data item is the smallest indivisible unit of data. A data item is a data description of a certain aspect of an objective thing.

Data Objects

Is a collection of data elements of the same nature, is a subset of data.

Data Structure

A collection of data elements that have a relationship with each other. The relationships (relationships) between elements are called logical structures. There are four basic types of logical structure between data elements.

Logical structure vs. physical structure

Logical structure

The relationship between data elements can be the natural relationship between elements that represents a certain meaning, or the relationship that is artificially defined for the convenience of dealing with problems. Such natural or artificially defined “relationship” is called the logical relationship between data elements, and the corresponding structure is called the logical structure. There are four basic types of logical structures:

  1. A collection ofData elements in a structure have no relationship other than that they belong to the same set.
  2. Linear structureThere is a one-to-one relationship between data elements in the structure.
  3. A tree structureThere is a one-to-many relationship between data elements in the structure.
  4. A graph structure or network relationshipThere is a many-to-many relationship between data elements in the structure.

The physical structure

Physical structure is the storage form of data logical structure in the computer, there are generally three kinds.

  1. Sequential storage structures, such as linear tables.
  2. Chain storage structures, such as trees.
  3. Composite storage structure, as shown.

algorithm

An algorithm is a description of a method (step) for solving a particular problem. It is a finite sequence of instructions, each of which represents one or more operations.

Characteristics of the algorithm

  • Finiteness: An algorithm must always end after executing finite steps, and each step must be completed in finite time.
  • Deterministic: Each instruction in an algorithm must have an exact meaning. There is no ambiguity. And the algorithm has only one entrance and one exit.
  • Feasibility: An algorithm can work. That is, the operations described by the algorithm can be implemented by performing a finite number of already implemented basic operations.
  • Input: An algorithm has zero or more inputs from a particular set of objects.
  • Outputs: An algorithm has one or more outputs, which are quantities that have some specific relationship to the outputs.

Algorithm design requirements

There are several criteria to evaluate a good algorithm:

  • correctness: The algorithm should meet the requirements of the specific problem.
  • readability: Algorithms should be easy to read and communicate. A readable algorithm facilitates understanding and modification of the algorithm.
  • Robustness,: The algorithm should be error tolerant. When invalid or incorrect data is entered, the algorithm can react or process it appropriately, rather than producing unintelligible output.
  • generality: The algorithm should be generic, that is, the processing results of the algorithm are valid for general data sets.
  • Efficiency and storage requirements: Efficiency refers to the algorithm execution time; Storage requirement Refers to the maximum storage space required during algorithm execution. Generally related to the size of the problem.

Algorithm efficiency measurement method

Algorithm execution time virtual is measured by the time consumed by the program based on the algorithm running on the computer, that is, time complexity.

Time complexity

The number of repeated execution of basic operations in the algorithm is a function of problem size N, and its time measure is written as T(n)=O(f(n)), which is called the asymptotic time complexity of the algorithm, or time complexity for short. In general, the frequency (the number of repeated executions) of the original operation in the statement in the deepest loop is often expressed. Commonly used time complexity relationship is as follows:

Spatial complexity

Spatial complexity: A measure of the amount of storage required to run an algorithm in a computer after it has been programmed. Let’s call it S(n)=O(f(n)). Where n is the size of the problem. Such as:

The linear table

The Linear List is composed of n (n>=0) elements a1, A2… A finite sequence of an. All nodes in the sequence have the same data type. Where the number of data elements n is called the length of the linear list.

  • When n=0, it is called an empty table.
  • When n>0, the non-empty linear list is denoted as :(a1, a2…… An), a1 is called the first node of a linear table, and an is called the last node of a linear table.

Sequential storage

The nodes of a linear table are stored in logical order in a set of contiguous storage cells. Linear tables stored in this way are called sequential tables.

Sequential storage features

  • The logical order of the linear list is consistent with the physical order;
  • The relationship between data elements is represented by their “physical proximity” within the computer.

The basic operation of a sequential table

In the sequential storage structure, it is easy to implement some operations of linear tables: initialize, assign, find, modify, insert, delete, find length, etc.

  • Initialization of a sequence table
Status Init_SqList(SqList *L){
    L->elem_array = (ElemType*)malloc(MAX_SIZE*sizeof(ElemType));
    if(!L->elem_array){
        return ERROR;
    }else{
        L->Length = 0;
        return OK;
    }
}
Copy the code

The memory space of the malloc keyword is opened directly.

  • Insertion of a sequence table
Status Insert_SqList(Sqlist *L, int i, ElemType e){ int j; if(i<0||i>L->Length-1) return ERROR; If (L->Length >= MAX_SIZE){printf(" linear table overflow! ); Return the ERROR; } for(j= L->Length; j>=i-1; j--){ L->Elem_array[j+1] = L->Elem_array[j]; } L->Elem_array[i-1] = e; L->Length++; return OK; }Copy the code

Step implementation split:

  1. Move the i-th node to the n-th node in linear table L by one position.
  2. Insert node E after node A [i-1].
  3. Linear list length plus 1.
  • Delete linear tables
ElemType Delete_SqList(Sqlist *L,int i){ int l; ElemType x; If (L->length == 0){printf(" linear table L is empty "); Return the ERROR; } else if (I < 1 | | I > L - > length) {printf (" want to delete the data element does not exist "); Return the ERROR; }else{// Save the value of the node to be deleted x = L->Elem_array[i-1]; for(k = i; k<L->Lenght; k++){ L->Elem_array[k-1] = L->Elem_array[k]; L->length--; return(x); }}}Copy the code

Step analysis:

  1. Move node I +1 to node N in linear table L forward one position.
  2. The length of the linear table is reduced by 1.

Chain store

Use an arbitrary set of storage cells to store data elements in a linear table. Linear lists stored in this way are called linear linked lists.

Characteristics of chain storage

An arbitrary group of nodes in a storage linked list can be contiguous, discontiguous, or even distributed anywhere in memory. The logical and physical order in a linked list are not necessarily the same.

This article mainly introduces some basic concepts, the next chapter will be a detailed introduction to linked lists and some basic operations algorithm implementation.