计算机软件技术基础

计算机软件技术基础

第一章软件工程1.1.1软件工程的形成与开展1.软件开展的三个阶段软件开发方法从机器语言编程到软件工程方法，经历了三个阶段。1.程序设计时期〔1946年到60年代中期〕生产方式是手工生产、个体劳动。只有程序，无软件的概念。2.软件时期〔60年代中期至70年代中期〕程序不再是硬件的附属，有软件的概念。作坊式的生产方式已难满足软件生产的质量和数量上的要求。出现了“软件危机〞。3.软件工程时期〔70年代至今〕1968年、1969年北大西洋公约组织成员国的软件工件者召开了两个研讨会，提出了“软件工程〞这一述语，根本目的在于克服“软件危机〞中所遇到的困难问题，从此进入软件工程时代。2.软件危机(1)软件危机的主要表现：软件开发本钱和进度的估计常常很不准确。用户往往对已完成的软件不满意。3)软件的质量常被疑心。4)软件极难维护。5)缺乏良好的软件文档。6)软件开发生产率提高的速度远远跟不上计算机应用迅速普及深入的趋势。1.1.2软件工程范型1、传统的软件工程范型――瀑布模型瀑布模型是1976年由B·W·Boehm提出的，是基于软件生存周期的一种范型。它将软件生存周期分为定义、开发、维护三个阶段，每个阶段又分为假设干个子阶段，各子阶段的工作顺序展开，如自上而下的瀑布。(见后图)定义阶段：分析用户需求。问题定义：收集、分析、理解、确定用户的要求。可行性研究：确定对问题是否有可行的解决方法。需求分析：确定用户对软件系统的全部需求。开发阶段：设计：设计软件系统的模块层次结构、数据库结构、模块控制流程等。编程：将每个模块的控制流程纺出相应的程序。测试：检查并排除软件中的错误，提高软件的可靠性。维护阶段：运行与维护：维护软件系统的正常运行。各个阶段确均有相应的文档。问题定义或行性研究需求分析设计编程测试运行与维护〔目标与范围说明〕〔可行性论证报告〕〔需求说明书〕〔设计文档〕〔程序〕〔测试报告〕〔维护报告〕定义阶段开发阶段维护阶段传统的软件工程范型――瀑布模型1.2软件开发方法两种不同的开发方法：结构化开发方法和面向对象的开发方法。1.2.1结构化开发方法一、结构化分析1.结构化分析方法，亦称SA〔StructuredAnalysis〕方法。(1)SA方法的特点：①核心思想：自顶向下和逐步求精。②根本手段：分解和抽象。分解：把大问题分割成假设干小问题，然后分别解决。抽象：略去细节，先考虑问题最本质的属性。③使用了描述需求说明书的几个标准工具。即数据流图、数据词典、小说明〔加工逻辑的描述〕等，使文档标准化。(2)数据流图〔DataFlowDiagram，简称DFD图〕SA方法采用“分解〞的方法来描述一个复杂的系统，数据流图是描述系统中数据流程的图形工具，它标识了一个系统的逻辑输入和逻辑输出以及把逻辑输入转换为逻辑输出所需要的加工处理。1

