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 Data structure C language version

Data structure C language version

Introduction to Chapter 1 of Data Structure C Language Edition 2nd Edition, which introduces the research content of 1.1 data structure, 1.2 Basic concepts and terminology of data structures, 1.3 Representation and implementation of abstract data types, etc.

Edited at 2024-04-21 17:36:01

PlotWizard

Recent works View more works>>

Data structure C language version

PlotWizard

Recent works View more works>>

Recommended to you
Outline

introduction

1.1 Research content of data structure

Data structure is a core course between mathematics, computer hardware and software

Student status management system: one-to-one linear relationship

Human-computer chess problem: one-to-many tree structure

Shortest path problem: many-to-many mesh structure

1.2 Basic concepts and terminology of data structures

1.2.1 Data, data elements, data items and data objects

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

Data Element is the basic unit of data and is usually considered and processed as a whole in computers.

Data Item is the smallest indivisible unit that constitutes a data element and has independent meaning.

Data Object is a collection of data elements with the same properties and is a subset of data.

1.2.2 Data structure

logical structure

Set structure There is no other relationship between data elements other than the relationship of "belonging to the same collection"

linear structure There is a one-to-one relationship between data elements

tree structure There is a one-to-many relationship between data elements

graph structure or mesh structure There is a many-to-many relationship between data elements

storage structure

sequential storage structure

chain storage structure

1.2.3 Data types and abstract data types

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

Abstract Data Type (ADT) generally refers to a mathematical model defined by the user to represent an application problem, and the general name of a set of operations defined on this model. It specifically includes three parts: data objects and relationships on data objects. A collection of data objects and a collection of basic operations on data objects.

1.3 Representation and implementation of abstract data types

(1) Predetermined constants and types (2) The representation of the data structure (storage structure) is described by a type definition (typedef); the data element type is agreed to be ElemType, which is defined by the user when using this data type. (3) The basic operation algorithms are described by functions in the following format. (4) Dynamic allocation and release of memory. (5) Assignment statement (6) Selection statement (7) Loop statement (8) End statement (9) Input and output statements use C + streaming input and output form (10) Basic functions

1.4 Algorithms and algorithm analysis

1.4.1 Definition and characteristics of algorithm

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

(2) Certainty. The operations that should be performed in each case are clearly specified in the algorithm, and there will be no ambiguity. The executor or reader of the algorithm can clearly understand its meaning and how to perform it.

(3) Feasibility. All operations in the algorithm can be implemented by executing the already implemented basic operations a finite number of times.

(4) Input. An algorithm has 0 or more inputs. When describing an algorithm as a function, the input is often represented by formal parameters, whose values are obtained from the calling function when they are called.

(5) Output. An algorithm has one or more outputs, which are the results of information processing by the algorithm. An algorithm without output has no meaning. When using functions to describe algorithms, the output is often represented by return values or formal parameters of reference types.

1.4.2 Basic criteria for evaluating the quality of algorithms

(1) Correctness. With reasonable data input, correct results can be obtained within a limited running time.

(2) Readability. A good algorithm should first be easy for people to understand and communicate with each other, and secondly, it should be machine executable. Readable algorithms help people understand the algorithm, while difficult-to-understand algorithms tend to hide errors and are difficult to debug and modify.

(3) Robustness. When the input data is illegal, a good algorithm can respond appropriately or handle it accordingly without producing some inexplicable output results.

(4) Efficiency. Efficiency includes both time and space aspects. Time efficiency means that the algorithm is reasonably designed and has high execution efficiency, which can be measured by time complexity; space efficiency means that the storage capacity occupied by the algorithm is reasonable, and can be measured by space complexity. Time complexity and space complexity are the two main indicators for measuring algorithms.

1.4.3 Time complexity of the algorithm

1. Question size and statement frequency

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

The problem size is the amount of input required by the algorithm to solve the problem. It is the essential representation of the size of the problem and is generally represented by an integer n.

2. Time complexity definition of algorithm

In general, the number of repeated executions of the basic statements in the algorithm is a function An) of the problem size n, and the time measurement of the algorithm is recorded as: The frequency is T(n)=O((n)) FrequencyA It means that as the problem size n increases, the growth rate of the algorithm execution time is the same as the growth rate of (n), which is called the asymptotic time complexity of the algorithm, or time complexity for short.

3. Examples of time complexity analysis of algorithms

[Example 1.5] Example of constant order. [x ;s=0;) Both sentences have a frequency of 1

[Example 1.6] Linear order example. for(i=0;i<n;i )(x ;s=0;) consider The frequency of the two basic statements in the loop body is A(n)=n, so the time complexity of the algorithm is T(n)=O(n), which is called linear order.

[Example 1.7] Square order example. Calculate (1) x=0;y=0; (2) for(k=1;k<=n;k) n) (3) x; (4) for(i=1;i<=n;i) (5) for(j=1;j<=n;j ) (6) y; For loop statements, we only need to consider the number of executions of the statements in the loop body. The most frequent statement in the above program segment is (6), and its frequency is f(n)=n2, so the time complexity of the algorithm is T(n )=O(n2), called square order.

4. Best, worst and average time complexity

The time complexity of an algorithm in the best case is called the best time complexity, which refers to the minimum possible calculation amount of the algorithm; the time complexity of the algorithm in the worst case is called the worst time complexity, which means that the algorithm The maximum possible amount of calculation; the average time complexity of an algorithm refers to the weighted average of the algorithm's calculation amount when the input instances appear with equal probability under all possible circumstances.

1.4.4 Space complexity of the algorithm

Regarding the storage space requirements of the algorithm, similar to the time complexity of the algorithm, we use asymptotic space complexity (Space Complexity) as a measure of the storage space required by the algorithm, referred to as space complexity. It is also a function of the problem size n, denoted as : one of Basic S(n)=O(f(n))