计算机科学导论数据结构与算法优选ppt资料.ppt

计算机科学导论(dǎolùn)数据结构与算法理解数据结构的概念，理解数据结构的逻辑和存储结构；理解算法的概念和算法的基本特性，了解算法复杂度的度量方法；理解线性数据结构，理解顺序存储和链式存储的存储方法；描述栈和队列、串和数组这几个线性数据结构的概念；了解非线性的数据结构，了解树、二叉树以及图的概念和数据结构；理解排序的概念，描述插入、选择、气泡和快速排序的算法；理解查找的概念，描述顺序查找和折半查找的算法，并能够比较它们(tāmen)理解递归的概念，能够在实践中了解递归的应用。学习重点第一节数据结构(shùjùjiéɡòu)概述1.数据结构(shùjùjiéɡòu)概述1.数据结构(shùjùjiéɡòu)概述1.2数据结构相关概念1.基本概念和术语数据元素、结点、数据项、关键字或主关键字、次关键字、数据对象、数据结构2.数据结构特性相同的数据元素构成的集合中，如果在数据元素之间存在一种(yīzhǒnɡ)或多种特定的关系，则称之为数据结构。Data-Structure=(D,R)其中，D是数据元素的有限集，R是D上关系的有限集。1.数据结构(shùjùjiéɡòu)概述[例5-2]线性数据结构(shùjùjiéɡòu)=(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>}[例5-3]图形(túxíng)数据结构=(D,R)D={1,2,3,4,5,6,7,8,9}R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}[例5-4]树形结构(jiégòu)=（D,R）D={a,b,c,d,e,f,g,h,i,j,k,l}R={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,<b,g>,<c,h>,<c,i>,<c,j>,<d,k>,<d,l>}1.3数据结构的分类1、按数据结构的性质划分数据的逻辑结构——数据元素之间的逻辑关系（设计算法——数学模型）数据的物理结构——数据结构在计算机中的映像（存储结构，算法的实现）2、按数据结构的操作来划分静态结构——经过操作后，数据的结构特征保持不变（如数组）。半静态结构——经过操作后，数据的结构特性只允许(yǔnxǔ)很小变迁（如栈、队列）。动态结构——经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。1.3数据结构的分类3、按数据结构在计算机内的存储方式来划分顺序存储结构——借助元素在存储器的相对位置来表示数据元素之的逻辑关系。链式存储结构——借助指示元素存储地址的指针表示数据元素之间的逻辑关系索引存储结构——在存储结点的同时(tóngshí)，建立附加的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。散列存储结构——根据结点的关键字直接计算出该结点的存储地址。说明：四种存储方法可结合起来对数据结构进行存储映像。1.4算法及其描述和算法分析1、算法的概念及特征算法:对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列。算法具有以下五个重要的特征：1）有穷性：一个算法必须保证执行有限步之后结束。2）确切性：算法的每一步骤必须有确切的定义。3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了(chúle)初始条件。4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。5）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。1.4算法及其描述(miáoshù)和算法分析2、算法的描述(miáoshù):1）流程图2）伪代码——类程序设计语言3、算法的基本结构:1）顺序结构2）分支结构3）循环结构1.数据结构(shùjùjiéɡòu)概述1.4算法及其描述和算法分析4、算法效率衡量(héngliáng)方法与准则:时间复杂度：指算法从开始执行到处理结束所需要的总时间。T（n）=O（f(n)）空间复杂度：指算法从开始执行到处理结束所需的存储量空间的总和。S（n）=O（g(n)）1.4算法及其描述和算法分析5、算法与数据结构的关系:计算机科学家沃斯（）提出的:“算法+数据结构=程序”揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定(juédìng)如何构造数据。第二节线性结构(jiégòu)2.1线性表1.线性表的定义线性表是n(n>