数据结构（第3版）高职全套教学课件.pptx

《数据结构》 (第3版）;第1页;知识目标： 了解数据结构的发展 理解数据结构中的基本概念 理解抽象数据类型的概念、记法和用法 理解算法分析的目的 掌握算法及其特性 掌握算法时间复杂度的分析方法 技能目标： 能分析一般算法的时间复杂度;1.1 数据结构的发展;1968年，美国的唐纳德·欧文克努特（Donald E. Knuth）教授在他的历史性经典巨著《计算机程序设计艺术》（The Art of Computer Programming）第一卷《基本算法》中较系统地阐述了数据结构的逻辑结构和存储结构及其操作，开创了数据结构的课程体系。 20世纪70年代初，数据结构作为一门独立的课程进入大学课堂。 在我国，自1978年美籍华裔学者冀中田在国内首开这门课程以来，经过几十年的发展，这门课程已经成为各大学计算机专业的本科主干课程，也成为非计算机类学生和研究生学习计算机的必修课程。;1.2 数据结构的意义;1.3 数据结构的基本概念和术语;3．数据项（Data Item） 数据项（Data Item）是数据的最小单位，是对数据元素属性的描述，也称域或字段。例如，在图书管理系统中，可以把一本图书的有关信息作为一个数据元素，它由书名、作者、ISBN号、出版时间、出版社等等数据项组成。 4．数据对象（Data Object） 数据对象（Data Object）是性质相同的数据元素的集合，是数据的子集。例如，整数数据对象是集合N={0,±1，±2，……}；图书数据对象是集合A={“数据结构”，“数据库”，“软件工程”}。;第8页;第9页;（1）线性结构： 数据元素之间存在着一对一的关系。线性结构中有且仅有一个首结点和一个尾结点，首结点只有一个直接后继结点，尾结点只有一个直接前驱结点，其他结点有且仅有一个直接前驱和一个直接后继结点。如图1-1(a)。 【例1-1】 学生信息表 现有某大学学生信息表，如下表。其中，每个学生的信息由编号、姓名等数据项组成。;（2）非线性结构：非线性结构可细分为： 集合：数据元素之间同属于一个集合，除此之外没有其他关系。如图1-1(b)。 树形结构：数据元素之间存在着一对多的关系。如图1-1(c)。在现实生活中，部门的组织结构、体育比赛赛制安排等问题都可以用树形结构来描述。 【例1-2】 学生会组织结构 ;图结构：数据元素之间存在着多对多的关系。如图1-1(d)。当数据元素间有着多对多关系时，形成图形结构。如，交通、网络布线等等，许多问题模型都属于图结构。 【例1-3】 安排国际会议座位 举行一个国际会议， 有A，B，C，D，E，F，G共 7 个人。已知下列事实：A 会讲英语；B 会讲英语和汉语；C 会讲英语、意大利语和俄语；D 会讲日语和汉语；E 会讲德语和意大利语；F会讲法语、日语和俄语；G 会讲法语和德语。试问这7 个人应如何排座位，才能使每个人都能和他身边的人交谈？; 分析：问题中有“人和语言”。用结点来代表人；对于任意的两点，若有共同语言，就在它们之间连一条边，形成图1-3。通过这个图结构的模型，原问题就转化为在图中寻找一条通过每个结点一次且仅一次的回路的问题。;1.3.3 数据的存储结构;索引存储结构：在存储数据元素的同时，建立一个附加的索引表。利用索引表中索引项的值来确定结点的存储单元地址。 散列存储：根据数据元素的关键字通过散列函数直接计算出该数据元素的存储地址。 一种逻辑结构可以采用不同的存储结构，具体选定哪种存储结构，主要取决于算法运算的方便以及算法的时间空间利用率。　　;1.3.4 抽象数据类型;第17页;例如：队列的抽象数据类型描述如下: ADT Queue{ 数据对象：D={ai|ai为DataType类型，1≤i≤n，n≥0} /*DataType为自定义类型*/ 数据关系：R={ai-1,ai|ai-1, ai∈D, 2≤i≤n }。在非空表中，除了首结点，每个结点都有且只有一个前驱结点；除了尾结点外，每个结点都有且只有一个后继结点。队列中的数据元素只能在队尾一端进行插入，在队首一端进行删除操作。 基本操作： 　 InitQueue(Q)：初始化操作。建立一个空队列。 QueueEmpty(Q)：判断队列是否为空，如果为空，返回1；否则，返回0. EnQueue(Q,x)：入队操作。将元素x插入到队列Q的队尾。 DelQueue(Q,x)：出队操作。将队列Q的队头元素删除，将其值由变量x返回。 GetHead(Q,x)：取队头元素。将队列Q的队头元素值由变量x返回。 Cle