《数据结构—chapter 1- 绪论.ppt》由会员分享，可在线阅读，更多相关《数据结构—chapter 1- 绪论.ppt（35页珍藏版）》请在金锄头文库上搜索。
1、教材及参考书目,教材： 数据结构使用C语言（第3版），朱战立编著，西安交通大学出版社 数据结构实习指导书 中国地质大学（武汉）计算机科学与技术系 C语言程序设计（第二版），谭浩强，清华大学出版社 主要参考书目： 数据结构（C语言版），严蔚敏等编著，清华大学出版社 ； 计算机程序设计技巧，D.E.克努特美著，管纪立等译，第一卷 基本算法，第三卷 排序与查找； 数据结构题集（C语言版），严蔚敏、吴伟民编著，清华大学出版社； 数据结构习题与解析（C语言篇），李春葆编著，清华大学出版社,学习数据结构的意义,数据结构是为研究和解决如何有效地组织和处理非数值数据而产生的理论、技术和方法。 数据结构是软件设
2、计技术的理论基础，是计算机学科的核心专业基础课程，也是所有应用计算机的其他学科所必须掌握的课程。,学习这门课程的目的,训练复杂程序设计技能，提高编程能力： 掌握常用的基本数据结构； 培养分析问题的能力：培养数据抽象能力，学会分析研究具体问题中的数据特性； 培养解决问题的能力：能够根据实际问题的需要选择合适的数据结构和算法 初步掌握算法效率的度量时间复杂度分析技巧,教 学 内 容,研究八大基本数据结构线性表、栈、队列、（串）、数组、树、二叉树、图 逻辑特性 在计算机中的存储方式 操作集和在不同存储方式下操作的算法实现(重点、难点) 各种算法的性能分析 各种数据结构的应用(重点、难点) 研究两大基
3、本操作查找和排序 各种实现算法及其效率分析,数据结构课程的特点及学习方法,特点1：内容广，概念多 学习方法1：注重各章节间的联系与衔接，抓住主线，融会贯通 特点2：实践性强、动手编程难 学习方法2：数据结构是一门实践性很强的课程，上机实习是其中很重要的一个环节。因此，学习一个阶段后要及时上机实习。 要求： (1) 认真地完成课后习题以及上机实习 (2) 编写的程序正确、结构清楚、易读，符合软件 工程的规范(P25)。,第 一 次 课,阅读： 朱战立，第1-13、14-18、18-25页 谭浩强 练习 ： 作业1,Chapter 1 绪论,1.1-2 基本术语 - 数据结构 - 抽象数据类型 1
4、.3 算法与算法分析 - 算法 - 时间复杂度,1.1 基本术语, 数据（Data） 凡是能输入到计算机，由计算机进行加工处理的数字、字母、文字和其它符号均叫做数据。 含义极为广泛，如图形、声音等都属数据的范畴。 数据元素（Data Element） 数据的基本单位，即数据集合中的一个个体。 有时，一个数据元素可由若干数据项组成，数据项是具有独立含义的最小单位。,例、图书自动检索系统的数据, 数据结构（Data Structure） 元素之间的关系称为结构。数据结构，简单地说，就是数据元素的集合加上数据元素之间的相互关系的集合，可形式化地描述成一个二元组： Data Structure=(D,
5、S) 其中，D：数据元素的集合， S：D上关系的集合。 1968年唐欧克努特美：,数据结构=数据的逻辑结构+数据的存储结 构+数据的运算, 数据的逻辑结构 数据元素之间抽象化的相互关系。二元组形式化定义中的S即指的逻辑结构。 三类基本结构： 线性结构 树形结构 图形结构 也可简单分为： 线性结构：线性表、栈、队列、 串、 数组 非线性结构：树、二叉树、图,例1、图书自动检索系统（建立、查找、插入/删除）,例2、一个大学的人事档案处理系统 学校 一院(系) 二院(系) n院(系) 一专业 二专业 m专业 教师 学生 档案 档案档案,例3、交通管理信息系统, 数据的物理结构（存储结构） 逻辑结构到
6、计算机存储器的映象。 映象方法： 顺序分配 链式分配, 数据的运算（操作） 逻辑操作 和 具体操作 ： 逻辑结构 逻辑操作 存储结构 具体操作 常用的逻辑操作有： （1）建立一个数据结构 （2）销毁一个数据结构 （3）插入一个新元素到一个指定的数据结构 （4）删除一个元素 （5）修改一个元素（或其中的数据项）的内容 （6）排序 （7）查找,抽象 只知道做什么，而无须考虑如何做,具体,概念小结,数据结构研究数据元素间在客观世界的相互联系、在计算机内的存储方法以及如何能在各种结构上实施有效的操作算法。 一个具体问题的软件设计通常包含三个步骤： （1）分析和确定问题的逻辑结构和逻辑操作；（2）设计该
7、问题的具体存储结构；（3）设计该问题在具体存储结构下的操作实现算法。, 数据类型（Data Type） 数据类型是一组值的集合以及定义在这个值集上的一组操作的总称。通常可看作是高级程序设计语言中已实现的数据结构。 例：C语言中的“整型”变量。, 抽象数据类型（Abstract Data Type, Abbr. ADT） 是指一个数学模型以及定义在该模型上的一组操作，可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 对一个ADT必须经过定义和实现之后才能使用。 定义包含三部分： 数据元素 数据元素之间的相互关系（结构） 定义在数据结构上的一组操作,例、线性表抽象数据类型的定义： ADT Li
8、st 数据元素： ai是整数，i=0,1,n-1 (n0) 结构：对所有的数据元素ai ( i=0,1,n-2 )存在次序关系 , a0无前趋，an-1无后继。 操作：设L为 List 型的线性表 ListInitiate(L) /构造一个空的线性表L。 ListLength(L) /返回线性表L中的元素个数，即求表长。 ListInsert(L,i,x) /在线性表L的第i个位置前插入一个值 为x 的新元素，插入成功返回1，失败返回0。 0in，插入后表L的长度为n+1。 ListDelete(L,i,x)/删除线性表L的第i个元素。0in-1， 被删除的元素通过x带回。删除成功返回1，失败
9、返回 0。删除后表L的长度为n-1。 ListGet(L,i,x) /取线性表L中的第i个元素，并由参数x 带回，0in-1。成功返回1，失败返回0 。,1.3 算法和算法分析,1. 算法（Algorithm） 什么叫算法？ 一个算法是解决某一特定类型问题的一个有穷运算序列。 算法的设计 “自顶向下，逐步以模块的形式细化”原则, 算法的描述 自然语言 流程图 高级程序设计语言 伪码语言 算法与程序的区别 算法 程序 有穷性 可无穷（如OS) 任何方法描述 机器可执行语言书写 程序=算法 + 数据结构 （Niklaus Wirth),2. 算法分析 评价算法好坏的标准 除算法应该是“正确”的外，
10、还应考虑： 该算法是稳健的，是可读的； 该算法能有效地使用计算机资源(主要是CPU和 内存)，尤其是尽量少占用机器的运行时间。 评价方法 算法所需的计算时间（时间复杂度） 算法所需的空间（空间复杂度）, 算法的时间复杂度,设 n 表示问题的规模，则一个算法的时间复杂度是问题规模 n 的函数，记为 T ( n )。 算法的时间复杂度 T ( n )采用算法中各个基本语句执行次数的总和 f ( n ) 来度量，使用大O表示法，O (f ( n )是算法的渐进时间复杂度（时间复杂度），表达算法运行时间增长率的上界，表示当n增大时，算法运行时间至多将以正比于 f(n)的速度增长。 定义：T( n )=
11、O( f( n ) )当且仅当存在正常数c和n0，对所有的n(n n0)满足T(n)cf(n)。,（c是常数）,也可以理解为：,通常T(n)的数量级有： 常量阶 O( 1 )多项式阶 O( nk ) 对数阶 O( lgn ) 或 O( lbn ) 线性阶 O(n) 线性对数阶 O( n lgn ) 指数阶 O( 2n ),可实际使用的算法,为简化分析， T(n)通常抛弃常数系数和低阶项,例1. temp=i; i=j; j=temp; f(n)=?,T(n)=O(1),例2. for (i=1；i=2*n-1；i+) x+; f(n)=,T(n)=O(n),3,2n-1,对于更复杂的算法，可以
12、分块估算，再利用“O”的加法规则(块并列）和乘法规则（块嵌套）求出总的时间复杂度。 设 T1(n)=O(f(n)，T2(n)=O(g(n) 则 T1(n)+T2(n)=O( maxf(n), g(n) ) T1(n)T2(n)=O( f(n)g(n) ),例3. for (i=1; i n; i+) y=y+1; for (j=0; j=2*n; j+) x+; f(n)=,T(n)=O(n2),(n-1)+(n-1)*(2n+1),例4. for (i=2; i=n; i+) for (j=2; j=i-1; j+) x+; f(n)=,T(n)=O(n2),1+2+3+.+(n-2),算法
13、的时间复杂度还与初始输入集有关,最坏输入数据集情况下的时间复杂度称最坏时间复杂度。一般若无特定说明，讨论的时间复杂度均指的是最坏情况下的运行时间。 平均时间复杂度是指所有可能的输入数据集均以等概率出现的情况下，算法的平均运行时间。, 空间复杂度 数据结构所需空间和算法在处理过程中 所需额外空间的总和。 它同样是问题规模n的函数。,3. 用C语言描述算法的有关说明 算法以函数形式描述 函数类型 函数名(函数参数表) /* 算法说明 */ 局部变量的类型说明； 语句序列； 抽象数据元素类型约定为DataType，由用户利用typedef自行定义。,例. 图书自动检索系统中数据元素的类型定义 str
14、uct Date int year; int month; int day; /时间 typedef struct Book long loginnumber; char booktitle20; char authorname20; long classnumber; char publisher20; struct Date publishdate; BookType / 数据元素类型 typedef BookType DataType / DataType：抽象数据元素类型,作业1,p26，1-11，1-13, 数据结构的产生与发展 1）60s 初，散见于“操作系统”、“编译原理”等专业
15、课 2）1968年作为一门独立的课程，但内容没做明确的规定。几乎和图论，特别和表、树的理论是同义语。后来逐步扩充网络、集合代数论、格、关系等内容，变成了现在称为“离散结构”的内容。 3）1968， 唐欧克努特（美）：数据结构=数据的逻辑结构+数据的存储结构+对数据的操作 4）70年代，出现大型程序，结构化程序设计成为主流。程序设计的实质：对所研究的问题选择一种好的结构以及设计一种好的算法。“数据结构”越来越受到重视。 70年代后期，我国高校陆续开设该课程。 目前：数据结构在计算机领域占有重要地位。 发展：空间数据结构、多维图形数据结构,例 for (i=1；i=22*n-37；i+) x+;,Part 1): f(n)= ?,Part 2): 已知T(n)=22n-37，使用大O表示法，证明T(n) =O(n2).,证明：我们需要找到c和n0 以使22n 37 22, （3）式成立. 因此当c = 1 ，n0 =
