数据结构1第1章：绪论

数据结构与算法

第 1章 绪 论

数据结构与算法Data Structures and Algorithm教学安排：讲课学时：44 实验学时：12,课程设计：18+1周

考核要求：期末考试占60%,实验成绩占30% ,平时作业占10% 本学期上课时间：1-12周,周二5-6节，周四5-6节. 致知24 考 课 试 程 时 间：14周 设 计：7-15周2015秋

Slide. 1 - 1

理论系列 数据结构与算法 第一 学期 第二 学期 工科数析Ⅰ 代数与几何 工科数析Ⅱ 离散数学

系统系列 计算机导论 数字逻辑 计算机组成技术 数据结构与算法

工具系列 第1 章 绪 论 程序设计语言 C++语言 程序设计实践 Java语言

工程系列

管理系列

其他课程 军训 大学外语 体育 政治 大学外语 体育

计算机职业道德交流技巧 IT企业管理

第三 学期

Linux操作系统*

市场营销软件工程概论 合同法

概率论与数理统计

操作系统 数据结构与算法 课程设计 数据库系统

面向对象技术 与UML

马哲 英语限选 体育

第四 学期

.Net J2EE 系统分析与设计 财务管理 英语限选 体育 英语口语

运筹学

数据库系统 课程设计 计算机网络 编译原理

软件开发实践用户界面设计 面向服务的 计算技术 服务学概论 软件开发过程管理 软件项目管理 中文信息处理 软件质量保证与测试 商务谈判 知识产权法 嵌入式操作系统

第五 学期 方向课 第六 学期

多核程序设计 计算机安全概论

英语限选 英语口语

算法设计与分析方向

软件外包开发技术*2)服务学与企业信息化

软件工程 综合课程设计 3)多媒体与信息处理

IT企业创业管理

英语限选

1)网络通信与信息安全

4)嵌入式系统与软件

第七学期 第八学期

毕业设计

2015秋

Slide. 1 - 2

数据结构与算法

第 1章 绪 论

物联网专业2015秋

Slide. 1 - 3

数据结构与算法

第 1章 绪 论

教 材数据结构与算法(第4版)编著 廖明宏 郭福顺 张岩 李秀坤

高等教育出版社

2015秋

Slide. 1 - 4

数据结构与算法

第 1章 绪 论

参考资料数据结构严尉敏 吴伟民 编著

清华大学出版社

2015秋

Slide. 1 - 5

数据结构与算法

第 1章 绪 论

引进教材Data Structures and Program Design in C++

数据结构与程序设计——C++语言描述(影印版) Robert L. Kurse, Alexandeer J. Ryba ISBN 7-04-010039-8/TP.691 P7362015秋

Slide. 1 - 6

数据结构与算法

第 1章 绪 论

教材比较

2015秋

Slide. 1 - 7

数据结构与算法

第 1章 绪 论

主要内容1.1 数据结构研究对象1.2 数据结构发展概况 1.3 抽象数据型(ADT)

1.4 数据结构 与 程序设计1.5 算法描述 与 算法分析2015秋

Slide. 1 - 8

数据结构与算法

第 1章 绪 论

1.1 数据结构研究对象◆计算机科学：信息在计算机内使用数据来表示, 研究信息表示和信息处理

。什么是数据？ ◆数据：是用以描述客观事物的数值、字符，以及一切可 以输入到计算机中并由计算机程序加以处理的符 号的集合。 数据的基本单位称为数据元素 数据的最小单位称为数据项

◆数据特征：数值、文本、多媒体、超媒体、实时、海量 ◆数据对象：性质相同的数据元素的集合◆数据类型? 高级语言中变量的取值范围和允许的操作2015秋

Slide. 1 - 9

数据结构与算法

第 1章 绪 论