数据流图的根本符号：(1)数据流(2)加工(3)数据存储(4)数据源点或终点。画各层数据流图应注意的问题：(1)父图和子图平衡(2)子图的编号(3)数据守恒(3)数据词典〔DataDictionary，简称DD〕对数据流图中包含的所有元素的定义的集合构成了数据字典。数据词典中有四种类型的条目：数据流、文件、数据项和加工。〔1〕数据流条目数据流条目给出某个数据流的定义，它通常是列出该数据流的各组成数据项。如：课程=课程名+教员+教材+课程表课程表={星期几+第几节+教室}〔2〕文件条目文件条目给出某个文件的定义。订单文件=订单编号+顾客名称+产品名称+订货数量+交货日期〔3〕数据项条目数据项条目给出某个数据单项的定义。学号编号=1～9999〔4〕加工条目加工条目又称小说明。小说明中应精确地描述用户要求某个加工做什么。2、结构化设计结构化设计方法，亦称SD〔StructuredDesign〕方法。是一种面向数据流的设计方法，目的在于确定软件的结构。(1)SD方法的根本思想其根本思想是：根据SA方法中的数据流图建立一个良好的模块结构图〔例如SC图或软件层次方框图〕；运用模块化的设计原理控制系统的复杂性，即设计出模块相对独立的，模块结构图深度、宽度都适当的，单入口单出口的，单一功能的模块结构的软件结构图或软件层次方框图。此方法提供了描述软件系统的工具，提出了评价模块结构图质量的标准，即模块之间的联系越松散越好，而模块内各成分之间的联系越紧凑越好。(2)SD方法的设计原理1〕模块化:模块化就是把系统划分为假设干个模块，从而获得满足问题需要的一个解的过程。2〕模块的独立性:模块独立性有两个定性的度量标准，即内聚和耦合。耦合有六种，从小到大如下：①两个模块完全独立〔没有任何联系〕；②数据耦合:即两个模块只通过数据进行交换；③状态耦合:即两个模块之间通过控制状态进行传递；④环境耦合:即两个模块之间通过公共环境进行数据存取；⑤公共块耦合:即多个模块引用一个全程数据区；⑥内容耦合:即一个模块使用保存在另一模块内部的数据或控制信息，或转移进入另一个模块中间时，或一个模块有多个入口时。由此看出模块间耦合性越小越好。内聚有六种，从小到大如下：①偶然内聚，即一个模块由多任务组成，这些任务之间关系松散或根本没联系；②逻辑内聚:即一个模块完成的任务在逻辑上相同或相似；③时间内聚:即一个模块所包含的任务必须在同一时间内执行；④通信内聚:即一个模块内所有处理元素集中于相同的数据结构；⑤顺序内聚:即一个模块中所有处理元素都是为完成同一功能而且必须顺序执行；⑥功能内聚:一个模块所有处理都完成一个而且仅完成一个功能。内聚性给出模块的内在联系，因此内聚性越大越好。3〕模块的设计准那么①通过模块的分解和合并，提高模块的独立性；②模块调用个数最好不要超过五个；③降低模块接口的复杂性；④一个模块的所有下属模块应该包括该模块受某一判定影响的所有模块的集合；⑤模块应设计成单入口和单出口；⑥模块的大小要适中，一般在50句左右。(3)数据流图的类型数据流图通常分为两大类型:转换处理型和事务处理型.转换处理型:由于大多数数据流图都可看成是对输入数据进行转换而得到输出数据的处理，因此可把这类处理抽象为转换处理型。转换处理过程大致分为输入数据，变换数据和输出数据三步；它包含的数据流有输入流、转换流、输出流三个局部。在输入流中，信息由外部形式转换为内部形式的结果；在输出流中，信息由内部形式的结果转换为外部形式数据流出系统。转换处理型的数据流图。事务处理型:另一类数据流图可看成是对一个数据流经过某种加工后，按加工的结果选择一个输出数据流继续执行的处理。这种类型的处理可以抽象为事务处理型。在事务处理中，输入数据流称为事务流，加工称为事务中心，假设干平行数据流称为事务路径。当事务流中的事务送到事务中心后，事务中心分析每一事务，根据事务处理的特点和性质选择一个事务路径继续进行处理。(4)SD方法的设计过程使用SD方法的根底是数据流图。正如前面所述，几乎所有软件在分析阶段都可以表示为数据流图，所以SD方法根本上可适用于任何软件的开发工作。用SD方法进行总体设计的过程大致如下：〔1〕研究、分析和审查数据流图，从软件的需求说明书弄清楚数据流加工的过程；〔2〕根据数据流图确定数据流图的类型；〔3〕从数据流图导出系统的初始软件结构图；〔4〕改进初始软件结构图，直到符合要求为止；〔5〕复查。(5)软件结构的描述方式在SD方法中，软件结构用一种结构图来描述，它是设计说明书的一局部。结构图描述了软件模块结构，并反映了模块和模块间联系等特性。3、详细设计和编码(1)详细设计的任务为软件结构图中的每一个模块确定采用的算法和块内数据结构，用某种选定的表达工具给出清晰的描述。(2)详细设计的描述工具①程序流程图也称为程序框图，独立于任何一种程序设计语言，比较直观、清晰、易于掌握。任何复杂的程序流程图都可以由以下不同类型的根本结构组合或嵌套而成：顺序结构选择结构(IF-THEN-ELSE)多分支选择结构(CASE)先判定循环结构(WHILE)后判定循环结构(UNTIL)(2)方框图〔N-S图〕：图形描述工具。限制了随意的控制转移。顺序结构选择结构多分支选择结构先判定型循环结构后判定型循环结构(3)结构化编码方法①对源程序的编码要求:最根本要求是源程序的正确性，同时还要考虑其可读性、可理解性、可测试性和可维护性。②写程序的风格:一个好的源程序意味着源程序代码逻辑简明清晰，易读易懂。编码原那么：程序内部文档应选取含义鲜明的名字，注解正确，程序清单层次清晰，布局合理。数据说明和次序应该标准化，个别复杂的数据结构应加注释。每个语句应该简单直接，不能为提高效率而使程序变得过份复杂。对输入数据应进行合法性检查；对输出数据要加输出数据的标志。在程序编码阶段以不影响程序的清晰度和可读性为前提，尽可能提高效率。1、面向对象分析〔OOA〕把对象作为现实世界的抽象表示，然后定义对象的属性和专门操纵那些属性的效劳，属性和效劳被看成对象的特征。具有相同的属性和效劳抽象的一系列对象组成类。因此在面向对象模型中，它可以包含假设干类，并且它对应于模型的不同层次，因此这些类有一定的层次关系和属性继承关系。面向对象分析由五个主要步骤构成：(1)标识对象(2)标识对象属性(3)定义对象的效劳(4)识别对象所属的类(5)定义主题2、面向对象的设计〔OOD〕OOA是一个分类活动，而OOD模型由主体部件、用户界面部件、任务管理部件和数据管理部件四局部构成。每个部件又由主题词、对象及类、结构、属性和外部效劳五层组成，它们分别对应OOA中的五个活动：定义主题词、标识对象、标识类、标识对象的属性和标识对象的效劳。其中主体部件是整个设计的主体，它包括完成目标软件系统主要功能的所有对象，用户界面部件给出人机交互需要的对象，任务管理部件提供协调和管理目标软件各个任务的对象，数据管理部件定义专用对象。要将目标软件系统中依赖于开发平台的数据存取操作与其他功能分开，以提高对象独立性。概括地说，OOD方法是以OOA模型为根底，不断填入和扩展有关软件设计的信息。3、面向对象编程完成OOD以后，将开始进入编程阶段。目前主要选取面向对象语言(如C++)、基于对象的语言(如Ada)、过程式语言(如C语言)。1.3软件测试与质量保证1.3.1软件测试原那么1、根本概念软件测试定义:软件测试是为了发现错误而执行程序的过程。软件测试分为：单元测试和综合测试。软件测试在软件生存周期中横跨了两个阶段：通常在编写出第一个模块之后就对它做必要的测试〔称作单元测试〕。编码与单元测试属于软件生存周期中的同一阶段。在结束这个阶段之后，对软件系统还要进行各种综合测试，这是软件生存周期的另一个独立的阶段，即测试阶段。2、目标和原那么软件测试的目标可以归纳为以下几点：1.测试是为了发现软件中的错误而去运行软件的过程。2.好的测试方案是尽可能地发现至今尚未发现的错误的测试方案。3.成功的测试那么是发现出至今未发现的错误的测试。1.单元测试〔模块测试〕目的是发现模块的子程序或过程的实际功能与该模块的功能和接口描述是否相符，以及是否有编码错误存在。单元测试的主要内容有:模块接口测试；局部数据结构测试；重要路径测试；出错处理能力测试；边界条件测试.2.组装测试〔集成测试或联合测试〕它的测试目的是为了发现程序结构的错误。组装测试过程中的模块组织方式有非渐增式和渐增式两种。①非渐增式组装测试：又称一次性组装方式或整体拼装。测试方式是先对每个模块分别进行测试。然后再把所以模块组装在一起整体测试。其优点是对各模块的测试可以并行进行，有利于充分利用人力，加快测试速度。其缺点是由于程序中不可防止的地存在涉及模块间接口、全局数据结构等方面的问题，所以一次试运行成功的可能性不大，结果是发现有错误，但却找不到错误的产生原因。②渐增式组装测试这种方式是对一个个模块进行模块调试，然后将这些模块逐步组装成较大的系统。在组装过程中，每连接一个模块便进行一次测试，直到把所有模块集成为一个整体并进行测试，那么软件的组装测试完成。在渐增测试过程中，将模块结合起来的策略有两种：自底向上测试和自顶向下测试。自底向上测试：从程序模块结构的最低层模块进行组装和测试。因为模块是自底向上进行组装的，对给定层次的模块的下层模块处理功能总可以得到，所以这种测试策略不必设计桩模块〔存根模块〕，但要设计驱动模块。自顶向下测试：将模块按系统程序结构，沿控制层次自顶向下进行组装。由主控模块开始，按照程序的层次结构向下移动。逐渐把各个模块组装起来。(3)确认测试(有效性测试)又称有效性测试。组装测试结束后，得到的是一个完整的软件系统。这时需要进行最后的测试，即有效性测试。有效性测试阶段主要进行的测试有：有效性测试〔黑盒测试〕、软件配置复查、α测试和β测试以及验收测试。(4)系统测试系统测试是指将经过测试后的软件系统与计算机硬件、外设、其他支持软件以及其他系统元素一起进行测试。测试内容主要有：功能测试、吞吐量测试、可用性测试、保密性测试、安装测试、可恢复性测试、资料测试和程序测试。2、常用的测试方法常用的测试方法有黑盒测试和白盒测试两种。(1)白盒测试白盒测试又称结构测试或逻辑驱动测试。所谓“白盒〞是指将对象看作一个翻开的盒子，测试人员可利用程序内部的逻辑结构及有关的信息来设计或选择测试用例。白盒测试主要考虑的是测试用例对程序内部逻辑的覆盖程度，而不考虑程序的功能。测试用例对程序的覆盖程序从低到高分别为：语句覆盖、判定覆盖、条件覆盖、判定/条件覆盖、条件组合覆盖。需要说明的是，上述各种覆盖准那么的侧重点不同，覆盖程度也不同。但它们共同的是：任何一种覆盖都不能做到完全测试。(2)黑盒测试黑盒测试又称功能测试或数据驱动测试。在这种测试方法中，程序对测试者是完全透明的。测试者不考虑程序的内部结构和特性，就好似把程序看作一个不能翻开的盒子，只根据程序的需求规格说明中的程序功能或程序的外部特性来设计测试用例。黑盒测试的方法包括：等价分类法、边缘值分析法、因果图法和错误推测法。测试方法还有回归测试、强度测试等等。每一种测试方法都各有所长，在实际测试中应综合使用。一般来讲，通常用黑盒法设计根本的测试方案，再利用白盒法做必要的补充。2．支持重用的环境从过程重用的观点，以下10种软件过程产物均可以重用：①工程方案②费用估算③体系结构④需求模型和规格说明⑤设计⑥源代码⑦各种文档⑧人机界面⑨测试用例⑩数据这些产物作为重用件要作分类、标记，作为对象构件放入构件库。在当今CIS分布系统上，构件库是一个数据库效劳器，它提供访问效劳。重用环境还必须提供集成工具，使重用的构件能集成到新工程中。1.5软件开发环境软件开发由来已久。一台宿主机，一个编译〔或汇编〕程序，加上编辑、链接、装入等少量实用程序，就构成了早期软件开发的舞台。从这个意义上讲，在软件工程兴起之前就有了软件开发环境。在70年代和80年代初期，开发环境常被称为“软件工程环境〞〔简称SEE或SE2〕或“程序设计支撑环境〞。“计算机辅助软件工程〞〔简称CASE〕，是今天对开发环境最流行的称呼。成为描述软件开发环境与工具的最通用的名称。另一个常见的名称——“工作台〞〔workshop〕。1976年，ICSE第二届会议在一篇文章中发表了一个基于UNIX操作系统的程序设计支撑环境，称之为“UNIX程序员工作台〞〔UNIXprogrammer’sworkbench，简写为UNIX/PWB〕。这是国际上出现的第一个有影响的软件开发环境。自此之后，工作台也常被用作开发环境的同义词。2．集成化工具开发软件用到两类工具。一类工具是画或写在纸上的，包括在不同阶段使用的各种图形与语言；另一类那么是用来“开发软件的软件〞，又称为“软件工具〞或CASE工具。这里讨论的是后一类工具。早期的环境只配置用于编码阶段的工具，也称为“低层〞CASE工具。今天在软件分析和总体设计等阶段也有了许多支持开发的工具，即“高层〞CASE工具。70年代出现了“工具箱〞能局部地实现从一个工具到另一个工具的切换。今天，高、低层CASE工具由一组专用程序和一个用来支持工具间数据交换的环境信息库构成的支持下，共同构成了具有统一的用户界面、并能自动实现工具切换的“集成工具〞，对软件开发的自动化提供了有力的支持。CASE环境还可能包括另两个层次。一个是环境体系结构，用于区分开发环境为单机环境或网络环境；另一个是可移植性效劳程序，它介于集成工具与宿主机之间，使集成后的CASE工具不需要作重大的修改即可与环境的软、硬件平台适应。软件设计可分为总体设计和详细设计。总体设计通常使用结构化设计方法。详细设计是根据结构化程序设计原那么进行的，只使用顺序、分支、重复三种结构来设计模块的控制流程，使用的表示工具有程序流程图、方框图、PAD图、伪码〔PDL语言〕等。软件编程的任务是将软件详细设计的结果转换成某种程序设计语言编写的源程序。面向对象的方法是在结构化程序设计的根底上，进一步力图用更自然的方法反映客观世界。在面向对象的系统中，将数据和使用该数据的一组根本操作或过程封装在一起，用“对象〞这个概念来完整地反映客观事物的静态属性和动态属性。“面向对象〞的根本思想就是把要构造的系统表示为对象的集合。第二章数据结构概述

