C语言教程.doc

C语言公共知识基础第1章 数据结构第1节 数据结构的基本概念 定义： 是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构具体指同一类数据元素中，各元素之间的相互关系，用前后件来表示，数据结构包括三个组成成分，数据的逻辑结构，数据的存储结构（数据逻辑结构在计算机中的存储形式，也称数据物理结构）和数据运算结构（插入和删除为其基本运算，还有查找，分裂，合并，分解，复制和修改等功能）。数据结构的图形表示夏的后件秋的前件春夏秋冬 图1.1 每一个元素用中间标有元素值的方框表示，称为数据结点，简称结点。用一条有向线段从前件结点指向后件结点。表示是一种顺序关系。在数据结构中，没有前件的结点称为根节点，没有后件的结点称为终端节点（也称叶子节点）。其他结点一般称为内部结点。线性表及其顺序存储结构定义：线性表是一个线性结构，它是一个含有n0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,kn，其中k1是开始结点，kn是终端结点。 特征：1集合中必存在唯一的一个“第一元素”； 2集合中必存在唯一的一个 “最后元素” ； 3除最后一个元素之外，均有 唯一的后继(后件)； 4除第一个元素之外，均有 唯一的前驱(前件)。线性表中结点的个数n称为线性表的长度，n为0称为空表 129292918a18871856a56185663a63266335a35633524a24352431a31243147a473147a47 线性表的顺序存储结构存储结构的存储特点：1线性表中所有元素所占的存储空间是连续的；2. 表中各元素的在空间存储位置是按逻辑顺序依次存放的线性表的插入运算要在第i个元素前插入一个新元素，要从最后一个元素开始，直到第n-i+1个元素依次向后移动一个位置，第i个位置就会被空出，然后将新元素插入第i项（见图 ）数据的删除运算要删除第i个元素，要从第i+1个元素开始，直到n个元素之间共n-1个元素依次向前移动一个位置（见图 ）常用数据结构：1. 数组 在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。（在c语言教程中有详细的解释）2. 栈 是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。3. 队列 一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作（故体现先进先出的原则，亦称先来先服务）。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列4. 线性链表（也称链表） 是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。数据域指针域在线性链表中，各数据元素之间的前后件关系有各结点的指针域来表示，指向第一个结点的指针HEAD称为头指针(如date 1)。Data2Date3Date n5. 树 是包含n（n0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件： （1）有且仅有一个结点 k0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。 （2）除K0外，k中的每个结点，对于关系N来说有且仅有一个前驱。（3）K中各结点，对关系N来说可以有m个后继（m=0）。空集合也是树，称为空树。空树中没有结点。关于树的术语： 节点的度：一个节点含有的子树的个数称为该节点的度； 叶节点或终端节点：度为零的节点称为叶节点； 非终端节点或分支节点：度不为零的节点； 双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点； 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 兄弟节点：具有相同父节点的节点互称为兄弟节点； 树的度：一棵树中，最大的节点的度称为树的度； 节点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推； 树的高度或深度：树中节点的最大层次； 堂兄弟节点：双亲在同一层的节点互为堂兄弟； 节点的祖先：从根到该节点所经分支上的所有节点； 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。 森林：由m（m=0）棵互不相交的树的集合称为森林；树的种类：无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树; 有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树； 二叉树：每个节点最多含有两个子树的树称为二叉树； 完全二叉树 ：除最后一层外，每一层的所有子节点均达到最大值，在最后一层只缺少右边若干个子节点。满二叉树 ：除最后一层外，每一层上的所有节点都有两个子节点，即每一层上的节点数均达到最大值。满二叉树的第k层上有2k-1个子节点，深度为m的二叉树有2m-1个子节点。 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树； 6. 图 图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系7. 堆 在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆8. 散列表 在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆9. 查找技：在某个指定的数据结构中查找某个特定的元素。 1.顺序查找：按照从前到后的顺序依次比对，找出目标元素。 2.二分法查找：如数学上使用的二分法相似10排序方法（1） 交换类排序法：冒泡法（详见C语言程序设计教程） 快速排序法（2） 插入类排序法：简单插入排序法，希尔排序法。（3） 选择类排序法：扫描整个线性列表，从中选出最小元素，将它交换到表的最前面，然后对剩下的子表采取同样的方法以上排序方法中，冒泡排序，快速排序，简单插入排序的运算次数最大值为n（n-1)/2次第2章 程序设计基础第1节 程序设计方法与风格结构化程序设计：是以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模块，1. 采用自顶向下，逐步求精的程序设计方法，在需求分析，概要设计中，都采用了自顶向下，逐层细化的方法。 2.使用三种基本控制结构构造程序，任何程序都可由顺序、选择、重复三种基本控制结构构造。 (1)用顺序方式对过程分解，确定各部分的执行顺序。 (2)用选择方式对过程分解，确定某个部分的执行条件。 (3)用循环方式对过程分解，确定某个部分进行重复的开始和结束的条件。 (4)对处理过程仍然模糊的部分反复使用以上分解方法，最终可将所有细节确定下来。 3.主程序员组的组织形式 指开发程序的人员组织方式应采用由一个主程序员（负责全部技术活动）、一个后备程序员（协调、支持主程序员）和一个程序管理员（负责事务性工作，如收集、记录数据，文档资料管理等）三个为核心，再加上一些专家（如通信专家、数据库专家）、其他技术人员组成小组。顺序结构，选择结构，循环型结构，（当型循环，直到型循环）均属于结构化设计方法面向对象程序设计：通过对象的事件的控制程序的执行。名词解释：对象：用来描述个客观事实的一个实体，它由一组静态特征的属性和它可执行的一组操作组成。类和实例：类是具有共同属性，共同方法的对象的集合。类是对象的抽象，对象是其对应类的一个实例。继承：是使用已有的类定义作为其基础建立新类的定义技术。多态性：同样的信息被不同的对象接受时可导致完全不同的行动。方法：对象的所有操作。对象的特点：分类性 多态性 封装性 模块独立性好程序设计风格：编写程序所表现的特点、习惯和逻辑思路。其风格整体而言强调简单清晰，程序必须是可以理解的。既清晰第一，效率第二。第3章 软件工程基础第1节 软件工程的基本概念软件 定义：软件是用户与硬件之间的接口界面。用户主要是通过软件与计算机进行交流1. 运行时，能够提供所要求功能和性能的指令或计算机程序集合。 2程序能够满意地处理信息的数据结构。 3描述程序功能需求以及程序如何操作和使用所要求的文档。 以开发语言作为描述语言，可以认为： 软件=程序+数据+文档。软件分类：一般来讲软件被划分为系统软件、应用软件,其中系统软件包括操作系统和支撑软件（包括微软发布的嵌入式系统，即硬件级的软件，使电脑及其它设备运算速度更快更节能）系统软件：系统软件为计算机使用提供最基本的功能，可分为操作系统和支撑软件，其中操作系统是最基本的软件系统软件是负责管理计算机系统中各种独立的硬件，使得它们可以协调工作。系统软件使得计算机使用者和其他软件将计算机当作一个整体而不需要顾及到底层每个硬件是如何工作的1操作系统是一管理计算机硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让使用者与系统交互的操作接口。 2支撑软件是支撑各种软件的开发与维护的软件,又称为软件开发环境（SDE）。它主要包括环境数据库、各种接口软件和工具组。应用软件：定义：为了某种特定的用途而被开发的软件。它可以是一个特定的程序，比如一个图像浏览器。也可以是一组功能联系紧密，可以互相协作的程序的集合，比如微软的Office软件。也可以是一个由众多独立程序组成的庞大的软件系统，比如数据库管理系统。软件特点是一种逻辑实体，不是物理实体，具有抽象性。生产方式与硬件不同，没有明显制作过程，一旦开发成功，可以大量拷贝在运行过程中不存在任何磨损和老化问题软件开发、运行对计算机有极强的依赖性软件复杂程度高，成本昂贵名词解释软件危机：计算机软件的开发和维护过程中所遇到的一系列严重问题软件生命周期：软件产品提出实现使用维护到停止使用退役的过程。其过程大致如下可行性研究和计划制定；需求分析；软件设计；软件实现；软件实现；软件测试；运行和维护软件工程的目标：在给定成本、进度的前提下，开发出具有有效性，可行性、可理解性、可维护性、可适应性、可移植性和可操作性且满足用户需求的产品第二节结构化分析方法需求分析和需求分析方法定义：用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。任务：发现需求、求精、建模、定义需求的产品工作：（1）需求获取：确定对目标系统各个方面的需求。 （2）需求分析；对获取的需求进行分析和综合，最终给出系统的解决方案和目标系 统的逻辑模型。（3）编写规格说明书（4）需求评审需求分析方法：结构化分析方法 面向对象分析方法结构化分析方法定义：结构化程序设计理念在软件需求分析阶段的应用一般步骤如下：（1） 通过对用户的调查，获得当前系统的具体模型（2） 根据具体模型，抽象出当前系统的逻辑模型。（3） 根据计算机的特点，建立目标系统的逻辑模型。（4） 写出目标软件规格需求说明书。（5） 评审直到确认完全符合用户对软件的需求结构化分析常用工具（1） 数据流程图：是描绘数据处理过程的工具，是需求理解逻辑模型的图形表示 ，数据流程图的主要图形元素与说明如下：建立数据流程图的步骤：由外向里；自顶向下；逐层分解。数据字典：对所有与形同有关的数据有关组织的一个列表，以及精确地严格的定义。数据字典作用是对数据流程图中出现的被命名的图形元素的精确解释软件需求规格说明书定义：作用：（1）便于用户、开发人员进行交流和理解。（2）反映出用户的问题的结构，可以作为软件开发的基础和依据。（3）作为确认测试和验收的依据。设计原则 使每个模块执行一个功能（坚持功能性内聚） 每个模块用过程语句（或函数方式等）调用其他模块与 模块间传送的参数作数据用与 模块间共用的信息（如参数等）尽量少第三节软件设计的概念从技术的角度来看，软件设计包括：软件结构设计，数据设计，接口设计，过程设计。从工程管理的角度来讲，软件设计分为两步：概要设计和详细设计。软件设计的基本原理：1抽象 2模块化 3信息隐蔽 模块独立性.内聚性：一个模块内部各个元素见彼此紧密程度的度量。耦合性：模块间互相连接紧密程度的度量。一般优秀的软件要求做到：高内聚，低耦合。二 概要设计 任务：设计软件系统结构：在需求分析阶段，已经把系统分解层次结构，在概要设计阶段，需要进一步分解，划分为模块以及模块的层次结构。（2) 数据结构和数据库设计（3) 编写概要设计文档。（4) 概要设计文档评审。3、 详细设计任务：为软件结构图中的每一个模块确定实现算法扥局部数据结构，用某种选定的表达工具表示算法和数据结构的细节第4节 软件测试1、 目的：使用人工手段或自动手段来运行或测试某个系统的过程，目的是在于检验它是否规定的需求或是弄清预期结果与实际结果之间的差别。测试要以查找错误为中心，而不是为了演示软件的正确功能。2、 软件测试的准则（1） 所有测试都应追溯到需求。（2） 严格执行测试计划，排除实验的随意性（3） 程序员应避免检验自己的程序（4） 妥善保管测试计划、测试用例、出错统计和最终的分析报告，为维护提供方便软件测试具体内容软件测试主要工作内容是验证(verification)和确认(validation )，下面分别给出其概念： 验证(verification)是保证软件正确地实现了一些特定功能的一系列活动， 即保证软件以正确的方式来做了这个事件(Do it right) 1.确定软件生存周期中的一个给定阶段的产品是否达到前阶段确立的需求的过程 2.程序正确性的形式证明，即采用形式理论证明程序符合设计规约规定的过程 3.评市、审查、测试、检查、审计等各类活动，或对某些项处理、服务或文件等是否和规定的需求相一致进行判断和提出报告。 确认(validation)是一系列的活动和过程，目的是想证实在一个给定的外部环境中软件的逻辑正确性。即保证软件做了你所期望的事情。(Do the right thing) 1.静态确认，不在计算机上实际执行程序，通过人工或程序分析来证明软件的正确性 2.动态确认，通过执行程序做分析，测试程序的动态行为，以证实软件是否存在问题。 软件测试的对象不仅仅是程序测试，软件测试应该包括整个软件开发期间各个阶段所产生的文档，如需求规格说明、概要设计文档、详细设计文档，当然软件测试的主要对象还是源程序。三 软件测试技术及方法从是否需要执行被测试的角度分为:静态测试和动态测试按照功能划分为白盒测试、黑盒测试和灰盒测试。名词解释：静态测试 指不运行被测程序本身，仅通过分析或检查源程序的语法、结构、过程、接口等来检查程序的正确性。对需求规格说明书、软件设计说明书、源程序做结构分析、流程图分析、符号执行来找错。静态测试包括代码检查、静态结构分析、代码质量度量等。优点：静态测试具有的发现缺陷早、降低返工成本、覆盖重点和发现缺陷的概率高的优点以及耗时长、不能测试依赖和技术能力要求高的缺点。动态测试：指通过运行被测程序，检查运行结果与预期结果的差异，并分析运行效率和健壮性等性能，这种方法由三部分组成：构造测试实例、执行程序、分析程序的输出结果。步骤：单元测试 是对软件中的基本组成单位进行测试，其目的是检验软件基本组成单位的正确性。集成测试 是在软件系统集成过程中所进行的测试，其主要目的是检查软件单位之间的接口是否正确。在实际工作中，我们把集成测试分为若干次的组装测试和确认测试。系统测试是对已经集成好的软件系统进行彻底的测试，以验证软件系统的正确性和性能等满足其规约所指定的要求。是验收测试 软件在投入使用之前的最后测试。是购买者对软件的试用过程。验收测试是黑盒测试。回归测试 是软件维护阶段，其目的是对验收测试结果进行验证和修改。 白盒测试：也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来 检测产品内部动作是否按照设计规格说明书的规定正常进行，检验程序中的每条通路是否都 能按预定要求正确工作。白盒的测试用例需要做到： 保证一个模块中的所有独立路径至少 被使用一次 对所有逻辑值均需测试 true 和 false 在上下边界及可操作范围内运行所有循环 检查内部数据结构以确保其有效性白盒测试实施步骤：1.测试计划阶段：根据需求说明书，制定测试进度。 2.测试设计阶段：依据程序设计说明书，按照一定规范化的方法进行软件结构划分和设计测试用例。 3.测试执行阶段：输入测试用例，得到测试结果。 4.测试总结阶段：对比测试的结果和代码的预期结果，分析错误原因，找到并解决错误黑盒测试：也称功能测试，它是通过测试来检测每个功能是否都能正常使用。在测试中，把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试着眼于程序外部结构，不考虑内部逻辑结构，主要针对软件界面和软件功能进行测试。一般作用为黑盒测试法注重于测试软件的功能需求，主要试图发现下列几类错误。 功能不正确或遗漏； 界面错误； 数据库访问错误； 性能错误； 初始化和终止错误等灰盒测试：灰盒测试关注输出对于输入的正确性，同时也关注内部表现，但这种关注不象白盒那样详细、完整，只是通过一些表征性的现象、事件、标志来判断内部的运行状态第五节程序的调试定义：是将编制的程序投入实际运行前，用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。软件测试贯穿软件的生命周期，而程序调试主要在开发阶段。程序调试主要分一下两个部分构成：（1） 根据错误的迹象确定程序中错误的确切性质、原因和位置。（2） （2）对程序进行修改，排除这个错误。（3） 程序调试的步骤：错误定位修改设计和代码，以排除错误进行回归调试，防止引进新错误（4） 程序调试方法：强行排错法回溯法原因排除法第4章 数据库设计基础第1节 数据库系统的基本概念数据（date) 描述事物的符号纪录数据库（datebase) 长期保存在计算机内，有组织，可共享的数据集合。数据库管理系统（datebase management system）对数据库进行管理和维护的系统软件。具有定义、操纵数据库，数据控制，故障恢复为完成以上功能，DBMS提供了相应的语言：（1）数据定义语言（DDL)：定义数据模式（2）数据操纵语言（DML)：查询，添加，删除，修改。（3）数据控制语言（DCL）：负责数据完整性、安全性、并发控制以及故障恢复。数据库管理员（datebase Adminstrator,)其主要工作如下：数据库设计数据库的维护改善系统性能，提高系统效率。数据库系统的构成：数据库（数据）数据库管理系统数据库管理员硬件：计算机、网络软件：操作系统，数据库系统开发工具，接口软件。数据库系统的发展（1） 人工管理阶段（2） 文件系统阶段：数据共享性差、独立性差、冗余性大。（3） 数据系统阶段：数据共享性好、独立性强、冗余度小。数据库系统基本特点：数据的集成性数据高共享性与低冗余性数据的独立性强数据的统一管理与控制。数据系统内部的三级结构：概念模式(Conceptual Schema)是数据库中全部数据的整体逻辑结构的描述。它由若干个概念记录类型组成，还包含记录间联系、数据的完整性、安全性等要求。描述概念模式的数据定义语言称为“模式DDL”。一个数据库只有一个逻辑模式。外模式又称子模式 是用户与数据库系统的接口，是用户用到的那部分数据的描述。它由若干个外部记录类型组成。 它是某个或某几个用户所看到的数据库的数据视图，是与某一应用有关的数据的逻辑表示。外模式是从模式导出的一个子集，包含模式中允许特定用户使用的那部分数据。用户可以通过外模式描述语言来描述、定义对应于用户的数据记录(外模式)，也可以利用数据操纵语言(DML)对这些数据记录进行。外模式反映了数据库的用户观。内模式又称存储模式，对应于物理级，它是数据库中全体数据的内部表示或底层描述，是数据库最低一级的逻辑描述，它描述了数据在存储介质上的存储方式翱物理结构，对应着实际存储在外存储介质上的数据库。内模式由内模式描述语言来描述、定义所有内部记录类型、索引和文件的组织方式，以及数据控制方面的细节，它是数据库的存储观。 是数据物理结构和存储方式的描述 是数据在数据库内部的表示方式 记录的存储方式（顺序存储，按照B树结构存储，按hash方法存储） 索引的组织方式 数据是否压缩存储 数据是否加密 数据存储记录结构的规定 一个数据库只有一个内模式 能够给出数据库物理存储结构与物理存取方法数据库系统的两级映射概念模式到内模式的映射外模式到概念模式的映射第2节 数据模型数据模型（Data Model）是数据特征的抽象，是数据库管理的教学形式框架。数据库系统中用以提供信息表示和操作手段的形式构架。数据模型包括数据库数据的结构部分、数据库数据的操作部分和数据库数据的约束条件数据模型所描述的内容包括三个部分：数据结构、数据操作、数据约束。1） 数据结构:数据模型中的数据结构主要描述数据的类型、内容、性质以及数据间的联系等。数据结构是数据模型的基础，数据操作和约束都建立在数据结构上。不同的数据结构具有不同的操作和约束。 2）数据操作:数据模型中数据操作主要描述在相应的数据结构上的操作类型和操作方式。 3）数据约束：数据模型中的数据约束主要描述数据结构内数据间的语法、词义联系、他们之间的制约和依存关系，以及数据动态变化的规则，以保证数据的正确、有效和相容。数据模型按不同的应用层次分成三种类型：分别是概念数据模型、逻辑数据模型、物理数据模型数据库领域采用的数据模型有层次模型、网状模型和关系模型层次模型：用树型（层次）结构表示实体类型及实体间联系的数据模型称为层次模型(Hierarchical Model)。 层次模型是指用树行结构表示实体及其之间的联系，树中每一个节点代表一个记录类型，树状结构表示实体型之间的联系。 在一个层次模型中的限制条件是：有且仅有一个节点，无父节点，此节点为树的根；其他节点有且仅有一个父节点。 层次模型的特点：记录之间的联系通过指针实现，查询效率高。网状模型：用有向图结构表示实体类型及实体间联系的数据结构模型称为网状模型（Network Model）。关系数据库模型：用二维表的形式表示实体和实体间联系的数据模型构E-R模型结E-R模型的构成成分是实体集、属性和联系集，其表示方法如下： （1） 实体集用矩形框表示，矩形框内写上实体名。 （2） 实体的属性用椭圆框表示，框内写上属性名，并用无向边与其实体集相连。 （3） 实体间的联系用菱形框表示，联系以适当的含义命名，名字写在菱形框中，用无向连线将参加联系的实体矩形框分别与菱形框相连，并在连线上标明联系的类型，即