大数据(big data)大数据可分成： 大数据技术：解决大数据为题的技术和方法 大数据工程：大数据工程指大数据的规划建设运营管理的系统工程； 大数据科学：大数据科学关注大数据网络发展和运营过程中发现和验证大数据 的规律及其与自然和社会活动之间的关系 大数据应用：

大数据的4个“V”: —Volume:数据体量巨大。从TB级别，跃升到PB级别； —Variety: 数据类型繁多。网络日志、视频、图片、地理位置信息等 —Value: 价值密度低。以视频为例，连续不间断监控过程中，可能有用的数据 仅仅有一两秒。 —Velocity:处理速度快，1秒定律。

2015秋

Slide. 1 - 10

数据结构与算法

第 1章 绪 论

李建中教授谈大数据第一，大数据的基本概念 第二，大数据计算及其挑战 第三，研究问题与部分解大数据无处不在：因特网有很多的大数据，在科学研究领域、医疗领域、商业领域、制造业、智慧城市都 有大量的数据。 全世界的感知数据增长率是每年58% 全世界拥有的存储能力或者是存储总量的增长率是每年只有40% 2007年，全世界的感知数据已经超过了全世界所拥有的存储器的容量 2010年，全世界的感知数据是1.25千万PB 大数据的输入是大数据D, 问题的解是f(D)。

2011年产生的感知数据已经二倍于我们人类所拥有的存储器的容量结论：大数据无处不在，数据量远远超出了现有的存储能力

2015秋

Slide. 1 - 11

数据结构与算法

第 1章 绪 论

◆结构：关系，组成整体的各部分的搭配和安排 ◆数据结构：数据元素彼此之间抽象的相互关系， 解决数据的 存储和组织的方式，不涉及数据元素的具体内容。 描述现实世界事物的数学模型及其操作在计算 机 中的表示和实现

◆数据结构分类：线性表：(a1,a2,a3,……ai-1,ai,ai+1……an-1,an) →线性结构 线性表的一般概念、字符串、数组，广义表等 树： 层次结构 二叉树，树等 图： 网状结构 有向图、无向图等 ① ② ③ ② ④2015秋

① ③有向图 Slide. 1 - 12

④ ⑤二叉树

数据结构与算法

第 1章 绪 论

2015秋

Slide. 1 - 13

数据结构与算法

第 1章 绪 论

资料：下棋程序 Blue Gene,

共装有32个并行处理器，速度

:2亿步棋 /秒

国际象棋：每次需要考虑的合乎规则的着法平均只有35 步“回合”,计算机预先分析7至8个回合的着 法。若设为7个回合，则有超过1亿亿亿个不 同的变化，经简化后，仍有500亿至600亿个 变化。多分析一步，增加18亿个变化 根据计算机“深蓝”的速度，平均5分钟走一步 围 棋：分析7个回合的着法，则需要考虑超过200的 14 次方个变化，经简化后，仍有1000亿亿个

变化。多分析一步，增加64万亿个变化 根据计算机“深蓝”的速度，平均1.5年走一步2015秋

Slide. 1 - 14

数据结构与算法

第 1章 绪 论

深蓝 vs 卡斯帕罗夫:第一次1996年：2月10日—17日， 第二次1997年：5月 3日—11日，双方先后共进行6局对弈 第一局，卡斯帕罗夫执白先行，经过3个多小时的苦战击败“深蓝”,力

比分2 : 4,卡斯帕罗夫赢 比分3.5 : 2.5

拔头筹；第二局，“深蓝”却以凌厉的攻势和明显的优势战胜卡氏，扳回一局； 第三、第四和第五局，双方下得异常激烈，鏖战数小时，平局； 第六局，“深蓝”执白先行，一路强攻，仅用一个多小时， 双方仅走19步，就让卡氏俯首称臣，取得了决定性的胜利。2015秋

Slide. 1 - 15

数据结构与算法

第 1章 绪 论

许峰雄1980年，台湾大学电机系毕业， 获得了电子工程学士学位; 美国卡内基· 梅隆大学博士 曾在IBM工作 现在微软亚洲研究院

