配套课件-数据结构与算法分析.ppt

1、第第1 1章章 绪绪 论论1.1 软件的基本概念1.2 数据结构概述1.3 算法与算法分析1.4 程序设计的关键技术1.5 程序设计的步骤及实例1.1 软件的基本概念从一般意义上讲，能够在计算机上运行的程序都可以称为软件。软件更准确的定义是利用计算机本身提供的逻辑功能，合理地组织计算机的工作流程，简化或替代人们使用计算机过程中的各个环节，提供给使用者一个便于操作的工作环境的“程序集”。软件是逻辑的而不是物理的产品，与硬件相比具有以下完全不同的特征：(1)软件是由开发或工程化而形成的，而不是由传统意义上的制造产生的。(2)软件不会磨损。软件的故障率随时间的推移而降低，而硬件的故障率随时间的推移而

2、增加。(3)大多数软件是自定义的，而不是通过已有的组件组装而来的。1.1.1 软件应用从某种程度上讲，对软件应用给出一个确切的分类是比较困难的。下面给出的一些软件的应用领域，可以看做是一种潜在的应用分类：(1)系统软件。(2)实时软件。(3)商业软件。(4)工程和科学计算软件。(5)嵌入式软件。(6)个人软件。(7)人工智能软件。1.1.2 软件生存期1制定计划2需求分析和定义3软件设计4程序编制5软件测试6运行/维护 图1-1 软件生存期模型1.1.3 软件技术软件是由程序、数据和文档组成的。为了开发高质量的软件，软件工程师必须遵循一个开发策略，即软件过程模型。软件技术是指开发软件所需的所有

3、技术的总称。按照软件分支学科的内容划分，软件技术包括以下几个领域：(1)软件工程技术。(2)程序设计技术。(3)软件工具环境技术。(4)系统软件技术。(5)数据库技术。(6)实时软件技术。(7)网络软件技术。(8)与实际工作相关的软件技术。1.1.4 程序设计技术程序设计技术的目标是提高程序的质量与生产率，最终实现程序的工业化生产。影响程序质量的因素有很多，如正确性、性能、可靠性、容错性、易用性、灵活性、可扩充性、可理解性、可维护性和复用性等。下面所介绍的程序设计技术主要是针对规模小且一个人能够独立完成的程序设计技术。程序设计的主要环节有：明确需求、设计、实现(即编码)、测试等，如图1-2所示

4、。图1-2 程序设计的主要环节1明确需求程序设计的第一步工作是明确需求，即明确待解决的问题是什么，也称为问题分析阶段。2设计设计是把需求转化为程序的最重要的环节。设计的优劣在根本上决定了程序的质量，它包括程序结构设计、模块设计、数据结构与算法设计和用户界面设计。1)结构设计结构是程序中最本质的内容。(1)结构是对复杂事物的一种抽象。(2)结构在一定的时间内保持稳定。2)模块设计 在程序结构设计完成后，就已经在宏观上明确了各个模块具有的功能以及在结构中的位置。我们习惯地从功能上划分模块，并保持“功能独立”是模块化设计的基本原则，这是因为功能独立的模块可以降低开发、测试、维护等阶段的代价。但是功能

5、独立并不意味着模块之间保持绝对的孤立，一个系统要完成某项任务，需要各个模块相互配合才能实现，此时模块之间就要进行信息交流。评价模块设计优劣的三个特征因素是信息隐藏、内聚与耦合和封闭开放性。(1)信息隐藏。(2)内聚与耦合。耦合的强度依赖于以下几个因素：一个模块对另一个模块的调用；一个模块向另一个模块传递的数据量；一个模块施加到另一个模块的控制的多少；模块之间接口的复杂程度。(3)封闭开放性。3)数据结构与算法设计设计高效率的程序是基于良好的数据结构与算法，而不是基于编程小技巧。人们对常用的数据结构与算法的研究已经相当透彻了，可以归纳出下列设计原则：(1)每一种数据结构与算法都有其时间、空间的开

6、销和收益。(2)与开销和收益有关的是时间空间的权衡。(3)程序员应该充分地了解一些常用的数据结构与算法，避免不必要的重复设计工作。(4)数据结构与算法为应用服务。4)用户界面设计(1)界面的合适性。(2)界面的风格。(3)界面的广义美。3编码编码(Coding)的任务是为每个模块编写程序，也就是说，将设计的结果转换为用某种程序设计语言编写的程序，这个程序必须是无错的，并且要有必要的内部文档和外部文档。4测试程序测试是指在受控制的条件下对程序进行操作并评价操作结果的过程。所谓控制条件，应包括正常条件与非正常条件。测试是程序的执行过程，测试的目的是发现尽可能多的缺陷。1.2 数据结构概述1.2.1

