单元4 程序设计与数据结构基础

1单元

4程序设计与数据结构基础程序设计是设计和构建可执行的程序，以完成特定数值计算和数据处理的过程，是软件开发过程的重要组成部分。熟悉和掌握程序设计的基础知识，是在现代信息社会中生存和发展应具备的基本技能之一。计算机系统软件和应用软件都要用到各种类型的数据结构。数据结构与数学、计算机硬件和软件有十分密切的关系，数据结构技术也被广泛应用于信息科学、系统工程、应用数学、工程技术等领域。计算长方形面积的流程图如图4-1所示22算法初步4.1程序设计基础4.24.34.44.5目录Python语言程序设计数据和数据结构概述典型的数据结构3图4-1计算长方形面积的流程图4计算长方形面积一般步骤的文字描述如下。第1步：输入长方形的长度和宽度。即设置num1和num2两个变量，接收用户输入的长度和宽度，并存储到num1和num2两个变量中。第2步：判断输入长方形的长度和宽度是否大于0，如果长度和宽度大于0，执行第3步，否则执行第5步。即判断num1和num2是否大于0，如果大于0，执行第3步，否则执行第5步。第3步：计算长度和宽度的乘积。即计算num1和num2的乘积，并将乘积结果存储到result变量。第4步：输出长方形的面积。即显示result变量的值到屏幕并退出。第5步：显示输入错误。即提示用户输入的长度和宽度有误。根据计算长方形面积一般步骤的文字描述和图4-1所示的流程图，猜测一下图4-2所示图例的作用是什么？图4-2流程图的图例5某洗衣机不启动的故障排除步骤的文字描述如下。第1步：检查电源是否接通，如果电源有问题，则解决电源问题后，故障排除。如果电源没有问题，则进入第2步。第2步：检查洗衣机门是否关严，如果洗衣机门没有关严，则关严洗衣机门，故障排除。如果洗衣机门已关严，则进入第3步。第3步：检查洗衣机进水部分，查看水龙头是否打开，如果水龙头没有打开，则打开水龙头，故障排除。如果水龙头已打开且有水压，则进入第4步。第4步：检查是否按下了启动键并有蜂鸣声，如果没有按下启动键，则按下启动键，故障排除。如果已按下启动键且有蜂鸣声，则需要给售后服务打电话报修。使用图4-2所示的图例尝试绘制洗衣机不启动故障排除流程图，明确排除使用不当而造成洗衣机不启动故障的排查方法和流程。4.

