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

data structure

Data structure mind map, such as a data type is a collection of values and a set of operations defined on this collection. I haven’t finished memorizing it at the beginning, so let’s take a look.

Edited at 2023-07-20 22:03:53

PlotWizard

Recent works View more works>>

data structure

PlotWizard

Recent works View more works>>

Recommended to you
Outline

data structure

introduction

data structure

basic concept

data

data element, data item

data objects, data structures

Data types, abstract data types

type of data

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

Atomic type

Its value cannot be further divided: bool, int, etc.

structure type

A data type whose value can be decomposed into components: struct

Abstract data type (ADT)

Abstract data organization and operations related to it

Three elements

logical structure

linear structure

One to one

nonlinear structure

Set structure

tree structure

one to many

graph structure

many to many

Data operations

Define basic operations based on logical structure and actual needs

Add, delete, modify, check

Define a data structure (define an ADT)

Physical structure (storage structure)

sequential storage

chain storage

Index storage

Hash storage (hash storage)

Non-sequential storage (discrete storage)

Implement a data structure (determine the storage structure of ADT)

algorithm

Algorithm definition

A description (a finite sequence of instructions) of the steps to solve a particular problem

Important features

Finiteness

The algorithm must be finite, but the program can be infinite

certainty

The same input can only produce the same output

feasibility

Implemented through a finite number of basic operations

enter

Zero or more inputs

output

one or more outputs

Characteristics of a “good” algorithm

correctness

readability

Comment

Robustness

React to illegal data

High efficiency and low storage requirements

Time complexity and space complexity

measure of efficiency

time complexity

Analyze the time complexity of a program

Addition rule

When adding multiple terms, only the highest order term is retained, and the coefficient becomes 1

T(n)=T₁(n)+T₂(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

multiplication rule

Multiple multiplications are retained

T(n)=T₁(n)×T₂(n)=O(f(n))×O(g(n))=O(f(n)×g(n))

Common time complexity orders of magnitude

(often refers to the order of power)

Solution: Only consider the relationship between the number of loops in the deepest loop and n

Worst time complexity

average time complexity

When evaluating algorithms, only consider these two

best time complexity

space complexity

It is defined as the storage space consumed by this algorithm, which is a function of problem size n, S(n)=O(g(n))

Algorithms work in place

The memory space required by the algorithm is constant, S(n)=O(1)

calculate

Ordinary program

Find variables related to the size of the space occupied and the size of the problem

Analyze the relationship between the occupied space x and the problem size n: x=f(n)

The order of magnitude O(x) of x is the algorithm space complexity S(n)

recursive program

Find the relationship between the depth of the recursive call x and the problem size n: x=f(n)

The order of magnitude O(x) of x is the algorithm space complexity S(n)

Note: The storage space required for functions at each layer of the algorithm is different. If the above rules are not met, additional analysis is required.

linear data structure

linear table

logical structure

Definition of linear table

Same data type, finite sequence

Table length, empty table

Table header, table footer

precursor, successor

order

Bit order starts from 1, array subscript starts from 0

Basic operations of linear tables

initialization table

InitList(&L)

destroy operation

&DestroyList(&L)

insert operation

ListInsert(&L,i,e)

Delete operation

ListDelete(&L,i,&e)

Find by value

LocateElem(&L,e)

Bitwise search

GetElem(&L,i)

Other common operations

Ask for table length

Length(L)

Output operations

PrintList(L)

short operation

Empty(L)

Notice: ①Operation of data (memory mode) -> creation, destruction, addition, deletion, modification and search; ②The naming must be readable; ③The modification results of the parameters need to be "brought back", and the reference "&" of the parameters must be passed in

Implementation of linear table

Storage structure (physical structure)

Sequence table (sequential storage)

definition

Adjacent logically and physically

sizeof(ElemType): Get the size of a data element

accomplish

static allocation

There is "dirty data" left in the memory; when initializing the sequence table, length must be assigned to 0

dynamic allocation

C language dynamically applies for and releases memory space

The header file where the malloc and free functions are located: #include<stdlib.h>

malloc function

L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);

The data pointer points to the starting address of an entire allocated continuous storage space.

free function

free(ElemType *p)

C dynamically apply for and release memory space

new

L.data=new ElemType(InitSize);

delete

Features

① Random access

Can find the i-th element in O(1) time

②High storage density

Each node stores only data elements

③It is inconvenient to expand the capacity

④ Insertion and deletion operations are inconvenient

Need to move a lot of elements

Basic operations

Pay attention to the relationship between bit order and array subscripts

insert

time complexity

Best case: insert to the end of the table

Best time complexity = O(1)

Worst case scenario: plug into the header

Worst time complexity = O(n)

average situation

delete

[Gallery: Insert operation]

time complexity

Find

Bitwise search

[Gallery: Search by bit]

Time complexity: O(1)

Find by value

In C language, structure comparison cannot use "==" directly.

[Gallery: Search by value]

time complexity

Linked list (linked storage)

nonlinear data structures