Features
Features:

Product Tour >

Edraw AI >

Paid Plans:

Individuals >

Business >

Eduaction >
Resources
Blog

History

How-tos & Tips

Discovery

Biography

Business Analysis

Examples

AI concept Map

Free AI Mind Map Generator

Onenote Mind Map

Bcg Matrix Examples

Nike Marketing Strategy

Unilever SWOT Analysis

Make Mind Maps in Google Docs

Guide

FAQs

What's New

Resource Center
Templates
All Templates

Brain Storming Templates

Strategy and Planning Templates

Project Management Templates

Product Management Templates

Human Resources Templates

Agile Workflow Templates

Marketing Templates

Education Templates

Fun and Games Templates

User Gallery
Download
Pricing
Enterprise

MindMap Gallery Introduction to data structures

Introduction to data structures

Algorithm time complexity, space complexity, basic concepts of data structure, algorithm characteristics, data objects, collection of relationships on data objects, collection of basic operations of data objects

Edited at 2022-07-05 22:49:15

PlotWizard

Recent works View more works>>

Introduction to data structures

PlotWizard

Recent works View more works>>

Recommended to you
Outline

introduction

Basic concepts and terminology

data, data element, data item, data object

Data(Date)

The symbolic representation of objective affairs is a general term for all symbols that can be input into a computer and processed by a computer program.

Date Element

The basic unit of data, usually considered as a whole in computers. Used to completely describe an object.

Date Item

It is the smallest indivisible unit that constitutes a data element and has independent meaning. Such as the student’s student number

Data Object

A collection of data elements with the same properties is a subset of data.

data structure

definition

A collection of data elements that have one or more relationships with each other. Structure is the relationship between elements

composition

logical structure

Describe data in terms of logical relationships, which has nothing to do with data storage and is independent of computers.

two elements

data element

relation

Logical relationships between data elements

Set structure

There is no other relationship between data elements except that they belong to the same structure.

linear structure

There is a one-to-one relationship between data elements. Student information table arranged by admission date

tree structure

There is a one-to-many relationship between elements.

graph structure, network structure

There is a many-to-many relationship between elements.

logical structure of data

linear structure

linear table

General linear table

linear table

special linear table

Stacks and Queues

string

Generalization of linear tables

array

generalized table

nonlinear structure

tree structure

Tree

Binary tree

graph structure

directed graph

Undirected graph

Set structure

storage structure

definition

The storage representation of data objects in the computer is called the storage structure of the data, also known as the physical structure. When storing data objects into the computer, it is usually required to store the data of each data element and also to store the logical relationship between the data elements.

Basic storage structure

sequential storage structure

The logical relationship between data elements is represented by the relative position of the elements in the memory. Usually with the help of arrays.

shortcoming

Elements are required to be stored in a continuous storage space.

Prone to storage fragmentation (small chunks of storage that cannot be used)

advantage

random access

High storage density

chain storage structure

There is no need for continuous storage space, but in order to express the relationship between nodes, a pointer field needs to be attached to each node to store the storage address of subsequent elements. Usually with the help of pointers.

Use pointers to represent logical relationships between elements.

advantage

There will be no fragmentation and storage space can be fully utilized.

shortcoming

Low storage density (each node needs to store one more pointer to the storage address of the next element)

Can only be accessed sequentially.

Index storage

While storing element information, a corresponding index table is also established. Each item in the index table is called an index item, and the general form of an index item is (keyword, address)

advantage:

Fast retrieval

shortcoming

Additional index tables occupy additional storage space

When adding or deleting data, you need to modify the index table, which will waste a lot of time.

Hash storage

The storage address of the element is directly calculated based on the element's keyword, also known as hash storage.

advantage

Fast retrieval

Add and delete quickly

shortcoming

If the hash function is not good, conflicts in element storage units may occur, and resolving conflicts will increase time and space overhead.

Data operations

Includes definition and implementation of operations

Definition depends on logical structure

The implementation depends on the storage structure.

Data types and abstract data types

type of data

A collection of values and a set of operations defined on this value collection. Such as integer type, with addition, subtraction, multiplication and division

abstract data type

A general term for a user-defined data model that represents an application problem and a set of operations defined on this model.

details

data object

A collection of relationships on a data object

A collection of basic operations on data objects

Algorithms and Algorithmic Analysis

Algorithm definition and characteristics

algorithm

A finite sequence of operations specified to solve a certain type of problem.

five characteristics

Finiteness

An algorithm must always end after executing a finite number of steps, and each step must be completed in finite time.

certainty

The operations that should be performed in each case are clearly specified in the algorithm, without ambiguity, so that both the executor and reader of the algorithm can clearly understand its meaning and how to perform it.

feasibility

All operations of the algorithm can be implemented by executing the already implemented basic operations a limited number of times.

enter

An algorithm has zero or more inputs.

output

An algorithm has one or more outputs, which are the results of information processing by the algorithm. Algorithms without output make no sense.

Basic criteria for evaluating the quality of algorithms

correctness

Reasonable input, correct output

readability

Easy to understand and read

Robustness

If the input is illegal, the correct response or corresponding processing can be made appropriately without producing some inexplicable output.

Efficiency

Measured by time complexity and space complexity.

Algorithm time complexity

Question size and statement frequency

Problem size

The amount of input required by an algorithm to solve a problem is an essential representation of the size of the problem, generally represented by n. Generally speaking, the larger n is, the longer the algorithm execution time is.

Sentence frequency

The number of times a statement is executed repeatedly is called statement frequency.

Assuming that the time required to execute each statement once is unit time, then the execution time of an algorithm can be measured by the sum of the frequencies of all statements in the algorithm.

Time complexity definition of algorithm

The workload of an algorithm is measured using the number of executions of basic statements in the algorithm.

Basic execution statements

A statement in an algorithm whose number of repetitions is proportional to the execution time of the algorithm. It contributes the most to the algorithm running time.

Under normal circumstances, the number of executions of a basic statement is a function f(n) of the problem size n, and the time complexity of the algorithm is recorded as T(n)=O(f(n))

Worst time complexity is commonly used to measure the time complexity of an algorithm.

Influencing factors

Problem size n

Data logical structure

data storage structure

The initial state of the data to be processed

Algorithm space complexity

space complexity

A measure of the storage space required by the algorithm.

is also a function of problem size n

If the auxiliary space required for algorithm execution is a constant relative to the input quantity, then the algorithm is called working in place, and the space complexity is O(1)

Data structure is a discipline that studies the operating objects in non-numerical computing programming, as well as the relationships and operations between these objects.