数据结构与算法分析第二版英文版课件chapter11

２．算法基本特性： • 有穷性：算法经有限步后结束； • 确定性：下一步必须是明确的； • 可行性：每一步是可执行的；
1.3 算法描述和算法分析
３．算法与程序的区别
• 算法 是解决问题的一种方法或一个过程，考虑如何将 输入转换成输出，一个问题可以有多种算法。 • 程序 是用某种程序设计语言对算法的具体实现。
数据结构
严蔚敏 吴伟民
（第二版）
清华大学出版社
第一章 绪论
1.1 <数据结构>的主要内容 1.2 基本术语 1.3 算法描述及分析
1.1 <数据结构>的主要内容
例1：
99080-33202670610054510102780618748 99080-3 班号 3202670 计算机学院办公室电话号码 610054 电子科技大学邮编 510102780618748 身份证号码
1.1 <数据结构>的主要内容
例４：图书目录管理
设每个书目含：书名，作者，登录号，分类，出版年月 对图书目录常有如下操作： • 查找：某书在书库中是否存在？ • 插入：购进新书时的登录； • 删除：报废或丢失的书，需从目录中去掉；
结论４． 在某种数据结构上可定义一组运算
《DS》就是要研究各类数据结构上的各种运算。
1.1 <数据结构>的主要内容
综上所述： 《DS》主要研究内容：
• 数据的各种逻辑结构和物理结构，以及它 们之间的相应关系；
• 对每种结构定义相适应的各种运算；
• 设计出相应的算法； • 分析算法的效率。 常见的数据结构有：数组、栈、队列、表、 串、树、图和文件等。
数据结构与问题求解
1. 在计算机中建立一个与实际问题有比较密 切对应关系的模型； 2. 计算机内部的数据 表示了需要被处理的 实际对象，包括其内在的性质和关系； 3. 处理这些数据的程序 则模拟对象领域中 的实际过程；

，对算法给定的初始量 输出：算法有一个或多个输出，即与输入有某个特
定关系的量，简单地说就是算法的最终结果
15
1.1.3 算法的概念
2．算法、数据结构与程序的关系
对算法不满意
对数据结构不满意
给定问题
设计求解问题的算法
抽象出数据，建立数据结构
将算法分解成对数据结构的运算 编程实现，并上机调试
对算法的性能进行评价
算法的空间复杂性（space complexity） 算法对空间的需求（存储空间）
34
1.2.2 算法的评价标准和评价方 法
3．时间复杂性 算法的时间复杂性是输入数据量n的函数，
记为T(n)，描述算法执行过程中所需的时间 用量与问题规模n之间的函数关系 评价算法的时间复杂性，就是设法找出T(n) 和n的函数关系，即计算出T(n) T(n)要计算得“精确”（客观）较困难
有穷性、确定性、可行性、输入、输出
14
1.1.3 算法的概念
有穷性：一个算法在执行有限步之后必须结束
确定性：算法的每一步骤必须确切定义。执行者可 根据该算法的每一步要求进行操作，并最终得出正 确的结果（即无歧义）
可行性：算法中所有的运算都可以精确地实现 输入：算法有零个或多个输入，即在算法开始之前
T(n)的上界 某算法执行时间T(n)，如果存在正的常数c和n0， 使对于一切n > n0，T(n)≤cf(n)都成立 那么，就记作 T(n)=O(f(n))
大“O”记号（big-Oh notation）
37
1.2.2 算法的评价标准和评价方 法
3．时间复杂性 T(n)=O(f(n))
f(n)：运行时间 增长率的上界
结束
28
示例1-2 二分查找（binary search）

40、人类法律，事物有规律，这是不 容忽视 的。— —爱献 生
21、要知道对好事的称颂过于夸大，也会招来人们的反感轻蔑和嫉妒。——培根 22、业精于勤，荒于嬉；行成于思，毁于随。——韩愈
23、一切节省，归根到底都归结为时间的节省。——马克思 24、意志命运往往背道而驰，决心到最后会全部推倒。——莎士比亚
25、学习是劳动，是充满思想的劳动。——乌申斯基
谢谢！Leabharlann 数据结构 （第二版）36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进 而变成 法律。 ——朱 尼厄斯

【Definition】An Abstract Data Type (ADT) is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation on the operations.
typedef struct list_node *list_ptr; typedef struct list_node {
char data [ 4 ] ;
N1->next = N2 ; N2->next = NULL ; ptr = N1 ;
list_ptr next ;
}; list_ptr ptr ;
array+i array+i+1
……
itemi itemi+1 ……
MaxSize has to be estimated.
Find_Kth takes O(1) time.
Insertion and Deletion not
only take O(N) time, but also involve a lot of data movements which takes time.
2. Linked Lists
Address
0010 0011 0110 1011
Data
SUN QIAN ZHAO
LI
Pointer