数据结构使用C语言朱战立.ppt

《数据结构使用C语言朱战立.ppt》由会员分享，可在线阅读，更多相关《数据结构使用C语言朱战立.ppt（53页珍藏版）》请在三一办公上搜索。

1、教材：朱战立编著，数据结构使用C语言（第3版），西安交通大学出版社，2003年,数 据 结 构,2,学时数：70（50学时授课20学时上机）教材：朱战立编著，数据结构（使用C语言）第3版，西 安交通大学出版社，2003年参考书：1严蔚敏等，数据结构（C语言版），清华大学出版社2 数据结构学习指导与典型题解，朱战立等编著，西安交通大学出版社，2002年,3,内 容 安 排,4,1、上课认真听讲，适当做好笔记。2、考试成绩分两部分：平时成绩（包括出勤和上机实验）占20%，期末成绩占80%。3、课后需要多读课文和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。4、上机实验十分重要，

2、一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实现算法解决一个问题。,对学生的几点要求,5,第1章绪论,讨论5个问题：,1.1 数据结构的基本概念1.2 抽象数据类型和软件构造方法1.4 算法和算法的时间复杂度1.5 算法书写规范,6,1.1 数据结构的基本概念,1、举例 建立一个学生档案系统。学生表包括学号、姓名、性别、籍贯。要求：查找“王红”是否存在。解决的方法步骤：如何记录所有学生记录（及选择何种逻辑数据结构）？选择何种存储结构？若把所有记录依次存储在一个数组中采用顺序存储结构若采用指针链表采用链式存储结构,7,为什么要学习数据结构？什么是程序、软件？N.沃思（Niklau

3、s Wirth)教授提出：程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构算法）。软件=程序+文档（软件工程的观点）,8,电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。,数值计算解决问题的一般步骤：数学模型选择计算机语言编出程序测试最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述,10,例1.1 电话号码查

4、询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引 要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。,非数值计算问题：,11,例1.2 田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。,非数值计算问题：,12,（1）设用如下六个不同的代号代表不同的项目：跳高 跳远 标枪 铅球 100米 200米A B C D E F（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有

5、边相连（不能同时比赛）。,非数值计算问题-田径赛的时间安排问题解法,13,只需安排四个单位时间进行比赛,14,非数值计算问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,15,数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构

6、”的内容。70年代后期，我国高校陆续开设该课程。,16,17,数据结构课程的地位,它是计算机专业及相关专业的核心课程之一，是计算机及相关专业的重要骨干基础课程。它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。即其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。,18,数据结构课程所处的地位：,19,数据结构的核心研究内容,数据的逻辑结构、存储结构及它们之间的关系和相应的基本操作运算的定义和实现。本书围绕数据结构的三种基本结构：线性结构（第2-5章）、树形结构（第7章）和图形结构（第8章）展开讨论，研究解决如下问题：一个具体问题的逻辑数据结构是什么？

7、适宜选用什么样的存储结构？采用什么样的操作实现算法效率更高？,20,2、基本术语,(1)数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。(2)数据元素:是数据的基本单位，具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。(3)数据项:构成数据元素的项目。它是数据不可分割的最小单位。(4)数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：数组、结构、联合、指针、枚举等）,(5)抽象数据类型（Abstruct Data Type，简称ADT）：是指一个数

8、学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。(6)抽象数据元素：抽象定义的、没有实际含义的数据元素。,21,22,2、基本术语(续）,(7)数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。逻辑结构、存储结构和运算合称为三要素。表示为：Data_Structure=（D,R）其中，D元素有限集，R关系有限集,23,数据结构涵盖的内容,24,集合结构：仅同属一个集合线

9、性结构:一对一（1:1)树 结 构:一对多（1:n)图 结 构:多对多(m:n),非线性,线 性,逻辑结构可细分为4类：,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,解释1：什么叫数据的逻辑结构？,25,（1）S=(D,R)D=a,b,c,d,e,f R=(a,e),(b,c),(c,a),(e,f),(f,d),解：上述表达式可用图形表示为：,b c a e f d,此结构为线性的。,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,26,d1 d5 d2 d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,（

10、2）S=(D,R)D=di|1i5 R=(di,dj),ij,27,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构可分为4大类：,例：复数3.02.3i 的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,解释2：什么叫数据的物理结构？,28,答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,解释3：什么是数据的运算？,练习1、设有数据逻辑结构为：line=(D,R);其中D=01，02，03，04，05，06；R=r；r=，,.

11、试分析该数据结构属于哪种逻辑结构。01-02-05-04-06-03线性结构,29,2、设有数据逻辑结构为tree=D,R,其中D=01,02,03,04,05,06,07,08;R=r；r=,.试分析该数据结构属于哪种逻辑结构.树型,30,作业,什么是逻辑结构与存储结构，他们之间的关系如何？,31,设有数据逻辑结构为：line=(D,R);其中D=a，b，c，d，e，f,g；R=r；r=，,.试画出对应的图形并说明属于哪种逻辑结构.,32,将上述关系改为r=，,.试画出对应的图形并说明属于哪种逻辑结构.,33,34,1.4 什么是抽象数据类型,1 数据类型与抽象数据类型的区别？2 抽象数据类

