数据结构1绪论课件

数据结构 付细楚 2011年2月1数据结构 付细楚 1联系方式联系方式电子邮件：欢迎同学们共同交流和探讨。2联系方式电子邮件：2课程的性质课程的性质l综合性的专业基础课程l软件专业课程体系中的核心课程先修课:C+程序设计语言,离散数学后续课:几乎所有的软件方面课程,如:操作系统,编译原理,算法分析 与设计,应用系统开发等.3课程的性质综合性的专业基础课程3课程安排课程安排l教学安排:教学总学时数 56学时（其中 讲授:40课时,实验 16 课时）数据结构与算法课程设计（2周）l10软件4、5、6、7、8班 4课程安排教学安排:4研究对象研究对象主要是研究：非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作 5研究对象主要是研究：5学习目的学习目的l了解计算机处理对象的特性，将现实世界中实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。l与此同时，通过算法训练提高计算机思维的能力，通过程序设计的技能训练来促进综合应用能力和专业素质的提高。6学习目的了解计算机处理对象的特性，将现实世界中实际问题中所涉教材教材1 严蔚敏等.数据结构（C语言版）,北京：清华大学出版社，1997年2 李根强 数据结构习题解答及实训指导 北京：中国水利出版社，2009年7教材1 严蔚敏等.数据结构（C语言版）,7参考资料参考资料1 殷人昆等.数据结构（用面向对象方法与C+描）,北京：清华大学出版社，1999年2 Bruno R.Preiss，数据结构与算法面向对象的C+设计模式，北京：电子工业出版社，2003年3 李春葆 数据结构习题与解析（C语言版 第二版）北京：清华大学出版社，2004年4 陈元春等编，用数据结构基础，中国铁道出版社2003年8参考资料1 殷人昆等.数据结构（用面向对象方法与C+第一章第一章 绪论绪论介绍数据结构的基本概念l1.什么是数据结构 l2.数据结构基本概念l3.抽象数据类型表示与实现l4.算法及算法分析9第一章 绪论介绍数据结构的基本概念91.1 什么是数据结构什么是数据结构信息管理、人工智能、文字处理加工对象：数 值字符、表格、图像或其他具有一定结构的数据l应用领域：科学计算101.1 什么是数据结构信息管理、人工智能、加工对象：字符、计算机解决问题的步骤计算机解决问题的步骤l用计算机解决具体实际问题时,一般过程如下:l从具体问题抽象出适当的数据模型抽象出适当的数据模型,l设计求解数据模型的算法求解数据模型的算法l编写程序编写程序,运行并调试程序,直到解决实际问题.举例举例:求水仙花数问题求水仙花数问题.l寻求数据模型实质是寻求数据模型实质是:分析问题,从中提取操作的对象提取操作的对象,并找出这些操并找出这些操 作对象之间的关系作对象之间的关系,然后用数学语言加以描述然后用数学语言加以描述.11计算机解决问题的步骤用计算机解决具体实际问题时,一般过程如下例例1.1 图书信息检索图书信息检索l登录号,书名,作者,出版社,出版日期等 构成一张表.每本书一个登录号.l要求按书名,作者,分类号等进行查找,建立分别按书名,作者名,分类号的顺序排列的索引表.l书目表书目表,书名书名,作者名作者名,分类号索引表分类号索引表 构成数学模型构成数学模型.12例1.1 图书信息检索登录号,书名,作者,出版社,出版图书信息表图书信息表 000001 高等数学樊映川 S01。000002 理论力学罗远祥 L01 。000003 高等数学华罗庚 S01 。000004 线性代数阳正宏 S02 。13图书信息表000001 高等数学樊映川 S01。000例例1.2 八皇后问题八皇后问题lN 皇后问题 是要求一个 NN 的棋盘上放置N 个皇后,每个皇后不能相遇 按国际象棋的规则,皇后可以横吃,竖吃,斜吃.l以简化的 四皇后问题为例,说明八皇后问题.四皇后问题最后结果如附图.四皇后最后的结果14例1.2 八皇后问题N 皇后问题 四皇后最后的结四皇后问题情形一四皇后问题情形一 15四皇后问题情形一 15例例1.3 交通灯管理问题交通灯管理问题交通管理问题（P3 图1.3）设计一个交通信号灯:使车辆通行时互相之间不能碰撞.问题转化为:对图上的每一个顶点染一种颜色,要求有连线的顶点颜色不能相同.16例1.3 交通灯管理问题交通管理问题（P3 图1.3）1例例1.4 交通咨询问题交通咨询问题城市公交线路图，求解出行路径。17例1.4 交通咨询问题城市公交线路图，求解出行路径。171.2 数据结构的基本概念数据结构的基本概念l数据（Data）信息的载体，它能够被计算机识别、存储和加工处理。l例如：数值计算中的整数和实数，编译程序或文本编辑程序中的字符串。多媒体技术中所涉及的视频和音频信号，经采集 转换后都能形成被计算机所接受的数据。181.2 数据结构的基本概念数据（Data）18第一讲第一讲19第一讲19基本术语基本术语l数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录。l数据元素类（Data Element Class）是具有相同性质的数据元素的集合。l例如：整数数据对象N0，1-1,2,-2 字母数据对象Ca,b,c20基本术语数据元素（Data Element）20数据结构的概念数据结构的概念l数据结构（数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。l 四类基本的结构：（图1.5）（1）集合 数据元素间的关系是属于同一个集合。（2）线性结构 数据元素之间存在一对一的关系。（3）树形结构 数据元素之间存在一对多的关系。（4）图状结构 数据元素之间存在多对多的关系，图状结构也称网状结构。21数据结构的概念数据结构（Data Structure）是指互数据的逻辑结构数据的逻辑结构l数据的逻辑结构可以看作是从具体问题中抽象出来的数学模型，它与数据的存储无关 逻辑结构线性：线性表、栈、队列、数组、串 非线性：广义表、树、图 22数据的逻辑结构数据的逻辑结构可以看作是从具体问题中抽象出来的数据结构定义举例数据结构定义举例Data Structure=(D,R)其中，D是数据元素的有限集，R是D上关系的有限集例如:按员工的编号来建立元素间的线性关系Linear-List=(D,R)其中：D=01,02,03,04,05,06,07,08,09,10 R,23数据结构定义举例Data Structure=(D,R)23l按行政分组来建立树形的数据结构Tree=(D,R)其中：D=01,02,03,04,05,06,07,08,09,10 R,l按员工的爱好来建立图状的数据结构 Graph=(D,R)其中：D=01,02,03,04,05,06,07,08,09,10,网，羽，乒 R,24按行政分组来建立树形的数据结构24数据的物理结构数据的物理结构l数据结构在计算机中的表示（又称映象）称为数据的物理结构，或称存储结构。l它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。物理结构顺序 使用一组连续的存储单元 非顺序链式索引存储、散列存储 25数据的物理结构数据结构在计算机中的表示（又称映象）称为数据的1.3 抽象数据类型表示与实现抽象数据类型表示与实现 l数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。l例如：整数类型，其取值的范围为-maxint,maxint上的整数 定义在其上的一组操作为加、减、乘、除及取模等。261.3 抽象数据类型表示与实现 数据类型（Data Typ抽象数据类型抽象数据类型l抽象数据类型（Abstract Data Type 简称 ADT）是指一个数学模型以及定义在该模型上的一组操作。l抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。27抽象数据类型抽象数据类型（Abstract Data Typ抽象数据类型的定义抽象数据类型的定义l抽象数据类型的定义可以由（元素、关系、操作）三种要素来进行定义（由于（由于 数据类型数据结构操作，数据类型数据结构操作，而数据结构数据元素元素间的关系）而数据结构数据元素元素间的关系）例如 栈的ADT定义：元素 属于同一个数据元素类。关系 数据元素间呈线性关系。操作 PUSH（S，X）进栈操作、POP（S）出栈操作等等 28抽象数据类型的定义抽象数据类型的定义可以由28实现方法的比较实现方法的比较l 面向过程的方法 在数据与操作二者之间并没有建立必然的联系 顺序执行l 面向对象的方法 相关的数据及操作被统一在一个整体对象之 中程序简洁有利于数据保护和代码重用 29实现方法的比较 面向过程的方法29栈演示程序栈演示程序l 面向过程的方法Node*top;char ch;Node*top;char ch;void push(char ch);void push(char ch);char pop();char pop();top=NULL;ch=top=NULL;ch=a a;while(ch!=while(ch!=E E)输入一个字符存入输入一个字符存入ch;ch;对对chch进行判别并进行相应的处理；进行判别并进行相应的处理；输出栈中的当前元素输出栈中的当前元素 ;l 面向对象的方法class class LinkStackLinkStack private:private:Node*top;Node*top;public:public:LinkStackLinkStack();();void init();void init();void prnt();void prnt();char pop();char pop();void push(char el);void push(char el);LinkStackLinkStack lz1;lz1;lz1.init();lz1.init();lz1.push(el);lz1.push(el);lz1.prnt();lz1.prnt();30栈演示程序 面向过程的方法 面向对象的方法301.4 算法及其分析算法及其分析 算法的概念：算法是对特定问题求解步骤的一种描述 算法的特性：有穷性、确定性、可行性、输入、输出算法的描述 自然语言。使用流程图、NS图等用于算法描述的工具，直接用某种高级程序设计语言来描述算法。使用伪码语言算法设计的要求 正确正确、可读、可读、健壮、健壮、高效高效 311.4 算法及其分析 31时间的复杂性分析时间的复杂性分析 表示形式：一个算法是由控制结构和原操作构成的。从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间量度。一般情况下，算法中原操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作：T(n)=o(f(n)该式表示算法中原操作的执行次数与问题规模n的某个函数同阶。32时间的复杂性分析 32常数阶、线性阶、平方阶常数阶、线性阶、平方阶 o(1)o(n)o(n2)x=x+1;for(i=1;i=n;i+)x=x+1;for(i=1;i=n;i+)for(j=1;j=n;j+)x=x+1;for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;/n for(k=1;k=n;k+)cij=cij+aik*bkj;/n2;33常数阶、线性阶、平方阶 o(1)o(n)o例例1.4 n阶矩阵相乘算法的时间复杂度阶矩阵相乘算法的时间复杂度 for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;/基本语句(1)for(k=1;k=n;k+)cij=cij+aik*bkj;/基语句(2);在通常情况下算法的时间复杂度是指基本语句重复执行的次数及频度。在上述算法中主要语句的频度分别是：基本语句(1)n2，基本语句(2)n3。该算法的时间复杂度所有语句的频度之和 T(n)=n2+n3=o(n3)。因此该算法时间复杂度为o(n3),称之为立方阶。34例1.4 n阶矩阵相乘算法的时间复杂度 34例例1.5 对数阶时间复杂度对数阶时间复杂度 i=1;/语句(1)while(i=n)i=i*2;/语句(2)其中语句(1)的频度是1，设语句(2)的频度是f(n)，则有 2 f(n)=n，即：f(n)=log2n，取最大值f(n)=log2n，因此该算法时间复杂度为:T(n)=1+log2n=o(log2n)35例1.5 对数阶时间复杂度 35空间的复杂性分析空间的复杂性分析 类似于时间复杂性分析,空间的复杂性也可以表示为问题规模的函数.表示形式：S(n)=o(f(n)36空间的复杂性分析 36例例1.6 空间的复杂性举例空间的复杂性举例 实例：将存放在一维数组a中的n个整数反向存放，即 将a1存放在原an存放的位置中，将a2存放在原an1存放的位置中，依次类推，直至将an存放在原a1存放的位置中。1.使用一组工作单元bn：for(i=1;i=n;i+)bn-i+1=ai;for(i=1;i=n;i+)ai=bi;2.只使用工作单元i与w：for(i=1;i=1;i-)ai=ai-1;a0=temp;时间复杂度 T(n)=1+(n-1)+1=o(n)线性阶空间复杂度 S(n)=2=o(1)常数阶39教学互动：算法及其算法分析39作业作业第一章 习题 1,5,7,8 1、给出以下算法的时间复杂度、给出以下算法的时间复杂度1）void funA(int n)Int i=1,k=100;While(i n)k=k+5;i+=2;2）void funB(int n)Int i,j,k,x=0;for(i=1;i n;i+)for(j=i+1;j=n;j+);x=x+1;40作业第一章 习题 40作业作业2、简述下列术语的喊含义？、简述下列术语的喊含义？数据、数据元素、数据对象、存贮结构、数数据、数据元素、数据对象、存贮结构、数据类型和抽象数据类型。据类型和抽象数据类型。3、数据结构在计算机内存中的表示是指什么？、数据结构在计算机内存中的表示是指什么？41作业2、简述下列术语的喊含义？41