搜索
合肥工业大学计算机与信息学院1数据结构（第一章概述）DataStructures胡学钢张晶计算机与信息学院2009年2月合肥工业大学计算机与信息学院2第一章概述主要内容1.1研究内容1.2术语1.3算法及其描述1.4算法分析合肥工业大学计算机与信息学院31.1研究内容数据结构课程的研究内容：软件设计中常用的基本技术包括哪些基本技术？下面从采用计算机来解决实际问题的过程中所涉及到的各步骤中的相关技术来对此作一分析：在用计算机解决实际问题时，一般要经过以下几个步骤：首先，对具体问题抽象出数学模型，然后针对数学模型设计出求解算法，选择或设计合适的数据结构存储相关数据，最后编出程序上机调试，直至得到最终的解答。下面简述各环节的有关内容。合肥工业大学计算机与信息学院41.1研究内容问题求解之一：问题建模：一般情况下，实际应用问题可能会各式各样，例如：我们所熟悉的工资表的处理问题，学生成绩管理问题，电话号码查询，数据加密、压缩问题等。这些问题中，无论是所涉及到的数据，还是其操作要求，都可能存在一定的差异。尽管如此，许多问题间还是具有一定相似之处的。例如：虽然工资表和学生成绩表的具体信息（栏目）不同，但如果将两个表中的每个人的工资信息和成绩信息分别看作一个整体，则这两个表结构之间就有了某些共性。从操作方面来看，虽然对这两种表的操作存在差异，但也存在一些相同或相似的基本操作。例如，查询一个人的工资信息和成绩信息，修改有关信息等。合肥工业大学计算机与信息学院51.1研究内容正因为许多不同的问题之间存在着的某些共性，可以将一个具体问题用这些共性的形式描述出来-----问题建模。问题建模通常包括：所描述问题中的数据对象的集合；对象间关系及其描述；问题求解的要求及方法等。建立问题模型的好处：通过建立模型，就可以将一个具体的问题转换为所熟悉的模型，然后借助于这一模型来实现。数据结构、离散数学及许多数学课程中就介绍了许多模型。例如：要描述一个群体中个体之间的关系时，可以采用”数据结构”和”离散数学”中所介绍的图结构。要描述一个工程内的关系或进展情况时，我们可以采用”数据结构”中所介绍的AOV网或AOE网等。即使所建立的模型没有现成的求解方法，借助于已有的模型的适当组合也相对易于构造求解方法。合肥工业大学计算机与信息学院61.1研究内容问题求解之二：构造求解算法通过问题建模，将一个具体的问题转换成一个用模型所描述的抽象的问题。借助于这一模型以及已有的知识（例如数据结构中有关图结构的基本知识），可以相对容易地描述出原问题的求解方法，即算法。算法设计过程中可能会涉及到多种技术，例如：递归、分治法等。需要更多地实践。算法设计是计算机专业的核心能力，是区别于其他专业的最核心能力之一。从某种意义上说，该算法不仅能实现原问题的求解，而且还可能实现许多类似的具体问题的求解，尽管这些具体问题的背景及其描述形式可能存在较大的差异。合肥工业大学计算机与信息学院71.1研究内容问题求解之三：选择或设计存储结构在构造出求解算法之后，需要考虑在计算机上实现求解了。为此，需要做两方面的工作：选择或设计合适的存储结构，以便将问题所涉及到的数据存储到计算机中。（这包括数据中的基本对象及对象之间的关系）不同的存储形式对问题的求解实现有较大的影响，所占用的存储空间也可能有较大的差异。设计程序，实现问题求解。存储形式和问题要求决定了程序设计的方法。另外，程序设计环境（如VC）的熟练掌握也是本课程的学习过程中需要注意的教学目标之一。合肥工业大学计算机与信息学院81.1研究内容问题求解之四：测试如何认定所设计的算法及程序能正确实现预定的功能和目标？理论证明：这是计算机科学领域曾经开展过的工作。由于算法和程序的复杂性急剧增长，因而难以实用。测试：通过对所开发的系统或模块，运行给定的测试数据，以发现存在的错误，而不是证明其正确。这是当前软件开发领域普遍采用方法，通常要占系统开发４０％以上的工作量。详细描述可参考“软件工程”相关的描述。所设计的算法和程序，需要经过充分的测试才能交付使用。对程序的测试态度反映出学生的治学态度：如果是认真、负责的态度，就会认识到，任何设计都难免有疏漏，或者受环境的影响。因而需要高度重视。对程序的测试设计也反映出学生的治学能力：如何设计测试用例？需要依据多种方法、策略和实践。合肥工业大学计算机与信息学院91.1研究内容问题求解的过程框架：实际问题求解算法测试程序设计数据结构组织数据结构课程中的内容数学模型抽象构造求解算法数据结构设计程序实现数据结构：计算机类专业核心课程之一合肥工业大学计算机与信息学院101.2术语下面介绍课程中所涉及到的一些术语数据（data）——能够输入到计算机中，并能被计算机处理的符号的集合。例如，工资表，学生成绩，电话号码簿，电子字典，编号姓名基本工资奖金……工资表示例学号姓名考试成绩备注学生成绩表示例****工资表**班级**课程成绩表合肥工业大学计算机与信息学院111.2术语A1A2A3A5A4A6A8A7群体之间的认识关系图AA2A1A11A3A12A311A21A32A31A121家族关系示例一个家族关系的表示形式，表示一个群体中个体之间关系的图形描述等。合肥工业大学计算机与信息学院121.2术语虽然数据的形式及运算存在较大的差异，但存在共性：由若干具有独立意义的个体所组成，个体间存在着某些关系。对这些数据的运算也有某些相似之处。例如，在家族关系数据中，组成数据的基本个体是个人信息，其中各人之间存在着多种关系，如父子关系、兄弟关系、祖先－后代关系等。其中有些关系是直接表示出来的，还有一些关系则是隐含的。对家族关系数据，通常要涉及到查询特定个体间的关系、插入和删除个体等。合肥工业大学计算机与信息学院131.2术语由前述示例可见，数据可以分解为元素的集合----数据元素（dataelement）——构成数据的基本单位（具有完整的独立意义）。例如，工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。在有些场合下，也称之为元素、记录、结点、顶点等。数据项（字段）——元素的具体描述信息。学号姓名考试成绩备注表中一行对应一个元素表中一列对应一个字段合肥工业大学计算机与信息学院141.2术语数据结构（datastructure）——构成数据的元素之间的结构关系。数据元素之间存在以下几类内在的关系：线性结构：元素之间具有次序关系树形结构（树型结构）：元素之间的关系类似于现实中的树。图结构（网状结构）：元素间的关系较复杂。集合：元素之间没有关系。逻辑结构合肥工业大学计算机与信息学院151.2术语更一般地，数据结构包括以下几个方面：逻辑结构——元素之间的内在结构关系（逻辑关系）线性、树形（树型）、图（网状）、集合存储结构——数据结构在内存中的实现形式运算------对数据所施加的运算。有关数据结构几个方面的联系图逻辑结构分析运算实现（算法）运算定义存储结构抽象数据类型（ADT）数据结构的组成合肥工业大学计算机与信息学院161.3算法及其描述算法以及算法设计是计算机专业的核心能力。下面讨论算法的相关概念。算法——特定问题的求解方法。这种说法较为粗略，不够严格。另一种定义：指令的有限序列满足：(1)输入：0～n个(2)输出：1～n个(3)确定性（无二义性）：指令的描述是确定的，使得对相同的输入能产生相同的输出结果。(4)有限性：指令的执行次数有限。(5)可行性：算法中每条指令可用计算机指令的有限次执行来实现。合肥工业大学计算机与信息学院171.3算法及其描述算法描述语言易懂，灵活自然语言不准确准确，严格计算机语言死板伪语言（类语言）：类pascal、类C、类C++算法举例：1.求最大公因子（辗转相除法）2.韩信点兵问题3.幻方问题（纵横图）合肥工业大学计算机与信息学院181.3算法及其描述例1.求最大公因子（辗转相除法）求任意两个整数M,N最大公因子(M,N)的方法如下：若M=N*Q+R其中:R为余数,满足O≤R≤N-1则(M,N)=(N,R)且当R=0时，(M,N)=N按照这种方法，可以快速而方便地求出任意两个整数的最大公因子。例如，（1500，550）的求解过程如下：（1500，550）=（550，400）=（400，150）=（150，100）=（100，50）=（50，0）=50最终求得1500和550的最大公因子为５０。１５００％５５０＝＞４００合肥工业大学计算机与信息学院191.3算法及其描述由此，可得到求任意两个整数M和N最大公因子的算法的Ｃ语言函数如下：inthcf(intm,intn){while(n!=0){r=m%n;m=n;n=r;}returnm;}其对应的递归函数如下：inthcf(intm,intn){if(n==0)returnm;elsereturnhcf(n,m%n);}合肥工业大学计算机与信息学院201.3算法及其描述例2.“韩信点兵”问题的求解方法有一队士兵，确切人数不知，但若每３人一组，则余２人；每５人一组，余３人；每７人一组，余５人；每１１人一组，余４人。请解答下列问题：⑴至少有多少人？⑵若已知人数在5000～10000之间，问有多少个答案？解：初学者容易想到用逐个试探的方法来求解，这样显然很耗时间，特别是在所求解的值非常大时。求解方法是：逐个满足条件，在寻找满足下一个条件的解时保证前面条件继续成立。如何做到这一点？可以这样实现：探索满足下一个条件的ｎ的值时，以累加前面各数的最小公倍数来试探。由此得到求解的程序段。合肥工业大学计算机与信息学院211.3算法及其描述问题（１）的Ｃ语言程序段如下：｛n=2;//满足3人一组余2while（n%5！=3）n=n+3;//在保证3人一组余2的前提下寻找满足5人一组余3的n值while（n%7！=5）n=n+15;//在满足前两个条件的前提下寻找满足7人一组余5的n值while（n%11！=4）n=n+105;//在满足前三个条件的前提下寻找满足11人一组余4的n值｝其中每次所加上的是前面数的最小公倍数－－－3，15，105问题（１）的Ｃ语言程序段如下：｛while（n5000）n=n+1155;while（n=10000）｛Coutn;n=n+1155;｝//输出满足条件的各解｝合肥工业大学计算机与信息学院221.3算法及其描述3.幻方问题（纵横图）将1～n２放在n＊n（n为奇数）的方阵中，使得任意一行任意一列以及两条对角线上的所有元素之和均相等。如n=5时的方阵如下图所示。１５８１２４１７１６１４７５２３２２２０１３６４３２１１９１２１０９２２５１８１１合肥工业大学计算机与信息学院231.3算法及其描述这一问题如果采用试探的方法，在ｎ值较大时，将难以求出，因为可能的状态数是ｎ２！个。经典的构造方法如下：将数1放在第一行的中间元素，然后往左上的位置上放入下一个数。若左上的位置已有数，则将其放入该数的下一行中的同一列的位置上。若已是最左或最上面位置上的元素，则其下一个位置的寻找方法是：将方阵卷成一个纸筒，然后依此再按同样的方向再找下一个位置，直到n×n个元素全部放入为止。合肥工业大学计算机与信息学院241.3算法及其描述ｎ＝５时的求解过程如下：１２３４５６７８９１０１１１２１３１４１５１６１７１８１９２０２１２２２３２４２５合肥工业大学计算机与信息学院251.4算法分析由前面例题可知，不同的算法花费时间是有差异的，某些方法就难以实际应用。除了时间方面外，还有哪些需要考虑的性能？算法的衡量指标：在正确性的前提下，重点关注以下指标:（1）时间性能——运行算法所需的时间开销。（2）空间性能——运行算法所需的辅助空间的规模。（3）其它性能——如可读性/可移植性等。时间性能（时间复杂度）的描述方法讨论：(1)以运行算法d的机器时间开销来度量问题是：与具体机器相关，难以比较（2）以算法中语句的执行次数来衡量问题是：