随着计算机应用领域的不断扩大，非数值数据的处理变得尤为重要，这些数据的元素之间在多是相互有关的。因此，讨论数据元素之间的逻辑关系、数据元素在计算机中的存储方式及在数据元素集合上设立的运算如何实现，这是研究数据处理的根底。本章在介绍数据结构的有关概念后，着重讨论线性结构、树型结构和图形结构等三类数据结构，最后介绍数据结构中两种特别重要的运算-查找和排序。对数据结构的根本操作，本章采用C语言描述。2.1概述2.2线性表2.3树型结构2.4图2.5查找2.6排序小结2.1概述计算机早期运算:原始数据和结果数据不多,重点在于算法。计算机应用的开展:逐渐变成对数据进行非数值型的加工处理为主。特点是数据量大，而计算的工作量可能很小。数据结构的提出：数据结构是为研究和解决诸如数据的分类与查找、情报检索、数据库、企业管理、系统工程、图形识别、人工智能以及日常生活等各领域的非数值问题而提出的理论与方法，即如何合理的组织数据，以提高算法的效率。重要性：对实现系统软件，如操作系统、编译程序和数据库管理系统等均有十分重要的意义。2.1.1数据结构的概念数据：描述客观事物的的信息〔数，字符，符号等〕的集合，是程序处理的对象。数据元素：是数据集合中的个体，是构成数据对象的根本单位，可由假设干个数据项组成。数据项：是数据的最小单位。一组数据元素具有某种结构形式。数据结构：就是描述一组数据元素及元素间的相互关系的。数据结构描述了一组性质相同的数据元素及元素间的相互关系。用集合论给出的数据结构的定义为:数据结构S是一个二元组：S=(D,R)。其中:D是一个数据元素的非空的有限集合。R是定义在D上的关系的非空的有限集合数据结构概念一般包括三个方面的内容：数据元素之间的逻辑关系、数据元素在计算机中的存储方式以及在这些数据元素上定义的运算的集合。2.1.2数据的逻辑结构数据的逻辑结构有时可直接称为数据结构。数据的逻辑结构的三种根本类型：线性表、树和图。分别属于两大类：(一)线性结构〔线性表〕各数据元素之间的逻辑关系可以用一个线性序列简单地表示出来。线性表是典型的线性结构，它的数据元素只按先后次序联接。有栈、队列、字串、数组和文件。(二〕非线性结构〔树，图〕不满足线性结构特点的数据结构称为非线性结构。树、图等是非线性结构。树中的数据元素是分层次的纵向联接。图中的数据元素那么有各种各样复杂联接。其它种类的数据结构由这三种根本结构派生的。2.1.3数据的物理结构数据的逻辑结构在计算机存储设备中的映象称为数据的存储结构(亦称为物理结构)。同一个逻辑结构可以有不同的存储结构。最常用的二种方式是：

顺序存储结构和链接存储结构。大多数据结构的存储表示都采用其中的一种方式或两种方式的结合。1.顺序存储结构数据结构的数据元素按某种顺序存放在存储器的连续单元中。即将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，而数据元素之间的关系由存储单元的邻接关系唯一确定。假设数据元素存放在以起始地址S开始的连续存储单元中。那么第i个元素的存储地址：LOC(i)=LOC(1)+(i-1)*l=S+(i-1)*l假定每个元素所占的存储空间是相同的,长度均为l。数据的这种顺序存储结构叫做向量，以V表示，向量V的分量V[i]是数据结构的第i个元素在存储器中的映像。顺序存储的主要特点是：1.结点中只有自身信息域，没有连接信息域。因此存储密度大，存储空间利用率高；2.可以通过计算直接确定数据结构中第i个结点的存储地址L。即可以对记录直接进行存取；3.插入、删除运算会引起大量结点的移动；4.要求存储在一片连续的地址中。这种存储方式主要用于线性的数据结构。2.链接存储结构存储数据结构的存储空间可以不连续，而数据元素之间的关系是由指针来确定的。主要特点是：〔1〕结点由两类域组成：数据域和指针域。〔2〕逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。〔3〕插入，删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。2.1.4数据结构的运算对一些典型数据结构中的结点进行操作处理。1.插入:在数据结构中的指定位置上插入新的数据元素；2.删除:根据一定的条件,将某个结点从数据结构中删除；3.更新:更新数据结构中某个指定结点的值；4.检索:在给定的数据结构中,找出满足一定条件的结点来，条件可以是某个或几个数据项的值；5.排序:根据某一给定的条件，将数据结构中所有的结点重新排列顺序等。从操作的特性来看，所有这些运算的操作可以分为二类:一类是加工型操作：操作改变了存储结构的值〔如插入、删除、更新等〕；另一类是引用操作：操作只是查询或求得结点的值〔如检索等〕。2.2线性表——最简单，最常用的一种数据结构2.2.1线性表线性是指表中的每个元素呈线性关系，即除第一个外，都有一个直接前趋(predecessor)，同时除最后一个元素外，都仅有一个直接后继(successor)。1.线性表的逻辑结构线性表L用符号表示为：L=(a1，a2，a3，..ai...，an)线性表也可以正式定义为：假设数据结构L=〔D，R〕是一个线性表，那么：D是包括a1,a2,a3.....an等元素的集合。R中只包含一个关系，即R={<ai-1,ai>|ai-1，ai∈D，2≤i≤n}。关系<ai-1,ai>给出了元素的一种先后次序。a1称为表的线性起始结点，an为表的终结点。2.线性表的存储结构存储结构:顺序存储结构和链接存储结构。具有顺序存储结构的线性表称为顺序表，即用一组地址连续的存储单元依次存储线性表中的每个数据元素。具有链接存储结构的线性表称为线性链表。链式存储结构是用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。常用的链表有单链表、循环链表和双向链表。3.线性表的根本运算常用的操作有:插入、删除、修改、读值、检索和排序等。线性表还可以进行一些更为复杂的操作。如将两个或两个以上的具有相同数据对象的线性表合并成一个线性表，将一个线性表拆成假设干个线性表，复制一个线性表等等。这些较为复杂的操作都可以利用上述几种常用的操作来实现。(1)顺序表的操作顺序表在各种高级语言里经常用一维数组实现。#defineMAXSIZE100//数组中元素个数的最大值intlist[MAXSIZE],n;//n为线性表中当前的结点数①插入运算插入运算是在线性表的第i个元素和第i+1个元素之间插入一个一个新元素x。

为了实现这个操作，必须把第i+1个元素到第n个元素依次向后移位一个位置，以便把第i+1个存储位置让出来，存储新元素X。

假定已有一个数组,其值是由小到大排列的,现插入一个新的结点p0,要求插入后仍能保持由小到大的顺序。#defineN20inta[N]；main(){inti,data,n=10;for(i=0;i<n-1;i++)scanf(“%d〞,&a[i]);scanf(“%d〞,&data);insert(a,n,data);for(i=0;i<n;i++)printf(“%3d〞,a[i]);}insert(inta[],intn,intdata){inti;if(a[n-1]<data)a[n]=data;else{a[n]=a[n-1];for(i=n-1;i>0;i--)if(a[i-1]>data)a[i]=a[i-1];else{a[i]=data;break;}if(i==0)a[0]=data;}}

当i=0时,新结点x插在a1之前,这时需移动线性表中的所有元素。

当i=n-1时,新结点x插入在an-1之后,这时不需移动线性表中的元素。

在具有n个结点的线性表中，插入一个新结点时，其执行时间主要化费在移动结点的循环上。移动结点的平均次数为：②删除运算线性表的删除运算是指将线性表中第i个数据元素除掉，即把长度为n的线性表〔a1,a2,...ai-1,ai,ai+1,...an)中的ai除去,变成长度为n-1的线性表〔a1,a2,...ai-1,ai+1,...an)。这只需将第i+1数据元素到n数据元素依次向前移动一个位置即可。设线性表用一维数组a(N)存放，那么在长度为n的线性表中删除值为data元素.函数如下：intdelete(inta[],intn,intdata){inti,j,k=0;for(i=0;i<n;i++)if(a[i]==data){for(j=i;j<n-1;j++)a[j]=a[j+1];/*数据元素依次向前移动*/a[n-1]=0;n--;k=1;break;}if(k==0)printf("Nothiselement!");return(n);}head..............an0a0a1a2(2)线性链表的操作单链表结点一般用结构体说明如下：structnode{intdata;structnode*next;};