1算法初步在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。使用计算机解决具体问题一般需要经过以下几个步骤：首先从具体问题抽象出适当的数学模型，然后设计或选择求解此数学模型的算法，接着编写程序并进行调试、测试，直至得到最终的解答。计算机解决问题的一般过程是：分析问题、设计算法、编写程序、调试运行、检测结果。64.1.1算法的概念做任何事情都有一定的步骤和方法，广义地讲，为解决某个问题而设计的确定的方法和有限的步骤，称为算法。算法是一个基本的概念，但也是一门深奥的学问，小到如何输出九九乘法表，如何对一组数据进行排序，大到如何控制飞行器的姿态，如何让无人机避障等。我们先分析如何求1×2×3×4×5的值。原始的算法如下。步骤1：先求1乘以2，得到结果2。步骤2：将2乘以3，得到结果6。步骤3：将6乘以4，得到结果24。步骤4：将24乘以5，得到结果120。这样的算法虽然正确，但有些烦琐。改进的算法如下。S1：使t=1。S2：使i=2。S3：求t×i，乘积仍然放在变量t中，可表示为t×i→t。S4：求i+1的值，即i+1→i。S5：如果i≤5，返回重新执行S3以及其后的S4和S5；否则，算法结束。如果要计算100！只需将S5的“i≤5”改成“i≤100”即可。如果改成求1×3×5×7×9×11，算法也只需做很少的改动，如下所示。S1：1→t。S2：3→i。S3：t×i→t。S4：i+2→i。S5：若i≤11，返回S3以及其后的S4和S5；否则，算法结束。该算法不仅正确，而且是便于计算机处理的算法，因为计算机是高速运算的自动机器，实现循环轻而易举。7算法设计具有以下特点。①解决同一个问题可以有不同的解题方法和步骤。②算法有优劣之分，有的算法只需要很少的步骤。同一个问题，计算机根据一种好的算法编写的程序只需运行很短的时间（几秒或几分钟）就能得到正确的解，而根据一种差的算法编写的程序可能需要运行很长的时间（几小时或几天）才能得到最终的解。可见优秀的算法可以带来高效率。③设计算法时，不仅要保证算法正确，还要考虑算法的质量。最优的算法应该实现计算次数最少，所需存储空间最小，但两者很难兼得。④不是所有的算法都能在计算机上实现。有些算法设计思路很巧妙，但计算机可能无法实现，不具有可行性。计算机算法分为数值运算算法和非数值运算算法。（1）数值运算算法数值运算的目的是求数值解，如求方程的根、求一个函数的定积分等。数值运算算法有现成的模型，各种数值运算都有比较成熟的算法可供选用。（2）非数值运算算法非数值运算算法主要用于处理非数值型的数据和问题，其应用范围广泛，种类繁多，要求各异，难以规范化。目前，计算机在非数值运算方面的应用远远超过了在数值运算方面的应用。84.1.2算法的特性算法（Algorithm）是对特定问题求解步骤的一种描述，是求解步骤（指令）的有限序列。其中每一条指令表示一个或多个操作。不同的问题需要用不同的算法来解决，同一问题也可能有不同的算法，一个算法应该具有下列特性。（1）有穷性（Finiteness）一个算法必须在执行有穷步骤之后正常结束，即必须在有限时间内完成。（2）确定性（Definiteness）算法中的每一个步骤都应该是确定的，而不是含糊或模棱两可的，对于相同的输入必须得出相同的执行结果。（3）可行性（Effectiveness）算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步骤，即算法中的每个计算步骤都应当能有效地被执行，并得到确定的结果，也称之为有效性。例如：若b=0，则a/b是不能被有效执行的。（4）输入（Input）一个算法具有零个或多个输入。所谓的输入，是指在执行算法时需要从外界取得的必要信息，这些输入取自特定的数据对象集合。一个算法也可以没有输入。94.1.3比较算法和程序（5）输出（Output）一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。算法的目的是求“解”，“解”就是输出。输出反映对输入数据加工后的结果，没有输出的算法是毫无意义的。101．算法和程序的区别算法与程序十分相似，但又有区别。一个程序不一定满足有穷性。如操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另外，程序中的指令必须是计算机可执行的，而算法中的指令无此限制。算法代表了对问题的求解，而程序是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，那它就是一个程序。（1）两者的定义不同算法是对特定问题求解步骤的描述，它是有限序列指令。（2）两者的书写规定不同程序必须用规定的程序设计语言来写，而算法描述方法多样。2．算法与程序的联系算法是程序的核心，程序是算法在计算机上的具体实现。4.1.4算法的描述方法算法设计者必须将自己设计的算法清楚、正确地按步骤记录下来，这个过程就叫描述算法。算法可以使用各种不同的方法来描述，常见的有自然语言、流程图、N-S图、伪代码、计算机语言等。最简单的方法是使用自然语言进行描述，也可以用以上的其他方法描述，还可以直接使用某种程序设计语言来描述算法，不过直接使用程序设计语言并不容易，而且不太直观。1．用自然语言描述算法例如，任意输入3个数，求这3个数中的最大数，用自然语言描述的算法如下。S1：定义4个变量，分别为x、y、z以及max。S2：输入大小不同的3个数，分别赋给x、y、z。S3：判断x是否大于y，如果大于，则将x的值赋给max，否则将y的值赋给max。S4：判断max是否大于z，如果大于，则执行S5，否则将z的值赋给max。S5：将max的值输出。112．用流程图描述算法流程图是一种传统的算法表示法，它用一些图框来代表各种不同性质的操作，用流程线来指示算法的执行方向，直观地描述算法的处理步骤。由于流程图具有直观、形象、容易理解的特点，所以应用广泛。但流程图表示控制的箭头过于灵活，且只描述执行过程而不能描述有关数据。常用的流程图的基本图例如图4-3所示。12图4-3常用的流程图的基本图例其中，起止框是用来标识算法开始和结束的；输入/输出框表示数据的输入和输出操作；判断框的作用是对一个给定的条件进行判断，并根据给定的条件是否成立来决定如何执行后面的操作；处理框表示完成某种操作，如初始化或运算等；流程线用箭头表示程序执行的流向。例如，有40个学生，要求输出不及格的学生的学号和成绩。ni代表第i个学生的学号，gi代表第i个学生的成绩，用流程图描述算法，如图4-4所示。13图4-4输出不及格的学生的姓名和成绩的流程图3．用N-S图描述算法例如，计算10！，用N-S图描述算法，如图4-5所示。14图4-5计算10！的N-S图4．用伪代码描述算法例如，计算10！，用伪代码描述算法。用伪代码表示的算法如下。15begin10→n1→sum1→numberwhilenumber<=nsum×number→sumnumber+1→numberendwhileprintsumend5．用计算机语言描述算法计算机无法识别流程图和伪代码，只有用计算机语言编写的程序才能被计算机执行。在用流程图或伪代码描述出一个算法后，要将其转换成计算机语言程序。用计算机语言描述算法必须严格遵循所用语言的语法规则。例如，计算10！，用Python语言描述算法。Python程序如下。16n=10sum=1number=1whilenumber<=n:sum=sum*numbernumber+=1print("1到{}阶乘为:{}".format(n,sum))4.1.5算法优劣的评价标准使用计算机解决问题的关键是算法的设计，对于同一个问题，可以设计出不同的算法，如何评价算法优劣是算法分析、比较、选择的基础。可以从以下几个方面对算法优劣进行评价。1．正确性算法能正确地实现预定的功能，满足具体问题的需求。正确性的具体要求如下。•不含语法错误。•对输入数据能够得出满足要求的结果。•对一切合法输入，都可以得到符合要求的解。172．可读性一个算法应当思路清晰、层次分明，易于阅读、理解和交流，便于调试、修改和扩充。写出的算法，能让人看明白，能让人明白算法的逻辑。如果算法通俗易懂，则在系统调试和修改或者功能扩充的时候更为便捷。3．健壮性算法应具有容错能力。输入非法数据，算法能适当地做出反应并进行处理，不会产生预料不到的运行结果。数据的形式多种多样，算法可能面临着接收各种各样的数据，当算法接收到不适合算法处理的数据时，算法本身该如何处理呢？如果算法能够处理异常数据，则处理能力越强，健壮性越好。4．稳定性稳定性主要指算法在噪声、干扰等不利因素下仍能保持稳定的性能输出。185．时空性算法的时空性是指该算法的时间复杂度和空间复杂度，主要是说算法在执行过程中的时间长短和空间占用问题。算法处理数据过程中，不同的算法耗费的时间和内存空间是不同的。（1）时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n的函数f(n)，算法的重复执行次数用T(n)表示，时间复杂度记作O(f(n))。问题的规模n趋近于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数，即T(n)=O(f(n))称作渐进时间复杂度（AsymptoticTimeComplexity）。（2）空间复杂度算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度的类似，一般都用复杂度的渐进性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。空间复杂度记作S(n)=O(f(n))。例如，直接插入排序的时间复杂度是O(n2)，空间复杂度是O(1)。而一般的递归算法就有O(n)的空间复杂度了，因为每次递归都要存储返回信息。194.1.6经典算法简介虽然设计算法，尤其是设计好的算法是一项困难的工作，但是设计算法也不是没有规律可循。人们经过几十年的探讨，总结和积累了许多行之有效的方法，了解和掌握这些方法会给我们解决问题提供一些思路。经常采用的算法设计方法有迭代法、穷举搜索法、递推法、递归法、回溯法、贪婪法等，了解和借鉴这些算法设计的方法，有助于解决类似程序的设计问题。这里简单介绍迭代法、穷举搜索法、递推法、递归法、回溯法、贪婪法这6种算法。1．迭代法迭代法是用来解决数值计算问题中的非线性方程（组）求解或求最优解的一种算法，以求方程（组）的近似根。迭代法的基本思想是：从某个点出发，通过某种方式求出下一个点，此点应该离要求解的点（方程的解）更进一步，当两者之差接近到可以接受的精度范围时，就认为找到了问题的解。简单迭代法每次只能求出方程的一个解，需要人工先给出近似初值。202．穷举搜索法穷举搜索法又称为枚举法，按某种顺序对所有的可能解逐个进行验证，从中找出符合条件要求的作为问题的解。此算法通常用多重循环实现，对每个变量的每个值都测试是否满足所给定的条件，以找到问题的一个解。这种算法简单、易行，但只能用于变量个数有限的场合。3．递推法递推法是利用问题本身具有的递推性质或递推公式求得问题的解的一种算法，从初始条件出发，逐步推出所需的结果。但是有些问题很难归纳出一组简单的递推公式。4．递归法递归法的思想是：将N=n时不能得出解的问题，设法递归转化为求n－1,n－2,…的问题，一直到N=0或1，由于初始情况的解比较容易给出或方便得到，因此可逐层得到N=2,3,…,n时的解，得到最终结果。用递归法写出的程序简单、易读，但效率不如递推法的高。任何可以用递推法解决的问题，都可以很方便地用递归法解决，但是许多能用递归法解决的问题，却不能用递推法解决。215．回溯法回溯法又称为试探法，在用某种方法找出解的过程中，若中间项结果满足所解问题的条件，则一直沿这个方向搜索下去，直到无路可走或无结果，则开始回溯，改变其前一项的方向或继续搜索。若其前一项的方向或值都已经测试过，还是无路可走或无结果，则继续回溯到其前一项，改变其方向或值继续搜索。若找到了一个符合条件的解，则停止或输出这个结果后继续搜索；否则继续回溯下去，直到回溯到问题的开始处（不能再回溯），仍没有找到符合条件的解，则表示此问题无解或已经找到了全部的解。用回溯法可以求得问题的一个解或全部解。6．贪婪法贪婪法又称为登山法，指从问题的初始解出发，一步步接近给定的目标，并尽可能快地去逼近更好的解。贪婪法是一种不追求最优解，只希望最快得到较为满意解的方法。贪婪法不需要回溯，只能求出问题的某个解，不能求出所有的解。22平时购物找零时，为使找回的货币数量最少，不考虑找零钱的所有方案，而是从最大面额的货币开始，按递减的顺序考虑各货币，先尽量用大面额的货币，当不足大面额货币的金额时才去考虑下一种较小面额的货币，这就使用了贪婪法。例如，50元找成20元、20元、10元。234.