7、 数据结构的引入从提出一个实际问题到计算机解出答案，需要经历下列步骤：分析阶段、设计阶段、编码阶段和测试维护阶段等。其中，分析阶段就是要从实际问题中提取操作对象以及操作对象之间的关系。下面举例说明。例1-1计算机管理图书目录问题。要利用计算机帮助查询书目，首先必须将书目存入计算机，那么这些书目如何存放呢？我们既希望查询时间短，又要求节省空间。一个简单的办法就是建立一张表，每本书的信息只用一张卡片表示，在表中占一行，如表1-1所示。例1-2 工厂的组织管理问题。某工厂的组织机构如图1-3所示。厂长要通过计算机了解各个科室及车间的工作和生产情况，于是，将该组织机构抽象成某个结构树，如图1-4所示，

8、它可以表示问题中各数据之间的关系。只要将数据按一定的方式存入计算机中，并对这棵树遍历，就能了解厂内的整个情况。图1-3 工厂组织机构 图1-4 树形结构 例1-3 多岔路口交通灯管理问题。通常，在十字交叉路口只要设置红绿两色的交通灯便可保持正常的交通秩序，但是对于多岔路口，需要设置几种颜色的交通灯，既能使车辆相互间不发生碰撞，又能达到交通控制的最大流通量呢？图1-5(a)所示是一个实际的五岔路口，我们如何设置交通灯，即最少应设置几种颜色的交通灯，才能保证正常的交通秩序？图1-5 五岔路口交通灯管理问题1.2.2 数据结构的基本概念计算机处理的对象是数据，那么什么是数据呢？简单地讲，数据就是客观

9、事物在计算机中的表示，它具有可识别性、可加工处理性和可存储性等特征。数据结构所要研究的主要内容可以简要地归纳为以下三个方面：(1)研究数据元素之间固有的客观联系，即数据的逻辑结构(Logical Structure)。(2)研究数据在计算机内部的存储方法，即数据的存储结构(Storage Structure)，又称物理结构。(3)研究如何在数据的各种结构(逻辑的和物理的)上施加有效的操作或处理(算法)。表 1-2 学 生 成 绩 表 学 号 姓 名 性 别 课 名 成 绩 22001 王 丽 女 物理 81 22002 刘建东 男 物理 76 22031 陈立平 男 物理 92 数据的逻辑结构

10、有两大类：(1)线性结构。线性结构的逻辑特征是有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一种典型的线性结构。本书第2章第4章介绍的数据逻辑结构都是线性结构。(2)非线性结构。非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。例如，树和图就是典型的非线性结构。数据的存储结构可用以下四种基本的存储方法得到。(1)顺序存储方法。(2)链接存储方法。(3)索引存储方法。(4)散列存储方法。例1-4 抽象数据类型复数的定义。1.2.3 数据结构与程序设计关于“计算机科学”，从20世纪60年代以来，一直有两种观点。一种观点认为“计算机科学是一种

11、基于信息结构转换的科学”，另一种观点认为“计算机科学是算法的学问”。这两种观点从不同的侧面说明了数据结构、算法在计算机科学中的重要位置。实际上数据结构与算法之间存在着本质联系，应该说，数据结构与算法是计算机科学的核心。例1-5 电话号码查询问题。假定要编写一个程序，查询某人的电话号码。对任意给出的一个姓名(假设不存在重名的情况)，若该人的电话已登记，则要迅速找到其电话号码；否则指出该人没有电话。解决此问题的办法是，首先要构造一张电话号码登记表，表中每个结点存放两个数据项：姓名和电话号码。其次，如何组织表中的数据是问题的关键，最简单的方法是将每个人的信息顺序存放在表中(如图1-6所示)，查找时从

12、头开始依次查找姓名，直到找到相应的姓名，或找遍整个表没有找到为止。但是，这种查找方法不适用于表中内容庞大的情况。图1-6 电话号码查询中的顺序存储现在我们从数据结构的角度考虑，即对图1-6所示表中信息的组织和存储重新考虑，将表中的姓名按姓氏排列，并另外再建一张姓氏索引表，其存储结构如图1-7所示。图1-7 电话查询中的索引存储 例1-6 人事档案的建立及管理。假设要建立一个大学的教师和学生档案，并完成日常的管理(如查询、插入、删除等)。教师和学生档案的逻辑结构如图1-8所示(以一系教师和学生逻辑结构示意)。图1-8 人事档案1.3 算法与算法分析1.3.1 算法的概念通俗地讲，一个算法就是一种

