大学计算机基础：第6章 算法与数据结构基础

计算机计算机程序程序主要对主要对数据数据进行进行加工加工和和处处理理。通常程序中要说明数据的。通常程序中要说明数据的组织形式组织形式和和存存储方式储方式，即，即数据结构数据结构；也要给出操作数据的；也要给出操作数据的步骤和方法，即步骤和方法，即算法算法。数据结构基本概念数据结构基本概念 算法基本概念算法基本概念典型数据结构典型数据结构典型算法典型算法 6 6 学学 时时 6.1 6.1 数据结构基本概念数据结构基本概念 6.1.1 6.1.1 数据结构示例数据结构示例 学号学号姓名姓名性别性别出生出生日期日期班级班级专业专业2004000120040001刘强刘强男男1984/02/131984/02/131400114001机械机械2004000220040002王晓红王晓红女女1986/05/061986/05/061400114001机械机械2004000320040003李明李明男男1984/10/251984/10/251400114001机械机械2004004120040041张宇张宇男男1984/06/141984/06/141400214002机械机械数据数据也称为也称为数据元素数据元素或或结点结点，现实，现实世界中一切客观事物都可以抽象成数据世界中一切客观事物都可以抽象成数据元素。元素。6.1.2 6.1.2 数据结构的定义数据结构的定义 数数据据结结构构是是指指具具有有相相同同特特征征、相相互互之间有之间有关联关联的的数据集合数据集合。9向量向量22，4343，6868，4545，3232是数据结构是数据结构每个数据每个数据元素元素由由一个数据项一个数据项组成，数组成，数据元素之间有位置上的据元素之间有位置上的前后前后关系关系 每个数据每个数据元素元素由由一个数据项一个数据项组成，组成，数据元素之间有位置上的数据元素之间有位置上的前后前后关系关系 9季度名称组成的集合是数据结构：季度名称组成的集合是数据结构：春，夏，秋，冬春，夏，秋，冬 9家庭成员家庭成员 祖父、父亲、儿子祖父、父亲、儿子 是数据结构是数据结构每个数据每个数据元素元素由由一个数据项一个数据项组成，数组成，数据元素之间有层次上的据元素之间有层次上的高低高低关系关系 9学生信息学生信息数据结构中，数据结构中，数据元素数据元素由由学号学号、姓名姓名、性别性别、出生日期出生日期、班级班级和和专业专业组成。组成。每个数据每个数据元素元素由由多个数据项多个数据项组成组成 数数据据结结构构是是指指带带有有结结构构特特性性的的数数据据元素集合元素集合，主要研究：，主要研究：1 1）数数据据集集合合中中数数据据元元素素之之间间所所固固有的关系有的关系，即数据，即数据逻辑结构逻辑结构；2 2）数数据据处处理理时时数数据据在在计计算算机机中中的的存储关系存储关系，即数据，即数据存储结构存储结构；3 3）对数据所进行的）对数据所进行的操作操作，即，即算法算法。6.1.3 6.1.3 数据逻辑结构数据逻辑结构 数数据据结结构构中中数数据据元元素素之之间间所所固固有有的的关系关系描述成描述成前后件前后件（前驱与后继前驱与后继）关系。）关系。数数据据之之间间前前后后件件关关系系是是它它们们之之间间的的逻逻辑辑关关系系，与与它它们们在在计计算算机机中中存存储储位位置置无无关关，因因此此将将这这种种关关系系称称为为数数据据逻逻辑辑结结构构。一个数据结构可以表示为：一个数据结构可以表示为：S=S=（D D，R R）S S:数据结构数据结构 D D:数据元素集合数据元素集合 R:R:D D中中数数据据元元素素之之间间前前后后件件关关系系集集合合，即数据即数据逻辑结构逻辑结构 两两个个元元素素之之间间前前后后件件关关系系用用一一个个二二元元组组表示，例：表示，例：(a a1 1,a2a2)季节数据结构可以定义成季节数据结构可以定义成 S=(D,R)S=(D,R)其中其中:D=:D=春春,秋秋,冬冬,夏夏 R=(R=(春春,夏夏),(),(夏夏,秋秋),(),(秋秋,冬冬)向量数据结构可以定义成向量数据结构可以定义成 S=(D,R)S=(D,R)其中其中:D=2,43,68,45,32 :D=2,43,68,45,32 R=(2,43),(43,68),(68,45),(45,32)R=(2,43),(43,68),(68,45),(45,32)线性结构：线性结构：数据之间有数据之间有集合集合,线性线性,树形树形和和图图形形 4 4 种基本逻辑结构。种基本逻辑结构。数据元素之间数据元素之间一对一一对一关系关系除第一个除第一个结点无前件外结点无前件外,其他结点其他结点都都 只有一个前件只有一个前件除最后一个除最后一个结点无后件外结点无后件外,其他结其他结点都点都只有一个后件只有一个后件例如例如:春春夏夏冬冬秋秋O数据之间数据之间一对多一对多关系关系O一一个个结结点点仅仅有有一一个个前前件件,可有可有多个后件多个后件O前、后件之间前、后件之间层次关系层次关系树型结构：9数据元素之间数据元素之间多对多多对多关系关系9一个结点可有一个结点可有多个前多个前件件和多个和多个后件后件图形结构：图形结构：集集合合：是是一一种种松松散散结结构构，数数据据元元素素之之间间的的关关系系是是属属于于一一个个集集合合，可可用用其其他他结结构构表示。表示。集合集合 非线性结构非线性结构:有有多个开始结点多个开始结点和和多个多个终端结点终端结点，每个结点可以有，每个结点可以有多个前件多个前件和和多个多个后件后件。线性结构线性结构:有且只有有且只有一个开始结点一个开始结点和和一个终端结点一个终端结点，并且每个结点最多只有，并且每个结点最多只有一个一个前件前件和和一个后件一个后件，线性结构也称为，线性结构也称为线性表线性表。数据逻辑结构数据逻辑结构分为分为线性结构线性结构和和非线性非线性结构结构。6.1.4 6.1.4 数据物理结构数据物理结构 数据数据在计算机存储器中的在计算机存储器中的存储方式存储方式称为称为数据数据存储结构存储结构（或数据物理结构）。（或数据物理结构）。数据结构数据结构中数据元素之间在计算机中的中数据元素之间在计算机中的位置关系位置关系与与逻辑关系逻辑关系不一定相同不一定相同。在数据在数据存储结构存储结构中，不仅要存放各个数中，不仅要存放各个数据元素据元素信息信息，还要存放数据元素之间，还要存放数据元素之间前后件前后件关系信息关系信息。数据存储数据存储结构是结构是逻辑结构逻辑结构在计算机存储在计算机存储器中的器中的表示表示。数据元素在计算机中通常有四种存储方数据元素在计算机中通常有四种存储方式，即式，即顺序顺序、链式链式、索引索引和和散列散列，常用，常用顺序顺序存储结构存储结构和和链式存储结构。链式存储结构。数据数据地址地址A1A2A3A42000H2001H2002H2003H 顺序存储结构顺序存储结构是在内存中开辟是在内存中开辟一块连续一块连续内存单元用于存放数据，内存单元用于存放数据，逻辑上相邻逻辑上相邻的结点的结点在物理位置上也在物理位置上也邻接邻接，结点之间的，结点之间的逻辑关系逻辑关系是由存储单元是由存储单元相邻关系相邻关系来体现。来体现。链式存储结构：结点由链式存储结构：结点由两部分两部分组成：组成：数据数据域域和和指针域指针域 数据域数据域用于存放数据元素用于存放数据元素值值 指针域指针域用于存放用于存放前件前件或或后件后件的的存储地址存储地址 链式存储结构是通过链式存储结构是通过指针指针反映数据元素之反映数据元素之间的间的逻辑关系逻辑关系。a13003Ha22506Ha32509Ha42000H2001H3003H3004H2506H2507H2509H2510H 6.2 6.2 算法基本概念算法基本概念 6.2.1 6.2.1 算法定义算法定义 算法算法是定义在是定义在逻辑结构逻辑结构上的操作，上的操作，独立于计算机独立于计算机，而算法必须在，而算法必须在计算机上计算机上执行执行，因此算法的实现，因此算法的实现依赖依赖于于数据存储数据存储结构结构。算法算法是解决问题的是解决问题的具体方法具体方法和和步骤步骤的描述的描述，是一组，是一组有限运算序列有限运算序列。算法的特征算法的特征Z可行性可行性Z确定性确定性Z有穷性有穷性Z输入输入Z输出输出采取的采取的方法方法和和步骤可行步骤可行，结构另人满意。结构另人满意。算法中每个步骤算法中每个步骤结果结果都必须都必须确确定定，不能产生歧义。，不能产生歧义。执行算法时从外界取得必要的执行算法时从外界取得必要的信息。一个算法可以信息。一个算法可以有零或多有零或多个输入个输入。算法得到的算法得到的结果结果就是输出就是输出,没有输没有输出的算法是没有意义的出的算法是没有意义的,一个算法一个算法应该应该有一个或多个输出有一个或多个输出。算法必须由算法必须由有限有限步步组成，并能在组成，并能在有效时间有效时间内内完成完成。用于描述算法的工具很多，通常有用于描述算法的工具很多，通常有流流程图程图、N-SN-S图图、自然语言自然语言和和伪代码伪代码等工具。等工具。自然语言自然语言：带序号的人类语言描述方法。带序号的人类语言描述方法。1.1.将变量将变量s s清清0 0；2.2.将变量将变量n n置置1 1；3.3.把把s+ns+n的值赋给的值赋给s s；4.4.把把n+1n+1的值赋给的值赋给n n；5.5.判断判断 n n 100 100？是否成立？是否成立，若成立，转，若成立，转3 3；否则转否则转6 66.6.输出输出s s的值的值;S=1+2+3+S=1+2+3+99+100+99+100特点特点:易懂却不直观易懂却不直观,对复杂算法描述很对复杂算法描述很困难困难,易产生歧义。易产生歧义。若成立若成立,伪伪代代码码法法：是是一一种种假假的的代代码码不不能能被被计计算算机执行，可由机执行，可由计算机语言计算机语言和和自然语言自然语言构成。构成。0S1nwhilen 100S+nSn+1nprintS 接近接近某种语言编写的某种语言编写的程序程序,便于转换便于转换成程成程序。序。流程图法：流程图法：用一些用一些图框图框、线条线条以及以及文字文字说明说明 来形象地、直观地描述算法。来形象地、直观地描述算法。输入输入/输出输出处理处理判断判断起止起止连接点连接点流程线流程线符号说明符号说明：开始开始0 S1 nSn Sn1 n输出输出S结束结束T F n 100S=1+2+3+S=1+2+3+99+100+99+100优点优点:直观形象直观形象缺缺点点:算算法法复复杂杂时时,篇篇幅幅 较较多多,费费时时且且不不方方便便修改。修改。N-SN-S图图:去去掉掉箭箭头头流流程程线线、算算法法处处理理步步骤骤写写在在大大矩矩形形框框内内,框框内内还还可可包包含含一一些些小小矩矩形框形框,适于结构化程序设计。适于结构化程序设计。顺序顺序A AB B判断判断条件条件F FT TB BA A当型循环当型循环当条件成立当条件成立A A直到型循环直到型循环直到条件成立直到条件成立A A0 S0 S1 n1 nn n 100 100S Sn Sn Sn n1 n1 n输出输出S S的值的值算法评价算法评价 某某一一任任务务的的算算法法设设计计得得优优与与劣劣,将将直直接接影影响响程程序序的的运行效率运行效率、稳定性稳定性和和可维护性可维护性。从。从4 4个方面评价算法：个方面评价算法：U正确性正确性U可读性可读性U健壮性健壮性U执行效率执行效率算法本身没有算法本身没有语法错误语法错误,执行时执行时输入输入正确数据能够得到正确正确数据能够得到正确结果结果.算法要算法要容易理解容易理解和和阅读阅读,容易容易实现实现，便于程序维护和完善。便于程序维护和完善。算法执行的算法执行的时间时间性能和性能和空间性能空间性能 。算法能够对各种输入数据给予适当算法能够对各种输入数据给予适当处理和提示。处理和提示。解解决决同同一一问问题题的的多多个个算算法法，执执行行时时