文档介绍：第一章概论
第一章概论
一、教学内容:
1、数据结构基本概念 数据、数据元素、数据对象、数据类型和数据结构等概念
2、算法及算法分析 算法的概念及特征;衡量算法的性能标准;时间空间复杂度度量
2
第一章概论
二、教学要求:
1、了解数据、数据元素、数据对象、数据类型、数据结构、数据的逻辑结构与数据的物理结构概念及逻辑结构与物理结构间的关系
2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价
3、掌握计算语句频度和估算算法时间复杂度的方法
3
第一章概论
什么是数据结构 数据结构的基本概念 算法和算法分析
什么是数据结构
一、为什么要学习数据结构?
电子计算机的主要用途:
早期:
主要用于数值计算。
后来:
处理逐渐扩大到非数值计算领域(能处理多种复杂的具有一定结构关系的数据)。
5
数值计算解决问题的一般步骤:
数学模型→选择计算机语言→编出程序→测试→最终解答
数值计算的关键是:如何得出数学模型(方程)?
程序设计人员比较关注程序设计的技巧。
非数值计算问题:
数据元素之间的相互关系一般无法用数学方程式加以描述
解决问题的关键:合适的数据结构及有效的算法
6
数据结构讨论的范畴。
尼克莱斯·沃思( Niklaus Wirth )
在计算机领域人尽皆知的名言
Algorithm + Data Structures = Programs
程序设计:
算法:
数据结构:
为计算机处理问题编制一组指令集
处理问题的策略
问题的数学模型
7
非数值计算问题:
例1 电话号码查询问题
(1) 按顺序存储方式:
8
需遍历表
要写出好的查找算法,取决于这张表的结构及存储方式。
电话号码表的结构和存储方式决定了查找(算法)的效率。
(2) 按姓氏索引方式:
索引
——线性表结构
非数值计算问题:
例2 田径赛的时间安排问题:
——无向图的着色问题
设有六个比赛项目,规定每个选手至多可参加三个项目,有五人报名参加比赛(如下表所示)设计比赛日程表,使得在尽可能短的时间内完成比赛。
姓名
项目1
项目2
项目3
丁一
跳高
跳远
100米
马二
标枪
铅球
张三
标枪
100米
200米
李四
铅球
200米
跳高
王五
跳远
200米
9
非数值计算问题:
田径赛的时间安排问题解法
设用如下六个不同的代号代表不同的项目:
跳高跳远标枪铅球 100米 200米
A B C D E F
用顶点代表比赛项目
不能同时进行比赛的项目之间连上一条边。
某选手比赛的项目必定有边相连(不能同时比赛)
10