Chapter I Introduction

Chapter one The introduction

Chapter two The linear table

The third chapter Stack 、 Queues and arrays

Chapter four strand

The fifth chapter Trees and binary trees

Chapter six chart

Chapter vii. lookup

Chapter viii. Sort

00 The opening —— What data structures are learning

• How to use program code to informationize real-world problems
• How to process this information efficiently with computers

01 The introduction

1.1 Basic concepts

data ： Data is the carrier of information , It's a number that describes the attributes of an objective thing 、 A collection of characters and all symbols that can be input into a computer and recognized and processed by a computer program . Data is the raw material for computer programming

data elements ： It's the basic unit of data , Usually considered and dealt with as a whole

A data element can consist of several data items , A data item is the smallest indivisible unit of data elements

A data object is a collection of data elements with the same properties , It's a subset of the data

A data structure is a collection of data elements with one or more specific relationships

 The course of data structure focuses on the relationship between data elements , And operations on these data elements , And don't care about the specific data item content 

 The same data elements , Can form different data structures 

 Different data elements can form the same data structure 

1.2 The three elements of data structure

1.2.1 Logical structure

1.2.2 The operation of data

The operation of data ： For a logical structure , Combined with actual needs , Define basic operations （ Additions and deletions ）

1.2.3 Physical structure （ Storage structure ）

Sequential storage ： Store logically adjacent elements in a physical location that is also adjacent to each other , The relationship between elements is represented by the adjacency of storage units .

Chain store ： Logically adjacent elements may not be adjacent in physical position , The logical relationship between elements is represented by a pointer indicating the storage address of the element .

Index storage ： While storing element information , Also create additional index tables . Each item in an index table is called an index entry , The general form of an index entry is （ keyword , Address ）

Hash store ： According to the key words of the element, the storage address of the element can be calculated directly , Also known as hash （Hash） Storage

1.2.4 data type 、 Abstract data types

A data type is a collection of values and a set of operations defined on it .

• Type of atom . A data type whose value cannot be subdivided .
• Structure type . Its value can be further decomposed into several components （ component ） Data type of .

Abstract data types （Abstract Data Type,ADT） Abstract data organization and its related operations

1.3 The basic concept of algorithm

1.3.1 What is algorithm

Algorithm （Algorithm） It is a description of the steps to solve a specific problem , It is a finite sequence of instructions , Each of these instructions represents one or more operations

1.3.2 Characteristics of the algorithm

• Fineness ： An algorithm must always end after a finite step , And each step can be completed in limited time .（ The algorithm is finite , And programs can be infinite ）
• deterministic ： Every instruction in an algorithm must have a precise meaning , For the same input, you can only get the same output
• The feasibility of ： The operations described in the algorithm can be realized by executing the basic operation for a limited number of times .
• Input ： An algorithm has zero or more inputs , These inputs are taken from a collection of specific objects .
• Input ： An algorithm has zero or more inputs , These inputs are taken from a collection of specific objects .

1.3.3 Good algorithm

• correctness . The algorithm should be able to solve the problem correctly
• Readability . The algorithm should have good readability , To help people understand .
• Robustness, . When entering illegal data , The algorithm can respond or process appropriately , Without producing inexplicable output results .
• High efficiency and low storage demand
  

1.3.4 The measurement of algorithm efficiency

• Time complexity

  Addition rules ： Multinomial addition , Keep only the highest order items , And the coefficient becomes 1

  Multiplication rules ： Multiple multiplication , All reserved

  Constant exponential order

  

   Conclusion 1： Sequentially executed code only affects constant terms , You can ignore 
   Conclusion 2： Just pick a basic operation in the loop and analyze its execution times and  n  The relationship between 
   Conclusion 3： If there are multiple nested loops , Just focus on the deepest cycle a few times 
  

• Spatial complexity

  The algorithm works in place —— The memory space required by the algorithm is constant

  Spatial complexity = Depth of recursive call