数据结构课件第01章.ppt

《数据结构课件第01章.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第01章.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构(C语言版语言版)Data Structure主讲教师主讲教师马宁马宁 计算机科学学院计算机科学学院软件工程教研室软件工程教研室1学习的直接收益学习的直接收益编程基础编程基础计算机专业考研课程计算机专业考研课程计算机等级考试课程计算机等级考试课程软件资格与水平考试课程软件资格与水平考试课程进入优秀企业的敲门砖进入优秀企业的敲门砖 盖茨说：盖茨说：学通了这本书学通了这本书（程序设（程序设计技巧，共三卷，其中第一卷主要为数据结构）计技巧，共三卷，其中第一卷主要为数据结构）来找我吧来找我吧！请同学们重视本课程的学习。请同学们重视本课程的学习。总学时：总学时：64 学时学时 讲课学时：

2、讲课学时：48 学时学时 实验学时：实验学时：16 学时学时 教材：教材：数据结构数据结构（C语言版）严蔚敏、吴伟民语言版）严蔚敏、吴伟民-清华大学出版社清华大学出版社课程安排课程安排程序设计课程与数据结构课程的关系程序设计课程与数据结构课程的关系程序设计强调程序设计强调程序设计的基本概念程序设计的基本概念和和做法做法，如：，如：数据类型与表达式数据类型与表达式程序流程控制程序流程控制子程序子程序递归递归数据抽象，等数据抽象，等数据结构强调数据结构强调程序设计思想程序设计思想和和技术的典型技术的典型应用应用，如：，如：线性表、栈、队列线性表、栈、队列检索、排序检索、排序图、树，等图、树，等两者

3、的内容又有交叉两者的内容又有交叉本课程的体系结构本课程的体系结构第一章第一章 绪论绪论 介绍数据、数据结构和抽象数据类型的概念。介绍数据、数据结构和抽象数据类型的概念。第二章第二章 第七章第七章 基本数据结构基本数据结构 从抽象数据类型的角度，从抽象数据类型的角度，分别讨论分别讨论线性表、栈和队列、线性表、栈和队列、串、数组和广义表、串、数组和广义表、树、图树、图等基本数据结构及其应用。等基本数据结构及其应用。1.1 数据结构学科的研究对象数据结构学科的研究对象1.什么是程序、软件？什么是程序、软件？N.沃思（沃思（Niklaus Wirth)教授提出：教授提出：程序程序=算法算法+数据结构数

4、据结构 以上公式说明了如下两个问题：以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据）数据上的算法决定如何构造和组织数据（算法（算法数据结构）数据结构）（2）算法的选择依赖于作为基础的数据结构）算法的选择依赖于作为基础的数据结构（数据结构（数据结构算法）算法）软件软件=程序程序+文档（软件工程的观点）文档（软件工程的观点）第一章第一章 绪论绪论2.电子计算机的主要用途电子计算机的主要用途 早期：早期：主要用于主要用于数值计算数值计算。后来：后来：应用逐渐扩大到应用逐渐扩大到非数值计算非数值计算领域（能处理多种复杂领域（能处理多种复杂的具有一定结构关系的数据）。的具有一定结构

5、关系的数据）。数据复杂数据复杂数据结构数据结构3.计算机解决问题的一般步骤计算机解决问题的一般步骤 数学模型数学模型算法算法程序程序(1)数值计算数值计算 数学模型数学模型选择计算机语言选择计算机语言编出程序编出程序测试测试最终解答。最终解答。数值计算的关键是：如何得出数学模型（方程）？数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。程序设计人员比较关注程序设计的技巧。(2)非数值计算问题非数值计算问题 数据元素之间的相互关系一般无法用数学方程加以描述。数据元素之间的相互关系一般无法用数学方程加以描述。例例1、电话号码查询问题、电话号码查询问题 查找查找：给出一

6、个姓名，如果存在，打印此人的电话号码；：给出一个姓名，如果存在，打印此人的电话号码；如果不存在，报告没有这个人的标志。如果不存在，报告没有这个人的标志。（1）按顺序存储方式：须遍历表）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引）按姓氏索引方式：索引 要写出好的查找算法，取决于这张表的结构及存储方式。要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。电话号码表的结构和存储方式决定了查找（算法）的效率。4.非数值计算问题举例非数值计算问题举例登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片线性表书目文件例例2 书目自动检索

7、系统书目自动检索系统按书名按作者名按分类号索引表例例3 人机对奕问题人机对奕问题树.例例4 多叉路口交通灯管理问题多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图 求解非数值计算的问题求解非数值计算的问题 主要考虑的是设计出合适的数据结构及相应的算法。主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑即：首先要考虑对相关的各种信息如何表示、组织和存对相关的各种信息如何表示、组织和存储？储？数据结构数据结构的研究对象是：的研究对象是：非数值计算非数值计算的程序设计问题中的程序设计问题中计算机的计算机的操作对象操作对象以及它们之间的以及它们之间的关系