①单链表的插入假定已有一个链表的表头为h,其data域的值是由小到大排列的,现插入一个新的结点p0,要求插入后仍能保持由小到大的顺序.考虑:1.链表h假设为空，那么将p0的next值为NULL，并将h指向p0。2.链表h不是空表，那么首先确定p0的插入位置。那么分三种情况:①p0插在第一个结点之前：将p0的next指向h的第一个结点，然后将h指向p0。②p0插在链表中间：假设在ai-1和ai之间插入,可将p0的next指向ai;ai-1的next指向p0.③p0插在链表的末尾：将最后一个结点的next指向p0，而使p0的next置为NULL。......p2p1p0structnode*insert(structnode*h,structnode*p0){structnode*p1=h,*p2;if(h==NULL){h=p0;p0->next=NULL;}else{while((p0->data>p1->data)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p0->data<=p1->data){if(h==p1)h=p0;elsep2->next=p0;p0->next=p1;}else{p1->next=p0;p0->next=NULL;}}return(h);}②单链表的删除在已给定的链表h中,删除data值为m的结点。1.链表h是否指向空表,如果是空表,那么报告空表信息。2.假设h不为空:①一直查到表尾还找不到该结点,那么在此链表中无此结点。②查找到该结点:假设该结点在头部,那么h指向该结点的下一个结点。假设该结点在中部,那么前趋结点的指针指向后趋结点。假设该结点在尾部,那么前趋结点的指针为NULL。p2p1structnode*del(structnode*h,intm){structnode*p1,*p2;if(h==NULL){printf("\nThisnull!\n");return(h);}p1=h;while((p1->data!=m)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p1->data==m){if(p1==h)h=p1->next;elsep2->next=p1->next;free(p1);}elseprintf("%dnodbeedfound!\n",m);return(h);}实例：单链表的建立、打印和插入：#defineNULL0#defineLENsizeof(structnode)#include"stdio.h"structnode{intdata;structnode*next;};structnode*create()/*建立链表*/{structnode*h=NULL,*p,*q;intx;for(;;){printf("Inputdata:");scanf("%d",&x);if(x<0)break;p=(structnode*)malloc(LEN);p->data=x;if(h==NULL)h=p;elseq->next=p;q=p;}if(h!=NULL)p->next=NULL;return(h);}voidprint(structnode*h){structnode*p=h;while(p!=NULL){printf("%d\n",p->data);p=p->next;}}structnode*insert(structnode*h,structnode*p0){structnode*p1=h,*p2;if(h==NULL){h=p0;p0->next=NULL;}else{while((p0->data>p1->data)&&(p1->next!=NULL)){p2=p1;p1=p1->next;}if(p0->data<=p1->data){if(h==p1)h=p0;elsep2->next=p0;p0->next=p1;}else{p1->next=p0;p0->next=NULL;}}return(h);}main(){structnode*h,*p;intx;h=create();print(h);p=(structnode*)malloc(LEN);scanf("%d",&x);p->data=x;h=insert(h,p);print(h);}二.循环链表〔1〕循环链表的最后一个结点的指针域不为NULL，而是指向头结点，整个链表形成一个环。〔2〕在循环链表中设置一个表头结点，使空表与非空表的运算统一起来。(a)非空表(b)空表图2-2-5带表头结点的循环链表〔1〕插入算法：在头指针为h的循环链表中元素b的结点前插入新元素a.structnode*inscst(structnode*h,intb,inta){structnode*q,*p;q=(structnode*)malloc(LEN);q->data=a;p=h;

