计算机科学导论数据结构与算法补充ppt课件.ppt

数据结构与算法(补充内容)计算机科学概论理解数据结构的概念,理解数据结构的逻辑和存储结构;理解算法的概念和算法的基本特性,了解算法复杂度的度量方法;理解线性数据结构,理解顺序存储和链式存储的存储方法;描述栈和队列、串和数组这几个线性数据结构的概念;了解非线性的数据结构,了解树、二叉树以及图的概念和数据结构;理解排序的概念,描述插入、选择、气泡和快速排序的算法;理解查找的概念,描述顺序查找和折半查找的算法,并能够比较它们理解递归的概念,能够在实践中了解递归的应用。教学目的123学****内容数据结构概述线性结构非线性结构基本算法递归45学****重点数据结构的基本概念算法的描述、流程图的使用以及算法的复杂度的衡量顺序存储和链式存储的方法栈、队列、串和数组的概念和用法二叉树数据结构查询、《数据结构》研究的对象(1)对所加工的对象进行逻辑组织(2)如何把加工对象存储到计算机中去(3)数据运算数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作[例6-1]设有一个电话号码薄,有N个人的姓名和电话号码。要求设计一个程序,按人名查找号码,若不存在则给出不存在的信息。 数据元素、结点、数据项、关键字或主关键字、次关键字、数据对象、 特性相同的数据元素构成的集合中,如果在数据元素之间存在一种或多种特定的关系,则称之为数据结构。 Data-Structure=(D,R)其中,D是数据元素的有限集,R是D上关系的有限集。。在集合结构中,数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构,各元素间没有直接的关联。线性结构。该结构的数据元素之间存在着一对一的关系。树型结构。该结构的数据元素之间存在着一对多的关系。图形结构。该结构的数据元素之间存在着多对多的关系,图形结构也称作网状结构。123456[例6-2]线性数据结构=(D,S) D={1,2,3,4,5,6,7,8,9,10}S={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>,<7,8>,<8,9>,<9,10>}