13、解题方法。更严格地说，算法是由若干条指令组成的有限序列，它必须满足以下性质。(1)输入性：具有零个或多个输入量，即算法开始前对算法给出的初始量。(2)输出性：至少产生一个输出。(3)有穷性：每条指令的执行次数必须是有限的。(4)确定性：每条指令的含义必须明确，无二义性。(5)可行性：每条指令都应在有限的时间内完成。1.3.2 算法分析求解一个问题，可以有许多种不同的算法，究竟如何评价这些算法的好坏呢？显然，选用的算法首先应该是“正确的”，其次，还需考虑以下几个因素：(1)执行算法所消耗的时间。(2)执行算法所消耗的存储空间，其中主要考虑辅助存储空间。(3)算法的可读性好，易理解，易编码、调试。

14、例如，求两个n阶方阵的乘积C=AB，其算法描述如下：例如，MatrixMulti算法的时间复杂度T(n)在n趋向无穷大时，显然有2n12n3nn2limnT(n)lim323n3n例如，交换i和j的内容。temp=i;i=j;j=temp;对于较复杂的算法，我们则可以将其分隔成容易估算的几个部分，然后利用“O”的求和原则得到整个算法的时间复杂度。例如，若算法中两个部分的时间复杂度分别为T1(n)=(f(n)和T2(n)=O(g(n)，则总的时间复杂度为 T(n)=T1(n)+T2(n)=O(max(f(n),g(n)若T1(m)=O(f(m)，T2(n)=O(g(n)，则总的时间复杂度为T(m

15、,n)=T1(m)+T2(n)=O(f(m)+g(n)图1-9 几种常见函数的增长率类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间的量度，记做S(n)=O(f(n)其中，n为问题的规模。渐近空间复杂度也常常简称为空间复杂度。1.4 程序设计的关键技术结构化程序设计中要遵循如下原则：(1)分解原则。(2)模块独立性原则。(3)编码结构化原则。1.4.1 程序结构设计1自顶向下自顶向下层次结构设计方法的主要思想是：先设计第一层(即顶层)，然后步步深入，逐层细分，逐步求精，直到整个问题可用程序设计语言明确地描述出来为止。2自底向上

16、自底向上层次结构设计方法的主要思想：先设计底层，最后设计顶层。这种层次结构设计方法的优点是：由表及里、由浅入深地解决问题。自底向上层次结构设计方法的不足之处是：在逐步细化的过程中可能发现原来的分解细化不够完善。这种层次结构设计方法主要用于修改、优化或扩充一个程序。3模块划分模块划分的目的是将较复杂的程序/模块分解为规模较小、功能单一的子模块，以便于把握程序的实现。为了达到这个目的，必须深入理解程序/模块的功能及其应用环境，在此基础上才能设计出好的程序。图1-10 程序结构与组成示意图 图1-11 程序的分解示意图(1)模块独立性原则。每一个功能模块都必须是独立的，即模块内部的处理与其他模块的任

17、何信息处理无关。模块外部只提供输入条件和输出条件，这是与其化模块之间仅有的联系。图1-12 块间联系与块内联系示意图(2)信息隐蔽原则。程序经常被其他程序设计人员阅读，在整个生命期中要经历多次修改，程序设计时如何划分模块，才能使将来修改的影响范围尽量小呢？D.Parnas提出了信息隐蔽原则。根据信息隐蔽的原则，设计时应列出可能发生变化的因素，在划分模块时将一个可能发生变化的因素包含在某个模块的内部，使其他模块与这个因素无关。这样，将来某个因素发生变化时，我们只需要修改一个模块就够了，而其他模块则不受这个因素的影响。下面用一个例子来解释信息隐蔽原则：用数组实现了一个栈，有十个模块要对栈做存取操作

18、。一种设计方案是将数组、栈顶、深度等作为全程变量，由各个模块自行对栈进行存取操作，如图1-13(a)所示，也就是说十个模块都需了解栈的具体结构细节。这个方案的缺点是：如果将来栈的具体结构发生变化(如深度增加)，那么这十个模块都必须做相应的修改。另一种设计方案是根据信息隐蔽的原则，先构造两个模块Push和Pop，它们分别负责对栈做存取操作，十个模块通过调用Push和Pop实现栈操作，如图1-13(b)所示。此时，栈的具体结构是隐含在Push和Pop两个模块内部的，其他十个模块完全不了解这些细节，栈对这十个模块来说是一个抽象的数据结构。这个方案的优点是：如果将来需要修改栈的具体结构，只须改动Pus

19、h和Pop两个模块就够了，其余十个模块完全不受影响。图1-13 模块对栈的存取操作(3)重用性原则。软件的可重用性一直是软件工程所追求的目标之一，人们希望利用标准化的软件模块快速地构建特定的应用系统。软件开发的全生命周期都有可重用的价值，包括项目的组织，软件需求、设计、文档、实现、测试方法和测试用例，都是可以被重复利用或借鉴的有效资源。软件代码的可重用性是最直观、最容易想到的部分，也是程序员们最乐意追求和有成就感的部分。4模块功能确定和接口定义在模块划分原则的基础上，可根据程序的功能对程序进行模块划分。在模块划分时一定要遵循模块划分原则和程序的功能要求。程序具有特定的功能，而程序的功能是由所有

20、模块的功能经过有机组合来实现的，因此确定每一个模块的功能和模块间的关系是非常重要的。确定模块的功能必须与模块划分同时考虑。接口定义是指为了实现模块间的相互调用而约定的调用协议，即调用模块所应遵守的规则。如图1-13中的模块Push，该模块的输入是一个有效的X，其操作结果是将X入栈，那么该模块的接口可定义为(用C语言给出)：Output_Type Push(Stack_Type X);在调用该模块时，应采用如下格式：Stack_Type input;Output_Type output;output=Push(input);5调用关系确定模块间的调用关系是指模块间调用的次序。模块调用关系分为递归

21、调用和非递归调用。递归调用是指模块自身调用自己；非递归调用是指模块调用其他模块。递归调用分为直接递归调用和间接递归调用,直接递归调用是指模块直接调用自身；间接递归调用是指模块通过其他模块调用自身。图1-14 模块间调用关系说明在确定调用关系时，应根据程序的处理流程确定模块间的调用关系。实际上，程序的处理流程与程序中模块的调用关系有着明显的对应关系。例如，在1.5.2节将介绍的程序设计实例中，查询请求的处理流程(图1-18)所对应的模块调用关系如图1-15所示。图1-15 模块调用关系1.4.2 模块设计1输入到输出的映射建模输入到输出的映射建模是根据模块的功能要求，对输入进行有效的变换，得到期

22、望的输出结果。假设Compute模块的功能是求input的平方根，并且没有现成的平方根函数，则抽象的映射为inputoutput 2数据结构和算法设计算法的描述方法有自然语言描述法、类计算机语言描述法、形式语言描述法和图示描述法，而使用最普遍的方法是类计算机语言描述法和图示描述法。最具代表性的类计算机语言描述方法是类Pascal语言，而图示描述法中常用的方法是流程图。1.4.3 良好的编程风格好程序除了满足必需的要求(如正确性、可靠性、健壮性、高效率等)外，还必须具有好的编程风格。好的编程风格对于好的程序设计具有关键性作用，它使程序代码容易被读懂。1命名在程序中有大量的变量、常量、宏和函数等，

23、如何为这些变量和函数命名？名字用来标识某个对象，带着说明其用途的一些信息。一个名字应该是简练的、容易记忆的，如果可能的话，最好是能够拼读的。一个变量的作用域越大，它的名字所携带的信息就应该越多。因为全局变量可以出现在整个程序中的任何地方，所以它们的名字应该足够长，具有足够的说明性，以便使读者能够记得它们的用途。2注释注释是帮助程序阅读的一种手段。好的注释可用于简洁地说明程序的突出特征，帮助读者理解程序。(1)不要注释明显的内容。(2)给函数和全局数据加注释。(3)不要注释差的代码，而应重写代码。(4)不要与代码矛盾。(5)澄清情况，不要添乱。3程序的外观1)块的对齐方式2)适当的缩进和空白一致

24、的缩进风格会使程序清晰易懂。缩进用于描述程序中各部分或语句之间的结构关系。在嵌套结构中，每个内层部分或语句应该比外层缩进适当的空格。例如：for(i+;i 100;fieldi+=c);fieldi=0;return 0;该程序段的格式就不好，重新调整格式如下所示：for(i+;i=actblks|(block_id unblocks)4)分解复杂的表达式C语言有很丰富的表达式语法结构和运算符，因此很容易把一大堆内容写进一个语句中。例如：*x+=(*xp=(2*k (n-m)?ck+1:dk-);该表达式虽然很紧凑，但是写进一个语句里的内容确实太多了，把它分解成几个部分，其含义更容易把握，如下

25、所示：if(2*k (n-m)*xp+=ck+1;else*xp+=dk-;如果将其改写为if(2*k (n-m)*xp=ck+1;else*xp=dk-;*x+=*xp;则更加直观。4一致性和习惯用法1)使用一致的缩排和加括号风格缩排可以显示出程序的结构，那么什么样的缩排风格最好呢？是采用次行风格，还是采用行尾风格？实际上，特定风格远没有一致性那么重要。2)为了保持一致性，使用习惯用法和自然语言一样，程序设计语言也有许多习惯用法，也就是那些经验丰富的程序员的习惯方式。在学习一个语言的过程中，一个主要问题就是逐渐熟悉它的习惯用法。1.4.4 排错与测试1排错1)排错系统每种语言的编译系统通常都

26、带有一个排错系统。它常常作为整个开发环境里的一个组成部分，在这个环境里集成了有关程序建立和源代码编辑、编译、执行和排错的各种功能。排错系统使我们能够以语句或者按函数的方式分步执行程序，在某个特定程序行或者在某个特定条件发生时停下来等，通常还提供了按照某些指定格式显示变量值等功能。2)寻找错误线索(1)寻找熟悉的模式。(2)检查最近的改动。(3)取得堆栈轨迹。(4)键入前仔细读一读。(5)把代码解释给别人。3)写测试代码如果上面的方法都不能帮助定位程序中的错误，这时我们可以编写自己的检查函数去测试某些条件，打印出相关变量的值或者终止程序，如下所示：另外，还可以把对Check的调用加到程序里可能需

27、要它的地方，如下所示：Check(“before suspect”);/suspect code Check(“after suspect”);即使在错误排除后，也不要简单地将Check丢掉，而应让它留在源程序里，将它写成注释或者用一个排错选项来控制它，以便在遇到问题时还可以重新启用。2测试1)测试代码的边界情况在编写好一个简单的代码段，如一个循环或一个条件分支语句之后，就应该检查条件所导致的分支是否正确，循环实际执行的次数是否正确等。这种工作称为边界条件测试，原因是这种检查是在程序和数据的自然边界上。例如，检查不存在的或者空的输入，单个的输入数据项，一个正好填满了的数组等。这里要强调的是：大

28、部分错误都出现在边界上。如果一段代码出错，则错误最可能是出现在边界上。2)测试前置条件和后置条件通过验证在某段代码执行前所期望的或必须满足的性质(前条件)，执行后的性质(后条件)是否成立，是防止错误发生的一个方法。保证输入取值在某个范围之内是前置条件测试的一种常见例子。3)使用断言C语言里提供了一种断言机制，它鼓励给程序加上前/后条件测试。断言失败将会终止程序，所以这种机制通常是保留给某些特殊情况使用的，写在这里的错误是不应该出现的，而且是无法恢复的。4)防御性的程序设计还有一种很有用的技术，那就是在程序里增加一些代码，专门处理所有“不可能”出现的情况，也就是处理那些从逻辑上讲是不可能发生的，