8、关系和和操作操作。5.数据结构课程的形成和发展数据结构课程的形成和发展 形成阶段：形成阶段：60年代初期，年代初期，“数据结构数据结构”有关的内容散见于操作系统、有关的内容散见于操作系统、编译原理和表处理语言等课程。编译原理和表处理语言等课程。1968年，年，“数据结构数据结构”被被列入美国一些大学计算机科学系的教学计划。列入美国一些大学计算机科学系的教学计划。发展阶段：发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关数据结构的概念不断扩充，包括了网络、集合代数论、关系等系等“离散数学结构离散数学结构”的内容。的内容。70年代后期，我国高校陆续开设该课程。年代后期，我国高校陆续开设

9、该课程。6.数据结构课程所处的地位数据结构课程所处的地位1.2 基本概念和术语基本概念和术语1.数据数据(Data):是对信息的一种符号表示。在计算机科学中是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总是指所有能输入到计算机中并被计算机程序处理的符号的总称。称。2.数据元素数据元素(Data Element):是数据的基本单位，在计算机是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个一个数据元素可由若干个数据项数据项组成。组成。数据项是数据的不可分割的最小单位。数据项是数据的

10、不可分割的最小单位。3.数据对象数据对象(Data Object)：是性质相同的数据元素的集合，：是性质相同的数据元素的集合，是数据的一个子集。是数据的一个子集。4.数据类型数据类型(Data Type)：在一种程序设计语言中，变量所：在一种程序设计语言中，变量所具有的数据种类。具有的数据种类。例例1、在在FORTRAN语言中，变量的数据类型有整型、实型、语言中，变量的数据类型有整型、实型、和复数型和复数型 例例2、在、在C语言中语言中数据类型：基本类型、指针类型、空类型和结构类型数据类型：基本类型、指针类型、空类型和结构类型其中，基本类型包括整型、浮点型、字符型和枚举类型其中，基本类型包括整

