第4章 数据结构与简单的算法设计

本章学习目标了解数据结构与算法的基本概念；了解几种基本数据结构；掌握算法的结构以及描述方法；熟练掌握算法的流程图表示，能熟练的绘制算法流程图。4.1算法概念算法：解决一个问题而采取的方法和步骤。算法与数据结构关系紧密，在算法设计时先要确定相应的数据结构，而在讨论某一种数据结构时也必然会涉及相应的算法。著名的计算机科学家尼古拉斯·沃斯曾提出：程序设计=数据结构+算法。算法的性质

一个成熟的算法应该具有以下六个特性：算法名称：就是给算法命名，每个算法都应该有一个名字，在C语言中，算法名通常就是函数名。输入：算法可能会有若干个输入。输出：算法至少有一个或多个输出，表示算法运算的结果。有效性：算法的每一步都有确定的含义，计算可以进行操作和运算的。正确性：是指算法的结果必须正确，能够解决相应问题的。有限性：一个算法必须在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。算法的结构C语言是一种结构化的程序语言。任何复杂的算法都可以由顺序结构、分支结构和循环结构这三种基本结构组成。1、顺序结构，是简单的线性结构，程序在执行过程中是按语句的先后顺序来执行的。2、分支结构，程序在执行过程中，会根据条件的不同有选择的执行不同的功能。3、循环结构，程序在执行过程中，在一定的时间段内或一定的条件下，重复地执行某个功能，直到时间已到或条件不再满足。数据结构概念

数据是计算机处理符号的总称。数据可以是数值型，也可以是非数值型。数值数据主要有整数和浮点数等。数据元素之间的关系称为“结构”。有4种基本结构:集合关系(无序的松散关系)；线性关系(一一对应关系)；树树关系(一对多关系)；图关系(多对多关系)。数据结构是研究数的逻辑结构和物理存储结构以及它们之间的相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得得到的新结构仍然是原来的结构类型。数据结构类型

根据数据元素间关系的不同特性，数据的逻辑结构有4种基本类型:集合结构中，数据元素之间的关系是“属于同一个集合”。由于集合是数据元素之间关系极为松散的一种结构，因此也可用其他数据结构来表示。4.2几种基本数据结构

线性表是最简单、最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。在实际应用中，线性表的形式有字符串、一维数组、栈、队列、链表等数据结构。4.2几种基本数据结构

栈最大的特点是先进后出。是一种特殊的线性表，栈的插人和删除运算限定在的某一端进行。允许插人和删除的一端称为栈顶，另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。在如图所示的栈中，元素以a1，a2，……，an的顺序进栈，因此栈底元素是a1，栈顶元素是an。不含任何数据元素的栈称为空栈。4.2几种基本的数据结构

队列是先进先出，队列也是一种运算受限的线性表，在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。新插入的元素只能添加到队尾，被删除的元素只能是排在队头的元素。4.2几种基本的数据结构