29、但是或许(由于其他地方的某些失误)可能出现的情况。前面讨论的在Average里加上检查数组长度是否为0或者负数就是一个例子。5)以递增方式做测试测试应该与程序的构造同步进行。与逐步推进的方式相比，以“大爆炸”方式先写出整个程序，然后做测试，面临的困难较多，通常也要花费更长时间。写出程序的一部分并测试，加上一些代码后再进行测试，如此下去，这样做效果会更好。如果有两个程序包，且都已经写好并经过了测试，那么就把它们直接连接起来测试，看看它们能否在一起工作。6)弄清所期望的输出对于所有测试，都必须知道正确的答案是什么，如果不知道，那么所做的测试就是白白浪费时间了。7)测试自动化以手工方式做大量测试既枯

30、燥无味又很不可靠，严格意义上的测试总要涉及大量的测试实例，大量的输入以及大量的输出比较，所以测试最好由程序来做，原因是程序不会疲劳，也不会疏忽。花点时间编写一个简单程序，用它包装起所有的测试，这样我们就可以通过一个按键使得测试顺利执行。8)测试用例的设计所谓测试用例，就是以发现错误为目的而精心设计的一组测试数据。测试一个程序，往往需要一组测试用例。每一个完整的测试用例，不仅包含有被测程序的输入数据，而且还包括用这组数据执行被测程序后预期的输出结果。每次测试时，都要把实测的结果与期望的结果做比较，若不相符，就表明程序可能存在错误。(1)等价分类法。(2)边界值分析法。(3)错误猜测法。(4)因果