2程序设计基础程序设计是指编写程序的过程。程序设计是一门技术，需要相应的理论、技术、方法和工具支持。程序设计不仅要保证设计的程序能正确地解决问题，还要求程序具有可读性、可维护性。244.2.1程序设计概述程序的概念非常普遍，一般来说，人们在完成一项复杂的任务时，需要进行一系列的具体工作，这些按一定的顺序安排的工作就是完成该任务的程序。但在计算机领域，“程序”一词特指计算机程序，即计算机为完成某任务所执行的一系列有序的指令集合。程序设计是为解决特定问题而使用某种程序设计语言编写程序的过程，程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。专业的程序设计人员常被称为程序员。4.2.2应用软件程序设计离不开程序设计语言，程序设计语言是人类用来和计算机沟通的工具。最早的程序设计语言是机器语言，用0和1两种符号组成的二进制数表示，计算机只能直接执行机器语言编写的程序，但直接用机器语言编写程序非常困难，效率也非常低。为了解决这个问题，诞生了各种各样的程序设计语言，这些程序设计语言更加接近人类的语言和思维。4.2.3程序设计语言的基本类型人和计算机交流信息使用的语言称为计算机语言或程序设计语言，计算机语言通常分为机器语言、汇编语言和高级语言3类。从程序设计语言的发展历程来看，程序设计语言可以分为以下5代。1．第一代程序设计语言：机器语言机器语言（MachineLanguage）是一种用“0”和“1”两个二进制符号表示的，能被计算机直接识别和执行的语言，是早期的程序设计语言。它是一种低级语言，用机器语言编写的程序不便于记忆、阅读和书写，通常不用机器语言直接编写程序。用机器语言编写的程序，称为计算机机器语言程序。任何程序或语言在执行前都必须转换为机器语言。机器语言是面向计算机的语言，其中的每一条语句就是一段二进制指令代码。用机器语言编程不仅工作量大，而且难学、难记、难修改，因此它只适合专业人员使用。而且不同品牌和型号的计算机的指令系统有差异，因此机器语言所编写的程序只能在相同的硬件环境下使用，可移植性差。但机器语言也有编写的程序代码不需要翻译、占用空间少、执行速度快等优点。252．第二代程序设计语言：汇编语言汇编语言（AssemblyLanguage）是一种用助记符表示的面向计算机的程序设计语言。汇编语言的每条指令对应一条机器语言代码，不同类型的计算机系统一般有不同的汇编语言。用汇编语言编制的程序称为汇编语言程序，计算机不能直接识别和执行，必须由“汇编程序”（或汇编系统）翻译成机器语言程序才能运行。这种“汇编程序”就是汇编语言的翻译程序。汇编语言适用于编写直接控制计算机操作的底层程序，它与计算机密切相关，不容易使用。汇编语言在一定程度上克服了机器语言难学、难记、难修改的缺点，同时保持了编程质量高、占用空间少、执行速度快的优点。但与机器语言一样，汇编语言也是面向计算机的语言，使用汇编语言编写的程序的通用性和可读性都较差。3．第三代程序设计语言：高级语言高级语言（HighLevelLanguage）是一种比较接近自然语言和数学表达式的计算机程序设计语言，并且高级语言完全与计算机的硬件无关，程序员在编写程序时，无须了解计算机的指令系统。因此，程序员在编写程序时就不用考虑计算机硬件的差异，因而编程效率大大提高。由于高级语言与具体的计算机硬件无关，因此使用高级语言编写的程序通用性强、可移植性高，易学、易读、易修改，被广泛应用于商业、科学、教育、娱乐等众多领域。26一般用高级语言编写的程序称为“源程序”，计算机不能识别和执行，要把用高级语言编写的源程序翻译成机器指令，通常有编译和解释两种方式。编译是指将源程序整个编译成目标程序，然后通过链接程序将目标程序链接成可执行程序。解释是指将源程序逐句翻译，翻译一句执行一句，边翻译边执行，不产生目标程序，这个过程由计算机的执行解释程序自动完成，如JavaScript、Python、Basic语言采用的就是这种方式。常用的高级语言有Python、Java、C#、C++、C、Fortran等。4．第四代程序设计语言：非过程语言非过程语言（NonproceduralLanguage）的特点是程序员不必关心问题的解法和处理问题的具体过程，只需说明所要完成的目标和条件，就能得到想要的结果，而其他的工作都由系统来完成。数据库的结构查询语言（StructureQueryLanguage，SQL）就是非过程语言颇具代表性的例子。例如，“Selectname,sex,ageFromstudentWhereclass=1”这一语句就可以直接从student数据表中查询出class为1的学生的name、sex和age信息。而读取数据、比较数据、显示数据等一系列具体操作都由系统自动完成。相比于高级语言，非过程语言使用起来更加方便，但是非过程语言目前只适用于部分领域，其通用性和灵活性不如高级语言。275．第五代程序设计语言：人工智能语言人工智能语言目前刚刚起步，也是未来程序设计语言的发展方向。人工智能语言是一类适用于人工智能和知识工程领域的、具有符号处理和逻辑推理能力的程序设计语言。人工智能语言可以用于解决非数值计算、知识处理、推理、规划、决策等各种复杂问题。284.2.4常见的高级程序设计语言自20世纪60年代以来，世界上公布的程序设计语言已有上千种之多，但是只有很小一部分得到了广泛的应用。目前主流的程序设计语言主要包括以下几种。1．PythonPython是一种跨平台、交互式、面向对象、解释型的计算机程序设计语言，它具有语法简洁、清晰的特点，具有丰富和强大的库，能够把用其他语言开发的各种模块很轻松地联结在一起，因此常被称为“胶水语言”。Python主要应用于Web和互联网开发、科学计算和统计、人工智能、大数据处理、网络爬虫、游戏开发、图形处理、界面开发等领域。Python支持广泛的应用程序开发，从简单的文字处理到Web开发再到游戏开发，并且简单、易学。2．JavaJava是一种面向对象的程序设计语言，它不仅吸收了C++的各种优点，还摒弃了C++中难以理解的多继承、指针等概念。因此，Java具有功能强大和简单易用两个优势，并且具有封装、继承、多态等面向对象语言的基本特征，以及稳定、安全、可移植性强、与平台无关、支持网络编程、支持多线程等许多优良特性，是目前使用十分广泛的编程语言。Java可以用于编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等。3．JavaScriptJavaScript是一种直译式脚本编程语言，可以与超文本标记语言（HypertextMarkupLanguage，HTML）一起实现网页中的动态交互功能，弥补HTML的不足，使网页变得更加生动。JavaScript是一种基于对象和事件驱动的脚本语言，是一种轻量级的编程语言，现代浏览器都可以通过嵌入或调用JavaScript代码在标准的HTML中实现其功能。JavaScript的基本语法与C语言的类似，但在运行过程中不需要单独编译，而是逐行解释执行，运行快。JavaScript具有跨平台性，与操作环境无关，只依赖于浏览器本身，只要是支持JavaScript的浏览器就能正确执行。294．C语言C语言是一种优秀的面向过程的结构化程序设计语言，被广泛应用于底层开发。它具有结构严谨、数据类型完整、语句简练灵活、运算符丰富等特点。同时，C语言面向硬件的底层编程能力很强，在硬件驱动程序开发和嵌入式应用程序设计等方面应用较多。C语言主要用于开发系统软件、应用软件、设备驱动程序、嵌入式软件等。5．C#C#是微软公司发布的一种面向对象的、运行于.NETFramework环境的高级程序设计语言。C#是一种强大而灵活的编程语言，借鉴了Java、C语言和C++的一些特点。它可以用来开发Windows应用、企业级业务应用、开发软件等。6．C++C++是C语言的继承，它既可以进行C语言的过程化程序设计，又可以进行以抽象数据类型为特点的基于对象的程序设计，还可以进行以继承和多态为特点的面向对象的程序设计。C++是一种面向对象的计算机程序设计语言，支持静态数据类型检查和多重编程范式。它还支持泛型程序设计等多种程序设计风格。304.2.5程序设计的基本过程计算机解决问题的过程也是程序设计的过程。程序设计是运用计算机解决问题的一种方式，数值、逻辑等问题适合通过程序设计的方式解决，通过对实际问题的分析，设计算法，把所要解决的问题转化成程序输入计算机，经调试后让计算机执行这个程序，最终达到利用计算机解决问题的目的。程序设计往往以某种程序设计语言为工具，给出用这种语言编写的程序。1．分析问题分析问题也就是分析编写该程序的目的、要解决的实际问题，并将实际问题抽象为计算机可以处理的模型。对于接受的程序设计任务要进行认真的分析，研究所给定的条件，分析最后应达到的目标，找出解决问题的规律，选择解题的方法，完成实际问题求解。分析问题主要需要明确以下5点。①要解决的问题是什么？②问题的输入是什么，已知什么，还要添加什么，使用什么格式？③期望的输出是什么，需要什么类型的报告、图表或信息？④数据具体的处理过程和要求是什么？⑤要建立什么样的计算模型？312．建立模型建立模型是指从现实项目的真实情境中提炼出核心的要素并加以确定或假设，最终定义出一个有明确已知条件和求解目标的问题，并用数学符号描述解决该问题的计算模型。3．设计算法设计算法即设计出解题的方法和具体步骤。在这一阶段可以使用伪代码描述算法，在描述整个模型的实现过程时，每一句伪代码即对应一个简单的程序操作。对简单的程序来说，可以直接按顺序列出程序需要执行的操作，从而产生伪代码。但对复杂一些的程序来说，则需要先将整个模型分割成几个大的模块，必要时还需要将这些模块分割为多个子模块，然后用伪代码来描述每个模块的实现过程。4．编写程序要让计算机按照预先设计的算法进行处理，需要对该算法用计算机程序设计语言进行描述，形成计算机程序，并对源程序进行编辑、编译和连接。5．运行程序，分析结果运行可执行程序，得到运行结果。能得到运行结果并不意味着程序正确，要对结果进行分析，看它是否合理。不合理则要对程序进行调试，即排除程序中的故障。32程序难免会有各种错误和漏洞，因此，为了验证程序的正确性，还需要对程序进行测试。测试程序的目的是找出程序中的错误，具体操作是在没有语法和连接上的错误的基础上，让程序试运行多组数据，查看程序是否能达到预期的结果。这些测试数据应是以“任何程序都是有错误的”假设为前提精心设计出来的。6．编写程序文档许多程序是提供给别人使用的，如同正式的产品应当提供产品说明书一样，正式提供给用户使用的程序，必须向用户提供程序文档。程序文档相当于产品说明书，对程序的使用、维护、更新都有很重要的作用，主要包括程序使用说明书和程序技术说明书。（1）程序使用说明书程序使用说明书是为了让用户清楚该程序的使用方法而编写的，其内容包括程序运行需要的软件和硬件环境，程序的安装和启动的方法，程序的功能，需要输入的数据类型、格式和取值范围，涉及文件的数量、名称、内容，以及存放的路径等。（2）程序技术说明书程序技术说明书是为了便于程序员今后对程序进行维护而编写的，其内容包括程序中各模块的描述，程序使用硬件的有关信息，主要算法的解释和描述，各变量的名称、作用，程序代码清单等。334.2.6程序设计的基本方法1．结构化程序设计早期的计算机编程是面向过程的方法，如算术运算1+1+2=4，可以通过设计一个算法来解决。（1）结构化程序设计的基本思路结构化程序设计的程序结构：按功能划分为若干个基本模块；各模块之间的关系尽可能简单，在功能上相对独立；每一模块内部由顺序、选择和循环3种基本结构组成；其模块化实现的具体方法是使用子程序。结构化程序设计采用了模块分解与功能抽象，自顶向下、分而治之的方法，从而能有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子任务，便于开发和维护。虽然结构化程序设计方法具有很多的优点，但它仍是一种面向过程的程序设计方法，它把数据和处理数据的过程分离为相互独立的实体。当数据结构改变时，相关的处理过程都要进行相应的修改，每一种相对于老问题的新方法都要带来额外的开销，程序的可重用性差。由于图形用户界面的应用，程序运行由顺序运行演变为事件驱动，使软件使用起来越来越方便，但开发起来却越来越困难，对于这种软件的功能很难用过程来描述和实现，使用面向过程的方法来开发和维护都将非常困难。34（2）结构化程序设计的主要原则①自顶向下。程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，应先从最上层总目标开始设计，逐步使问题具体化。②逐步求精。对于复杂问题，应设计一些子目标作为过渡，逐步细化。③模块化。一个复杂问题，肯定是由若干稍简单的问题构成的。模块化是指把程序要解决的总目标分解为子目标，再进一步分解为具体的小目标，把每一个小目标称为一个模块。④限制使用goto语句。goto语句是程序设计语言中的一种无条件转移语句，一般用在模块中改变程序执行的顺序。在程序中过多地使用goto语句，会使程序变得难以理解。从提高程序清晰度考虑，一般建议不使用goto语句。（3）结构化程序设计的基本结构面向过程的结构化程序设计采用3种基本结构：顺序结构、选择结构、循环结构。①顺序结构是指程序按照语句先后顺序进行执行，这是开发过程中十分简单的程序结构，设计好顺序执行的语句即可。②选择结构是指在程序设计的过程中出现了分支语句，它根据判断条件结果选择执行其中的一个分支。选择结构包含单分支、双分支和多分支3种表现形式。35③循环结构是指程序反复地执行同一个操作，直到某个表达式的条件为真或者为假则中止循环，否则继续执行对应的循环操作。循环结构可分为两种形式：当型循环和直到型循环。a．当型循环：先判断表达式的条件是否成立，成立的情况下进行循环，直到循环条件不成立，则跳出循环。b．直到型循环：先执行一遍循环语句，然后进行条件判断，如果条件不成立，循环不再执行；如果条件成立，继续执行循环体里的内容。2．面向对象程序设计面向对象（Object-Oriented，OO）是一种软件开发方法，面向对象是一种理解和抽象现实世界的方法，是计算机编程技术发展到一定阶段的产物。面向对象方法可以有效提高编程效率，通过封装技术和消息机制，可以像搭积木一样快速开发出全新的系统。面向对象方法更有利于开发人员以可理解的方式对复杂系统进行分析、设计和编程。面向对象编程更易于维护、重用和扩展。由于面向对象具有封装性、继承性和多态性的特点，因此可以设计出低耦合的系统，使得系统更加灵活，更易于维护。面向对象的概念和应用已经超越了程序设计和软件开发，扩展到数据库系统、交互界面、应用结构、应用平台、分布式系统、网络管理结构、计算机辅助设计技术、人工智能等领域。364.2.7良好的程序设计风格为了提高程序的可阅读性，要形成良好的程序设计风格。风格就是一种好的规范，我们所说的程序设计风格应是一种好的程序设计规范，包括良好的代码设计、函数模块、接口功能以及可扩展性等。更重要的是，程序设计过程中代码的风格包括缩进、注释、变量及函数的命名等。374.2.8程序设计质量评价评价一个程序设计质量如何，首先看该设计是否能满足程序的功能需求。除具有正确性之外，程序设计质量的评估指标还应当包含正确性、可读性、可靠性、可复用性、可扩展性、可维护性、规范性、适应性、内聚度、耦合度等。1．正确性①程序中没有语法错误。②程序运行时没有发现明确的运行错误。③程序中没有不适当的语句。④用有效的测试数据，程序能得到正确的结果。38⑤用无效的测试数据，程序能得到的正确结果。⑥用任何可能的数据，程序在运行时能得到正确的结果。2．可读性程序的内容清晰、明了，便于阅读和理解，没有太多繁杂的技巧。对于大规模、工程化开发软件而言，可读性指标具有非常重要的作用。为提高程序的可读性，可在程序中插入解释型语句，以对程序中的变量、功能、特殊处理细节等进行解释，为今后他人阅读该段程序提供方便。可读性好的程序设计文档容易被其他程序员理解，可读性差的设计会给大型软件的开发和维护过程带来严重的危害。3．可靠性可靠性指标可分解为两个方面的内容。一方面是程序或系统的安全、可靠性，这些工作一般都要在系统分析和设计时严格定义。另一方面是程序运行的可靠性，这只能靠调试时的严格把关来保证编程工作的质量，程序的功能必须按照规定的要求实现，以满足预期的需求。规范性指系统的划分、书写的格式、变量的命名等都按统一的规范进行，这对于程序今后的阅读、修改和维护都是十分必要的。394．可复用性可复用性指程序的架构、类、组件等单元能否很容易被本项目的其他部分或者其他项目复用。5．可扩展性可扩展性指程序面对需求变化时，功能或性能扩展的难易程度。6．可维护性可维护性指程序各部分相互独立，程序之间只有数据联系。也就是说不会发生那种在维护时牵一发而动全身的连锁反应。一个规范性、可读性、结构划分都很好的程序模块，它的可维护性也是比较好的。可维护性好的程序，其错误的修改、遗漏功能的添加也较容易。7．规范性规范性指系统的划分、书写的格式、变量的命名等都按统一的规范进行，这对于程序今后的阅读、修改和维护都是十分必要的。8．适应性适应性指程序交付使用后，若应用问题或外界环境有变化，调整和修改程序比较简便、易行。409．内聚度好的软件设计应该做到高内聚。内聚度表示一个应用程序的单个单元所负责的任务数量和多样性，内聚与单个类或者单个方法单元相关。10．耦合度耦合度表示类之间关系的紧密程度，它决定了变更一个应用程序的难易程度。概括起来，较低的耦合度和较高的内聚度，即我们常说的“高内聚、低耦合”，是所有优秀程序的共同特征。4.

