数据结构(C语言版)教学指导：第1章 绪论及C语言介绍

数据结构——C语言描述（慕课版）
第1章 绪论
编著：张同珍 & 学校： 上海交通大学
绪论
数据结构定义 逻辑结构 基本操作
存储结构 算法 算法的时空复杂度
数据结构：
数据是外界信息进入计算机，并被计算机处理的符号，数据元素是数据的基本单位。 如有一组学生信息，每个学生信息是一个结构类型数据，包含了学号、姓名、年龄等 字段，那么这组学生信息是数据，每一个学生信息是数据元素。
关系操作（或称基本操作）
是和数据的逻辑结构紧密相关的，它来源于关系自身的特点。
基本操作都可以分为五大类：构造类、属性类、数据操纵类、遍历类、典型应用类。
构造类：在内存中建立这种数据结构。如一个空的队列。 属性类：对元素及元素之间的关系的各类查询。 属于东瞧瞧、西看看，不影响元 素及元素关系本身。 数据操纵类：对元素或元素关系有改变的操作，如插入或删除某个元素。修改 可视作删除后插入。 遍历类：对结构中的每个元素访问且只访问一遍。 典型应用类：所属结构独特的应用，不同结构其典型应用各不相同。
数据的逻辑结构+基本操作=抽象数据类型ADT（Abstract Data Type）。
ADT和在计算机内的表示、实现无关，只和数据自身的逻辑特征相关。
ADT类似高级语言中的数据类型，如整型: 一个整数集合以及在这个集合中系统支持的 基本操作（四则运算、比较运算等）。
ADT区别于具体某种类型，只关心元素关系和关系操作，不实际要求数据的具体类型， 只要元素类型一致。 ADT的描述可以用自然语言也可以用伪代码，其内容包含元素集合、元素关系集合、 基本操作。
算法的执行时间，应能满足问题解决的时间 容忍要求。 如实时系统对处理时间有一个及 时性反应的要求。执行时间越短，算法的时 间效率越高。

存储结构（物理结构）---运算（算法）
23
数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机语言。
1.2 基本概念和术语
数据结构的三个方面： 线性结构
数据的逻辑结构 非线性结构 数据的存储结构
24
线性表 栈 队 树形结构
图形结构
顺序存储
链式存储
数据的运算：检索、排序、插入、删除、修改等
26
四个基本结构
•
集合 线性结构 树形结构
•
•
•
网状结构
27
线性结构
bin
dev
etc
lib
user
树形结构
树
3 1 2
2 5
二叉树
2
二叉排序树
1
9 3 6 3
1 13
4
6 7 8 9 10
4
7 8
5 9
6
8 5 7
10
11 12 13 14
11
28
堆结构
11
7 3 5 10 4 8
12 9 6
定义2----
22
按某种逻辑关系组织起来的一批数据（或称带结构 的数据元素的集合）应用计算机语言并按一定的存储 表示 方式把它们存储在计算机的存储器中，并在其上 定义了一个运算的集合。
1.2 基本概念和术语
数据结构的三个方面的含义：
逻辑结构--数据元素间抽象化的相互关系（简称为数据结构）。 与数据的存储无关，独立于计算机，它是从具体问题抽 象出来的数学模型。
按书名
S 0 1 L 0 1 S 0 1 S 0 2 … …
索引表
分类号： 高 等 数 学 0 0 1 ， 0 0 3 … … 樊映川 出版单位： 理 论 力 学 0 0 2 ， … … . . 华罗庚 出版时间： 线 性 代 数 0 0 4 ， … … 栾汝书 价格： … …… … . .

31
4、效率与低存储量需求 、
通常，效率指的是算法执行时间；存储量指的是 算法执行过程中所需要的最大存储空间。两者都 与问题的规模有关。
32
算法效率的衡量方法和准则
通常有两种衡量算法效率的方法： 事后统计法 缺点：1、必须执行程序 2、其它因素掩盖算法本质 事后分析估算法 和算法执行时间相关的因素： 1算法选用的策略 2、问题的规模 3、编写程序的语言 4、编译程序产生的机器代码的质量 5、计算机执行指令的速度
5
–例
书目自动检索系统
线性表
书目文件
书目卡片 001 高等数学 樊映川 002 理论力学 罗远祥 登录号： 003 高等数学 华罗庚 004 书名： 线性代数 栾汝书 …… 作者名： …… ……
按书名
高等数学 理论力学 线性代数 ……
S01 L01 S01 S02 ……
索引表
按分类号
分类号： 001， 003… … 樊映川 出版单位： 002， … … .. 华罗庚 出版时间： 004， … … 栾汝书 价格： … … ..
29
2、可读性 、
算法主要是为了人的阅读与交流，其次才是为计 算机执行。因此算法应该易于人的理解；另一方 面，晦涩难读的程序易于隐藏较多错误而难以调 试；
30
3.健壮性 健壮性
当输入的数据非法时，算法应当恰当地作出反映 或进行相应处理，而不是产生莫名奇妙的输出结 果。并且，处理出错的方法不应是中断程序的执 行，而应是返回一个表示错误或错误性质的值， 以便在更高的抽象层次上进行处理。
23
1.3 算法和算法分析
算法的概念和描述： 算法的概念和描述： 什么是算法？ 什么是算法？ 算法（ 算法（Algorithm)是为了解决某类问题而规定的一 是为了解决某类问题而规定的一 个有限长的操作序列。 个有限长的操作序列。一个算法必须满足以下五 个重要特性： 个重要特性：

第 1章 绪 论
4. 数据结构（Data Structure） 数据结构（ ） 数据结构是指相互之间存在一种或多种特定关系的数据元 素集合
学校
系
处
研究机构
教研室
实验室
学校组织层次结构图
第 1章 绪 论
5. 数据类型 数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值集 合上的一组操作的总称。数据类型中定义了两个集合，即该 类型的取值范围，以及该类型中可允许使用的一组运算。例 如高级语言中的数据类型就是已经实现的数据结构的实例。 从这个意义上讲，数据类型是高级语言中允许的变量种类， 是程序语言中已经实现的数据结构（即程序中允许出现的数 据形式）。在高级语言中，整型类型可能的取值范围是-32 768~+32 767， 可用的运算符集合为加、 减、 乘、 除、 乘方、 取模（如C语言中+， -， *， /， %）。
第 1章 绪 论
2） 可读性 ） 3） 健壮性 ） 4） 高效率和低存储要求 ）
第 1章 绪 论
算法描述的工具
1. 算法、 语言和程序的关系 算法、 语言和程序的关系 (1) 算法： 描述了数据对象的元素之间的关系（包括数 据逻辑关系、 存储关系描述）。 (2) 描述算法的工具：算法可用自然语言、框图或高级 程序设计语言进行描述。 自然语言简单但易于产生二义， 框图直观但不擅长表达数据的组织结构， 而高级程序语言 则较为准确但又比较严谨。 (3) 程序是算法在计算机中的实现（与所用计算机及所 用语言有关）。
第 1章 绪 论

3. 算法设计的要求 １） 算法的正确性 (1) 所设计的程序没有语法错误； (2) 所设计的程序对于几组输入数据能够得出满足要求的 结果； (3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难 性的几组输入数据能够得到满足要求的结果。 (4) 程序对于一切合法的输入数据都能产生满足要求的结 果。