31、图法。(5)逻辑覆盖法。语句覆盖。判定覆盖。条件覆盖。条件组合覆盖。1.4.5 程序性能(1)可维护性。(2)可靠性。(3)效率。1.5 程序设计的步骤及实例1.5.1 程序设计的步骤程序设计的步骤如下：1明确问题的要求对要解决的问题，必须通过分析明确题目的要求，列出所有已知量，找出题目的求解范围、解的精度等。2分析问题与问题分解根据问题的要求，明确程序应具有哪些功能，分析清楚解决问题的流程，以及这些功能如何有效地组织在一起解决问题。3设计程序结构层次结构是一种主要的程序结构。在结构化程序设计中，程序层次结构设计的依据是：为了实现程序的功能需要哪些支持，这些支持与程序的功能要求就构成了程序的“

32、一级”程序层次结构。假设程序功能要求为G，为了实现G必须有五个支持(S1，S2，S3，S4，S5)，那么该程序的一级层次结构如图1-16所示。图1-16 层次结构设计的基本原理4算法与数据结构设计在程序结构设计完成之后，需要对其中的每一个模块进行更详细的设计，该设计过程一般称为模块设计或函数设计。5编写程序实现在程序结构框架和所有模块设计完成之后，接下来的工作是采用某种程序设计语言实现上述设计。程序实现时需要考虑的问题有：选择程序设计语言，界面设计，程序风格和实现程序时的其他细节问题。把整个程序看做一个整体，先全局后局部，自顶向下，一层一层地分解处理，如果某些子问题的算法相同而仅参数不同，则可