3

Python语言程序设计Python是一种跨平台、交互式、面向对象、解释型的计算机程序设计语言，它具有丰富和强大的库，能够把用其他语言开发的各种模块很轻松地联结在一起。Python支持广泛的应用程序开发，从文字处理到Web开发再到游戏开发，并且简单易学。414.3.1Python程序的运行1．Python程序的运行方式（1）交互式运行方式交互式是利用Python内置的集成开发环境IDLE（IntegratedDevelopmentandLearningEnvironment）来运行程序，适合入门Python、编写功能简单的程序的初学者使用。首先打开命令提示符窗口，在窗口命令提示符“>”后输入“python”命令并执行来启动Python解释器，这样就进入了交互式编程，并且会出现Python提示符“>>>”。在Python提示符“>>>”后输入以下语句，然后按“Enter”键查看运行结果。print("Hello,Python!")以上命令运行结果如下。Hello,Python!没有提示符“>>>”的行表示程序运行结果。输入“exit()”或“quit()”则可以退出IDLE。42（2）脚本式运行方式我们先把Python语句写好，并将其保存在扩展名为“py”的文件里，然后从外部调用这个文件。例如，将如下代码输入hello.py文件中。print("Hello,Python!")输出结果如下。Hello,Python!2．Python程序常用的开发与运行环境Python程序常用的开发与运行环境主要有以下几个。①IDLE：Python内置的集成开发环境，IDLE随Python安装包提供。②PyCharm：由JetBrains公司开发，带有一整套可以帮助用户在使用Python语言开发时提高效率的工具，例如，项目管理、程序调试、语法高亮、代码跳转、智能提示、单元测试以及版本控制。此外，PyCharm提供了一些高级功能，用于支持Django框架下的专业Web应用开发。Python主要有两个版本，即2.x版（简称为Python2）和3.x版（简称为Python3）。打开命令提示符窗口，然后在窗口命令提示符“>”后输入以下命令并执行以运行该脚本。pythonD:\Test\hello.py4.3.2Python的基础语法1．Python的保留字保留字即关键字，是Python本身的专用单词，不能把它们用作任何标识符名称。如果尝试使用关键字作为变量名，Python解释器会报错。Python3包含表4-1所示的35个关键字。43FalseNoneTrueandasassertasyncawaitbreakclasscontinuedefdelelifelseexceptfinallyforfromglobalifimportinislambdanonlocalnotorpassraisereturntrywhilewithyield

