数据结构1绪论课件.ppt

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

1、数据结构 付细楚 2011年2月1联系方式电子邮件：欢迎同学们共同交流和探讨。2课程的性质l 综合性的专业基础课程l 软件专业课程体系中的核心课程先修课:C+程序设计语言,离散数学后续课:几乎所有的软件方面课程,如:操作系统,编译原理,算法分析 与设计,应用系统开发等.3课程安排l 教学安排:教学总学时数 56学时（其中 讲授:40课时,实验 16 课时）数据结构与算法课程设计（2周）l 10软件4、5、6、7、8班 4研究对象主要是研究：非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作 5学习目的l 了解计算机处理对象的特性，将现实世界中实际问题中所涉及的处理对象在计

2、算机中表示出来并对它们进行处理。l 与此同时，通过算法训练提高计算机思维的能力，通过程序设计的技能训练来促进综合应用能力和专业素质的提高。6教材1 严蔚敏等.数据结构（C语言版）,北京：清华大学出版社，1997年2 李根强 数据结构习题解答及实训指导 北京：中国水利出版社，2009年7参考资料1 殷人昆等.数据结构（用面向对象方法与C+描）,北京：清华大学出版社，1999年2 Bruno R.Preiss，数据结构与算法面向对象的C+设计模式，北京：电子工业出版社，2003年3 李春葆 数据结构习题与解析（C语言版 第二版）北京：清华大学出版社，2004年4 陈元春等编，用数据结构基础，中国铁

3、道出版社2003年8第一章 绪论介绍数据结构的基本概念l 1.什么是数据结构 l 2.数据结构基本概念l 3.抽象数据类型表示与实现l 4.算法及算法分析91.1 什么是数据结构信息管理、人工智能、文字处理 加工对象：数 值字符、表格、图像或其他具有一定结构的数据l 应用领域：科学计算10计算机解决问题的步骤l 用计算机解决具体实际问题时,一般过程如下:l 从具体问题抽象出适当的数据模型,l 设计求解数据模型的算法l 编写程序,运行并调试程序,直到解决实际问题.举例:求水仙花数问题.l 寻求数据模型实质是:分析问题,从中提取操作的对象,并找出这些操 作对象之间的关系,然后用数学语言加以描述.1

4、1例1.1 图书信息检索l 登录号,书名,作者,出版社,出版日期等 构成一张表.每本书一个登录号.l 要求按书名,作者,分类号等进行查找,建立分别按书名,作者名,分类号的顺序排列的索引表.l 书目表,书名,作者名,分类号索引表 构成数学模型.12图书信息表 000001 高等数学 樊映川 S01。000002 理论力学 罗远祥 L01。000003 高等数学 华罗庚 S01。000004 线性代数 阳正宏 S02。13例1.2 八皇后问题l N 皇后问题 是要求一个 NN 的棋盘上放置N 个皇后,每个皇后不能相遇 按国际象棋的规则,皇后可以横吃,竖吃,斜吃.l 以简化的 四皇后问题为例,说明八

5、皇后问题.四皇后问题最后结果如附图.四皇后最后的结果14四皇后问题情形一 15例1.3 交通灯管理问题交通管理问题（P3 图1.3）设计一个交通信号灯:使车辆通行时互相之间不能碰撞.问题转化为:对图上的每一个顶点染一种颜色,要求有连线的顶点颜色不能相同.16例1.4 交通咨询问题城市公交线路图，求解出行路径。171.2 数据结构的基本概念l 数据（Data）信息的载体，它能够被计算机识别、存储和加工处理。l 例如：数值计算中的整数和实数，编译程序或文本编辑程序中的字符串。多媒体技术中所涉及的视频和音频信号，经采集 转换后都能形成被计算机所接受的数据。18第一讲19基本术语l 数据元素（Data

6、 Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录。l 数据元素类（Data Element Class）是具有相同性质的数据元素的集合。l 例如：整数数据对象N0，1-1,2,-2 字母数据对象Ca,b,c20数据结构的概念l 数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。l 四类基本的结构：（图1.5）（1）集合 数据元素间的关系是属于同一个集合。（2）线性结构 数据元素之间存在一对一的关系。（3）树形结构 数据元素之间存在一对多的关系。（4）图状结构 数据元素之间存在多对多的关系，图状结构也称网状结构。2