while((p->next!=h)&&((p->next)->data!=b))p=p->next;/*寻找指定元素的前一结点*/q->next=p->next;p->next=q;return(h);}hpqba(2)删除算法：在头指针为h的循环链表中删除元素为b的结点delcst(structnode*h,intb){structnode*p,*q;p=h;while((p->next!=h)&&((p->next)->data!=b))p=p->next;/*寻找指定元素的前一结点*/if(p->next==h){printf(“Nothisnodeinthelist\n〞);return(h);}q=p->next;p->next=q->next;free(q);return(h);}bpq三.多项式相加A(x)=3x14+2x8+1B(x)=8x14-3x10+10x6C(x)=A(x)+B(x)

设pa,pb指针〔1〕假设指针相等，那么系数相加，c(x)中建项〔系数为0，不建〕〔2〕假设pa->exp>pb->exp复抄pa所指项，反之，复抄pb所指项。-13142810ah-1814-310106bhcofexpch-11411-3102810610papbpcstructnode1*addpoly(structnode1*ah,structnode1*bh){structnode1*pa,*pb,*pc,*ch,*pp;intx,e;ch=(structnode1*)malloc(LEN);ch->exp=-1;ch->next=ch;pc=ch;/*建立新表头结点*/pa=ah->next;pb=bh->next;while((pa->exp!=-1)||(pb->exp!=-1)){if(pa->exp==pb->exp){x=pa->cof+pb->cof;e=pa->exp;/*系数相加*/pa=pa->next;pb=pb->next；/*修改指针*/}elseif(pa->exp>pb->exp){x=pa->cof;e=pa->exp;/*复抄A(x)*/pa=pa->next;}else{x=pb->cof;e=pb->exp;/*复抄B(x)*/pb=pb->next;}if(x!=0)/*形成新结点链入C(x)*/{pp=(structnode1*)malloc(LEN);pp->cof=x;pp->exp=e;pp->next=ch;pc->next=pp;pc=pp;}}return(ch);}

