第1章绪论--jy

1、 主讲教师主讲教师: : 金英金英Room Number：4-230教材和参考书教材和参考书教材教材：严蔚敏等，严蔚敏等，数据结构数据结构 (C (C语言版）语言版）（第（第2 2版），版），人民邮电出版社人民邮电出版社参考书参考书： 1. 1. 王晓东王晓东, ,计算机算法设计与分析计算机算法设计与分析（第（第4 4版），版）， 电子工业出版社电子工业出版社2. Thomas H. Cormen, 2. Thomas H. Cormen, 算法导论算法导论 （第三版）（第三版）, , The MIT Press, 2013 The MIT Press, 2013. .3. 3. 严蔚敏等，严

2、蔚敏等，数据结构数据结构C C语言版语言版，清华大学出版社，清华大学出版社4. 4. 唐策善等，唐策善等，数据结构数据结构用用C C语言描述语言描述， 高等教育出版社高等教育出版社 平时成绩平时成绩 : 40%作业作业发言发言出勤出勤小测验小测验( (期中考试）期中考试）实验实验(20(20分）分） 期末成绩期末成绩 : 60% (: 60% (闭卷笔试闭卷笔试) )考核方式考核方式第第1章绪章绪 论论 教教 学学 目目 标标 1. 了解数据结构研究的主要内容了解数据结构研究的主要内容 2. 掌握数据结构中涉及的基本概念掌握数据结构中涉及的基本概念 3. 掌握算法的概念、算法分析的方法掌握算法

3、的概念、算法分析的方法 * & N. 沃思（沃思（Niklaus Wirth)教授教授提出：提出： 程序程序 = = 算法算法+ +数据结构数据结构 Niklaus Wirth 1934年生于瑞士年生于瑞士 1963 在在UC Berkeley获博士学位获博士学位 教授：教授：Stanford University, 主要贡献主要贡献 提出著名公式提出著名公式“算法算法+数据结构数据结构=程序程序” Pascal之父：创建并实现了之父：创建并实现了Pascal语言语言 由于开发了一系列计算机语言，由于开发了一系列计算机语言，1984年获得年获得 图灵奖图灵奖& 电子计算机的主要

4、用途： 早期早期： 主要用于主要用于数值计算数值计算。 后来后来： 处理逐渐扩大到处理逐渐扩大到非数值计算非数值计算领域，能处理多领域，能处理多种复杂的具有一定结构关系的数据。种复杂的具有一定结构关系的数据。 书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件书目文件按书名按书名按作者名按作者名按分类号按分类号索引表索引表线性表线性表人 机 对 奕 问 题 树树./ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系统的系统结构图树树 公路网管理问题图图公路网最

5、短路径&求解非数值计算的问题求解非数值计算的问题： 设计出合适的设计出合适的数据结构数据结构及相应的及相应的算法算法。 即：首先要考虑即：首先要考虑对相关的各种信息如何表示、对相关的各种信息如何表示、组织和存储？组织和存储？ 数据结构的研究内容为：数据结构的研究内容为： 研究非数值计算的程序设计问题中计算机研究非数值计算的程序设计问题中计算机的的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作。 介于数学、计算介于数学、计算机硬件和计算机机硬件和计算机软件三者之间的软件三者之间的一门一门核心课程核心课程。v 编程基础编程基础v计算机及相关专业考研考计算机及相关专业考研考

6、博课程博课程v 计算机等级考试课程计算机等级考试课程v 程序员考试课程程序员考试课程数据结构与算法在计算机学科中的地位数据结构与算法在计算机学科中的地位概率统计概率统计数学基础数学基础集合与图论集合与图论程序设计程序设计数据结构与算法数据结构与算法数据库概论数据库概论线性表、多链表线性表、多链表排序、排序、B+B+索引树索引树操作系统操作系统队列、存储管理表队列、存储管理表排序、目录树排序、目录树编译原理编译原理队列、存储管理表队列、存储管理表排序、目录树排序、目录树数据结构与算法在计算机学科中的地位数据结构与算法在计算机学科中的地位Web信息处理信息处理队列、图、字符、矩队列、图、字符、矩阵

7、、散列表、排序、阵、散列表、排序、索引、检索索引、检索人工智能人工智能线性表、多链表线性表、多链表排序、排序、B+B+索引树索引树图形图像图形图像线性表、多链表线性表、多链表排序、排序、B+B+索引树索引树数据结构与算法在计算机学科中的地位数据结构与算法在计算机学科中的地位 课 程 目 的： 能够分析研究计算机加工的对象的特性，获能够分析研究计算机加工的对象的特性，获得其得其逻辑结构逻辑结构，根据需求，选择合适的根据需求，选择合适的存储存储结构结构及其及其相应的算法相应的算法 学习一些学习一些常用的算法常用的算法及及设计算法的基本方法设计算法的基本方法 初步掌握算法初步掌握算法复杂性分析技术复

8、杂性分析技术 复杂程序设计的训练过程，要求编写的程序复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读结构清楚和正确易读 1、数据数据(data) 所有能输入到计算机中去的所有能输入到计算机中去的描述客观事物的描述客观事物的符号。符号。u数值性数据数值性数据u非数值性数据（多媒体信息）非数值性数据（多媒体信息） 1.2 基本概念和术语基本概念和术语2. 数据元素数据元素(data element) 数据的数据的基本单位基本单位, 也称结点也称结点(node)或记录或记录(record)。3、数据项数据项(data item) 有独立含义的数据有独立含义的数据最小单位最小单位也称域也称域(

9、 (field)field)。三者之间的关系：数据三者之间的关系：数据 数据元素数据元素 数据项数据项例：例：学生表学生表 个人记录个人记录 学号、姓名学号、姓名姓姓 名名学学 号号性性 别别年年 龄龄健康情况健康情况王小林王小林790631790631 男男 1818 健康健康陈陈 红红790632790632 女女 2020 一般一般 . .数数据据元元素素u整数数据对象整数数据对象 N = 0, 1, 2, u学生数据对象学生数据对象 学生记录的集合学生记录的集合 4、数据对象数据对象(Data Object)：是是性质相同的性质相同的数据元素的集合，是数据的一个子集。数据元素的集合，是

10、数据的一个子集。5 、数据结构数据结构（Data Structure） 数据结构数据结构是相互之间存在一种或多种特定关系的是相互之间存在一种或多种特定关系的数据元素的集合。数据元素的集合。数据结构是带数据结构是带结构结构的数据元素的集合的数据元素的集合结构指的是数据元素之间存在的结构指的是数据元素之间存在的关系关系&数据结构的两个层次：& 逻辑结构 数据元素间抽象化的相互关系，与数据的存储无数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的关，独立于计算机，它是从具体问题抽象出来的数学模型。数学模型。& 存储结构(物理结构) 数据元素数

11、据元素及其及其关系关系在计算机存储器中的存储方式。在计算机存储器中的存储方式。 划分方法一划分方法一 （1）线性结构 有且仅有一个开始和一个终端结点，并且所有结点都有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。最多只有一个直接前趋和一个后继。 例如：例如：线性表、栈、队列、串。线性表、栈、队列、串。 （2）非线性结构 一个结点可能有多个直接前趋和直接后继。一个结点可能有多个直接前趋和直接后继。 例如：例如：树、图。树、图。 逻辑结构线性结构线性结构： 一个对一个，如线性表、栈、队列。一个对一个，如线性表、栈、队列。树形结构树形结构： 一个对多个，如树。一个对多个

12、，如树。集合：集合：数据元素间除数据元素间除“同属于一个集合同属于一个集合”外，无其它关系外，无其它关系。图形结构：图形结构：多个对多个，如图。多个对多个，如图。 逻辑结构划分方法二划分方法二存储结构分为：存储结构分为： 顺序顺序存储结构存储结构 借助元素在存储器中的借助元素在存储器中的相对位置相对位置来表示数据元素来表示数据元素间的逻辑关系。间的逻辑关系。 链式链式存储结构存储结构 借助指示元素存储地址的借助指示元素存储地址的指针指针表示数据元素间的表示数据元素间的逻辑关系。逻辑关系。 存存 储储 结结 构构元素元素n.元素元素i.元素元素2元素元素1LoLo+mLo+(i-1)*mLo+（

13、n-1)*m存储地址存储地址 存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1536元素元素21400元素元素11346元素元素3 元素元素41345h存储地址存储地址 存储内容存储内容 指针指针 1345 元素元素1 1400 1346 元素元素4 . . . . . 1400 元素元素2 1536 . . . . . 1536 元素元素3 1346 链式存储 h 逻辑结构和存储结构都相同逻辑结构和存储结构都相同, , 但运算不同但运算不同, , 则则数据结构不同。数据结构不同。 例如例如, , 栈与队列。栈与队列。 对于一种数据结构对于一种数据结构, , 常见的

14、运算常见的运算：插入插入删除删除修改修改查找查找排序排序 数据的运算数据的运算 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：数据的运算：插入、删除、修改、查找、排序插入、删除、修改、查找、排序 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表 栈、队列栈、队列 串、数组串、数组树形结构树形结构图形结构图形结构逻辑结构逻辑结构存储结构存储结构不唯一运算运算实现依赖于存储结构 广义上讲数据结构包括：广义上讲数据结构包括： n定义：定义：在一种程序设计语言中，变量所在一种程序设计语言中，变量所具有的数据种类。具有的数据种类。数据类型

15、数据类型FORTRAN语言：语言：整型、实型、和复数型整型、实型、和复数型 C语言语言：基本数据类型：基本数据类型： char int float double void构造数据类型：构造数据类型：数组、结构体、共用体、文件数组、结构体、共用体、文件 数据类型是一组性质相同的值的集合是一组性质相同的值的集合, , 以及以及定义于这个集合上的一组运算的总称。定义于这个集合上的一组运算的总称。u更高层次的数据抽象更高层次的数据抽象u由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型u由由基本的数据类型基本的数据类型组成组成, , 并包括并包括一组相关的一组相关的操作操作抽

16、象数据类型抽象数据类型抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = （D，S，P） 数据对象数据对象 D D上的关系集上的关系集 D D上的操作集上的操作集 ADT抽象数据类型名抽象数据类型名 数据对象：数据对象： 数据关系：数据关系： 基本操作基本操作 ： ADT抽象数据类型名抽象数据类型名ADT常常用用定定义义格格式式抽抽象象数数据据类类型型查找查找插入插入 删除删除 修改修改 线性表线性表接口或用接口或用户界面户界面数据类型数据类型的物理实的物理实现封装现封装信息隐蔽和数据封装，使用与实现相分离1.3.1 算法的定义及特性算法的定义及特性n算法

17、定义：算法定义：一个有穷的指令集一个有穷的指令集，这些指令为，这些指令为解决某一特定任务规定了一个运算序列。解决某一特定任务规定了一个运算序列。 1.3 算法和算法分析输入输入u 输出输出确定性确定性有穷性有穷性有效性有效性u 自然语言自然语言u 流程图流程图u 程序设计语言程序设计语言u 伪码伪码算法的描述：u正确性正确性u可读性可读性u健壮性健壮性u高效性（高效性（时间代价时间代价和和空间代价）空间代价）通常有两种衡量算法效率的方法:事后统计法事后统计法事前分析估算法事前分析估算法缺点：缺点：1. 1. 必须执行程序必须执行程序 2. 2. 其它因素掩盖算法本质其它因素掩盖算法本质优点：优

18、点：可以预先比较各种算法，以便均衡利弊可以预先比较各种算法，以便均衡利弊从中选优。从中选优。1.3.3 算法的时间复杂度和算法执行时间相关的因素：和算法执行时间相关的因素： 1算法选用的策略算法选用的策略2问题的规模问题的规模3编写程序的语言编写程序的语言4编译程序产生的机器代码的质量编译程序产生的机器代码的质量5计算机执行指令的速度计算机执行指令的速度算法选用的策略算法选用的策略问题的规模问题的规模 可见，用绝对时间单位衡量算法的效可见，用绝对时间单位衡量算法的效率是不合适的。率是不合适的。算法的执行时间算法的执行时间 = = 该算法中所有语句的频度之和。该算法中所有语句的频度之和。如何估算

19、算法的时间复杂度？语句频度：一条语句的重复执行次数。一条语句的重复执行次数。假设：假设：每条语句执行一次的时间均为单位时间。每条语句执行一次的时间均为单位时间。例例一一 两两个个矩矩阵阵相相乘乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素以二维数组存储矩阵元素，c 为为 a 和和 b 的乘积的乘积 for (i=1; i=n; +i) /频度为频度为n+1 for (j=1; j=n; +j) /频度为频度为n(n+1) ci,j = 0; for (k=1; k=n; +k) /频度为频度为n2(n+1) ci,j += ai,k *

20、bk,j; /频度为频度为n3 /for /mult时间复杂度时间复杂度: T(n)=2n3+3 n2+2n+1forforfor *算法的时间复杂度算法的时间复杂度T(n)是问题规模是问题规模n的函数。的函数。问题的规模问题的规模: 算法求解问题的输入量，一般用算法求解问题的输入量，一般用n表示。表示。问题的规模对不同问题的含义不同，问题的规模对不同问题的含义不同，如：如： 在在n*n矩阵乘法运算问题中，问题规模为矩阵乘法运算问题中，问题规模为n。 在具有在具有n个元素的线性表的排序问题中，个元素的线性表的排序问题中， 问题规模为问题规模为n。算法的渐进时间复杂度算法的渐进时间复杂度 n*n

21、矩阵乘法运算算法矩阵乘法运算算法: T(n)=2n3+3 n2+2n+1 即，当即，当n充分大时，充分大时，T(n)与与n3同阶。同阶。此时可记作，此时可记作，T(n)=O(n3) ，用，用O表示数量级！表示数量级！算法的渐进时间复杂度：算法的渐进时间复杂度：当问题的规模当问题的规模n趋向无穷大时，趋向无穷大时，T(n)的的数量级数量级称为算称为算法的渐进时间复杂度法的渐进时间复杂度, 记作记作T(n)=O(f(n)。 其中的其中的f(n)一般是算法的最大语句频度。一般是算法的最大语句频度。231)/n2n23n3(2nnlim3T(n)/nnlimfor( i = 0; i n; i+) f

22、or( j = 0; j n; j+)cij = aij + bij;最大语句频度最大语句频度： n*n时间复杂度时间复杂度: T(n) = O ( n2)例例二二 两两个个矩矩阵阵加加法法最深层循环内最深层循环内语句频度语句频度(1) x = 0; y = 0;(2) for ( int k = 0; k n; k + )(3) x +;(4) for ( int i = 0; i n; i+ )(5) for ( int j = 0; j n; j+ )(6) y +;T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)最大语句频度最大语句频度： n*n时间复杂度时间

23、复杂度: T(n) = O(n2)最深层循环内最深层循环内语句频度语句频度回顾例回顾例1：NN矩阵相乘矩阵相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; 算法中的基本操作语句为算法中的基本操作语句为: : cij=cij+aik*bkj; 233111111( )1()nnnnnnijkijiT nnnno n 3T nO n * x=1;for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+)x=x+1; n1in1ii1jn1ii1jj1k21)i(ij162)1)(nn(n21)n(n61)1)(2nn(n21ii21n1in1i2语句频度语句频度 = =【例例5】顺序查找，在数组顺序查找，在数组aiai中查找值中查找值等于等于e e的元素，返回其所在位置。的元素，返回其所在位置。 for (i=0;i n;i+)