33、以用子程序来表示。6调试运行调试程序的过程就是排错的过程，其目的是解决程序中的语法错误和明显的逻辑错误。语法错误可根据系统的提示修改。明显的逻辑错误表现为运行结果不正确，对此一般采用的方法是跟踪程序的运行过程，发现错误出现的位置，并做相应的修改。7测试与结果分析测试的目的是发现调试时未能发现的错误。一般的方法是给出测试用例，并运行程序，分析期望的运行结果与实际运行结果。如果两个结果不一致，则需要分析原因，并改正。8写出程序的文档程序的文档主要用来对程序中的变量、函数或过程做必要的说明，解释编程思路，画出框图，讨论运行结果等。1.5.2 程序设计实例1问题与分析很多读者看到该问题后认为：问题简单

34、，容易实现。实际情况真是这样吗？完全不是。真实情况是很多学生在8个小时的实验时间内没有完成程序设计。其原因归纳起来有两条：一是没有完全理解问题；二是基础薄弱，面对较大的程序无从下手。图1-17 学生信息查询问题的原型2问题处理流程与问题分解图1-17仅仅说明了问题，并没有给出具体的处理问题过程，下面将从学生信息查询的实际过程来进一步说明处理该问题的流程。程序的使用者有两类：一是查询者；二是维护者。因此将处理流程分为查询者流程和维护者流程。查询者的使用步骤如下：(1)启动查询过程；(2)选择查询方式；(3)输入查询条件；(4)根据查询条件在学生信息文件中查询；(5)显示查询结果；(6)结束本次查

35、询。对于查询者而言，处理问题的流程如图1-18所示。图1-18 查询请求的处理流程维护者的使用步骤如下：(1)启动维护过程；(2)选择维护方式；(3)输入维护内容；(4)根据维护方式和维护内容维护学生信息文件；(5)显示维护结果；(6)结束本次维护。对于维护者而言，处理问题的流程如图1-19所示。图1-19 维护请求的处理流程根据问题的分析和初步的处理流程，可以将问题分解为两个子问题：查询和维护，如图1-20所示。图1-20 问题分解假设经过交流得到的查询功能要求如下：(1)根据学号或姓名能够完成学生基本信息及学生家庭信息等的查询；(2)根据家庭所在地(地址)和系别查询学生的基本信息。经过与问

36、题提出人员交流得到的维护功能要求如下：(1)根据学号修改学生的信息；(2)增加一个新学生的信息；(3)删除一个学生的信息。据此可以得到维护的功能包括：修改学生信息，插入一个新学生的信息，删除一个学生的信息。根据上述要求和功能划分，对问题做进一步的分解，其分解的结果如图1-21所示。图1-21 对子问题的进一步分解根据问题分解的结果对问题处理流程进一步细化，得到如图1-22和图1-23所示的细化后的查询和维护处理流程。图1-22 细化后的查询处理流程 图1-23 细化后的维护处理流程3程序结构根据上述分析，整个程序应具有两部分功能：查询和维护。现在面临的问题是如何将两部分功能集成在一起。查询和维