多重链表:每个结点均有两个或两个以上指针的链表。双重链表设两个指针域：一个指向后继结点，另一个指向前趋结点。 structnode{intdata;structnode*prio;structnode*next;}

图2-2-6带表头结点的双向循环链表a.插入运算在已由小到大排列的带表头结点的双向循环链表h中，插入一个新的结点p0插入后，要求仍保持由小到大的排列次序。structnode*insert2(structnode*h,structnode*p0){structnode*p1p1=h->next;while((p0->data>p1->data)&&(p1!=h))p1=p1->next;p0->prio=p1->prio;p1->prio->next=p0;p0->next=p1;p1->prio=p0;return(h);}p0p1hb.删除操作在已给定的头结点h的双向链表中，删除一个data值为m的结点。structnode*data(structnode*h,intm){structnode*p1；p1=h->next;while((p1->data!=m)&&(p1!=h))p1=p1->next;if(p1->data==m){p1->prio->next=p1->next;p1->next->prio=p1->prio;free(p1);}elseprintf(“%dnotbeenfound!\n〞,m);return(h);}hmp12.2.2栈栈是限定在一端进行插入与删除的线性表。允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。例如，给定栈(a0,a1,…,an-1〕称a0为栈底元素，an-1为栈顶元素。栈是一种后进先出(LIFO--LastInFirstOut)或先进后出〔FILO)的线性表。在栈中，元素的插入称为进栈，元素的删除称为出栈。1.顺序存储的栈顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设指针top指示栈顶元素的当前位置。假设用一维数组s[max]表示栈，指针top指向栈顶元素.s[0]为最早进入栈的元素，s[top]为最迟进入栈的元素。当top=max-1时，为满栈.初始化top=-1注：top,max为全局变量〔1〕进栈push(ints[],intx){if(top==max-1)printf(“Stackoverflow!\n〞);/*上溢*/elses[++top]=x;}〔2〕出栈intpop(ints[]){inty=-1;if(top==-1)printf(“Stackunderflow!\n〞);/*下溢*/elsey=s[top--];return(y);}图2-2-8数据元素和栈顶指针之间的对应关系假设有两个栈，我们让它们共享一数组s[m]，因为栈底位置是不变动的，所以可将两个栈底分别设在数组空间的两端，然后各自向中间伸展(如以下图所示)，显然，仅当两个栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺，使得每个栈实际可利用的最大空间大于m/2。2.链存储的栈当栈的最大容量事先不能估计时，也可采用链式存储结构的栈，称为链栈。一个链栈由它的栈顶指针top唯一确定。如图2.11所示。这里栈空的判别条件是top是否为NULL，而栈满将不会发生,除非计算机的全部可利用空间都被占满。对一个元素多变的栈来说，链式存储结构似乎更适宜。栈链的运算实现也比较简单。计算表达式运算符:**/*+-X=A*(B+C/D)-E*F**G优先数:43322ABCDOptrOpnd(a)进栈后*〔+/ABT1*(+(b)T1=C/DAT2*((c)T2=B+T1AT2*(d)弹出左括号T3(e)T3=A*T2T3EFG_***(f)进栈后T3ET4_*(g)T4=F**GT3T5_(h)T5=E*T4T6(i)T6=T3_T5求表达式3*〔7-2〕的值。optropnd输入字符主要操作1#3*〔7-2〕#push(opnd,3)2#3*〔7-2〕#push(optr,’*’)3#*3〔7-2〕#push(optr,’(’)4#*(37-2〕#push(opnd,7)5#*(37-2〕#push(optr,’-’)6#*(-372〕#push(opnd,2)7#*(-372〕#operate(‘7’,’-’,’2’)8#*(35)#pop(optr)&&一对〔〕出栈9#*35#operate(’3’,’*’,’5’)10#15#return2.2.3队列队列〔Queue〕也是操作受限的线性表.队列是一种先进先出(FIFO)的线性表.(a1,a2,…,an)允许在表的一端进行插入，而在表的另一端进行删除，允许插入的一端叫做队尾〔rear〕，允许删除的一端那么称队头〔front〕。假设限制插入和删除能在表的两端进行，称此队列为“双向队〞。假设限制插入在表的一端进行，而限制删除在表的另一端进行,称此队列为“单向队〞。允许插入的一端称为队尾，允许删除的一端称为队首。队列是一种先进先出〔FIFO)的线性表。队列的根本运算有以下四种:①获得队列的队首结点之值：gethead(q,x)；读取q队列的队头元素于变量x中,队列不变。②队列q中插入一个结点：(进队)add(q,x)；在队尾插入一个元素x。③队列q中删除一个结点：〔出队〕del(q)；删除队头元素。④判队列q是否为空：empty(q)；假设存储空间为数组q[m]，把队列数组的元素q[0]和q[m-1]连接起来，形成一个环形的表。初始值front=rear=0〔1〕进队rear=(rear+1)%m;q[rear]=x;出队front=(front+1)%m;y=q[front];01m-1frontreara1a2a3a4(2)环形队列的队空和队满都有rear==front专门设立一个标志符少用一个元素空间，用(rear+1)/m==front作为队满的判别条件循环队列中入队和出队操作的具体算法intfront,rear,m;/*全局变量*/addque(intq[],intx)/*进队算法*/{rear=(rear+1)%m;if(rear==front)printf("Queenoverflow!\n");elseq[rear]=x;}delque(intq[])/*出队算法*/{inty=-1;if(front==rear)printf("Queenundelflow!\n");else{front=(front+1)%m;y=q[front];}return(y);}2．链接存储的队采用链式存储结构的队列称为链队列。一个链队列需要队头和队尾的两个指针才能唯一确定。b.链式存储的队列(1)进队算法注：front,rear是全局变量

