数 据 结 构 授 课： 课件制作： 单 位： 曾翎 杨鹏 应用数学学院.

Presentation on theme: "数 据 结 构 授 课： 课件制作： 单 位： 曾翎 杨鹏 应用数学学院."— Presentation transcript:

1 数 据 结 构 授 课： 课件制作： 单 位： 曾翎 杨鹏 应用数学学院

2 数 据 结 构 简 介 数据结构是计算机及其相关专业的核心课程。 学会分析研究计算机加工的数据结构的特性，以
便为应用的数据选择适当的逻辑结构和存储结构和算 法，并初步掌握算法的时间分析和空间分析的技术。 学习本课程的过程也是复杂程序设计的训练过程。 学 时: 56 学时 上机时间: 8 学时 教 材: 数据结构(C语言) 严蔚敏 吴伟民 编著

3 数据结构重要性  编程基础  考研课程  计算机等级考试课程  程序员考试课程

4 第一章 绪 论 1.1数据结构的定义和地位 1.2数据结构的基本术语 1.3算法和算法分析

5 N.沃思（Niklaus Wirth)教授提出：
§1.1 数据结构的定义和地位 什么是程序、软件？ N.沃思（Niklaus Wirth)教授提出： 程序=算法+数据结构 以上公式说明了如下两个问题： （1）数据上的算法决定如何构造和组织数据（算法→数据结构）。 （2）算法的选择依赖于作为基础的数据结构（数据结构→算法）。 软件=程序+文档（软件工程的观点）

6 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题： 数据元素之间的相互关系一般无法用数学方程加以描述。 例1.1 电话号码查询问题： （1）按顺序存储方式：遍历表 （2）按姓氏索引方式：要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。

7 例1.2 田径赛的时间安排问题（无向图的着色问题） ：
设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。 姓名 项目1 项目2 项目3 丁一 跳高 跳远 100米 马二 标枪 铅球 张三 200米 李四 王五

8 （1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目
田径赛的时间安排问题解法： （1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。 A E B F D C 姓名 项目1 项目2 项目3 丁一 A B E 马二 C D 张三 F 李四 王五 结论：安排四各比赛时间 1（A,C）,2（B,D）,3（E）,4（F）

9 例1.3 人机对弈：树形结构 …….. …...

10 数据结构作为一门独立的课程在国外从1968年开始设立。 数据结构介于数学、计算机硬件和计算机软件三者之间的一门核心学科。
数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 数据结构作为一门独立的课程在国外从1968年开始设立。 数据结构介于数学、计算机硬件和计算机软件三者之间的一门核心学科。 在计算机科学中，数据结构不仅 是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序设计的重要基础。

11 §1.2 数据结构的基本术语 1.数据,数据对象和数据元素 数据是对客观事物的符号表示，是指计算机能处理的符号的总称。 (其他定义类似见书)
2.数据结构 数据结构（Data Structure)是相互之间存在一种或多种特定关系 的数据元素的集合。通常有四种结构： 　　　（１）集合 　　　（２）线形结构 　　　（３）树型结构 　　　（４）图状结构或网状结构

12 逻辑结构:数据元素间抽象化的相互关系（即数据结构） 与数据的存储无关，独立于计算机，它是从具体问题 抽象出来的数学模型。
3.逻辑结构和物理结构 逻辑结构:数据元素间抽象化的相互关系（即数据结构） 与数据的存储无关，独立于计算机，它是从具体问题 抽象出来的数学模型。 物理结构（存储结构）: 数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机语言。 小结: (1)数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。 (2)程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。

13 抽象数据类型（Abstract Data Type) 是指一个数学模型以及定义在该模型上的一组操作。
4.数据类型 抽象数据类型（Abstract Data Type) 是指一个数学模型以及定义在该模型上的一组操作。 　　ＡＤＴ　抽象数据类型｛ 　　　　　　数据对象：＜数据对象的定义＞ 　　　　　　数据关系：＜数据关系的定义＞ 　　　　　　数据操作：＜数据操作的定义＞ 　　｝ＡＤＴ　抽象数据类型名 5.算法 所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。

14 §1.3 算法和算法分析 一、算法的表示和实现： 描述---可采用自然语言、数学语言或约定的符号语言。
实现---必须借助程序设计语言提供的数据类型及其运算 本课的描述---采用类C语言。 二、算法的定义和特性： 有穷性: 执行了有限条指令后一定要终止。 确定性:算法的每一步操作都必须有确切定义，不得有任何歧义性。 可行性:算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。 输入:一个算法有n（n>=0)个初始数据的输入。 输出:一个算法有一个或多个与输入有某种关系的有效信息的输出。 思考题:算法和程序主要区别是什么?

15 三、算法设计的要求： 正确性 （1）不含语法错误 （2）程序对于n组输入数据能够得出满足规格说明要求的结果。 （3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。 （4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。 可读性 健壮性 效率与存储需求。

16 四、算法的度量： 1.程序运行所耗费的时间(由下列因素决定)： 算法所选用的策略 问题的规模 书写程序所采用的语言 编译程序所产生的机器代码的质量 机器执行指令的速度 一个算法耗费的时间=算法中每条语句的执行时间之和。 若不考虑机器硬、软件因素，可以认为算法“运行工作量”的大小是问题规模的函数。

