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 Chapter One Introduction

Chapter One Introduction

An article about data structure mind maps, basic concepts of data structures, algorithms and algorithm evaluation, etc. Hope this helps!

Edited at 2023-11-21 17:17:08

PlotWizard

Recent works View more works>>

Chapter One Introduction

PlotWizard

Recent works View more works>>

Recommended to you
Outline

Chapter One Introduction

1.1 Basic concepts of data structure

Basic concepts and terminology

1. Data

The set of all symbols that can be input into a computer and recognized and processed by a computer program

All data is represented in the computer as binary

2. Data elements

Data elements are the basic units of data and are usually considered and processed as a whole

3. Data items

Data elements are composed of several data items, which are the smallest indivisible units of data.

4. Data objects

A data object is a collection of data elements with the same properties

5. Data type

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

Classification

Atomic type

Data types whose values are not divisible

For example: int

structure type

Data types whose values can be subdivided

For example: structure

Abstract data type (ADT)

D: data object

S: data relationship

P: Basic operations

Three elements of data structure

1. Logical structure of data

definition

A collection of data elements that have one or more specific relationships with each other

Classification

linear structure

one-to-one relationship

Features

Except for the first element, all other elements have only one "direct predecessor"

Except for the last element, all other elements have a unique "direct successor"

gather

Belong to the same set

Tree

one-to-many relationship

Features

Except for the root node, all other points have only one "direct predecessor"

Except for leaf nodes, all other elements have several "direct successors"

grid (Graphic structure)

many-to-many relationship

Features

For any vertex, there can be several "direct predecessors" and "direct successors"

2. Physical structure of data (storage structure)

definition

Storage structure refers to the representation of data structure in the computer (also called image), also called physical structure

Classification

sequential storage structure

definition

Store logically adjacent nodes in physically adjacent storage units.

Generally represented by an array

advantage

Random access can be achieved

Each element takes up the least space

shortcoming

Only a whole adjacent block of storage space can be used, which is prone to fragmentation.

Illustration

chain storage structure

definition

It is not required that logically adjacent elements are also physically adjacent.

Use pointers to represent logical relationships between elements

advantage

Make full use of all storage space

shortcoming

Only sequential access

Pointers take up additional storage space

illustrate

Storage unit address within the node: must be continuous

Storage unit addresses between nodes: not necessarily consecutive

Illustration

Index storage structure

definition

While storing data element information, an index table is also created.

The general form is: <keyword, address>

advantage

Fast retrieval

shortcoming

Index tables take up additional storage space

When adding or deleting data, you need to modify the index table

Hash storage structure

definition

Calculate the address of the data element directly based on the size of the keyword

Also known as hash storage

advantage

Retrieving, adding, and deleting nodes are fast

shortcoming

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

non-sequential storage structure

3. Data operations

definition

Operations applied to data include the definition and implementation of the operations.

Operations are defined for logical structures

The implementation of the operation is based on the physical structure

1.2 Algorithms and algorithm evaluation

Basic concepts of algorithms

Worth formula = data structure algorithm = program

1. Definition of algorithm

It is a description of the steps to solve a specific problem. It is a finite sequence of instructions, where each instruction represents one or more operations.

2. Description method of algorithm

natural language

flow chart

pseudocode

programming language

3. Five characteristics of algorithms

(1) Finiteness

Ends after executing finite steps, and each step can be completed in finite time

For example: infinite loop program code

(2) Certainty

Each instruction must have an exact meaning so that there will be no ambiguity when the reader understands it.

Only the same output can be obtained for the same input

(3) Feasibility

The operations described in the algorithm can be realized by executing the basic operations a limited number of times.

(4)Input

An algorithm has zero or more inputs

(5)Output

An algorithm has one or more outputs

4. Evaluation of algorithms

(1) Correctness

Algorithms solve problems correctly

The “right” level

a. The program does not contain grammatical errors

b. For several sets of method input data, output results that meet the requirements can be produced.

c. Able to produce output results that meet the requirements for illegal input data

d. For all legal input data, output results that meet the requirements can be produced

(2) Readability

Help people understand the algorithm

(3) Robustness

Algorithms can also react or process appropriately when input data is illegal

(4) High efficiency and low storage requirements

Efficiency refers to the time it takes for an algorithm to execute

Storage requirements refer to the maximum storage space required during algorithm execution.

Metrics of Algorithms

metrics

time complexity

space complexity

Measurement method

Post-event statistics

Use a computer timer to time the running time of the program on the computer

shortcoming

(1) The program compiled based on the algorithm must be run first

(2) The resulting running time depends on environmental factors such as computer hardware and software.

(3) The cost of running the program is relatively high

Pre-analysis and estimation

Before computer programming, algorithms are estimated based on statistical methods

The time taken to run depends on

(1) What strategy should the algorithm choose?

(2) Scale of the problem

(3) Language for writing programs

(4) The quality of the machine code generated by compilation

(5) The speed at which the machine executes instructions

focus point

Putting aside factors related to computer hardware and software, it can be considered that the size of the "running workload" of a specific algorithm only depends on the size of the problem (n), or in other words, it is a function of the size of the problem.

time complexity

Calculation method

Sentence frequency

The number of times the original operation is executed in the statement within the deepest loop

function representation

Generally speaking, the number of times the basic operations in the algorithm are repeated is a function f(n) of the problem size n, and the time measurement of the algorithm is recorded as T(n)=O(f(n)) (time complexity)

focus point

Only look at the highest level

Remove the constant term

ignore coefficient

Common O(n) size relationship

three conditions

best time complexity

Worst time complexity

average time complexity

Influencing factors

initial state of data

Problem size

space complexity

Calculation method

The space complexity of the algorithm is recorded as S(n)=O(f(n))

focus point

Analyze extra space beyond input and program