表4-1Python3的关键字2．Python标识符的命名要求简单地理解，标识符就是一个名字，就像我们每个人都有属于自己的名字，它的主要作用就是作为变量、函数、类、模块以及其他对象的名称。标识符的命名格式必须统一，这样才会方便不同人阅读，Python的标识符就是用于给程序中变量、类、方法命名的符号（简单来说，标识符就是合法的名字）。标识符需要遵守一些规则，违反这些规则将引发错误。Python中标识符的命名不是随意的，而要遵守一定的命名规则，Python语言的标识符的命名规则如下。①标识符中的第1个字符必须是字母（A～Z和a～z）或下画线（_），其后可以是任意数量的字母、数字和下画线。②Python中的标识符，不能以数字开头，也不能包含空格、@、%以及$等特殊字符。③由于Python3支持UTF-8字符集，因此Python3的标识符可以使用UTF-8所能表示的多种语言的字符。在Python3中，非ASCII标识符也是允许的，标识符中的字母并不局限于26个英文字母，可以包含汉字、日文字符等，但建议尽量不要使用汉字作为标识符名称。44④Python中的标识符对大小写敏感。Python语言的标识符字母是严格区分大小写的，也就是说，两个同样的单词，如果大小写格式不一样，所代表的意义也是完全不同的，如abc和Abc是两个不同的标识符。⑤不能将Python关键字和内置函数名作为标识符名称，如print等。但标识符名称中可以包含关键字。⑥变量不要以双下画线开头和结尾，这是Python专用的标识符。另外，避免使用小写l、大写O和大写I作为变量名。454.3.3Python3的基本数据类型Python3有6个标准的数据类型，其中不可变数据有3个，包括Number（数值）、String（字符串）、Tuple（元组）；可变数据有3个，包括List（列表）、Dictionary（字典）、Set（集合）。下面对数值和字符串类型进行简要介绍。1．数值Python3中数值有4种类型：int（整型，如3）、float（浮点型，如1.23、3E-2）、complex（复数，如1+2j、1.1+2.2j）和bool（布尔型，如True）。（1）整型整型（int）通常被称为整数，可以是正整数、负整数和0，不带小数点。整数可以使用十进制、十六进制、八进制和二进制来表示。例如：46>>>a,b,c=10,100,-786#十进制>>>a,b,c运行结果：(10,100,-786)（2）浮点型浮点型（float）由整数部分与小数部分组成，常被称为浮点数，例如：0.5、1.414、1.732、3.1415926。浮点型也可以使用科学记数法表示，例如5e2。（3）复数Python还支持复数（complex），复数由实数部分和虚数部分构成，虚数部分使用j或J表示，可以用a+bj或者complex(a,b)表示，复数的实部a和虚部b都是浮点型，如2.31+6.98j。2．字符串Python中单引号和双引号的使用完全相同，使用三引号（'''或"""）可以指定一个多行字符串。Python没有单独的字符类型，一个字符就是长度为1的字符串。以下都是正确的字符串表示方式。47word='字符串'sentence="这是一个句子。"paragraph="""这是一个段落，可以由多行组成"""反斜线“\”可以用来转义字符，通过在字符串前加r或R可以让反斜线不发生转义。例如，“r"thisisalinewith\n"”，则\n会显示，并不会换行。Python允许处理Unicode字符串，加前缀u或U即可，如“u"thisisanunicodestring"”。4.3.4Python运算符及其应用1．Python的算术运算符及其应用运算符是一些特殊的符号，主要用于数学计算、比较运算和逻辑运算等。Python语言支持以下类型的运算符：算术运算符、赋值运算符、比较（关系）运算符、逻辑运算符、位运算符、成员运算符、身份运算符。使用运算符将不同类型的数据按照一定的规则连接起来的算式，被称为表达式。例如，使用算术运算符连接起来的算式称为算术表达式，使用比较（关系）运算符连接起来的算式称为比较（关系）表达式，使用逻辑运算符连接起来的算式称为逻辑表达式。比较（关系）表达式和逻辑表达式通常作为选择结构和循环结构的条件语句。（1）Python的算术运算符Python的算术运算符及应用实例如表4-2所示。4849表4-2Python的算术运算符及应用实例运算符名称说明实例输出结果+加两个数相加21+1031-减得到负数或是一个数减去另一个数21－1011*乘两个数相乘或是返回一个被重复若干次的字符串21*10210/除x除以y21/102.1%取余返回除法的余数，如果除数（第2个操作数）是负数，那么结果也是一个负值21%10121%(－10)－9**幂返回x的y次幂21**2441//取整除返回商的整数部分21//21021.0//2.010.0－21//2－11（2）Python算术运算符的运算优先级Python算术运算符的运算优先级由高到低顺序排列如下。第1级：**。第2级：*、/、%、//。第3级：+、－。同级运算符从左至右计算，可以使用()调整运算的优先级，加()的部分优先运算。（3）Python算术表达式Python的算术表达式由数值类型数据与+、－、*、/等算术运算符组成，括号可以用来为运算分组。包含单一算术运算符的算术表达式的实例如图。50>>>5+4#加法9>>>4.3–2#减法2.3>>>3*7#乘法21>>>2/4#除法，得到一个浮点数0.5>>>8/4#总是返回一个浮点数2.0>>>17%3#％操作符表示返回除法的余数2浮点数得到Python完全的支持，不同类型的数值混合运算时，Python会把整数转换为浮点数。包含多种算术运算符的算术表达式的实例如下。51>>>5*3+217>>>50－5*620>>>(50－5*6)/45.0>>>3*3.75/1.57.52．Python的赋值运算符与变量（1）Python的赋值运算符Python的赋值运算符如表4-3所示，表4-3中变量x的初始值为0。52表4-3Python的赋值运算符运算符描述实例等效形式变量x的值=简单赋值运算符x=21+10将21+10的运算结果赋值给x31+=加法赋值运算符x+=10x=x+1041－=减法赋值运算符x－=10x=x－1031*=乘法赋值运算符x*=10x=x*10310/=除法赋值运算符x/=10x=x/1031.0%=取模赋值运算符x%=10x=x%101.0**=幂赋值运算符x**=10x=x**101.0//=取整除赋值运算符x//=10x=x//100.0（2）变量定义及赋值Python中的变量不需要声明变量名及其类型。每个变量在使用前都必须被赋值，变量被赋值以后该变量才会被创建。在Python中，变量就是变量，变量本身没有类型的概念，我们所说的“类型”是变量所指的内存中对象的类型。①变量赋值的基本语法格式。等号（=）运算符用于给变量赋值，变量赋值的基本语法格式如下。<变量名>=<变量值>等号（=）运算符左边是一个变量名，等号（=）运算符右边是存储在变量中的值。变量命名应遵循Python一般标识符的命名规则，变量值可以是任意数据类型。变量被赋值之后，Python解释器不会显示任何结果。例如：53>>>width=20>>>height=5*9>>>width*height900②定义变量。程序中当变量被指定一个值时，对应变量就会被创建。例如：54>>>var1=6>>>var2=10.5>>>print("var1=",var1)>>>print("var2=",var2)运行结果：var1=6var2=10.5变量在使用前必须先“定义”（即赋予变量一个值），否则会出现错误。在Python语言中，除了变量，还有常量的概念，所谓常量就是程序运行过程中值不会发生改变的量，如数学运算中的圆周率，在Python中，没有提供定义常量的关键字。3．Python的比较运算符及其应用比较运算符，也称为关系运算符，用于对变量或表达式的结果进行大小、真假等比较，如果比较结果为成立，则返回True，如果为不成立，则返回False。Python的比较运算符及应用实例如表4-4所示，所有比较运算符的运行结果返回True表示真，返回False表示假，这分别与Python2中的1和0等价，True和False的首字母必须大写，实例假设变量x为21，变量y为10，即x=21，y=10。55运算符名称说明实例运行结果==等于比较x和y两个对象是否相等x==yFalse!=不等于比较x和y两个对象是否不相等x!=yTrue>