树形结构广泛存在于客观世界中，如人类的族谱，各种社会组织机构，各种事物的分类等，都可以用树表示。树在计算机领域得到了广泛应用，如：操作系统中的目录结构。简单地说，一切具有层次关系或包含关系的问题都可用树来描述。4.2几种基本的数据结构图中的数据元素称为顶点(Vertex)，顶点之间的逻辑关系用边来表示。V是图G中顶点的集合，E是图G中边的集合。图中的边按有无方向分为无向图和有向图，无向图由顶点和边组成，有向图由顶点和弧构成，如图所示。如果图中的边没有权值关系时，一般定义边长为1，如果图中的边有权值，则构成的图称为网图。4.3算法的描述常用的算法的描述方法有：自然语言、流程图、伪代码、PAD图等。自然语言描述：用日常交流语言直接将算法步骤表述出来。优点：简单，便于人们对算法的阅读；缺点：文字冗长，容易出现歧义；描述分支和循环结构不直观。4.3算法的描述【例4-1】计算并输出z=x/y的值。自然语言算法描述：S1：输入变量x，y;S2：判断y是否为0；S3：如果y=0；则输出错误提示信息；S4：否则计算z=x/y；S5：输出z；S6：算法结束。4.3算法的描述【例4-3】求和sum=1+2+3+4+5+……+n，输出sum的值。算法描述：s1：给定一个大于0的正整数n的值；s2：定义一个整型变量i，设其初始值1；s3：定义整型变量sum，其初始值设置为0；s4：如果i小于等于n，则转到s5，否则转到s8；s5：将sum的值加上i的值后，重新赋值给sum；s6：将i的值加1，重新赋值给i；s7：转到第4步；s8：输出sum的值；s9：算法结束。4.3算法的描述流程图是由流程线和几何图形框连接而成的。开始结束框：代表算法的开始和结束，每个算法都必须有且仅有一个开始和一个结束。数据框：代表算法中数据的输入或输出。处理框：表示算法对数据的处理，通常为程序的表达式语句。判断框：代表算法中的分支情况，判断条件只有满足和不满足两种情况。流向线：用来连接各个流程图框，表示算法的流程走向。连接点：当同一个算法流程图在不同页时，在分割点画连接点，来连接流程图。4.3算法的描述顺序结构是一种简单的线性结构，由处理框和流向线组成，根据流程线所示的方向，按顺序执行各矩形框的指令。指令A、指令B、指令C可以是一条指令语句，也可以是多条指令。执行顺序为从上到下顺序执行:A-B-C。4.3算法的描述分支结构由判断框、处理框和流向线组成，先要对给定的条件进行判断，根据条件结果的真假而分别执行不同的处理框，其流程图的基本形状有两种：注：虚线框表示可将分支结构看成一个矩形框。指令A、指令B可以是一条或多条指令，也可以是分支结构。4.3算法的描述循环结构同选择分支结构一样，循环结构也是由判断框、处理框和流向线组成的。但循环结构是在某个条件为真的情况下，重复执行某个框中的内容。循环结构有两种基本形态while型循环和dowhile型循环。while型循环的流程图如图所示。执行顺序为:先判断条件，如果条件为真，则执行A；然后再进入条件判断，构成一个循环，一但条件为假，则跳出循环，进入下一个结构。问：分支结构和循环结构流程图有什么区别？dowhile型循环的流程图如图所示，执行顺序为:先执行A，再判断条件，若条件为真，则重复执行A，一旦条件为假，则跳出循环，进入下一个结构。4.3算法的描述注：(1)虚线框表示可将循环结构看成一个矩形框。(2)指令A称为循环体，可以是一条或多条指令，也可以是其他分支或循环结构。(3)do_while结构可以转化成while结构。4.3算法的描述循环结构注意事项：①在循环体中的指令有可能不只一条，也可能是其他分支或循环结构；②指令中必须有修改循环变量值的语句，使得经过有限次循环后，循环一定能结東。③while循环中循环体语句可能一次都不执行，而dowhile循环体语句则至少执行一次。④dowhile循环可以转化成为while循环，但while型循环不一定能转化为dowhile型循环。将dowhile循环转化成while循环，如图所示。4.3算法的描述【例4-4】计算并输出z=x/y的值。流程图表示：4.3算法的描述【例4-6】求和sum=1+2+3+4+5+……+n，输出sum的值。流程图表示：4.4算法设计范例【例4-7】输入三个整数a，b，c，找出其中最小值并输出。自然语言描述：S1：输入三个整数a,b,c；S2：比较a和b的值，将a,b中较小的值赋值给min；S3：比较min和c的值，如果c<min，则将c的值赋给min；S4:输出min；S5:算法结束。流程图表示：4.4算法设计范例【例4-8】输入一个正整数n，求出1+1/2+1/3+……+1/n的值。自然语言描述：S1：给定一个大于0的正整数n的值；S2：定义一个整型变量i，设其初始值1；S3：定义整型变量sum，其初始值设置为0；S4：如果i小于等于n，则转到第5步，否则转到第8步；S5：将sum的值加上1/i的值后，重新赋值给sum；S6：将i的值加1，重新赋值给i；S7：转到第4步；S8：输出