12、型如何定义？3 抽象数据类型如何表示和实现？,讨论：,35,1 数据类型与抽象数据类型的区别,数据类型：是一个值的集合和定义在该值上的一组操作的总称。,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）,36,2 抽象数据类型如何定义,抽象数据类型可以用以下的三元组来表示：ADT=（D，R，P）,ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名,ADT常用定义格式,数据对象,D上的关系集,D上的操作集,37,1.4.3

13、抽象数据类型如何表示和实现,抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。（参看课本P28，线性表的抽象数据类型，思考用具体C语言如何实现）,注意：上机时要必须用具体语言实现，如C或C+等,队列的抽象数据类型定义ADT Queue数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=1,2,n 约定a1为队列头，an为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：销毁队列Q。QueueLength(Q)初始条件：队列Q已存在。操作

14、结果：返回Q的数据元素个数，即队列的长度。,38,39,1.5 算法效率的度量,1 什么是算法？如何评判算法的好坏？2 时间复杂度和空间复杂度如何表示？3 计算举例,讨论：,40,1 什么是算法？如何评判一个算法的好坏？,常用时间复杂度来衡量,算法的基本特性：,算法评价指标：,有穷性、确定性、可行性、必有输出,正确性、可读性、健壮性、高效率与低存储量需求(见课本P20),常用空间复杂度来衡量,好的程序设计：好算法好结构,算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。,有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在

15、有穷时间内完成。确定性：每条指令必须有确切的含义可行性：算法是能行得通的必有输出,41,正确性：算法应当满足具体问题的需求可读性：算法的可读性有利于人们对算法的理解健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的结果。效率与低存储需求：时间短，存储空间少（两者不能兼得）,42,1.3.3 算法效率的度量,求解同一个问题,可以有许多不同的算法,究竟如何评价这些算法的好坏呢?显然,选用的算法首先应该是“正确的”.此外,主要考虑如下三点:(1)执行算法所消耗的时间;(2)执行算法所消耗的存储空间,其中主要考虑辅助存储空间.(3)算法应该易于理解,易于编码,易于调试等.

16、,43,时间复杂度(time complexity),语句频度(Frequency Count)语句重复执行的次数语句的执行时间 语句频度执行一次所需时间算法的执行时间 所有语句执行时间的总和算法的渐近时间复杂度(asymptotic time complexity)，简称时间复杂度 因为语句的执行时间取决于机器的硬件速度、指令类型、以及编译所产生的代码质量，所以将算法中基本操作的最大语句频度作为算法执行时间的量度，它是问题规模n 的某个函数 f(n),44,时间复杂度表示法 记作T(n)=O(f(n)（称为大O表示法)，表示随问题规模n 的增大，算法执行时间的增长率和f(n)的增长率相同。时

17、间复杂度往往不是精确的执行次数，而是估算的数量级，它着重体现的是随着问题规模n的增大，算法执行时间的变化趋势 时间复杂度的数量级 O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(3n)O(n!),例如在下列三个程序段中：(a)x=x+1；(b)for(i=1;i=n;i+)x=x+1;(c)for(j=1;j=n;j+)for(k=1;k=n;k+)x=x+1;基本语句均为 x=x+1;程序段(a)中频度为1，则T(n)=O(1)；程序段(b)中频度为n，则T(n)=O(n)；程序段(c)中频度为n2，则T(n)=O(n2)。,时间复杂度的求解,算法1.1的

18、时间复杂度void sort(ElemType SMAXSIZE，int n)*对数组S中的n个数据按由大到小的顺序排序并输出,nMAXSIZE*/for(i=1;in;i+)for(j=i；j=n；j+)if(SiscoreSjscore)t=Si；Si=Sj；Sj=t；for(i=1；i=n；i+)printf(“%8d%8d%8dn”,i,Si.no,Si.score);/*sort*/算法中if语句的执行频度为：n+(n-1)+(n-2)+3+2+1=n*(n+1)/2 T(n)=O(n2),加法规则(针对并列程序段)T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)

19、乘法规则(针对嵌套程序段)T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)算法1.1中既有并列程序段又有嵌套程序段 并列程序段：T(n)=O(max(n2,n)=O(n2)嵌套程序段：T(n)=O(f(n)*g(n)=O(n2),有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Void bubble-sort(int a，int n)for(i=1;iaj+1)flag=1;aj aj+1;,分析算法复杂度：最好情况：0次最坏情况：1+2+3+n-1=n(n-1)/2 平均时间复杂度为:O(n2),50,空间复杂度度量（Space Complexity

20、）,空间是指执行算法所需用的存储空间存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成员等)变量所占的空间可变部分递归栈所用的空间、通过malloc()和free()等函数动态使用的空间与问题规模 n 的函数关系表示为：S（n）=O（f(n)）,52,本章小结,数据结构课程 数据结构算法程序，涉及数学、计算机硬件和软件。数据结构定义指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。数据结构内容数据的逻辑结构、存储结构和基本运算。数据结构描述工具抽象数据类型和C语言。算法效率时间效率和空间效率。,53,作业：,课本P25 1.2，1.3，1.4，1.7，1.10，1.11 题。建议独立完成辅导材料第1章自测卷。复习C语言，重点是结构类型、指针和数组概念等。,