37、护功能的集成与程序的实际应用模式有关。程序的应用模式有两种：一种是一体模式，即查询和维护功能集中在一个应用界面下；另一种模式是分离模式，即查询和维护功能分别实现，且维护功能采用远程或“离线”方式对学生信息进行更新。由于第二种模式需要网络方面的知识，因此下面主要讨论一体模式。图1-24 程序的总体结构框架 图1-25 细化后的程序总体结构框架4模块设计在程序总体框架设计完成之后，需要对其中的每一个模块进行详细的设计，这个设计过程一般称为模块设计或函数设计。模块设计的重点是模块内的算法设计和数据结构设计。模块的算法设计是指为实现模块功能而设计的“计算”过程。例如，按姓名查询模块的核心算法是查找算法

38、。下面以修改模块为例说明算法设计的过程。修改模块实现修改学生信息的过程如下：(1)获取待修改的学生信息所对应的学号；(2)查找该学号所对应的学生信息；图1-26 修改学生信息流程图(3)修改学生信息；(4)确认修改；(5)保存修改后的信息。修改学生信息的流程图如图1-26所示。图1-26 修改学生信息流程图采用数组和链表表示学生信息各有其优点，但是从程序实现的简洁性考虑，应选择用链表表示学生信息，其数据结构可以定义为 图1-27 学生信息链表5程序实现在完成了程序结构设计和模块设计后，接下来的工作是实现程序，即通常意义下的编写程序代码。对编写程序代码有两个方面的要求：一是必须严格遵守语言的语法

39、规则使其能够正确运行；二是要求写出好程序。根据上述设计，我们采用C语言实现程序编写，编程环境采用VC+6.0。建立一个简单的Console Application程序，在此基础上改进。图1-28 建立Mystudent工程点击OK按钮，在选择A“Hello World!”Application.后，按OK就可以生成一个工程模板。该工程只完成在Console显示“Hello World!”。自动生成的代码如下所示：1)程序结构实现程序结构实现是指对程序结构设计的C语言描述。这是主要实现图1-25所示的程序结构框架。(1)实现main()函数。(2)实现Find()函数。(3)实现Maintain

40、()函数。2)数据结构实现根据程序设计中对数据结构设计的讨论，数据结构的实现如下：struct student char No6,name10,sex5,age4;char className10,address30,email20,QQ10,tel15;struct student*next;为了方便处理学生信息，将学生信息存储于链表中，即struct student*head;那么，所有对学生信息的操作，都是针对链表head的操作。3)模块实现/算法实现下面以按学号查询学生信息为例来说明算法设计。该算法采用链表上的查找算法，算法实现如下：6完整程序注：程序正确运行前，应事先建立两个文本文件

41、：FILE.DAT和superUser.DAT，分别存放学生信息和维护权限信息。上述程序中还有许多值得改进的地方，另外，程序中存放的学生信息内容(9项)少于问题中所要求的，请读者认真思考。第第2 2章章 线线 性性 表表2.1 线性表的基本概念及运算2.2 顺序表2.3 链表2.1 线性表的基本概念及运算线性表(Linear List)是最常用且最简单的一种数据结构。简单地讲，一个线性表是n个数据元素的有限序列(a1，a2，an)。至于一个数据元素ai的具体含义，在不同的情况下可以不同。例如，英文字母表(A，B，C，Z)是一个线性表，表中的每一个英文字母为一个数据元素。表2-1所示的学生成绩登

42、记表，是一个略为复杂一点的线性表的例子。例2-1 利用线性表的基本运算实现清除线性表中多余的重复结点。实现该运算的基本思想是：从表的第一个结点(i=1)开始，逐个检查i位置以后的任意位置j，若两个结点相同，则将位置j上的结点从表中删除；当j遍历了i后面的所有位置之后，i位置上的结点就成为当前表中没有重复值的结点，然后将i向后移动一个位置。重复上述过程，直至i移到当前表的最后一个位置为止。该运算可用如下形式的算法描述：2.2 顺 序 表在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表的元素。假设线性表的每个元素需占用c个存储单元，并以所占

