数据结构第1章绪论.ppt

1、数 据 结 构（C语言版,严蔚敏 吴伟民编著 清华大学出版社,数据结构课程的地位和作用,数据结构课程”是计算机专业的专业基础课。 学习“数据结构”课程需要一些课程作为它的基础，如“C语言”与“离散数学”。若没有“C语言”或其它语言基础，学生就难以理解描述数据结构及其算法的类C或类C+，更重要的是造成学生上机环节的困难，影响该课程的学习。同样，“离散数学”课程是“数据结构”课程的理论基础，其中集合、树及图等重要理论知识为“数据结构”课程的学习提供了重要的理论基础。 “数据结构”课程为“编译原理”、“数据库系统”和“操作系统”等课程的学习奠定必要的基础。例如：“编译原理”的表达式求解用到“数据结构

2、”的栈知识，符号表管理技术用到哈希查找技术；“数据库系统”的存储用到B+树知识；“操作系统”的设备链表管理用到线性链表知识，最短作业优先用到队列知识。 计算机解决现实问题的方法一般经历下列步骤： 建立数学模型设计解此模型的算法编程、调试 而数据结构几乎体现在问题求解的各个步骤，尤其是步骤2。可见学好数据结构具有十分重要的意义,数据结构的教学目的,懂得“数据结构+算法=程序” 培养数据抽象的能力 把数据结构和算法理论与编程实践相结合，能够在实际的工程实践中灵活地予以应用,数据结构的教学要求,掌握并灵活应用常用的基本数据结构的抽象数据类型、各种基本存储方法、主要的算法。 掌握并简单应用常用的排序、

3、检索和索引算法和方法。 掌握基本的算法设计和分析技术，并对自己设计的数据结构和算法进行简单的分析。 在进行程序设计、调试、测试的课程项目训练（即上机实习训练）过程中，要求学生综合应用所学到的数据结构和算法知识，学会分析研究数据对象的特性，以便选择合适的数据结构和存储结构以及相应的算法，合理地组织数据、有效地表示数据、有效地处理数据，书写的程序结构清楚、正确易读，提高程序设计的质量,参考书籍,数据结构教程（第3版）李春葆主编 清华大学出版社 数据结构（用面向对象方法与C+语言描述） （第2版） 殷人昆主编 清华大学出版社 数据结构课程设计（第2版）苏仕华主编 机械工业出版社,实验程序上交地址,信

4、息技术学院ftp地址： 内网访问： 外网访问： 用户名：stq 密 码：2,什么是数据结构 基本概念和术语 抽象数据类型的表示与实现 算法和算法分析,第1章 绪论,学习要点 1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 2. 了解抽象数据类型的定义、表示和实现方法。 3理解算法五个要素的确切含义：动态有穷性（能执行结束）；确定性（对于相同的输入执行相同的路径）；有输入；有输出；可行性（用以描述算法的操作都是足够基本的）。 4掌握计算语句频

5、度和估算算法时间复杂度的方法,1.1什么是数据结构,一般来说，用计算机解决一个具体问题时，需经历下列步骤： 建立数学模型设计解此模型的算法编程、调试 寻求数学模型的实质：分析问题，从中提取操作的对象，并找出对象之间的关系，然后用数学的语言加以描述,1.1 什么是数据结构 程序=数据结构+算法 例1 书目自动检索系统,书目文件,例2 人机对奕问题,数据结构定义,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科,1.2 基本概念和术语,1 数据（data） 数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。是计算机操作的对象的总称。 例如：数

6、字、字母、汉字、图形、图像、声音都称为数据,2数据元素（data element） 数据元素是组成数据的基本单位。 数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位,3 数据对象（data object） 是性质相同的数据元素组成的集合，是数据的一个子集。 例如，整数数据对象的集合可表示为N0，1，2.，字母字符数据对象的集合可表示为C=A,B,Z,4 数据类型（data type） 是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。 例如，高级语言中用到的整数数据类型，是指由32768到32767中值构成的集合及一

7、组操作（加、减、乘、除、乘方等）的总称,数据结构是相互之间存在一种或多种特定关系的数据元素的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为： （1）数据的逻辑结构独立于计算机，是数据本身所固有的。 （2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 （3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构,5. 数据结构（data structure,从逻辑结构划分数据结构,数据结构从逻辑结构划分为： （1）线性结构 元素之间为一对一的线性关系，第一个元素无直接前驱，最后

