数据结构基本概念.pptVIP

voidselectSort(inta[],constintn){//对n个整数a[0],a[1],…,a[n-1],按非递减顺序排序for(inti=0;in-1;i++){intk=i;//从a[i]检查到a[n-1],找最小的整数,在a[k]for(intj=i+1;jn;j++) if(a[j]a[k])k=j; //k指示当前找到的最小整数inttemp=a[i];a[i]=a[k];a[k]=temp;//交换a[i]与a[k]}} 算法的性能标准算法的空间复杂性算法的时间复杂性算法的性能分析与度量算法的性能标准数据结构的优劣与算法直接有关，其性能由实现其各个服务的算法来体现。对数据结构的分析实质上是对实现其各个服务的算法的性能的分析。判断一个算法的优劣的标准：正确性——最重要标准要求算法能够正确地执行预先规定的功能和性能要求。要求算法的编写者对问题要求有正确的理解；正确地、无歧义地描述和利用某种编程语言正确地实现对算法的要求。可使用性——用户友好性要求算法能够很方便地使用。为了便于用户使用，要求算法具有良好的界面，完备的用户文档。算法设计必须符合抽象数据类型和模块化的要求；最好所有的输入和输出数据都通过参数表显示地传递，少用公共变量；每一个算法只完成一个功能。可读性算法应当可读，是理解、测试和修改算法的需要。为了达到这一要求，算法逻辑必须清晰、简单和结构化：所有的变量名、函数名的命名必须有实际含义，让人见名知义；在算法中必须加入注释，简要说明：算法的功能；输入与输出参数的使用规则；重要数据的作用；算法中各程序段完成的功能等。效率算法执行时计算机资源的消耗，包括存储（空间代价）和运行时间（时间代价）的开销。与多种因素有关：计算机系统、可用存储容量和算法复杂性。健壮性——容错性或例外处理要求在算法中加入对输入参数、打开文件、读文件记录、子程序调用状态进行自动检错、报错并通过与用户对话来纠错的功能。一个算法必须具有健壮性，能够对不合理的数据进行检查。在算法初写时可暂不管，待算法成熟时再追加。算法的运行时间依赖于所使用的计算机系统、编译器、可用存储空间大小等。同样的算法在速度不同的计算机上，执行速度相差非常大。算法用不同的编译器编译出的目标代码不一样长，完成同样功能所需时间不同。如果可用存储空间不够，算法需要的运行时间很多；如果空间足够大，则时间明显减少。通过比较算法的复杂性来评价。算法复杂性与具体运行环境和编译器无关。空间复杂性(SpaceComplexity)当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占的存储空间也以某种单位由1增加到f(n)。问题的规模可以从问题的描述中找到。因为算法针对某一实例（类的对象），问题规模可视为实例的特性。在有n个记录的学生文件中查找某个学生，或者对一个n阶线性方程求解，n即为问题的规模。空间单位一般规定为一个工作单元所占的存储空间的大小。********数据结构

DATASTRUCTURE——用C描述第一章基本概念什么是数据结构数据结构的抽象层次算法定义性能分析与度量初等项：如学生性别、籍贯等，不能再分割的最小数据单位。1组合项：如一组成绩，可以再划分为物理成绩、化学成绩等更小的项。2“学生”表格选课关系包含如下信息学号课程编号成绩学生选课系统中实体构成的网状关系UNIX文件系统的系统结构图在应用程序中涉及到各种各样的数据，为了存储它们，组织它们，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，并依此实现要求的软件功能。数值性数据如整数、实数、双精度数等主要用于工程和科学计算，及商业事务处理中使用。非数值性数据如字符串、多媒体信息（文字、图形、语音）等。数据：信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。01整数数据对象N={0,?1,?2,…}英文字母数据对象LETTER={‘A’,‘B’,…,‘Z’}学生数据对象数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。02什么是数据结构？定义:一组数据对象及数据对象之间的关系组成。记为