深蓝1996年，美国IBM公司 建基于RS/6000 SP AIX操作系统 重1270公斤，32个微处理器 每秒钟可以计算2亿步。

―神来之手”

IBM“深蓝”--棋王卡斯帕罗夫 卡斯帕罗夫 身高 体重 5英尺10英寸 176磅 深蓝 6英尺5英寸 1.27吨

卡斯帕罗夫: 他在观察电脑下棋时感觉电脑的决定有智慧及 创意，是他所不能理解的。他亦认为电脑在棋 局中可能有人类的帮助，因此要求重赛。 IBM: 拒绝，并把深蓝退役。 2003年一部纪录片 “游戏结束：卡斯巴罗夫 与电脑” (Game Over: Kasparov and the Machine)2015秋

年龄行棋速度

34岁2 步/每秒

4岁2 亿步/每秒

Slide. 1 - 16

数据结构与算法

第 1章 绪 论

1.1 数据结构研究对象◆数据结构研究方法

逻辑结构：对操作对象的一种数学描述，或从操作对象 中抽象出的数学模型，用以描述数据元素之 间的逻辑关系，与存储方式无关。物理结构：数据结构在计算机中的表示或映象，逻辑结构的 存储方式 物理结构又称存储结构，分为顺序映象和 非顺序映象，或称顺序存储结构和链式存储结构 计算机解题过程： 问题 → 数学模型 → 算法 → 程序 → 测试 → 计算

分析数据并确定存储结构 输入到计算机中2015秋

Slide. 1 - 17

数据结构与算法

第 1章 绪 论

◆数据结构研究的范畴

程序设计、算

法、数据结构

程序设计：为计算机处理问题编制一组指令集 算 法：怎么处理的策略 数据结构：问题的数学模型数值计算的程序设计问题： 问题 算法 数学模型

求解一元二次方程 一组整数排序结构静力分析计算 全球天气预报

? “冒泡”方法? ?

求根公式 数组线性代数方程组 环流模式方程

非数值计算的程序设计问题：问题 求一组整数的最大值 计算机对弈 足协的数据库管理 算法 比较两个数的大小 对弈的规则和策略 什么项目？如何管理？接口？ 条例？规则？ ? 棋子、棋盘的表示 表格，数据库 数学模型

2015秋

Slide. 1 - 18

数据结构与算法

第 1章 绪 论

1.2 数据结构发展概况●数据结构侧重解决非数值问题■FORTRAN,ALGOL等高级语言是以程序为中心 侧重于解决数值问题

■ LISP,SONBOL表或串处理语言是以数据为中心 侧重于解决非数值问题 ■从PASCAL语言开始逐渐形成二者结合● 1968年以前，数据结构的内容大多包含在形如表、树、 图论、集合代数论、格、关系等方面。1968年开始，“数据 结构”逐渐开始成为独立的一门课程。 ● 作为一门专业基础课，“数据结构”是计算机专业的核心 课程之一，是其他专业课的基础。是数学、硬件和软件三者 的交叉，很受重视。2015秋

Slide. 1 - 19

数据结构与算法

第 1章 绪 论

知 识 结 构

2015秋

Slide. 1 - 20

数据结构与算法

第 1章 绪 论

1.3 抽象数据型Abstract Data Types(ADT)抽象：从众多事物中舍弃个别的、非本质的属性，抽出 共同的、本质性的特征。 是形成概念的重要手段，其目的是使复杂度降低。●

软件系统由数据结构、操作过程和控制机能三者组

成，软件设计是对三者的抽象过程，即数据抽象、过程 抽象和控制抽象。 [定义]:抽象数据型是一个数学模型和在该模型上定义 的操作的集合 ADT特点：①降低了软件设计的复杂性 ②提高了程序的可读性和可维护性 ③程序的正确性容易保证2015秋

Slide. 1 - 21