数据结构与软件工程.
数据结构与软件工程
信息科学与技术学院 郝矿荣
E-mail: krhao@
1
数据结构与软件工程
教材及参考书目: • 数据结构(C语言版) 严蔚敏等编 清华大学出版社 • 数据结构习题集(C语言版) 严蔚敏等编 清华大学出版社 • 数据结构C++语言描述 刘卫东等译 清华大学出版社
18
1.1 什么是数据结构
例1. 电话号码查询系统 设有一个电话号码薄,它记录了N个人的名字和其相 应的电话号码,假定按如下形式安排: (a1, b1)(a2, b2)…(an, bn) 其中,ai, bi(i=1, 2, …, n) 分别表示某人的名字和对应 的电话号码 要求:设计算法,给定某人的名字,打印出此人的电 话号码;如果无此人,则报告无此人的标志
2
数据结构与软件工程
预备知识: • C语言 • 程序设计的基本技术 • 离散数学 • 概率论
3
数据结构与软件工程
计算机三级偏硬: • 计算机原理 60% • 数据结构 30% • Internet等 10% 研究生入学考试的核心课程
4
数据结构与软件工程
“数据结构”所处的地位
ห้องสมุดไป่ตู้
5
数据结构与软件工程
1.1 什么是数据结构
二、数据结构 Niklaus Wirth: Algorithms + Data Structures = Programs 程序设计: 为计算机处理问题编制一组指 令集 算法:处理问题的策略 数据结构:问题的数学模型
15
1.1 什么是数据结构
二、数据结构 从数学模型上分: • 数值问题(数学方程),如: 桥梁结构的应力分析模型——线性方程组 人口增长模型——微分方程 全球天气预报 ——环流模式方程 • 非数值问题(集合、线性表、树、图等) 无法用数学方程加以描述
13
1.1 什么是数据结构
二、数据结构 1、用计算机解决问题的步骤:具体问题—建立 数学模型—设计算法—编制程序—测试和调 整—最终答案 • 建立数学模型(关键):分析问题、提取操 作对象、找出对象间关系,对此用数学语言 加以描述 • 算法设计:利用建立的数学模型,根据具体 问题,设计出解决问题的方法 14
20
1.1 什么是数据结构
例2. 图书馆的书目检索系统自动化问题(线性结构) 图书馆的一本图书由书名、作者、出版社等数据来 描述,根据需要我们选择其中的若干项组成一个数 据元素来对应一本书 图书馆的编目表反映了书与书之间的关系,是数据 元素之间的结构。当然我们还应注意到书是具体地 放在某个书架上的,它是编目表的物理实现 图书馆从两方面管理图书:物理的藏书和逻辑的编 目表。这就是图书馆的结构。和图书馆一样计算机 管理数据,也有两个方面:即物理的存储和逻辑的 关系
1)信息的表示和组织:直接关系到处理信息 的程序的效率; 2)信息的处理:面向系统程序和应用程序的 大规模和复杂结构 12
1.1 什么是数据结构
一、数据结构形成和发展背景
计算机的飞速发展及其应用范围的迅速扩展 计算机处理的对象由纯粹的数值发展到字符、 表格和图像等各种具有一定结构的数据 编制“好”的程序要求分析待处理的对象以 及各处理对象之间存在的关系
16
1.1 什么是数据结构
二、数据结构
非数值计算的程序设计问题 例1: 求一组(n个)整数中的最大值 算法: 基本操作是“比较两个数的大小” 例2:计算机对弈 算法:对弈的规则和策略 例3:协会会员注册系统 算法:需要管理的项目?如何管理?用户界面? 模型:?
17
1.1 什么是数据结构
二、数据结构 2、数据结构主要关心的: • 结构中各元素之间逻辑关系(数学模型) 线性结构:如图书馆的书目索引 树形结构:见后面例子 图形结构:见后面例子 • 结构中各元素的存储方式 • 结构具有的行为特征(其上的操作) 在计算机中的表示和实现
高等数学 001,003,… 理论力学 002,… 线性代数 004,… ... ...
21
1.1 什么是数据结构
1 2 3 4 … ¸ ß À í ¸ ß Ï ß … µ È Û Â È µ Ô Ð Ê ý ¦ Á ý Ê ú ´ Ñ § § Ñ § Ñ ý Ê ·Ó ® ³ Þ Ô Â ¶ ª Â » Þ ï È è ê … ´ ¨ é Ï ý ¸ é Ê S01 L01 S01 S02 … … … … …
要求: • 上课认真听课 • 作业按时完成 • 上机实习认真,按质按量完成
6
数据结构与软件工程
第一章 绪 论 第六章 树与二叉树
第二章
第三章 第四章
线性表
栈和队列 串
第七章
第八章 第九章
图
动态存储管理 查找
第五章
数组与广义表
第十章
内部排序
7
第一章 绪
论
目的: 了解数据结构的背景 掌握一些基本概念和术语 掌握抽象数据类型的定义、表示与实现 描述算法的类C语言 掌握算法分析的一些基本方法
8
第一章 绪
论
重点: 有关数据结构的基本概念和术语 掌握抽象数据类型 ADT 的定义、表示与 实现 熟悉类C语言的书写规范 理解算法五个要素的确切含义 掌握估算时间复杂度的方法,了解空间 复杂度的度量方法
9
第一章 绪
论
难点: 抽象数据类型ADT的表示与实现 算法复杂度的分析方法
19
1.1 什么是数据结构
算法的设计,依赖于计算机如何存储人的名字和对应
的电话号码,或者说依赖于名字和其电话号码的结构 数据的结构,直接影响算法的选择和效率 上述问题是一种数据结构问题。可将名字和对应的 电话号码设计成:二维数组、表结构、向量 1) 假定名字和其电话号码逻辑上已安排成N元向量 的形式,它的每个元素是一个数对(ai, bi),1≤i≤n 2) 数据结构还要提供每种结构类型所定义的各种运 算的算法
10
第一章 绪 论
1.1 1.2 1.3 1.4 什么是数据结构 基本概念和术语 抽象数据类型的表示与实现 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求
11
1.1 什么是数据结构
一、数据结构形成和发展背景
计算机是一门研究用计算机进行信息表示和 处理的科学 两个问题: