01 第01章 数据结构-C#语言描述绪论.pptx

第1页：第一章绪论封面

本页为《数据结构(C#语言描述)》第一章绪论封面，本章从什么是数据结构讲起，依次展开数据与数据结构的定义、数据的逻辑结构与存储结构，并给出算法及算法分析的基本方法。

第2页：什么是数据结构

随着计算机日益普及，人类社会已经进入以信息化为标志并飞速发展的时代。数据作为信息的载体，需要由计算机处理的数据量不断增大，数据类型也随之增多，不再局限于单纯的数值数据，更多的是用于表示文字、图像、声音等非数值数据。

在数据类型增多的同时，数据结构也更加复杂。因此，大多数的计算机程序不单要完成运算，还要进行数据的存储、检索和处理。

第3页：线性表：学生信息表

本页以表 1.1 学生信息表为例说明线性表这种数据结构：表中每一条学生记录作为一个数据元素依次排列，除首末元素外每个元素都有唯一的前驱和后继，元素之间是严格的一对一关系。

该表为图片，正文未提取到表内字段与记录数据，具体信息请对照原课件图示查看。

第4页：树形结构：文件系统

本页用图 1.1 文件系统结构图说明树形结构：根目录之下的各级子目录与文件构成明显的层次，上层结点可以对应多个下层结点，呈现一对多的关系。

树形结构是编译系统、数据库索引与各类目录管理中广泛使用的数据结构。

第5页：图形结构：公路运输网

本页用图 1.2 部分城市公路运输网络图说明图形结构：任意两个城市之间都可能存在直达线路，一个顶点可以有多个前驱和多个后继，元素之间是多对多的关系。

相比线性表和树，图形结构是约束最少、表达能力最强的一类非线性结构。

第6页：数据结构的产生与发展

迄今为止，程序设计经历了三个阶段：

1. 无结构阶段
2. 结构化程序设计阶段
3. 面向对象技术

数据结构正是伴随着程序设计方法的演进而不断发展与体系化的。

第7页：数据和数据结构

数据

客观事物的符号表示，在计算机科学中指能输入计算机并能由计算机程序进行处理的符号总称

数据元素

数据的基本单位，在程序中通常作为一个整体来考虑和处理

数据对象

性质相同的数据元素的集合，是数据的一个子集

数据结构

相互之间存在一种或多种特定关系的数据元素的集合

第8页：数据的逻辑结构

数据元素之间的关系称为结构。根据数据元素之间关系的不同特性，通常有下列四种基本结构形式：

• 集合关系（图 1.3）：元素之间除同属一个集合外无其他关系
• 线性关系（图 1.4）：元素之间一对一
• 树形关系（图 1.5）：元素之间一对多
• 图状关系（图 1.6）：元素之间多对多

第9页：数据结构的组成部分

数据结构在形式上可以定义为一个二元组：数据结构 = <数据对象，关系>，记为 Data_Structure =（D，S）。

D

数据元素的有限集

S

D 上关系的有限集

第10页：数据的存储结构

数据结构在计算机中的存储方式称为数据的物理结构，又称存储结构。它包含数据元素及数据元素之间关系的表示，不同于逻辑结构，是依赖于计算机语言的、具体的。

通常，在计算机内数据元素用一组连续的二进制位串来表示，位串称为结点。结点之间的关系，即数据元素之间的关系，在计算机内有四种基本的存储表示方法：

1. 顺序存储结构
2. 链式存储结构
3. 索引存储方法
4. 散列存储方法

第11页：数据类型

高级程序语言中的数据类型可以分为两类：

原子类型

值不可分解，例如 C# 语言中的字符型、整型、浮点型等

结构类型

值由若干成分按某种结构组成，例如 C# 语言中的数组，其分量可以是整型、字符型等原子类型，也可以是数组

第12页：算法及其特性

算法（Algorithm）是对特定类型的问题的求解步骤的一种描述，是指令的有限序列。算法具有下列特性：

1. 确定性（Unambiguousness）
2. 可行性（Realizability）
3. 有穷性（Finity）
4. 输入（Input）
5. 输出（Output）

第13页：算法设计的目标

设计一个“好”的算法应考虑达到以下几个目标：

1. 正确性（Correctness）
2. 可读性（Readability）
3. 健壮性（Robustness）
4. 效率与低存储量需求

第14页：算法的时间复杂度

算法的时间复杂度（Time Complexity）又称为计算复杂度（Computational Complexity），是算法有效性的度量之一。

不管是简单还是复杂的算法，都必须经过编译后分解成基本操作来具体执行，每个算法都对应一定的基本操作次数。基本操作次数越少，运行时间相对越少；次数越多，运行时间相对越多。所以通常用它来衡量算法的运行时间性能或计算性能。

第15页：例1.5 求1到n的整数和

例 1.5 求 1 到 n 的整数和，逐行统计基本操作的执行次数：

• int sum=0; 执行 1 次
• int i=1; 执行 1 次
• i<=n 判断执行 n+1 次
• i++ 执行 n 次
• 循环体内 sum += i; 执行 n 次

基本语句共执行 3n+3 次。

第16页：时间复杂度的数量级

分析算法的运行时间相当繁琐，实际上不一定要精确计算运行时间，只要计算出相应的数量级（Order）即可。

一般情况下，算法的运行时间 T 是问题规模 n 的函数 f（n），算法的时间度量记作 T（n）= O（f（n））。

例如例 1.5 中的算法，只要确定 for 循环中的基本操作被执行的次数 n，就可以求出时间复杂度为 O（n）。

第17页：算法的空间复杂度

空间复杂度（Space Complexity）是对一个算法在运行时占用存储空间大小的度量，也是衡量算法有效性的重要因素。分析算法性能时，不单需要分析运行时间，还要分析所采用的数据结构占用的空间。

存储空间包括内存和外存，一般用字节作为空间的基本度量单位。问题规模为 n 时，算法所需的空间单元数 S 一般是 n 的函数 f（n），记作 S（n）= O（f（n））。