43、第一个单元的存储地址作为数据元素的存储位置，如图2-1所示，则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)之间满足下列关系：Loc(ai+1)=Loc(ai)+c (2-1)图2-1 线性表顺序存储结构示意图一般来说，线性表的第i个元素ai的存储位置为Loc(ai)=Loc(a1)+(i1)c 1in (2-2)其中，Loc(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。由于C语言中的向量(一维数组)也是采用顺序存储表示，因此可以用向量这种数据类型来描述顺序表。2.2.1 顺序表的基本运算1.插入运算在线性表的

44、第i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表(a1，ai-1，ai，an)变成长度为n+1的线性表(a1，ai-1，x，ai，an)图 2-2 顺序表插入元素的过程下面我们给出一个完整的C程序，其中包括三个子函数：Create(建立顺序表)、Insert(插入元素)、Output(输出线性表)，并由主函数调用。2.删除运算线性表的删除运算是指将表的第i(1in)个结点ai删去，使长度为n的线性表(a1，ai-1，ai，ai+1，an)变成长度为n1的线性表(a1，ai-1，ai+1，an)可以看出，数据元素ai-1，ai，ai+1的逻辑关系发生了变化。为了在存储结构上反映这

45、个变化，同样需要移动元素，即若1in-1，则必须将顺序表中在位置i+1，i+2，n上的结点，依次前移到位置i，i+1，n-1上，以填补删除操作造成的空缺；若i=n，则只要简单地删除终端结点，而无须移动。其删除过程如图2-3所示。图2-3 顺序表删除元素的过程3.算法分析从上面两个算法可以看出，顺序表的插入与删除运算，其时间主要耗费在移动顺序表中的元素上，而所移动的元素个数不仅依赖于表长n，而且还与插入及删除的位置i有关。为了不失一般性，假设pi是在第i个位置上插入一个元素的概率，则在长度为n的线性表中插入一个元素须移动元素次数的期望值(平均次数)为 (2-3)EIS=)1i(npi1n1i 假

46、设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素须移动元素次数的期望值(平均次数)为 (2-4)EDE=)i(nqin1i 为了不失一般性，假设在线性表中任何位置上插入或删除元素的概率相等，则故 (2-5)(2-6)pi=1n1，qi=n1 故 EIS=故 EIS=2n)1i(n1n11n1i (2-5)EDE=(2-5)EDE=21n)i(nn1n1i 2.2.2 顺序表的应用实例学生学籍档案管理1问题描述及要求现有若干学生的学籍档案信息，要求编写一个应用软件对其进行日常管理，以实现学生档案信息的插入和删除，并能根据学生姓名查询。2数据结构我们将所有学生的档案信息存放在一个顺

47、序表中，其中的每个结点是一个学生的档案信息，并假设每个学生的数据包括以下内容：学号、姓名、性别、籍贯，则数据结构定义如下：3算法设计根据问题的要求，整个软件分成四个子模块：按姓名的字典顺序插入学生数据，数据的删除，按姓名查询，打印学生档案。其程序结构如图2-4所示。图2-4 程序结构示意图2.3 链 表链式存储是最常用的存储方法之一，它不仅可以用来表示线性表，而且还可以用来表示各种非线性的数据结构。本节将讨论几种用于存储线性表的链接方式：单链表、双链表和循环链表，统称为链表(Linked list)。2.3.1 单链表在顺序表中，我们是用一组地址连续的存储单元来依次存放线性表的结点，因此结点的

48、逻辑次序和物理次序一致。而链表是用一组任意的存储单元来存放线性表的元素，这组存储单元既可以是连续的，也可以是不连续的。因此，为了正确地表示元素间的逻辑关系，在存储每个元素值的同时，还必须存储指示其后继元素的地址(或位置)信息。这两部分信息组成数据元素的存储映像，即结点。它包括两个域，存储数据元素信息的域称做数据域；存储后继元素存储位置的域称做指针域。指针域中存储的信息称做指针或链。结点的结构为data next 图2-5 线性单链表示意图 图2-6 单链表的一般图示法单链表是由头指针唯一确定的，因此单链表可以用头指针的名字来命名。例如，若头指针名是head，则把链表称为表head。用C语言描述

49、单链表如下：实际上，以上定义的指针变量p所指向的结点变量是通过标准函数生成的，即p=malloc(sizeof(linklist)；图 2-7 指针变量p(其值是结点地址)和结点 变量p(其值是结点内容)的关系2.3.2 单链表的基本运算1单链表的建立1)头插法建表头插法建表是从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直至读入结束标志为止。例如，在空链表head中依次插入结点a、结点b、结点c之后，将结点d插入到当前链表的表头，其指针的修改情况如图2-8所示。其中序号表明了结点插入时的操作次序。其算法描述如下：图2-8 将新

50、结点s插入到单链表head的头上2)尾插法建表头插法建表虽然简单，但是生成的链表中结点的次序和输入的顺序相反。若希望两者次序一致，可利用尾插法建表。尾插法建表是将新结点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例如，在空链表head中插入结点a、结点b、结点c之后，将结点d插入到当前链表的表尾，其指针的修改情况如图2-9所示。图2-9 将新结点s插入到单链表head的尾上其中序号表明插入结点时的操作顺序。其算法描述如下：这种带有头结点的单链表如图2-10所示，其中，#部分表示头结点的数据域不存储信息，但是在有的应用中，可利用该域来存放表的长度等附加信息。图2