《常用软件算法基础》课件-第章 绪论

本门课程安排概述（理论2+上机2）学生信息管理设计（理论2+上机2）顺序表（理论4+上机4）链表（理论4+上机4）栈（理论2+上机2）队列（理论2+上机2）树和树的遍历（理论4+上机4）查找（理论4+上机4）排序（理论4+上机4）算法（理论2+上机2）机动和复习（理论2+上机2）本课程学习要求

平时出勤12分旷课一次扣1分，扣完12分，取消考试资格。平时作业24分（8次每次3分）独立完成，发现抄袭：抄袭者记-3分，被抄袭者纪0分上机作业24分（8次每次3分）独立完成，发现抄袭：抄袭者记-3分，被抄袭者纪0分项目设计（课程设计）20分分小组完成。期末理论考试20分本课程的总体要求要求：1.掌握常用数据结构的基本概念和操作。2.熟悉常用算法的设计和编程思想。3.利用数据结构和算法完成简易的学生信息系统开发。4.了解使用三层结构进行项目开发的基本思想。第一章概述教学目标：了解数据结构的相关概念和掌握算法的基本概念和性质算法的性能分析和评价重点：算法的概念、描述方法、评价标准和分析难点：算法分析内容组织结构：1.1数据结构的基本概念1.2算法的基本概念和特征1.3算法的评价与分析1.1.1数据结构的种类（线性）

程序=数据结构+算法例1书目自动检索系统书目文件按姓名按专业按年级索引表线性表1.1.1数据结构的种类（树）例2人机对奕问题树……..……..…...…...…...…...1.1.1数据结构的种类（图）图课程编号课程名称先修课程C1计算机导论无C2数据结构C1，C4C3汇编语言C1C4C程序设计语言C1C5计算机图形学C2，C3，C4C6接口技术C3C7数据库原理C2，C9C8编译原理C41.1.2数据结构的科学发展背景.应用领域从最初的简单科学计算逐步发展到人类活动的各个领域，例如企业管理、工程过程控制、经济系统工作及管理信息系统等.计算机处理的对象从简单的数值和字符扩大到现在的带有不同复杂结构的各种数据。例如图像、声音及信号等面对不同的数据处理对象，不同的要求，数据的组织形式、存储及运算必须有不同的方法，才能进行有效的处理。因此努力研究数据的内在结构，分析待处理的对象的特征以及各处理对象的关系，才能寻找到某些规律性的方法，编写出好的程序。1.1.3数据结构的学科地位.综合性的专业基础课.介于数学、计算机硬件和计算机软件之间的核心课程.不仅仅是程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的基础1.1.4数据结构的基本概念和术语数据（data)—所有能输入到计算机中去的描述客观事物的符号数据元素（dataelement）—数据的基本单位，也称节点（node）或记录（record）数据项（dataitem）—有独立含义的数据最小单位，也称域(field)数据对象（dataObject）—具有共同特性的元素集合，是数据的一个子集数据结构（datastructure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图1.1.4数据结构的基本概念和术语数据的逻辑结构—指抽象反映数据元素的逻辑关系。它是从具体问题中抽象出来的数学模型。是独立于计算机存储器（与具体的计算机无关）。可分为如下几种基本类型：集合结构：线性结构：树型结构：图形结构：数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的存储方式。可分为如下两种类型。顺序存储结构：链式存储结构：数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 1.1.4数据结构的基本概念和术语存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系索引存储：在数据文件的基础上增加一个索引文件，通过索引表建立索引，可以将一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。散列存储：是通过数据元素与存储地址之间建立某种映射关系，使每个数据元素与每个存储地址之间尽量达到一对一的关系。链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3

∧元素41345h存储地址

存储内容

指针1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

链式存储

h

数据的逻辑结构

数据的存储结构数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构数据结构的三个方面：1.2算法的基本概念和特征算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列算法的三要素—算法由操作、控制结构、数据结构3要素组成。操作：算术运算：加、减、乘、除。关系比较：大于、小于、等于、不等于逻辑运算：与、或、非数据传送：输入、输出（计算）、赋值（计算）。控制结构：顺序结构：选择结构：循环结构：数据结构：1.2算法的基本概念和特征算法基本性质—目的性----算法有明确的目的，算法能完成赋予它的功能。分步性----算法为完成其复杂的功能，由一系列计算机可执行的步骤组成。有序性----算法的步骤是有序的，不可随意改变算法步骤的执行顺序。有限性----算法是有限的指令序列，算法包含的步骤是有限的。操作性----有意义的算法总是对某些对象进行操作，使其改变状态，完成其功能。1.2算法的基本概念和特征算法特征—1.3算法的评价算法的评价—衡量算法优劣的标准1)、正确性（correctness）算法对于一切合法的输入数据都能得出满足要求的结果；对于精心选择的、典型的、苛刻的几组输入数据，算法也能得出满足要求的结果。2）可读性（readability）算法主要是为了人的阅读与交流，其次才是让计算机执行。因此算法应该易于人的理解；另一方面，难读的算法易于隐藏较多错误而难以调试；有些算法设计者总是把自己设计的算法写的只有自己才能看懂，这样的算法反而没有太大的实用价值。1.3算法的评价算法的评价—衡量算法优劣的标准3）稳健性（robustness）当输入的数据非法时，算法应当恰当地做出反映或进行相应处理，而不是产生莫名其妙的输出结果。这就需要一定充分地考虑可能的异常情况，并且处理出错的方法不应当是简单中断算法的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4）高效率与低存储量的要求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者多与问题的规模无关。1.3算法评价：对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量、占用存储空间等诸多因素。其中评价算法的3条主要标准是：（1）算法实现所耗费的时间（时间复杂度）。（2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间（空间复杂度）。（3）算法应易于理解、易于编码、易于调试等。1.3算法评价—度量算法时间的两种方法：算法效率——用依据该算法编制的程序在计算机上执行所消耗的时间来度量：评价的方法有：

1.事后统计——利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣1.3算法评价—度量算法时间的两种方法：2.事前分析估计——一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用绝对时间单位衡量算法效率不合适1.3算法评价—时间复杂度计算：时间复杂度的：在算法分析中，算法整个运行过程所耗费的时间：具体计算如下：1.每个赋值语句或读/写语句的运行时间通常是O(1）。但有一些例外情况,如赋值语句的右部表达式可能出现函数调用,这时就要考虑计算函数值所耗费的时间。1.3算法评价—时间复杂度计算：2.顺序语句的运行时间由线性规则决定，即为该序列中耗费时间最多的语句的运行时间。3.语句if的运行时间为条件语句测试时间（通常取0(1)）加上分支语句的运行时间，语句if-else-if的运行时间为条件测试时间加上分支语句的运行时间。4.循环语句的运行时间是n次重复执行循环体所耗费时间的总和。5.O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)1.3算法评价—时间复杂度案例分析：时间