7、1数据的逻辑结构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,23l 按行政分组来建立树形的数据结构Tree=(D,R)其中：D=01,02,03,04,05,06,07,08,09,10 R,l 按员工的爱好来建立图状的数据结构 Graph=

8、(D,R)其中：D=01,02,03,04,05,06,07,08,09,10,网，羽，乒 R,24数据的物理结构l 数据结构在计算机中的表示（又称映象）称为数据的物理结构，或称存储结构。l 它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。物理结构顺序 使用一组连续的存储单元 非顺序链式索引存储、散列存储 251.3 抽象数据类型表示与实现 l 数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。l 例如：整数类型，其取值的范围为-maxint,maxint上的整数 定义在其上的一组操作为加、减、乘、除及取模等。26抽象数据类型

9、l 抽象数据类型（Abstract Data Type 简称 ADT）是指一个数学模型以及定义在该模型上的一组操作。l 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。27抽象数据类型的定义l 抽象数据类型的定义可以由（元素、关系、操作）三种要素来进行定义（由于 数据类型数据结构操作，而数据结构数据元素元素间的关系）例如 栈的ADT定义：元素 属于同一个数据元素类。关系 数据元素间呈线性关系。操作 PUSH（S，X）进栈操作、POP（S）出栈操作等等 28实现方法的比较l 面向过程的方法 在数据与操作二者之间并没有建立必然的联系 顺序执行l 面向对象的方法 相

10、关的数据及操作被统一在一个整体对象之 中程序简洁有利于数据保护和代码重用 29栈演示程序l 面向过程的方法Node*top;char ch;void push(char ch);char pop();top=NULL;ch=a;while(ch!=E)输入一个字符存入ch;对ch进行判别并进行相应的处理；输出栈中的当前元素;l 面向对象的方法class LinkStack private:Node*top;public:LinkStack();void init();void prnt();char pop();void push(char el);LinkStack lz1;lz1.init

11、();lz1.push(el);lz1.prnt();301.4 算法及其分析 算法的概念：算法是对特定问题求解步骤的一种描述 算法的特性：有穷性、确定性、可行性、输入、输出算法的描述 自然语言。使用流程图、NS图等用于算法描述的工具，直接用某种高级程序设计语言来描述算法。使用伪码语言算法设计的要求 正确、可读、健壮、高效 31时间的复杂性分析 表示形式：一个算法是由控制结构和原操作构成的。从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间量度。一般情况下，算法中原操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作：T(n)=o(f(n)该

12、式表示算法中原操作的执行次数与问题规模n的某个函数同阶。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例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);在 通

13、 常 情 况 下 算 法 的 时 间 复 杂 度 是 指 基 本 语 句 重 复 执 行的次数及频度。在上述算法中主要语句的频度分别是：基本语句(1)n2，基本语句(2)n3。该算法的时间复杂度所有语句的频度之和 T(n)=n2+n3=o(n3)。因此该算法时间复杂度为o(n3),称之为立方阶。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空

14、间的复杂性分析 类似于时间复杂性分析,空间的复杂性也可以表示为问题规模的函数.表示形式：S(n)=o(f(n)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=n/2;i+)w=ai;ai=an-i+1;an-i+1=w;37教学互动：算法及其算法分析试写一个算法，实现将数组an中的n个整数

15、循环后移一个位置，并给出它的时间复杂度和辅助空间的大小。38教学互动：算法及其算法分析int i,temp;temp=an-1;for(i=n-1;i=1;i-)ai=ai-1;a0=temp;时间复杂度 T(n)=1+(n-1)+1=o(n)线性阶空间复杂度 S(n)=2=o(1)常数阶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作业2、简述下列术语的喊含义？数据、数据元素、数据对象、存贮结构、数据类型和抽象数据类型。3、数据结构在计算机内存中的表示是指什么？41