大于比较x是否大于yx>yTrue<

小于比较x是否小于yx<yFalse>=大于或等于比较x是否大于等于yx>=yTrue<=小于或等于比较x是否小于等于yx<=yFalse表4-4Python的比较运算符及应用实例例如：56>>>x=5>>>y=8>>>print(x==y)>>>print(x!=y)FalseTrue比较运算符与比较对象（变量或表达式）构建出比较表达式，也称为关系表达式。比较表达式通常用在条件语句和循环语句中作为“条件表达式”。以上实例的运行结果：4．Python的逻辑运算符及其应用Python语言支持逻辑运算符，逻辑运算符是对True和False两种布尔值进行运算，运算后的结果仍是一个布尔值。逻辑运算符也可以对非布尔值进行运算。Python对非布尔值的逻辑运算符及应用实例如表4-5所示，实例假设变量x为21，变量y为10，变量z为0，即x=21，y=10，z=0。57表4-5Python对非布尔值的逻辑运算符及应用实例运算符名称逻辑表达式结合方向说明实例运算结果and逻辑与xandy从左到右如果x为False或0，xandy返回False或0，否则返回y的计算值xandy10xandz0zandx0or逻辑或xory从左到右如果x是True，返回x的值，否则返回y的计算值xory21xorz21zorx21not逻辑非notx从右到左如果x为True，返回False，如果x为False，返回TruenotxFalsenotyFalsenot(xandy)Falsenot(xory)FalsenotzTrue4.3.5Python程序流程控制程序的流程控制结构主要包括选择结构和循环结构，选择结构是根据条件表达式的结果选择运行不同语句的流程结构；循环结构则是在一定条件下反复运行某段程序的流程结构，被反复运行的语句体称为循环体，决定循环是否终止的判断条件称为循环条件。流程控制语句的条件表达式主要为比较（关系）表达式和逻辑表达式。1．Python的顺序结构计算机程序主要有3种基本结构：顺序结构、选择结构、循环结构。如果没有流程控制的话，整个程序都将按照语句的编写顺序（从上至下的顺序）来运行，而不能根据需求决定程序运行的顺序。2．Python的流程控制流程控制对任何一门编程语言来说都是非常重要的，因为它提供了控制程序运行的方法。Python3根据条件语句的运算结果选择不同路径的运行方式。Python条件语句通过一条或多条语句的运行结果（True或者False）来决定运行的代码块。可以通过图4-6来简单了解条件语句的运行过程。如果条件表达式的值为True，则执行代码块，否则不执行代码块。5859图4-6条件语句的运行过程示意3．Python的选择结构及其应用Python的选择结构是根据条件表达式的结果选择运行不同语句的流程结构，选择语句也称为条件语句，即按照条件选择运行不同的代码片段，Python中选择语句主要有3种形式：if语句、if…else语句和if…elif…else语句。Python使用if…elif…else多分支语句或者if语句的嵌套结构实现多重选择。（1）if语句及其应用Python中使用if关键字来构成选择语句，if语句的一般形式如下。60if<条件表达式>:<语句块>>>>password=input("请输入密码：")条件表达式可以是一个单纯的布尔值或变量，也可以是比较表达式或逻辑表达式，如果条件表达式的值为True，则运行<语句块>；如果条件表达式的值为False，就跳过<语句块>，继续运行后面的语句。例如：运行结果：请输入密码：123456>>>ifpassword=="123456":print("输入的密码正确")61输入的密码正确if<条件表达式>:<语句块1>else：