11、型、浮点型、字符型和枚举类型5.抽象数据类型抽象数据类型(Abstract Data Type简称简称ADT）抽象数据类型是用户在数据类型基础上新定义的数据类型抽象数据类型是用户在数据类型基础上新定义的数据类型抽象数据类型定义包括数据组成和对数据的处理操作抽象数据类型定义包括数据组成和对数据的处理操作抽象数据类型是数据和数据的使用者的一个接口抽象数据类型是数据和数据的使用者的一个接口抽象数据类型的三元组表示抽象数据类型的三元组表示 （D，S，P）D：数据对象数据对象 S：D上的关系集上的关系集 P：对：对D的基本操作的基本操作ADT的作用的作用结构与用户无关，提高代码的复用率结构与用户无关，提

12、高代码的复用率抽象数据类型的定义抽象数据类型的定义：包括数据对象定义、数据关系定义和：包括数据对象定义、数据关系定义和基本操作定义，书写格式为：基本操作定义，书写格式为：ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据逻辑关系的定义数据关系：数据逻辑关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 P 8 倒数倒数7行行 ADT 抽象数据类型名抽象数据类型名 （P9 例例 1-6 伪码描述）伪码描述）P 8 倒数倒数4行行C+的引用类型的引用类型引用类型用于给一个变量取一个引用类型用于给一个变量取一个别名别名。例如：。例如：in

13、t x=0;int&y=x;/y为引用类型的变量为引用类型的变量cout x ,y endl;/结果为：结果为：0,0y=1;cout x ,y endl;/结果为：结果为：1,1在语法上，对引用类型变量的访问与非引用类型在语法上，对引用类型变量的访问与非引用类型相同；但在语义上，对引用类型变量的访问实际相同；但在语义上，对引用类型变量的访问实际访问的是另一个变量（被引用的变量）。访问的是另一个变量（被引用的变量）。引用类型作为函数的参数类型引用类型作为函数的参数类型#include using namespace std;void swap(int&x,int&y)int t;t=x;x=y

14、;y=t;int main()int a=0,b=1;cout a ,b endl;/结果为：结果为：0,1swap(a,b);cout a ,b endl;/结果为：结果为：1,0return 0;指针类型作为函数的参数类型指针类型作为函数的参数类型#include void swap(int*p1,int*p2)int t;t=*p1;*p1=*p2;*p2=t;void main()int a=0,b=1;cout a ,b endl;/结果为：结果为：0,1swap(&a,&b);cout a ,b=0)个初始数据的输个初始数据的输入。入。（5）输出输出数据数据-一个算法有一个或多个的

15、有效信息的输一个算法有一个或多个的有效信息的输出。出。&算法的描述和实现算法的描述和实现 描述描述-可采用自然语言、数学语言或约定的符号语言。可采用自然语言、数学语言或约定的符号语言。实现实现-必须借助程序设计语言提供的数据类型及其运算。必须借助程序设计语言提供的数据类型及其运算。本课的描述本课的描述-采用采用类类C语言语言 （P9-13 1.3 课后仔细阅读课后仔细阅读）思考：算法与程序有何区别？思考：算法与程序有何区别？&算法设计的要求算法设计的要求正确性正确性、可读性、健壮性、高效率与低存储量需求、可读性、健壮性、高效率与低存储量需求程序正确性的四个层面：程序正确性的四个层面：（1）不含

16、语法错误）不含语法错误（2）程序对于）程序对于n组输入数据能够得出满足规格说明要求的结果组输入数据能够得出满足规格说明要求的结果（3）程序对于精心选择的典型、边界性的）程序对于精心选择的典型、边界性的n组输入数据能得出满组输入数据能得出满足规格说明要求的结果足规格说明要求的结果（4）程序对于一切合适的输入数据都能得出满足规格说明要求的）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）结果（穷举）算法的效率指算法的执行时间，也称作算法的效率指算法的执行时间，也称作算法的时间复杂度算法的时间复杂度算法的存储量需求指算法执行过程中所需的最大存储空间，算法的存储量需求指算法执行过程中所

17、需的最大存储空间，也称作也称作算法的空间复杂度算法的空间复杂度&算法效率的度量算法效率的度量 程序运行所耗费的时间（由下列因素决定）：程序运行所耗费的时间（由下列因素决定）：算法所选用的策略算法所选用的策略 问题的规模问题的规模算法求解问题的输入量（或初始数据量）算法求解问题的输入量（或初始数据量）书写程序所采用的语言书写程序所采用的语言 编译程序所产生的机器代码的质量编译程序所产生的机器代码的质量 机器执行指令的速度机器执行指令的速度 一个算法耗费的时间一个算法耗费的时间=算法中每条语句的执行时间之和算法中每条语句的执行时间之和 若不考虑机器硬、软件因素，可以认为算法若不考虑机器硬、软件因素

18、，可以认为算法“运行工作量运行工作量”的大小是问题规模的函数的大小是问题规模的函数。设：执行每条语句所需时间为单位时间，则：设：执行每条语句所需时间为单位时间，则：一个算法的时间耗费：一个算法的时间耗费：f(n)=所有语句的频度之和所有语句的频度之和 其中，其中，n 为问题的规模为问题的规模 渐近时间复杂度渐近时间复杂度(Asymptotic Time Complexity)：O(f(n)随问题的规模随问题的规模n的增大，的增大，f(n)的的增长和增长和f(n)的数量级（阶）的数量级（阶）O(f(n)的增长的增长率率相同。相同。时间复杂度时间复杂度：T(n)=O(f(n)算法效率的度量：采用算

19、法效率的度量：采用时间复杂度时间复杂度例例7 分析以下程序段的时间复杂度分析以下程序段的时间复杂度for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;/*1 */*2 */频度频度:指的是该语句重复执行的次数。指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。一个算法中所有语句的频度之和构成了该算法的运行时间。语句语句1的频度是的频度是：n-1语句语句2的频度是：的频度是：时间耗费：时间耗费：f(n)=2n2-2时间复杂度：时间复杂度：T(n)=O(n2)例例8 分析以下程序段的时间复杂度分析以下程序段的时间复杂度i=1;while

20、(i=n)i=i*2语句语句1的频度是：的频度是：1设语句设语句2的频度是的频度是f(n)，则有：，则有：即即 ，取最大值，取最大值则该程序段的时间复杂度为：则该程序段的时间复杂度为：/*1 */*2 */例例9 x=1;for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=1&change;-I)change=false;for(j=0;jaj+1)aj aj+1;change=TURE;最好情况：最好情况：0次次 最坏情况最坏情况：1+2+3+n-1 =n(n-1)/2 平均时间复杂度为平均时间复杂度为：O(n2)&算法的存储空间需求算法的存储空间需求空间复杂度空

21、间复杂度：算法所需存储空间的度量，记作算法所需存储空间的度量，记作:S(n)=O(f(n)其中其中n为问题的规模为问题的规模(或大小或大小)空间复杂度一般只分析空间复杂度一般只分析辅助空间辅助空间课外学习课外学习看书看书 P1P17思考题思考题 1、什么是数据结构，其三个方面含义是什么？、什么是数据结构，其三个方面含义是什么？2、线性结构和非线性结构的逻辑特征是什么？线性结构和非线性结构的逻辑特征是什么？3、数据存储的四种基本方法是什么？数据存储的四种基本方法是什么？4、算法的五个重要特性是什么？、算法的五个重要特性是什么？5、分析、分析P15、P16 程序段的时间复杂度程序段的时间复杂度 6、举例说明引用类型与指针类型的区别、举例说明引用类型与指针类型的区别作业题：用函数实现作业题：用函数实现2个变量的值的交换个变量的值的交换1）用指针类型的参数）用指针类型的参数2）用引用类型的参数）用引用类型的参数