add(intx){structnode*q;q=(structnode*)malloc(LEN);q->data=x;q->next=NULL;if(front==NULL){front=q;rear=q;}else{rear->next=q;rear=q;}}(2)出队算法注：front,rear是全局变量del(){structnode*q;inty=-1;if(front==NULL)printf(“Queennderflow!\n〞);else{q=front;y=q->data;front=q->next;free(q);}return(y);}2.2.4串串(String)也是一种特殊的线性表，即当线性表中的元素为字符时的情形。串定义：由零个或多个字符组成的有限序列，称为串。一般记为：s=’a1a2…an’(n>=0)线性表上的操作通常是对其中的单个元素进行的，如插入一个元素，删除一个元素等。对于串，经常要对其连续的字符组进行操作，如从正文中取一个单词，替换一个单词等。串的根本运算有：求串s的长度的函数len(s)；求串s的第m位置开始且长度为n的子串的函数sub(s,m,n)；求子串t在主串s中的位置的函数index(s,t)；串v的值替换所有在串s中出现的子串t的值的函数rep(s,t,v)及将串s2的值紧接着放在串s1的值的末尾，联接成一个新串的函数concat(s1,s2)等。1.串的顺序存储用一组地址连续的存储单元来存放字符串的值。为了唯一确定串，需要设置两个变量，一个是指向串第一个字符位置的指针sp，一个是指示串长度的整型变量sl。可以将串的长度和串值一起存于内存，也可以用一个特定字符作为串结束标志和串值一起存放，这样就不需要设置sl了。C语言就是用NULL(‘\0’)作为串结束标志的。不同的字符所占据的内存空间都是一个字节c o m p u t e r \0ll+1l+2……l+8图2-2-14顺序存储r的串2.串的链式存储链表存储串值时,由于串中每个数据元素是一个字符，因而存在一个结点大小的选择问题，即结点中是存放一个字符，还是存放多个字符.结点大小的选择直接影响对串和处理效率。结点越小，串处理越方便，但所占内存也随之扩大。反之，结点越大，串处理越不方便，但可以节省内存。串的根本运算一.求串的长度main(){longle;longlen(char[]);chars[30];scanf("%s",s);le=len(s);printf("len(s)=%d\n",le);}longlen(chars[]){longi=0;while(s[i]!='\0')i++;returni;}二.求子串sub(s,m,n)求串s的第m位置开始且长度为n的子串。三.求子串t在主串s中的位置index(s,t)从主串S的第一个字符起和模式t的另一个字符比较，假设相等，那么继续逐个比较后继字符，如果全部相等，那么匹配成功，返回子串的位置。否那么从S的第二个字符起重新开始新的比较，直至某一步匹配成功或S结束，无法再进行比较为止，此时返回-1作为匹配失败的标志。index(chars[],chart[]){inti=0,j=0;while(s[i]!='\0'&&t[j]!='\0'){if(s[i]==t[j]){i=i+1;j=j+1;}else{i=i-j+1;j=0;}}if(t[j]=='\0')return(i-j);elsereturn(-1);}四.字符串置换rep(s,t,v)以串v的值替换所有在串s中出现的子串t的值。五.字符串连接char*concat(char*s1,char*s2){char*p;p=s1;while(*p++);--p;while(*p++=*s2++);return(s1);}六.字符串比较intcmp(chars1[],chars2[]){inti=0,r;while(s1[i]==s2[i]&&s1[i]!='\0')i++;if(s1[i]=='\0'&&s2[i]=='\0')r=0;elser=s1[i]-s2[i];return(r);}以下是C语言提供的一些有关字符串的库函数：unsignedstrlen(char*str) /*字符串长度函数*/char*strcat(char*str1,char*str2)/*连接函数*/char*strcpy(char*str1,char*str2)/*拷贝函数*/