8、一个元素无直接后继，其余元素都有一个直接前驱和直接后继。 （2）非线性结构 元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继,根据数据元素间关系的基本特性，有四种基本数据结构,集合）数据元素间除“同属于一个集合”外，无其它关系,线性结构一个对一个，如线性表、栈、队列,树形结构一个对多个，如树,图状结构多个对多个，如图,从存储结构划分数据结构,数据结构从存储结构划分为： (1)顺序存储（向量存储） 所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。 (2) 链式存储 所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑

9、 上相邻的元素存放到计算机内存后不一定是相邻的,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,数据结构的抽象描述,数据结构可用二元组D=(K,R)的形式来描述。其中，K=a1,a2,an为元素集合，R=r1,r2,rm为关系的集合。 例1 设有一个线性表(a1,a2,a3,a4,a5)，它的抽象描述可表示为D=(K,R),其中K=a1,a2,a3,a4,a5,R=,，则它的逻辑结构用图描述见下图,例2 设一个数据结构的抽象描述为D=(K,R),其中

10、K=a,b,c,d,e,f,g,h,r=,则它的逻辑结构用图描述见下图,例3 设一个数据结构的抽象描述为D=(K,R),其中K=1,2,3,4,而R=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4), 则它的逻辑结构用图描述见下图,是指一个数学模型以及定义在该模型上的一组操作,一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。 抽象数据类型可用三元组表示： (D，S，P,6.抽象数据类型,采用以下格式定义抽象数据类型： ADT抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名,基本操作的定义格式为 基本操作名（参数表） 初始条件： 操作

11、结果： 基本操作有两种参数： 赋值参数：只为操作提供输入值 引用参数：以/由InitTriplet 分配3个元素存储空间 /-基本操作的函数原型说明- Status InitTriplet(Triplet /InitTriplet,1.4 算法的描述和算法分析 算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性,1）有穷性：算法必须在有限步内结束。2）确定性：组成算法的操作必须清晰无二义性。3）可行性：组成算法的操作必须能够在计算机上实现。 4）输入：0个或多个输入。 5）输出：1个或多个输出,算法的描述采用C语言 算法的评价衡量算法优劣的标准 正确性(co

12、rrectness) 可读性(readability) 健壮性(robustness) 效率与低存储量,算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量,1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件 等环境因素，有时容易掩盖算法本 身的优劣,2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于： 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使

13、用绝对时间单位衡量算法效率不合适,时间复杂度：基本操作重复执行的次数的阶数 T(n)=O(f(n) 空间复杂度：是指算法在计算机内执行时所占用的内存开销规模 s(n)=O(f(n,例1：NXN矩阵相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj;,基本操作: 乘法,基本操作重复执行次数是 n3 时间复杂度T(n)=O(n3,a) +x; s=0;,b) for (i=1;i=n;+i) +x; s+=x;,c) for ( j=1; j=n; +j) for ( k=1; k=n; +k) +x;

14、 s+=x;,含基本操作“x自增1”的语句的频度是1， 则T(n)=O(1)，称为常量阶,含基本操作“x自增1”的语句的频度是n， 则T(n)=O(n)，称为线性阶,含基本操作“x自增1”的语句的频度是n2， 则T(n)=O(n2) ，称为平方阶,补充：求时间复杂度的方法 选择基本操作 计算基本操作的重复执行次数 写出T(n)=O(f(n,若计算出的基本操作的重复执行次数是： aknk + ak-1nk-1+ a1n+a0 （其中，ak a0是常数，n是问题规模） 则T(n)=O(nk,例2 起泡排序 void bubble_sort(int a, int n) / 将a中整数序列重新排列成自

15、小至大有序的整数序列。 for (i=n-1, change=TRUE; i=1 / bubble_sort 基本操作: 交换序列中相邻两个整数,最坏时间复杂度T(n)=O(n2,最好情况下，即a中初始序列为自小至大有序，基本操作的执行次数为0,最坏情况下，即a中初始序列为自大至小有序，基本操作的执行次数为(n-1)+(n-2)+1=n(n-1)/2,例3 分析下列算法段的时间频度及时间复杂度 for(i=1;i=n;i+) for (j=1;j=i;j+) for ( k=1;k=j;k+) x=i+j-k,T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n) = = = + = + 故时间复杂度为(n3,在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)。另外，在语句频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不