<语句块2>运行结果：（2）if…else语句及其应用Python中if…else语句的一般形式如下。if…else语句主要解决二选一的问题，使用if…else语句时，条件表达式可以是一个单纯的布尔值或变量，也可以是比较表达式或逻辑表达式，如果条件表达式的值为True，则运行if语句后面的<语句块1>，否则，运行else后面的<语句块2>。（3）if…elif…else语句及其应用Python中if…elif…else语句的一般形式如下。62if<条件表达式1>:<语句块1>elif<条件表达式2>:<语句块2>else:<语句块N>Python中用elif代替了elseif，所以多分支选择结构的关键字为if…elif…else。if…elif…else语句运行的规则如下。条件表达式1和条件表达式2可以是一个单纯的布尔值或变量，也可以是比较表达式或逻辑表达式。如果<条件表达式1>的值为True，则运行<语句块1>；如果<条件表达式1>的值为False，将判断<条件表达式2>，如果<条件表达式2>的值为True，则运行<语句块2>；如果<条件表达式1>和<条件表达式2>的值都为False，则运行<语句块N>。Python中if语句每个条件后面要使用冒号“:”，表示接下来是满足条件后要运行的语句块。使用缩进来划分语句块，相同缩进数的语句在一起组成一个语句块。if和elif都需要判断条件表达式的真假，而else则不需要判断；另外，elif和else都必须与if一起使用，不能单独使用。4．for循环语句及其应用循环结构是在一定条件下反复运行某段程序的流程结构，被反复运行的语句体称为循环体，决定循环是否终止的判断条件称为循环条件。Python中的循环语句有for和while两种类型。Python中for循环也称为计次循环，其循环语句可以遍历各种序列数据，如一个列表或者一个字符串。while循环也称为条件循环，可以一直进行循环，直到条件不满足时才结束循环。for循环通常适用于枚举或遍历序列，以及迭代对象中的元素，一般应用于循环次数已知的情况。for循环语句的基本格式如下。63for<循环变量>in<序列结构>:<语句块>其中，循环变量用于保存取出的值，序列结构为要遍历或迭代的序列对象，如字符串、列表、元组等，语句块为一组被重复运行的语句。for循环语句的运行流程图如图4-7所示。64图4-7for循环语句的运行流程图5．while循环语句及其应用Python中的while循环通过一个条件表达式来控制是否要继续反复运行循环体中的语句块。Python中while循环语句的一般形式如下。65while<条件表达式>:

<语句块>while循环语句的条件表达式的值为True时，则运行循环体的语句块；运行一次后，重新判断条件表达式的值，直到条件表达式的值为False时，退出while循环。while循环语句的运行流程图如图4-8所示。Python中while循环语句的条件表达式后面要使用冒号“:”，表示接下来是满足条件后要运行的语句块。使用缩进来划分语句块，相同缩进数的语句组成一个语句块。66图4-8while循环语句的运行流程图4.

4数据和数据结构概述在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。随着计算机应用领域的扩大和软硬件的发展，非数值计算问题显得越来越重要，这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构。描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。674.4.1数据结构的基本概念在系统地学习数据结构知识之前，先明确一些基本术语的确切含义。1．数据计算机应用程序处理各种各样的数据，数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据包括实数和复数，主要用于工程计算、科学计算和商务处理等，非数值数据包括字符、文字、图形、图像、音频、视频等。2．数据元素数据元素（DataElement）是数据的基本单位。在不同的条件下，数据元素又可称为元素（Element）、节点（Node）、顶点（Vertex）、记录（Record）等。有时，一个数据元素可由若干个数据项（DataItem）组成，例如，学生管理信息系统中学生信息表的每一个数据元素就是一条学生记录，它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫作基本项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再被分割的最小单位；另一种叫作组合项，如学生的成绩，它可以再被划分为数学成绩、物理成绩、化学成绩等更小的项。通常，在解决实际应用问题时是把每个学生记录当作一个基本单位进行访问和处理的。3．数据对象数据对象（DataObject）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据对象的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据对象，顶点A和顶点B各自代表一个城市，是该数据对象中的两个实例，其数据元素的值分别为A和B。4．数据结构数据结构（DataStructure）是指互相之间存在着一种或多种关系的数据元素的集合。在各种问题中，数据元素都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的相互关系称为结构。数据结构包括数据的逻辑结构和数据的物理结构。数据的逻辑结构是指数据元素之间的关系，从逻辑关系角度描述数据，可以看作从具体问题抽象出来的数学模型，它与数据的存储无关。数据元素及数据元素之间的逻辑关系在计算机存储器内的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。68根据数据元素间关系的不同特性，通常有下列4种基本的结构。（1）集合结构集合是一种常用的数据表示方法，是数据元素的有限集合。该结构中，数据元素间的关系是“属于同一个集合”，集合是元素关系极为松散的一种结构。对集合可以进行多种操作，假设集合S由若干个元素组成，可以按照某一规则把集合S划分成若干个互不相交的子集合，例如，集合S={1,2,3,4,5,6,7,8,9,10}，可以被分成如下3个互不相交的子集合。S1={1,2,4,7},S2={3,5,8}，S3={6,9,10}。集合{S1,S2,S3}就被称为集合S的一种划分。此外，在集合中还有常用的一些运算，如集合的交、并、补、差，以及判定一个元素是否是集合中的元素等。（2）线性结构线性结构指的是数据元素的有序集合，该结构中数据元素之间存在着一对一的关系，线性表、栈、队列、字符串都属于线性结构。（3）树形结构树形结构指的是数据元素的层次结构，该结构中的数据元素之间存在着一对多的关系。（4）图形结构图形结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。树形结构和图形结构都属于非线性结构。69704.4.2数据的基本运算数据的运算即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合，只有确定了物理结构，才能具体实现这些运算。数据的运算通常包括以下5种操作。①插入：在指定位置上添加一个新节点。②删除：删除指定位置上的节点。③更新：修改某个节点的值。④查找：搜索满足指定条件的节点及其位置。⑤排序：按指定的顺序使节点重新排列。4.

5典型的数据结构典型的数据结构有线性表、栈、队列、树、图等。1．线性表线性表是一种线性结构，线性结构的特点是数据元素之间存在一种线性关系，数据元素“一个接一个地排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，例如，学生信息表是线性表，表中数据元素的类型为学生类型；一个字符串也是一个线性表，表中数据元素的类型为字符型。线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为（a1,a2,…,ai-1,ai,ai+1,…,an）。其中n为表长，n=0时称为空表，即没有任何数据元素的线性表。线性表中相邻元素之间存在着顺序关系。将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。对于ai，当i=2,…,n时，有且仅有一个直接前趋ai-1，当i=1,2,…,n－1时，有且仅有一个直接后继ai+1，而a1是表中第一个元素，它没有直接前趋，an是最后一个元素，它没有直接后继。712．栈栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶（StackTop），固定端称为栈底。当栈中没有元素时称为空栈。向栈中插入元素称为进栈，从栈中删除元素称为出栈。元素的进栈和出栈使得栈顶的位置经常变动。如图4-9所示