树的根本概念树的根结点:是树中一个特定的结点，它是没有前趋的结点。结点的度:树中每个结点拥有的子树的数目。度为0的结点为终端结点或叶子。度不为0的结点称为非终端结点或分支结点。树中各结点度的最大值称为树的度。子女与双亲:兄弟:同一双亲的各子女间互称为兄弟。树的高度(或深度):树中结点的最大层次。有序树和无序树:m(m>0)棵互不相交的树的集合，称为森林。树结构有广泛的应用，经常被用来定义层次关系。/*-*+5ABCD2用树表示家庭结构老张张一张二张小一张小二张小三2.3.3二叉树1.二叉树的概念：二叉树定义为：或为空，或由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。二叉树不是树的特殊情况。它们之间最重要的区别是：二叉树的结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。二叉树允许空.而一般的树至少有一个结点。完全二叉树(见后图)一棵二叉树，假设所有的结点其度数或者为0，或者为2，那么称为完全二叉树。满二叉树：深度为K且有2K-1个结点的二叉树称为满二叉树。此时，每一层上的结点数都是该层上的最大结点数。顺序二叉树：一棵深度为K的二叉树，如果它的叶结点都在第K层或第K-1层上，且对任一结点，假设其右子树中有叶结点在第K层，那么其左子树的叶结点都应在第K层。从上述定义可以看出，如果对一棵深度为K的满二叉树和一棵深度为K，具有相同个结点的完全二叉树从根结点开始，从上到下，从左到右进行连续编号那么相同位置上结点的编号完全相同。完全二叉树满二叉树顺序二叉树2.二叉树的性质性质1在二叉树中,第i层最多有2i-1个结点。性质2在深度为K的二叉树中,结点总数最多为2K-1个，K≥1。性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2,那么n0=n2+1。设n1为二叉树T度为1的结点数。因为二叉树T中结点的度数均小于或等于2，所以其结点总数为:n=n0+n1+n2(1)设m为二叉树T中总的分支数目。因为除根结点外，其余结点都有一个分支进入，所以m=n-1。但这些分支是由度为1或2的结点射出的，所以m=n1+2n2,于是得n=n1+2n2+1(2)由(1)式和(2)式得n0=n2+1性质4具有n个结点的顺序二叉树的深度为[log2n]+1。假设树的深度为K。那么根据性质2和顺序二叉树为定义，有2K-1-1<n≤2k-1或2K-1≤n<2k于是K-1≤log2n<K因为K是整数所以K=[log2n]+1性质5如果对一棵有n个结点的顺序二叉树的结点自上而下，自左至右连续地从1开始编号，那么对任一结点i(1≤i≤n),有1)如果i=1，那么结点i是二叉树的根，无双亲；如果i>1，那么其双亲结点数是[i/2]。2)如果2i>n，结点i无左孩子(此时结点i为叶子)；否那么其左孩子是结点2i。3)如果2i+1>n,结点i无右孩子；否那么其孩子是结点2i+1。3.二叉树的存储结构〔1〕二叉树的顺序存储用一组连续的存储单元存储顺序二叉树中的数据元素，编号为i的结点的数据元素存放在相应向量中序号为i的位置上。根据二叉树性质5，结点i的双亲存放在序号为[i/2]的位置上，结点i的左、右孩子(如果有的话)将依次存放在序号为2i和2i+1的位置上。这种方法对于一般二叉树空间浪费大，特别是单支树。〔2〕二叉树的链式存储方式当用链表表示二叉树时，结点至少包含数据域、左指针域和右指针域，其结点binode结构如下:structbinode{intdata;structbinode*lchild;structbinode*rchild;}ABDECFGABCDEFG00000000T链表中会有许多空指针。4.二叉树的遍历所谓二叉树的遍历，是指树的每个结点按某种规律恰好被处理〔访问〕一次的过程。二叉树的遍历是一种最根本的算法。其含义是逐一访问树中的各结点，且只访问一次。从二叉树的递归定义可知，二叉树是由三个根本单元组成，即根结点(D)，左子树(L)，右子树(R)。因此，假设能依次遍历这三局部，便是遍历了整个二叉树。根据排列组合，共有六种方案，即DLR，LDR，LRD，DRL，RDL，RLD。假设对左右子树的访问次序限定是先左后右，那么只有前三种情况，分别称为先序遍历，中序遍历和后序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。遍历二叉树的递归算法：三种方法：先序遍历：假设二叉树空，那么空操作：否那么：(1)处理根(2)按先序遍历左子树(3)按先序遍历右子树中序遍历：假设二叉树空，那么空操作：否那么：(1)按中序遍历左子树(2)处理根(3)按中序遍历右子树后序遍历：假设二叉树空，那么空操作：否那么：(1)按后序遍历左子树(2)按后序遍历右子树(3)处理根ABDEFGCHI对左图的三种遍历：先序：ABDEHICFG中序：DBHEIAFCG后序：DHIEBFGCA先序遍历:ABDEGCF；中序遍历:DBGEACF；后序遍历:DGEBFCA。假设二叉树采用链式存储结构，结点为:structbinode{intdata;structbinode*lchild;structbinode*rchild;}二叉树的先序遍历算法的递归过程描述如下:preorder(structbinode*t)/*先序遍历*/{while(t!=NULL){printf("%d\n",t->data);/*处理根结点*/preorder(t->lchild);/*遍历左子树*/preordee(t->rchild);/*遍历右子树*/}}二叉树的中序遍历算法的递归过程描述如下:midorder(structbinode*t)/*中序遍历*/{while(t!=NULL)

{midorder(t->lchild);/*遍历左子树*/printf("%d\n",t->data);midordee(t->rchild);/*遍历右子树*/

}

}递归形式的算法描述过程精练，算法的正确性也容易得到证明。缺点：一是执行效率较低；二是要求编写程序用的高级语言允许过程递归调用。二叉树先序遍历的非递归的过程描述如下：〔此时需要用到栈。用指针数组a表示栈，记下尚待遍历的子树根结点指针，这也是栈的一种典型应用。〕ppreorder(structbinode*t){inti=0;structbinode*a[]，*p;a[0]=t;while(i>=0){p=a[i];printf("%d\n",p->data);/*处理根结点*/i--;if(p->rchild!=NULL){i++;a[i]=p->rchild;}/*假设右指针不为空，那么进栈*/if(p->lchild!=NULL){i++;a[i]=p->lchild;}/*假设左指针不为空，那么进栈*/}}二叉树中序遍历的非递归的过程描述如下：〔此时用到栈为链接栈。栈用于存放正在遍历的子树根结点指针。〕structsnode{structbinode*addr;structsnode*link;//定义链栈};midorder(structbinode*t)//t为树根{structsnode*top,*p;//链栈指针top=NULL;while(t!=NULL||top!=NULL){while(t!=NULL){p=(structsnode*)malloc(sizeof(structsnode));p->addr=t;p->link=top;top=p;t=t->lchild;}if(top!=NULL){t=top->addr;printf(“%c〞,t->data);p=top;top=top->link;free(p);t=t->rchild;}}}实例：先建立一