17 评价一个算法的时间性能，主要标准是算法的渐近时间复杂度
四、算法的度量： 2.问题的规模（size)---n 算法求解问题的输入量（或初始数据量）。 3.不考虑机器软硬件环境时算法的时间耗费： 设：执行每条语句所需时间为单位时间，则： 一个算法耗费的时间=所有语句的频度之和。 时间复杂度T(n)--- 即：时间耗费，它是算法求解问题n的函数。 渐近时间复杂度--- 即当问题的规模n→∞时的时间复杂度T(n)的数量级（阶），记作：T(n)=O(f(n)) 评价一个算法的时间性能，主要标准是算法的渐近时间复杂度

18 (渐进）时间复杂度：T(n)=O(f(n)) （渐进）空间复杂度：S(n)=O(f(n))
四、算法的度量： 4.算法度量主要指标 频度：语句在算法中重复的次数。 (渐进）时间复杂度：T(n)=O(f(n)) （渐进）空间复杂度：S(n)=O(f(n)) 频度 1 n n-1 时间复杂度： T(n)=O(f(n))=O(3n-1)=O(n) 例. i=1; while (i<n) {x=x+1; i=i+1;} 空间复杂度： S(n)=O(f(n))=O(3)=O(1)

19 四、算法的度量： 例1. x=0; for(i=1;i<=n;++i) for(j=1;j<=n;++j)
for(k=1;k<=n;++k) ++x; 例 scanf(&x); i=0; while(i<n&&a[i]==x) ++i;

20 思考题： 计算下列程序中每条语句的频度： 1. count=1; for(i=1;i<=n;i++)
for(j=1;j<=i;j++) for(k=1;k<=j;k++) count++; 2. i=n;j=0; while (i>(j+1)*(j+1)) j++;

21 例、储油点问题 一辆重型卡车欲穿过1000公里的沙漠，卡车耗油为1升/公里，卡车总载油能力为500升。因此司机必须设法在沿途建立几个储油点，使卡车能顺利穿过沙漠，试问司机如何建立这些储油点？每个储油点应存多少油，才能使卡车以消耗最少油的代价通过沙漠？ 设dis[i]   为第i个贮油点至终点(i=0)的距离；     oil[i]   为第i个贮油点的存贮油量；     我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。 下图表示倒推时的返回点：

22 从贮油点i向贮油点i+1倒推的策略是，卡车在点i和点i+1间往返若干次。卡车每次返回i+1处时正好耗尽500公升汽油，而每次从i+1出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下使i点贮足i*500分升汽油的要求(0<=i<=n-1)。 具体地讲，第一个贮油点i=1应距终点i=0处500km且在该处贮藏500公升汽油，这样才能保证卡车能由i=1处到达终点i=0处，这就是说     dis[1]=500        oil[1]=500; 为了在i=1处贮藏500公升汽油，卡车至少从i=2处开两趟满载油的车至i=1处。所以i=2处至少贮有2*500公升汽油，即oil[2]=500*2=1000。另外，再加上从i=1返回至i=2处的一趟空载，合计往返3次。三次往返路程的耗油量按最省要求只能为500公升。即d12=500/3km         dis[2]=dis[1]+d12=dis[1]+500/3

23 为了在i=2处贮存1000公升汽油，卡车至少从i=3处开三趟满载油的车至i=2处。报以i=3处至少贮有3
为了在i=2处贮存1000公升汽油，卡车至少从i=3处开三趟满载油的车至i=2处。报以i=3处至少贮有3*500公升汽油，即oil[3]=500*3=1500。加上i=2至i=3处的二趟返程空车，合计5次。路途耗油量也应为500公升，即d23=500/5,    dis[3]=dis[2]+d23=dis[2]+500/5;

24 依此类推，为了在i=k处贮藏k. 500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即 oil[k+1]=[k+1]
依此类推，为了在i=k处贮藏k*500公升汽油，卡车至少从i=k+1处开k趟满载车至i=k处，即     oil[k+1]=[k+1]*500=oil[k]+500，加上从i=k处返回i=k+1的k-1趟返程空间，合计2k-1次。这2k-1次总耗油量按最省要求为500公升，即     dk,k+1=500/(2k-1)         dis[k+1]=dis[k]+dk,k+1                 =dis[k]+500/(2k-1);

25 例、渡河问题 一个人带了一只狼、一只山羊和一棵白菜想要渡河。河上有一只独木船，每次除人外只能带一样东西，另外如果人不在时狼就要吃山羊，羊就要吃白菜。问应该怎样安排渡河，才能做到既把所有东西都带过河，而且在河上来回的次数又最少？ 设M代表人，W代表狼，S代表山羊，V代表白菜。

26 例、渡河问题 算法思想： 用集合表示在某岸上的所有情况（16种）：
[MWSV] [MWS] [MWV] [MSV] [WSV] [MW] [MS] [MV] [WS] [WV] [SV] [M] [S] [V] [空] 剩下的10种情况,按若甲经过一次渡河可变成乙,那么就在甲与乙之间连一条边,由此得到如下图G: MWSV MWS MWV MSV MS MS W S V 空 结论:在G中找一条连接顶点MWSV与空,并且包含边数最少的路.